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

1

最後に、これを真剣に処理する時間を見つけました。

一般的な実装を理解するにはまだ問題があります。(エドガー・ダイクストラのバンカーのアルゴリズム自体を理解するのに数時間を費やしてから、戻ってきました。)

したがって、なぜ と を区別するのか理解できませneed[]んthreadParams.req[]。私がそれを正しく理解したとき、これは実際には同じであるはずです (つまり、それらの 1 つが存在しないはずです)。

ただし、これまでに得たものをお見せしたいと思います (これは助けになるかもしれません)。複数のサンプルを調べて比較した後、最終的に、rosettacode.org で Banker's Algorithm の修正版を作成しました。

#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.

$

これは（私にとっては）かなり良さそうです。

さて、マルチスレッドを導入した派生サンプルを作りました。

これに関するメモ:

ウィキペディアの記事Banker's algorithmでは、このアルゴリズムは、メモリ、セマフォ、インターフェイス アクセスなどの OS リソース管理を目的としていると述べられています。私には、これらのアルゴリズムはミュートなどを管理することを目的としているように思えます。したがって、ミューテックスを使用する必要がある/使用できないため、マルチスレッドはあまり意味がありません。

ただし、私の懸念は忘れて、これは教育/理解を目的としたものであると言いましょう:

#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% 正しいかどうかはわかりません。マルチスレッドでは非決定論が導入されるため、これをテストするのは困難です。「頭でデバッグ」しようとしましたが、頭痛がしてしまいました...

実装に関する注意:

再び、マルチスレッドに薄層を使用しました。std::threadしたがって、これらのサンプルは C++ ( 、VS2013/g++) および C ( pthread、gcc)でコンパイルできます。

于 2017-03-30T14:26:13.640 に答える