Почему моя глобальная структура размещения не обновляет значения правильно?
Я работал над реализацией алгоритма банкиров в 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,¶ms);
}
for(index = 0; index < NUMBER_OF_CUSTOMERS; ++index){
pthread_join(threads[index], NULL);
}
printf("\nDone");
}
2 ответа
Решение
Наконец, я нашел время, чтобы серьезно с этим справиться:
У меня все еще есть проблемы, чтобы понять вашу реализацию в целом. (Я потратил несколько часов, чтобы сначала понять сам алгоритм Edsger Dijkstra 's Banker, прежде чем я вернулся.)
Таким образом, я не понимаю, почему вы различаете 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, но) скомпилировано и протестировано с помощью gcc в cygwin в Windows 10 (64-разрядная версия):
$ 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 в статье из Википедии гласит, что алгоритм предназначен для управления ресурсами ОС, такими как память, семафоры и доступ к интерфейсу. Мне кажется, что этот алгоритм предназначен для управления такими вещами, как отключение звука. Таким образом, мьютекс не должен / не может использоваться для него, и многопоточность не имеет особого смысла.
Тем не менее, давайте забудем о моей заботе и скажем, что это для образовательных целей:
#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, но) скомпилировано и протестировано с помощью gcc в cygwin на Windows 10 (64-битная версия):
$ 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).
После того, как я исправил некоторые проблемы, я получил работающую версию:
#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;
}
Заметки:
Я боялся жизни
struct threadParams param(вmain()). Таким образом, я сделал его массивом и перенес его объявление в область видимости, где он живет дольше потоков. (Это была моя первая рекомендация.)Незначительная проблема: я не использую post-fix inc./dec. если не нужно - дело вкуса.
Я ввел некоторые
#ifdef __cplusplusи тонкий слой, чтобы иметь возможность переключаться между pthread (C) и std::thread (C++). Я сделал это, чтобы иметь возможность скомпилировать и отладить его в VS2013 с его хорошим отладчиком.Небольшая проблема: я поставил перед всеми глобальными
static, Я сделал это, чтобы предотвратить возможные проблемы сexterns, которые могут быть объявлены в любом заголовке за пределами моего ведома.Незначительная проблема: я предоставил некоторые значения по умолчанию для отсутствующих аргументов командной строки, чтобы упростить тесты.
Отладчик VS2013 обнаружил еще одну проблему
int work[NUMBER_OF_RESOURCES];(вsafe_state()вне доступа), который я исправил.Небольшая проблема: я немного отформатировал вывод, чтобы сделать его более компактным.
Я скомпилировал и протестировал его в VS2013 на Windows 10 (64 бит) и получил этот вывод (использование 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 . . .
Я также скомпилировал и протестировал его с помощью gcc на cygwin (используя 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