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