1

我一直在研究 C 中的银行家算法实现，它似乎工作正常，除了分配矩阵没有正确添加值。在请求资源函数中，我在开头使用互斥锁并在返回值之前解锁以指示通过或失败。在函数本身中，分配矩阵会根据请求和给定的内容进行更新，但是当另一个线程进入并发出请求时，分配会重置并再次开始添加。我不确定为什么会这样，因为分配是全局的，就像函数中正在修改的其他结构一样，它们正在正确更新值。

    #include<stdio.h>
    #include<stdlib.h>
    #include<unistd.h>
    #include<pthread.h>
    #include<semaphore.h>


    /* these may be any values >= 0 */

    #define NUMBER_OF_CUSTOMERS 5
    #define NUMBER_OF_RESOURCES 3

    /* the available amount of each resource */
    int available[NUMBER_OF_RESOURCES];

    /*the maximum demand of each customer */
    int maximum[NUMBER_OF_CUSTOMERS][NUMBER_OF_RESOURCES];

    /* the amount currently allocated to each customer */
    int allocation[NUMBER_OF_CUSTOMERS][NUMBER_OF_RESOURCES];

    /* the remaining need of each customer */
    int need[NUMBER_OF_CUSTOMERS][NUMBER_OF_RESOURCES];


    pthread_mutex_t mutex =
    PTHREAD_MUTEX_INITIALIZER;

    struct threadParams {
        int req[3];
        int threadNum;
    };

        int safe_state(int customer_num){

            int work[NUMBER_OF_RESOURCES];
            int done =0;
            for(int w = 0; w < NUMBER_OF_CUSTOMERS; w++){
                work[w] = available[w];
            }

            int finish[NUMBER_OF_CUSTOMERS];

            for(int i = 0; i < NUMBER_OF_CUSTOMERS; i++){
                finish[i] = 0;
                //setting finish to false
            }

            for(int k = 0; k < NUMBER_OF_CUSTOMERS; k++){
                for(int j = 0; j< NUMBER_OF_RESOURCES; j++){
                    if(finish[k] == 0 && need[customer_num][k] <= work[j]){
                        work[j] += allocation[customer_num][j];
                        finish[k] = 1;
                        //printf("%d\n", finish[k]);
                    }
                }
            }

            for(int x = 0; x < NUMBER_OF_CUSTOMERS; x++){
                if(finish[x] == 1){
                    done = 1;
                }
                else{
                    done = -1;
                }
            }
            if(done == 1){
                printf("\n Granted\n");
                return done;
            }
            printf("\nDenied\n");
            return done;

        }


        void* request_resources(void *arg){
            pthread_mutex_lock(&mutex);
            struct threadParams  *params = arg;
            int customer_num = params->threadNum;
            printf("\nCustomer %d is in critical\n", customer_num+1);           
            int request[3];
            request[0] = params->req[0];
            request[1] = params->req[1];
            request[2] = params->req[2];

            int pass;
            for(int i = 0; i < NUMBER_OF_RESOURCES; i++){
                if(request[i] <= need[customer_num][i] && request[i] <= available[i]){
                    //printf("\nreq: %d, need: %d, avail: %d, alloc: %d\n\t", request[i], need[customer_num][i], available[i],allocation[customer_num][i]);                 
                    int state = safe_state(customer_num);

                    if(state == 1){
                        available[i] -= request[i];
                        allocation[customer_num][i] += request[i];
                        //printf("%d + %d\n", allocation[customer_num][i], request[i]);
                        need[customer_num][i] -= request[i];
                        pass = 1;

                    }
                    else if(state == -1){
                        printf("\nThe request from customer %d results in unsafe state\n", customer_num+1);
                        printf("\nreq: %d, need: %d, avail: %d, alloc: %d\n\t", request[i], need[customer_num][i], available[i],allocation[customer_num][i]);                                                       
                        pass = -1;
                        break;
                    }
                }
                else{
                    printf("\nreq: %d, need: %d, avail: %d\n", request[i], need[customer_num][i], available[i]);
                    printf("\nNot enough resources for customer %d's request or the customer doesn't need this resource.\n", customer_num);
                    pass = -1;
                    break;
                }
                printf("\nResource: %d req: %d, need: %d, avail: %d, alloc: %d\n\t",i+1, request[i], need[customer_num][i], available[i],allocation[customer_num][i]);                              

            }
            //printf("I'm a thread\n");
            pthread_mutex_unlock(&mutex);
            printf("\n Customer %d has left critical\n", customer_num+1);
            return pass;

        } 

        int release_resources(int customer_num, int release[]){

        }




    int main(int argc, char *argv[]){
        pthread_t threads [NUMBER_OF_CUSTOMERS];
        int result;
        unsigned index = 0;


        // for(int ii = 0; ii < NUMBER_OF_CUSTOMERS; ii++){
            // for(int jj = 0; jj < NUMBER_OF_RESOURCES; jj++){
                // allocation[ii][jj] += 0;
            // }
        // }    

        for(index = 0; index < NUMBER_OF_RESOURCES; index++){
            available[index] = strtol(argv[index+1], NULL,10);
        }

        for(int i = 0; i < NUMBER_OF_CUSTOMERS; i++){
            for(int j = 0; j < NUMBER_OF_RESOURCES; j++){
            maximum[i][j] = strtol(argv[j+1], NULL, 10)-4;
            need[i][j] = 2; //strtol(argv[j+1], NULL, 10) - 6;
            //printf("%d\t", maximum[i][j]);
            }
        }


        for(index = 0; index < NUMBER_OF_CUSTOMERS; index++){
            printf("\nCreating customer %d\n", index+1);
            struct threadParams params;
            params.req[0] = 2;
            params.req[1] = 2;
            params.req[2] = 2;
            params.threadNum = index;
            result = pthread_create(&threads[index],NULL,request_resources,&params);    

        }

        for(index = 0; index < NUMBER_OF_CUSTOMERS; ++index){
            pthread_join(threads[index], NULL);
        }

        printf("\nDone");

    }
4

2 回答 2

2

在我修复了一些问题后，我得到了一个正在运行的版本：

#ifdef __cplusplus
#include <cstdio>
#include <cstdlib>
#include <mutex>
#include <thread>
using namespace std;
#else /* (not) __cplusplus */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>
#endif /* __cplusplus */

/* these may be any values >= 0 */

#define NUMBER_OF_CUSTOMERS 5
#define NUMBER_OF_RESOURCES 3

/* the available amount of each resource */
static int available[NUMBER_OF_RESOURCES];

/*the maximum demand of each customer */
static int maximum[NUMBER_OF_CUSTOMERS][NUMBER_OF_RESOURCES];

/* the amount currently allocated to each customer */
static int allocation[NUMBER_OF_CUSTOMERS][NUMBER_OF_RESOURCES];

/* the remaining need of each customer */
static int need[NUMBER_OF_CUSTOMERS][NUMBER_OF_RESOURCES];

struct ThreadParams {
  int req[3];
  int threadNum;
};

typedef void* (*PThreadFunc)(void*);

#ifdef __cplusplus
/* multi-threading thin layer for C++ and std::thread */
static mutex mtx;
static inline void lockMutex(mutex *pMtx) { pMtx->lock(); }
static inline void unlockMutex(mutex *pMtx) { pMtx->unlock(); }
typedef std::thread Thread;
static inline int startThread(
  Thread *pThread,
  void* (*pThreadFunc)(ThreadParams*), ThreadParams *pThreadParams)
{
  return (*pThread = Thread(pThreadFunc, pThreadParams)).get_id()
    == Thread::id();
  /* thread creation failed -> thread id == thread::id() -> 1
   * thread creation successful -> thread id != thread::id() -> 0
   */
}
static inline void joinThread(Thread *pThread) { pThread->join(); }
#else /* (not) __cplusplus */
/* multi-threading thin layer for C and pthread */
pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
static void lockMutex(pthread_mutex_t *pMtx)
{
  pthread_mutex_lock(pMtx);
}
static void unlockMutex(pthread_mutex_t *pMtx)
{
  pthread_mutex_unlock(pMtx);
}
typedef pthread_t Thread;
static int startThread(
  Thread *pThread,
  void* (*pThreadFunc)(struct ThreadParams*),
  struct ThreadParams *pThreadParams)
{
  return pthread_create(pThread, NULL,
    (void*(*)(void*))pThreadFunc, pThreadParams);
}
static void joinThread(Thread *pThread) { pthread_join(*pThread, NULL); }
#endif /* __cplusplus */

static int safe_state(int customer_num)
{
  int work[NUMBER_OF_RESOURCES];
  for (int i = 0; i < NUMBER_OF_RESOURCES; ++i) {
    work[i] = available[i];
  }

  int finish[NUMBER_OF_CUSTOMERS];
  for(int i = 0; i < NUMBER_OF_CUSTOMERS; ++i) {
    finish[i] = 0;
    //setting finish to false
  }

  for (int k = 0; k < NUMBER_OF_CUSTOMERS; ++k) {
    for (int j = 0; j < NUMBER_OF_RESOURCES; ++j) {
      if (finish[k] == 0 && need[customer_num][k] <= work[j]) {
        work[j] += allocation[customer_num][j];
        finish[k] = 1;
        //printf("%d\n", finish[k]);
      }
    }
  }

  int done = 0;
  for (int x = 0; x < NUMBER_OF_CUSTOMERS; ++x) {
    done = finish[x] ? 1 : -1;
  }
  if (done) printf("Granted\n");
  else printf("Denied\n");
  return done;
}

static void* request_resources(struct ThreadParams *params)
{
  lockMutex(&mtx);
  int customer_num = params->threadNum;
  printf("Customer %d is in critical\n", customer_num+1);           
  int request[3];
  request[0] = params->req[0];
  request[1] = params->req[1];
  request[2] = params->req[2];
  int pass;
  for (int i = 0; i < NUMBER_OF_RESOURCES; ++i) {
    if (request[i] <= need[customer_num][i] && request[i] <= available[i]) {
      //printf("\nreq: %d, need: %d, avail: %d, alloc: %d\n\t", request[i], need[customer_num][i], available[i],allocation[customer_num][i]);                 
      int state = safe_state(customer_num);

      if (state == 1) {
        available[i] -= request[i];
        allocation[customer_num][i] += request[i];
        //printf("%d + %d\n", allocation[customer_num][i], request[i]);
        need[customer_num][i] -= request[i];
        pass = 1;
      } else if (state == -1) {
        printf("The request from customer %d results in unsafe state\n",
          customer_num + 1);
        printf("req: %d, need: %d, avail: %d, alloc: %d\n",
          request[i], need[customer_num][i], available[i],
          allocation[customer_num][i]);
        pass = -1;
        break;
      }
    } else {
      printf("req: %d, need: %d, avail: %d\n",
        request[i], need[customer_num][i], available[i]);
      printf("Not enough resources for customer %d's request"
        " or the customer doesn't need this resource.\n", customer_num);
      pass = -1;
      break;
    }
    printf("Resource: %d req: %d, need: %d, avail: %d, alloc: %d\n",
      i + 1, request[i], need[customer_num][i], available[i],
      allocation[customer_num][i]);
  }
  //printf("I'm a thread\n");
  printf("Customer %d is about to left critical\n", customer_num + 1);
  unlockMutex(&mtx);
  return (void*)pass;
} 

static int release_resources(int customer_num, int release[]) {

}

int main(int argc, char *argv[])
{
  int input[NUMBER_OF_RESOURCES];
  /* default input */
  for (int i = 0; i < NUMBER_OF_RESOURCES; ++i) input[i] = 10;
  /* override default input with command line arguments if provided */
  if (argc > NUMBER_OF_RESOURCES) {
    for (int i = 0; i < NUMBER_OF_RESOURCES; ++i) {
      input[i] = strtol(argv[i + 1], NULL, 10);
    }
  }

  int result;
        // for(int ii = 0; ii < NUMBER_OF_CUSTOMERS; ii++){
            // for(int jj = 0; jj < NUMBER_OF_RESOURCES; jj++){
                // allocation[ii][jj] += 0;
            // }
        // }    

  for (int i = 0; i < NUMBER_OF_RESOURCES; ++i) {
    available[i] = input[i];
  }

  for(int i = 0; i < NUMBER_OF_CUSTOMERS; ++i) {
    for (int j = 0; j < NUMBER_OF_RESOURCES; ++j) {
      maximum[i][j] = input[j] - 4;
      need[i][j] = 2; //input[j] - 6;
      //printf("%d\t", maximum[i][j]);
    }
  }

  Thread threads[NUMBER_OF_CUSTOMERS];
  struct ThreadParams params[NUMBER_OF_CUSTOMERS];
  for (int i = 0; i < NUMBER_OF_CUSTOMERS; ++i) {
    printf("Creating customer %d\n", i + 1);
    params[i].req[0] = 2;
    params[i].req[1] = 2;
    params[i].req[2] = 2;
    params[i].threadNum = i;
    result = startThread(threads + i, &request_resources, params + i);
  }

  for (int i = 0; i < NUMBER_OF_CUSTOMERS; ++i) {
    joinThread(threads + i);
  }

  printf("Done\n");
  return 0;
}

笔记：

  1. 我害怕struct threadParams param(in main()) 的一生。因此我把它做成了一个数组，并将它的声明移动到一个比线程寿命更长的作用域。（这是我的第一个建议。）

  2. 一个小问题：我不使用 post-fix inc./dec。如果没有必要 - 口味问题。

  3. 我介绍了一些#ifdef __cplusplus和一个薄层，以便能够在 pthread (C) 和 std::thread (C++) 之间切换。我这样做是为了能够使用它漂亮的调试器在 VS2013 中编译和调试它。

  4. 一个小问题：我在所有全局变量前面加上static. 我这样做是为了防止externs 的任何潜在问题，这些问题可能在我不知道的任何标题中声明。

  5. 一个小问题：我为缺少的命令行参数提供了一些默认值以简化测试。

  6. VS2013 调试器发现了我修复的另一个问题int work[NUMBER_OF_RESOURCES];（in safe_state()，超出范围的访问）。

  7. 一个小问题：我稍微重新格式化了输出以使其更紧凑。

我在 Windows 10（64 位）上的 VS2013 中编译并测试了它，并得到了这个输出（使用std::thread）：

Creating customer 1
Customer 1 is in critical
Granted
Resource: 1 req: 2, need: 0, avail: 8, alloc: 2
Granted
Resource: 2 req: 2, need: 0, avail: 8, alloc: 2
Granted
Resource: 3 req: 2, need: 0, avail: 8, alloc: 2
Customer 1 is about to left critical
Creating customer 2
Customer 2 is in critical
Granted
Resource: 1 req: 2, need: 0, avail: 6, alloc: 2
Granted
Resource: 2 req: 2, need: 0, avail: 6, alloc: 2
Granted
Resource: 3 req: 2, need: 0, avail: 6, alloc: 2
Customer 2 is about to left critical
Creating customer 3
Customer 3 is in critical
Granted
Resource: 1 req: 2, need: 0, avail: 4, alloc: 2
Granted
Resource: 2 req: 2, need: 0, avail: 4, alloc: 2
Granted
Resource: 3 req: 2, need: 0, avail: 4, alloc: 2
Customer 3 is about to left critical
Creating customer 4
Customer 4 is in critical
Granted
Resource: 1 req: 2, need: 0, avail: 2, alloc: 2
Granted
Resource: 2 req: 2, need: 0, avail: 2, alloc: 2
Granted
Resource: 3 req: 2, need: 0, avail: 2, alloc: 2
Customer 4 is about to left critical
Creating customer 5
Customer 5 is in critical
Granted
Resource: 1 req: 2, need: 0, avail: 0, alloc: 2
Granted
Resource: 2 req: 2, need: 0, avail: 0, alloc: 2
Granted
Resource: 3 req: 2, need: 0, avail: 0, alloc: 2
Customer 5 is about to left critical
Done
Drücken Sie eine beliebige Taste . . .

我也在 cygwin 上使用 gcc 编译并测试了它（使用pthread）：

$ gcc -std=c11 -x c bankers.cc -o bankers -pthread

$ ./bankers
Creating customer 1
Creating customer 2
Customer 1 is in critical
Granted
Resource: 1 req: 2, need: 0, avail: 8, alloc: 2
Granted
Resource: 2 req: 2, need: 0, avail: 8, alloc: 2
Granted
Resource: 3 req: 2, need: 0, avail: 8, alloc: 2
Customer 1 is about to left critical
Creating customer 3
Customer 2 is in critical
Granted
Resource: 1 req: 2, need: 0, avail: 6, alloc: 2
Granted
Resource: 2 req: 2, need: 0, avail: 6, alloc: 2
Granted
Resource: 3 req: 2, need: 0, avail: 6, alloc: 2
Customer 2 is about to left critical
Creating customer 4
Customer 3 is in critical
Granted
Resource: 1 req: 2, need: 0, avail: 4, alloc: 2
Granted
Resource: 2 req: 2, need: 0, avail: 4, alloc: 2
Granted
Resource: 3 req: 2, need: 0, avail: 4, alloc: 2
Customer 3 is about to left critical
Creating customer 5
Customer 4 is in critical
Granted
Resource: 1 req: 2, need: 0, avail: 2, alloc: 2
Granted
Resource: 2 req: 2, need: 0, avail: 2, alloc: 2
Granted
Resource: 3 req: 2, need: 0, avail: 2, alloc: 2
Customer 4 is about to left critical
Customer 5 is in critical
Granted
Resource: 1 req: 2, need: 0, avail: 0, alloc: 2
Granted
Resource: 2 req: 2, need: 0, avail: 0, alloc: 2
Granted
Resource: 3 req: 2, need: 0, avail: 0, alloc: 2
Customer 5 is about to left critical
Done
于 2017-03-28T05:49:00.840 回答
1

最后，我找到了一些时间来认真处理这个问题：

一般来说，我仍然难以理解您的实施。（在我回来之前，我花了几个小时首先了解了Edsger Dijkstra的银行家算法本身。）

因此，我不明白您为什么要区分need[]和threadParams.req[]。当我做对时，这实际上应该是相同的（即其中一个不应该在那里）。

但是，我想向您展示到目前为止我得到了什么（这可能会有所帮助）。在我研究并比较了多个样本之后，我终于在 rosettacode.org 上制作了银行家算法的修改版本：

#ifdef __cplusplus
#include <cassert>
#include <cstdio>
#include <cstring>
using namespace std;
#else /* (not) __cplusplus */
#include <assert.h>
#include <stdio.h>
#include <string.h>
#endif /* __cplusplus */

enum { nResources = 4 };
enum { nCustomers = 3 };

struct System {
  /* the total amount of resources */
  int total[nResources];
  /* the available amount of each resource */
  int available[nResources];
  /* currently allocated resources */
  int allocation[nCustomers][nResources];
  /* the maximum demand of each customer */
  int maximum[nCustomers][nResources];
};

static struct System testSetSafe1 = {
  /* the total amount of resources */
  { 6, 5, 7, 6 },
  /* the available amount of each resource */
  { },
  /* currently allocated resources */
  {
    { 1, 2, 2, 1 },
    { 1, 0, 3, 3 },
    { 1, 2, 1, 0 }
  },
  /* the maximum demand of each customer */
  {
    { 3, 3, 2, 2 },
    { 1, 2, 3, 4 },
    { 1, 3, 5, 0 }
  }
};

static struct System testSetSafe2 = {
  /* the total amount of resources */
  { 6, 5, 7, 6 },
  /* the available amount of each resource */
  { },
  /* currently allocated resources */
  {
    { 1, 0, 0, 1 },
    { 1, 0, 3, 3 },
    { 1, 2, 1, 0 }
  },
  /* the maximum demand of each customer */
  {
    { 5, 3, 2, 2 },
    { 1, 2, 3, 4 },
    { 1, 3, 5, 0 }
  }
};

static struct System testSetUnsafe = {
  /* the total amount of resources */
  { 6, 5, 7, 6 },
  /* the available amount of each resource */
  { },
  /* currently allocated resources */
  {
    { 1, 2, 2, 1 },
    { 1, 0, 3, 3 },
    { 1, 2, 1, 0 }
  },
  /* the maximum demand of each customer */
  {
    { 5, 3, 2, 2 },
    { 1, 2, 3, 4 },
    { 1, 3, 5, 0 }
  }
};

void initSystem(struct System *pSystem)
{
  for (int j = 0; j < nResources; ++j) {
    pSystem->available[j] = pSystem->total[j];
    for (int i = 0; i < nCustomers; ++i) {
      pSystem->available[j] -= pSystem->allocation[i][j];
    }
  }
}

void printR(const char *title, int table[nResources])
{
  printf("%s:\n", title);
  for (int j = 0; j < nResources; ++j) printf("\t%c", 'A' + j);
  printf("\n");
  for (int j = 0; j < nResources; ++j) printf("\t%d", table[j]);
  printf("\n");
}

void printCR(const char *title, int table[nCustomers][nResources])
{
  printf("%s:\n", title);
  for (int j = 0; j < nResources; ++j) printf("\t%c", 'A' + j);
  printf("\n");
  for (int i = 0; i < nCustomers; ++i) {
    printf("C%d", i + 1);
    for (int j = 0; j < nResources; ++j) printf("\t%d", table[i][j]);
    printf("\n");
  }
}

int run(struct System *pSystem)
{
  initSystem(pSystem);
  printR("Total resources in system", pSystem->total);
  printR("Available resources", pSystem->available);
  printCR("Customers (currently allocated resources)",
    pSystem->allocation);
  printCR("Customers (maximum required resources", pSystem->maximum);
  int running[nCustomers];
  for (int count = nCustomers, safe; count;) {
    safe = 0;
    for (int i = 0; i < nCustomers; ++i) {
      if (running[i]) {
        int needed[nResources], blocked = 0;
        for (int j = 0, block; j < nResources; ++j) {
          needed[j]
            = pSystem->maximum[i][j] - pSystem->allocation[i][j];
          if ((block = needed[j] > pSystem->available[j])) {
            printf("Customer %d blocked due to resource %c\n",
              i + 1, 'A' + j);
          }
          blocked |= block;
        }
        if (!blocked) {
          printf("Customer %d is served.\n", i + 1);
          /* allocate resources */
          for (int j = 0; j < nResources; ++j) {
            pSystem->available[j] -= needed[j];
            pSystem->allocation[i][j] += needed[j];
            assert(pSystem->allocation[i][j] == pSystem->maximum[i][j]);
          }
          /* perform customer */
          printR("Allocated resources", pSystem->allocation[i]);
          running[i] = 0;
          printf("Customer %d is done.\n", i + 1);
          --count; /* customer finished */
          safe = 1; /* processes still safe (no deadlock) */
          /* free resources */
          for (int j = 0; j < nResources; ++j) {
            pSystem->available[j] += pSystem->allocation[i][j];
            pSystem->allocation[i][j] = 0;
          }
          break; /* bail out of inner loop */
        }
      }
    }
    if (!safe) {
      printf("Unsafe state (i.e. dead lock).\n");
      printR("Total resources in system", pSystem->total);
      printR("Available resources", pSystem->available);
      printCR("Customers (currently allocated resources)",
        pSystem->allocation);
      printCR("Customers (maximum required resources",
        pSystem->maximum);
      return -1;
    }
    printR("Available resources", pSystem->available);
  }
  return 0;
}

int main()
{
  /* 1st try: all requests can be granted soon */
  printf(
    "1st Run:\n"
    "========\n"
    "\n");
  run(&testSetSafe1);
  printf("\n");
  /* 2nd try: all requests can be granted by changing order */
  printf("2nd Run:\n"
    "========\n"
    "\n");
  run(&testSetSafe2);
  printf("\n");
  /* 3rd try: unsafe state */
  printf("3rd Run:\n"
    "========\n"
    "\n");
  run(&testSetUnsafe);
  printf("\n");
  /* done */
  printf("Done.\n");
  return 0;
}

（在 VS2013 中调试但）在 Windows 10（64 位）的 cygwin 中使用 gcc 编译和测试：

$ gcc -std=c11 -x c bankers.cc -o bankers

$ ./bankers
1st Run:
========

Total resources in system:
        A       B       C       D
        6       5       7       6
Available resources:
        A       B       C       D
        3       1       1       2
Customers (currently allocated resources):
        A       B       C       D
C1      1       2       2       1
C2      1       0       3       3
C3      1       2       1       0
Customers (maximum required resources:
        A       B       C       D
C1      3       3       2       2
C2      1       2       3       4
C3      1       3       5       0
Customer 1 is served.
Allocated resources:
        A       B       C       D
        3       3       2       2
Customer 1 is done.
Available resources:
        A       B       C       D
        4       3       3       3
Customer 2 is served.
Allocated resources:
        A       B       C       D
        1       2       3       4
Customer 2 is done.
Available resources:
        A       B       C       D
        5       3       6       6
Customer 3 is served.
Allocated resources:
        A       B       C       D
        1       3       5       0
Customer 3 is done.
Available resources:
        A       B       C       D
        6       5       7       6

2nd Run:
========

Total resources in system:
        A       B       C       D
        6       5       7       6
Available resources:
        A       B       C       D
        3       3       3       2
Customers (currently allocated resources):
        A       B       C       D
C1      1       0       0       1
C2      1       0       3       3
C3      1       2       1       0
Customers (maximum required resources:
        A       B       C       D
C1      5       3       2       2
C2      1       2       3       4
C3      1       3       5       0
Customer 1 blocked due to resource A
Customer 2 is served.
Allocated resources:
        A       B       C       D
        1       2       3       4
Customer 2 is done.
Available resources:
        A       B       C       D
        4       3       6       5
Customer 1 is served.
Allocated resources:
        A       B       C       D
        5       3       2       2
Customer 1 is done.
Available resources:
        A       B       C       D
        5       3       6       6
Customer 3 is served.
Allocated resources:
        A       B       C       D
        1       3       5       0
Customer 3 is done.
Available resources:
        A       B       C       D
        6       5       7       6

3rd Run:
========

Total resources in system:
        A       B       C       D
        6       5       7       6
Available resources:
        A       B       C       D
        3       1       1       2
Customers (currently allocated resources):
        A       B       C       D
C1      1       2       2       1
C2      1       0       3       3
C3      1       2       1       0
Customers (maximum required resources:
        A       B       C       D
C1      5       3       2       2
C2      1       2       3       4
C3      1       3       5       0
Customer 1 blocked due to resource A
Customer 2 blocked due to resource B
Customer 3 blocked due to resource C
Unsafe state (i.e. dead lock).
Total resources in system:
        A       B       C       D
        6       5       7       6
Available resources:
        A       B       C       D
        3       1       1       2
Customers (currently allocated resources):
        A       B       C       D
C1      1       2       2       1
C2      1       0       3       3
C3      1       2       1       0
Customers (maximum required resources:
        A       B       C       D
C1      5       3       2       2
C2      1       2       3       4
C3      1       3       5       0

Done.

$

这看起来相当不错（对我来说）。

现在，我制作了一个介绍多线程的派生示例。

关于此的注释：

Wikipedia 文章Banker's algorithm指出，该算法旨在用于操作系统资源管理，例如内存、信号量和接口访问。听起来对我来说，这些算法旨在管理诸如静音之类的东西。因此，互斥体应该/不能用于它，并且多线程没有多大意义。

但是，请忘记我的担忧，并说这是出于教育/理解目的：

#ifdef __cplusplus
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <mutex>
#include <thread>
using namespace std;
#else /* (not) __cplusplus */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>
#endif /* __cplusplus */

enum { nResources = 4 };
enum { nCustomers = 3 };

struct System {
  /* the total amount of resources */
  int total[nResources];
  /* the available amount of each resource */
  int available[nResources];
  /* currently allocated resources */
  int allocation[nCustomers][nResources];
  /* the maximum demand of each customer */
  int maximum[nCustomers][nResources];
  /* customers to serve, blocked customers */
  int running, blocked;
};

static struct System testSetSafe1 = {
  /* the total amount of resources */
  { 6, 5, 7, 6 },
  /* the available amount of each resource */
  { },
  /* currently allocated resources */
  {
    { 1, 2, 2, 1 },
    { 1, 0, 3, 3 },
    { 1, 2, 1, 0 }
  },
  /* the maximum demand of each customer */
  {
    { 3, 3, 2, 2 },
    { 1, 2, 3, 4 },
    { 1, 3, 5, 0 }
  }
};

static struct System testSetSafe2 = {
  /* the total amount of resources */
  { 6, 5, 7, 6 },
  /* the available amount of each resource */
  { },
  /* currently allocated resources */
  {
    { 1, 0, 0, 1 },
    { 1, 0, 3, 3 },
    { 1, 2, 1, 0 }
  },
  /* the maximum demand of each customer */
  {
    { 5, 3, 2, 2 },
    { 1, 2, 3, 4 },
    { 1, 3, 5, 0 }
  }
};

static struct System testSetUnsafe = {
  /* the total amount of resources */
  { 6, 5, 7, 6 },
  /* the available amount of each resource */
  { },
  /* currently allocated resources */
  {
    { 1, 2, 2, 1 },
    { 1, 0, 3, 3 },
    { 1, 2, 1, 0 }
  },
  /* the maximum demand of each customer */
  {
    { 5, 3, 2, 2 },
    { 1, 2, 3, 4 },
    { 1, 3, 5, 0 }
  }
};

void initSystem(struct System *pSystem)
{
  for (int j = 0; j < nResources; ++j) {
    pSystem->available[j] = pSystem->total[j];
    for (int i = 0; i < nCustomers; ++i) {
      pSystem->available[j] -= pSystem->allocation[i][j];
    }
  }
  pSystem->running = nCustomers; pSystem->blocked = 0;
}

void printR(const char *title, int table[nResources])
{
  printf("%s:\n", title);
  for (int j = 0; j < nResources; ++j) printf("\t%c", 'A' + j);
  printf("\n");
  for (int j = 0; j < nResources; ++j) printf("\t%d", table[j]);
  printf("\n");
}

void printCR(const char *title, int table[nCustomers][nResources])
{
  printf("%s:\n", title);
  for (int j = 0; j < nResources; ++j) printf("\t%c", 'A' + j);
  printf("\n");
  for (int i = 0; i < nCustomers; ++i) {
    printf("C%d", i + 1);
    for (int j = 0; j < nResources; ++j) printf("\t%d", table[i][j]);
    printf("\n");
  }
}

struct Customer {
  int i;
  struct System *pSystem;
  int blocked;
};

static void initCustomer(
  struct Customer *pCustomer, int i, struct System *pSystem)
{
  pCustomer->i = i;
  pCustomer->pSystem = pSystem;
  pCustomer->blocked = 0;
}

#ifdef __cplusplus
/* multi-threading thin layer for C++ and std::thread */
static mutex mtx;
static inline void lockMutex(mutex *pMtx) { pMtx->lock(); }
static inline void unlockMutex(mutex *pMtx) { pMtx->unlock(); }
typedef std::thread Thread;
static inline int startThread(
  Thread *pThread,
  void* (*pThreadFunc)(Customer*), Customer *pCustomer)
{
  return (*pThread = Thread(pThreadFunc, pCustomer)).get_id()
    == Thread::id();
  /* thread creation failed -> thread id == thread::id() -> 1
   * thread creation successful -> thread id != thread::id() -> 0
   */
}
static inline void joinThread(Thread *pThread) { pThread->join(); }
#else /* (not) __cplusplus */
/* multi-threading thin layer for C and pthread */
pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
static void lockMutex(pthread_mutex_t *pMtx)
{
  pthread_mutex_lock(pMtx);
}
static void unlockMutex(pthread_mutex_t *pMtx)
{
  pthread_mutex_unlock(pMtx);
}
typedef pthread_t Thread;
static int startThread(
  Thread *pThread,
  void* (*pThreadFunc)(struct Customer*),
  struct Customer *pCustomer)
{
  return pthread_create(pThread, NULL,
    (void*(*)(void*))pThreadFunc, pCustomer);
}
static void joinThread(Thread *pThread) { pthread_join(*pThread, NULL); }
#endif /* __cplusplus */

void* runCustomer(struct Customer *pCustomer)
{
  int i = pCustomer->i;
  struct System *pSystem = pCustomer->pSystem;
  int needed[nResources];
  for (int j = 0; j < nResources; ++j) {
    needed[j] = pSystem->maximum[i][j] - pSystem->allocation[i][j];
  }
  for (int done = 0; !done;) {
    lockMutex(&mtx); /* thread-safe access to shared system */
    if (pCustomer->blocked) --pSystem->blocked;
    pCustomer->blocked = 0;
    for (int j = 0, block; j < nResources; ++j) {
      if ((block = needed[j] > pSystem->available[j])) {
        printf("Customer %d blocked due to resource %c\n",
          i + 1, 'A' + j);
      }
      pCustomer->blocked |= block;
    }
    if (!pCustomer->blocked) {
      printf("Customer %d is served.\n", i + 1);
      /* allocate resources */
      for (int j = 0; j < nResources; ++j) {
        pSystem->available[j] -= needed[j];
        pSystem->allocation[i][j] += needed[j];
        assert(pSystem->allocation[i][j] == pSystem->maximum[i][j]);
      }
      /* perform customer */
      printR("Allocated resources", pSystem->allocation[i]);
      --pSystem->running;
      done = 1; /* customer finished */
      printf("Customer %d is done.\n", i + 1);
      /* free resources */
      for (int j = 0; j < nResources; ++j) {
        pSystem->available[j] += pSystem->allocation[i][j];
        pSystem->allocation[i][j] = 0;
      }
    } else {
      ++pSystem->blocked;
      if ((done = pSystem->running <= pSystem->blocked)) {
        printf("Customer %d exited (due to dead-lock).\n", i + 1);
      }
    }
    unlockMutex(&mtx);
  }
  return 0;
}

int run(struct System *pSystem)
{
  initSystem(pSystem);
  printR("Total resources in system", pSystem->total);
  printR("Available resources", pSystem->available);
  printCR("Customers (currently allocated resources)",
    pSystem->allocation);
  printCR("Customers (maximum required resources", pSystem->maximum);
  /* created threads for customers */
  lockMutex(&mtx); /* force concurrency a little bit */
  Thread threads[nCustomers];
  struct Customer customers[nCustomers];
  for (int i = 0; i < nCustomers; ++i) {
    printf("Creating customer %d\n", i + 1);
    initCustomer(customers + i, i, pSystem);
    if (startThread(threads + i, &runCustomer, customers + i)) {
      printf("ERROR: Failed to start thread for customer %d!\n", i + 1);
    }
  }
  /* unlock mutex to let threads compete */
  printf("Ready, steady, go...\n");
  unlockMutex(&mtx);
  /* join all threads */
  for (int i = 0; i < nCustomers; ++i) joinThread(threads + i);
  /* report */
  if (pSystem->blocked) {
    printf("Unsafe state (i.e. dead lock).\n");
    printR("Total resources in system", pSystem->total);
    printR("Available resources", pSystem->available);
    printCR("Customers (currently allocated resources)",
      pSystem->allocation);
    printCR("Customers (maximum required resources",
      pSystem->maximum);
    return -1;
  }
  return 0;
}

int main()
{
  /* 1st try: all requests can be granted soon */
  printf(
    "1st Run:\n"
    "========\n"
    "\n");
  run(&testSetSafe1);
  printf("\n");
  /* 2nd try: all requests can be granted by changing order */
  printf("2nd Run:\n"
    "========\n"
    "\n");
  run(&testSetSafe2);
  printf("\n");
  /* 3rd try: unsafe state */
  printf("3rd Run:\n"
    "========\n"
    "\n");
  run(&testSetUnsafe);
  printf("\n");
  /* done */
  printf("Done.\n");
  return 0;
}

（再次在 VS2013 中调试，但是）在 Windows 10（64 位）的 cygwin 中使用 gcc 编译和测试：

$ gcc -std=c11 -x c bankersMT.cc -o bankersMT -pthread

$ ./bankersMT
1st Run:
========

Total resources in system:
        A       B       C       D
        6       5       7       6
Available resources:
        A       B       C       D
        3       1       1       2
Customers (currently allocated resources):
        A       B       C       D
C1      1       2       2       1
C2      1       0       3       3
C3      1       2       1       0
Customers (maximum required resources:
        A       B       C       D
C1      3       3       2       2
C2      1       2       3       4
C3      1       3       5       0
Creating customer 1
Creating customer 2
Creating customer 3
Ready, steady, go...
Customer 1 is served.
Allocated resources:
        A       B       C       D
        3       3       2       2
Customer 1 is done.
Customer 2 is served.
Allocated resources:
        A       B       C       D
        1       2       3       4
Customer 2 is done.
Customer 3 is served.
Allocated resources:
        A       B       C       D
        1       3       5       0
Customer 3 is done.

2nd Run:
========

Total resources in system:
        A       B       C       D
        6       5       7       6
Available resources:
        A       B       C       D
        3       3       3       2
Customers (currently allocated resources):
        A       B       C       D
C1      1       0       0       1
C2      1       0       3       3
C3      1       2       1       0
Customers (maximum required resources:
        A       B       C       D
C1      5       3       2       2
C2      1       2       3       4
C3      1       3       5       0
Creating customer 1
Creating customer 2
Creating customer 3
Ready, steady, go...
Customer 1 blocked due to resource A
Customer 2 is served.
Allocated resources:
        A       B       C       D
        1       2       3       4
Customer 2 is done.
Customer 3 is served.
Allocated resources:
        A       B       C       D
        1       3       5       0
Customer 3 is done.
Customer 1 is served.
Allocated resources:
        A       B       C       D
        5       3       2       2
Customer 1 is done.

3rd Run:
========

Total resources in system:
        A       B       C       D
        6       5       7       6
Available resources:
        A       B       C       D
        3       1       1       2
Customers (currently allocated resources):
        A       B       C       D
C1      1       2       2       1
C2      1       0       3       3
C3      1       2       1       0
Customers (maximum required resources:
        A       B       C       D
C1      5       3       2       2
C2      1       2       3       4
C3      1       3       5       0
Creating customer 1
Creating customer 2
Creating customer 3
Ready, steady, go...
Customer 1 blocked due to resource A
Customer 2 blocked due to resource B
Customer 3 blocked due to resource C
Customer 3 exited (due to dead-lock).
Customer 1 blocked due to resource A
Customer 1 exited (due to dead-lock).
Customer 2 blocked due to resource B
Customer 2 exited (due to dead-lock).
Unsafe state (i.e. dead lock).
Total resources in system:
        A       B       C       D
        6       5       7       6
Available resources:
        A       B       C       D
        3       1       1       2
Customers (currently allocated resources):
        A       B       C       D
C1      1       2       2       1
C2      1       0       3       3
C3      1       2       1       0
Customers (maximum required resources:
        A       B       C       D
C1      5       3       2       2
C2      1       2       3       4
C3      1       3       5       0

Done.

$

虽然，这看起来也不错，但我不确定死锁检测是否 100% 正确。因为多线程引入了不确定性，所以很难测试。我试图“用头调试它”，但结果头痛......

实施注意事项：

我再次将薄层用于多线程。因此，这些示例可以在 C++ ( std::thread, VS2013/g++) 以及 C ( pthread, gcc) 中编译。

于 2017-03-30T14:26:13.640 回答