Process Scheduling Notes

Basic Concepts

Process State

• As a process executes, it transitions through different states:

  • New: The process is being created.

  • Running: Instructions are being executed.

  • Waiting: The process is waiting for an event (I/O completion, signal).

  • Ready: The process is waiting to be assigned to a processor.

  • Terminated: The process has finished execution.

CPU-I/O Burst Cycle

• Process execution is characterized by alternating cycles of CPU execution (CPU burst) and I/O wait (I/O burst).

• A process starts with a CPU burst, then performs I/O, followed by another CPU burst, and so on.

• The final CPU burst ends with a system request to terminate execution.

CPU Scheduler

• When the CPU becomes idle, the operating system selects a process from the ready queue to execute.

• The CPU scheduler carries out this selection process.

• The ready queue can be implemented using various data structures like FIFO queues, priority queues, trees, or linked lists.

• The ready queue typically stores process control blocks (PCBs) of the processes.

Preemptive and Nonpreemptive Scheduling

Preemptive Scheduling

• The operating system can interrupt (preempt) a currently running process.

• The CPU can be allocated to another process, often based on priority or scheduling criteria.

• Preemption occurs when:

  • A new process arrives with a higher priority.

  • A time quantum expires (e.g., in Round Robin scheduling).

• Requires context switching: saving the state of the preempted process and restoring the state of the new process.

Non-preemptive Scheduling

• Once a process is allocated the CPU, it runs to completion or voluntarily yields the CPU.

• The OS cannot interrupt the running process unless it completes or enters a waiting state.

• Fewer context switches compared to preemptive scheduling.

Dispatcher

• The dispatcher gives control of the CPU core to the process selected by the CPU scheduler.

• Dispatcher functions include:

  • Switching context from one process to another.

  • Switching to user mode.

  • Jumping to the proper location in the user program to resume execution.

• Context switches can be monitored using the vmstat command on Linux systems (e.g., vmstat 1 3 shows system-wide statistics including context switches per second).

Dispatch Latency

• Dispatch latency is the time taken by the dispatcher to stop one process and start another.

Scheduling Criteria

• CPU utilization: Keep the CPU as busy as possible (Maximize).

• Throughput: Number of processes that complete execution per time unit (Maximize).

• Turnaround time: The sum of time spent waiting in the ready queue, executing on the CPU, and doing I/O (Minimize).

• Waiting time: Amount of time a process has been waiting in the ready queue (Minimize).

• Response time: Amount of time it takes from request submission until the first response is produced (Minimize).

Scheduling Algorithms

First-Come, First-Served (FCFS) Scheduling

• Processes are executed in the order they arrive in the ready queue.

• Non-preemptive algorithm.

Advantages

• Simple and easy to implement.

• Fair in that processes are handled in order of arrival.

Disadvantages

• Convoy Effect: A long CPU burst process arriving first can cause subsequent processes to wait for a long time, increasing the average waiting time.

• Not optimal for systems requiring fast response times.

How it works

1. Processes are placed in the ready queue in order of arrival.

2. The first process in the queue is assigned the CPU until its CPU burst is complete.

3. Once the first process finishes, the next process in the queue is executed, and so on.

Example

• Processes arrive at time 0 with the following CPU burst times (in milliseconds):

• If processes arrive in the order P1, P2, P3:

  • Gantt Chart: P1(0-24), P2(24-27), P3(27-30)

  • Average waiting time: $(0 + 24 + 27) / 3 = 17$ milliseconds.

• If processes arrive in the order P2, P3, P1:

  • Gantt Chart: P2(0-3), P3(3-6), P1(6-30)

  • Average waiting time: $(0 + 3 + 6) / 3 = 3$ milliseconds.

Shortest-Job-First (SJF) Scheduling

• Prioritizes the process with the shortest CPU burst at the time the CPU becomes available.

• Non-preemptive algorithm.

• If two processes have the same CPU burst time, FCFS is used to break the tie.

Advantages

• Optimizes average waiting time.

• Efficient in systems where CPU burst times can be predicted.

Disadvantages

• Requires prior knowledge of CPU burst times.

• Can lead to starvation.

• Not suitable for systems requiring fast response times.

How It Works

1. Processes are placed in the ready queue.

2. When the CPU becomes available, the process with the shortest CPU burst is selected.

3. The process runs to completion.

Example

• Consider the following set of processes with CPU burst times:

• Gantt chart: P4(0-3), P1(3-9), P3(9-16), P2(16-24)

• The average waiting time is $(3 + 16 + 9 + 0)/4 = 7$ milliseconds.

Predicting CPU Burst Time

• A prediction method is used to estimate the CPU burst time based on the history of previous CPU bursts.

• The next CPU burst is often similar to previous bursts.

• An exponential average of previous CPU bursts is calculated.

• Let $t_n$ be the actual CPU burst time of the $n$-th execution of a process.

• Let $\tau_{n+1}$ be the predicted CPU burst time for the $(n+1)$-th execution.

• The exponential average formula is: $\tau<em>{n+1} = \alpha t</em>n + (1 - \alpha) \tau_n$ where:

  • $\alpha$ is a weighting factor, with $0 \le \alpha \le 1$.

  • $\tau_n$: The predicted CPU burst time for the current execution.

• The initial $\tau_0$ can be defined as a constant or as an overall system average.

Expanded Formula

• Substituting $\tau<em>n$ in the formula $\tau</em>{n+1} = \alpha t<em>n + (1 - \alpha) \tau</em>n$ yields:
  $\tau<em>{n+1} = \alpha t</em>n + (1 - \alpha)(\alpha t<em>{n-1} + (1 - \alpha) \tau</em>{n-1})$

• Continuing to expand, we get:
  $\tau<em>{n+1} = \alpha t</em>n + (1 - \alpha) \alpha t<em>{n-1} + … + (1 - \alpha)^{n-j} \alpha t</em>{n-j} + … + (1 - \alpha)^{n+1} \tau_0$

• This shows that $\tau<em>{n+1}$ is a linear combination of all actual CPU burst times from $t</em>0$ to $t<em>n$, plus the initial value $\tau</em>0$, with weights that decrease over time.

Example

• Calculating $\tau<em>4$ with $\alpha = 1/2$ and $\tau</em>0 = 10$:
  $\tau<em>4 = \alpha t</em>3 + (1 - \alpha) \alpha t<em>2 + (1 - \alpha)^2 \alpha t</em>1 + (1 - \alpha)^3 \tau_0$

• If $t<em>3 = 6$, $t</em>2 = 4$, $t<em>1 = 6$: $\tau</em>4 = (0.5 \times 6) + (0.5 \times 0.5 \times 4) + (0.5^2 \times 0.5 \times 6) + (0.5^3 \times 10)$
  $\tau<em>4 = 3 + 1 + 0.75 + 1.25$ $\tau</em>4 = 7$

Shortest-Remaining-Time-First (SRTF) Scheduling

• If a new process arrives with a remaining time shorter than the remaining time of the running process, the current process is preempted.

• Preemptive algorithm.

Advantages

• Reduces average waiting time.

• Theoretically optimal for minimizing average waiting time if CPU burst times are known.

Disadvantages

• Requires prior knowledge of CPU burst times.

• Increases system overhead due to context switches.

• Can cause starvation.

How it works

1. At each time step, the OS checks all processes in the ready queue.

2. The process with the shortest remaining time is selected.

3. If a new process arrives with a shorter burst time, the current process is preempted.

Example

• Consider four processes with burst times and arrival times:

• The average waiting time is $[(10 - 1) + (1 - 1) + (17 - 2) + (5 - 3)]/4 = 26/4 = 6.5$ milliseconds.

Round Robin (RR) Scheduling

• Ensures fairness among processes.

• Each process is assigned the CPU for a fixed time interval (time quantum).

• Preemptive algorithm.

• Processes are placed in a circular queue.

How it works

1. Processes are placed in a circular queue.

2. The first process in the queue is assigned the CPU and runs for one time quantum.

3. If the process completes within the time quantum, it releases the CPU.

4. If the process does not complete, it is preempted and placed at the end of the queue.

Advantages

• Fairness.

• Suitable for time-sharing systems.

• Easy to implement and manage.

Disadvantages

• Context switch overhead.

• High average waiting time if the time quantum is not chosen appropriately.

• Performance depends on the time quantum.

Example

• Consider the set of processes arriving at time 0 with given burst times:

• With a time quantum of 4 milliseconds, the average waiting time is $17/3 = 5.66$ milliseconds.

Priority Scheduling

• Each process is assigned a priority.

• The CPU is allocated to the process with the highest priority.

• If two processes have the same priority, they are scheduled in FCFS order.

Advantages

• Simple to implement.

• Prioritizes important processes.

Disadvantages

• Starvation.

• Not optimal for systems requiring fast response times.

Example

• Consider the set of processes arriving at time 0 with burst times and priorities:

• The average waitting time is $8.2$ milliseconds.

• With a time quantum of 2 milliseconds, the average waiting time is $14$ milliseconds.