Problem description in terms of process scheduling Consider two processes, each with two CPU bursts with one I/O burst in between. Process 1 has a CPU burst of x1 units followed by an I/O burst of y1 units followed by a second CPU burst of z1 units. Process 2 has a CPU burst of x2 units followed by an I/O burst of y2 units followed by a second CPU burst of z2 units. Suppose that Process 1 arrives in the ready queue just before Process 2 and just after Process 2 arrives the process that was in the CPU terminates. No other processes are in the system. For each of the scheduling algorithms draw a Gantt charts showing the state of each of the two processes. Use the letter R to represent the running state, the letter w for the waiting state and the letter r for the ready state. Calculate the two waiting times, the average waiting time and the CPU utilization. (Break any ties by having process 1 run first.) Part 1 of assignment 1 describes an algorithm that is similar, but possibly not identical to the FCFS algorithm, where the last 6 input parameters are x1, y1, z1, x2, y2, and z2. The numbers displayed are the waiting times for process 1 and process 2, the average waiting time, and the cpu utilization. This version of the algorithm always chooses process 1 if both processes become ready at the same time. Part 1 In this part of the assignment you will write your fcfs program using a state machine design. A state machine has a state (the values of the variables) which changes over time. At each time step the state changes to a new state. The new state depends only on the old one and the input values. In this case, the state of the system is the state of the two processes, including information about all of their remaining CPU and I/O bursts. Use this code as a prototype for your fcfs function. Insert the appropriate code so that it behaves like the fcfs algorithm. It should usually produce the same strings as your Assignment 0. The protoype may handle some cases that are not related to fcfs, such as a quantum. You may delete the unncessary code. Run your program with these test inputs:

Test 1: 3 8 7 3 6 3 2. Test 2: 3 8 7 3 6 7 2. Test 3: 4 8 7 3 6 1 2. Test 4: 3 3 3 4 2 1 2. Test 5: 3 3 2 3 2 1 2. Test 6: 3 5 2 5 4 1 1.

Part 2 Implement the SJF algorithm (non-preemptive). Again, ignore the first input parameter. Do this by using the function: sjf(char *s1, char *s2, int x1, int y1, int z1, int x2, int y2, int z2); Implement this by modifying your fcfs code or the prototype. Part 3 Implement the PSJF algorithm. That is, write the function: psjf(char *s1, char *s2, int x1, int y1, int z1, int x2, int y2, int z2); Part 4 Implement the Round Robin algorithm. That is, write the function: rr(char *s1, char *s2, int q, int x1, int y1, int z1, int x2, int y2, int z2); In this case the first input parameter is the quantum and the others will be as before. Now run your program on the inputs of assignment1. Example1: 3 4 2 7 3 6 5 Example2: 3 4 9 5 6 3 7 Test 1: 3 8 7 3 6 3 2 Test 2: 3 8 7 3 6 7 2. Test 3: 4 8 7 3 6 1 2. Test 4: 3 3 3 4 2 1 2. Test 5: 3 3 2 3 2 1 2. Test 6: 3 5 2 5 4 1 1

Prototype Code to use:

typedef TaskState{

 E_TASK_READY = 0, E_TASK_RUNNING, E_TASK_WAITING, E_TASK_DONE } eTaskState; static char stateChars[] = {'r','R','w',0}; /* 1) handle state changes: running process completes CPU burst running process has quantum expire IO complete 2) do context switch if necessary both ready one ready and CPU free 3) append appropriate characters to character arrays avoid putting in multiple string terminators */ /* assume s1 and s2 point to buffers with enough space to hold the result */ /* assume that the int parameters are strictly greater than 0 */ void fcfs(char *s1, char *s2, int quantum, int x1, int y1, int z1, int x2, int y2, int z2) { int i; /* next string position (time) */ /* start with both ready */ eTaskState state1 = E_TASK_READY; eTaskState state2 = E_TASK_READY; int cpuLeft1 = x1; /* P1 next CPU burst remaining */ int cpuLeft2 = x2; /* P2 next CPU burst remaining */ int ioLeft1 = y1; /* P1 next IO burst remaining, 0 if no more IO */ int ioLeft2 = y2; /* P2 next IO burst remaining, 0 if no more IO */ int qleft; /* quantum remaining */ for (i=0; (state1 != E_TASK_DONE) || (state2 != E_TASK_DONE); i++) { /* running process completes its CPU burst */ if((state1 == E_TASK_RUNNING) && (cpuLeft1== 0)) { // If process finishes all its cpu-related workload. // Let's check the io of process1 if (ioLeft1 == 0) { state1 = E_TASK_DONE; s1[i] = stateChars[state1]; /* terminate the string */ } else state1 = E_TASK_WAITING; } else if ((state2 == E_TASK_RUNNING) && (cpuLeft2 == 0) ) { ... } /* running process has quantum expire */ if ((state1 == E_TASK_RUNNING) && (qleft == 0) ) { ... } if ((state2 == E_TASK_RUNNING) && (qleft == 0) ) { ... } /* handle IO complete */ if ((state1 == E_TASK_WAITING) && (ioLeft1 == 0)) { state1 = E_TASK_READY; cpuLeft1 = z1; } if ((state2 == E_TASK_WAITING) && (ioLeft2 == 0)) { ... } /* if both ready, depends on algorithm */ if ( (state1 == E_TASK_READY) && (state2 == E_TASK_READY)) { ... } /* handle one ready and CPU available */ else if ( (state1 == E_TASK_READY) && (state2 != E_TASK_RUNNING)) { state1 = E_TASK_RUNNING; qleft = quantum; } else if ( (state2 == E_TASK_READY) && (state1 != E_TASK_RUNNING)) { ... } /* insert chars in string, but avoid putting in extra string terminators */ if (state1 != E_TASK_DONE) s1[i] = stateChars[state1]; if (state2 != E_TASK_DONE) s2[i] = stateChars[state2]; /* decrement counts */ qleft--; /* OK to decrement even if nothing running */ if (state1 == E_TASK_RUNNING) cpuLeft1--; if (state1 == E_TASK_WAITING) ioLeft1--; if (state2 == E_TASK_RUNNING) cpuLeft2--; if (state2 == E_TASK_WAITING) ioLeft2--; } /* end of main for loop */ }