操作系统讲义-第三章处理机调度与死锁

《操作系统讲义-第三章处理机调度与死锁》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章处理机调度与死锁2021年10月2日1操作系统讲义主要内容3.1处理机调度的层次3.2调度队列模型和调度准则3.3几种调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测和解除2021年10月2日2第二章进程管理3.1处理机调度的层次作业的基本概念1.高级调度（HighLevelScheduling）主要功能：根据某种算法，把外存中把处于后备队列中的那些作业调入内存，当作业完成时做善后处理。作业（Job）：包含通常的程序和数据，并且配有作业说明书；作业步（JobStep）：“编

2、译”->“连接装配”->“运行”；作业流：若干个作业在系统外存形成的输入流。作业控制块JCB（JobControlBlock）通常包含：作业标识、用户名称、用户账户、作业类型（CPU繁忙，I/O繁忙，批量型，终端型）、作业状态、调度信息（优先级，作业运行时间）、资源需求（运行时间，内存，I/O类型数量）、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况。2021年10月2日3第二章进程管理3.1处理机调度的层次1.高级调度（HighLevelScheduling）作业调度：是根据作业控制块中的信息，

3、审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存后备队列中选取某些作业调入内存，为他们创建进程、分配必要的资源，然后将进程插入就绪队列，准备执行。目的：提高内存利用率和系统吞吐量，使那些暂时不能运行的进程不再占用内存，把它们调至外存（存储管理中的对换功能）。1）接收多少个作业到内存取决于多道程序度2）接收哪些作业取决于调度算法最简单：先来先服务调度算法最常用：短作业优先调度算法较常用：优先级调度算法比较好：响应比高者优先调度算法2.中级调度（IntermediateLevelScheduling）2021

4、年10月2日4第二章进程管理3.1处理机调度的层次3.低级调度（LowLevelScheduling）它所调度的对象是进程（或内核级线程），当CPU需要重新分配时，利用一定的算法把它分配给进程，它是最基本的调度。进程调度的功能（1）保存处理机的现场信息；（2）按照某种算法选择进程（如优先数算法，轮转算法）（3）把处理器分配给进程。进程调度的三个基本机制（1）排队器：事先将系统所有就绪进程排成一个队列，方便调度程序最快找到它；（2）分派器（分派程序）：把进程调度程序选定的进程从就绪队列移出，切换上下文，然后把CPU分配给

5、它；（3）上下文切换机制：保存当前程序的上下文，装入分配程序的上下文；移出分派程序，装入新选进程的CPU信息；2021年10月2日5第二章进程管理3.1处理机调度的层次进程调度方式3.低级调度（LowLevelScheduling）非抢占方式：一旦处理机分配给某个进程，不管它要运行多长时间，都让它一直运行下去，决不会因为其他原因而抢占正在运行进程的处理机。这种方式下引起进程调度的因素包括：执行完毕或者发生某事件不能再执行执行进程提出I/O请求而暂停执行在进程通信或者同步过程中执行了某种原语操作，如P，Block等优点：

6、实现简单，系统开销小，适用于大多数批处理系统；缺点：难以满足紧急任务要求，可能造成难以预料的后果。2021年10月2日6第二章进程管理3.1处理机调度的层次进程调度方式3.低级调度（LowLevelScheduling）抢占方式：允许调度程序根据某种原则去暂停某个正在执行的进程，这些原则主要包括：优先权原则短作业优先原则时间片原则优点：防止一个长进程长时间占用处理机，公平服务，适合实时任务的需求；缺点：需要付出较大的开销。2021年10月2日7第二章进程管理3.2调度队列模型和调度准则仅有进程调度的调度队列模型通常在分

7、时系统中只设置进程调度，每个用户建立一个进程，系统利用堆栈，树或者链表来管理就绪进程队列。1.调度队列模型进程执行时可能出现的三种情况：在给定时间片完成，释放处理机进入完成状态；本次时间片内未完成，放入就绪队列尾部；因为某事件被阻塞，放入阻塞队列。就绪队列CPU阻塞队列交互用户时间片完进程调度等待事件进程完成事件出现2021年10月2日8第二章进程管理3.2调度队列模型和调度准则具有高级和低级调度的调度队列模型作业调度按照一定的算法从外存的后备队列选择一批作业调入内存，建立进程，送入就绪队列，然后按照一定的进程调度算法

8、选择进程，分配CPU。1.调度队列模型就绪队列CPU阻塞队列作业调度时间片完进程调度等待事件1进程完成事件1出现队列后备阻塞队列阻塞队列等待事件2等待事件n事件2出现事件n出现……队……2021年10月2日9第二章进程管理3.2调度队列模型和调度准则同时具有三级调度的调度队列模型可把进程的就绪状态分成内存就绪和外存就绪，类似地，阻