《双语教学-调度2》由会员分享，可在线阅读，更多相关《双语教学-调度2（38页珍藏版）》请在金锄头文库上搜索。
1、scheduling2006-0812.5 Scheduling When a computer is multi-programmed , it frequently has multiple processes competing for the CPU at the same time: The part of operating system that makes the choice is called the scheduler and the algorithm it uses is called the scheduling algorithm 2.5.1 introduce
2、to scheduling In addition to picking the right process to run the scheduler also has worry about making efficient use of the CPU because process switching is expensive Process behavior: I/O-bound process: short CPU burst CPU-bound process: long CPU burst12.5 调度 当一台计算机使用多道程序设计的时候 , 经常要有多个进程同时竞争 CPU资源
3、: 那么,我们把操作系统中作出决定(决定哪个进程得到CPU)的那一部分 叫做调度程序(scheduler) 调度程序在进行调度的时候所使用的算法叫调度算法 (scheduling algorithm) 2.5.1 调度简介 除了选择正确的进程运行之外 调度程序还要关心CPU的高效使用问题,因为进程切换的代价是很高 的 进程的行为: (I/O-bound) I/O密集型进程: CPU突发很短 (CPU-bound) CPU密集型进程: CPU突发很长2 when to make scheduling decision: First, when a new process is created,
4、a decision needs to be made whether to run the parent process or the child process Second, a scheduling decision must be made when a process exits Third, when a process blocks on I/O , on a semaphore , or for some other reason, another process has to be selected to run. Fourth, when an I/O interrupt
5、 occurs, a scheduling decision may be made.2 什么时候作出调度选择: 第一,当有一个新进程被创建的时候,必须作出调度 选择以决定是运行父进程还是子进程 第二,当一个进程终止的时候,必须作出调度选择 第三,当一个进行被阻塞的IO上一个信号量上,或 是由于其它原因被阻塞时,必须选出另一个进行来 运行 第四,当发生IO中断时,必须作出调度选择3 Two kinds or scheduling ways: A non-preemptive scheduling algorithm picks a process to run and then just le
6、ts it run until it blocks or until it voluntarily releases the CPU A preemptive scheduling algorithm picks a process and lets it run for a maximum of some fixed time Categories of scheduling algorithms: Batch Interactive Real time3 两种调度的方式: 非抢占式(non-preemptive)的调度算法:选出一个 进程运行并且让它一直运行,直到发生阻塞或是这 个进程自动
7、放弃CPU 抢占式(preemptive)的调度算法:选出一个进程并 让它运行一段固定的最大的时间(后便强行让其它 进程进行) 调度算法种类: 批处理 交互式 实时4Goals of scheduling: All systems: Fairness-giving each process a fair share of the CPU Policy enforcement-seeing that stated policy is carried out Balance-keeping all parts of the system busy Batch systems: Throughput
8、-maximize jobs per hour Turnaround time-minimize time between sub-mission and termination CPU utilization-keep the CPU busy all the time4调度的目标: 所有系统中: 公平性(Fairness)-给每一个进程以公平的CPU使用机会 策略的强制执行(Policy enforcement)-执行既定的策略 平衡性(Balance)-保持系统各个部分处于工作状态 批处理系统中: 吐吞量(Throughput)-每小时可完成的最大作业数 周转时间(Turnaround
9、time)-作业提交到终止的最小时间 CPU利用率(CPU utilization)-保持CPU在不停的工作5 Interactive systems: Response time-respond to requests quickly Proportionally-meet users expectations Real-time systems: Meeting deadlines-avoid losing data Predictability-avoid quality degradation in multimedia systems5 交互式系统中: 响应时间(Response t
10、ime)-快速地对请求进行响 应 公正性-满足各个用户的期望 实时系统: 满足底线(Meeting deadlines)-(在规定时间前必须 完成某些操作)以防止数据丢失 可预测性(Predictability)-在多媒体系统中避免质 量下降6 2.5.2 Scheduling in batch systems First-come first-served With this algorithm, processes are assigned the CPU in the order they request it Shortest job first When several equall
11、y important jobs are sitting in the input queue waiting to be started, the scheduler picks the shortest job first Here we find four jobs A,B,C, and D, with run times of 8,4,4,and 4 minutes. By running them in that order, the turnaround for A is 8 minutes, for B is 12 minutes , for C is 16 minutes an
12、d for D is 20 minutes, for an average of 14 (8+12+16+20)/4) minutes 6 2.5.2 Scheduling in batch systems First-come first-served With this algorithm, jobs are assigned the CPU in the order they request it Here we find four jobs A,B,C, and D, with run times of 8,4,4,and 4 minutes. By running them in t
13、hat order, the turnaround for A is 8 minutes, for B is 12 minutes , for C is 16 minutes and for D is 20 minutes, for an average of 14 (8+12+16+20)/4) minutes Shortest job first When several equally important jobs are sitting in the input queue waiting to be started, the scheduler picks the shortest
14、job first6 2.5.2 批处理系统中的调度 先来先服务(First-come first-served) 当使用这种算法时,按作业请求CPU的先后顺序得以CPU 资源 假如有四个作业A,B,C,D,各自的运行时间是8,4,4,4分钟。 若是按照A，B，C，D这样的顺序来运行它们，A的周转 时间是8分钟，B的是12分钟，C的是16分钟，D的是20分 钟。平均周转时间是14分钟。 最短作业优先 当几个相同的重要的作业在输入队列中等候调度的时候， 调度程序选择其中最短的作业运行。7 Now let us consider running these four jobs using shor
15、test job first, the turnaround are now 4,8,12,20 minutes , and for an average of 11 minutes （4+8+12+20）/4=11(minutes)A(8 )B(4 )C(4 )D(4 )A(8 )B(4 )C(4 )D(4 )7 现在我们考虑使用最短作业优先（shortest job first）算法来运行这些作业,四个作业的周转时 间现在分别是4,8,12,20分钟 , 并且平均周转周 期是：11 minutes （4+8+12+20）/4=11(minutes)A(8 )B(4 )C(4 )D(4 )A(8 )B(4 )C(4 )D(4 )8Shortest remaining time next The scheduler always choose the proc
