SchedulingContentsProcess: An Object With StateProcess StructureProcess StatesMajor Process StatesSlide 7Process States Finite State DiagramState TransitionsProcess Control Block (PCB)Slide 11Slide 12Process/thread switching (1)Process/thread switching (2)Implementation of Processes on interrupt (2)CPU SchedulerCPU Scheduler ExampleQueuing Diagram for ProcessesSlide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Queueing TheoryDiscussionSlide 34ProblemRandom EventsQueuing TheorySlide 38Analysis of Queueing BehaviorUseful Facts From Queuing TheorySlide 41Analysis of Single Server QueueExampleSlide 44Slide 45Slide 46Slide 47Slide 48Simulation DiagramSummary01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved1SchedulingCS 241 Lecture 13T:Ch 2.4 pp125-132Roy Campbell01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved2ContentsScheduling Queueing ModelSimulation models of scheduling01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved3Process: An Object With StateAn operating system manipulates a process as if it is an object The operations the OS performs on the process changes the state of the process01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved4Process StructureProgram code;Program counter value;Content of processor's registers;Process stack - contains temporary data such as subroutine parameters, return addresses, temporary variables;Data section - contains global variables;01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved5Process StatesThe process has states during its lifetime: running, waiting, ready, suspended, ended State of a process is defined by the current process activity Operations on the process may depend on its state---01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved6Major Process StatesActive Running: On CPU - instructions in the program code are being executed; Waiting or halted - process is waiting for some event to occur; Start (new): before execution - process is being created;01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved7Major Process StatesReady: waiting for CPU - process is waiting to be assigned to the CPU;Blocked (waiting): waiting for an eventSuspended: waiting to be swapped inDead (terminated): finished or aborted01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved8Process States Finite State Diagram01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved9State Transitions01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved10Process Control Block (PCB)Each process is represented in OS by a PCB which is a task control block. PCB consists of the following information:01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved11Process Control Block (PCB)Process state - includes process states such as new, ready, running, waiting, halted;CPU registers - stack pointersCPU scheduling information - includes process priority and pointer;01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved12Process Control Block (PCB)Memory management information - includes base/limit information;Accounting information - includes time limits, process number; I/O status information - includes list of I/O devices allocated to the process;01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved13Process/thread switching (1)Skeleton of what lowest level of OS does when switching from one process to another1. Store program counter, registers etc on stack2. Queue pointer to PCB on “ready” queue3. Dequeue pointer for a PCB from “ready queue”4. Load page table to make virtual memory accessible5. Load program counter, registers etc from stack01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved14Process/thread switching (2)Skeleton of what lowest level of OS does when process blocks because of synchronizationExample: Semaphore or Mutex1. Store program counter, registers etc on stack2. Queue pointer to PCB on “synchronization” queue3. Update “synchronization data structure”4. Dequeue pointer for a PCB from “ready queue”5. Load page table to make virtual memory accessible6. Load program counter, registers etc from stack01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved15Implementation of Processes on interrupt (2)Skeleton of what lowest level of OS does when an interrupt occursInterrupt hardware stores program counter, registers etc on stackHardware loads new program counter from interrupt vectorAssembly language procedure stores registers on stackAssembly language procedure sets up new stackC interrupt service runs (services interrupt)Scheduler called to decide what process to run – returns PCBLoad page table to make virtual memory accessibleLoad program counter, registers etc from stack01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved16CPU SchedulerCPU scheduler selects one of the processes from the ready queue and allocates CPU to one of them;Ready queue:= FIFO queue, tree queue, or unordered linked list, or priority queue;Elements in the ready queue are PCBs (Process Control Block) of processes01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved17CPU Scheduler ExampleProcess 1 burst computes for 14 time units Process 2 burst computes for 8 time units Process 3 burst computes for 8 time units01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved18Queuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPU01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved19Queuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPU01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved20Queuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPU01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved21Queuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPU01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved22Queuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPU01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved23Queuing Diagram for Processes StartStartReady QueueReady QueueEvent QueueEvent QueueEventEventExitExitTime SliceTime SliceCPUCPU01/14/19 CS241 © 2005 Roy
View Full Document