#include#include #include #include #include #define True 1 #define False 0 const int left = 0; const int right = 9; enum State { Error, Block, Success }; int generating_data(int left,int right) { static int seed = 1; srand((unsigned)time(NULL) + seed * seed + seed); int random_data; random_data = rand() % (right - left + 1) + left; ++seed; return random_data; } void free_resouce(int** resource,int size) { for(int i = 0;i < size;++i) free((void*)resource[i]); free((void*)resource); } void print(int* p,int size) { for(int i = 0;i < size;++i) { printf("%d ",p[i]); } printf("n"); } void print_current_state(int processes,int resource_types,int* available,int* security_queue, int** max,int** allocation,int** need,int** work_plus_allocation) { printf("Available:"); print(available,resource_types); enum MatrixType { Max = 0, Allocation, Need, Work_Plus_Allocation }; printf("tt%-20s%-20s%-20s%sn","Max","Allocation","Need","Work+Allocation"); int** matrix_ptr = NULL; for(int i = 0;i < processes;++i) { printf("Process%dt",security_queue[i]); for(enum MatrixType matrix_type = Max;matrix_type <= Work_Plus_Allocation;++matrix_type) { switch(matrix_type) { case Max:matrix_ptr = max; break; case Allocation:matrix_ptr = allocation; break; case Need:matrix_ptr = need; break; case Work_Plus_Allocation:matrix_ptr = work_plus_allocation; break; default:break; } for(int j = 0;j < resource_types;++j) { if(matrix_ptr[security_queue[i]][j] == -1) { printf("%s ","None"); continue; } printf("%d ",matrix_ptr[security_queue[i]][j]); } int placeholder_num = 20 - (resource_types * 2); for(int k = 0;k < placeholder_num;++k) printf(" "); } printf("n"); } matrix_ptr = NULL; } int detect_1(int* request,int** need,int process_no,int resource_types) { int is_legal = True; for(int i = 0;i < resource_types;++i) { if(request[i] > need[process_no][i]) { is_legal = False; break; } } return is_legal; } int detect_2(int* request,int* available,int process_no,int resource_types) { int is_legal = True; for(int i = 0;i < resource_types;++i) { if(request[i] > available[i]) { is_legal = False; break; } } return is_legal; } typedef struct DataLog { int* available_last; int* allocation_last; int* need_last; }DataLog; void record(int* p,int* p_log,int resource_types) { for(int i = 0;i < resource_types;++i) { p_log[i] = p[i]; } } int security_testing(int resource_types,int processes, int* available,int** max,int** need,int** allocation) { int* work = (int*)malloc(sizeof(int) * resource_types); memcpy(work,available,sizeof(int) * resource_types); int* security_queue = (int*)malloc(sizeof(int) * processes); for(int i = 0;i < processes;++i) { security_queue[i] = -1; } int* finish = (int*)malloc(sizeof(int) * processes); for(int i = 0;i < processes;++i) { finish[i] = False; } int** work_plus_allocation = (int**)malloc(sizeof(int*) * processes); for(int i = 0;i < processes;++i) { work_plus_allocation[i] = (int*)malloc(sizeof(int) * resource_types); } int is_continue = True; int count = 0; while(is_continue) { is_continue = False; for(int i = 0;i < processes;++i) { if(finish[i] == True) continue; int legal = True; for(int j = 0;j < resource_types;++j) { if(need[i][j] > work[j]) { legal = False;break; } } if(legal) { finish[i] = True; security_queue[count] = i; #ifdef _DEBUG_ printf("Security queue[%d]=%dn",count,i); #endif for(int j = 0;j < resource_types;++j) { work[j] = work[j] + allocation[i][j]; work_plus_allocation[i][j] = work[j]; } is_continue = True; ++count; break; } } } int is_security = True; for(int i = 0;i < processes;++i) { if(finish[i] == False) { is_security = False; break; } } if(is_security) { print_current_state(processes,resource_types,available,security_queue,max,allocation,need,work_plus_allocation); } free((void*)finish); free((void*)security_queue); free((void*)work); free_resouce(work_plus_allocation,processes); return is_security; } DataLog* try_to_allocate(int* request,int* available, int** allocation,int** need, int process_no,int resource_types) { DataLog* data_log = (DataLog*)malloc(sizeof(DataLog)); data_log->available_last = (int*)malloc(sizeof(int) * resource_types); record(available,data_log->available_last,resource_types); for(int i = 0;i < resource_types;++i) { available[i] = available[i] - request[i]; } data_log->allocation_last = (int*)malloc(sizeof(int) * resource_types); record(allocation[process_no],data_log->allocation_last,resource_types); for(int i = 0;i < resource_types;++i) { allocation[process_no][i] = allocation[process_no][i] + request[i]; } data_log->need_last = (int*)malloc(sizeof(int) * resource_types); record(need[process_no],data_log->need_last,resource_types); for(int i = 0;i < resource_types;++i) { need[process_no][i] = need[process_no][i] - request[i]; } #ifdef _DEBUG_ printf("Available lastn"); print(data_log->available_last,resource_types); printf("Allocation lastn"); print(data_log->allocation_last,resource_types); printf("Need lastn"); print(data_log->need_last,resource_types); #endif return data_log; } enum State request_resources(int processes,int resource_types, int* available,int** max,int** allocation,int** need) { enum State state; int process_no; #ifdef _DEBUG_ printf("Input request process number:"); scanf("%d",&process_no); #else process_no = generating_data(0,processes - 1); #endif printf("Process no:%dn",process_no); int* request = (int*)malloc(sizeof(int) * resource_types); #ifdef _DEBUG_ printf("Input request vector:"); for(int i = 0;i < resource_types;++i) { scanf("%d",&request[i]); } #else for(int i = 0;i < resource_types;++i) { request[i] = generating_data(left,right); } #endif printf("Request:"); print(request,resource_types); printf("n"); int is_legal; is_legal = detect_1(request,need,process_no,resource_types); if(is_legal == False) { state = Error; return state; } is_legal = detect_2(request,available,process_no,resource_types); if(is_legal == False) { state = Block; return state; } DataLog* data_log = try_to_allocate(request,available,allocation,need,process_no,resource_types); int is_security = security_testing(resource_types,processes,available,max,need,allocation); if(is_security == False) { state = Block; for(int i = 0;i < resource_types;++i) { available[i] = data_log->available_last[i]; allocation[process_no][i] = data_log->allocation_last[i]; need[process_no][i] = data_log->allocation_last[i]; } } else { state = Success; } free((void*)data_log->available_last); free((void*)data_log->allocation_last); free((void*)data_log->need_last); free((void*)data_log); free((void*)request); return state; } int main(int argc,char** argv) { int processes; // The number of processe #ifdef _DEBUG_ printf("Input the number of processes:"); scanf("%d",&processes); #else processes = generating_data(left + 1,right - 3); #endif printf("The number of processes:%dn",processes); // The number of resource types int resource_types; #ifdef _DEBUG_ printf("Input the number of of resource types:"); scanf("%d",&resource_types); #else resource_types = generating_data(left + 1,right - 3); #endif printf("The number of resource types:%dn",resource_types); // The number of different types of resources int* resource_total = (int*)malloc(sizeof(int) * resource_types); #ifdef _DEBUG_ printf("Input the number of different types of resources:"); for(int i = 0;i < resource_types;++i) { scanf("%d",&resource_total[i]); } #else for(int i = 0;i < resource_types;++i) { resource_total[i] = generating_data(left + 5,right + 5); } #endif printf("The number of different types of resources:"); print(resource_total,resource_types); int* resource_total_copy = (int*)malloc(sizeof(int) * resource_types); memcpy(resource_total_copy,resource_total,sizeof(int) * resource_types); // Max int** max = (int**)malloc(sizeof(int*) * processes); #ifdef _DEBUG_ printf("Input Max:n"); for(int i = 0;i < processes;++i) { max[i] = (int*)malloc(sizeof(int) * resource_types); for(int j = 0;j < resource_types;++j) { scanf("%d",&max[i][j]); } } #else for(int i = 0;i < processes;++i) { max[i] = (int*)malloc(sizeof(int) * resource_types); for(int j = 0;j < resource_types;++j) { // Maximum quantity required max[i][j] = generating_data(left,right); } } #endif // Allocation int** allocation = (int**)malloc(sizeof(int*) * processes); #ifdef _DEBUG_ printf("Input Allocation:n"); for(int i = 0;i < processes;++i) { allocation[i] = (int*)malloc(sizeof(int) * resource_types); for(int j = 0;j < resource_types;++j) { scanf("%d",&allocation[i][j]); } } #else for(int i = 0;i < processes;++i) { allocation[i] = (int*)malloc(sizeof(int) * resource_types); for(int j = 0;j < resource_types;++j) { // Number of allocated resources int right_range = (max[i][j] < resource_total[j] ? max[i][j] : resource_total[j]); allocation[i][j] = generating_data(left,right_range); resource_total[j] = resource_total[j] - allocation[i][j]; } } #endif // Need int** need = (int**)malloc(sizeof(int*) * processes); for(int i = 0;i < processes;++i) { need[i] = (int*)malloc(sizeof(int) * resource_types); for(int j = 0;j < resource_types;++j) { // Number of resources still needed need[i][j] = max[i][j] - allocation[i][j]; } } // Available int* available = (int*)malloc(sizeof(int) * resource_types); for(int i = 0;i < resource_types;++i) { // The number of resouces int have_allocated = 0; for(int j = 0;j < processes;++j) { have_allocated += allocation[j][i]; } available[i] = resource_total_copy[i] - have_allocated; } int** work_plus_allocation = (int**)malloc(sizeof(int*) * processes); for(int i = 0;i < processes;++i) { work_plus_allocation[i] = (int*)malloc(sizeof(int) * resource_types); for(int j = 0;j < resource_types;++j) { work_plus_allocation[i][j] = -1; } } int* security_queue = (int*)malloc(sizeof(int) * processes); for(int i = 0;i < processes;++i) { security_queue[i] = i; } print_current_state(processes,resource_types,available,security_queue,max,allocation,need,work_plus_allocation); free_resouce(work_plus_allocation,processes); free((void*)security_queue); int is_security; is_security = security_testing(resource_types,processes,available,max,need,allocation); if(is_security == False) { printf("The initial state is unsafen"); } else { printf("Initial state securityn"); } //enum State state = request_resources(processes,resource_types,available,max,allocation,need); if(is_security) { // Request 5 times enum State state = request_resources(processes,resource_types,available,max,allocation,need); if(state == Error) printf("Errorn"); else if(state == Block) printf("Blockn"); else printf("Successn"); } free((void*)resource_total); free((void*)resource_total_copy); free((void*)available); free_resouce(max,processes); free_resouce(allocation,processes); free_resouce(need,processes); return 0; }
