2.1进程的基本概念

一、程序顺序执行时的特征

（一）、顺序性：处理机的操作严格按程序规定顺序执行

（二）、封闭性：程序一旦开始执行，其计算结果不受外界因素影响。

（三）、可再现性：程序执行只要初始条件一样，不论如何停顿，重复执行多少次结果都一样。

二、进程的定义

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

①、可并发执行的程序在一个数据集合上的一次执行过程。

②、程序的一次执行

③、是一个程序与其数据一道通过处理机的执行所发生的活动。

三、进程的特征

（一）、结构性特征，进程的根本——PCB

（二）、动态性：

1、进程实质上是进程实体的一次有生命期的执行过程。程序只是静态的一组有序指令。

2、进程最基本特征

（三）、并发性：

1、多个进程实体同存于内存中，在一段时间内同时运行。

2、有PCB的程序才能并发。

（四）、独立性

（五）、异步性

四、区别进程与程序

（一）、动与静：

进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。

（二）、永久与暂时：

进程是暂时的，程序是永久的：进程是一个状态变化的过程，程序可长久保存。

（三）、结构：

进程的组成包括程序、数据和进程控制块（进程各种控制信息）。

（四）、进程与程序的对应关系：

都可1对n。通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。

五、进程的基本状态

进程执行时的间断性，决定了其具有多种状态。把握各进程所属的状态对进程控制至关重要。与进程执行相关的各种共享资源有：CPU、存储器、I/O设备、时间片

注意体会这些资源在进程状态变化中对进程运行的影响。

六、进程的三种基本状态

（一）、就绪状态(Ready)

进程获得除CPU之外的所有必需资源，一旦得到CPU控制权，可立即运行。

（二）、运行状态(Running)

进程已获得所有运行必需的资源，正在处理机上执行。

（三）、阻塞状态(Blocked)

正在执行的进程由于发生某事件（请求I/O、申请缓冲、时间片到）而暂时无法执行时，便放弃CPU后暂停

*进程实体：代码段+数据段+PCB

*进程控制块（Process Control Block）定义：存放进程的管理和控制信息的数据结构称为进程控制块。 

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

七、进程控制块（PCB）中的信息

（一）、进程标识符信息

（二）、处理机状态信息

（三）、进程调度信息

（四）、进程控制信息

2.2 进程控制

一、进程控制的基本过程：

（一）、进程的创建

（二）、进程的终止

（三）、进程的阻塞与唤醒

（四）、进程的挂起和激活

二、进程的创建过程

（一）、申请空白PCB

（二）、为新进程分配资源

主要是内存资源的处理

（三）、初始化进程控制块

标识符（包括父进程的）、程序计数器指向程序入口地址，就绪态、优先级等信息的填写。

（四）、将新进程插入就绪队列

*原语是由若干指令构成的原子操作过程，作为整体实现功能，不可被打断。

三、进程的阻塞与唤醒

（一）、引起进程阻塞和唤醒的事件

1、请求系统服务的满足情况

2、启动某种需等待（I/O）操作

3、合作需要的新数据尚未到达

4、执行某功能的进程暂时无新工作可做(如发送数据进程)

（二）、阻塞和唤醒过程

由进程调用阻塞原语阻塞自己，是主动行为：

1、将PCB中的状态改为阻塞

2、该PCB加入到阻塞队列中

3、转进程调度，将处理机分配给另一进程

4、进行进程切换，即根据两切换进程的PCB，保护与重新设置处理机状态。

四、进程的挂起与激活

挂起原语将指定进程或阻塞进程挂起。

（一）、检查被挂起进程的状态，活动就绪则改为静止就绪，活动阻塞则改为静止阻塞

（二）、将该PCB复制到内存（方便检查）/外存（对换）指定区域

（三）、若挂起的进程是执行态，则需重新进行进程调度。

*注意：进程只能挂起自己或其子孙进程。

2.3 进程同步

一、进程间的两种制约关系：

间接相互制约关系：主要源于资源共享,表现为进程A---打印机资源---进程B（互斥）

直接相互制约关系：主要源于进程合作，表现为进程A写缓冲---进程B读缓冲（有序）

二、进程同步的一些基本概念：

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

（二）、临界资源：一次仅允许一个进程使用的资源。

（三）、临界区：每个进程中访问临界资源的那段代码。

（四）、同步机制应遵循的规则：

1、空闲让进：资源使用最基本原则

2、忙则等待：保证互斥

3、有限等待：合适时被唤醒防止死等

4、让权等待：能主动释放CPU防止忙等

三、整型信号量：

（一）、信号量定义为一个整型量；

（二）、根据初始情况赋相应的值；

（三）、仅能通过两个原子操作来访问。

1、P操作：wait(S){

                          While S<=0 do no-op;

                          S:=S-1;

                       }

2、V操作：signal(S){

                        S:=S+1;

                     }

四、整型信号量符合“有限等待”原则但不符合“让权等待”原则

（一）、符合“有限等待”：

signal释放资源后，当CPU被分配给等待进程后，等待进程仍可继续执行，可以符合“有限等待”。

（二）、不符合“让权等待”：

1、整型信号量的wait操作，当s ≤0时，当前进程会占着CPU不断测试；

2、信号量原语不能被打断，这个占有CPU的进程会一直不断的占据CPU循环下去，陷入忙等。

五、 记录型信号量

（一）、变化：

1、不仅要有值的处理，还有队列的处理。此时形成记录型数据结构，包括两部分：

（1）、整型变量value(代表资源数目)            

（2）、进程链表L(链接所有等待进程)

2、定义信号量semaphore代表可用资源实体的数量。     

（1）、Value>0，表示当前可用资源的数量；     

（2）、Value≤0，其绝对值表示等待使用该资源的进程数，即在该信号量队列上排队的PCB的个数。

3、先修改资源数，再判断处理。

（1）、P操作：wait(){

                                  S->value--;

                                   if  (S->value< 0)  

                                        then  block(S->list);

                              }

（2）、V操作: signal(){

                                S->value++;

                                 if  (S.value<= 0) 

                                        then wakeup(S->list);

                                  }

4、建立一个信号量必须经过说明，包括：

（1）、信号量所代表的意义；

（2）、赋初值；

（3）、建立相应的数据结构，以便指向等待使用临界区的进程。

六、信号量的基本应用

（一）、实现进程互斥

1、两个操作原语：

（1）、P操作：P(mutex){

                                S.value = S.value - 1;

                                if  S.value < 0  then  block(S,L)；

                             }

（2）、V操作：V(mutex){

                                S.value = S.value + 1;

                                if  S.value <= 0 then wakeup(S,L)；

                             }

2、几个注意点：

（1）、互斥信号量mutex初值为1；

（2）、每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间

（3）、必须成对使用P和V原语（在同一进程中），不能次序错误、重复或遗漏：

        ①、遗漏P原语则不能保证互斥访问

        ②、遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；

（二）、实现进程间的前趋关系（有序）

1、对于前趋关系的理解:

并发执行的进程P1和P2中，分别有代码C1和C2，要求C1要在C2开始前完成；

2、几个注意点：

（1）、信号量值为0的点是限制的关键所在；

（2）、成对使用P和V原语（在有先后关系的两个进程中），不能次序错误、重复或遗漏，否则同步顺序出错。

七、AND型信号量

（一）、出现原因

一些应用往往需要两个或多个共享资源，而不是前述的一个资源。进程同时要求的共享资源越多，发生死锁可能性越大。

（二）、解决思路

一次性分配给进程所需资源，用完一起释放。Wait操作时对它所有需要的资源都要判断，有AND条件，故称“AND同步”、“同时wait”。

（三）、两个操作原语

1、Swait(S1, S2, …, Sn){

            if（S1 >=1 and … and Sn>=1 ）then{

                 for i:=1 to n do

                 Si:= Si -1 ;

                  endfor

            }

            else

                  将进程阻塞在第一个不能满足资源信号量的队列中。

            }

2、Ssignal(S1, S2, …, Sn){

            for i:=1 to n do

                    Si:= Si +1 ;

                    唤醒所以与si相关的阻塞进程

            endfor

}

八、信号量集

（一）、引入原因：

1、每次只能获得或释放一个单位的资源，低效；

2、某些时候资源分配有下限的限制；

修改：在大于可分配设置的下界值t前提下，每次可分配d个。

（二）、两个操作原语：

1、AND信号量机制上加以扩充，每种资源参数有三：

①、S 为信号量（现有值）；

②、t 为下限值（现有不能少于该条件）；

③、d 为需求值；

2、Swait(S1, t1, d1, …, Sn, tn, dn){

        if S1>= t1 and … and Sn>= tn then{

            for i:=1 to n do

               Si:= Si - di ;

            endfor

        else

            …

        }

      }

3、Ssignal(S1, d1, …, Sn, dn){

            for i:=1 to n do

            Si:= Si +di ;

            ….

            endfor

       }

（三）、只有一个信号量S的几种特殊情况：

1、Swait(S, d, d)，允许每次申请d个资源，若现有资源数少于d，不予分配。

2、Swait(S, 1, 1)，蜕化为一般的记录型信号量，一次申请一个，至多分配一个(S>1时可计数，或S=1时可控制互斥)。

3、Swait(S, 1, 0)，当S>=1时，允许多个进程进入某特定区，当S变为0后，阻止任何进程进入特定区，相当于可控开关。并不对S资源的数量产生影响。

九、信号量题目做题一般方法：

（一）、分析问题，找出同步、互斥关系

（二）、根据资源设置信号量变量

（三）、写出代码过程，并注意P、V操作的位置

（四）、检查代码，模拟机器运行，体验信号量的变化和程序运行过程是否正确。

2.4 经典同步问题

一、 生产者—消费者问题

（一）、使用场景：多个生产者和消费者对n个缓冲区的使用。

（二）、几个问题;

1、无论生产者、消费者使用缓冲池时应保证互斥使用（互斥信号量mutex ）

2、生产者和消费者间交叉有序：

①、有序的控制最根源在产品数量上。

②、设置两个信号量：

                分别针对生产者、消费者设置不同的信号量，empty和full分别表示缓冲池中空缓冲池和满缓冲池（即产品）的数量。

注意：empty、full两者有天然的数量关系，在PV控制下值不断变化，但在值等于0的点上是控制顺序的关键。

（三）、检查：

1、每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对地出现。

2、控制顺序的信号量empty和full的wait和signal操作，成对地出现在不同的进程中。

3、在每个程序中的多个wait操作顺序不能颠倒。且应先执行对资源信号量的wait操作，再执行对互斥信号量的wait操作，否则可能引起进程死锁。

4、模拟交替执行过程，检查控制是否正确。

二、哲学家就餐问题

（一）、原题：五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在桌子上有五只碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐毕，放下筷子继续思考。

                 可见：相邻两位不能同时进餐；最多只能有两人同时进餐。

（二）、记录型信号量解决哲学家进餐问题

1、筷子是临界资源，在一段时间内只允许一个哲学家使用。

2、所有信号量均被初始化为1。

（三）、就餐死锁问题——解决方法：

1、数量控制：限制并发执行的进程数

2、一刀切：采用AND信号量。

3、IF编程控制

三、读者—写者问题

（一）、一个数据文件被多个进程共享。

（二）、合理的同步关系是：

1、多个读进程可同时读；

2、Writer进程与任何其他进程（包括Reader进程或其他Writer进程）不允许同时访问文件。

（三）、解决读者问题的关键：除第1读者，其他读者不申请读写互斥信号量，防止读者间互斥。

2.5 信号量习题

一、黑白棋子问题

先抢到棋盘者先下，然后轮流下子

（一）、无法用单纯的信号量操作完成，因为初始值无法设置固定值。

（二）、利用互斥信号量与特殊标志变量的结合使用实现有序控制。

二、嗜睡的理发师问题

（一）、共享变量count的使用需要互斥。

（二）、注意if分支加入后P、V操作配对核对清楚

2.5 管程机制

一、管程基本思想：

将共享变量及对共享变量能够进行的所有操作集中在一个模块中。（把信号量及其操作原语“封装”在一个对象内部）

二、管程的组成：

（一）、一组局部变量

（二）、对局部变量操作的一组过程

（三）、对局部变量进行初始化的语句。

三、管程特点：

（一）、任何进程只能通过调用管程提供的过程入口才能进入管程访问共享数据；（就如同使用临界资源，就要先通过其信号量的申请。）

（二）、任何时刻，仅允许一个进程在管程中执行某个内部过程。

四、变量：

（一）、局部于管程的变量有两种：

1.普通变量

2.条件变量（用于控制进程阻塞和唤醒）

①、类似信号量变量，但不取具体值；相当于每个阻塞队列的队列指针。

②、对条件变量的操作需结合对普通变量的条件判断，从而控制进程状态。

（二）、条件变量作用

进程同步的阻塞和唤醒控制

2.6 进程通信

一、进程通信是指进程之间的信息交换。

1、低级通信——进程之间的互斥和同步

信号量机制是有效的同步工具，但作为通信工具缺点如下：

①、效率低（通信量少）

②、通信对用户不透明（程序员实现，操作系统只提供共享存储器供代码操作）

2、高级进程通信

用户直接利用操作系统提供的一组通信命令，高效地传送大量数据的通信方式。（操作系统隐藏了进程通信的细节，对用户透明，减少了通信程序编制上的复杂性。）

二、进程通信的类型

（一）、共享存储器系统（操作存储区方式）

相互通信的进程共享某些数据结构或共享存储区，进程之间能够通过这些空间进行通信。

1、基于共享数据结构的通信方式（低级）

2、基于共享存储区的通信方式（高级）

（二）、消息传递系统（发--收方式）

1、最广泛使用的一种，进程间的数据交换，以格式化的消息为单位。屏蔽底层复杂操作。

2、单机：操作系统底层编程中的消息传递系统调用；

3、计算机网络：消息称为报文。程序员直接利用系统提供的一组通信命令(原语)进行通信。（④客户机-服务器系统）

（三）、管道通信（中间文件方式）

1、所谓“管道”，是指用于连接一读进程和一写进程以实现通信的一个共享文件，又名pipe文件。

2、向共享文件输入的写进程以字符流形式将大量的数据送入管道；而接收管道输出的读进程则从管道中接收(读)数据。

（四）、Client-Server system

1、套接字（Socket）

2、远程过程调用（远程方法调用）

3、RPC应用开发步骤

三、 消息传递通信的实现方法

（一）、直接通信方式

发送进程利用OS所提供的发送命令（原语），直接把消息发送给目标进程。此时，发送进程和接收进程都以显式方式提供对方的标识符。通常利用系统通信命令（原语）：

Send(Receiver, message);

Receive(Sender, message);

（二）、间接通信方式

基于共享数据结构的实体用来暂存发送给目标进程的消息；接收进程则从该实体中，取出对方发送给自己的消息。通常把这种实体称为信箱。（消息在信箱中可以安全地保存，只允许核准的目标用户随时读取。既可实时通信，又可非实时通信。）

系统为信箱通信提供原语：

1.信箱的创建和撤消

①.信箱名

②.权限属性

<1>.私用信箱

<2>.公用信箱

<3>.共享信箱

③.共享者名称

2.信箱消息的发送和接收

进程之间利用信箱进行通信时，必须使用共享信箱。

Send(mailbox, message);

Receive(mailbox, message);

四、信箱通信时发送进程和接收进程间有四种关系：

（一）、一对一关系

（二）、多对一关系

（三）、一对多关系

（四）、多对多关系

五、消息传递系统的实现

单机和网络环境下的高级进程通信广泛采用“消息传递”方式，需要考虑的问题：

（一）、通信链路的建立

1.计算机网络环境下，用原语显式建立/拆除链路

2.单机系统只须利用系统原语，进程间链路由系统自动管理。

（二）、消息格式

1.单机系统，发送与接收进程在同一台机器，环境相同故格式简单；

2.网络环境下，受不同目标机器的环境和长距离信息传输等因素的影响，消息格式较复杂，消息常是“大头+正文”

（三）、同步方式（如何控制发送和接收的状态）

1.发送进程阻塞、接收进程阻塞（无缓冲紧密同步）

2.发送进程不阻塞、接收进程阻塞（服务器程序）

3.发送进程和接收进程均不阻塞（缓冲队列）

2.7 线程

一、线程的属性

多线程OS中，一个进程包括多个线程，每个线程都是利用CPU的基本单位。

（一）、轻型实体：只需一点必不可少的、能保证独立运行的资源。（TCB）

（二）、独立调度和分派的基本单位：调度切换迅速且开销小。

（三）、可并发执行

（四）、共享进程资源：同进程中的线程可共享相同的进程地址空间、已打开文件、信号量机构等。

二、线程的信息（TCB管理什么信息）

（一）、状态参数

标识符、运行状态、优先级、寄存器状态、堆栈、专有存储器、信号屏蔽等。

（二）、运行状态

执行、就绪、阻塞

三、线程的创建和终止

在多线程OS中，应用程序启动时，通常只有一个线程(初始化线程)在执行，它根据需要再创建若干线程。

（一）、创建新线程

利用线程创建函数(或系统调用)，提供相应参数。线程创建函数执行完后，返回一个线程标识符供以后使用。

（二）、线程被终止：

1.不立即释放资源，只有当进程中的其它线程执行分离函数后，资源才分离出来能被其它线程利用。

2.被终止而未释放资源的线程仍可被需要它的线程调用，使其重新恢复运行。

四、多线程的应用

（一）、一个应用程序有多个任务或功能需要同时进行处理，就最适合多线程机制。

（二）、应用情况举例：

1.网络软件，需要同时进行用户界面响应、收数据、发数据。

2.网络下载工具：多线程下载的下载工具

*五、线程与进程的比较

（一）、调度：线程作为CPU调度的基本单位，而进程只作为其它资源分配单位。

（二）、并发性：进程之间可以并发，实质上是不同进程中的两个线程并发。一个进程的多个线程之间亦可并发。

（三）、拥有资源：进程间资源相互独立；同一进程的各线程间共享。某进程内的线程在其它进程不可见

（四）、系统开销：线程上下文切换在同进程环境下上下文切换要快得多。因为同进程内线程间共享内存地址和打开的文件资源；

六、线程的管理

同步和通信机制

（一）、互斥锁

1.比较简单的，控制线程互斥访问资源；

2.适用于高频度使用的关键共享数据和程序段；

3.unlock和lock两个锁操作原语；

（二）、条件变量

1.与互斥锁一起使用

2.锁保证互斥进入临界区，但利用条件变量使线程阻塞

3.注意不满足条件时，wait条件变量：

①.释放互斥锁

②.进程阻塞在条件变量指向队列中

③.被唤醒后要重新再设互斥锁

（三）、信号量

1.私用信号量（private samephore）

用于同进程的线程间同步，数据结构存放在应用程序的地址空间。属于特定进程，OS感知不到其存在。

2.公用信号量（public samephore）

用于不同进程间或不同进程中线程的同步，数据结构由OS管理，存放在受保护的系统存储区。

*注：互斥锁是为了上锁而优化的；条件变量是为了等待而优化的；信号灯即可用于上锁，也可用于等待，因而可能导致更多的开销和更高的复杂性。三种机制适用逐渐复杂的同步情况

七、线程的实现方式

（一）、内核线程KST(kernel-level thread)

（二）、用户线程ULT(user-level thread)

（三）、组合方式