Exponential Averaging and Scheduling Algorithms

Exponential Averaging

Definition: Exponential averaging is a technique used to predict the next CPU burst time based on previous burst times.
Formula Variations:
- When α = 0:
  - Formula: τ_n+1 = τ_n
  - Implication: Recent history does not influence the prediction.
- When α = 1:
  - Formula: τ_n+1 = αt_n
  - Implication: Only the most recent CPU burst is considered.
- General Case:
  - Expanded formula: τ_{n+1} = αt_n + (1 - α)αt_{n-1} + ... + (1 - α)^{n+1}τ_0
  - Observation: Each successive term has less weight than its predecessor since both α and (1 - α) are ≤ 1.

Shortest Remaining Time First (SRTF)

Definition: SRTF is a preemptive scheduling algorithm that selects the process with the smallest remaining time to completion.

Example Scenario:

Processes with arrival times and CPU bursts:

Process	Arrival Time	Burst Time
P1	0	8
P2	1	4
P3	2	9
P4	3	5

Average Waiting Time Calculation:
- Waiting Time for P1: (10 - 1 - 0) = 9 ms
- Waiting Time for P2: (1 - 0 - 1) = 0 ms
- Waiting Time for P3: (17 - 0 - 2) = 15 ms
- Waiting Time for P4: (5 - 0 - 3) = 2 ms
- Average Waiting Time: (9 + 0 + 15 + 2) / 4 = 6.5 ms

Turnaround Time in SRTF

Definition: Turnaround time is the total time taken from arrival to completion of a process.

Example Scenario:

Processes:

Process ID	Arrival Time	Burst Time
P1	0	10
P2	3	6
P3	7	1
P4	8	3

Turnaround Time Calculation:
- Turnaround Time for P1: (20 - 0) = 20 ms
- Turnaround Time for P2: (10 - 3) = 7 ms
- Turnaround Time for P3: (8 - 7) = 1 ms
- Turnaround Time for P4: (13 - 8) = 5 ms
- Average Turnaround Time: (20 + 7 + 1 + 5) / 4 = 8.25 ms

Shortest Job First (SJF) Scheduling

Definition: SJF is a non-preemptive scheduling algorithm that selects the process with the smallest burst time.

Example Scenario:

Processes:

Process ID	Arrival Time	Burst Time
P0	0	7
P1	2	4
P2	4	1
P3	5	4

Average Turnaround Time Calculation:
- Average Turnaround Time: (7 + 10 + 4 + 11) / 4 = 8 ms
- Average Waiting Time: (0 + 6 + 3 + 7) / 4 = 4 ms

Priority Scheduling

Definition: In priority scheduling, each process is assigned a priority, and the CPU is allocated to the process with the highest priority.
Characteristics:
- Equal-priority processes are scheduled in First-Come-First-Serve (FCFS) order.
- SJF can be viewed as a priority scheduling algorithm where priority is inversely related to the predicted CPU burst time.
- Priority scheduling can be either preemptive or non-preemptive.

Example Scenario:

Processes:

Process ID	Burst Time	Priority
P1	10	3
P2	1	1
P3	2	4
P4	1	5
P5	5	2

Average Waiting Time Calculation:
- Waiting Time for P1: 6 ms
- Waiting Time for P2: 0 ms
- Waiting Time for P3: 16 ms
- Waiting Time for P4: 18 ms
- Waiting Time for P5: 1 ms
- Average Waiting Time: (6 + 0 + 16 + 18 + 1) / 5 = 8.2 ms

Challenges in Priority Scheduling

Indefinite Blocking (Starvation): Low-priority processes may wait indefinitely for CPU time due to a continuous influx of high-priority processes.
Solution - Aging: Aging is a technique that gradually increases the priority of waiting processes to prevent starvation.
Example of Aging:
- If priorities range from 127 to 0, a waiting process's priority is increased by 1 every 15 minutes.
- This ensures that even a process with an initial priority of 127 will eventually gain a higher priority, allowing it to execute.

CPU Scheduling and Process Management

Key Concepts

I/O Time: The duration a process spends performing input/output operations. Generally, I/O time is ignored in CPU scheduling discussions, focusing instead on CPU time.
Burst Time: The total time a process requires for execution on the CPU.
Arrival Time: The moment a process enters the ready state, prepared for execution. For example:
- P1: 0 ms
- P2: 1 ms
- P3: 2 ms

CPU Scheduler

The CPU scheduler is responsible for selecting processes from the ready queue when the CPU becomes idle.
It operates under the following conditions:
1. Switches from running to waiting state: The CPU is assigned to another process.
2. Switches from running to ready state: The CPU switches to another ready process due to an interrupt.
3. Switches from waiting to ready: The OS chooses among processes that are now ready to run.
4. Process termination: The CPU is free and must be assigned to a new process.
In non-preemptive scheduling, once a process is allocated the CPU, it retains it until it either terminates or enters a waiting state.
Preemptive scheduling allows the OS to interrupt a running process and allocate the CPU to a different process, providing flexibility and reducing potential race conditions.

Dispatcher

The dispatcher module transfers control of the CPU to the selected process by the short-term scheduler.
Key functions of the dispatcher include:
- Context switching: Managing the transition between processes.
- Switching to user mode: Changing the CPU mode to allow user processes to run.
- Jumping to the appropriate location in the user program to resume execution.
Dispatch Latency: The time taken by the dispatcher to stop one process and start another, crucial for maintaining system performance.

Scheduler vs Dispatcher

Scheduler: Selects which process from the ready queue will be executed next.
Dispatcher: Allocates the CPU to the selected process, performing the necessary context switch.

Scheduling Criteria

Different CPU scheduling algorithms have varying properties, and the choice of algorithm is influenced by several factors:
- CPU Utilization: Keeping the CPU as busy as possible.
- Throughput: The number of processes completed per time unit, indicating the work done by the CPU.
- Turnaround Time: The total time taken from the moment a process enters the ready state until its completion, calculated as: TAT = W + R + E + I where W = waiting time, R = time in ready queue, E = execution time on CPU, and I = I/O time.
- Waiting Time: The duration a process spends waiting in the ready queue.
- Response Time: The time from when a request is submitted until the first response is produced.

Example of Turnaround Time Calculation

Given processes P1, P2, and P3 with burst times of 5 ms, 15 ms, and 10 ms respectively:
- P1 completes in 5 ms.
- P2 completes in 20 ms (5 ms waiting for P1 + 15 ms execution).
- P3 completes in 30 ms (5 ms waiting for P1 + 15 ms waiting for P2 + 10 ms execution).

Response Time Calculation

For the processes:
- P1: Response Time = 0 ms (first to execute).
- P2: Response Time = 7 ms (waits for P1 to finish).
- P3: Response Time = 13 ms (waits for both P1 and P2).

Optimization Criteria for Scheduling Algorithms

Maximize CPU utilization and throughput.
Minimize turnaround time, waiting time, and response time.

Types of Scheduling Algorithms

Various CPU scheduling algorithms include:
1. First-Come, First-Served (FCFS)
2. Shortest Job Next (SJN)
3. Priority Scheduling
4. Shortest Remaining Time
5. Round Robin (RR)
6. Multiple-Level Queues Scheduling

Process Scheduling and Time Management

Process Information

The following table summarizes the process details including their IDs, arrival times, burst times, completion times, turnaround times, and waiting times:

Process ID	Arrival Time	Burst Time	Completion Time	Turnaround Time	Waiting Time
P1	0	5	13	13 - 0 = 13	13 - 5 = 8
P2	1	3	12	12 - 1 = 11	11 - 3 = 8
P3	2	1	5	5 - 2 = 3	3 - 1 = 2
P4	3	2	9	9 - 3 = 6	6 - 2 = 4
P5	4	3	14	14 - 4 = 10	10 - 3 = 7

Round Robin (RR) Scheduling

Overview: Round Robin scheduling is designed to ensure fair CPU allocation among processes, improving response times by providing regular time slices.
Average Turnaround Time: Typically, RR has a higher average turnaround time compared to Shortest Job First (SJF) but offers better response times.
Time Quantum (q):
- Should be larger than the context switch time to minimize the frequency of context transitions.
- Commonly set between 10 ms and 100 ms, while context switch time should be less than 10 microseconds (μs).
Efficiency: A larger time quantum allows processes to utilize more of their allotted time, reducing the overhead of context switching.

Trade-offs in Time Quantum and Context Switch Time

Choosing the right time quantum involves balancing turnaround time and context switch time. A smaller time quantum may lead to increased context switches, thereby increasing the average turnaround time.

Impact of Time Quantum on Turnaround Time

Turnaround time is minimized when most processes complete their CPU bursts within one time quantum.
Using a 1 ms quantum often results in longer turnaround times as most processes cannot complete in a single quantum.
A 10 ms quantum allows most processes to complete within one quantum, resulting in shorter turnaround times.
Example:
- Average turnaround time with a 1 ms quantum is 29.
- Average turnaround time with a 10 ms quantum is 20.
Adding context switch time further increases the average turnaround time for smaller time quantums due to more frequent context switches.
Rule of thumb: 80% of CPU bursts should be smaller than the time quantum to optimize performance.

Multilevel Queue Scheduling

Definition: A multilevel queue scheduling algorithm categorizes processes into different groups based on specific characteristics.
Queue Types:
- Foreground Processes: Interactive processes that require quick response times.
- Background Processes: Batch processes that do not require immediate interaction.
Scheduling Needs: Different groups have varying response time requirements and scheduling needs.
Priority: Foreground processes typically have priority over background processes.

Multilevel Queue Scheduling Example

Each queue can implement its own scheduling algorithm:
- Foreground processes may use Round Robin (RR).
- Background processes may use First-Come, First-Served (FCFS).
Scheduling Between Queues:
- Fixed priority scheduling: Serve all from the foreground queue before moving to the background queue, which may lead to starvation of background processes.
- Time slice allocation:
  - 80% of CPU time allocated to foreground processes using RR.
  - 20% of CPU time allocated to background processes using FCFS.
In multilevel scheduling, processes are permanently assigned to a queue based on properties such as memory size, process priority, or process type.

Conclusion

Understanding the intricacies of process scheduling, including Round Robin and Multilevel Queue algorithms, is crucial for optimizing CPU utilization and improving system performance. The choice of time quantum and the management of context switches are key factors that influence turnaround times and overall efficiency.

Pthread Scheduling and Operating System Scheduling Concepts

Pthread Scheduling API

The Pthread library provides a way to manage threads in C programming.
Thread attributes can be set using pthread_attr_setscope to define the scheduling scope:

PTHREAD_SCOPE_PROCESS: Threads can be scheduled across multiple processes.
PTHREAD_SCOPE_SYSTEM: Threads are scheduled within the system, allowing for more efficient scheduling.

Example code snippet:

if (scope == PTHREAD_SCOPE_PROCESS) printf("PTHREAD_SCOPE_PROCESS"); else if (scope == PTHREAD_SCOPE_SYSTEM) printf("PTHREAD_SCOPE_SYSTEM"); else fprintf(stderr, "Illegal scope value.\n");

Threads are created using pthread_create and joined with pthread_join.
Each thread begins execution in a specified function, typically defined as:

void *runner(void *param) { /* do some work ... */ pthread_exit(0); }

Operating System Scheduling Examples

Common operating systems with distinct scheduling strategies include:

Linux
Windows
Solaris

Linux Scheduling

Linux Scheduling Through Version 2.5

Prior to kernel version 2.5, Linux used a variation of the standard UNIX scheduling algorithm.
Version 2.5 introduced a constant order O(1) scheduler, enhancing performance by ensuring scheduling time remains constant regardless of task number.
This scheduler is:
- Preemptive and priority-based.
- Utilizes two priority ranges: time-sharing (0-139) and real-time (0-99).
- Tasks are tracked in a per-CPU run queue with two priority arrays (active and expired).
Drawbacks included poor response times for interactive processes.

Linux Scheduling in Version 2.6.23+

Introduced the Completely Fair Scheduler (CFS).
Tasks are prioritized based on CPU time proportion rather than fixed time allotments.
Two main scheduling classes: default and real-time, with quantum calculated based on a nice value ranging from -20 to +19.
CFS maintains a virtual run time (vruntime) for each task to determine scheduling priority.
The scheduler selects the task with the lowest vruntime to run next.

CFS Performance

CFS uses a red-black tree to manage runnable tasks.
Tasks with smaller vruntime values are positioned towards the left of the tree, indicating higher priority.
The leftmost node represents the task with the highest priority.

Real-Time Scheduling in Linux

Real-time tasks have static priorities and are mapped into a global priority scheme.
Nice values range from -20 (highest priority) to +19 (lowest priority), with the mapping formula:

Priority = 120 + nice value

Example mappings:

Nice -20 maps to 100.
Nice +19 maps to 139.

Windows Scheduling

Windows employs a priority-based preemptive scheduling model.
The dispatcher is responsible for managing thread execution.
Threads run until they block, exhaust their time slice, or are preempted by a higher-priority thread.
Windows uses a 32-level priority scheme:

Variable class: 1-15
Real-time class: 16-31
Priority 0 is reserved for memory management threads.

Each priority level has a corresponding queue, and if no threads are ready, the dispatcher executes an idle thread.

Windows Priority Classes

Win32 API defines several priority classes:

REALTIME_PRIORITY_CLASS
HIGH_PRIORITY_CLASS
ABOVE_NORMAL_PRIORITY_CLASS
NORMAL_PRIORITY_CLASS
BELOW_NORMAL_PRIORITY_CLASS
IDLE_PRIORITY_CLASS

Threads within a priority class can have relative priorities, allowing finer adjustments.
Priority levels range from 0 (lowest) to 31 (highest), with a base priority of NORMAL.
Quantum expiration results in priority reduction, but not below the base level.

Windows Priority Class Use Cases

Priority Class	Priority Level	Typical Use Case
Idle Priority Class	Lowest	Background maintenance tasks
Below Normal Priority Class	Low	Background services, low-priority tasks
Normal Priority Class	Default	General applications (e.g., web browsers)
Above Normal Priority Class	Moderate	Important background tasks needing a boost
High Priority Class	High	Time-sensitive tasks (e.g., multimedia)
Real-Time Priority Class	Highest	Critical real-time processing

Solaris Scheduling

Solaris employs priority-based scheduling with six available classes:

Time sharing (default)
Interactive
Real-time
System
Fair Share
Fixed priority

Each class has its own scheduling algorithm, with time-sharing using a multi-level feedback queue.
Priority management includes:

Lower priority threads receive more time quantum.
Threads that exhaust their quantum are considered CPU-intensive and have their priorities lowered.
Threads returning from sleep have their priorities boosted to improve response times for interactive processes.

End of Chapter 6

Priority Scheduling and Round Robin Scheduling

Priority Scheduling

Definition: A CPU scheduling algorithm where processes are assigned a priority. The process with the highest priority (lowest numerical value) is executed first.
Process Information:
- Processes are characterized by their arrival time, burst time, and priority.
- Example set of processes:
  - P1: Arrival Time = 0, Burst Time = 11, Priority = 9
  - P2: Arrival Time = 5, Burst Time = 28, Priority = 0
  - P3: Arrival Time = 12, Burst Time = 2, Priority = 3
  - P4: Arrival Time = 2, Burst Time = 10, Priority = 7
  - P5: Arrival Time = 9, Burst Time = 16, Priority = 4
Gantt Chart: A visual representation of process execution over time.
Average Waiting Time Calculation:
- Formula: Waiting Time = Total Waiting Time - No. of ms Process Executed - Arrival Time
- Example Calculations:
  - Waiting Time for P1 = (40 - 2 - 0) = 38 ms
  - Waiting Time for P2 = (5 - 0 - 5) = 0 ms
  - Waiting Time for P3 = (49 - 0 - 12) = 37 ms
  - Waiting Time for P4 = (33 - 3 - 2) = 28 ms
  - Waiting Time for P5 = (51 - 0 - 9) = 42 ms
- Average Waiting Time: Average Waiting Time = (38 + 0 + 37 + 28 + 42) / 5 = 29 ms

Non-Preemptive Priority Scheduling

Characteristics:
- Higher numerical values indicate higher priority.
- CPU scheduling is non-preemptive.
Process Information:
- P1: Arrival Time = 0, Burst Time = 4, Priority = 2
- P2: Arrival Time = 1, Burst Time = 3, Priority = 3
- P3: Arrival Time = 2, Burst Time = 1, Priority = 4
- P4: Arrival Time = 3, Burst Time = 5, Priority = 5
- P5: Arrival Time = 4, Burst Time = 2, Priority = 5
Turnaround Time and Waiting Time Calculations:
- Turnaround Time = Completion Time - Arrival Time
- Waiting Time = Turnaround Time - Burst Time
- Example Calculations:
  - P1: Completion Time = 4, Turnaround Time = 4 - 0 = 4, Waiting Time = 4 - 4 = 0
  - P2: Completion Time = 15, Turnaround Time = 15 - 1 = 14, Waiting Time = 14 - 3 = 11
  - P3: Completion Time = 12, Turnaround Time = 12 - 2 = 10, Waiting Time = 10 - 1 = 9
  - P4: Completion Time = 9, Turnaround Time = 9 - 3 = 6, Waiting Time = 6 - 5 = 1
  - P5: Completion Time = 11, Turnaround Time = 11 - 4 = 7, Waiting Time = 7 - 2 = 5
- Average Turnaround Time: Average Turnaround Time = (4 + 14 + 10 + 6 + 7) / 5 = 8.2 ms
- Average Waiting Time: Average Waiting Time = (0 + 11 + 9 + 1 + 5) / 5 = 5.2 ms

Round Robin Scheduling

Definition: A scheduling algorithm designed for time-sharing systems, incorporating preemption.
Process Execution:
- Each process is assigned a time quantum (typically between 10 to 100 ms).
- The CPU scheduler assigns the CPU to the first process in the ready queue.
- Processes are executed in a FIFO manner, with new processes added to the tail of the queue.
Execution Flow:
- The CPU scheduler picks the first process from the ready queue and sets a timer for the time quantum.
- Two scenarios may occur:
  - The process completes its burst time within the quantum, or
  - The process requires more time than the quantum, leading to a timer interrupt.
- In case of a timer interrupt, a context switch occurs, and the process is placed at the end of the ready queue.
Choosing Time Quantum:
- A larger time quantum can lead to behavior similar to FCFS, causing starvation for shorter processes.
- A smaller time quantum can result in excessive context switching, increasing overhead.
- Finding a balance is crucial for optimal performance.

Process Scheduling Algorithms

Average Waiting Time Calculation

Average Waiting Time Formula: W_{avg} = \frac{W_1 + W_2 + W_3 + W_4 + W_5}{5}
- Example Calculation: W_{avg} = \frac{0 + 7 + 0 + 11 + 4}{5} = \frac{22}{5} = 4.4

Process Information

Process ID	Arrival Time	Burst Time
P1	4	5
P2	6	4
P3	0	3
P4	6	2
P5	5	4

Completion, Turnaround, and Waiting Times

Process ID	Completion Time	Turnaround Time	Waiting Time
P1	9	9 - 4 = 5	5 - 5 = 0
P2	17	17 - 6 = 11	11 - 4 = 7
P3	3	3 - 0 = 3	3 - 3 = 0
P4	19	19 - 6 = 13	13 - 2 = 11
P5	13	13 - 5 = 8	8 - 4 = 4

First-Come, First-Served (FCFS) Scheduling

Advantages:
- Simple and easy to implement.
Disadvantages:
- Can suffer from the Convoy Effect, where long processes can delay shorter ones.
- May result in low throughput.
- High turnaround, waiting, and response times.
- Particularly problematic in time-sharing systems.
- Non-preemptive nature can lead to inefficiencies.

Shortest Job First (SJF) Scheduling

Definition: The process with the shortest execution time is selected next.
Associates each process with the length of its next CPU burst.
When the CPU is available, it is assigned to the process with the smallest next CPU burst.
In case of ties, FCFS is used to break them.
SJF can be:
- Non-preemptive
- Preemptive (known as Shortest Remaining Time Next)
Optimal in terms of minimizing average waiting time.

Advantages and Disadvantages of SJF

Advantages:
- Reduces waiting time compared to FCFS.
Disadvantages:
- May lead to starvation for longer processes.
- Can result in long turnaround times.
- Difficulty in predicting the length of the next CPU request.

Example of SJF Scheduling

Processes and their burst times:

Process	Burst Time
P1	6
P2	8
P3	7
P4	3

Gantt Chart and Average Waiting Time Calculation:
- Waiting Time for P1 = 3 ms
- Waiting Time for P2 = 16 ms
- Waiting Time for P3 = 9 ms
- Waiting Time for P4 = 0 ms
- Average Waiting Time: W_{avg} = \frac{3 + 16 + 9 + 0}{4} = 7
- Comparison with FCFS: W_{avg} = 10.25 ms

Determining Length of Next CPU Burst

Estimation of the next CPU burst length is based on previous bursts.
Utilizes exponential averaging for prediction.
Commonly, the value of α is set to ½.
Preemptive version is called shortest remaining time first.
Formula for predicting the next CPU burst: \tau_{n+1} = \alpha t_n + (1 - \alpha) \tau_n

Examples of Exponential Averaging

If α = 0: \tau_{n+1} = \tau_n (Recent history does not count)
If α = 1: \tau_{n+1} = \alpha t_n (Only the last CPU burst counts)
Expanded formula: \tau_{n+1} = \alpha t_n + (1 - \alpha) \alpha t_{n-1} + \ldots

CPU Scheduling Overview

CPU scheduling is a critical function of the operating system (OS) that allocates CPU time among various processes or tasks. The primary objectives of CPU scheduling include:

Ensuring fair distribution of CPU time and resources among tasks.
Preventing any single task from monopolizing CPU resources.

There are several CPU scheduling algorithms, each with its own approach to managing process execution:

First-Come, First-Served (FCFS) Scheduling
Shortest Job Next (SJN) Scheduling
Priority Scheduling
Shortest Remaining Time
Round Robin (RR) Scheduling
Multiple-Level Queues Scheduling

First-Come, First-Served (FCFS) Scheduling

FCFS is the simplest CPU scheduling algorithm, characterized by the following features:

Processes are scheduled based on their arrival time; the first process to arrive is the first to be allocated CPU time.
Implementation utilizes a First-In-First-Out (FIFO) queue, where each process's Process Control Block (PCB) is linked at the tail of the queue upon arrival.
When the CPU becomes available, it services the process at the head of the queue.
FCFS is a non-preemptive scheduling algorithm, meaning that once a process starts executing, it runs to completion without interruption.

Example of FCFS Scheduling

Consider three processes with the following burst times:

P1: 24 ms
P2: 3 ms
P3: 3 ms

Assuming they arrive in the order P1, P2, P3, the Gantt chart would look like this:

Gantt Chart FCFS Example 1

Calculating the waiting times:

Waiting Time for P1 = 0 ms
Waiting Time for P2 = 24 ms
Waiting Time for P3 = 27 ms

Average waiting time = (0 + 24 + 27) / 3 = 17 ms.

Impact of Process Order on FCFS

If the processes arrive in a different order, such as P2, P3, P1, the results change significantly:

New waiting times:

Waiting Time for P1 = 6 ms
Waiting Time for P2 = 0 ms
Waiting Time for P3 = 3 ms

Average waiting time = (0 + 3 + 6) / 3 = 3 ms, demonstrating that the order of arrival greatly affects performance.

Convoy Effect in FCFS Scheduling

The convoy effect occurs when a process with a long burst time delays shorter processes. Key points include:

When a long process is executed first, shorter processes must wait, leading to inefficient CPU utilization.
This effect can severely degrade system performance, particularly when many short processes are queued behind a single long process.

Round Robin (RR) Scheduling

Round Robin scheduling is designed to provide a fair allocation of CPU time among processes. Key characteristics include:

Each process receives a small unit of CPU time, known as a time quantum (q), typically ranging from 10 to 100 milliseconds.
After the time quantum expires, the process is preempted and moved to the end of the ready queue.
If there are n processes in the queue, each process effectively gets 1/n of the CPU time in chunks of at most q time units.
No process waits more than (n - 1) * q time units before it gets another chance to execute.

Timer interrupts are used to manage the scheduling of processes at the end of each quantum.

Example of Round Robin Scheduling

Consider the following processes with a time quantum of 4 ms:

P1: 24 ms
P2: 3 ms
P3: 3 ms

The Gantt chart for this scenario would be constructed as follows:

Gantt Chart RR Example

Calculating turnaround time and average waiting time:

Turnaround Time = Completion Time – Arrival Time
Waiting Time = Turnaround Time – Burst Time

Average Turnaround Time = (30 + 7 + 10) / 3 = 15.66 ms

Average Waiting Time = (6 + 4 + 7) / 3 = 5.66 ms

Further Examples of RR Scheduling

In subsequent examples, variations in process burst times and arrival times can lead to different average waiting and turnaround times. For instance:

With a time quantum of 2 ms, the average turnaround time and average waiting time can be calculated based on the specific processes and their characteristics.

Overall, understanding these scheduling algorithms is crucial for optimizing CPU utilization and improving system performance.

Multilevel Queue Scheduling

Multilevel queue scheduling is a method used in operating systems to manage processes by organizing them into multiple queues based on specific characteristics. This approach enhances the efficiency of process management and scheduling.

Key Features

Multiple Queues: Unlike single queue scheduling, multilevel queue scheduling utilizes multiple queues to manage processes.
Permanent Assignment: Processes are permanently assigned to a specific queue based on certain properties, such as:
- Memory size
- Process priority
- Process type
Queue Partitioning: The ready queue is divided into different queues, where processes with the same priority level are grouped together.
Scheduling Algorithms: Each queue can implement its own scheduling algorithm, allowing for tailored management of processes.
Fixed Priority Preemptive Scheduling: Scheduling among the queues is typically managed using fixed priority preemptive scheduling, where higher priority queues are serviced before lower priority ones.

Process Execution Order

Queues are listed in order of priority.
Processes in lower priority queues cannot execute until all higher priority queues are empty.

Advantages

Diverse Scheduling Algorithms: Different scheduling algorithms can be applied to different processes, optimizing performance.
Reduced Response Time: This method can lead to improved system performance and reduced response times for processes.
Low Scheduling Overhead: The overhead associated with scheduling is minimized.

Disadvantages

Preemption Issues: A running process in a low priority queue can be preempted if a process in a high priority queue arrives.
Starvation Risk: Processes in lower priority queues may experience starvation if they are not promoted to higher priority queues.
Inflexibility: The system can be inflexible, making it difficult to adapt to varying process requirements.
Complexity: Implementing and managing multilevel queues can be complex.

Multilevel Feedback Queue

The multilevel feedback queue scheduling algorithm enhances the multilevel queue approach by allowing processes to move between queues based on their CPU usage characteristics.

Key Features

Dynamic Movement: Processes can move between queues, allowing for more flexible scheduling based on CPU burst characteristics.
CPU Time Management: If a process consumes excessive CPU time, it is moved to a lower-priority queue.
Higher Priority for I/O Bound Processes: I/O bound and interactive processes are kept in higher priority queues.
Aging Mechanism: To prevent starvation, processes that wait too long in a lower priority queue may be promoted to a higher priority queue.

Example of Multilevel Feedback Queue

Three queues are defined:
- Q0: Round Robin (RR) with a time quantum of 8 ms.
- Q1: Round Robin (RR) with a time quantum of 16 ms.
- Q2: First-Come, First-Served (FCFS).
Execution Order: Q0 is executed first, followed by Q1 and then Q2.
Job Processing:
- A new job enters Q0 and is served in a FCFS manner, receiving 8 ms of CPU time.
- If the job does not complete in 8 ms, it is moved to Q1, where it receives an additional 16 ms.
- If it still does not complete, it is preempted and moved to Q2.

Parameters of Multilevel Feedback Queue

The number of queues.
The scheduling algorithm for each queue.
Criteria for upgrading a process to a higher priority queue.
Criteria for demoting a process to a lower priority queue.
Determination of which queue a process enters when it requires service.

The implementation of a multilevel feedback queue scheduler is complex due to the need to manage all the above parameters effectively.

Comparison Questions

Difference Between Scheduling Types:
Multilevel feedback scheduling is a variant of multilevel queue scheduling in which processes can move between queues based on their behavior. In contrast, multilevel queue scheduling assigns a fixed priority to each process, which remains unchanged.
Queue Movement:
In multilevel queue scheduling, a process cannot move between queues; its priority is fixed, and it remains in the same queue throughout its execution.

Queue Scheduling and Thread Scheduling Concepts

Queue Scheduling

Complexity of Queue Scheduler: The queue scheduler is complex due to the need to manage multiple parameters effectively.

Multilevel Queue Scheduling vs. Multilevel Feedback Scheduling

Multilevel Queue Scheduling:
- Processes are assigned to fixed priority queues.
- Each queue is executed in turn, maintaining the order of execution.
- Processes cannot move between queues; their priority is fixed throughout execution.
Multilevel Feedback Scheduling:
- A variant of multilevel queue scheduling allowing processes to move between queues based on their behavior.
- This flexibility helps optimize CPU usage and responsiveness.

Handling I/O-bound Processes

I/O-bound processes are assigned to the highest priority queue with the shortest time quantum.
This assignment ensures quick responsiveness for such processes, improving overall system performance.

Prevention of Starvation

Multilevel queue scheduling can prevent starvation by executing each queue in turn.
This method ensures that no single process monopolizes CPU time, allowing fair access for all processes.

Thread Scheduling

User-level vs. Kernel-level Threads:
- User-level threads are managed by a thread library, while kernel-level threads are managed by the operating system.
- When threads are supported, they are scheduled instead of processes.
Many-to-One Model:
- User threads are scheduled on a single Lightweight Process (LWP).
- The thread library controls the scheduling, allowing all user threads to take turns on the LWP.
Many-to-Many Model:
- Multiple user threads are mapped to multiple LWPs.
- The thread library can run several user threads in parallel on different LWPs, improving concurrency.

Contention Scope

Process Contention Scope (PCS):
- Describes how user-level threads compete for execution on a limited set of LWPs within a single process.
- Known as process local scheduling, it uses many-to-many or many-to-one models.
- The thread library has full control over thread scheduling.
- Example: Solaris implementation of threads.
System Contention Scope (SCS):
- Kernel threads compete for CPU time across the entire system.
- Known as system global scheduling, it uses a one-to-one model.
- The kernel manages scheduling, allowing for independent scheduling of each thread on available CPUs.
- Example: Linux and Mac OS implementations of threads.

Pthread Scheduling

The Pthread API allows the specification of either PCS or SCS during thread creation.
PTHREAD_SCOPE_PROCESS: Schedules threads using PCS scheduling.
PTHREAD_SCOPE_SYSTEM: Schedules threads using SCS scheduling.
Limitations exist in certain operating systems; for example, Linux and Mac OS X only allow PTHREAD_SCOPE_SYSTEM.

Pthread Scheduling API Example

The following code snippet demonstrates how to set up and use the Pthread scheduling API:

#include <pthread.h>
#include <stdio.h>
#define NUM_THREADS 5
int main(int argc, char *argv[]) {
    int i, scope;
    pthread_t tid[NUM_THREADS];
    pthread_attr_t attr;
    /* get the default attributes */
    pthread_attr_init(&attr);
    /* first inquire on the current scope */
    if (pthread_attr_getscope(&attr, &scope) != 0)
        fprintf(stderr, "Unable to get scheduling scope \n");
    else {
        if (scope == PTHREAD_SCOPE_PROCESS)
            printf("PTHREAD_SCOPE_PROCESS");
        else if (scope == PTHREAD_SCOPE_SYSTEM)
            printf("PTHREAD_SCOPE_SYSTEM");
        else
            fprintf(stderr, "Illegal scope value. \n");
    }
}

Setting Scheduling Algorithm

The following code snippet shows how to set the scheduling algorithm to PCS or SCS:

/* set the scheduling algorithm to PCS or SCS */
pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);
/* create the threads */
for (i = 0; i < NUM_THREADS; i++)
    pthread_create(&tid[i], &attr, runner, NULL);
/* now join on each thread */
for (i = 0; i < NUM_THREADS; i++)
    pthread_join(tid[i], NULL);

Chapter 6: CPU Scheduling

Overview

This chapter focuses on CPU scheduling, which is essential for multiprogrammed operating systems. It covers various CPU scheduling algorithms, evaluation criteria for selecting these algorithms, and examples from different operating systems.

Objectives

Introduce CPU scheduling as a fundamental aspect of multiprogrammed operating systems.
Describe various CPU scheduling algorithms.
Discuss evaluation criteria for selecting a CPU scheduling algorithm suitable for specific systems.
Examine the scheduling algorithms used in several operating systems.

Basic Concepts

A single processor can only run one process at a time.
The goal of multiprogramming is to ensure that some process is running at all times to maximize CPU utilization.
When a process must wait, the operating system (OS) reallocates the CPU to another process.
Multiple processes are kept in memory simultaneously, allowing for efficient CPU scheduling.
Scheduling is a fundamental function of the OS, as almost all computer resources require scheduling before use.
The CPU is one of the primary resources that need scheduling.

Process Execution

Process execution consists of alternating between two states: CPU execution and I/O wait.
Each process begins with a CPU burst followed by an I/O burst, repeating this cycle.
CPU Burst: The period during which a process is actively executing on the CPU.
I/O Burst: The period during which a process is waiting for I/O operations to complete.

CPU and I/O Bursts

The duration of CPU bursts can vary significantly between processes and across different computer systems.
Complex tasks requiring more calculations or logic operations tend to need longer CPU cycles.
Processor architecture affects burst duration, as different processors have varying speeds and core counts.
Studies show that CPU burst distribution typically follows an exponential pattern, characterized by:
- A large number of short CPU bursts.
- A small number of long CPU bursts.

Histogram of CPU Burst Times

The distribution of CPU burst times is generally exponential, indicating that most processes involve numerous short bursts, with only a few requiring long bursts. This pattern reflects typical process behavior and the distribution of CPU time needed.

Understanding Burst Time

Every process requires a specific amount of time for execution, which includes both CPU and I/O time.
CPU Time: The time taken by the CPU to execute the process.
I/O Time: The time taken by the process to perform I/O operations.
For analysis, I/O time is often ignored, focusing primarily on CPU time.
Burst Time: The total time taken by a process for execution on the CPU.

Arrival Time

Arrival Time: The moment a process enters the ready state and is prepared for execution.

Exponential Averaging and CPU Scheduling Algorithms

Exponential Averaging and CPU Scheduling Algorithms