MEMO

1. PCB块：进程存在唯一唯一唯一！标志
2. 程序静态，进程动态
3. 每个进程有
   UID：用户ID，进程创建者的ID；通常大于500
   EUID：有效用户ID，表示进程对文件资源的访问权限；
4. setuid：对二进制文件执行setuid，任何用户执行时都以setuid程序文件所属用户权限去执行；(用户uid执行passwd命令时，euid=root ID=0)
5. PC程序计数器： PC总是指向下一条将要取指的指令地址。CPU总是按照PC的指向对指令序列进行取指、译码和执行。PC决定了程序运行流向。
6. 原语：不可中断的一段程序。注意，像赋值操作一般都是原子操作i++; int i=2;这样的

进程

一次只有一个进程在一个处理器上运行。
进程是资源拥有的资本单位；线程是CPU调度的基本单位

• PCB块：包含①进程状态(5种)、②进程编号、③PC程序计数器、④寄存器、⑤内存界限、⑥打开文件列表……还有CPU调度信息内存管理信息、记账信息(CPU时间、等等)、I/O状态信息(分配到的I/O设备列表、打开文件列表)
  
• 进程的内存结构：①栈(向低地址生长)、②堆(向高地址生长)、③数据段(全局变量)、④文本段/代码段、⑤PC程序计数器的值
  

1.进程调度

1.1调度队列

• 作业队列：所有进程
• 就绪队列；
• 设备队列：每个设备都有自己的设备队列，e.g.I/O设备队列：等待I/O操作。

1.2进程调度程序

调度器/调度程序执行。
调度程序将CPU控制 交给 短期调度程序选择的进程。
要切换上下文-->切换用户模式-->跳转到用户程序合适的位置重启程序。

• 长期调度程序(作业调度)：从缓冲池选择进程加入内存。选择合适的I/O、CPU密集型进程组合，使得V_创建进程 = V_{进程离开系统}
  频率低
• 短期调度程序(CPU调度程序)：从ready队列中取出一个进程，并分配CPU。频率高。
  1. 运行-->阻塞：I/O请求、wait()等待子进程终止、系统调用申请某资源 资源还未被申请到时
  2. 运行-->就绪：中断、时间片到期、被高优先级进程抢占
  3. 阻塞-->就绪：I/O完成、申请的资源已分配；
  4. 进程终止
• 中期调度程序（内存调度）：swap 降低多道程序程度，提高内存利用率、吞吐量挂起一些暂时不能运行的进程到外存等待(阻塞态)，后面再调回来加入ready队列(就绪态)。

1.3进程状态切换

• 运行态：正在占用CPU运行ing；

• 就绪态：在ready就绪队列中排队等待CPU

• 阻塞态：e.g.在等待I/O

• 创建态：new正在创建

• 终止态：进程完成执行。

• 就绪态-->运行态：被CPU调度，获得CPU资源开始运行；

• 运行态-->就绪态：时间片用完、更高优先级进程抢占

• 运行态-->阻塞态：主动、请求某一资源、等待I/O操作完成

• 阻塞态-->就绪态：被动I/O完成、中断结束

1.4 CPU上下文切换/进程间CPU切换

上下文切换：从进程A切换到进程B运行；
PCB信息：寄存器值、进程状态、内存管理信息等等

• 上下文切换流程：A状态保存、B状态恢复

  1. 进程0running，挂起进程0：保存状态到PCB0
  2. 进程1执行，从PCB1加载状态
  3. CPU跳转到PCB1的PC指向位置执行

• 上下文切换 与 进程调度：调度是一种决策行为，决定资源分配给哪个进程；
  而上下文切换是执行行为。懂了吧

• 进程间CPU切换：中断/陷阱（异常）

  1. 进程0running，中断or系统调用；
  2. 挂起进程0：保存状态到PCB0；
  3. 进程1执行，从PCB1加载状态；
  4. 中断or系统调用；
  5. 挂起进程1：保存状态到PCB1；
  6. 进程0恢复执行，从PCB0加载状态

上下文切换时间是纯粹的时间开销，与硬件支持密切相关。

1.5 移动操作系统的多任务

• 移动操作系统：
  • iOS：前台应用程序+后台应用程序；
    可能会限制多任务。
    • 前台应用程序：打开的屏幕显示的应用程序
    • 后台应用程序：位于内存但不占用屏幕的应用程序
  • Android：对需要后台处理的应用程序，该应用程序使用服务(独立的应用程序组件)，服务没有用户界面、占用内存少。
    高效的多任务支持。

1.6 进程调度原则

使这些量尽量优化，平均值尽量优。当然要综合目的(保证用户收到的服务质量：响应时间↓↓)

• CPU使用率↑：使CPU尽量忙
• 吞吐量↑：throughput = 完成进程数量/单位时间
• 周转时间↓(不是最佳准则：= T _进程完成 - T_进程提交 = 在CPU执行时间+在ready队列等待时间+I/O执行时间+阻塞时间(大杂烩)
• 等待时间↓：在ready队列中时间之和。SJF最短作业优先调度算法最佳
• 响应时间：提交进程<-->产生第一响应 期间的时间。

1.7 调度算法

短期调度程序(CPU调度程序) 在ready队列中选择进程的方法

1.7.1 FIFO/FCFS

先来先服务

• 缺：平均等待时间长
  护航效果：队列里的短进程都在等那个正在执行的长进程，等待长进程释放CPU，这样CPU、设备利用率↓↓。

1.7.2 SJF最短作业优先调度算法

最短CPU优先执行，平均等待时间最小。
可抢占、可不抢占。

• 用起来很困难，要知道一个进程的执行时间，so一般SJF只是一个判断用的媒介
• 指数平均预测方法：T_n+1 = αt_n + (1-α)T_n
  • T_n+1：下一次CPU执行预测值
  • t_n：第n个CPU执行长度
  • T_n：存储过去历史
    so，α→1：说明更侧重最近历史
    α→0：说明更侧重历史

1.7.3 优先级调度算法

会出现饿死的情况：来的都是高优先级的，一直挤你(要看抢占or非抢占)，一直在队尾...可怜。
↑可以用老化解决，随时间增高优先级这样。

• 注意是大数高优先级or小数高优先级。坑啊

1.7.4 RR轮转调度算法

抢占的
时间片T，运行中进程A运行时间>T，则中断、上下文切换，A回队尾。

• 不会有进程连续分到时间片(除非只有它一个进程了)-->抢占的
• 极端情况
  • 时间片太大：→FIFO
  • 时间片太短：上下文切换太频繁，开销大，没意义。-->时间片>>上下文切换时间

1.7.5 多级队列调度算法

ready队列分成多个单独队列。有各自的调度算法。

1.7.6 多级反馈队列调度算法

允许进程在队列中迁移

• 过多使用CPU-->去低优先级队列
• 等待过长-->去高优先级队列
• I/O密集型 and 交互进程-->高优先级队列

2. 进程运行

2.1 创建进程

• 进程树：父进程 --创建--> 子进程
• pid进程标识符：每个进程唯一。
• init进程(pid = 1)：Linux系统所有进程的父进程
  开机后创建各类用户进程
  • kthreadd(pid=2)：创建额外进程
  • Web服务器、打印服务器
• ps -el：列出当前系统中所有活动进程完整信息

2.1.1子进程

fork()时父进程会阻塞！！从CPU中离开。

• 获取资源
  1. 从OS直接获取资源
  2. 从父进程获得资源子集
• 执行方式
  1. 可能父子进程并发执行
  2. 可能父进程等待，知道某个子进程完全执行完
• 子进程地址空间
  1. 是父进程复制品、有和父进程完全一致的程序和数据。
     e.g.fork()允许父子进程轻松通信。
     子进程内 系统调用fork() return 0;
     而父进程内返回值 = 子进程pid 非0；
  2. 子进程加载另一个新程序
     • 如果fork()之后调用exec()，
       • pid不变
       • 以新程序取代进程空间，堆栈、代码段都改写；当前剩下代码不再执行；
       • 失败return -1 成功无返回
• Linux/Windows：fork()不用传递参数，CreateProcess()要传至少10个参数。

2.1.2 创建原语：进程创建过程

1. 为新进程分配唯一pid，申请空白PCB块(PCB块有限)；
2. 分配资源：内存、I/O、文件等。从OS or 父进程获得
3. 初始化PCB块
4. 加入ready队列

2.2创建终止

• 终止事件：
  1. 正常结束，任务完成
     也可以是进程调用exit()请求删除自己
  2. 异常结束：非法指令、运行超时、I/O故障等等
  3. 外界干预：如操作员系统干预
• 父进程调用wait() 或 pid = waitpid(-1/*pid*/, NULL, 0)，把自己调出ready队列，直到所有子进程终止。
• wait(pid) 或 waitpid(pid, NULL, 0) pid>0则等待指定进程终止
• 级联终止：通常由OS启动，父进程终止，其所有子进程也终止。OS不允许无父进程的子进程在系统内。
• 僵尸进程：子进程终止，但父进程还没调用wait()，短暂存在。等待父进程调用wait()。
• 孤儿进程：父进程没有调用wait()就终止。init()进程会定期调用wait()。

2.2.1终止原语：进程终止过程

1. 根据pid检索PCB块，读该pid进程的状态；
2. 若还在running，立即终止，让出CPU
3. 将子进程都终止；
4. 释放其资源给父进程 or OS
5. PCB从其队列中删除

3. IPC 进程间通信

共享内存、消息传递、管道通信

3.1 共享内存

e.g.生产者消费者模型
ps.进程内多线程自然共享进程 空间
对共享内存进行写or读操作时，要使用同步互斥工具(信号量操作等等)进行控制。

• 缓冲区 buffer：允许生产者进程、消费者进程并发执行。
  • 无界缓冲区：不限制缓冲区大小
  • 有界缓冲区：可用循环队列实现，0 ~ N-1
    • buffer is empty:in == out
    • buffer is full:(in + 1)%BUFFER_SIZE

3.1.1 POSIX 共享内存

• 创建共享内存对象：shm_fd = shm_open(naem名字, O_create对象不存在时创建 | O_RDRW打开读写权限, 0666目录权限)
• 设置共享内存大小：ftruncate(shm_fd文件描述符，4096字节单位)
• mmp()创建内存映射文件；
• 写入共享内存：sprintf()

3.2 消息传递

e.g.微内核(Mach OS)采用，当前IPC最常用方式。

• 适用少量数据，不同避免冲突；适用分布式系统、计算机网络。

• 单位：格式化消息message

  • 定长消息：更复杂的系统级实现，编写简单。
  • 变长消息：编写稍难

• 两个原语操作

  • 发送消息
  • 接收消息

3.2.0 消息传递的同步/阻塞

涉及原语的设计。毕竟是原子操作。
同步--阻塞，异步--非阻塞

• 阻塞发送：send的过程一直阻塞，直到被接收才恢复；
• 非阻塞发送：send完立即进行下一步；
• 阻塞接收：receieve的过程一直阻塞，接收完恢复；
• 非阻塞接收：receive一个空值or一串消息，马上下一步
  收发双方的模式互不影响，独立的。

3.2.1 直接通信

两个原语：send、receive

• 寻址对称性：一定要指定对方
  1. 发送进程Q发送消息给P：send(P, message)
  2. 挂在接收进程.消息队列上
  3. 接收进程P从自己的消息队列上取出消息 receive(Q, message)
• 变形-->寻址非对称性：发送方指定即可
  • 发送进程Q发送消息给P：send(P, message)
  • 接收进程P收消息可以是任何进程发来的，不一定是Q发的，id被设置成对方通信进程的名称 receive(id, message)

3.2.2 间接通信

1. 发送进程发送消息给中间实体(常称为：信箱)
2. 接收进程从中间实体上取出消息

• 广泛用于计算机网络中。像什么邮箱啊，好理解了吧。

3.2.3 管道通信 pipe

消息传递的一种特殊方式。

• 管道：pipe文件。一个读进程 一个写进程之间的共享文件。

3.2.3.1 普通管道

也叫匿名管道。允许一对进程通信。
通信进程双方具有父子关系。

• fd[0]管道读出端
• fd[1]管道写入端，毕竟pipe是文件属性嘛，有文件描述符
• 单向，如果需要双向，设置两个管道。-->半双工

3.2.3.2命名管道

通信双向，半双工，可多个进程之间通信。UNIX中命名管道叫FIFO，mkfifo()创建，直到被显示删除都一直存在。

• 如果要全双工-->建立两个FIFO。
  不同系统之间，使用socket套接字。

ps.Windows的命名管道更丰富，支持全双工通信，可不同机器。

3.2.4 Mach OS例子

• 接收消息msg_receive()
  blablabla，队列中消息按照FIFO排列，但不绝对。Mach专为分布式系统设计。

3.2.5 Windows ALPC例子

高级本地程序调用 ALPC工具，同机器两进程之间，类似RPC远程系统调用。(不能给程序员用，不是API)，但RPC有用到ALPC简介处理。

1. 小消息<=256B，利用端口消息队列中转，直接复制
2. 更大一点，用区段对象(相关共享内存区段)
3. 太大时：服务器通过API读写客户端地址。

• 连接端口：处理连接请求
• 通信端口：

3.2.6 客户机/服务器通信例子

1. 套接字socket：连接有一对socket
2. RPC远程程序调用：传递有结构的数据。
   每个单独远程过程都有一个--客户端提供stub存根
   定义一个XDR外部数据表示，从而解决不同机器大端小端表示的差异。
   保证每个消息执行正好一次。
3. 管道。上面复习了

4. 多处理器调度

多个CPU负载分配问题。

1. 非对称多处理器：一个CPU(作主服务器)，处理所有调度决定、I/O等；；其他CPU负责执行代码。简单理解
2. SMP对称多处理器：每个处理器自我调度，
   • 可能只有一条ready队列
   • 可能每个处理器一个ready队列

• 软亲和：进程尽量保持在to同一处理器上(不强硬)
• 硬亲和：允许在某个处理器子集上运行。

4.1 负载平衡

SMP系统尽量一视同仁对待各个处理器。

• 公共队列不用考虑，因为处理器空闲了自然回去找它的
• 私有队列：一个特定任务周期性检查每个处理器负载。
  • 忙的就pull拉迁移
  • 闲的就push推给它。

5. 实时CPU调度

硬实时要求严格，软实时就是尽量。
实时操作系统CPU特殊

5.1 优先权调度

抢占的优先权调度算法。

• 进程周期性的，定期需要CPU，固定处理时间t，进程的CPU处理截止期限d、CPU周期p。0<=t<=d<=p
• 调度程序任务：
  • 准入控制，进来了就要保证进程完成
  • 进不来，拒绝请求。

5.2 单调速率调度

抢占 分配优先级 = 周期↓优先级↑ or 周期↑优先级↓
频繁需要CPU的进程优先级更高
周期性进程，每次执行时，CPU执行长度相等。

5.3 最早截止期限优先调度

截止期限越早，优先级越高。抢占

6. 例 Linux调度

默认算法：CFS 完全公平调度程序，以vruntime为key的红黑树，vruntime↓越先运行，支持SMP。

• vruntime += 实际运行时间（time process run) * 1024 / priority
  • 运行时间↑ vruntime↑-->CPU密集型在树右边
  • I/O密集型运行时间短，稍稍右移(相对左移)
• priority 优先级：
  • 根据友好值分配查优先级，默认为0，越重要友好值越小。
    • 友好值↓，优先级↑。 友好值↑，优先级↓。
    • 友好值每小一级，也就是优先级↑↑，CPU usage多10%，vruntime增加得越小，相对往树的左边移动，从而获得更多时间片。