MM Process ManagementAnnouncementsCPU SchedulingProcess StateProcess Control BlockResource QueuesCPU SchedulerEvaluation CriteriaScheduling AlgorithmsFCFSShortest-Job-FirstPriorityRound RobinTake Home ExerciseMultimedia ProcessesSchedulingAdmissibility TestRate Monotonic SchedulingModel AssumptionsTerminologyExample 1Example 2Feasibility TestProblem for Two TasksCase 1Case 2Minimum Occurs at BoundaryGeneral CaseExampleSlide 30Deadline Driven Scheduling (EDF)Compare Rate Monotonic vs. EDFMM Process ManagementKarrie KarahaliosSpring 2007(based off slides created by Brian Bailey)AnnouncementsCPU Scheduling•Maintain many programs in memory•Determine how to best schedule them•Requires information about the processes and an understanding of the system goals•Switch among processes rapidly so each user perceives direct ownership of systemProcess State•New – being created•Terminated – finishing execution•Running – executing on the CPU•Waiting – blocking on an event•Ready – waiting for the CPUProcess Control Block•Represents a process in the OS–process state–program counter–CPU registers–scheduling information–virtual memory information (e.g., page tables)–I/O status informationResource QueuesSem QueueheadtailReady QueueheadtailPCB6StateRegisters…Disk QueueheadtailPCB5StateRegisters…PCB4StateRegisters…PCB3StateRegisters…PCB2StateRegisters…PCB1StateRegisters…CPU Scheduler•When CPU becomes idle, select next process from the ready queue•CPU may become idle when:–allotted time slice expires–interrupt occurs (timer, I/O, user input)–application makes an I/O request–application terminatesEvaluation Criteria•Throughput: processes completed per unit time•Turnaround: from submission to termination•Wait: time waiting in the ready queue•Response: from user request to system response•Utilization: how busy the CPU is over time•Want predictable system behaviorScheduling Algorithms•FCFS•Shortest Job First•Priority scheduling•Round-robin•Multi-level queue•Rate monotonic•Earliest deadline firstFCFS•Process requests in order of arrival–non-preemptive algorithm–fairness (human vs. system perspective)–convoy effectShortest-Job-First•Schedule process with smallest burst–difficult to know next CPU burst–use weighted average of past performance•Gives min wait time for processes–if preemptive, may lead to starvationnnnt)1(1Priority •Associate priority with each process•Schedule process with highest priority–equal priority resolved via FCFS–if priority is a function of time, gives SJF•Combat CPU starvation using aging–increase priority of long-waiting processesRound Robin•Schedule process after a time quantum–circulate around queue, give each process single time quantum to execute–results in lots of context switches•Selection of time quantum–short quantum results in longer waits–infinite quantum results in FCFS–should be large relative to context switch timeTake Home Exercise•Assume workload shown on the right•Compare FCFS, SJF, and RR (quantum=10)–compare along each evaluation criteriaProcess Arrival CPU BurstP1 1 10P2 2 29P3 3 3P4 4 7P5 5 12Multimedia Processes•Exhibit continuous, periodic behavior•Execute along with other processes•Have perceptual constraints (QoS)Scheduling•Determine sharing of a resource such that all admitted tasks meet their deadlines•Balance need to meet deadlines with maximizing throughput and utilizationAdmissibility Test•If test succeeds, the task can be added, and all tasks will still meet deadlines–called a feasible schedule•Process utilization (U)<1 if deadlines consideredniiiTCU1/Rate Monotonic Scheduling•Static, fixed priority-based, periodic tasks–Ci is execution time of task i–Ti is request period of task i•Determines if a set of periodic tasks can be scheduled or not (feasible schedule)–no other fixed priority scheme can schedule a set of tasks which can’t be scheduled by RMLiu, C.L. and J.W. Layland. Journal of the ACM, 20(1): 46-61, 1973Model Assumptions•All requests to process tasks are periodic•Each task must finish before next request•Each request is independent•Execution time for each task is constant•Non-periodic tasks are special•Tasks are preemptive based on priority–static: priorities assigned once at initialization–dynamic: priorities change during executionTerminology•Deadline–time of the next request for same task•Feasible–no deadlines are missed•Response time–time between request and completion of a task•Critical instant–when a request for a task will have the largest response time–occurs when a task is requested simultaneously with requests for all higher priority tasks•Critical time zone–time between a critical instant and the end of the response to the corresponding request of the lowest priority taskExample 1T1 = 2C1 = 1 C2 = 1T2 = 5T1 is higher priorityUtilization (U) =Example 2T1 = 2C1 = 1 C2 = 2T2 = 5T1 is higher priorityUtilization (U) =Feasibility Test•If requests for all tasks at their critical instants can be fulfilled, then feasible•Determine least upper bound of U–maximum utilization such that all deadlines are still satisfied, in the general case•Assigning highest priority to task with the smallest period yields best utilizationProblem for Two Tasks•Tasks (C1, T1) and (C2, T2), with T1 < T2•Within request period of T2, there can be at most ceil(T2 / T1) requests from T1•Adjust C2 to fully utilize CPUCase 1•Requests for task1 completed within T2–no overlap with T2•In this case, largest value of C2 can beC2 = T2 – C1*ceil(T2/T1)•U = 1 + C1[ (1/T1) – (1/T2) *ceil(T2 / T1)]Case 2•Execution of ceil(T2/T1)th request from task1 overlaps second request from task2–e.g. (C1=1,T1=1.5); (C2=1, T2=5)•In this case, largest value of C2 can beC2 = T1*fl(T2/T1) – C1*fl(T2/T1)•U = (T1/T2)*fl(T2/T1) + C1[ (1/T1) – (1/T2) *fl(T2 / T1)]Minimum Occurs at Boundary•Minimum of U occurs at the boundary between these two cases•Set equations equal and solve for C1C1 = T2 – T1*fl(T2/T1)•U = 2(21/2 – 1) =~ 0.83–highest utilization such that all deadlines metGeneral Case•For two tasks–U < 2 (2½ - 1), ~= 0.83•For three tasks–U < 3 (21/3 - 1) ~= 0.78•For n tasks–U < n (21/n – 1) -> ln 2 ~= 0.69•If configuration of tasks pass the test, no deadlines will be missed–must limit
View Full Document
Unlocking...