OS：进程管理中

OS：进程管理中

进程间通信

共享存内存通信
消息传递系统：内核缓冲区

直接通信方式
间接通信方式

管道通信
信号

信号搜集
信号

信号有关问题总结

调度

调度层次

作业调度（高级调度）
中级调度（内存调度）
低级调度（进程调度）

处理机调度方式

抢占式调度的实现方式

发生抢占时的时机
need位被置位时机

有进程进入就绪态时
响应时钟中断时
不能调度的时机

进程调度算法

调度相关参数
先来先服务
优先级调度算法

非抢占式
抢占式

短进程优先算法
短剩余时间调度算法
最高响应比优先算法
时间片轮转法

时钟中断简介
真题分析

多级队列调度算法（MQ）
多级反馈队列调度算法
传统调度算法

调度综合题

多处理机调度

多处理机分类与调度

多处理机调度
负载均衡
处理器亲和性
调度策略

单队列调度/多队列调度
多处理机调度的性能指标

进程间通信

问题：为什么只有进程间通信，没有线程间通信？
线程共享进程间的地址空间，本身就是共享的。

共享存内存通信

进程1与进程2的内存映射关系不同。

如何观看表格令不同进程共享数据：令进程1和进程2的某个虚拟内存映射到同一块物理内存。

实际使用：

以页为单位或者以段为单位进行共享，因为两个进程都可以访问共享内存，因此需要同步与互斥。
注意：共享内存的这个内存是在用户空间的，而非再内核区域。

具体过程
首先将用户空间的某一块内存定义为要被共享的内存，其次再连接到自己的逻辑地址空间内。
以上两步都需要“系统调用”。

但是用户A与用户B再想要访问这块区域时，并需要系统调用，直接访问自己的逻辑地址空间即可。

而当A和B都不在链接到该块区域时，共享内存也并不会被释放，只有os接收到释放的系统调用时才会释放。
注意：共享内存的访问方式。

问题1：共享内存的访问得用P、V操作吧，也不用进内核么？
共享内存区的建立需要系统调用，把共享存储区映射到自己的用户内存，建立之后就是进程自己完成同步和互斥了。

问题2：进程A和B共享，然后A跟B都又不想共享了，都删除了页表的链接，然后只有执行系统调用的时候共享内存才会呗释放，那不还得是最后一个共享该内存的进程发起这个系统调用吗？
进程只回收自己的那块区域，最终没进程用了，这区域是os负责回收。

内核空间共享

与“操作系统引导过程联系起来”：os也是磁盘上的一个程序，因此将OS从磁盘加载到内存的过程就是操作系统引导过程。
BIOS是内存ROM中的一个程序（断电后也不会消失）,开机后PC指向BIOS的第一条指令，开始执行BIOS程序，BIOS会硬件自检，且在内存最开始的地方构建中断向量表，之后加载磁盘的第一哥扇区MBR并开始执行MBR。

MBR内包含磁盘分区表，表内容包括是否为系统分区（只有分区内存在os的才叫系统分区），选择哪个分区并加载PBR。

PBR功能就是加载该分区的OS并将CPU控制权交给OS。

基于前面的怎么理解每个进程都有内核空间在自己的逻辑地址？

注意：进程间通信除了共享内存存储是用户空间，其他都是内核空间。

消息传递系统：内核缓冲区

内核缓冲区的定义：

私有心想

私有心想都在内核中。

公共心想

共享信箱

共享的话进程1会将位置告诉进程2

直接通信方式

P1为什么会知道进程2的私有信箱，因为进程1通过系统调用进入内核，内核知道进程2的私有信箱。
私有信箱会放在进程自己的PCB里。

间接通信方式

共享信箱可能又多个，因此要指明信箱号。

管道通信

管道依靠内核空间中的环形缓冲区（循环队列）。

管道特点

具体例子

管道所有的例子都可以兼容，注意：nread与nwirte都只是所有的读取次数与写入次数，而非与ds上的rear跟front指针，因此并不要mod 16，而下标在这个例子中已经mod 16了。

上图可以读的区域：12、13、14、15、0、1、2、3、4
可以写的区域：5、6、7、8、9、10、11

总结： 所以每一个打开的文件都是一种管道，分别有写管道和读管道，对应读文件和写文件，因为比如父进程和子进程可以共享文件，因此视为一种进程间的通信方式。这样理解对么？

答案：不对。

修正后的总结： 管道可以视作一种特殊的文件，在创建管道的时候会同时得到一个读端和写端的文件描述符，分别对应读写管道。一般拥有管道的进程会再创建一个子进程，子进程会继承管道的读写端，父进程和子进程之间可以通过管道通信。

但是一般打开文件，就只会得到一个代表该文件的文件描述符，使用read/write系统调用操作该文件描述符，从而实现读写文件的功能。

因此： 跟普通的文件没有关系，管道创建就是为了进程通信。管道可以视为是一种特殊的文件，管道的使用目的就是为了多进程之间通信。

读写管道何时被阻塞
当管道空了或者满了，进程再读写时都会被阻塞。


管道空：读次数和写的次数一样
满了：写的次数-读的次数=管道大小

管道初始时为空：

建立管道

管道被视为一种打开的文件（只有被打开的文件才会有文件描述符），读管道和写管道分别有一个文件描述符。

管道权限与通信方式：半双工通信

不同进程对管道的权限不一样，有的不读不写，有的只读不写。

通信方式（A与B之间进行通信）：
单向通信：A只能跟B进行通信
全双工（双向）通信：A跟B可以同时给对方发信息
半双工通信：A确实可以跟B传，B也确实可以对A传送，但是A跟B不可以同时给对方发信息。

具体例子：
首先分析两种通信方式：
A->B：A写B读
B->A：B写A读
管不得要分两个文件描述符，因为两个进程要使用。

不可以A写一半了B也开始写，那就分不清哪个是A写的哪个是B写的。
PPT上有例子，但是并不会要求A全部写完了，B才能开始读，可以并发的。

管道的继承

匿名管道通信是在亲属关系的进程之间的进程通信，父子进程之间当然可以通过管道通信，当然兄弟进程之间也可以通过进程通信。

问题： 子进程可以修改从父进程哪里继承来的管道的权限么？
可以自行关闭文件描述符，但是一旦读或写的进程描述符被关闭了就再也无法打开。

匿名管道，父进程的权限是可读可写，那么子进程继承了匿名管道的两个文件描述符，那子进程不能修改自己对管道的访问权限变成只读或者只写吗？
可以的，如果想只读，那么就把写管道的文件描述符关闭即可。

但是不能返过来对吧，就是父进程如果只读不写，子进程没法写。
是的，如果继承之前父进程已经把写口给关闭了，那么子进程也只能继承到读口。这样的话这个管道就用不来了。

管道的引用计数
管道本质就是打开的文件，因此也有引用计数：有几个进程共享他就是几。

管道中的写端关闭是暂时关闭还是永久关闭？是永久关闭的。
当写端读端同时关闭就可以释放管道，当读端关闭了就可以释放管道也合理。

多进程读写管道


读管道或者写管道都会有互斥锁。

匿名管道与命名管道：

信号

用户与进程基本来说是等价的。

终止信号

系统调用信号

某一种系统调用的作用就是发信号。

硬件异常

发送信号的源头可以是os或者进程。

信号搜集

有64种信号，从0到31种是缺省信号，32-63是自定义信号。
receive中的每一位都表示一种信号，若该位为1则表名接收到了该信号。
sigmask的某一位为1则标识屏蔽该种信号。

信号

缺省信号

用户自定义信号

调用一次系统调用sigaction(signum，function)就可以注册一个用户自定义信号，signum是信号的编号，信号处理函数定义在用户空间下，而非内核空间。
则当os向用户进程发送55信号时，进程就会调用hello()的信号处理函数。

信号处理全流程

在中断返回前检测与处理缺省信号，如果有缺省信号那就处理了；如果有用户自定义信号那就将内核栈中保存的断点修改为用户态下的信号处理函数，依旧进行中断返回，此时就会返回到信号处理函数。
处理过以后还要再次返回内核恢复原断点，因此在每一个信号处理函数的末尾都有一个信号返回系统调用，返回内核恢复原断点。

问题：中断和异常是缺省信号么？ 不是，这两个是两个体系。

信号有关问题总结

信号的发送方是谁？
OS或者别的进程

信号的搜集依靠什么方式？

信号的类型有哪些？
缺省信号+用户自定义信号

OS中不同进程处理缺省信号的方式是否相同？OS中不同进程处理缺省信号的方式是否相同？
相同：因为是OS自己定义的。 不相同：是用户进程自己定义的。

除数为0异常类型和发送的信号类型分别由谁决定？
硬件和OS

由硬件决定是中断源。
发送信号的时机：中断或者异常处理程序
检测信号的时机：中断返回前

具体案例

自己的答案：OS加入一个除0的异常处理程序，这个程序会在中断返回前发送一个用户自定义信号，进程自己通过系统调用在信号表中加入除0的信号+信号处理函数。

调度

调度层次

作业调度（高级调度）

一个作业可以理解为就是一个任务。

左下角的蓝色块块是作业控制块。
作业调度产生PCB：

中级调度（内存调度）

与前面所讲的“7状态转化图”息息相关，就绪态的进程被挂起时会变成挂起就绪态，阻塞态的进程被挂起时变成挂起阻塞态。
进程被挂起时并没有消除进程的PCB。

低级调度（进程调度）

三级调度的图示

作业调度与中级调度的区别

处理机调度
可能是进程或者线程占据CPU，但是不区分，统一都叫处理机调度。

调度器

current_proc永远指向当前的进程，进程切换前她指向切换前的进程，进程切换后指向切换后的进程。

闲逛进程
当就绪队列内为空时，为了防止CPU空转，就会有一个闲逛进程占据CPU

处理机调度方式

非抢占式调度

yield系统调用可以主动进入就绪态，除了抢占式调度还有协作式调度，每个进程不争不抢，os也不分配全靠进程自觉，进程觉得我应该把CPU交给其他进程使用时就会调用yield系统调用让自己进入就绪态。

注意：是有某些方式可以主动进入就绪态的。

问题：非抢占式调度比抢占式调度的CPU利用率更高？

抢占式调度

调度时机： 时间片用完或者有更高优先级进入就绪态、进程主动放弃CPU
因此：时间片调度算法是一种抢占式调度算法。

抢占式调度的实现方式

只有进入内核时进程才会被OS下CPU，增加了这个标志就意味着进程需要被抢占。

进程发生调度前一定会发生异常或者中断。

发生抢占时的时机

need：有更高优先级的进程出现，需要被调度
can：可以被调度

need位被置位时机

有进程进入就绪态时

举个例子：阻塞态->就绪态
有进程进入就绪态只有两种情况：阻塞态->就绪态，创建态->就绪态，不考虑运行态->就绪态，这是被调度之后的。

当进程P被唤醒以后，检查P的优先级是否大于当前进程的优先级，若大于则将current的need标志位置为1，则在中断返回前可能发生进程调度。

举个例子2：创建态->就绪态

创建态->就绪态置位need时，只能是父子进程，一定是父进程执行在内核创建的。

响应时钟中断时

处理时钟中断，让时间片-1，若时间片为0时将need位置1

不能调度的时机

重点是什么时候进程不能发生调度：

当前进程正在执行中断处理程序；处在内核临界区中，但是在用户临界区中就可以被调度；

注意： 执行调度程序前通常需要关中断，进程调度程序也是一个原语；用户态的上下文与内核态的上下文是不一样的。

能不能被调度主要是修改了“can”的标志位：

进程调度算法

调度相关参数

CPU利用率：只有当进程在自己用户空间时才是实际运行，不包括执行中断处理程序的执行时间。
系统吞吐率：单位时间内完成作业的个数，有一段时间N，有几个作业C，则C/N就是系统吞吐率。
周转时间：作业从提交（创建进程）到完成经过的总时间；作业完成时间-作业提交时间。
带权周转时间：周转时间/运行时间

等待时间：从创建到完成，处于就绪态的时间之和，等待CPU的时间。
响应时间：用户提交请求到系统首次响应的时间间隔。

先来先服务

周转时间：作业完成的时间-作业到达的时间

优缺点

进程在系统中执行时有时候用CPU有时候用I/O，使用CPU的时间更长就是CPU密集型进程，使用I/O的时间更长就是I/O密集型进程，但是调度看的是对CPU的分配。

因此：期望CPU短的进程先上CPU，以此更快的能够使用I/O。

优先级调度算法

非抢占式

即使更高优先级的进程进入就绪态也不会去抢占CPU

抢占式

抢占式调度算法中新进程进入就绪态后一定是原进程创建的新进程。

短进程优先算法

一般说短进程优先算法都是非抢占式的。
优点： 具有最优的平均周转时间
缺点：

短进程优先算法只是一个理论上的调度算法。

短剩余时间调度算法

最高响应比优先算法

响应比=1+等待时间/运行时间

短进程优先调度只考虑了运行时间短不短，并没有考虑等待时间长不长；而最高响应比优先算法同时考虑了等待时间与运行时间。
分析：
运行时间越短、等待时间越长则响应比越大，因此既综合了短进程优先的长处，又不会造成进程饥饿。

时间片轮转法

时间片轮转算法实际上是先来先服务的一种改进，时间片很依赖时钟中断，时钟中断没发生一次时间片就-1。

时间片举例：时间片为20

等待时间：从提交到完成处于就绪态的总时间

时间片轮转调度中的时间片长度

时钟中断简介

问题：时间片调度算法中时间片为20应该是指：发生20次时钟中断就让进程放弃CPU，而不是一次时钟中断是20个时钟周期。
回答：是的，不是后者。

时钟中断是一种外中断，依赖于计算机中一个叫计时器的部件，每隔一段时间就会发生一次时钟中断，而这段时间的设置取决于“特权指令中设置的时钟时间”。

错误认知：时钟中断的间隔就是时钟周期，每过一次时钟周期就发生一次时钟中断（错误的）。时钟周期是硬件设置的，时钟中断是依靠特权指令可以设置的。


增加了一个“need标志位 与 can标志位”。

真题分析

I只有在抢占式调度时才有可能会发生进程调度，其他时候不会发生进程的调度，而是直接中断返回。

多级队列调度算法（MQ）

分为队列间的调度算法与队列内的调度算法。
特点：进程一旦进入某个队列就不会再变化了，而多级反馈队列调度中进程是可以来回移动的。

多级反馈队列调度算法

改进：进程可以在不同队列间移动。

传统调度算法

先来先服务：不公平，平均等待时间较差
短进程优先算法

最高响应比优先算法：不可抢占
时间片轮转算法：公平，但是平均等待时间较差
多级反馈队列：多种算法的集成

调度综合题

是“多级队列”不是“多级反馈队列”，注意：一切调度方式都是非抢占！

等待时间：处于就绪态的时间，=开始执行的时间 – 创建的时间

多处理机调度

多个CPU就可以实现并行。

多处理机分类与调度

对称多处理机又称为SMP

多处理机调度

静态分配

在调度之初就决定好哪个任务属于哪个CPU，任务123属于CPU1，任务456属于CPU2，任务3只会在CPU1上执行，不会在CPU2去执行。

动态分配

每一个任务都有可能跑到任意一个CPU上去执行。

负载均衡

处理器亲和性

每个任务对CPU应具有亲和性，既：每次都找执行过的CPU继续执行，因为局部性原理，所以Cache、TLB都会有缓存，更容易命中。

处理器亲和性和负载均衡是相矛盾的两个特点，因此需要统筹考虑。

调度策略

单队列调度/多队列调度

单队列调度

单队列调度天然就是动态调度策略

多队列调度

但是多队列调度并不等同于静态调度策略，因为可以进程窃取。

CPU2执行完任务4后为了防止CPU2空转，可以将左边的任务过渡到右边，这称为”进程窃取“。

多处理机调度的性能指标

性能指标举例：

任务流时间：某个进程执行的时间（会在不同CPU上运行）
调度流时间：所有进程完成的总时间
平均流时间：调度流时间 / 任务数

重要：
CPU利用率：该CPU上任务流之间之和 / 最大有效时间单位

=自己运行的时间 / 整个任务完成需要的时间

最大有效时间单位：一共需要多长时间完成所有任务

加速比：调度流时间 / 最大任务时间
假设任务在单CPU上运行，则需要19.5的时间；但是多CPU上运行只需要7的时间，因此加速比为：19.5 / 7