操作系统——进程管理

进程的基本概念

程序的顺序执行及其特征

• 程序：一个在时间上按严格次序、顺序执行的操作序列
• 程序的顺序执行：一个具有独立功能的程序独占处理剂，直到得到最终结果
  特征：
  顺序性：一个程序的各个部分的执行，严格地按照某种先后次序执行；
  封闭性：程序在封闭的环境下运行，即程序运行时独占全部系统资源；
  可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都将获得相同的结果。

前趋图（DAG）

前趋图是有向无循环图

程序的并发执行及其特征

• 不可再现性：由于程序的并发执行，打破了由另一程序独占系统
  资源的封闭性，因而破坏了可再现性。
• 间断性：程序并发执行时，由于它们共享资源或程序之间相互合作完
  成一项共同任务，因而使程序之间相互制约。
• 通信性：对于相互合作的程序，为了更有效地协调运行，相互之间进
  行通信。
• 独立性：并发程序在运行过程中，既然是作为一个独立的运行实体，
  它也必然具有作为一个单位去获得资源的独立性。
• 程序和进程的区别：
  进程就是一个活跃着的程序（动态的）,即:已经被放入了系统调度队列当中了,占有一定的系统资源的程序.

进程的特征与状态

• 结构性：程序块、数据块、进程控制块（PCB）
  进程实体=程序段+相关的数据段+PCB
  进程创建和撤销都是创建和撤销的 PCB
• 动态性：进程是程序在数据集合上的一次执行过程，有生命周期：由创建而产生、由调度而执行、由事件而等待、由撤销而消亡。
• 并发性：多个进程实体同存于内存中，能在一段时间内同时运行。是进程的重 要特征。
• 独立性：进程是系统中资源分配、保护和调度的基本单位

• 异步性：进程按各自独立的，不可预知的速度向前推进

• 进程的状态转换
  三态转换图
  
  挂起：进程被交换到外存，状态变为挂起状态
  进程进入挂起状态是由于操作系统、父进程或进程本身阻止它的运行。
  结束进程挂起状态的命令只能通过操作系统或父进程发出。
  

进程控制块（PCB）

• 系统为了管理进程设置的一个专门的数据结构，存放了用于描述该进程情况和控制进程运行所需的全部信息。
• 系统利用 PCB 来控制和管理进程，所以 PCB 是系统感知进程存在的唯一标志
• 进程与 PCB 是一一对应的
• 作用：使一个在多道程序环境下不能独立运行的程序（含数据），成为一个独立运行的基本单位。

---

进程同步

基本概念

• 进程互斥：指在多道程序环境下，每次只允许一个进程对临界资源进行访问。
• 进程同步：指多个相关进程在执行次序上的协调
• 临界资源:一次仅供一个进程使用的资源。
• 在进程中涉及到临界资源的程序段叫临界区
• 多个进程的临界区称为相关临界区
• 进程的同步机制 ── 信号量及 P.V 操作（解决进程同步,互斥问题）

进程间的两种制约关系

• 直接作用(相互合作）：
  进程间的相互联系是有意识的安排的，直接作用只发生在相交进程间
  进程的同步
  

• 间接作用（资源共享）：
  进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间
  进程的互斥
  由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥。

• 同步是一种更为复杂的互斥，而互斥是一种特殊的同步

生产者-消费者问题

• P、V 信号量

  P 和 V 是来源于两个荷兰语词汇，P() —prolaag （荷兰语，尝试减少的意思），V() —verhoog（荷兰语，增加的意思）

• 信号量（Semaphore）是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 P 和 V 操作。
  down : 如果信号量大于 0 ，执行 -1 操作；如果信号量等于 0，进程睡眠，等待信号量大于 0；（阻塞）
  up ：对信号量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作。（唤醒）
• 如果信号量的取值只能为 0 或者 1，那么就成为了 互斥量（Mutex） ，0 表示临界区已经加锁，1 表示临界区解锁。

#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void producer() {
    while(TRUE){
        int item = produce_item(); // 生产一个产品
        // down(&empty) 和 down(&mutex) 不能交换位置，否则造成死锁
        down(&empty); // 记录空缓冲区的数量，这里减少一个产品空间
        down(&mutex); // 互斥锁
        insert_item(item);
        up(&mutex); // 互斥锁
        up(&full); // 记录满缓冲区的数量，这里增加一个产品
    }
}

void consumer() {
    while(TRUE){
        down(&full); // 记录满缓冲区的数量，减少一个产品
        down(&mutex); // 互斥锁
        int item = remove_item();
        up(&mutex); // 互斥锁
        up(&empty); // 记录空缓冲区的数量，这里增加一个产品空间
        consume_item(item);
    }
}

注意，不能先对缓冲区进行加锁，再测试信号量。也就是说，不能先执行 down(mutex) 再执行 down(empty)。如果这么做了，那么可能会出现这种情况：生产者对缓冲区加锁后，执行 down(empty) 操作，发现 empty = 0，此时生产者睡眠。消费者不能进入临界区，因为生产者对缓冲区加锁了，也就无法执行 up(empty) 操作，empty 永远都为 0，那么生产者和消费者就会一直等待下去，造成死锁。

哲学家进餐问题

如果所有哲学家同时拿起左手边的筷子，那么就无法拿起右手边的筷子，造成死锁。
有多种办法可以解决这个问题
1、只有哲学家两只手的筷子都可以用时，才允许他吃饭
2、奇数号先取左手边的叉子，偶数号先取右手边的筷子；

管程机制

• P.V 操作的优缺点：
  简单，而且表达能力强（用 P.V 操作可解决任何同步和互斥问题），但 P, V 操作代码均由用户编写，计算机系统无法有效地控制和管理这些 P，V 操作。分散在各进程中的临界段没有集中加以管理不够安全；P.V 操作使用不当会出现死锁；且这种错误只有在特定顺序下才出现；遇到复杂同步和互斥问题时实现复杂。
  总之，信号量(P,V)不是最安全的进程通讯手段
  管程的基本原理
  把分散在各进程中的临界区集中起来管理，并把共享资源用数据结构抽象地表示出来,代表共享资源的数据结构及并发进程在其上执行的一组过程就构成管程。
• 管程的属性
  模块化：管程是一个基本程序单位
  抽象数据类型：管程中不仅有数据，而且有对数据的操作
  信息掩蔽:管程的数据结构只能供过程调用，过程内的过程
  被管程外的进程调用，数据结构和过程对外不可见
• 通常系统为每个共享资源设置一个管程

---

进程通信

通信机制

每 个进程各自有不同的用户地址空间，任何一个进程的全局变量在另一个进程中都看不到，所以进程之间要交换数据必须通过内核，在内核中开辟一块缓冲区，进程 1 把数据从用户空间拷到内核缓冲区，进程 2 再从内核缓冲区把数据读走，内核提供的这种机制称为进程间通信（IPC，InterProcess ommunication）

高级通信机制分类

• 共享存储器系统
• 管道通信
  管道(pipeline)是连接读写进程的一个特殊文件，允许进程按先进先出方式传送数据,也能使进程同步执行操作。
  发送进程以字符流形式把大量数据送入管道，接收进程从管道中接收数据，所以叫管道通信。
  管道的实质是一个共享文件，基本上可借助于文件系统的机制实现，包括（管道）文件的创建、打开、关闭和读写。
• 消息传递通信系统

---

线程及其实现

进程的“独立分配资源”和“被调度分派执行”的功能分离

• 独立分配资源：由进程完成，作为系统资源分配和保护的独立单位，无须频繁的切换
• 被调度分派执行：交给线程的实体来完成，线程作为系统系统调度和分派的基本单位，会被频繁地调度和切换。