This is a set of problems and explanations from the course, Operating Systems in a computer science program. To avoid copyright infringement, all problems have been modified from the original. All problems refer to the "Operating Systems" in zyBooks.
Also brief explanations in Japanese are included for Japanese readers.
Problem 1 Scheduling with FIFO, SJF, and SRT.
1-1
Three processes are depicted. Complete the missing values by applying FIFO scheduling.
Calculate the average turnaround time (ATT):
1-2
Three processes are depicted. Complete the missing values by applying SJF scheduling.
1-3
Three processes are depicted. Complete the missing values by applying SRJ scheduling.
Problem 2 Predicting CPU bursts.
The observed CPU burst sequence is as follows: 7, 6, 4, 5, 14, 14.
a) Utilizing an initial estimate of 7 (S₀), generate the sequence of predictions (Si) for the corresponding observed values (Ti) with 1≤i≤5 and a rate of the relative weight of α=0.8.
b) Perform the identical predictions with a rate of the relative weight of α=0.5.
Problem 3 Determining quantum size.
In a scenario where n processes share the CPU via time-sharing, and each process necessitates T ms of CPU time to finish, a context switching overhead of S ms is present.
a) What should the quantum size Q, be set to ensure that the time gap between the end of one quantum and the start of the subsequent quantum for any process does not surpass M ms?
b) Given n = 5, S = 10, and M = 350, M = 100 and M = 60, find:
The associated values of Q.
The percentage of CPU time wasted on context switching.
Problem 4 MLF scheduling.
A Multi-Level Feedback (MLF) algorithm employs 5 priority levels. At level 5, a process runs for a time quantum of 1 ms. As we move down the priority levels, each subsequent level’s quantum is doubled (2Q, 4Q, 8Q, 16Q).
Now, consider the following processes:
Following termination, process p1 pauses for 4 ms before rejoining the queue at level 5. Likewise, process p2 pauses for 5 ms before returning to the queue at level 5.
a) Illustrate a timing diagram for the first 33 ms. Use three lines, each representing one of the processes, to indicate when they are active and at what priority level.
b) Calculate the Average Turnaround Time for each process.
Answers
To problem 1
1-1
ATT = (5 + 7 + 10)/3 = 7.33
1-2
1-3
To problem 2
For short-term scheduling, the most common approach to predict the total CPU time uses exponential averaging, which combines the last estimate of the total CPU time, Sₙ, with the last actually observed total CPU time, Tₙ, to predict the next total CPU time, Sₙ₊₁:
α controls the relative weight of the last observation(Tₙ) versus the history of past predictions(Sₙ).
a)
Sₙ₊₁ = αTₙ₊₁ + (1 - α)Sₙ
S₁ = (0.8)7 + (0.2)7 = 7
S₂ = (0.8)6 + (0.2)7 = 6.2
S₃ = (0.8)4 + (0.2)6.2 = 4.44
S₄ = (0.8)5 + (0.2)4.44 = 4.89
S₅ = (0.8)14 + (0.2)4.89 = 12.18
b)
S₁ = (0.5)7 + (0.5)7 = 7
S₂ = (0.5)6 + (0.5)7 = 6.5
S₃ = (0.5)4 + (0.5)6.5 = 5.25
S₄ = (0.5)5 + (0.5)5.25 = 5.125
S₅ = (0.5)14 + (0.5)5.125 = 9.56
To problem 3
a)
Between the end of one quantum and the start of the next, n - 1 processes each execute one quantum: (n - 1)Q. In addition, n context switches are required before the next n + 1 process is started. The sum of these two times must not exceed the limit M, i.e., (n - 1)Q + nS ≤ M.
Solving this for Q, we get
b)
When M = 350, Q = (350 - 50)/(5 - 1) = 300/4 = 75
When M = 100, Q = (100 - 50)/(5 - 1) = 50/4 = 12.5
When M = 60, Q = (60 - 50)/(5 - 1) = 10/4 = 2.5
The formula for the percentage of CPU time wasted is
When M = 350, time wasted = 100*10/(75 + 10) = 11.76%
When M = 100, time wasted = 100*10/(12.5 + 10) = 44.44%
When M = 60, time wasted = 100*10/(2.5 + 10) = 80%
To problem 4
a)
Explanation:
Under the multilevel feedback (MLF) algorithm, a newly arriving process enters the highest-priority queue, N, and then executed for Q time units. For example, At the time of 6ms, process p2 terminated at level 2 and blocks for 5 ms, and then reentered the queue again at level 5 at the time of 11ms.
（MLFアルゴリズムでは、新しく到着したプロセスが最優先キューNに入り、Qクオンタム分実行される。例えば、6ms時点でp2はレベル2でプロセスを終了させ、5msブロックした後、11ms時点で再度レベル5のキューに入り直している。)
b)
p1 executes 5 times. In the first execution, the waiting time is 2 and the CPU time is 2. So the turnaround time is 4. In the rest of the executions, the waiting time is 0 and the CPU time is 2. So the turnaround time is 2.
ATT:(4+2+2+2+2)/5 = 2.4
p2 executes 4 times. In the first and third executions, the waiting time is 2 and the CPU time is 3. So the turnaround time is 5. In the second and fourth executions, the waiting time is 0 and the CPU time is 3. So the turnaround time is 3.
ATT: (5+3+5+3)/4 = 4
p3 executes 4 time. the waiting time is 17 and the CPU time is 10.
ATT: 17+10 = 27
Note: The turnaround Time ＝ The waiting time + The CPU time
Top comments (0)