Answers for the midterm review: 1) Describe the steps that occur when a user program to executes a system call (assuming that there is a system library to wrap the call). 1 - push parameters to the stack 2 - call the library wrapper 3 - wrapper sets the system call register 4 - wrapper traps to the kernel 5 - kernel reads the system call register to find the sys call handler 6 - sys call handler executes 7 - kernel returns to the wrapper 8 - wrapper sets return values 9 - wrapper returns to the calling code 2) Describe the steps that occur when the operating system performs a context switch between processes. 1 - an interrupt causes the OS to stop running the process 2 - switch to kernel space 3 - save the CPU state and the running information to the Process Control Block 4 - reset the cache 5 - select the new process (or handler) to run 6 - restore the CPU state for the new process 7 - execute the next instruction of the new process 3) Consider the following table of process, all of which are available at the time of scheduling and arrived in the order in which they are numbered , with the given burst times and priorities (lower numbers are higher priority). Process | Time | Priority P1 | 8ms | 2 P2 | 4ms | 1 P3 | 10ms | 0 P4 | 2ms | 2 P5 | 8ms | 1 Draw the Gantt chart and calculate the average turnaround time for the following algorithms. Turnaround time is calculated taking the time when a process finishes running. 3a) First Come, First Served | Process time run->total time since starting | | P1 8ms->8ms | P2 4ms->12ms | P3 10ms->22ms | P4 2ms->24ms | P5 8ms->32ms| Turnaround Time: P1 = 8ms, P2 = 12ms, P3 = 22ms, P4 = 24ms, P5 = 32ms. Average = 19.6 3b) Shortest Job First Assuming that we'll run jobs arrived earlier to break ties | P4 2ms->2ms | P2 4ms->6ms | P1 8ms->14ms | P5 8ms->22ms | P3 10ms->32ms | Turnaround Time P1 = 14ms, P2 = 6ms, P3 = 32ms, P4 = 2ms, P5 = 22ms Average = 15.2 3c) Priority Assuming that we'll run jobs arrived earlier to break ties | P3 10ms->10ms | P2 4ms->14ms | P5 8ms->22ms | P1 8ms->30ms | P4 2ms->32ms | Turnaround Time P1 = 30ms, P2 = 14ms, P3 = 10ms, P4 = 32ms, P5 = 22ms Average = 21.6 3d) Round Robin (with a 5ms time quantum) Remember that we start with FCFS so each process gets to run for its quantum or until its done. | P1 5ms->5ms | P2 4ms->9ms | P3 5ms->14ms | P4 2ms->16ms | P5 5ms->21ms | P1 3ms->24ms | P3 5ms->29ms | P5 3ms->32ms | Turnaround Time P1 = 24ms, P2 = 9ms, P3 = 29ms, P4 = 16ms, P5 = 32ms Average = 22ms 4)Consider the following table of process, with the given burst and arrival times Process | Time | Arrival Time P1 | 8ms | 0 ms P2 | 4ms | 4 ms P3 | 10ms | 6 ms P4 | 2ms | 12 ms P5 | 8ms | 18 ms Draw the Gantt chart and calculate the average turnaround time for the following algorithms. 4a) Shortest Job First (Non-Preemptive) Times we need to schedule: t=0ms Queue=[P1] We schedule P1 it runs for 8ms t=8ms Queue=[P2-P3] We schedule P2 (it's shorter) it runs for 4ms t=12ms Queue=[P3-P4] We schedule P4 (it's shorter) it runs for 2ms t=14ms Queue=[P3] We schedule P3 it runs for 10ms t=24ms Queue=[P5] We schedule P5 it runs for 8ms | P1 8ms->8ms | P2 4ms->12ms | P4 2ms->14ms | P3 10ms->24ms | P5 8ms->32ms | Turnaround time Completion time - arrival time P1 = 8ms - 0ms = 8ms, P2 = 12ms - 4ms = 8ms, P3 = 24ms - 6ms = 18ms, P4 = 14ms - 12ms = 2ms, P5 = 32ms - 18ms = 14ms Average Time = 10ms 4b) Shortest Job First (Preemptive) Times we need to schedule: t=0ms Queue=[P1] We schedule P1, it runs until P2 arrives at 4ms t=4ms Queue=[P1-P2] We schedule P1, it runs until P3 arrives at 6ms (we have a tie between P1 and P2, we can (roughly) assume that we can save a context switch by sticking with the process already being scheduled) t=6ms Queue=[P1-P2-P3] We schedule P1 it runs until 8ms when it finishes running t=8ms Queue=[P2-P3] We schedule P2 it runs until 12ms when it finishes and P4 arrives t=12ms Queue[P3-P4] We schedule P4 and it runs for 2ms t=14ms Queue[P3] We schedule P3 and it runs until P5 arrives at 18ms t=18ms Queue[P3-P5] We schedule P3 and it runs until it finishes at 24ms t=24ms Queue[P5] We schedule P5 and it runs until it finishes | P1 4ms->4ms | P1 2ms->6ms | P1 2ms->8ms | P2 4ms->12ms | P4 2ms->14ms | P3 4ms->18ms | P3 6ms->24ms | P5 8ms->32ms | Turnaournd Time P1 = 8ms - 0ms = 8ms, P2 = 12ms - 4ms = 8ms, P3 = 24ms - 6ms = 18ms, P4 = 14ms - 12ms = 2ms, P5 = 32ms - 18ms = 14ms Average=10ms * It happens that the preemptive algorithm is the same as the non-preemptive in this case, that's a quirk of the numbers I picked (rather late at night) If you want to check the difference see what happens if P2 is 2ms on. 4c) Round Robin (with a 5ms time quantum) Non-preemptive, processes will be added to the end of the queue Times we need to schedule: t=0ms Q=[P1] We schedule P1 and it runs for its quantum (5ms) and goes on the back of the queue t=5ms Q=[P2-P1] We schedule P2 and it runs for 4ms until it finishes t=9ms Q=[P1-P3] We schedule P1 and it runs for 3ms until it finishes t=12ms Q=[P3-P4] We schedule P3 and it runs for its quantum (5ms) t=17ms Q=[P4-P3] We schedule P4 and it runs until it finishes (2ms) t=19ms Q=[P3-P5] We schedule P3 and it runs until it finishes t=24ms Q=[P5] We schedule P5 and it runs for its quantum t=29ms Q=[P5] We schedule P5 and it runs until its done | P1 5ms->5ms | P2 4ms->9ms | P1 3ms->12ms | P3 5ms->17ms | P4 2ms->19ms | P3 5ms->24ms | P5 5ms->29ms | P5 3ms->32ms | Turnaround Times: P1 = 12ms - 0ms = 12ms, P2 = 9ms - 4ms = 5ms, P3 = 24ms - 6ms = 18ms, P4 = 19ms - 12ms = 5ms, P5 = 32ms - 18ms = 14ms Average = 10.8 4d) A Multi-Level Feedback Queue (with 3 queues, a high priority queue served with Round Robin with a a 2 ms quantum, a medium priority queue served with Round Robin with a a 6 ms quantum, and a low priority queue served First Come First Served. a job is preempted if a higher priority job is available. A preempted job is put on the HEAD of its queue.) Structure QH-[] 2ms quantum <- new processes go here! QM-[] 6ms quantum QL-[] FCFS t=0ms QH-[P1] 2ms quantum <- new processes go here! QM-[] 6ms quantum QL-[] FCFS We scheudle P1 it runs for its quantum (2ms) t=2ms QH-[] 2ms quantum <- new processes go here! QM-[P1] 6ms quantum QL-[] FCFS We scheudle P1 it runs until P2 arrives at 4ms t=4ms QH-[P2] 2ms quantum <- new processes go here! QM-[P1] 6ms quantum (P1 has 4ms of its quantum left) QL-[] FCFS We schedule P2 (higher priority) it runs for its quantum (2ms) t=6ms QH-[P3] 2ms quantum <- new processes go here! QM-[P1-P2] QL-[] FCFS We schedule P3 (higher priority) it runs for its quantum (2ms) t=8ms QH-[] 2ms quantum <- new processes go here! QM-[P1-P2-P3] QL-[] FCFS We schedule P1 it runs for the rest of its quantum (4ms) t=12ms QH-[P4] 2ms quantum <- new processes go here! QM-[P2-P3] QL-[] FCFS We schedule P4 it runs for its quantum (and its burst time) (2ms) t=14ms QH-[] 2ms quantum <- new processes go here! QM-[P2-P3] QL-[] FCFS We schedule P2 it runs for the rest of its burst time (2ms) t=16ms QH-[] 2ms quantum <- new processes go here! QM-[P3] QL-[] FCFS We schedule P3 and it runs until P5 arrives at 18ms t=18ms P3 goes back on the Medium Queue (at the head) with 4ms left to run in its quantum QH-[P5] 2ms quantum <- new processes go here! QM-[P3] QL-[] FCFS We schedule P5 and run it for its quantum 2ms t=20ms QH-[] 2ms quantum <- new processes go here! QM-[P3-P5] QL-[] FCFS We schedule P3 and run it for the rest of its quantum (4ms) t=24ms QH-[] 2ms quantum <- new processes go here! QM-[P5] QL-[P3] FCFS We schedule P5 and run it for its quantum (6ms) (also its remaining burst time) t=24ms QH-[] 2ms quantum <- new processes go here! QM-[] QL-[P3] FCFS We schedule P3 and run it for its its remaining burst time (2ms) | P1 2ms->2ms | P1 2ms->4ms | P2 2ms->6ms | P3 2ms->8ms | P1 4ms->12ms | P4 2ms->14ms | P2 2ms->16ms | P3 2ms->18ms | P5 2ms->20ms | P3 4ms->24ms | P5 6ms->30ms | P3 2ms->32ms | Turnaround Time: P1 = 12ms - 0ms = 12ms, P2 = 16ms - 4ms = 12ms, P3 32ms - 6ms = 26ms, P4 = 14ms - 12ms = 2ms, P5 = 30ms - 18ms = 12ms Average = 15.2 5) 5) Recall the formula calculating exponential average: (Tau)_n+1 = (Alpha) t_n + (1 - (Alpha))(Tau)_n For a process with the following real burst times, an initial estimated burst time of (4 ms) and a memory factor () of .5 calculate estimated burst times for each n. (Round to the nearest integer ms) Estimated (Tau)_1=5ms Real t_1=10ms t_2=2ms t_3=8ms t_4=4ms t_5=12ms (Tau)_2 = (Alpha) t_1 + (1-(Alpha)) (Tau)_1 (Tau)_2 = (0.5) 10ms + (0.5) 5ms = 7.5 (rounds to 8) (Tau)_3 = (0.5) 2ms + (0.5) 8ms = 5ms (Tau)_4 = (0.5) 8ms + (0.5) 5ms = 6.5 (rounds to 7) (Tau)_5 = (0.5) 12ms + (0.5) 7 = 9.5 (rounds to 10)