processes
jbwyatt.com
jbwyatt.com
. process introduction
Process (Task) ============= An instance of an executable program An active entity Need HW resources: processor, registers, RAM Need DS to 'manage' (PCB) Processor (CPU) ============== Performs calculations and executes programs In single-user systems: Processor is busy only when executing a job In a multiprogramming environment: Processor allocated to each job in a fair and efficient manner Need scheduling policy and scheduling algorithm Process Context stored in PCB ============================= In Queues Created when job started, updated as it progresses PID Process status (READY, RUNNING, WAITING) Process state (registers, main memory info, resources (files, devices), priority) Accounting (CPU time, total time, memory use, I/O operations, etc.)
Context Switch ============== Save job’s processing information in its PCB when interrupted Choose new job according to scheduling policy Restore new process info from PCB to HW Invokes SCHEDULER
Interrupt ========= is a signal cpu interrupted to handle interrupt bathroom polling vs interrupt what is an interrupt vector? interrupt handler -> i/o interrupt call context_switch() -> time slice interrupt call context_switch() Types of Interrupts: Page interrupts Time quantum expiration interrupts I/O interrupts when READ or WRITE Hardware needs servicing (keyboard) Illegal arithmetic operations (dividing by 0). Illegal job instructions (attempts to access protected memory)
. process scheduler
Multi-CPU vs Multi-Core ======================= Scheduling requires communication between processors which thread runs where memory access coordination (ram contents NOT in another core's cache) protocol for communication between processors (MESI, MOESI) Communication lag time 1. beteween processors 2. between processor and memory/cache system Core reduces communication overhead - All on same chip...
Process Scheduler ================= Which job will get the CPU Queues and de-queues jobs When interrupt occurs that invokes scheduler, performs a context switch ^^^^^^^^^^^^^^ context_switch() { SCHEDULER picks next process to execute saves current process info -> pcb puts pcb into appropriate q (ready, wait) gets pcb of next job from q (ready, wait) copies pcb -> registers return } Scheduling policy ================= decides how long each job should get cpu algorithm I/O-bound jobs: many brief CPU cycles, long I/O cycles EX: printing a series of documents CPU-bound jobs: long CPU cycles, shorter I/O cycles EX: finding the first 300 prime numbers Total all CPU cycles approximates a Poisson distribution curve
Distribution of CPU cycle times
Job status: states as it moves through the system HOLD READY WAITING RUNNING FINISHED
A typical job (or process) changes status as it moves through the system from HOLD to FINISHED
THREE Main states ================= 1. Ready 2. Running 3. Waiting Which transitions can be made? what causes each?? Queues must be managed by process scheduling policies and algorithms --------------------------------------------------------------------OS has 3 problems scheduling in multi-programming environment: ========== 1. Finite resources 2. Some resources can’t be shared (printers) 3. Some resources require operator intervention (mount disk, tape drives, printer paper, jams) A good process scheduling policy ================================ Maximize throughput: run as many jobs as possible Minimize response time: interactive requests Minimize turnaround time: complete as many jobs quick as possible Maximize CPU efficiency: keep CPU busy 100% Ensure fairness Process Scheduler uses interrupts Time quantum expires Suspends all activity on the current process Reschedules it into the READY queue Why Interrupts? Process claims CPU for very long time before I/O Huge READY queue & empty I/O queues Imbalance in the system Multiple-Processor Scheduling ============================= Asymmetric multiprocessing – one core acts as a master and schedules all cores in the CPU Symmetric multiprocessing - each core is self scheduling. If the ready queue is shared we must synch properly Afinity - each core has its own cache. Moving a thread from one core to another is therefore costly in cache misses Soft affinity: OS tries to schedule on same core, but threads can migrate between cores Hard affinity: thread may explicitly declare no migration
. process scheduling policies
Types of Scheduling Policies ============================ 1. Preemptive scheduling : Interrupts processing of a job 2. Nonpreemptive scheduling: Functions w/o external interrupts Process Scheduling Algorithms: First Come, First Served (FCFS) Shortest Job Next (SJN) Shortest Remaining Time (SRT) Round Robin
FCFS ==== Nonpreemptive Schedule as they arrive Simple: uses a FIFO queue Good for batch systems; unacceptable for interactive systems Turnaround time is unpredictableJobs arrival sequence: A, B, C JobA CPU cycle: 15 ms, JobB CPU cycle: 2 ms, JobC CPU cycle: 1 ms Average turnaround time: 16.67
Jobs arrival sequence: C, B, A Average turnaround time: 7.3
SJN (Shortest Job Next) === Nonpreemptive Handles jobs based on length of CPU cycle time Easiest to implement in batch environments Doesn’t work in interactive systems Optimal only when all jobs are available at same time and the CPU estimates are available and accurate Four batch jobs A, B, C, D, in the READY queue Job: A B C D CPU cycle: 5 2 6 4Average turnaround time: 9 s
SJR (preemptive) === Preemptive version of SJN Processor allocated to job closest to completion Current job preempted if newer job in Q has shorter time to complete Not in interactive system Requires knowledge of the CPU time required to finish jobs SRT involves more overhead than SJN OS monitors CPU time for all jobs in Q and performs context switchingArrival time: 0 1 2 3 Job: A B C D CPU cycle: 6 3 1 4 Turnaround: 14 4 1 6 Average Turnaround: 6.25s Same jobs using SJN (nonpreemptive)
Arrival time: 0 1 2 3 Job: A B C D CPU cycle: 6 3 1 4 Turnaround: 6 9 5 11 Average Turnaround: 7.75s
Round Robin =========== Preemptive Interactive Size of time quantum crucial (100 ms to 1-2 s) Ensures CPU equally shared among active processes If CPU cycle > time quantum Job is preempted and put at the end of the READY Q If CPU cycle < time quantum If job finished resources released If interrupted by I/O request Info saved in PCB Linked at end of appropriate I/O queue When I/O complete, job returns to READY Q
Quantum ======= Efficiency depends on quantum in relation to the average CPU cycle If quantum too large - larger than most CPU cycles Algorithm reduces to FCFS If the quantum too small Context switching slows down job execution Overhead increases General rules of thumb for time quantum: ======================================= 1. Long enough for 80% of CPU cycles to complete 2. 100 times longer than context switch time
Timeslice (quantum) = 4 ======================== Arrival time: 0 1 2 3 Job: A B C D CPU cycle: 8 4 9 5 Turnaround: 20 7 24 22 Average Turnaround: 18.25 s (20+7+24+22)/4
Context switches for job A (cycle=8) with three different time quantums. ==================================== In (a) the job finishes before the time quantum expires. In (b) and (c), the time quantum expires first, interrupting the job.
