Abstract The goal of this assignment is to write a program in GO that reads an i
ID: 3913212 • Letter: A
Question
Abstract
The goal of this assignment is to write a program in GO that reads an input ?le containing several con?gurationparameterstosimulateFirst-ComeFirst-Served,preemptiveShortestJobFirst,andRoundRobin CPU scheduling algorithms. The output will re?ect the results of the con?gured CPU scheduling algorithm to a speci?ed output ?le.
1 Objectives
The objectives of this assignment are to simulate the CPU scheduline of several processes for the con?guredFirst-ComeFirst-Served,preemptiveShortestJobFirst,andRound-RobinCPUschedulingalgorithms. Therefore the algorithm will need to be selected/con?gured as will the processes and their durations and burst cycles, as appropriate.
1.1 Algorithms 1.1.1 First-ComeFirst-Served The First-Come First-Served algorithm is just that: processes are allocated the CPU in the order in which they arrive and run until completion or termination.
1.1.2 PreemptiveShortestJobFirst The Preemptive Shortest Job First selects the process for execution which has the smallest amount of time remaining until completion. Therefore, a process with a budget or expected time of 2 time units will be scheduledaheadof a process with 6 time units.
1.1.3 Round-Robin Round-Robin was originally built for time-sharing systems. It works on the premise of providing a rigorous enforcementofaninterrupteverycon?guredtimeinterval,thenswappingtothenexttaskintheprocesslist at the moment of the interrupt. This scheduling algorithm treats the process list as a circular list until each process is complete. New processes can be added in?nitum. NotethattheRound-Robinalgorithmrequiresacon?gurationofthetimequantumfortheperiodoftime used for the process to be in the CPU. Once the period expires the next process in the list will have CPU resources until its time quantum expires.
1
2 Speci?cations 2.1 Inputs Theinput?lewillbepassedasthe?rstcommandlineargument. Alsotheprogramshouldignoreeverything on a line after a # mark and ignore additional spaces in the input ?le.
processcount 2 # Read 2 processes runfor 15 # Run for 15 time units use rr # Can be fcfs, sjf, or rr quantum 2 # Time quantum, only if using rr process name P1 arrival 3 burst 5 process name P2 arrival 0 burst 9 end
There is no requirement to process blank lines. The input ?les are as follows:
Table 1: Input Test Files
Filename Description c2-fcfs.in 2 processes scheduled First-Come First-Served c2-rr.in 2 processes scheduled Round-Robin c2-sjf.in 2 processes scheduled preemptive Shortest Job First c5-fcfs.in 5 processes scheduled First-Come First-Served c5-rr.in 5 processes scheduled Round-Robin c5-sjf.in 5 processes scheduled preemptive Shortest Job First c10-fcfs.in 10 processes scheduled First-Come First-Served c10-rr.in 10 processes scheduled Round-Robin c10-sjf.in 10 processes scheduled preemptive Shortest Job First
2.1.1 CommandLineInputs The command line inputs or cli are the input ?le name as the ?rst parameter and the output ?le name as the second parameter. For example: ./pa1 c5-fcfs.in c5-fcfs.stu where the ?les’ extensions correspond to input and student. Review the pa1Test.sh ?le in the assignment ZIP ?le for more examples.
2
2.2 Outputs The output of each schedule shall be formatted as shown below. Note that the output below corresponds to the input ?le shown above. You can also review the ?les that have the base extension for each test cases’ expected outputs.
2 processes Using Round-Robin Quantum 2
Time 0 : P2 arrived Time 0 : P2 selected (burst 9) Time 2 : P2 selected (burst 7) Time 3 : P1 arrived Time 4 : P1 selected (burst 5) Time 6 : P2 selected (burst 5) Time 8 : P1 selected (burst 3) Time 10 : P2 selected (burst 3) Time 12 : P1 selected (burst 1) Time 13 : P1 finished Time 13 : P2 selected (burst 1) Time 14 : P2 finished Time 14 : Idle Finished at time 15
P1 wait 5 turnaround 10 P2 wait 5 turnaround 14
Notes: 1. All integer numeric data is formatted using %3d. 2. Process names are speci?ed in the input ?le.
3 Resources Therearemany, manyresourcesonGoavailableonline. Thelistbelowshouldhelpyougetquicklystarted. • Basic building blocks: Go by example (Very useful for command line interfaces, ?les, and so much more. • A cookbook with examples: Go Language CookBook With Examples Nice seminar summary with extensive examples and descriptions. • Whatnottodo: 50ShadesofGo: Traps,Gotchas,andCommonMistakesforNewGolangDevsHint: If you are new to Go the information here will save you hours debugging your code. There are many different links that were provided during lecture and are in the Intro to GO slide deck. Note that the links above work in most Acrobat Readers - with one notable exception - the Webcourses PDF reader in the browser. To take advantage of the links, download this assignment PDF and use Adobe’s Acrobat reader.
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
struct proc_ess {
int pid, bu, pri, wo, wa;
struct proc_ess *nxt;
};
/* Function Prototype Declarations */
struct proc_ess *init_proc_ess (int pid, int bu, int pri);
void fcfs (struct proc_ess *proc);
void listprocs (struct proc_ess *proc);
void pri (struct proc_ess *proc);
void rr (struct proc_ess *proc, int qt);
void sjf (struct proc_ess *proc);
int main (void) {
struct proc_ess *plist, *ptmp;
plist = init_proc_ess(1, 10, 3);
plist->nxt = init_proc_ess(2, 1, 1); ptmp = plist->nxt;
ptmp->nxt = init_proc_ess(3, 2, 3); ptmp = ptmp->nxt;
ptmp->nxt = init_proc_ess(4, 1, 4); ptmp = ptmp->nxt;
ptmp->nxt = init_proc_ess(5, 5, 2);
listprocs(plist);
fcfs(plist);
sjf(plist);
pri(plist);
rr(plist, 1);
while (plist != NULL) {
ptmp = plist;
plist = plist->nxt;
free(ptmp);
};
return(0);
};
struct proc_ess *init_proc_ess (int pid, int bu, int pri) {
struct proc_ess *proc;
proc = malloc(sizeof(struct proc_ess));
if (proc == NULL) {
printf("Fatal error: memory allocation failure. Terminating. ");
exit(1);
};
proc->pid = pid;
proc->bu = bu;
proc->pri = pri;
proc->wo = 0;
proc->wa = 0;
proc->nxt = NULL;
return(proc);
};
void fcfs (struct proc_ess *proc) {
int time = 0, st, ed;
struct proc_ess *tmp = proc;
printf("BEGIN: First-Come-First-Served scheduling simulation ");
while (tmp != NULL) {
st = time;
time += tmp->bu;
ed = time;
printf("Proc_ess: %d Ed Time: %d Wa: %d Turnaround: %d ", tmp->pid, time, st,ed);
tmp tmp->nxt;
}
printf("ED: First-Come-First-served scheduling simulation ");
};
void listprocs (struct proc_ess *proc) {
struct proc_ess *tmp = proc;
printf("BEGIN: Proc_ess Listing ");
while (tmp != NULL) {
printf("PID: %d Pri: %d Bu: %d ", tmp->pid, tmp->pri, tmp->bu);
tmp = tmp->nxt;
};
printf("ED: Proc_ess Listing ");
};
/* priority scheduling lower priority values has higher priority*/
void pri (struct proc_ess *proc) {
int time, st, ed, highest;
struct proc_ess *cp, *tmpsrc, *tmp, *before_highest ;
printf("BEGIN: Pri scheduling simulation ");
tmpsrc = proc;
cp = tmp = NULL;
while (tmpsrc != NULL) {
if (cp == NULL) {
cp = init_proc_ess(tmpsrc->pid, tmpsrc->bu, tmpsrc->pri);
tmp = cp;
} else {
tmp->nxt = init_proc_ess(tmpsrc->pid, tmpsrc->bu, tmpsrc->pri);
tmp = tmp->nxt;
};
tmpsrc = tmpsrc->nxt;
};
time = 0;
while (cp != NULL) {
before_highest = NULL;
highest = cp->pri;
tmp = cp->nxt;
tmpsrc = cp;
while (tmp != NULL) {
if (tmp->pri < highest) {
highest = tmp->pri;
before_highest = tmpsrc;
};
tmpsrc = tmp;
tmp = tmp->nxt;
};
if (before_highest == NULL) {
st = time;
time += cp->bu;
ed = time;
printf("Proc_ess: %d Ed Time: %d Wa: %d Turnaround: %d ", cp->pid, time, st, ed);
tmpsrc = cp->nxt;
free(cp);
cp = tmpsrc;
} else {
tmp = before_highest ->nxt;
st = time;
time += tmp->bu;
ed = time;
printf("Proc_ess: %d Ed Time: %d Wa: %d Turnaround: %d ", tmp->pid, time, st, ed);
before_highest ->nxt = tmp->nxt;
free(tmp);
};
};
printf("ED: Priority scheduling simulation ");
};
/* Round-Robin scheduling simulation */
void rr (struct proc_ess *proc, int qt) {
int jobs_remain, passes;
struct proc_ess *cp, *tmpsrc, *tmp, *slot;
printf("BEGIN: Round-Robin scheduling simulation (Qt: %d) ", qt);
tmpsrc = proc;
cp = tmp = NULL;
while (tmpsrc != NULL) {
if (cp == NULL) {
cp = init_proc_ess(tmpsrc->pid, tmpsrc->bu, tmpsrc->pri);
tmp = cp;
} else {
tmp->nxt = init_proc_ess(tmpsrc->pid, tmpsrc->bu, tmpsrc->pri);
tmp = tmp->nxt;
};
tmpsrc = tmpsrc->nxt;
};
jobs_remain = 1;
slot = NULL;
while (jobs_remain) {
jobs_remain = 0;
if (slot == NULL) {
slot = cp;
jobs_remain = 1;
} else {
passes = 0;
do {
if (slot->nxt == NULL) {
passes++;
slot = cp;
} else {
slot = slot->nxt;
};
} while (passes <= 2 && slot->bu == slot->wo);
if (passes <= 2) {
jobs_remain = 1;
};
};
tmp = cp;
while (tmp != NULL) {
if (tmp->bu > tmp->wo) {
if (tmp == slot) {
tmp->wo += qt;
} else {
tmp->wa += qt;
};
};
tmp = tmp->nxt;
};
};
tmp = cp;
while (tmp != NULL) {
printf("Proc_ess: %d Wo: %d Wa: %d Turnaround: %d ", tmp->pid, tmp->wo,tmp->wa, tmp->wo + tmp->wa);
tmpsrc = mp;
tmp = tp->nxt;
free(tpsrc);
}
printf("ED: RR scheduling simulation ");
};
void sjf (struct proc_ess *proc) {
int time, st, ed, shortest;
struct proc_ess *cp, *tmpsrc, *tmp, *before_shortest ;
printf("BEGIN: Shortest Job First scheduling simulation ");
tmpsrc = proc;
cp = tmp = NULL;
while (tmpsrc != NULL) {
if (cp == NULL) {
cp = init_proc_ess(tmpsrc->pid, tmpsrc->bu, tmpsrc->pri);
tmp = cp;
} else {
tmp->nxt = init_proc_ess(tmpsrc->pid, tmpsrc->bu, tmpsrc->pri);
tmp = tmp->nxt;
};
tmpsrc = tmpsrc->nxt;
};
time = 0;
while (cp != NULL) {
before_shortest = NULL;
shortest = cp->bu;
tmp = cp->nxt;
tmpsrc = cp;
while (tmp != NULL) {
if (tmp->bu < shortest) {
shortest = tmp->bu;
before_shortest = tmpsrc;
};
tmpsrc = tmp;
tmp = tmp->nxt;
};
if (before_shortest == NULL) {
st = time;
time += cp->bu;
ed = time;
printf("Proc_ess: %d Ed Time: %d Wa: %d Turnaround: %d ", cp->pid, time, st, ed);
tmpsrc = cp;
cp = cp->nxt;
free(tmpsrc);
} else {
tmp = before_shortest ->nxt;
st = time;
time += tmp->bu;
ed = time;
printf("Process: %d Ed Time: %d Wa: %d Turnaround: %d ", tmp->pid, time, st, ed);
before_shortest ->nxt = tmp->nxt;
free(tmp);
};
};
printf("ED: Shortest Job First scheduling simulation ");
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.