Operating System CPU Scheduling

CPU Utilization

• Maximum CPU utilization is achieved through multiprogramming.

CPU-I/O Burst Cycle

• Process execution involves a cycle of CPU execution and I/O wait.
• CPU burst is followed by an I/O burst.
• The distribution of CPU bursts is a key concern in scheduling.

CPU Burst Times Histogram

• A histogram illustrates the frequency of CPU burst durations.
• The distribution typically shows a higher frequency of shorter bursts.

CPU Scheduler

• The short-term scheduler selects a process from the ready queue and allocates the CPU to it.
• Scheduling methods include non-preemptive techniques (e.g., FCFS, SJF, priority) and preemptive scheduling (e.g., round robin)
• CPU scheduling decisions occur when a process:
  • Switches from running to waiting (blocked) state, often due to I/O or resource requests.
  • Switches from running to ready state (e.g., timer interrupt).
  • Switches from waiting to ready state (e.g., completion of I/O).
  • Terminates

Dispatcher

• The dispatcher gives control of the CPU to a selected process.
• This involves context switching, switching to user mode, and jumping to the correct location in the user program.
• Dispatch latency is the time it takes the dispatcher to pause one process and start another.

Scheduling Criteria

• CPU utilization: Keeping the CPU busy executing applications.
• Throughput: Number of processes completed per unit time.
• Turnaround time: Total time taken from process arrival to completion.
• Waiting time: Time spent in the ready queue.
• Response time: Time from submission of a request to the first response.

First-Come, First-Served (FCFS) Scheduling

• Processes are executed in the order of arrival.
• A Gantt chart illustrates this schedule.
• Average waiting time is calculated for a set of processes.
• Convoy effect can occur when short processes are delayed behind long processes.

Shortest-Job-First (SJF) Scheduling

• Processes are scheduled based on the length of their next CPU burst.
• It's an optimal algorithm, minimizing average waiting time for a given set of processes.
• The challenge is accurately predicting the next CPU burst length.
• Shortest-remaining-time-first (preemptive version) is also considered.

Determining Length of Next CPU Burst

• Burst length estimation is based on prior burst lengths for the same process.
• Methods like exponential averaging use previous CPU bursts to predict future ones.
• The formula for exponential averaging involves weight (α), varying from 0 to 1 and the current and prior burst length values.

Examples of SJF Scheduling

• SJF scheduling chart and associated waiting times calculations are provided.

Example of Shortest-Remaining-Time-First

• Example Gantt chart and calculation of average waiting time are included.

Priority Scheduling

• Processes are assigned priority numbers, and the CPU is given to the process with the highest priority.
• Preemptive and non-preemptive versions are possible.
• SJF is a specific priority scheduling type where priority is inversely related to the predicted next CPU burst.
• Starvation (low-priority processes might never execute) is a potential issue.
• Aging (increasing priority over time) is a solution.

Example of Priority Scheduling

• Gantt chart and average waiting time calculations are given.

Round Robin (RR) Scheduling

• Each process receives a small time quantum (fixed duration).
• After the quantum, the process is preempted, and the scheduler moves to the next process in the ready queue.
• The time quantum should be larger than the context switch time to balance performance and overhead.
• Performance is affected by the time quantum.

Example of Round Robin

• Example with a Gantt chart illustrating the round-robin scheduling for different processes.

Time Quantum and Context Switch Time

• Comparison between time quantum and context switch times for better understanding of the relationship.

Turnaround Time Varies with the Time Quantum

• Graph showing how the average turnaround time varies based on the time quantum, providing insight into the tradeoffs.

Proportional Share Scheduling

• Each process is allocated a share of the processing time. The scheduler ensures each application receives a proportional share of the processor time.

Multilevel Queue

• Ready queue is subdivided into separate queues (e.g., foreground and background) organized into different categories of processes.
• Each queue can use varying scheduling algorithms to optimize performance for the specific type of process.

Thread Scheduling

• Distinction between user-level and kernel-level threads exists.
• Kernel-managed threads are included in the system-contention scope.
• User-level threads operate within the current process scope for scheduling.

Pthread Scheduling

• API for specifying the scheduling scope (either process-contention scope or system-contention scope).
• Methods like PTHREAD_SCOPE_PROCESS and PTHREAD_SCOPE_SYSTEM are available for thread creation.

Real-Time CPU Scheduling

• Soft and hard real-time systems are differentiated.
• Soft real-time systems give preference to real-time processes, but not guaranteed execution times.
• Hard real-time systems require tasks completed by their deadlines.
• Interrupt latency and dispatch latency affect real-time performance.
• Potential conflicts may occur when scheduling real-time processes.

Priority-based Scheduling

• Real-time scheduling needs preemptive priority scheduling to manage deadlines effectively.
• Hard real-time systems involve periodic processes.
• Rate Monotonic Scheduling is a priority-based algorithm that assigns priorities to processes based on their period. Shorter periods mean higher priority.

Rate Monotonic Scheduling

• Priority assignment method for real-time tasks.
• Process with shorter periods are assigned higher scheduling precedence.
• Example scenarios for different tasks are discussed, demonstrating the concept using deadlines for better comprehension.