Process Scheduling Notes
Chapter 5: Process Scheduling
5.1 Overview of Process Scheduling
Process Definition: A program in execution.
Unit of Work: Each process represents the program and execution context loaded into memory.
5.2 Transition from Program to Process
A program becomes a process when its executable file is loaded into memory.
Example:
gcc -o test test.c // Compiling C program
#include <stdio.h>
int main() {
printf("Hello CIS370!\n");
return 0;
}
5.3 Process Control Block (PCB)
PCB: Data structure that stores information about a process, including:
Process State: Possible states include new, ready, running, waiting, and terminated.
Program Counter: Pointer to the next instruction to be executed.
CPU Registers: Stores process-specific register content.
CPU Scheduling Info: Contains priority and pointers for scheduling queues.
Memory Management Info: Memory allocated to the process (base/limit registers, page tables).
Accounting Info: Time used and other accounting metrics.
I/O Status Info: List of I/O devices allocated to the process.
5.4 Process States
New: Process is being created.
Ready: Process is ready to run and waiting for CPU.
Running: Process is currently being executed.
Waiting: Process is waiting for some event to occur (e.g., I/O completion).
Terminated: Process has finished execution.
5.5 Objectives of CPU Scheduling
Maximize CPU Utilization: Keep CPU as busy as possible.
Maximize Throughput: Increase the number of processes completed in a time unit.
Maximize Response Time: Decrease the time between request submission and first response.
5.6 Context Switching
Context Switch: Saving the state of a CPU process and loading the next process's state. This allows multiple processes to share a single CPU.
Context Switching Overhead: Increased complexity leads to longer context switch times. Hardware support for multiple registers can speed this up.
5.7 Process Scheduling Types
Short-Term Scheduling: Selects which process to execute next from the ready queue; invoked frequently, must be fast (milliseconds).
Long-Term Scheduling: Decides which processes can be brought into the ready queue; invoked less frequently (seconds, minutes).
Medium-Term Scheduling: Swaps processes in and out of memory to control multiprogramming degree.
5.8 I/O-Bound vs. CPU-Bound Processes
I/O-Bound Process: Spends more time on I/O operations than computations.
CPU-Bound Process: Spends more time on calculations.
5.9 Scheduling Algorithms
First-Come, First-Served (FCFS): Simple, but can lead to long wait times especially for short tasks.
Gantt Chart Example: Process order matters; average wait time can vary significantly.
Shortest Job First (SJF): Allocates CPU to the process with the shortest expected CPU burst.
Can be preemptive (shortest remaining time first) or nonpreemptive.
Priority Scheduling: Allocates CPU according to priority levels assigned to each process, can also be preemptive or nonpreemptive.
Round Robin (RR): Time quantum allocated to each process; ensures response time but can lead to high turnaround times if misconfigured.
Multilevel Queue Scheduling: Divides ready processes into different queues, each with different scheduling algorithms.
Multilevel Feedback Queue: Processes can move between queues based on their CPU burst length and waiting time.
5.10 CPU Scheduling Evaluation
CPU Utilization: Keep CPU busy.
Throughput: Processes completed per time unit.
Turnaround Time: Total time from submission to completion of a process.
Waiting Time: Time a process spends in the ready queue.
Response Time: Time from submission to the first response.
5.11 Real-world Implementations
Linux CFS: Completely Fair Scheduler aimed at better interactive process performance.
Windows Scheduler: It uses prioritization and time slices for threads; includes user-mode scheduling.
5.12 Conclusion
The choice of scheduling algorithm impacts system performance heavily. Evaluation methods vary, and it's crucial to choose the right type based on system requirements and user expectations.