2.1 前趋图和程序执行

前趋图

前趋图（Procedence Graph）是一个有向无循环图DAG（Directed Acyclic Graph）。

• 结点：语句、程序段或进程。
• 有向边→：前趋关系，执行顺序。Pi→Pj或(Pi,Pj)。
• 初始节点
• 终止节点
• 重量：程序量或执行时间。

程序的顺序执行

可以一个程序分成若干个程序段，各程序段之间，必须按照某种先后次序顺序执行，仅当前一程序执行完后，才运行后一段程序。

程序的顺序执行时的特征

顺序性：一个程序的各个部分的执行，严格地按照某种先后次序执行。

封闭性：程序在封闭的环境下运行，即程序运行时独占全部系统资源。

可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都将获得相同的结果。

程序的并发执行

并发执行是指两个程序执行时间上是重叠的。

凡是能由一组并发程序完成的任务，都能由相应的单个程序完成。

程序的并发执行时的特征

间断性：并发执行的程序之间相互制约导致“执行——暂停——执行”这种间断性的活动规律。

失去封闭性：多个并发执行的程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，指示程序的运行失去了封闭性。

不可再现性：由于失去了封闭性，也将导致失去了可再现性。

2.2 进程的描述 ★

进程的定义和特征

进程的定义

进程是程序的一次执行。

进程是一个程序及其数据在处理机上顺序执行时所发生的活动。

进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调配的一个独立单位。

进程实体

进程实体（进程映像）：即进程，由程序段、相关的数据段和进程控制块PCB(Process Control Block)组成，所谓创建和撤销进程实际是对其中的PCB的创建和撤销。

进程是进程实体的运行过程， 是系统进行资源分配和调配的一个独立单位。

进程的特征

1）结构特征：程序段、数据段、PCB。

2）动态性：进程是程序的一次运行过程，有生命周期。

3）并发性

4）独立性：进程是一个能独立运行的基本单位，同时也是系统分配资源和调度的独立单位。

5）异步性：进程按各自独立的、 不可预知的速度向前推进。

进程与程序的关系

进程的基本状态及转换

进程的三种基本状态

就绪状态（Ready）：得到了除CPU以外的所有必要资源。

执行状态（Running）：已获得处理机，程序正在被执行。

阻塞状态（Blocked）：因等待某事件发生而暂时无法继续执行，从而放弃处理机，使程序执行处于暂停状态。（阻塞原因：I/O请求、申请缓冲区失败等）

三种基本状态的转换 ★

注意转换的条件。

创建状态和终止状态

创建状态：进程已拥有了自己的PCB，但进程自身还未进入主存，即创建工作尚未完成，进程还不能被调度运行，其所处的状态。

终止状态：当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入终止状态。

进程的挂起 Suspend

把一个进程挂起使之处于静止状态，以便研究它的执行情况或对它进行修改。暂停执行（执行状态下挂起），暂不接受调度（就绪状态下挂起）。

原因：是基于系统和用户的需求（终端用户请求、父进程请求、负荷调节的需要、操作系统的需要）。

进程的激活 Active

先将进程从外存调入内存，检查进程现行状态，由静止状态转变成活动状态。

进程状态的转换

活动就绪→静止就绪 静止就绪→活动就绪 活动阻塞→静止阻塞 静止阻塞→活动阻塞 静止阻塞→静止就绪

进程控制块PCB ★

进程控制块的概念

进程控制块是进程实体的重要组成部分，是操作系统中最重要的记录型数据，在进程控制块PCB（Program Contral Block）中记录了操作系统所需要的、用于描述进程情况及控制进程运行所需要的全部信息。

进程控制块的作用

通过PCB，使得原来不能独立运行的程序（数据），成为一个可以独立运行的基本单位，一个能够并发执行的进程。

进程控制块是进程存在的唯一标志。

进程控制块中的信息 ★★★

(1) 进程标识符：唯一地标识一个进程。

• 内部标识符。在所有的操作系统中，都为每一个进程赋予了一个惟一的数字标识符，它通常是一个进程的序号。
• 外部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用户(进程)在访问该进程时使用。
• 为了描述进程的家族关系，还应设置父进程标识及子进程标识。
• 还可设置用户标识，以指示拥有该进程的用户。

(2) 处理机状态：保留进程存放在处理器中的各种信息，主要由处理器内的各个寄存器的内容组成。

(3) 进程调度信息：进程状态、进程优先级、阻塞原因等等。

(4) 进程控制信息：程序和数据的地址、进程同步和通信机制、资源清单、链接指针。

进程控制块的三种组织方式

①线性方式：将系统中所有的PCB都组织在一张线性表中，查表

②链接方式：把具有相同状态进程的PCB分别通过PCB中的链接字链接成一个队列

③索引方式：根据所有进程状态的不同，建立索引表

2.3 进程控制

操作系统内核

进程控制是对系统中所有进程从产生、存在到消亡的全过程实行有效的管理和控制。

进程控制一般是由操作系统的内核来实现，内核在执行操作时，往往是通过执行各种原语操作来实现的。

内核

加在硬件上的第一层软件，通过执行各种原语操作来实现各种控制和管理功能，具有创建、撤消、进程通信、资源管理的功能。

系统态和用户态

为了防止OS本身及关键数据（如PCB等）遭受应用程序有意或无意的破坏，通常也将处理机的执行状态分成系统态和用户态两种：

系统态：又称为管态，也称为核心态。它具有较高的特权，能执行一切指令，访问所有寄存器和存储区，传统的OS都在系统态运行。

用户态：又称为目态。它是具有较低特权的执行状态，仅能执行规定的指令，访问指定的寄存器和存储器。

一般情况下，应用程序只能在用户态运行，不能去执行OS指令及访问OS区域，这样可以防止应用程序对OS的破坏。

内核的基本功能

支撑功能：中断处理、时钟管理、原语操作。

资源管理功能：进程管理、存贮管理、设备管理。

原语

是由若干条机器指令所构成，用以完成特定功能的一段程序 。原语在执行期间是不可分割的或不可中断的。

原语是”原子操作“（一个操作中的所有动作要么全做，要么全不做）。

例如：创建原语、撤消原语、阻塞原语、唤醒原语。

进程的创建

进程之间的关系

父、子进程与祖先进程（PCB中标识、继承/归还资源、“父”创建“子”、父撤子消）

引起进程创建的事件

用户登录：在分时系统中，用户在终端键入登录命令。

作业调度：在批处理系统中，当作业调度程序按一定的算法调度到某作业。

提供服务：用户程序提出某种请求后，系统将专门创建一个进程来提供用户所需要的服务。

应用请求：它自己创建一个新进程，以便使新进程以并发运行方式完成特定任务。

进程创建的过程 ★★

进程创建原语Create()

1. 申请一个空白PCB
2. 为新进程分配资源
3. 初始化PCB
4. 新进程加入到就绪队列

进程的终止

引起进程终止的事件

进程正常结束。

在进程运行期间，由于出现某些错误和故障而使得进程被迫中止。

进程应外界的请求而中止运行。

进程终止的过程

进程终止原语Destroy()

1. 根据被终止进程的标识符，从PCB集合中检索该进程的PCB，读出进程状态。
2. 若该进程处于执行状态，则立即终止该进程的执行。
3. 若该进程有子孙进程，还要将其子孙进程终止。
4. 将该进程所占用的资源回收，归还给其父进程或操作系统。
5. 将被终止进程的PCB从所在队列中移出，并撤消该进程的PCB。

进程的阻塞与唤醒 ▽

引起进程阻塞的事件

请求系统服务，要求不能立即满足

启动某种操作，必须在操作完成后才能继续

合作进程提供的新数据尚未到达

无新工作可做

进程阻塞的过程

进程阻塞原语Block()

1. 立即停止执行
2. 修改进程控制块中的相关信息
3. 把进程控制块插入到阻塞队列
4. 转调度程序重新调度

引起进程唤醒的事件

请求系统服务得到满足

启动某种操作完成

新数据已经到达

有新工作可做

进程唤醒的过程

进程唤醒原语Wakeup()

1. 从阻塞队列中找到该进程
2. 修改该进程控制块的相关内容
3. 把进程控制块插入到就绪队列

进程的挂起与激活 ▽

进程挂起的方式

把发出本原语的进程自身挂起

挂起指定进程名的进程

把某进程及其全部或部分子孙一起挂起

进程挂起的过程

进程挂起原语Suspend()

1. 检查被挂进程的状态，改为相应的挂起状态
2. 把进程的PCB复制到指定的区域
3. 转向调度程序重新调度

进程激活的过程

进程激活原语Active()：先将进程从外存调入内存，检查该进程的现行状态，改为相应的活动状态。根据优先级可能引起调度。

2.4 进程同步 ★

进程同步的基本概念

进程同步的主要任务：使并发执行的进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。

并发进程间的相互制约关系

① 间接相互制约关系：进程间对类临界资源的间接相互制约关系，为保证进程有序运行，此类资源必须由系统实施统一分配（即用户使用前，应先提出申请）。

② 直接相互制约关系：源于某些进程（隶属于同一应用程序）之间为完成同一项任务而相互合作（相互间唤醒激活）。

临界资源与临界区 ★

临界资源(Critical Resouce)：一次仅允许一个进程使用的资源，如打印机、磁带机、变量等。进程间互斥来实现对临界资源的共享。

临界区(Critical Section)：临界区是每个进程中访问临界资源的那段代码。若能保证诸进程互斥地进入自己的临界区，便可实现诸进程对临界资源的互斥访问。

可把一个访问临界资源的循环进程描述如下：

• 进入区(entry section)：进程进入临界区前，对临界资源进行检查是否正被访问。
• 临界区(critical section)：若未被访问，进入临界区对该资源访问，并设置“正被访问”的标志。
• 退出区(exit section)：临界区后面代码，将临界区“正被访问”的标志恢复为“未被访问”的标志。
• 剩余区(remainder section)：除进入区、临界区、退出区外的其余代码。

同步机制应遵循的原则 ★★★

目的：实现进程互斥地进入自己的临界区。

• 空闲让进：当无进程处于临界区时，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。
• 忙则等待：当已有进程进入临界区时，其它试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。
• 有限等待：对要求访问临界资源的进程，应保证有限时间内能进入自己的临界区，以免陷入“死等”状态。
• 让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。

信号量机制 ★

由Dijkstra提出的一种解决进程的同步与互斥的工具——信号量（semaphores）。

信号量：用于表示资源数目或请求使用某一资源的进程个数的整型量。

• S是与临界区内所使用的公用资源有关的信号量
• S≥0 可供并发进程使用的资源数
• S<0 正在等待使用临界区的进程数

① 整型信号量

S仅能通过两个标准的原子操作(Atomic Operation) wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V操作。

wait和signal操作可描述为：

wait(S){
	while(S≤0);   
	S--;
}

signal(S){   
	S++;
}

Wait和Signal是两个原子操作，在执行时是不可中断的。

整型信号量解决临界区调度的缺点：

• 对不能进入临界区的进程，采用忙式等待测试法，浪费CPU时间。因此未遵循“让权等待”的准则，使进程处于“忙等”状态。
• 在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。

② 记录型信号量 ★★

记录型信号量是由于采用了记录型的数据结构而得名的。在代表资源数目的整型变量value基础，增加一个进程链表指针list，用于链接所有等待进程。它包含两个数据项，可描述为：

struct semaphore{
	int value;
	struct process_control_block *L;
}

wait(S)和signal(S)操作可描述为：

wait(semaphore S){
	S.value--;
	if(S.value＜0)
		block(S.L);
}

signal(semaphore S){
	S.value++;
	if(S.value≤0)
		wakeup(S.L);
}

• 若信号量s为正值，则s就代表实际还可以使用的物理资源数。
• 若信号量s为负值，则其绝对值等于信号量链表中已阻塞进程的数目。
• 通常，wait(s)操作意味着请求一个资源，signal(s)操作意味着释放一个资源。在一定条件下，wait(s)操作代表挂起进程操作，而signal(s)操作代表唤醒被挂起进程的操作。
• 若加1后仍是S.value≤0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S.L链表中的第一个等待进程唤醒。如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。

记录型信号量是不存在“忙等”的进程同步机制。

③ AND型信号量

AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。

只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。

亦即，对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。

Swait(S1, S2, …, Sn){
	while(true){
    	if(Si≥1 && … && Sn≥1){
            for( i = 1;i<=n;i++) Si--;
            break;
        }
        else{
            将进程插入第i（Si<1）个等待队列。
            设置该进程的程序计数器到Swait操作的开始。
        }
	}
}

Ssignal(S1, S2, …, Sn){
	while(true){      
		for(i=1;i<=n;i++){
            Si++;
            将所有等待Si资源的进程移到就绪队列。 
		}
	}
}

④ 信号量集

问题：当一次需要N个某类临界资源时，要进行N次wait(S)操作。在有些情况下，当资源数量低于某一下限值，不予以分配。

为解决上述问题，信号量集在AND型信号量基础上，对进程所申请的所有资源以及每类资源不同的资源需求量，在一次P、V原语操作中完成申请或释放。

Swait(S, t, d)：S为信号量，t为下限值，d为需求值。

一般“信号量集”的几种特殊情况：

• Swait(S, d, d)。 此时在信号量集中只有一个信号量S， 但允许它每次申请d个资源，当现有资源数少于d时，不予分配。
• Swait(S, 1, 1)。 此时的信号量集已蜕化为一般的记录型信号量(S＞1时)或互斥信号量(S=1时)。
• Swait(S, 1, 0)。这是一种很特殊且很有用的信号量操作。当S≥1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。

信号量的应用

利用信号量实现进程互斥

利用信号量实现进程互斥的进程可描述如下：

semaphore mutex= 1;
process 1: {
    while(1){
        wait(mutex);
        critical section
        signal(mutex);
        remainder seetion
    };
}
process 2: {
    while(1){
        wait(mutex);
        critical section
        signal(mutex);
        remainder section
    };
}

利用信号量实现前驱关系

方法：若图中存在结点S1指向结点S2的有向边，表示进程P1中的程序段S1应该先执行，而进程P2中的程序段S2后执行。设置一个信号量s,初值为0，将Signal(s)放在S1后面，而在S2前面先执行Wait(s)。

• 进程P1的语句序列为：S1;Signal(s)
• 进程P2的语句序列为：Wait(s);S2

例：根据前趋图写出可并发执行的程序

P1(){S1; signal(a); signal(b); }
P2(){wait(a); S2; signal(c); signal(d); }
P3(){wait(b); S3; signal(e);}
P4(){wait(c); S4; signal(f); }
P5(){wait(d); S5; signal(g); }
P6(){wait(e); wait(f); wait(g); S6; }
main(){
	semaphore a,b,c,d,e,f,g;
	a.value=b.value=c.value=d.value=e.value=0;
	f.value=g.value=0;
	cobegin
		P1();P2();P3();P4();P5();P6();
	coend;
}

管程机制 ▽

为什么引入管程

把分散在各进程中的临界区集中起来进行管理；

防止进程有意或无意的违法同步操作；

便于用高级语言来书写程序，也便于程序正确性验证。

管程的定义

“一个管程定义了一个数据结构和能为并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据。”

• ①共享资源的数据结构；
• ②对该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成的一个操作系统的资源管理模块。

管程的组成

由四部分组成：

• ①管程的名称
• ②局部于管程的共享数据结构说明
• ③对该数据结构进行操作的一组过程
• ④对局部于管程的共享数据设置初始值的语句

管程被请求和释放资源的进程所调用。

说明：

• 局部变量只能被管程的过程访问；
• 进程通过调用管程的过程进入管程；
• 只能有一个进程在管程中执行。

条件变量 ○

条件变量：当调用管程过程的进程无法运行时，用于阻塞进程的一种信号量，用于区分等待原因。

2.5 经典进程同步问题 ★★★

使用信号量方法解决经典进程同步问题。

生产者-消费者问题 ★

问题描述：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中； 消费者进程可从一个缓冲区中取走产品去消费。

利用记录型信号量解决生产者-消费者问题

算法描述：

semaphore mutex=1,empty=n,full=0;   
item buffer[n];
int in=0,out=0;

说明：

• mutex为互斥信号量，实现对缓冲池的互斥访问，初值为1，取值为0、1。
• empty,full为资源信号量，为正时表示可用资源的数目；为负时，其绝对值为相应阻塞进程的数目。初值为n，0。可为负。

void proceducer(){
    do{
        producer an item nextp;
        wait(empty);
        wait(mutex);
        buffer[in]=nextp;
        in=(in+1) % n;
        signal(mutex);
        signal(full);
    }while(ture);
}
void consumer(){
    do{
        wait(full);
        wait(mutex);
        nextc = buffer[out];
        out = (out+1) % n;
        signal(mutex);
        signal(empty);
        consumer the item in nextc;
    }while(ture);
}

void main(){
    cobegin
        proceducer();consumer();
    coend
}

wait(empty)	
	empty >= 0	则数据送入缓冲区
	empty < 0	被阻塞（满）
signal(empty)	
	empty > 0		
	empty <= 0	释放一个空缓冲区，唤醒一个阻塞的生产者进程
wait(full)	
	full >= 0	则从缓冲区取走数据
	full < 0	被阻塞（空）
signal(full)	
	full > 0		
	full <= 0	数据装入缓冲区，唤醒一个阻塞的消费者进程

注意：

• 互斥和资源信号量的原语必须成对出现。
• signal操作的次序无关紧要，但wait操作的次序不能颠倒，否则会造成死锁。

利用AND型信号量解决生产者-消费者问题

semaphore mutex=1, empty=n;
item buffer[n];
int in=0, out=0;
void producer(){
    do{
        produce an item in nextp;
        Swait(empty, mutex);
        buffer[in] = nextp;
        in = (in+1)%n;
        Ssignal(mutex, full);
    }while(true);
}
void consumer() {
    do {
        Swait(full, mutex);
        nextc = buffer[out];
        out := (out+1) % n;
        Ssignal(mutex, empty);
        consumer the item in nextc;
    }while(true);
}

哲学家进餐问题 ○

书P69-70

读者-写者问题 ★

问题描述：一个文件可能被多个进程共享，为了保证读写的正确性和文件的一致性，系统要求，当有读者进程读文件时，不允许任何写者进程写，但允许多读者同时读；当有写者进程写时，不允许任何其它写者进程写，也不允许任何读者进行读。

算法描述：设置两个互斥信号量wmutex和rmutex。

• wmutex，实现Reader与Writer进程间在读或写时的互斥。
• rmutex，用于使读者互斥地访问共享变量readcount。
• readcount表示正在读的进程数目，只要有一个Reader进程在读，便不允许Writer进程去写。

因此，仅当readcount=0，表示尚无Reader进程在读时，Reader进程才需要执行Wait(wmutex)操作。若wait(wmutex)操作成功，Reader进程便可去读，相应地，做readcount+1操作。同理，仅当Reader进程在执行了readcount减1操作后其值为0时，才须执行signal(wmutex)操作，以便让Writer进程写。

semaphore rmutex=1, wmutex= 1;
int readcount= 0;
void reader() {
    do {
        wait(rmutex);
        if(readcount==0)   wait(wmutex);
        readcount++;
        signal(rmutex);
        
        perform read operation;
        
        wait(rmutex);
        readcount--;
        if(readcount==0)   signal(wmutex);
        signal(rmutex);
    }while(ture);
}
void writer() {
    do{
        wait(wmutex);
        
        perform write operation;
        
        signal(wmutex);
    }while(ture);
}
void main() {  
    cobegin
    	reader(); writer();
    coend
}

用信号量解题的关键

步骤：

1. 信号量的设置：互斥信号量、资源信号量。
2. 给信号量赋初值：通常，互斥信号量为1，资源信号量为0或n。
3. P、V操作安排的位置（其中，P的顺序不能颠倒，V的顺序任意）。

2.6 进程通信 ▽

进程同步是一种进程通信，通过修改信号量，进程之间可建立起联系，相互协调运行和协同工作。进程协同工作时，需要互相交换信息，有些情况下进程间交换的少量信息，有些情况下进程间交换大批数据。

进程之间互相交换信息的工作称为进程通信。

进程间通信的方式：

• 信号量机制
• 共享存储器系统(shared memory system)
• 管道通信（共享文件）
• 消息传递系统(message passing system)

低级通信：进程的同步和互斥。信号量机制作为同步工具是卓有成效的，但作为通讯工具则不够理想。（效率低。通讯对用户不透明。）

高级通信：用户可以直接利用操作系统所提供的一组通信命令，高效地传送大量数据的一种通信方式。

进程通信的类型

①共享存储器系统

相互通讯的进程通过共享数据结构和存储区进行通讯，因而可进一步分为：

• 基于共享数据结构的通讯方式；（低效，只适于传递少量数据）
• 基于共享存储区的通讯方式。为了传送大量数据，在存储区中划出一块共享存储区，诸进程可通过对共享存储区进行读或写数据实现通讯。

步骤：

1. 向系统申请共享存储区中的一个分区
2. 指定该分区的关键字
3. 如果已经给其他进程分配了这样的存储区，将使用分区的描述符返回给申请者
4. 申请者将申请到的共享分区挂到本进程上
5. 读写该公用存储分区

②管道通信系统

所谓“管道”（pipe），是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件。

• 发送进程以字符流形式把大量数据送入管道，接收进程从管道中接收数据。
• 管道的实质是一个共享文件，基本上可借助于文件系统的机制实现，包括（管道）文件的创建、打开、关闭和读写。
• 进程对通信机构的使用应该互斥，一个进程正在使用某个管道写入或读出数据时，另一个进程就必须等待。
• 发送者和接收者双方必须能够知道对方是否存在，如果对方已经不存在，就没有必要再发送信息。
• 管道长度有限，发送信息和接收信息之间要实现正确的同步关系，当写进程把一定数量的数据写入pipe，就去睡眠等待，直到读进程取走数据后，把它唤醒。

③消息传递系统

消息传递系统中，进程间的数据交换，是以格式化的消息(message)为单位的；在计算机网络中，又把message称为报文。

程序员直接利用系统提供的一组通信命令(原语)进行通信。

操作系统隐藏了通信的实现细节，大大减化了通信程序编制的复杂性，而获得广泛的应用。

消息传递系统的通信方式属于高级通信方式。又因其实现方式的不同而进一步分成直接通信方式和间接通信方式两种。

④客户机-服务器系统

网络环境

套接字、远程过程调用、远程方法调用

消息传递通信的实现方式

直接通信

直接通信：发送或接收消息的进程必须指出信件发给谁或从谁那里接收消息。

原语：

• 原语send（P，消息）：把一个消息发送给进程P
• 原语receive（Q，消息）：从进程Q接收一个消息

通信链路(communication link)

建立：发送进程用显式的“建立连接”命令(原语)请求系统为之建立一条通信链路；发送进程利用系统提供的发送命令(原语)，系统会自动地为之建立一条链路。

链路的连接方法：点—点连接通信链路；多点连接链路。

分类：单向通信链路；双向链路。

信箱通信

进程间发送或接收消息通过信箱进行，消息可被理解成信件。

• 原语send（A，信件）：把一封信件（消息）传送到信箱A
• 原语receive（A，信件）：从信箱A接收一封信件（消息）

发送进程把消息送到信箱，接收进程从信箱中取走消息。

• 信箱头：名称，大小，方向，进程名等；
• 信箱体：由若干格子组成，每一格存放一条消息。

信箱类型：

• 私用信箱：单向通信链路，由用户创建。
• 公用信箱：多输入/输出公用信箱，提高效率。双向通信链路，由OS创建。
• 共享信箱：由进程创建。

在利用信箱通信时，在发送进程和接收进程之间，存在着四种关系：

• 一对一关系：即可以为发送进程和接收进程建立一条专用的通信链路；
• 多对一关系：允许提供服务的进程与多个用户进程进行交互，也称客户/服务器交互；
• 一对多关系：允许一个发送进程与多个接收进程交互，使发送进程用广播的形式，发送消息；
• 多对多关系：允许建立一个公用信箱，让多个进程都能向信箱投递消息，也可取走属于自己的消息。

消息缓冲队列通信机制 ★

消息缓冲队列通信机制中的数据结构

消息缓冲区：

type message buffer=record
    sender; 发送者进程标识符
    size; 消息长度
    text; 消息正文
    next; 指向下一个消息缓冲区的指针
end 

PCB中有关通信的数据项：

type processcontrol block=record
    …
    mq; 消息队列队首指针
    mutex; 消息队列互斥信号量
    sm; 消息队列资源信号量
    …
end 

消息缓冲队列

发送原语

procedure send(receiver, a)
     begin
        getbuf(a.size,i);            根据a.size申请缓冲区
        i.sender := a.sender; 
        i.size := a.size;
        i.text := a.text;
        i.next := 0;
       getid(PCB set, receiver.j);   获得接收进程内部标识符
       wait(j.mutex);
       insert(j.mq, i);              将消息缓冲区插入消息队列
       signal(j.mutex);
       signal(j.sm);
    end 

接收原语

procedure receive(b)
   begin
      j := internal name;    j为接收进程内部的标识符
      wait(j.sm);
      wait(j.mutex);
      remove(j.mq, i);       将消息队列中第一个消息移出
      signal(j.mutex);
      b.sender := i.sender;    
      b.size := i.size;
      b.text := i.text;
  end

2.7 线程的基本概念 ▽

线程：“轻级进程”，作为调度和分派的基本单位，是程序执行流的最小单位。

为了减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性。

进程与线程间的异同

①调度性：线程是作为调度和分派的基本单位；进程不再是调度的基本单位，进程只作为资源拥有的基本单位。

②线程上下文切换比进程上下文切换快得多。

③并发性：进程间可并发执行，线程（无论在同一进程与否）间也可并发执行。

④拥有资源：进程拥有系统资源，线程仅有一点必不可少、保证独立运行的资源。多个线程可共享本进程所拥有的资源。

⑤独立性：同一进程中的不同线程之间的独立比不同进程之间的独立性低得多。

⑥系统开销：进程的创建或撤销的系统消耗“明显大于”线程的创建或撤销的系统消耗。

2.8 线程的实现 ▽

线程的实现方式：

• 内核支持线程
• 用户级线程