Operating System CPU Scheduing - 3 Monday, August 11, 2008

Roadmap Basic Concepts Scheduling Criteria Scheduling Algorithms Real-Time Scheduling Multiple-Processor Scheduling Operating System Examples Algorithm Evaluation 多道程序设计的目标是在任何时候都有一个进程在运行，以使CPU使用率最大化。 调度是操作系统的基本功能。几乎所有计算机资源在使用前都要被调度。当然，CPU是最为重要的计算机资源之一。因此，CPU调度对操作系统设计来说非常重要。 8/11/2008 6:14 PM bettynj@gmail.com

Algorithm Evaluation Deterministic modeling Queuing models Simulations Implementation 8/11/2008 6:14 PM bettynj@gmail.com

Deterministic Modeling Analytic evaluation: one major class of evaluation methods It uses the given algorithm and the system workload to produce a formula or number that evaluates the performance of the algorithm for that workload. Deterministic modeling: one type of analytic evaluation. 一种主要类型的评估方法称为分析评估法，该方法使用给定算法和系统负荷，产生一个公式或数字，以评估针对该负荷算法的性能。 一种类型的分析评估是确定性建模法。该方法采用特定预先确定的负荷，定义在给定负荷下每个算法的性能。 8/11/2008 6:14 PM bettynj@gmail.com

Example Process Burst time Average waiting time: P1 10 P2 29 P3 3 P4 7 FCFS: (0+10+39+42+49)/5=28ms Non-preemptive SJF: (10+32+0+3+20)/5=13ms RR(10): (0+32+20+23+40)/5=23ms 在此情况下，SJF调度策略所产生的平均等待时间不到FCFS调度中的一半；RR算法给出了一个中间值。 8/11/2008 6:14 PM bettynj@gmail.com

Features of Deterministic Modeling Advantages Deterministic modeling is simple and fast. It gives exact numbers, allowing the algorithms to be compared. Disadvantages It requires exact numbers for input, and its answers apply to only those cases. Usage: describing scheduling algorithms and providing examples. 确定性建模不但简单而且也快。他给出了确切数字，以允许算法被比较。然而，它要求输入为精确数字，而且其答案只适用于这些情况。 确定性建模主要用途在于描述调度算法和提供例子。然而，其通常过分特殊且要求过多精确知识，股用处有限。 Limitation: too specific and requires too much exact knowledge. 8/11/2008 6:14 PM bettynj@gmail.com

Queuing models Queuing-network analysis The computer system is described as a network of servers. Each server has a queue of waiting process. The CPU is a server with its ready queue, as is the I/O system with its device queues. Knowing arrival rates and service rates, we can compute utilization, average queue length, average wait time, and so on. 在许多系统上运行的进程每天都在变化，因此，没有静态的进程集合和时间用于确定性建模。然而，CPU和I/O区间的分布是可以确定的。这些分布可以被测量，近似或简单估计，其结果是一个数学公式以描述特定CPU区间的分布概率。 计算机系统可描述为服务器网络。每个服务器都有一个等待队列。CPU是具有就绪队列的服务器，而I/O系统具有设备队列。知道了到达率和服务率，就可以计算使用率、平均队列长度、平均等待时间等。这种研究领域称为排队网络分析。 8/11/2008 6:14 PM bettynj@gmail.com

Example of Queuing models Let n be the average queue length, let w be the average waiting time in the queue, and let λ be the average arrival rate for new processes in the queue. Expect During the time w that a process waits, w×λ new processes will arrive in the queue. If the system is in a steady state, the number of processes leaving the queue must be equal to the number of processes that arrive. n= w×λ -- Little’s formula 设n为平均队列长度（不包括正在服务的进程），设w为队列的平均等待时间，设λ为新进程到达队列的平均到达率（如每秒三个进程）。那么，希望在进程等待的w时间内，由w×λ 新进程到达队列。如果系统处于稳定状态，那么离开队列的进程的数量必定等于到达进程的数量。因此，由n=w×λ。 8/11/2008 6:14 PM bettynj@gmail.com

Queuing models Useful for comparing scheduling algorithms. Real distributions are difficult to work with. Some assumptions required. 排队分析可用于比较调度算法，但它也有限制。为了能计算一个答案，排队模型通常只是显式系统的近似。因此，计算结果的精确性值得怀疑。 8/11/2008 6:14 PM bettynj@gmail.com

Simulation Simulations involve programming a model of the computer system. Software data structures represent the major components of the system. The simulator has a variable representing a clock; as this variable’s value is increased, the simulator modifies the system to reflect the activities of the device, the processes, and the scheduler. As the simulation executes, statistics that indicate algorithm performance are gathered and printed. 为了获得对调度算法更为精确的评估，可使用模拟。 模拟涉及对计算机系统模型进行程序设计。通过软件数据结构表示系统主要组成成分。 随着模拟程序的执行，用以表示算法性能的统计数字可以被收集并打印出来。 8/11/2008 6:14 PM bettynj@gmail.com

Simulation To get a more accurate evaluation of scheduling algorithms, we can use simulation. Useful but expensive. 最为普通的产生模拟数据的方法是使用随机数生成器，它被编程以根据概率分布生成进程。CPU区间时间、到达时间、离开时间等。分布可以数学地（统一的、指数的、泊松）或经验地加以定义。 分布驱动模拟可能不够精确：频率分布只表示每个时间发生了多少次；它并不能表示事件的发生顺序。可以采用跟踪磁带来纠正这个问题。 8/11/2008 6:14 PM bettynj@gmail.com

Implementation Even a simulation is of limited accuracy, the only completely accurate way to evaluate a scheduling algorithm is implementation: To code the algorithm, To put it in the OS, To see how it works. Major difficulty is the cost of this approach: A perfect scheduling algorithm is not easy to found. In practice, we don’t really need the perfect scheduling algorithm. 8/11/2008 6:14 PM bettynj@gmail.com

Keystone How to evaluate different algorithms 8/11/2008 6:14 PM bettynj@gmail.com

Homework Suppose that the following processes arrive for execution at the times indicated. Each process will run the listed amount of time. In answering the questions, use nonpreempive scheduling and base all decisions on the information you have at the time the decision must be made. process arrival time burst time P1 0.0 8 P2 0.4 4 P3 1.0 1 a. What is the average turnaround time for these processes with the FCFS scheduling algorithm b. What is the average turnaround time for these processes with the SJF scheduling algorithm c. Compute what the average turnaround time will be if the CPU is left idle for the first 1 unit and them SJF scheduling is used. 8/11/2008 6:14 PM bettynj@gmail.com

Homework What advantage is there in having different time-quantum sizes on different levels of a multilevel queueing system Explain the differences in the degree to which the following scheduling algorithms discriminate in favor of short processes: FCFS RR Multilevel feedback queues 8/11/2008 6:14 PM bettynj@gmail.com

Operating System Algorithm Evaluation Monday, August 11, 2008