当前位置：文档之家 › 第4章 调度与死锁1

第4章 调度与死锁1

  • 格式：ppt
  • 大小：486.50 KB
  • 文档页数：82

下载文档原格式

  / 82

合集下载

湘潭大学 操作系统 课程复习

湘潭大学 操作系统 课程复习
• • • • • 程序的顺序执行及其特征（理解） 程序的并发执行及其特征（理解） 进程的概念及其特征（掌握） 进程状态（掌握） 进程控制块（理解）
– 3.2 进程控制（理解）
• 进程创建和终止 • 进程阻塞和唤醒 • 进程挂起和激活
6
第3章
• 第3章 进程描述和控制
– 3.3 线程
• 线程简介（理解） • 多线程（掌握） • 线程实现与线程模型（理解）
• 第6章 输入输出系统
• 磁盘管理（不考） • 容错技术：廉价磁盘冗余阵列（了解）
16
第7章
• 第7章 文件管理
– 7.1 概述（理解）
• 文件、文件系统的定义
– 7.2 文件结构
• 逻辑结构（理解） • 物理结构：顺序结构、链接结构、索引结构（掌握 ）；直接文件、哈希文件（理解）
– 7.3 文件目录
10
第5章
• 第5章 存储器管理
– 5.4 页式存储管理
• 页、块、页表、地址结构、分页地址变换、快表（ 掌握） • 两级页表、多级页表（理解）
– 5.5 段式与段页式存储管理
• 段、段表、地址结构、分段地址变换（掌握） • 分页和分段的区别（掌握） • 段页式存储管理（理解）
– 5.6 内存扩充技术（了解）
• 安全状态 • 银行家算法数据结构、流程 • 安全性算法
– 4.6 死锁检测和恢复（了解）
9
第5章
• 第5章 内存管理
– 5.1 概述（理解）
• 存储层次结构 • 存储管理的目的和任务
– 5.2 地址重定位（理解）
• 重定位的基本概念 • 补充：程序的装入、程序的链接
– 5.3 分区存储管理
• 单一连续、固定分区、可变分区分配（理解） • 分区分配算法（掌握） • 补充：哈希算法、伙伴系统（理解）

操作系统第4章ppt课件

操作系统第4章ppt课件

THANKS
感谢观看
P/V操作
对信号量进行加减操作，实现进程同 步与互斥。
经典同步问题及其解决方法
1 2
生产者-消费者问题
通过两个信号量分别控制生产者和消费者进程， 确保生产者和消费者之间的同步与互斥。
哲学家进餐问题
通过引入资源分级法或信号量集机制，避免死锁 的发生，确保哲学家进餐过程中的同步与互斥。
3
读者-写者问题
。
多线程模型比较分析
01
多对一模型Leabharlann 将多个用户级线程映射到一个内核级线程上。该模型下，线程管理在用
户空间完成，线程的调度采用非抢占式调度，由线程库负责。
02
一对一模型
将每个用户级线程都映射到一个内核级线程上。该模型下，线程的创建
、撤销和同步等都在内核中实现，线程的调度由内核完成。
03
多对多模型
将多个用户级线程映射到少数但不止一个内核级线程上。该模型结合了
前两种模型的优点，允许多个用户级线程映射到不同的内核级线程上运
行。
线程同步与互斥机制
互斥锁
采用互斥对象机制，只有拥有互斥对象的线程才有访问公共 资源的权限。因为互斥对象只有一个，所以能保证公共资源 不会同时被多个线程同时访问。
信号量
信号量是一个整型变量，可以对其执行down和up操作，也 就是常见的P和V操作。信号量初始化为一个正数，表示并发 执行的线程数量。
死锁避免：银行家算法是一种典型的 死锁避免算法。该算法通过检查请求 资源的进程对资源的最大需求量是否 超过系统可用资源量来判断是否分配 资源给该进程。如果分配后系统剩余 资源量仍然能够满足其他进程的最大 需求量，则分配资源，否则不分配资 源。
死锁检测：通过定期运行死锁检测算 法来检测系统中是否存在死锁。常见 的死锁检测算法有资源分配图算法和 银行家算法等。如果检测到死锁发生 ，则需要采取相应措施来解除死锁， 例如通过撤销部分进程或抢占部分资 源来打破死锁状态。

处理机调度与死锁习题

处理机调度与死锁习题

处理机调度和死锁习题第一部分：处理机的调度一、单项选择题1．时间片轮转调度算法是为了（）。

A．多个终端能够得到系统及时响应B．使系统变得高效C．优先级较高的进程得到及时响应D．需要CPU时间最少的进程最先做2．在单处理器的多进程系统中，进程什么时候占用处理器以及决定占用时间的长短是由（）决定的。

A．进程相应的代码长度B．进程总共需要运行的时间C．进程特点和进程调度策略D．进程完成什么功能3．（）有利于CPU繁忙型的作业，而不利于}/0繁忙型的作业。

A．时间片轮转调度算法B．先来先服务调度算法C．短作业（进程）优先算法D．优先权调度算法4．下面有关选择进程调度算法的准则中不正确的是（）。

A．尽快响应交互式用户的请求B．尽量提高处理器利用率C．尽可能提高系统吞吐量D．适当增长进程就绪队列的等待时间5．设有4个作业同时到达，每个作业的执行时间均为2h，它们在一台处理器上按单道运行，则平均周转时间为（）。

A．1h B．5h C．D．8h6．若每个作业只能建立一个进程，为了照顾短作业用户，应采用（）；为了照顾紧急作业用户，应采用（）；为了能实现人机交互，应采用（）；而能使短作业．长作和交互作业用户都满意，应采用（）。

A．FCFS调度算法B．短作业优先调度算法C．时间片轮转调度算法D．多级反馈队列调度算法E．剥夺式优先级调度算法7．（）优先级是在创建进程时确定的，确定之后在整个运行期间不再改变。

A．先来先服务B．动态C．短作业D．静态8．现在有三个同时到达的作业J1，J2和J3，它们的执行时间分别是T1，T2，T3，且T1 <T2 <T3。

系统按单道方式运行且采用短作业优先调度算法，则平均周转时间是（）。

A．T1+T2 +T3 B．（3 x Tl+2 x T2 + T3）/3 C．（T1+T2+T3）/3 D．（TI+2 x T2+3 x T3 ）/3 9．设有三个作业，其运行时间分别是2h，5h，3h，假定它们同时到达，并在同一台处理器上以单道方式运行，则平均周转时间最小的执行顺序是（）。

操作系统原理-第四章 处理机调度(有答案)

操作系统原理-第四章 处理机调度(有答案)

第四章处理机调度4.3 习题4.3.1 选择最合适的答案1．某系统采用了银行家算法，则下列叙述正确的是（）。

A.系统处于不安全状态时一定会发生死锁B.系统处于不安全状态时可能会发生死锁C.系统处于安全状态时可能会发生死锁D.系统处于安全状态时一定会发生死锁2．银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need，下列选项正确的是（）。

A.Max[i,j]=Allocation[i,j]+Need[i,j]B.Need[i,j]= Allocation[i,j]+ Max[i,j]C.Max[i,j]= Available[i,j]+Need[i,j]D.Need[i,j]= Available[i,j]+ Max[i,j]3．下列进程调度算法中，（）可能会出现进程长期得不到调度的情况。

A.非抢占式静态优先权法B.抢占式静态优先权法C.时间片轮转调度算法D.非抢占式动态优先权法4．在下列选项中，属于预防死锁的方法是（）。

A.剥夺资源法B.资源分配图简化法C.资源随意分配D.银行家算法5．在下列选项中，属于检测死锁的方法是（）。

A.银行家算法B.消进程法C.资源静态分配法D.资源分配图简化法6．在下列选项中，属于解除死锁的方法是（）。

A．剥夺资源法 B.资源分配图简化法C．银行家算法 D.资源静态分配法7．为了照顾紧迫型作业，应采用（）。

A.先来服务调度算法B.短作业优先调度算法C.时间片轮转调度算法D.优先权调度算法8．在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和（）相同。

A.先来先服务调度算法B.短作业优先调度算法C.时间片轮转调度算法D.长作业优先调度算法9．作业从后备作业到被调度程序选中的时间称为（）。

A.周转时间B.响应时间C.等待调度时间D.运行时间10．资源静态分配法可以预防死锁的发生，它们使死锁四个条件中的（）不成立。

习题解答——第4章调度与死锁

习题解答——第4章调度与死锁

第4章调度与死锁思考与练习题2．考虑下面的进程集合：（1）（2）分别对以上两个进程集合，计算使用先来先服务（FCFS）、时间片轮转法（时间片q=1）、短进程优先（SPN）、最短剩余时间优先（SRT，时间片q=1）、响应比高者优先（HRRN）及多级反馈队列（MFQ,第1个队列的时间片为1，第i(i<1)个队列的时间片q=2（i-1））算法进行CPU调度，请给出各进程的完成时间、周转时间、带权周转时间，及所有进程的平均周转时间和平均带权周转时间。

解答：（1）平均带权周转时间W=(1+1.4+3.5+1.2+1.6)/5=8.7/5=1.74平均带权周转时间W= (2+2.5+2+1.8+1.6)/5=9.4/5=1.98平均带权周转时间W=(1+1.8+1+1.2+1.6)/5=6.6/5=1.32平均带权周转时间W=(1+1.8+1+1.2+1.6)/5=6.6/5=1.32平均带权周转时间W=(1+1.4+3.5+1.2+1.6)/5=8.7/5=1.74多级反馈队列：第1个队列的时间片为1，第i(i<1)个队列的时间片q=2（i-1））即：平均带权周转时间W= (1.33+2.5+1.8+1.8+1.6)/5=9.03/5=1.806（2）平均带权周转时间W=(1+1+9+1.89)/4=3.22平均带权周转时间W=(1+1.89+1+1.89)/4=1.45平均带权周转时间W=3.22平均带权周转时间W=1.25平均带权周转时间W=3.22平均带权周转时间W=1.4453．考虑系统中出现的情况：（1）计算每个进程还可能需要的资源，并填入表的“仍然需要”栏目中。

（2）系统当前是否处于安全状态？为什么？（3）系统当前是否死锁？为什么？（4）如果进程P3又有新的请求（0，2，0，0），系统是否可以安全地接受此请求？解答：存在安全序列<P1,P4,P5,P2,P3>（3）不会发生死锁，因为存在安全序列，进程按此顺序执行可保证不死锁。

(完整版)计算机操作系统(第四版)课后习题答案第三章

(完整版)计算机操作系统(第四版)课后习题答案第三章

第三章处理机调度与死锁1，高级调度与低级调度的主要任务是什么？为什么要引入中级调度？【解】（1）高级调度主要任务是用于决定把外存上处于后备队列中的那些作业调入内存，并为它们创建进程，分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。

（2）低级调度主要任务是决定就绪队列中的哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。

（3）引入中级调度的主要目的是为了提高内存的利用率和系统吞吐量。

为此，应使那些暂时不能运行的进程不再占用宝贵的内存空间，而将它们调至外存上去等待，称此时的进程状态为就绪驻外存状态或挂起状态。

当这些进程重又具备运行条件，且内存又稍有空闲时，由中级调度决定，将外存上的那些重又具备运行条件的就绪进程重新调入内存，并修改其状态为就绪状态，挂在就绪队列上，等待进程调度。

3、何谓作业、作业步和作业流？【解】作业包含通常的程序和数据，还配有作业说明书。

系统根据该说明书对程序的运行进行控制。

批处理系统中是以作业为基本单位从外存调入内存。

作业步是指每个作业运行期间都必须经过若干个相对独立相互关联的顺序加工的步骤。

作业流是指若干个作业进入系统后依次存放在外存上形成的输入作业流；在操作系统的控制下，逐个作业进程处理，于是形成了处理作业流。

4、在什么情冴下需要使用作业控制块JCB？其中包含了哪些内容？【解】每当作业进入系统时，系统便为每个作业建立一个作业控制块JCB，根据作业类型将它插入到相应的后备队列中。

JCB 包含的内容通常有：1) 作业标识2)用户名称3)用户账户4)作业类型（CPU 繁忙型、I/O芳名型、批量型、终端型）5)作业状态6)调度信息（优先级、作业已运行）7)资源要求8)进入系统时间9) 开始处理时间10) 作业完成时间11) 作业退出时间12) 资源使用情况等5．在作业调度中应如何确定接纳多少个作业和接纳哪些作业？【解】作业调度每次接纳进入内存的作业数，取决于多道程序度。

计算机操作系统名词解释

第一章引论1操作系统：操作系统是管理和控制计算机系统内各种硬件和软件资源，有效地组织多道程序运行的系统软件（或程序集合），是用户与计算机之间的接口。

2管态：当执行操作系统程序时，处理机所处的状态3目态：当执行普通用户程序时，处理机所处的状态。

4多道程序设计：在这种设计技术下，内存中能同时存放多道程序，在管理程序的控制下交替的执行。

这些作业共享CPU和系统中的其他资源。

5并发：是指两个或多个活动在同一给定的时间间隔中进行。

它是宏观上的概念。

6并行：是指两个或多个活动在同一时刻同时执行的情况。

7吞吐量：在一段给定的时间内，计算机所能完成的总工作量。

8分时：就是对时间的共享。

在分时系统中，分时主要是指若干并发程序对CPU时间的共享。

9实时：表示“及时”或“既时”。

10系统调用：是用户在程序中能以“函数调用”形式调用的、由操作系统提供的子功能的集合。

每一个子功能称作一条系统调用命令。

它是操作系统对外的接口，是用户级程序取得操作系统服务的唯一途径。

11特权指令：指指令系统中这样一些指令，如启动设备指令、设置时钟指令、中断屏蔽指令和清内存指令，这些指令只能由操作系统使用。

12命令解释程序：其主要功能是接收用户输入的命令，然后予以解释并且执行。

13脱机I/O：是指输入/输出工作不受主机直接控制，而由卫星机专门负责完成I/O，主机专门完成快速计算任务，从而二者可以并行操作。

14联机I/O：是指作业的输入、调入内存及结果输出都在CPU直接控制下进行。

15资源共享：是指计算机系统中的资源被多个进程所功用。

例如，多个进程同时占用内存，从而对内存共享；它们并发执行时对CPU进行共享；各个进程在执行过程中提出对文件的读写请求，从而对磁盘进行共享等等。

第二章进程和线程1顺序性：是指顺序程序所规定的每个动作都在上个动作结束后才开始的特性。

2封闭性：是指只有程序本身的动作才能改变程序的运行环境。

3可再现性：是指程序的执行结果与程序运行的速度无关。

操作系统第4章(调度与死锁习题与解答)

第4章调度与死锁习题与解答4.2 例题解析例4.2.1 当前运行的进程（），将引发系统进行进程调度。

A.执行了一条转移指令B.要求增加主存空间，经系统调用银行家算法进行测算认为是安全的C.执行了一条I/O指令D.执行程序期间发生了I/O完成中断解本题考核进程调度的时机，相关的概念有：(1)进程执行转移指令表示CPU将转到一个新程序段去，并不是转到一个新进程，因而不会重新分配CPU。

(2)当前进程提出主存请求时，若系统认为分配是安全的，则可以立即使进程的请求得到满足，不会因而造成进程阻塞。

因此不会分配CPU。

(3)当前进程执行了I/O指令，提出了输入输出请求。

由于I/O是低速的，因此不能让CPU等待I/O完成。

因此需要阻塞当前进程，重新分配CPU。

(4)当前进程运行程序期间发生了I/O完成中断，说明有一个处于阻塞队列上的进程，正等待此I/O事件的出现。

因此可在中断处理程序中查出等待的进程，将它唤醒。

然后再返回到当前进程来执行。

只要恢复当前进程的现场信息就可以了，不会重新分配CPU。

正确答案应为C。

例4.2.2分时系统中的当前运行进程连续获得了两个时间片，原因可能是（）。

A．该进程的优先级最高B．就绪队列为空C．该进程最早进入就绪队列D．该进程是一个短进程解(1)在分时系统中，诸多进程以轮流方式分享CPU，一般不考虑进程的优先级。

(2)当前进程运行完一个时间片后回到就绪队列，如果此刻就绪队列为空队列，那么下一个时间片仍然由该进程使用CPU。

(3)在分时系统中，诸多进程轮流地使用CPU，并不考虑进程进入就绪队列的时间，也不登记进程进入就绪队列的时间。

(4)分时系统中诸多进程轮流使用CPU不考虑进程的长短，也不登记进程预估将运行多长时间。

正确答案应为B。

例4.2.3有三个作业A（到达时间8:50，执行时间1.5小时）、B（到达时间9:00，执行时间0.4小时）、C（到达时间9:30，执行时间1小时）。

当作业全部到达后，单道批处理系统按照响应比高者优先算法进行调度，则作业被选中的次序是（）。

第四章进程调度与死锁作业

第四章进程调度与死锁一.选择题（50题）1.预防死锁不可以去掉以下__A__条件。

A．互斥 B.请求与保持 C.不可剥夺 D.环路2.资源分配图是否可以完全简化是判断死锁的_C__。

A．充分条件 B.必要条件 C.充分必要条件 D.什么也不是3.设有4个作业同时到达，每个作业的执行时间是2min，它们在一台处理机上按单道方式运行，则平均周转时间为_B__。

A．1min B.5min C.2.5min D.8min4.若系统中有8台绘图仪，有多个进程均需要使用两台，规定每个进程一次仅允许申请一台，则至多允许_C__各进程参与竞争，而不会发生死锁。

A.5 B .6 C .7 D .85.响应比高者优先作业调度算法除了考虑进程在CPU上的运行时间，还考虑以下__D_因素。

A.输入时间B.完成时间C.周转时间D.等待时间6.产生系统死锁的原因可能是_B__。

A.一个进程进入死循环B.多个进程竞争资源出现了循环等待C.进程释放资源D.多个进程竞争共享型设备7.以下_B__方法可以解除死锁。

A.挂起进程B.剥夺资源C.提高进程优先级D.降低进程优先级8.采用有序分配资源的策略可以破坏产生死锁的__D_。

A.互斥条件B.请求与保持条件C.不可剥夺条件D.环路条件9.连个进程争夺同一个资源_B__。

A.一定死锁B.不一定死锁C.不死锁D.以上说法都不对10.以下解决死锁的方法中，属于预防策略的是_C__。

A.化简资源分配图B.银行家算法C.资源的有序分配D.死锁检测法11.下面__D_说法是对可剥夺系统的正确描述。

A.时间片轮转法是一种可剥夺式调度B.进程因等待某一事件而引起系统调度是一种可剥夺式调度C.实时系统采用可剥夺式调度D.优先级低的进程放弃CPU，让优先级高的进程运行12.以下关于调度的说法__A__正确。

A.进程通过调度得到CPUB.优先级是进程调度的主要依据，一旦确定就不能改变C.在单CPU的系统中，任何时刻都有一个进程处于运行状态D.进程申请CPU得不到时，其状态为阻塞13.既考虑进程的等待时间，又考虑进程的执行时间的调度算法是__A__。

操作系统复习考试第4章 调度与死锁 复习题

A. 银行家算法 C. 死锁检测法 答：B B. 资源有序分配法 D. 资源分配图化简法
11、某系统有3个并发进程，都需要同 类资源4个，试问该系统不会发生死锁的 最少资源数是多少？ 答：最少要10个。 由于各进程最大需求量之和要小于“进 程数+资源数” 3+x>12 X>9 所以最少要10个资源。
18（续）
A ll oc at i on 0 01 2 1 42 0 1 35 4 0 63 2 0 01 4 M ax 0 01 2 1 75 0 2 35 6 0 65 2 0 65 6 N ee d 0 00 0 0 33 0 1 00 2 0 02 0 0 64 2 A va il ab l e 1 10 0
16、
在一个实际的计算机系统中，资源可以更新和增减，进 程可以创建和撤销。如果系统用banker算法处理死锁，那么， 在什么情况下，下列改变可以安全地进行而不会引起死锁发 生? (1)增加Available(增添新资源)； (2)减少Available(资源永久性地从系统中删除)： (3)增大Max(对一进程而言，它可能希望更多的资源)； (4)减少Max(一进程决定不需要那么多资源)； (5)增加进程数； (6)减少进程数。
解：在本题中，当两个进程都执行完第一步后，即进 程P1和P2都申请到一个R1资源以后，系统进入不安 全状态。随着两个进程的向前推进，无论哪个进程 执行完第2步，系统都将进入死锁状态。可能到达的 死锁点是：进程P1占有一个单位的R1类资源及一个 单位的R2类资源，P2占有一个单位的R1类资源，此 时系统已经没有空闲资源，而两个进程都在保持已 占有的资源不释放的情况下继续申请资源，从而造 成死锁。或者是进程P2占有一个单位的R1类资源及 一个单位的R2类资源，P1占有一个单位的R1类资源， 此时系统已经没有空闲资源，而两个进程都在保持 已占有的资源不释放的情况下继续申请资源，从而 造成死锁。 假定进程P1成功执行了第二步，则死锁点的资源 分配图如下所示：
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

4.3.2 进程调度的方式
进程调度有两种方式：
抢占方式 非抢占方式
抢占方式
抢占方式：又称剥夺方式、可剥夺方式。 这种调度方式是指允许调度程序根据某 种原则去停止正在执行的进程，将已分 配给该进程的处理机重新分配给其他进 程。 抢占原则有：优先权、时间片。
非抢占方式
非抢占方式：又称非剥夺方式、不可剥夺 方式、不可抢占方式。这种调度方式是指 一旦将处理机分配给某进程后，便让该进 程一直执行，直到该进程完成或发生某事 件而进入阻塞状态，才把处理机分配给其 他进程。 非抢占方式中引起进程调度的因素有：进 程结束、因某种原因而阻塞、执行同步原 语等。 特点：简单，系统开销小，但无法处理紧 急任务。
短作业优先调度算法例
作业 1 2 3 4 提交 时间 10 10.2 10.4 10.5 运行 时间 2 1 0.5 0.3 开始 时间 10 12.8 12.3 12 完成 时间 12 13.8 12.8 12.3 周转 时间 2 3.6 2.4 1.8 带权周 转时间 1 3.6 4.8 6
平均周转时间 T=(2.0＋1.8＋2.4＋3.6)/4=2.45 平均带权周转时间 W=(1＋6＋4.8＋3.6)/4=3.85
先来先服务调度算法例
设有4道作业，它们的提交时间及执行时间如 下表，若按先来先服务调度算法进行调度，试 计算4个作业的平均周转时间和平均带权周转 时间。（时间单位：小时，以十进制计算）。
作业 1 2 3 4 提交时间 10 10.2 10.4 10.5 估计运行时间 2 1 0.5 0.3
作业周转时间及带权周转时间的计算
4.1.4 调度性能评价
由于操作系统的类型及目标不同，因此 选择的调度策略及算法也不同。
调度性能的评价准则
有很多评价准则，下面介绍几种主要的 评价准则：
CPU利用率高 系统吞吐量大。系统吞吐量表示单位时间内 CPU完成作业的数量。 周转时间短。 响应时间快。响应时间是指从用户提交请求 到系统首次产生响应所用的时间。
周转时间
作业的周转时间是指从作业提交到作业完 成之间的时间间隔。 平均周转时间是指多个作业的周转时间的 平均值。ｎ个作业的平均周转时间：
T =（T1＋T2＋ … ＋Tn）／n（Ti为作业ｉ的 周转时间）
带权周转时间
带权周转时间是指作业周转时间与作业实际 运行时间的比。 平均带权周转时间是指多个作业的带权周转 时间的平均值。ｎ个作业的平均带权周转时 间：
作业控制块
为管理作业，系统设置了作业控制块。系 统通过JCB感知作业的存在，JCB是作业 存在的唯一标志。 通常作业控制块中包括的主要内容有：
资源要求。 资源使用情况。 作业的控制方式、类型和优先级等。 作业名、作业状态。
资源要求
资源要求是指作业运行需要的资源情况， 包括：估计运行时间、最迟完成时间、 需要的内存容量、外设类型及数量等。
W ＝（W1＋W2＋ … ＋Wn）/n（Wi为作业ｉ的 带权周转时间）
4.2 作业调度
作业是用户在一次解题或一个事务处理 过程中要求计算机系统所做工作的集合， 包括用户程序、所需的数据及命令等。 计算机系统在完成一个作业的过程中所 做的一项相对独立的工作称为一个作业 步。 例如，在编制程序过程中通常要进行编 辑输入、编译、链接、运行几个作业步。
最短平均周转时间
当一批作业同时到达时，最短作业优先调度 算法才能获得最短平均周转时间。 设一组作业p1、p2、…、pn，其运行时间为t1、 t2、 …、tn，且假定t1<t2< …<tn，则短作业 优先调度算法的总周转时间为：
t1+（t1+t2）+ … +（t1+ … +tn） =n*t1+（n-1）t2+ … +tn
时间片轮转算法例
设有A、B、C、D、E五个进程，其到达 时间分别为0、1、2、3、4，要求运行时 间依次为3、6、4、5、2，采用时间片轮 转调度算法，当时间片大小为1和4时， 试计算其平均周转时间和平均带权周转 时间。
优先级的类型
优先级分为两种：
静态优先级 动态优先级
静态优先级
静态优先级是在创建进程时确定的，确定之 后在整个进程运行期间不再改变。 确定依据有：
进程类型：系统，用户 进程对资源的需求：执行ቤተ መጻሕፍቲ ባይዱ间，资源数量 用户要求：紧迫程度
特点：简单易行，系统开销小，但不精确。
动态优先级
动态优先级是指在创建进程时，根据进程的 特点及相关情况确定一个优先级，在进程运 行过程中再根据情况的变化调整优先级。 确定原则有：占用CPU时间，等待时间。 例：优先数=CPU使用时间/2+基本优先数 =CPU /2+
进程调度又称低级调度、微观调度或短 程调度，其主要任务是按照某种策略和 方法从就绪队列中选取一个进程，将处 理机分配给它。 进程调度的运行频率很高，一般几十毫 秒要运行一次。
4.1.3 中级调度
中级调度又称中程调度或交换调度，其功能 是将内存中暂时不用的信息移到外存，以腾 出空间给内存中的进程使用，或将需要的信 息从外存读入内存。 引入中程调度的目的是提高内存利用率和系 统吞吐量。 中级调度的运行频率介于两者之间。
4.4 调度算法
调度算法是指根据系统资源分配策略所 规定的资源分配算法。 本章的算法有些适合作业调度，有些适 合进程调度，有些适用于两者。
4.4.1 先来先服务调度算法
先来先服务算法既可用于作业调度，也可用 于进程调度。
在作业调度中：从后备作业队列中选择一个或多 个最先进入该队列的作业，将它们调入内存，为 它们分配资源，创建进程，然后放入就绪队列。 进程调度中：从就绪队列中选择一个最先进入该 队列的进程，为之分配处理机，使之投入运行。 该进程一直运行到完成或因等待某一事件而阻塞 时才释放处理机。
最短平均周转时间（续）
可以证明：若a1≤ a2≤ … ≤ an且 b1≤b2≤ … ≤bn，则 a1bn+a2bn-1 +…+anb1 ≤ a1bi1+a2bi2 +…+anbin ≤ a1b1+a2b2 + +anbn +…+a 其中i1、i2、 …、in 是1、2、 …、n的 一个排列。
4.4.3 优先级调度算法
作业 1 2 3 4 提交 时间 10 10.2 10.4 10.5 运行 时间 2 1 0.5 0.3 开始 时间 10 12 13 13.5 完成 时间 12 13 13.5 13.8 周转 时间 2 2.8 3.1 3.3 带权周 转时间 1 2.8 6.2 11
平均周转时间T=(2.0＋2.8＋3.1＋3.3)/4=2.8 平均带权周转时间W=(1＋2.8＋6.2＋11)/4=5.25
在作业调度中，从后备作业队列中选择 若干优先级高的作业调入内存。 在进程调度中，将处理机分配给就绪队 列中优先级最高的进程。 优先级表示进程的重要性及运行优先性， 通常用优先数来衡量。在某些系统中， 优先数越大优先级越高；而在另一些系 统中，优先数越大优先级越小。
按调度方式对优先级调度算法分类
非抢占式优先级调度算法：系统一旦将处理机分配 给就绪队列中优先级最高的进程后，该进程便一直 运行下去，直到完成或因发生某事件使该进程放弃 处理机时，系统才将处理机分配给另一个更高优先 级的进程。 抢占式优先级调度算法：将处理机分配给优先级最 高的进程，使之运行。在进程运行过程中，一旦出 现了另一个优先级更高的进程时，进程调度程序就 停止原运行进程，而将处理机分配给新出现的高优 先级进程。
CPU使用时间衰减函数: Decay(CPU使用时间)=CPU使用时间/2
4.4.4 时间片轮转调度算法
时间片轮转法：系统将所有就绪进程按到达 时间的先后次序排成一个队列，每次调度时 把CPU分配给队首进程，并令其执行一个时 间片。当时间片用完时，停止该进程的执行， 将它送至就绪队列末尾等待下一次执行，然 后再把处理机分配给就绪队列中的新队首进 程。如此不断循环，直至完成为止。
资源使用情况
资源使用情况包括作业进入系统的时间、 开始运行时间、已运行时间、内存地址、 外设台号等。
作业控制方式、类型和优先级
作业的控制方式有联机作业控制和脱机 作业控制。 从不同角度出发可以对作业进行不同的 分类，如终端型和批量型， 作业的优先级是指作业进入系统运行的 优先级别，优先级高的作业可以优先进 入系统运行。
4.1.1 作业调度
作业调度又称高级调度、宏观调度或长程调 度，其主要任务是按一定的原则从外存上处 于后备状态的作业中选择一个或多个作业， 给它们分配内存、输入/输出设备等必要的资 源，并建立相应的进程，以使该作业具有获 得竞争处理机的权利。 作业调度的运行频率较低，通常为几分钟一 次。
4.1.2 进程调度
作业名、作业状态
记录作业的标识信息及作业的当前状态。
4.3 进程调度-4.3.1 进程调度的功能
进程调度程序主要完成以下功能：
记录系统中所有进程的状态、优先数和资源 情况。 选择获得处理机的进程。 实施处理机的分配及回收。
引起进程调度的原因
正在运行进程结束 运行进程因某种原因阻塞，如P操作、I/O等 从系统调用或中断返回时，有进程进入就绪 队列且就绪队列为空，或进程优先级高于当 前运行进程且为剥夺调度方式 时间片用完
时间： 0
最短剩余时间优先算法例（续）
作业 A B C D 提交 时间 0 1 2 3 运行 时间 8 4 9 5 开始 时间 0 1 17 5 完成 时间 17 5 26 10 周转 时间 17 4 24 7 带权周 转时间 2.125 1 2.67 1.4
平均周转时间 T=(17＋4＋24＋7)/4=13 平均带权周转时间 W=(2.125＋1＋2.67＋1.4)/4=1.8
作业状态转换图