Untitled
unknown
c_cpp
2 years ago
23 kB
3
Indexable
#include <math.h> #include <stdio.h> #include <stdlib.h> #include <algorithm> #include <cstdlib> #include <cstring> #include <fstream> #include <iostream> #include <sstream> #include <string> using namespace std; // Banker's Algorithm of allocating resources // const size_t MAX_TASKS = 20; const size_t MAX_RES = 30; enum command_t { Initiate, Request, Release, Compute, Terminate }; // Posible commands enum task_state { blocked, running, aborted }; struct res { // Resources kept here int r_type; int units; } resources[MAX_RES]; struct comm { // List of allocation commands int task_id; command_t cmd; int r_type; int units; } commlist[MAX_RES]; struct tsk { // Aray to keep basic info about the tasks int task_id; task_state state; struct tskact *taskp; } task_array[MAX_TASKS]; struct tskact { // This structure keeps the activities for each task command_t cmd; int r_type; int units; struct tskact *next; // It is kept as FIFO linked list } task_activity; struct stats { // Here we keep statistics about tasks, to generate the output char *status; int time; int wait; } t_stats[MAX_TASKS]; int curr[MAX_TASKS][MAX_RES]; // Current allocation of resources int maxalc[MAX_TASKS][MAX_RES]; // Maximum claims int save_curr[MAX_TASKS][MAX_RES]; // To facilitate safety check int release_curr[MAX_TASKS][MAX_RES]; // To facilitate provisional release int avail[MAX_RES]; int save_avail[MAX_RES]; int provisional_avail[MAX_RES]; //"in cycle" release of resources // FUNCTIONS PROTOTYPES void print_c(struct comm[], int); void init_storage(int, int); bool safe(int, int); void print_matrix(int[][MAX_RES], int, int); void backup_state(int, int); void restore_state(int, int); void print_array(struct tsk[], int); void print_stats(struct stats[], int); void update_provisional(int[], int[], int); bool exceed(int, int); void init_stats(struct stats[], int); void grant(int, int, int); void sort_task(struct tsk[], int); void init_provisional(int[], int); void init_matrix(int[][MAX_RES], int, int); void update_curr(int[][MAX_RES], int, int); //----------------------------------------------------- MAIN int main(int argc, char *const argv[]) { char *in_file; in_file = argv[1]; fstream in(in_file, ios::in); if (!in) { cout << "\n Input cannot be opened" << "\n Please check file: " << in_file << "\n"; exit(1); } char tk[10]; int t1, r1; // t1 - number of tasks, r1 - number of resources int c_i = 1; int task, resource, u, cyc; // Reading the resources pool in >> tk; t1 = atoi(tk); cout << "\n T=" << t1 << "\n"; in >> tk; r1 = atoi(tk); // # resource types cout << "\n R=" << r1 << "\n"; for (int i = 1; i <= r1; ++i) { in >> tk; u = atoi(tk); resources[i].r_type = i; resources[i].units = u; // cout <<"\n Resource type " << resources[i].r_type; // cout <<"\n units=" << resources[i].units; } // Reading the allocation instructions char comm_in[10]; in >> tk; strcpy(comm_in, tk); while (in) { // The 3rd character in comm_in, identifies the command char comm_id = *(comm_in + 2); // cout <<"\n comm_id=" << comm_id; // bexit(1); switch (comm_id) { case 'i': // Initiate commlist[c_i].cmd = Initiate; in >> task; in >> resource; in >> u; commlist[c_i].task_id = task; commlist[c_i].r_type = resource; commlist[c_i].units = u; break; case 'q': // Request commlist[c_i].cmd = Request; in >> task; in >> resource; in >> u; commlist[c_i].task_id = task; commlist[c_i].r_type = resource; commlist[c_i].units = u; break; case 'l': // Release commlist[c_i].cmd = Release; in >> task; in >> resource; in >> u; commlist[c_i].task_id = task; commlist[c_i].r_type = resource; commlist[c_i].units = u; break; case 'm': // Compute commlist[c_i].cmd = Compute; in >> task; in >> cyc; commlist[c_i].task_id = task; commlist[c_i].r_type = 0; // CPU is the // resource commlist[c_i].units = cyc; break; case 'r': // Terminate commlist[c_i].cmd = Terminate; in >> task; commlist[c_i].task_id = task; commlist[c_i].r_type = 0; commlist[c_i].units = -1; break; default: cout << "\n char is: " << comm_id; cout << "\ninvalid command encountered. " "Terminates.\n"; } // switch ++c_i; in >> comm_in; } // While input // End of input processing // Build Available resource array (initial availability of course) for (int i = 1; i <= r1; ++i) { avail[i] = resources[i].units; } // Initialize maxalc, curr alocation matrices init_storage(t1, r1); /*Build matrix of maximum allocation requested by all tasks for all resources for (int i=1;i<c_i;++i){ if (commlist[i].cmd==Initiate){ maxalc[commlist[i].task_id][commlist[i].r_type]+=commlist[i].units; } } */ cout << "\n Command list:\n"; print_c(commlist, c_i); // cout "\nCurr allocation:\n"; // print_matrix(curr,t1,r1); // cout << "\nMAX allocation:\n"; // print_matrix(maxalc,t1,r1); /****************************************************************************** * Built the construct of array of pointers, each of which belongs to one task * * and points to a linked list that contains all the activities we need to * * perform on those tasks. /*****************************************************************************/ int ind; // struct tskact *p; for (int i = 1; i < t1; ++i) { // Initialize array of pointers to activities task_array[i].taskp = NULL; task_array[i].task_id = 0; } // cout << "\n BUILDING THE FIFO\n"; for (int l = 1; l < c_i; ++l) { ind = commlist[l].task_id; if (task_array[ind].task_id == 0) { // First activity for the task, create entry task_array[ind].task_id = ind; // Initially the array's index=task ids task_array[ind].state = running; // zero excluded } if (task_array[ind].taskp == NULL) { task_array[ind].taskp = (struct tskact *)malloc(sizeof(struct tskact)); task_array[ind].taskp->cmd = commlist[l].cmd; task_array[ind].taskp->r_type = commlist[l].r_type; task_array[ind].taskp->units = commlist[l].units; task_array[ind].taskp->next = NULL; } else { // The array entry already has an activity(ies) add // more struct tskact *q; struct tskact *t; q = task_array[ind].taskp; while (q->next != NULL) q = q->next; t = (struct tskact *)malloc(sizeof(struct tskact)); t->cmd = commlist[l].cmd; t->r_type = commlist[l].r_type; t->units = commlist[l].units; t->next = NULL; q->next = t; } } /* DEBUG cout << "\n TASK ARRAY"; struct tskact *p; char *desc; for (int z=1;z<=t1;++z){ p=task_array[z].taskp; while (p!=NULL){ switch(p->cmd){ case Initiate: desc="initiate"; break; case Request: desc="request"; break; case Release: desc="release"; break; case Compute: desc="compute"; break; case Terminate: desc="terminate"; break; default: cout << "invalid command"; } cout <<"\n Element:" << z << " Command=" << desc << " R TYPE=" << p->r_type << " UNITS=" << p->units; p=p->next; } } END DEBUG */ // PROGRAM EXECUTION int tasknum; struct tskact *activity; bool all_tasks_terminated = false; // We assume that some tasks are ready to run int cycle = 0; bool ac_complete; // Check if activity was complete // DEBUG cout << "\nResource available before run:\n"; for (int i = 1; i <= r1; ++i) { cout << "\n resource: " << i << " Units=" << avail[i] << "\n"; } init_stats(t_stats, t1); int sum_t; int i1; init_provisional(provisional_avail, r1); // Empty provisional release array init_matrix(release_curr, t1, r1); // and image of current alocation while (!all_tasks_terminated) { // Not really necessary here, but // keeping good form cout << "\n\n ARRAY_TASK before cycle:" << cycle; print_array(task_array, t1); cout << "\nCurr allocation:\n"; print_matrix(curr, t1, r1); // tc - is Task Counter // tc may not corrspond to the task number because // we sort task_array, so "blocked" are treated first sum_t = 0; for (int tc = 1; tc <= t1; ++tc) { if (task_array[tc].task_id == 0) break; // Meaning task terminated, go to next // task tasknum = task_array[tc].task_id; if (task_array[tc].taskp == NULL) { task_array[tc].task_id = 0; break; } // Debug cout << "\n\n TASK ID EXAMINED: " << task_array[tc].task_id << "\n\n"; activity = task_array[tc].taskp; ac_complete = true; // DEBUG char *ac_desc; switch (activity->cmd) { case Initiate: ac_desc = "initiate"; break; case Request: ac_desc = "request"; break; case Release: ac_desc = "release"; break; case Compute: ac_desc = "compute"; break; case Terminate: ac_desc = "terminate"; break; default: cout << "invalid command"; } cout << "\n\n Checking, task: " << tasknum << " activity:" << ac_desc << " Resource T:" << activity->r_type << " units:" << activity->units; cout << "\nResource available, before SWITCH:\n"; for (int i = 1; i <= r1; ++i) { cout << "\n resource: " << i << " Units=" << avail[i] << "\n"; } switch (activity->cmd) { case Initiate: /********************************************************************************* * During the course of initiation(which *is done before requests), the avail *array* still holds the initial *availability, which is known in *advance from the input * and therefore *allows us to check that initiate does *not exceed availability * *********************************************************************************/ if (exceed(activity->r_type, activity ->units)) { // ERROR // DETECTION cout << "\n Banker aborts task: " << tasknum << " before execution"; cout << "\n Initial claim of " "task: " << tasknum << " is: " << activity->units << " units of resource " "type: " << activity->r_type << " which exceeds " "maximum of: " << avail[activity->r_type] << " available"; task_array[tc].task_id = 0; task_array[tc].state = aborted; t_stats[tasknum].status = "aborted"; // ABORT } else { maxalc[tasknum] [activity->r_type] += activity->units; } cout << "\n MAX allocation after this " "initiate:\n"; print_matrix(maxalc, t1, r1); cout << "\nCurr allocation, after " "initiate:\n"; print_matrix(curr, t1, r1); cout << "\nResource available, after " "initiate:\n"; for (int i = 1; i <= r1; ++i) { cout << "\n resource: " << i << " Units=" << avail[i] << "\n"; } break; case Compute: --activity->units; if (activity->units > 0) ac_complete = false; // Incomplete // activity break; case Release: provisional_avail[activity->r_type] += activity->units; release_curr[tasknum] [activity->r_type] += activity->units; /*debug*/ cout << "\n RELEASE Curr allocation:\n"; print_matrix(release_curr, t1, r1); break; case Terminate: task_array[tc].task_id = 0; t_stats[tasknum].status = "ended"; for (i1 = 1; i1 <= r1; ++i1) maxalc[tasknum][i1] = 0; // This task no onger // claims resources break; case Request: // if Request for resource // +in-use axceed maximum pledged // - abort task if (maxalc[tasknum][activity->r_type] < activity->units + curr[tasknum] [activity->r_type]) { task_array[tc].task_id = 0; task_array[tc].state = aborted; t_stats[tasknum].status = "aborted"; ac_complete = false; cout << "\nTask number: " << tasknum << " asked for:" << activity->units << " of resource type:" << activity->r_type << " and has already:" << curr[tasknum] [activity->r_type] << " units of it. It " "originally asked for:" << maxalc[tasknum] [activity->r_type] << " maximum"; } else { backup_state( t1, r1); // Save state in case // it would be unsafe // Firstly, grant the request // temporarily grant(tasknum, activity->r_type, activity->units); // DEBUG cout << "\n CALLING SAFE with:" << " t1=" << t1 << " r1=" << r1; cout << "\nResource available " "after temp GRANT and " "before SAFE:\n"; for (int i = 1; i <= r1; ++i) { cout << "\n resource: " << i << " Units=" << avail[i] << "\n"; } cout << "\nCurr allocation:\n"; print_matrix(curr, t1, r1); cout << "\nMAX allocation:\n"; print_matrix(maxalc, t1, r1); // END DEBUG if (safe(t1, r1)) { // contingent // safety restore_state(t1, r1); grant( tasknum, activity->r_type, activity ->units); // Now // grant // it // for // real task_array[tc].state = running; cout << "\nREQUEST " "GRANTED\n"; } else { // Request denied, // task blocked // (unsafe) cout << "\nREQUEST NOT " "GRANTED\n"; restore_state(t1, r1); ac_complete = false; // Incomplete // activity t_stats[tasknum].wait++; task_array[tc].state = blocked; } } break; default: cout << "\n Other UNKNOWN command"; break; } if (ac_complete) { // Incomplete activity is compute // that hasn't ended yet, or request // denied task_array[tc].taskp = task_array[tc] .taskp->next; // Drop the activity // after its complete // will become NULL if activity is Terminate } if (task_array[tc].task_id > 0) // one more cycle added to task's time t_stats[tasknum].time++; // free(activity); } update_provisional( avail, provisional_avail, r1); // Update resource vetor and current allocation update_curr( release_curr, t1, r1); // matrix with resources released in the last cycle init_provisional( provisional_avail, r1); // Initialize the temp storage for next cycle init_matrix( release_curr, t1, r1); // both current allocation and avail resource vetor ++cycle; sort_task(task_array, t1); // Sorting task array, so the // blocked tasks are ahead of others for (int l1 = 1; l1 <= t1; ++l1) { sum_t += task_array[l1].task_id; } if (sum_t == 0) all_tasks_terminated = true; sum_t = 0; // DEBUG if (cycle > 22) { all_tasks_terminated = true; } } // DEBUG cout << "\nResource available AFTER run:\n"; for (int i = 1; i <= r1; ++i) { cout << "\n resource: " << i << " Units=" << avail[i]; } cout << "\nMAX allocation:\n"; print_matrix(maxalc, t1, r1); // END DEBUG print_stats(t_stats, t1); return 0; } // Functions //--------------------------------------------------------------------------------------------------------------- void print_c(struct comm q[], int len) { char *comm_desc; for (int i = 1; i < len; ++i) { switch (q[i].cmd) { case Initiate: comm_desc = "initiate"; break; case Request: comm_desc = "request"; break; case Release: comm_desc = "release"; break; case Compute: comm_desc = "compute"; break; case Terminate: comm_desc = "terminate"; break; default: cout << "invalid command"; } cout << "\n" << comm_desc << " " << q[i].task_id << " " << q[i].r_type << " " << q[i].units; cout << "\n"; } } //--------------------------------------------------------------------------------------------------------------- bool safe(int running_tasks, int resources) { bool safe; int unfinished = running_tasks; int i, j; while (unfinished > 0) { i = 1; safe = false; while (i <= running_tasks && !safe) { // Assume it's not safe and look for a task // that can complete if (curr[i][1] != -1) { // I mark tasks that can complete with -1 safe = true; j = 1; while (j <= resources) { // Check if we can satisfy // all resources if ((maxalc[i][j] - curr[i][j]) > avail[j]) { safe = false; // It is enough that // we faile once, to // try next task break; } ++j; } } ++i; } if (safe) { --unfinished; // One less task to check --i; for (j = 1; j <= resources; ++j) { // Release the resources back to the pool avail[j] += curr[i][j]; } curr[i][1] = -1; // Mark the task as complete for now } else { return false; // It was unsafe (no task can complete) } } return true; // If we made it here, it means all tasks can complete (no // unfinished) ==> SAFE } //--------------------------------------------------------------------------------------------------------------- void init_storage(int tasks, int resources) { for (int i = 1; i <= tasks; ++i) { for (int j = 1; j <= resources; ++j) { maxalc[i][j] = 0; curr[i][j] = 0; } } } //--------------------------------------------------------------------------------------------------------------- void init_matrix(int m[][MAX_RES], int t, int r) { for (int i = 1; i <= t; ++i) { for (int j = 1; j <= r; ++j) { m[i][j] = 0; } } } //--------------------------------------------------------------------------------------------------------------- void init_stats(struct stats s[], int t) { for (int i = 1; i <= t; ++i) { s[i].status = ""; s[i].time = 0; s[i].wait = 0; } } //--------------------------------------------------------------------------------------------------------------- void print_matrix(int matrix[][MAX_RES], int t, int r) { for (int i = 1; i <= t; ++i) { cout << "\Task: " << i << " "; for (int j = 1; j <= r; ++j) { cout << "Resource type=" << j << " Units allocated=" << matrix[i][j] << " "; } cout << "\n"; } } //--------------------------------------------------------------------------------------------------------------- void backup_state(int t, int r) { int k1, k2; for (k1 = 1; k1 <= t; ++k1) { for (k2 = 1; k2 <= r; ++k2) { save_curr[k1][k2] = curr[k1][k2]; } } for (k2 = 1; k2 <= r; ++k2) { save_avail[k2] = avail[k2]; } } //--------------------------------------------------------------------------------------------------------------- void restore_state(int t, int r) { int k1, k2; for (k1 = 1; k1 <= t; ++k1) { for (k2 = 1; k2 <= r; ++k2) { curr[k1][k2] = save_curr[k1][k2]; } } for (k2 = 1; k2 <= r; ++k2) { avail[k2] = save_avail[k2]; } } //--------------------------------------------------------------------------------------------------------------- void update_provisional(int r1[], int r2[], int r) { // adding resources from r2 array to r1 array int k; for (k = 1; k <= r; ++k) { r1[k] += r2[k]; } } //--------------------------------------------------------------------------------------------------------------- void update_curr(int c[][MAX_RES], int t, int r) { // After "release", the current allocation is reduced int k1, k2; for (k1 = 1; k1 <= t; ++k1) { for (k2 = 1; k2 <= r; ++k2) { curr[k1][k2] -= c[k1][k2]; } } } //--------------------------------------------------------------------------------------------------------------- void print_array(struct tsk a[], int elements) { char *desc; struct tskact *p; for (int i = 1; i <= elements; ++i) { if (a[i].state == blocked) desc = "blocked"; if (a[i].state == aborted) desc = "aborted"; if (a[i].state == running) desc = "running"; cout << "\n Task id=" << a[i].task_id << " state= " << desc; p = a[i].taskp; if (p != NULL) { switch (p->cmd) { case Initiate: desc = "initiate"; break; case Request: desc = "request"; break; case Release: desc = "release"; break; case Compute: desc = "compute"; break; case Terminate: desc = "terminate"; break; default: cout << "invalid command"; } cout << "\n Activity:" << desc; cout << "\n Resource:" << p->r_type; cout << "\n Units :" << p->units; } else { cout << "\n NO MORE ACTIVITIES FOR THIS TASK\n"; } /* while (p!=NULL){ cout << " Activity:" << p->cmd; p=p->next; } */ } } //--------------------------------------------------------------------------------------------------------------- void print_stats(struct stats s[], int t) { double percent_w; double wait; double time; double tot_time = 0; double tot_wait = 0; double percent_av; for (int i = 1; i <= t; ++i) { wait = (double)s[i].wait; time = (double)s[i].time; if (time > 0) percent_w = (wait / time) * 100; else percent_w = 0; cout << "\n Task number: " << i; if (!strcmp(s[i].status, "aborted")) { // Task was aborted cout << " aborted"; } else { cout << " " << s[i].time << " " << s[i].wait << " " << percent_w << "%"; tot_time += s[i].time; tot_wait += s[i].wait; } } if (tot_time > 0) percent_av = (tot_wait / tot_time) * 100; else percent_av = 0; cout << "\n Total: " << tot_time << " " << tot_wait << " " << percent_av << "%\n"; } //--------------------------------------------------------------------------------------------------------------- bool exceed(int r, int u) { if (avail[r] < u) return true; else return false; } //--------------------------------------------------------------------------------------------------------------- void grant(int tn, int r, int u) { avail[r] -= u; curr[tn][r] += u; } //--------------------------------------------------------------------------------------------------------------- void sort_task(struct tsk v[], int t) { int temp1; struct tskact *temp2; task_state temp3; bool sw; do { sw = false; for (int i = 1; i <= t - 1; i++) { if (v[i].state > v[i + 1].state) { temp1 = v[i].task_id; v[i].task_id = v[i + 1].task_id; v[i + 1].task_id = temp1; temp2 = v[i].taskp; v[i].taskp = v[i + 1].taskp; v[i + 1].taskp = temp2; temp3 = v[i].state; v[i].state = v[i + 1].state; v[i + 1].state = temp3; sw = true; } } } while (sw); } //--------------------------------------------------------------------------------------------------------------- void init_provisional(int v[], int r) { for (int i = 1; i <= r; ++i) { v[i] = 0; } }
Editor is loading...