操作系统-进程管理

1. 进程与线程

1.1 进程

进程是资源分配的基本单位

进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态

1.2 线程

线程是独立调度的基本单位

一个进程中可以有多个线程，它们共享进程资源

1.3 进程与线程区别

	进程	线程
拥有资源	进程是资源分配的基本单位	线程不拥有资源，线程可以访问隶属进程的资源
调度	从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换	线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，
系统开销	在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，开销大	线程切换时只需保存和设置少量寄存器内容，开销很小
通信方面	进程通信需要借助 IPC	线程间可以通过直接读写同一进程中的数据进行通信

2. 进程状态切换

3. 进程调度算法

3.1 先来先服务FCFS

非抢占式的调度算法，按照请求的顺序进行调度。

有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

3.2 短作业优先SJF

非抢占式的调度算法，按估计运行时间最短的顺序进行调度。

长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

3.3 最短剩余时间优先SRTN

最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。 当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。

3.4 时间片轮转

将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。

3.5 优先级调度

为每个进程分配一个优先级，按优先级进行调度。

为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

3.6 多级反馈队列

一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。

多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。

每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

4. 进程同步

4.1 同步与互斥

• 同步：多个进程因为合作产生的直接制约关系，使得进程有一定的先后执行关系。
• 互斥：多个进程在同一时刻只有一个进程能进入临界区（对临界资源进行访问的代码称为临界区）。

4.2 哲学家就餐问题

五个哲学家围着一张圆桌，每个哲学家面前放着食物。哲学家的生活有两种交替活动：吃饭以及思考。当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，并且一次只能拿起一根筷子。

下面是一种错误的解法，如果所有哲学家同时拿起左手边的筷子，那么所有哲学家都在等待其它哲学家吃完并释放自己手中的筷子，导致死锁。

• 方案1：让偶数编号的哲学家「先拿左边的叉子后拿右边的叉子」，奇数编号的哲学家「先拿右边的叉子后拿左边的叉子」
• 方案2：用一个数组 state 来记录每一位哲学家的三个状态，分别是在进餐状态、思考状态、饥饿状态（正在试图拿叉子）。那么，一个哲学家只有在两个邻居都没有进餐时，才可以进入进餐状态

5. 进程通信

5.1 管道通信

• 匿名管道：对于匿名管道，它的通信范围是存在父子关系的进程，因为管道没有实体，也就是没有管道文件，只能通过 fork 来复制父进程 fd 文件描述符，来达到通信的目的
• 命名管道：对于命名管道，它可以在不相关的进程间也能相互通信。因为命令管道提前创建了一个类型为管道的设备文件，在进程里只要使用这个设备文件，就可以相互通信

5.2 消息队列

• a 进程要给 b 进程发消息，只需要把消息挂在消息队列（可以是中介邮局（间接），也可以是进程自己的信箱（直接））里就行了，b 进程需要的时候再去取消息队列里的消息。
• 消息队列可以独立于读写进程存在，就算进程终止时，消息队列的内容也不会被删除。
• 读进程可以根据消息类型有选择地接收消息，而不像 FIFO 那样只能默认接收。

如果进程发送的数据较大，并且两个进程通信非常频繁的话，消息队列模型就不太合适了，因为如果发送的数据很大的话，意味着**发送消息（拷贝）**这个过程就需要很多时间来读写内存。

5.3 共享内存

• 共享内存的方式就可以解决拷贝耗时很长的问题了。
• 共享内存是最快的一种进程通信的方式，因为进程是直接对内存进行存取的。因为可以多个进程对共享内存同时操作，所以对共享空间的访问必须要求进程对共享内存的访问是互斥的。所以我们经常把信号量和共享内存一起使用来实现进程通信。

5.4 信号量

• 共享内存最大的问题就是多进程竞争内存的问题，就像平时所说的线程安全的问题，那么就需要靠信号量来保证进程间的操作的同步与互斥。
• 信号量其实就是个计数器，例如信号量的初始值是 1，然后 a 进程访问临界资源的时候，把信号量设置为 0，然后进程 b 也要访问临界资源的时候，发现信号量是 0，就知道已有进程在访问临界资源了，这时进程 b 就访问不了了，所以说信号量也是进程间的一种通信方式。

5.5 套接字

套接字可以实现两个不同的机器之间的进程通信