【正文】 2022 Operating System Concepts – 9th Edition Rate Monotonic Scheduling ? This algorithm schedules periodic tasks using static priority policy with preemption. ? A priority is assigned based on the inverse of its period ? Shorter periods = higher priority and longer periods = lower priority ? Rate monotonic considered optimal, that is if a set of processes cannot be scheduled by this algorithm it cannot be scheduled by any other algorithm. ? For a process Pi if pi = period of Pi, ti= processing time of Pi, then CPU utilization of Pi = ti/ pi ? CPU utilization bounded and not always possible to fully to maximize CPU utilization. Silberschatz, Galvin and Gagne 169。2022 Operating System Concepts – 9th Edition FCFS Scheduling (Cont.) Suppose that the processes arrive in the order: P2 , P3 , P1 ? The Gantt chart for the schedule is: ? Waiting time for P1 = 6。2022 Operating System Concepts – 9th Edition CPU Scheduler Cont. ? When scheduling takes place under conditions 1 and 4 the scheduling scheme is called nonpreemptive. ? Process assigned to CPU, keeps the CPU till it terminates or changes its state to waiting. ? When scheduling takes place under conditions 2 and 3 the scheduling scheme is called preemptive. ? Processes can be removed from the CPU. Silberschatz, Galvin and Gagne 169。2022 Operating System Concepts – 9th Edition Example of RR with Time Quantum = 4 Process Burst Time P1 24 P2 3 P3 3 ? The Gantt chart is: ? Typically, higher average turnaround than SJF, but better response ? q should be large pared to context switch time ? q usually 10ms to 100ms, context switch 10 usec P P P1 1 10 1 8 3 02 61 44 7 1 0 2 2P 2 P 3 P 1 P 1 P 1 Silberschatz, Galvin and Gagne 169。2022 Operating System Concepts – 9th Edition Simulation and Implementation ? Simulations: ? Provide more accurate evaluation of scheduling algorithm ? Running Simulations involves programming a model of the system and maintaining a clock. ? Simulator modifies system state and logs the activities of the devices, processes and scheduler. ? Implementation: ? Most accurate way of evaluating a scheduling algorithm is to implement it and put it in the Operating system and test it in real time! Silberschatz, Galvin and Gagne 169。2022 Operating System Concepts – 9th Edition Example of Priority Scheduling ProcessAarri Burst Time(ms)T Priority P1 10 3 P2 1 1 P3 2 4 P4 1 5 P5 5 2 ? Priority scheduling Gantt Chart ? Average waiting time = (0 + 1 + 6 + 16 + 18 )/5 = ms (milliseconds) P2 P5 P1 P3 P4 Silberschatz, Galvin and Gagne 169。2022 Operating System Concepts – 9th Edition Basic Concepts ? OS schedules almost all resources available to the system. ? CPU being the primary resource, scheduling is central to OS design. ? Proce