IS CS-2022S-01

题目来源：Problem 1 日期：2024-07-01 题目主题：CS-操作系统-进程调度

具体题目

Answer the following questions on operating systems.

For the scheduling of five processes $P_{0}$ , $P_{1}$ , $P_{2}$ , $P_{3}$ , and $P_{4}$ , the arrival time (ms) and the computation time (ms) of each process $P_{i}$ are denoted by $A_{i}$ and $C_{i}$ , respectively. Also, assume that only one process is allowed to execute at any instant, and the overhead of context switches can be ignored. Obtain the average turnaround time and the average response time when the five processes are scheduled by the Preemptive Shortest Job First algorithm, where $A_{0} = 35$ , $A_{1} = A_{2} = A_{3} = 25$ , $A_{4} = 0$ , $C_{0} = 10$ , $C_{1} = 15$ , $C_{2} = 20$ , $C_{3} = 30$ , and $C_{4} = 50$ . Here, the turnaround time refers to the time interval from the arrival of the process to the completion of its execution, and the response time refers to the time interval from the arrival of the process to the beginning of its execution.
Obtain the average turnaround time and the average response time when the five processes with the same arrival and computation times as those given in question (1) are scheduled by the Non-Preemptive Shortest Job First algorithm.
Obtain the average turnaround time and the average response time when the five processes with the same arrival and computation times as those given in question (1) are scheduled by the Round Robin algorithm with the time slice 10 ms. The next time slice starts immediately when the current process does not exhaust its time slice. Also, a new process is added to the end of the Round Robin queue upon its arrival, and ties are broken in favor of the processes with shorter remaining computation times if multiple processes arrive at the end of the queue simultaneously.
In real-world operating systems, the overhead of context switches cannot be ignored. Explain the pros and cons of the Round Robin algorithm from the viewpoint of CPU scheduling and memory management, when this overhead is considered.
The Aging scheme is often used to determine process priorities in real-world operating systems. Explain the basic concept of the Aging scheme and its advantage over the classical static-priority scheme.

正确解答

问题 1

Preemptive Shortest Job First (SJF) Algorithm:

Process Information:
- $P_{0}$ : $A_{0} = 35$ , $C_{0} = 10$
- $P_{1}$ : $A_{1} = 25$ , $C_{1} = 15$
- $P_{2}$ : $A_{2} = 25$ , $C_{2} = 20$
- $P_{3}$ : $A_{3} = 25$ , $C_{3} = 30$
- $P_{4}$ : $A_{4} = 0$ , $C_{4} = 50$
Gantt Chart:

| P4(0-25) | P1(25-40) | P0(40-50) | P2(50-70) | P4(70-95) | P3(95-125) |

Calculations:
- Completion Time (CT):
  - $C T_{0} = 50$
  - $C T_{1} = 40$
  - $C T_{2} = 70$
  - $C T_{3} = 125$
  - $C T_{4} = 95$
- Turnaround Time (TAT):
  - $T A T_{0} = C T_{0} - A_{0} = 50 - 35 = 15$
  - $T A T_{1} = C T_{1} - A_{1} = 40 - 25 = 15$
  - $T A T_{2} = C T_{2} - A_{2} = 70 - 25 = 45$
  - $T A T_{3} = C T_{3} - A_{3} = 125 - 25 = 100$
  - $T A T_{4} = C T_{4} - A_{4} = 95 - 0 = 95$
  - Average TAT = $\frac{15 + 15 + 45 + 100 + 95}{5} = 54$
- Response Time (RT):
  - $R T_{0} = 40 - 35 = 5$
  - $R T_{1} = 25 - 25 = 0$
  - $R T_{2} = 50 - 25 = 25$
  - $R T_{3} = 95 - 25 = 70$
  - $R T_{4} = 0 - 0 = 0$
  - Average RT = $\frac{5 + 0 + 25 + 70 + 0}{5} = 20$

问题 2

Non-Preemptive Shortest Job First (SJF) Algorithm:

Gantt Chart:

| P4(0-50) | P0(50-60) | P1(60-75) | P2(75-95) | P3(95-125) |

Calculations:
- Completion Time (CT):
  - $C T_{0} = 60$
  - $C T_{1} = 75$
  - $C T_{2} = 95$
  - $C T_{3} = 125$
  - $C T_{4} = 50$
- Turnaround Time (TAT):
  - $T A T_{0} = C T_{0} - A_{0} = 60 - 35 = 25$
  - $T A T_{1} = C T_{1} - A_{1} = 75 - 25 = 50$
  - $T A T_{2} = C T_{2} - A_{2} = 95 - 25 = 70$
  - $T A T_{3} = C T_{3} - A_{3} = 125 - 25 = 100$
  - $T A T_{4} = C T_{4} - A_{4} = 50 - 0 = 50$
  - Average TAT = $\frac{25 + 50 + 70 + 100 + 50}{5} = 59$
- Response Time (RT):
  - $R T_{0} = 50 - 35 = 15$
  - $R T_{1} = 60 - 25 = 35$
  - $R T_{2} = 75 - 25 = 50$
  - $R T_{3} = 95 - 25 = 70$
  - $R T_{4} = 0 - 0 = 0$
  - Average RT = $\frac{15 + 35 + 50 + 70 + 0}{5} = 34$

问题 3

Round Robin Algorithm (Time Slice = 10 ms):

Process Information:
- $P_{0}$ : $A_{0} = 35$ , $C_{0} = 10$
- $P_{1}$ : $A_{1} = 25$ , $C_{1} = 15$
- $P_{2}$ : $A_{2} = 25$ , $C_{2} = 20$
- $P_{3}$ : $A_{3} = 25$ , $C_{3} = 30$
- $P_{4}$ : $A_{4} = 0$ , $C_{4} = 50$
Gantt Chart:

| P4(0-10) | P4(10-20) | P4(20-30) | P1(30-40) | P2(40-50) | P3(50-60) | P4(60-70) | P0(70-80) | P1(80-85) | P2(85-95) | P3(95-105) | P4(105-115) | P3(115-125) |

Calculations:
- Completion Time (CT):
  - $C T_{0} = 80$
  - $C T_{1} = 85$
  - $C T_{2} = 95$
  - $C T_{3} = 125$
  - $C T_{4} = 115$
- Turnaround Time (TAT):
  - $T A T_{0} = C T_{0} - A_{0} = 80 - 35 = 45$
  - $T A T_{1} = C T_{1} - A_{1} = 85 - 25 = 60$
  - $T A T_{2} = C T_{2} - A_{2} = 95 - 25 = 70$
  - $T A T_{3} = C T_{3} - A_{3} = 125 - 25 = 100$
  - $T A T_{4} = C T_{4} - A_{4} = 115 - 0 = 115$
  - Average TAT = $\frac{45 + 60 + 70 + 100 + 115}{5} = 78$
- Response Time (RT):
  - $R T_{0} = 70 - 35 = 35$
  - $R T_{1} = 30 - 25 = 5$
  - $R T_{2} = 40 - 25 = 15$
  - $R T_{3} = 50 - 25 = 25$
  - $R T_{4} = 0 - 0 = 0$
  - Average RT = $\frac{35 + 5 + 15 + 25 + 0}{5} = 16$

问题 4

Pros and Cons of Round Robin Algorithm:

From the Viewpoint of CPU Scheduling:

Pros:
- Fairness: Ensures that each process gets an equal share of the CPU, avoiding starvation. This means no process is left waiting indefinitely while others are executed.
- Responsiveness: Particularly suitable for time-sharing systems as it guarantees that all processes get CPU time frequently. This can improve the perceived responsiveness of the system, especially for interactive users.
Cons:
- Context Switch Overhead: Frequent context switches, especially with a small time slice, can lead to significant overhead. This overhead includes saving and restoring process states, which can reduce overall CPU efficiency.
- Increased Turnaround Time: If the time slice is too small, processes may spend more time being switched in and out of the CPU rather than executing, increasing the average turnaround time. Long processes may take a disproportionately long time to complete.
- Poor Performance for Short Jobs: Short processes may need to wait for a full cycle to get CPU time, which can be inefficient and reduce overall system performance.

From the Viewpoint of Memory Management:

Pros:
- Predictable Memory Usage: The consistent and cyclic nature of Round Robin can make memory usage patterns more predictable, aiding in efficient memory management and planning.
Cons:
- High Context Switch Cost: Each context switch requires saving the state of the current process and loading the state of the next process. This can involve a significant amount of memory operations, especially if the processes have large memory footprints. This can lead to increased memory access times and cache invalidation, further reducing efficiency.
- Increased Memory Bandwidth: Frequent context switches can lead to increased demand on memory bandwidth as process states are repeatedly saved and restored. This can cause contention and delays in memory access for other processes or system components.
- Paging Overhead: In systems with limited physical memory, frequent context switches can lead to increased paging activity if the working sets of multiple processes cannot fit in memory simultaneously. This can cause additional overhead and degrade system performance.

问题 5

Aging Scheme:

Concept:
- Aging gradually increases the priority of processes waiting in the queue for a long time to prevent starvation. This means that if a process has been waiting for too long, its priority will be increased to ensure it eventually gets CPU time.
Advantage:
- Overcomes the starvation problem present in static-priority schemes, ensuring that all processes eventually get executed. This is particularly useful in systems where certain processes might otherwise be perpetually postponed.

知识点

PreemptiveSJF Non-PreemptiveSJF RoundRobin Aging ContextSwitch

解题技巧和信息

Preemptive vs Non-Preemptive SJF: Preemptive SJF allows switching to a shorter job, minimizing the average turnaround time but may cause more context switches.
Round Robin: Suitable for time-sharing but requires careful management of context switch overhead. Choose an appropriate time slice to balance between responsiveness and efficiency.
Aging: Prevents starvation by gradually increasing the priority of waiting processes, ensuring fair CPU allocation over time.

重点词汇

Turnaround Time 周转时间
Response Time 响应时间
Context Switch 上下文切换
Preemptive 抢占式
Non-Preemptive 非抢占式
Starvation 饥饿
Aging 老化

Zephyr's Notes on ISCS & CBMS, UTokyo

Explorer

Explorer

IS_CS-2022S-01