进程

基本概念

进程：为了揭示多道程序、分时系统引发的动态特性（执行-暂停 -执行），而引入了进程。定义可参看内存管理。
并发：有两个活动a1和a2，如果在某一时刻t，无论它们是在同一处理机上还是在不同的处理机上执行，只要都处在各自的起点和终点之间的某一处，则称a1和a2是并发执行的。
并行：两个程序在同一时间度量下同时运行在不同的处理机上，则称这两个程序是并行执行的
竞争：多个进程在读写一个共享数据时结果依赖于它们执行的相对时间
竞争条件：多个进程并发访问和操作同一数据且执行结果与访问的特定顺序有关，称为竞争（发生）条件。
Bernstein条件：满足该条件，则程序并发执行结果可再现。该条件可简单理解为两个程序只可以同时读。

响应时间：进程到达直至进程结束之间的时间。响应比=响应时间/运行时间

进程与程序

  • 进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件，静态和可以复制。
  • 进程是暂时的，程序是永久的：进程是一个状态变化的过程，程序可长久保存。
  • 进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。

原语

由若干条指令所组成的指令序列，来实现某个特定的操作功能
原语是操作系统核心组成部分，必须在管态（内核态）下执行，且常驻内存。其指令序列的执行是连续的、不可分割的。

创建原语

  • fork
    创建子进程。一次调用有两个返回值。
    在fork函数执行完毕后，子进程中，fork函数返回0，在父进程中，fork返回新创建子进程的进程ID，如果出现错误则返回负值。
  • exec
    程序替换。
    当子进程调用exec函数来运行另一个程序时，这个进程的地址空间代码和数据都被新程序的代码和数据刷新替换。

    撤销原语

  • kill
    释放资源、撤销子进程、重新调度

    进程状态

就绪状态：进程已获得除处理机外的所需资源，只要分配CPU就可执行。

执行状态：占用处理机资源；处于此状态的进程的数目小于等于CPU的数目。在没有其他进程可以执行时（如所有进程都在阻塞状态），通常会自动执行系统的idle进程（相当于空操作）。

阻塞状态：正在执行的进程，由于发生某种事件而暂时无法执行，便放弃处理机处于暂停状态。

进程控制块

进程控制的主要任务是创建和撤销进程，以及实现进程的状态转换。

系统为每个进程定义了一个数据结构：进程控制块PCB。在创建进程时，建立PCB，伴随进程运行的全过程，直到进程撤消而撤消。

作用

进程的创建与撤销。是进程的唯一标志。

内容

  • 进程标识符：每个进程都必须有一个唯一的标识符。Linux系统中是一个整型数。 在进程创建时由系统赋予。
  • 现场保护区：进程阻塞释放CPU时，要将CPU的各种状态信息保存
  • 互斥与同步机制：用于实现进程间互斥、同步和通信所需的信号量等
  • 程序和数据地址，当前状态，优先级，资源清单，链接字（指出该进程所在队列中下一个进程PCB的首地址）

组织方式

  • 线性表

不论进程的状态如何，将所有的PCB连续地存放在内存的系统区

  • 索引方式

系统按照进程的状态分别建立就绪索引表、 阻塞索引表等

  • 链接表方式

系统按照进程的状态将进程的 PCB 组成队列，从而形成就绪队列、阻塞队列、运行队列等。

上下文切换

进程上下文，即一个进程在执行的时候，CPU的所有寄存器中的值、进程的状态以及堆栈上的内容。

当内核需要切换到另一个进程时，它需要保存当前进程的所有状态，即进程上下文，以便再次执行该进程时，能够恢复切换时的状态，继续执行。这些内容被保存在任务自己的堆栈中, 入栈工作完成后就把下一个将要运行的任务的当前状况从该任务的栈中重新装入CPU寄存器, 并跳转到下一个进程被中断时的PC，开始下一个任务的运行, 这一过程就是context switch。

而陷入/退出内核（模态切换 Mode Switch），是由中断、异常、Trap指令（系统调用）引起。系统调用涉及到进程从用户态到内核态的切换（mode switch），此时涉及到的切换主要是寄存器上下文的切换，和通常所说的进程上下文切换（Process Context Switch）不同，mode switch 的消耗相对要小很多。

注：处理器总处于以下状态中的一种：

  1. 内核态，运行于进程上下文，内核代表进程运行于内核空间；
  2. 内核态，运行于中断上下文，内核代表硬件运行于内核空间；
  3. 用户态，运行于用户空间。

线程

线程（thread）是操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每条线程并行执行不同的任务。
现代操作系统将资源拥有者称为进程，将可执行单元称为线程。

进程 & 线程

  • 线程间共享相同的地址空间，方便共享资源（也有栈、PC 等私有资源）。而进程地址空间相互独立，同步需要借助消息通信机制。
  • 进程切换涉及虚拟地址空间的切换而线程不会，有效减少切换造成的开销。
  • 进程创建/撤销时需要分配/回收大量资源，线程更轻量，开销更少
  • 多线程并发度更高

    线程实现方式

    用户级线程

User level threads(ULT)，线程在用户空间，是通过 library 模拟的 thread，不需要或仅需要极少的 kernel 支持。由用户程序自行调用、调度和维护。

典型的有：

  • POSIX Pthreads
    用于线程创建和同步的 POSIX 标准API , 可在用户级或者内核级实现。该 API 规定了线程库的行为，但不限定实现方法，在类 UNIX 系统（Solaris, Linux, Mac OS X）中很常见。
  • Java Threads

优点

  • 线程的创建、撤消和调度不需要OS内核的支持，是在语言或用户库这一级处理，容易进行优化
  • 可运行在任何操作系统上，只需要线程库的支持

    缺点

  • 用户级线程执行系统调用指令时将导致其所属进程被中断，内核会因此而阻塞所有相关的线程。
  • 内核只能将处理器分配给进程，即使有多个处理器，也无法实现一个进程中的多个线程的并行执行。

    内核级线程

    Kernel level threads (KLT)，kernel 有好几个分身, 一个分身可以处理一件事。支持内核线程的操作系统内核称作多线程内核

    优点

  • CPU调度以线程为单位，由OS的线程调度程序负责线程的调度。内核可以在多个处理器上调度一个进程的多个线程实现同步并行执行
  • 系统调用导致的阻塞只发生在线程级别
  • 内核中的一些处理可以通过多线程实现

    缺点

  • 一个进程中的线程切换需要内核参与，线程的切换涉及到两个模式的切换（进程-进程、线程-线程）
  • 效率降低

    混合的线程实现方式

    线程在用户空间创建和管理，实现从用户空间线程到内核空间线程的映射

    线程模型

    实现用户级线程和内核级线程的连接方式
  • Many-to-One Model
    多个用户级线程映射到一个内核级线程，线程管理在用户空间完成。
  • One-to-one Model
    每个用户级线程映射到一个内核级线程。并发能力较强，但对应用程序性能影响大
  • Many-to-Many Model
    n 个用户级线程映射到 m 个内核级线程上（m $\le$ n）

    同步与互斥

    基本概念

临界资源：一次仅允许一个进程访问的资源

临界区：每个进程中访问临界资源的那段代码称为临界区

进程互斥：两个或两个以上的进程，不能同时进入关于同一组共享资源的临界区，否则可能发生与时间有关的错误

进程同步：系统中各进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性的过程。让本来异步并发的进程相互配合，有序推进。

临界区管理

空闲让进：临界资源处于空闲状态，允许进程进入临界区。临界区内仅有一个进程运行。
忙则等待：临界区有正在执行的进程，所有其他进程则不可以进入临界区。
有限等待：对要求访问临界区的进程，应保证在有限时间内进入自己的临界区，避免死等。
让权等待：当进程（长时间）不能进入自己的临界区时，应立即释放处理机，尽量避免忙等。

基于信号量的同步与互斥

信号量

一个确定的二元组(s, q)，其中s是一个具有非负初值的整型变量，q是一个初始状态为空的队列程序。对其访问都是原子操作，且只允许对它进行P(信号变量)和V(信号变量)操作。它用来累计唤醒次数，由 Dijkstra 提出。

semWait 操作（P操作）：

  • 使信号量减1。若值为负，则执行 semWait 的进程被阻塞。否则进程继续执行。
  • 有进程被阻塞时就会进入 q 队列

semSignal操作（V操作）

  • 使信号量加1。若值小于或等于零，则被semWait操作阻塞的进程被解除阻塞。
    PV 操作简单但不安全，使用不当会出现死锁。

分类

  • 二元信号量：取值仅为“0”或“1”，主要用作实现互斥。
  • 一般信号量：初值为可用物理资源的总数，用于进程间的协作同步问题。

在并发中的应用

互斥

常使用二元信号量的PV操作实现两个进程的互斥。
信号量初值为 1，⼀个进程在进⼊临界区之前执⾏semWait操作，退出临界区后再执⾏⼀个semSignal操作。

同步

想要先执行code1 & code2，再执行code 4.

1
2
3
4
5
6
7
8
9
10
11
12
semaphore S = 0; // 同步信号量初值为 0
p1() {
    code 1;
    code 2;
    V(S);
    code 3;
}

p2() {
    P(S);
    code 4;
}

前驱关系

在”前操作”之后对相应同步变量执行 V 操作

在”后操作”之前对相应的同步变量执行 P 操作

例如：S1->S2, S1->S3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
semaphore a = 0, b = 0;
p1() {
	...
	S1;
	V(a);
	V(b);
}
p2() {
	...
	P(a);
	S2;
}
p3() {
	...
	P(b);
	S3;
}

有限并发

指有n（1≤n≤c，c是⼀个常量）个进程并发执⾏⼀个函数或者⼀个资源。⼀个初始值为c 的信号量可以实现这种并发。

信号量集机制

信号量集是指同时需要多个资源时的信号量操作

AND 型

将进程需要的所有共享资源一次全部分配给它；待该进程使用完后再一起释放。

一般型

进程对信号量$S_i$的测试值为$t_i$（用于信号量的判断，即$S_i >= t_i$，资源数量低于ti时，便不予分配），占用值为 $d_i$（用于信 号量的增减，即$S_i = S_i - d_i$ 和 $S_i = S_i + d_i$ ）

基于管程的同步与互斥

管程

信号量机制存在的问题：编写困难、易出错

管程是一种高级同步机制，由四部分组成：1. 管程的名称；2. 局部于管程内部的共享数据结构（变量）说明 3. 对该数据结构进行操作的一组互斥执行的过程；4. 对局部于管程内部的共享数据设置初始值的语句

这么看，管程其实很像

条件变量：为了区别等待的不同原因，管程引入了条件变量。不同的条件变量，对应不同原因的进程阻塞等待队列，初始时为空。若条件变量名为X，则调用同步原语的形式为wait(X)和signal(X)。

与信号量区别：

  • 条件变量的值不可增减，P-V操作的信号量值可增减
  • wait操作一定会阻塞当前进程；但P操作只有当信号量的值小于0时才会阻塞。
  • 如果没有等待的进程，signal将丢失；而V操作增加了信号量的值，不会丢失。
  • 访问条件变量必须拥有管程的锁

    Hoare 管程

入口等待队列：因为管程是互斥进入的，所以当一个进程试图进入一个已被占用的管程时它应当在管程的入口处等待，因而在管程的入口处应当有一个进程等待队列，称作入口等待队列。
紧急等待队列：如果进程Ｐ唤醒进程Ｑ，则Ｐ等待Ｑ继续；Ｑ执行完又唤醒进程Ｒ，则Ｑ等待Ｒ继续，… 如此，在管程内部，由于执行唤醒操作，可能会出现多个等待进程（已被唤醒，但由于管程的互斥进入而等待），这个管程内部的等待队列被称为紧急等待队列，其优先级高于入口等待队列。

同步原语

  • x.wait()
    如果紧急等待队列非空，则唤醒第一个等待者；否则释放管程的使用权，执行此操作的进程排入x队列尾部（紧急等待队列与x队列的关系：紧急等待队列是由于管程的互斥进入而等待的队列，而x队列是因资源被占用而等待的队列）
  • x.signal()
    如果x队列为空，则相当于空操作，执行此操作的进程继续；否则唤醒第一个等待者，执行x.signal()操作的进程排入紧急等待队列的

    信号量

  • mutex 用与互斥
    初值为 1，进程退出管程时应执行V(mutex)开放管程，以便让其他调用者进入。为了使进程在等待资源期间，其他进程能进入管程， 故在wait操作中也必须执行V(mutex)
    1
    2
    3
    4
    5
    6
    7
    8
    P(mutex);        // 管程入口
    …
    Body of F
    …
    If(next_count > 0)
    V(next);
    Else
    V(mutex);        // 管程出口
  • next 初值为 0
    凡发出si gnal操作的进程应该用P(next)挂起自己，直到被释放进程退出管程或产生其他等待条件。
    进程在退出管程的过程前，须检查是否有别的进程在信号量next上等待，若有，则用V(next)唤醒它。next-count（初值为0），用来记录在next上等待的进程个数
  • x-sem 初值为 0
    申请资源得不到满足时，执行P(x-sem)挂起。由于释放资源时，需要知道是否有别的进程在等待资源，用计数器x-count（初值
    为0）记录等待资源的进程数。
    执行signal操作时，应让等待资源的诸进程中的某个进程立即恢复运行，而不让其他进程抢先进入管程，这可以用V(x-se m)来实现

    进程间通信 IPC

低级通信：只能传递状态和整数值（控制信息），包括进程互斥和同步所采用的信号量和管程机制。
高级通信：适用于分布式系统，基于共享内存的多处理机系统，单处理机系统，能够传送任意数量的数据，可以解决进程的同步问题和通信问题，主要包括三类：管道、共享内存、消息系统。

Pipe

  • 数据只能向一个方向流动；写入的内容每次都添加在管道缓冲区的末尾，并且每次都是从缓冲区的头部读出数据。需要双方通信时，需要建立起两个管道；
  • 只能用于父子进程或者兄弟进程之间（具有亲缘关系的进程）
  • 单独构成一种独立的文件系统：管道对于管道两端的进程而言，就是一个文件，但它不是普通的文件，不属于某种文件系统，而是单独构成一种文件系统，并且只存在于内存中。

    Named Pipe / FIFO

  • 克服了”只能用于具有亲缘关系的进程间通信”的限制
  • 它提供一个路径名与之关联，以FIFO的文件形式存在于文件系统中。这样，只要可以访问该路径，就能够彼此通过FIFO 相互通信

    共享内存

    共享内存是指：同一块物理内存被映射到进程A、B各自的进程地址空间。
  • 共享内存是最有用的进程间通信方式，也是最快的IPC形式（因为它避免了其它形式的IPC必须执行的开销巨大的缓冲复制）。
    • 当多个进程共享同一块内存区域，需要同步机制约束（互斥锁和信号量都可以）。

      消息传递

      通过两个通信原语（OS系统调用）:
  • send (destination, &message)
  • receive(source, &message)

    经典进程互斥与同步问题

    生产者-消费者问题

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区取出一个产品并使用。

producer :

1
2
3
4
5
6
7
8
while(1) {
	生产一个产品
    P(empty);
    P(mutex);
    one >> buffer
    V(mutex);
    V(full);
}

consumer : 

1
2
3
4
5
6
7
8
while(1) {
    P(full);
    P(mutex);
    one << buffer
    V(mutex);
    V(empty);
    使用产品;
}

P 操作的互换可能会导致死锁（缓冲区无产品，且先执行 consumer；缓冲区满，producer阻塞）

多生产者-多消费者

不同类别的生产者生产的物品不同。

1
2
3
4
semaphore mutex = 1;	// 实现互斥访问盘子（缓冲区）
semaphore apple = 0;	// 盘子中有几个苹果
semaphore orange = 0;	// 盘子中有几个橘子
semaphore plate = 1;	// 盘子中还可以放多少水果

读者-写者问题

对共享资源的读写操作，任一时刻“写者 ”最多只允许一个，而“读者”则允许多个。即”读写互斥”和”写写互斥”。

为了不令读进程之间也互斥，而读进 程与写进程又必须互斥访问，那么我们可以让第一个访问文件的读进程“加锁”，让最后一个访问完文件的读进程“解锁”。可以设置一个整数量 count 来记录当前有几个读进程在访问文件。

读进程优先：

读写公平：

哲学家进餐问题

5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。如果筷子已在其他人手上，则需要等待。

思路

  • （破除资源互斥） 至多只允许四个哲学家同时（尝试）进餐,以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。设置信号量room=4。
  • （破除资源互斥）对筷子进行编号，每个哲学家按编号从低到高拿起筷子。或者对哲学家编号，奇数号哲学家先拿左，再拿右；偶数号相反。
  • （破除保持等待）同时拿起两根筷子，否则不拿起。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
semaphore chopstick[]={1,1,1,1};
semaphore mutex=1;//互斥地取筷子  
Pi(){
	while(1){
    	P(mutex);  
        P(chopstick[i]);  
        P(chopstick[(i+1)%5]);//拿右  
        V(mutex);  
        	吃饭  
        V(chopstick [i]);  
        V(chopstick[(i+1)%5]);//放右  
        思考
    }
}