c - 为什么我的全局分配结构没有正确更新值？

Question

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

    #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");

    }

Answer 1

在我解决了一些问题后，我得到了一个运行版本:

#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 的生命周期(在 main() 中)。因此我把它变成了一个数组并将它的声明移动到一个它比线程生命周期更长的范围。 (这是我的第一个建议。)

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

3. 我引入了一些#ifdef __cplusplus 和一个能够在 pthread (C) 和 std::thread (C++) 之间切换的薄层。我这样做是为了能够使用其出色的调试器在 VS2013 中编译和调试它。

4. 一个小问题:我在所有全局变量前加上了static 前缀。我这样做是为了防止 extern 出现任何潜在问题，这些问题可能在我不了解的任何 header 中声明。

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

6. VS2013 调试器发现了我修复的另一个问题 int work[NUMBER_OF_RESOURCES];(在 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