Single-CPU Processor Management

• These notes cover processor management, focusing on single-CPU systems
• Multi-CPU and multi-core systems are not explored

Core Concepts

• Program (Job):
  • Inactive unit, such as a file stored on a disk
  • Represents a unit of work submitted by a user
• Process (Task):
  • A program in execution
  • Can be described as an Active entity
  • Requires resources like a processor and registers
• Thread:
  • A portion of a process that runs independently
• Processor (CPU):
  • Performs calculations and executes programs

Key Terms

• Multiprogramming: Involves multiple processes competing to run on a single CPU, requiring fair and efficient CPU allocation
• Multitasking: Describes one user running multiple programs, which requires sharing of resources
• Interrupt:
  • A call for help that activates a higher-priority program
• Context Switch:
  • Saving job processing information when interrupted

Scheduling Sub-Managers

• Processor Manager: Composed of two sub-managers:
  • Job Scheduler (higher-level) handles job scheduling responsibilities and job initiation
  • Process Scheduler (lower-level) handles process scheduling responsibilities, determines execution steps

Job Scheduling

• Functions:
  • Selects incoming jobs from a queue
  • Places jobs in a process queue
  • Decides on job initiation criteria
• Goal:
  • Sequence jobs and balance I/O interaction and computation
  • Maximize system resource utilization and keep system components busy

Process Scheduling

• Functions:
  • Determines which job gets CPU resources (and for how long)
  • Decides how to handle interrupt processing
  • Determines queues for process movement during execution
  • Recognizes process conclusion or termination

Process Types

• I/O-Bound Job:
  • Performs many I/O operations, characterized by brief CPU cycles followed by long I/O cycles; for example of printing documents
• CPU-Bound Job:
  • Performs lots of computation, characterized by long CPU cycles and shorter I/O cycles; for example math calculation

Process States

• Key states include Ready, Running, Waiting, New, and Terminated
• CPU/Processor Scheduling involves determining which process in the ready state should be moved to the running state
• Multiple processes can be in the ready state, but only one can be in the running state at a time

Process Control Block (PCB)

• The operating system manages data for each active process
• Data is stored in RAM in a data structure called a process control block (PCB)
• The OS maintains one PCB for each process
• Attributes Include:
  • A unique Process ID
  • Processor status (HOLD, READY, RUNNING, WAITING)
  • Processor state information (Process Status Word, register contents, memory info, priority, resources)
  • Accounting information for billing and performance measurement
• Job PCB is created and updated as the job executes
• Queues use PCBs to track jobs and that PCBs are linked to form queues

Context Switching

• The CPU has one set of registers containing values for the currently executing process
• When a process moves to the running state:
  • Register values of the current running process are stored into its PCB
  • Register values of the new running state are loaded into the CPU, which is a context switch

Process Scheduling Policies

• Multiprogramming: More jobs than resources at any given time results in OS pre-scheduling to resolve system limitations:
  • A finite number of resources (disk drives, printers, memory, etc)
  • The inability to share some resources (printers)
  • The requirement for operator intervention to reassign some resources (tape drives)

Key Definitions

• CPU Utilization: Keeping the CPU as busy as possible
• Turnaround Time: the amount of time when process arrives in the ready state for the first time until it exits the running state for the last time
• Throughput: The number of processes that complete per unit of time
• Waiting Time: The amount of time a process waits in the ready queue
• Response Time: The time from request submission to the first response (in time-sharing environments)

Scheduling Policy Criteria

• Maximize throughput, minimize response time and turnaround time
• Minimize waiting time, maximize CPU efficiency, ensure fairness for all jobs
• Decisions are made by the system designer or administrator
• A corrective measure for jobs claiming the CPU for too long without an I/O request is an interrupt

Scheduling Policies

• Non-Preemptive Scheduling: The current process voluntarily gives up the CPU; the process keeps the CPU until exiting or switching to a waiting state
• Preemptive Scheduling: The OS favors another process and preempts the current one, transferring CPU to another job

Scheduling Algorithms

• Six types:
  • First-Come, First-Served (FCFS)
  • Shortest Job Next (SJN)
  • Priority scheduling
  • Shortest Remaining Time (SRT)
  • Round robin
  • Multiple-level queues
  • Earliest deadline first (EDF)
• Interactive systems emphasize use and response time so they use preemptive policies

First-Come, First-Served (FCFS)

• Non-preemptive, handles jobs based on arrival time using a FIFO queue
• Good for batch systems, unacceptable in interactive systems because turnaround time varies
• Average turnaround time is seldom minimized

Shortest Job Next (SJN

• Non-preemptive, and job is handled based on CPU cycle time
• Easy implementation in a batch environment but known CPU time is required in advance
• Does not work in interactive system but the algorithm is optimal when all jobs are available at the same time and CPU estimates are available and accurate

Priority Scheduling

• Non-preemptive, gives preferential treatment to important jobs; programs with highest priority are processed first
• There are no interrupts until CPU cycles complete or a natural wait occurs
• READY queues may contain two or more jobs with equal priority but FCFS policy within the priority is used
• Systems admins use different methods of assigning priorities such as memory requirements, number and type of peripheral devices, CPU time

Shortest Remaining Time (SRT)

• Preemptive version of SJN
• Processor allocates to job closest to completion, preempting if a newer job has shorter completion time
• It gives to short jobs in batch environments
• It is not applicable in interactive system that requires advance CPU time knowledge and involves more overhead than SJN

Round Robin

• Preemptive
• Distributes time equitably using a time slice (quantum)
• Quantum size is crucial for performance and varies from 100 ms to 1-2 seconds and shares CPU equally among all active process
• Extensively used in interactive system

Round Robin Efficiency

• Relies on time quantum size
• Quantum too large: It suffers response time and reduces FCFS scheme algorithm
• Quantum is too small: Throughput suffers and context switching occurs
• Job execution slows down, causing overhead to dramatically increase, information saved in PCB
• Best quantum time size depends on the system
  • Interactive System: Response time is key factor
  • Batch: Turnaround time is key factor
• General rule of thumb: long enough for 80% of CPU cycles to complete and at least 100 times longer than context switch time requirement

Multiple-Level Queues

• Algorithms categorize processes and can be used with other policies by memory size, process type, etc
• It divides a ready queue into several queues where processes are assigned
• Each queue uses a particular scheduling algorithm
  • example, interactive processes use Round Robin; background processes use FCFS and SRT
• Scheduling policy: Has a predetermined scheme

Multiple-Level Queues Characteristics

• Isn't a separate scheduling algorithm because it uses others
• Jobs are grouped according to common characteristics such as being Priority-based with CPU-bound jobs and I/O bound jobs or a hybrid environment
• Queues use a predetermined schedule according to policy

Earliest Deadline First (EDF)

• A dynamic priority, preemptive algorithm
• Addresses critical processing requirements of real-time systems which also adjusts job priorities
• Primary goal: Process jobs in order to run to completion before reaching deadlines
• Job priority is inversely proportional to its absolute deadline
• Jobs with same deadlines requires the OS using another scheme
• Priority can change as more important jobs enter the system

Problems with EDF

• Missed deadlines: This can happen if the required time for all jobs is greater than the time allocated until the total deadline as well as the OS being unable to predict throughput
• Result in high overhead from evaluation of deadlines

Interrupts

• Page Interrupt (memory manager): Accommodate job requests
• Time Quantum Expiration Interrupt
• I/O Interrupt: Result from READ or WRITE command issuance
• Internal Interrupt: Synchronous, result from arithmetic operation or job instruction
• Illegal Arithmetic Operation Interrupt: Dividing by zero; bad floating-point operation
• Illegal Job Instruction Interrupt: Protected storage/non-existent access attempt, undefined operation code
• An interrupt handler is a control program that handles the interruption event sequence and describes the type of interrupt and saves its state
• The interrupt is processed and the processor resumes normal operation