操作系统-5|6章
1. 进程调度
1.1 什么是进程调度
进程调度是系统有安排的让 CPU 运行不同的进程任务。同时考虑到最大化 CPU 的利用率，又要考虑到进程的平均响应时间，和进程占用 CPU 时间的公平。进程调度的目标是尽可能的实现 CPU 的效率的最大化，又要最小化进程的响应时间。
1.2 进程调度的算法
进程调度问题是个很久远的问题，产生了多种进程调度的算法，目前用的较多的是混合优先级调度算法。
先来先服务算法
FCFS，First Come First Service. 就像排队，先请求的进程优先服务。显然这种算法的平均响应时间较高。
时间片轮转算法
每个进程服务固定的时间，如A 进程20ms，然后 B 进程20ms，。。。 Z 进程20ms，再次 A 进程20ms。如此轮转的选择进程运行固定的时间片。 注意进程的切换也需要时间，这种算法的平均响应时间可能还会大于 FCFS 算法。
短任务优先算法
系统会对进程的运行时间有个评估，让时间最短的最先运行。才用贪心策略的这种算法能获得最好的平均响应时间。但是这会使得需要长时间运行的进程饥饿，并且我们并不能知道我们要运行的进程确定的运行时间。一个解决办法是启发式方法，即我们不能精确的给出一个进程的运行时间，我们可以通过它的大小来推断运行时间。
优先级调度算法
考虑到有的进程任务是重要的有的是不重要的，如内核程序和用户程序。设置优先级能将优先级最高的进程最先完成，要让每个进程都能合理的占用 CPU，可以动态的调整优先级来达到。
混合调度算法
混合 优先级调度算法和时间片轮转算法，将进程分为几个大类，每个大类设置优先级，在每个大类中采用时间片轮转算法。
实时调度算法 (realtime)
对于某些进程任务具有很高的重要性，我们必须在规定的时间内完成，都这将会造成严重的后果。实时调度算法考虑的是每个进程任务必须在规定的时间内完成，并不去考虑响应时间或是吞吐率。
- 最小截至时间优先：EDF, Earliest Deadline First。当新的进程来了，系统立刻检查所有进程中最早结束的进程，且抢占式的运行。是一种动态的分配优先级。动态优先级适用于任务源源不断产生，且不清楚任务的运行状况，并让所有的进程不感到饥饿。
- 最短周期优先（单调速率调度）：RMS, Rate Monotonic Scheduling。是一种静态优先级调度。事先已经设置好的优先级，在没有特权的情况下不能更改优先级。
1.3 进程调度的过程
因时序、外部中断、进程挂起等使得操作系统获得CPU 的控制权
操作系统在所有就绪的进程中按照某个算法选择进程
若选择的不是当前的进程，则将当前的状态保存，
将选中的进程的运行条件设置好，切换运行选中的进程
下图显示进程P0和进程 P1的调度运行。
1.4 优先级倒挂 (Priority Inversion)
是指低优先级的进程比高优先级的进程先占用 CPU 运行，这和优先级算法是相悖的。具体的有两种优先级倒挂的形式：
- 第一种是，低优先级进程L与高优先级进程 H共享一个资源，低优先级已经将资源锁定，等有高优先级的进程到来时因为它需要这个共享资源，所以不能抢占CPU ，要等到 L 进程将共享资源释放后 H 进程才能占用 CPU。 这就造成了低优先级的进程比高优先级进程先运行。
- 第二种是，有3个进程，L 低优先级，M 中等优先级，H 高优先级，L 锁住了 H 要用的资源，同时 M 不需要这个资源可以抢占 L 之前运行，这时L 和 H 都不会运行，要等到 M 运行结束后 L 运行，等 L 释放资源后，H 运行。
常用的解决办法是： - 优先级继承(Proirity Inheritance),让锁住资源的低优先级进程暂时继承比需要资源的高优先级进程更高的优先级, 使得资源尽快的释放.
- 禁止中断: 主要针对第二种优先级倒挂的情况,使得 M 进程不能抢占CPU。
1.5 参考
https://wenku.baidu.com/view/eb543ce29b89680203d825d7.html
https://www.embedded.com/design/configurable-systems/4024970/How-to-use-priority-inheritance
https://www.quora.com/What-is-priority-inversion
https://www.embedded.com/design/configurable-systems/4024970/How-to-use-priority-inheritance
2. 进程通信
进程之间的通信也是模仿了人类社会中的通信方法，一个发一个收，多个发多个收，大家在一起讲话各自取得个字咬的信息。父进程与子进程之间通信，普通进程之间通信。
2.1 点到点连接通信
管道（pipe）
一个发一个收。一个进程要和另一个进程通信，A 进程创建一个管道，并标明目标通信的进程B。A写入管道，B从管道取出。创建一个管道必须要标明发送端和接收端。
类似真实的管道，建设好后使用。
特点：必须事先建立好两端之间的连接。只能是一个读、另一个写，方式确定。
套接字（socket）
通信双方都要创建一个套接字，一个作为服务方套接字，一个属于服务方套接字。具体工作过程：服务器套接字在监听请求，客户端创建的套接字向服务方发送服务请求，服务方将会创建一个客户端套接字与远程客户端对应点对点的连接。然后双方就可以使用发送和接收功能来交流。
2.2 信号（signal）
信号本质上是一个内核中的数据结构，发送方将这种数据结构的数据准备好并指明目标就发送。不事先建立连接。通过产生中断给操作系统，操作系统知道有进程要发送信号就按照目标查找接收方发过去。
类似电报，将报文和收报人交给电报公司，电报公司就发送这个电报（中断）。若收报方不响应，则本次通信结束。
2.3 信号量（旗语）（semaphore）
指示当前信道是否正在使用的一个标志量。在一个信道中在一个时刻只能存在一个信号通过，就像火车通过隧道，当有信号正在途中则设置一个标志，否则设置另一个标志，以此来告诉下个信号是否应该到来。
2.4 共享内存（Share Memory）
通信双方需要共享某些数据，由进程 A 创建一个内存空间，且双方都将内存的物理地址映射到自己的（虚拟）地址空间，这样在操作物理内存中的资源时就像操作自己的空间。较为复杂的方式。两端都可以写读。必须在同一个物理机上。
2.5 消息队列
生产者消费者模式。任何进程都可以写入，任何进程都可以读出。多对多的模式。
