# 1 处理机调度和死锁 ## 1.1 处理机调度 在多道程序系统中，调度的实质是一种资源分配，处理及调度是对处理及资源进行分配。 ### 1.1.1 层次 1. 高级调度（外存 -> 内存 -> 就绪）（多道） 又称长程调度或作业调度，调度对象是作业。主要功能是根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为它们创建进程、分配必要的资源，并将它们放入就绪队列。 2. 低级调度（就绪 -> 运行）（多道、分时、实时） 又称短程调度或进程调度，调度对象是进程。主要功能是，根据某种算法，决定就绪队列中哪个进程获得处理机。 3. 中级调度（内存<->外存） 又称内存调度。提高内存利用率和系统吞吐量。为此，把暂时不能运行的进程，调至外存等待（挂起）。当它们具备运行条件且内存有空闲是，把外存上的就绪进程重新调入内存（就绪）。 ### 1.1.2 处理机调度算法的目标 1. 共同目标 - 提高资源利用率 - 公平性 - 平衡性 - 策略强制执行 2. 批处理系统的目标 - 平均周转时间短 - 系统吞吐量高 - 处理机利用率高 3. 分时系统的目标 - 响应时间快 - 均衡率 4. 实时系统的目标 - 截止时间的保证 - 可预测性 ## 1.2 作业与作业调度算法 ### 1.2.1 先来先服务（FCFS）和短作业优先（SJF） ### 1.2.2 优先级调度算法（PSA）和高响应比（HRRN） ## 1.3 进程调度 ### 1.3.1 轮转调度算法（RR） ### 1.3.2 优先级调度算法 ### 1.3.3 多队列调度算法 ### 1.3.4 多级反馈调度算法 ## 1.4 实时调度 ### 1.4.1 最早截止时间优先（EDF） ### 1.4.2 最低松弛度优先（LLF） ## 1.6 死锁（特别重要） ### 1.2.1 定义 在一组进程发生死锁的情况下，这组死锁进程中每一个进程，都在等待另一个死锁进程所占有的资源。 或者说，每个进程所等待的事件是该组中其他进程释放所占用的资源。但由于所有这些进程都已无法运行，因此它们谁都不能释放资源，致使没有任何一个进程可被唤醒。 ### 1.2.2 起因 1. 竞争不可抢占性资源 2. 竞争可消耗资源引起死锁 3. 进程推进顺序不当 ### 1.2.3 产生的必要条件 死锁发生必须具备四个必要条件： **1. 互斥条件**： 分配的资源使用具有排它性。 **2. 请求和保持条件**：进程已经保持至少一个资源，但又提出了新的资源请求。 **3. 不可抢占条件**：进程已获得不能被剥夺。 **4. 循环等待条件**：存在一个资源环形等待链。 ### 1.2.4 处理方法 1. 预防死锁 2. 避免死锁 3. 检测死锁 4. 解除死锁 ### 1.2.5 预防死锁 1. 破坏请求和保持条件 - 所有进程开始运行之前，必须一次性地申请其在运行过程中所需的全部资源 - 允许一个进程只获得运行初期所需要的资源后开始运行。进程运行过程中再逐步释放已分配给自己的、且已用毕的全部资源，然后再请求新的所需资源。 2. 破坏不可抢占条件 当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。 3. 破坏循环等待条件 对系统所有资源类型进行线性排序，并赋予不同的序号。规定每个进程必须按序号递增的顺序请求资源。一个进程在开始时，可以请求某类序号为 i 的资源，以后只能请求 序号大于 i 的资源，或释放 i 请求任意资源。 ### 1.2.6 避免死锁 [银行家算法](https://baike.baidu.com/item/%E9%93%B6%E8%A1%8C%E5%AE%B6%E7%AE%97%E6%B3%95/1679781?fr=aladdin) ## 进程（重要） ### 1. PCB PCB是用来记录进程信息的数据结构 ### 2. 进程的状态 1. 就绪状态 2. 执行状态 3. 阻塞状态 ### 3. 状态变化事件 空->新建：创建执行一个程序的新进程，可能的事件有：新的批处理作业、交互登录（终端用户登录到系统）、操作系统因为提供一项服务而创建、由现有的进程派生等。 新建->就绪：操作系统准备好再接纳一个进程时，把一个进程从新建态转换为就绪态。 就绪->运行：需要选择一个新进程运行时，操作系统的调度器或分配器根据某种调度算法选择一个处于就绪态的进程。 运行->退出：导致进程终止的原因有：正常完成、超过时限、系统无法满足进程需要的内存空间、进程试图访问不允许访问的内存单元（越界）、算术错误（如除以0或存储大于硬件可以接纳的数字）、父进程终止（操作系统可能会自动终止该进程所有的后代进程）、父进程请求终止后代进程等。 **运行->就绪**：最常见的原因是，正在运行的进程到达了“允许不中断执行”的最大时间段，该把**处理器的资源释放**给其他在就绪态的进程使用了；还有一中原因可能是由于具有更改优先级的就绪态进程抢占了该进程的资源，使其被中断转换到就绪态。 **运行->阻塞：**如果进程请求它必须等待的某些事件，例如一个**无法立即得到的资源（如I/O操作）**，只有在获得等待的资源后才能继续进程的执行，则进入等待态（阻塞态）。 **阻塞->就绪：** 当等待的事件发生时，处于阻塞态的进程转换到就绪态。 就绪->退出：在上图中没有标出这种转换，在某些进程中，父进程可以在任何时刻终止一个子进程，如果一个父进程终止，所有相关的子进程都被终止。 阻塞->退出：跟上一项原因类似。 ## 内存管理 要解决的两个问题 1. 每个进程代码中使用的地址可能相同。解决思路：对代码中的地址重定向（加个基地址）。 2. 物理内存可能比较小，不能同时放很多进程进来。解决思路：把要运行的代码移到内存，暂时不用的代码移入磁盘，即交换（swap），内存置换 ### 1. 分段 一个程序分成多个段（每个段特性不同为了方便管理，例如代码段只读、数据段等等），当然这都是逻辑上的。 管理段的结构叫段表，段表保存中进程的PCB中。 ### 2. 页表 把程序按段分对程序员是友好的，但是如果物理存储也按段存，则会导致大块的内存碎片，例如现在需要分个10M的段但是连续的存储空间只有8M/9M/5M三个。解决办法： （将段打散存到页中）不要对内存进行连续的分配，将内存划分成1页1页，按页分配，1页4kb大小，最多浪费的也就4KB。这样不会有内存碎片，也不会出现没有符合要求大小的内存可以申请的情况，因为可以打散了分散到一页一页中。 整个系统的页表就是https://www.cnblogs.com/xdyixia/p/9253138.html中说的多级页表（这个整个系统的多级页表简单来说就是把物理地址都进行了按页划分，保存了每页的基地址（对应下图中的页框号））。程序向系统申请时内存时，系统就会把哪几个页框号分给程序的某个段，程序再把它段0中的第3页数据放到页框6中。 说明：进程需要有自己的“页表”，里面映射双方是程序的逻辑地址中的页号和系统分给这給程序的页框号。 ### 3. 段页结合的内存管理 实际在内存管理中的段页结合如下图，页号加偏移称为虚拟地址，MMU负载从虚拟地址到物理地址的转换，同时也负责权限检查。 上面解决了每个进程代码中使用的地址可能相同，系统给每个进程分配基地址，进程保存在PCB中。 但是进程可操作的虚拟地址为4G（32位系统），可物理地址为1G怎么办。 ### 4. 请求调页内存换入 CPU对数据进行请求时，才会进行映射（虚拟内存到物理内存）。 例如进程1正在运行，进行映射拿数据，查页表发现页框号中没有数据或有进程2的数据，则需要页表调入内存。 ## 页面置换算法 **1：最佳置换算法（Optimal**）：一种理论的算法，选着淘汰的页面是以后一定不再使用的页面（理想化的），该算法无法实现，只能作为其他算法好坏的一个评价对比。 **2：先进先出（FIFO）算法：** 总是最先淘汰最先进去的页面，该算法容易实现。缺点：通常程序调入内存的先后顺序和程序执行的先后顺序不一致，导致缺页率高。 **3：最近最久未使用算法LRU：** 算法赋予每个页面一个访问字段，用来记录上次页面被访问到现在所经历的时间t，每次置换的时候把t值最大的页面置换出去(实现方面可以采用寄存器或者栈的方式实现)。 **4：时钟算法clock(也被称为是最近未使用算法NRU)**：页面设置一个访问位R，并将页面链接为一个环形队列，页面被访问的时候访问位设置R为1。页面置换的时候，如果当前指针所指页面访问R为0，那么置换，否则将其置为0，循环直到遇到一个访问为位0的页面。 但是这个方法有缺点：缺页比较少的时候（最近没有使用淘汰中的“最近”太长了），所有的R都为1（很少变成0）,每次都要转一圈才能找到换出去的页，退化成FIFO，效率不高。 ## 进程和线程 --- 转载至CSDN博主：[[李唐敏民](https://blog.csdn.net/qq_39041210 "李唐敏民")] -------------------------- --- 最后修改：2021 年 02 月 24 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用，请随意赞赏
2 条评论
社会责任感贯穿全文，彰显学者担当。
你的文章充满了创意，真是让人惊喜。http://www.zs0559.com