COIS-3320H Fundamentals of Operating Systems - Assignment 2: Scheduling, Predicting CPU Bursts
COIS 3320H Fall 2022 Assignment 2
Instructions: Complete the exercises below and your answers in one PDF named lastname_firstname_student number to the Assignment 2 submission dropbox on PDF by the 17th of November. Make sure your solution is not handwritten.
Each assignment question has the corresponding exercise number on the course ZyBook, if you have a problem with a concept, it is an excellent idea to read that portion of the course ZyBook.
1- Based on Exercise 3.2.1 – Scheduling using FIFO, SJF, and SRT a. For the 5 processes described below draw a timing diagram showing when each process will execute under FIFO, SJF, and SRT. b. Determine the ATT (Average Turnaround Time) for each scheduling algorithm for the 5 processes described below.
| Process | P1 | P2 | P3 | P4 | P5 |
|---|---|---|---|---|---|
| Arrival Time | 0 | 2 | 4 | 6 | 8 |
| Total CPU Time | 3 | 6 | 4 | 5 | 2 |
2- Based on Exercise 3.2.3 – Predicting CPU Bursts The following sequence of CPU bursts has been observed: 7, 5, 6, 15, 15, 15. a- Using 7 as the initial estimate, S0, generate the sequence of predictions, Si, for the corresponding observed values Ti, where 1 <= i <=5 and α = 0.8. b- Repeat the same predictions for α = 0.5.
3- Based on Exercise 3.3.1 – Turnaround Time Under Round Robin Scheduling Three processes, p1, p2, p3, arrive at the same time and start executing using RR scheduling. p1 starts first, followed by p2, and then p3. The respective total CPU times of the 3 processes are 8, 3, 5 time units. The context switching time is negligible.
a- Determine the average turnaround time, ATT, when the quantum is Q = 1 time unit. b- Determine the average turnaround time, ATT, when the quantum is Q = 3 time units.
4- Based on Exercise 3.3.2 – Determining Process Execution Time n processes are time-sharing the CPU using RR scheduling, each requiring T ms of CPU time to complete. a- How long will the execution take on a machine with n CPUs? b- How long will the execution take on a single CPU machine when the context switch overhead is zero? c- How long will the execution take on a single CPU machine when: I. The length of the time quantum is Q ms II. The length of the time quantum is Q ms d- Repeat the previous calculation using n=5, T=10,000, Q=100, S=10.
5- Based on Exercise 3.3.5 – Scheduling with MLF A MLF algorithm uses 5 priority levels. At level 5, a process executes for Q = 1 ms. At each of the lower levels the quantum is doubled (2Q, 4Q, 8Q, 16Q). The following processes are to be scheduled:
| Process | Arriva | Total CPU Time |
|---|---|---|
| P1 | 0 | 1 |
| P2 | 1 | 3 |
| P3 | 1 | 14 |
After termination, process p1 blocks for 4 ms and then reenters the queue again at level 5. Similarly, process p2 blocks for 5 ms and then reenters the queue again at level 5.
a- Draw a timing diagram for the first 33 ms. On each of the 3 lines (one per process) show when the process is running and at which priority level. b- Determine the ATT for each process.
6- Based on Exercise 3.4.2 – Determining Feasible Schedules Three periodic processes with the following characteristics are to be scheduled (D is the period and T is the total CPU time):
7- Based on Exercise 4.2.1 – Using P and V Operations to Enforce Precedence of Execution Four processes are executing the computations A through H:
The computations must be executed in the order given by the following precedence graph.
a- Insert P and V operations into the code to enforce the prescribed order. For example, since E and H must wait for A to complete, the processes p2 and p4 must each start with a P operation and A must end with 2 corresponding V operations. b- What are the initial semaphore values?
8- Based on Exercise 4.3.2 – A Different Implementation of P and V The following implementation of P and V uses busy-waiting inside P. Rather than blocking the process when s is less or equal 0, the process is prevented from continuing by executing Pb(ds), where ds is a binary semaphore initialized to 0. A V(s) then unblocks a process by performing Vb on the binary semaphore ds.
a- Since the original solution also uses Pb and Vb (implemented using busy-waiting), why is the above solution much worse in terms of performance?
9- Based on Exercise 4.5.6 – An Inadequate Solution to the Dining Philosophers Problem Each of the five philosophers, p[i], in the dining philosophers problem executes the code:
a- Does the solution satisfy all requirements of the dining philosophers problem?
