操作系统复习（2）进程管理

一、概述

1.1程序的顺序执行

一个具有独立功能的程序独占CPU运行，直至得到最终结果的过程称为程序的顺序执行。

程序的并发执行所表现出的特性说明两个问题

⑴ 程序和计算机执行程序的活动不再一一对应

⑵ 并发程序间存在相互制约关系（要求共享信息，竞争使用同一资源）

1.2进程概述

• 引入目的：更好地描述和控制程序的并发执行，实现操作系统的并发性和共享性（最基本的两个特性）
• 定义：进程：为了使程序并发执行， 并且可以对并发执行程序加以描述和控制（动态）
• 进程=程序+执行（进程：进展中的程序）
   
• 进程的构成：PCB、程序段、数据段

• PCB：
  
• 程序段：程序可被多个进程共享，即多个进程可运行同一个程序
• 数据段：可以使进程对应的程序加工处理的原始数据，也可以是程序执行时产生的数据

• PCB是进程存在的唯一标识

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

• 进程的特征：动态性、并发性、独立性、异步性、结构性、短暂性（有生命周期）

• 进程的基本状态：运行态、就绪态、阻塞态

进程状态及其转换

• 就绪状态：准备执行
• 执行状态：占用处理机（单处理机环境中，某一时刻仅一个进程占用处理机)
• 阻塞状态：等待某事件发生才能执行，如等待I/0完成等

具有挂起状态的进程状态转换

进程被交换到外存，状态变为挂起状态

引入挂起状态的主要原因

• 内存资源不足
• 另外当有终端用户请求、父进程请求、负荷调节需要等情况时，也要用到挂起状态。

1. 就绪态→运行态：处于就绪态的进程被调度后，获得处理机资源（分派处理机时间片），于是进程由就绪态转换为运行态。
2. 运行态→就绪态：处于运行态的进程在时间片用完后，不得不让出处理机，从而进程由运行态转换为就绪态。此外，在可剥夺的操作系统中，当有更高优先级的进程就绪时，调度
3. 运行态→阻塞态：进程请求某一资源（如外设）的使用和分配或等待某一事件的发生（如/O操作的完成)时，它就从运行态转换为阻塞态。进程以系统调用的形式请求操作系统提供服务，这是一种特殊的、由运行用户态程序调用操作系统内核过程的形式。
4. 阻塞态→就绪态：进程等待的事件到来时，如I/O操作结束或中断结束时，中断处理程序必须把相应进程的状态由阻塞态转换为就绪态。

 1.3进程分类

  进程分两类： 系统进程 用户进程

通常允许一个进程创建和控制另一个进程，前者称为父进程，后者称为子进程 

1.4进程控制（原语）

进程有由创建而产生，由调度而执行，由撤销而消亡的生命周期，因此操作系统要有对进程生命周期的各个环节进行控制的功能，这就是进程控制。

原语：

进程的控制通常由原语完成。所谓“原语”一般是指由若干条指令所组成，用来实现某个特定功能，在执行过程中不可被中断的程序段。 （常驻内存，通常在管态下执行）

能够导致创建进程的事件

• 用户登录
• 作业调度
• 提供服务
• 应用请求

创建进程原语与 撤销进程原语

创建进程原语是一种操作系统提供的基本功能，用来实现新进程的创建。创建进程原语的实现需要完成以下几个步骤：

1. 申请进程控制块：操作系统通过调用内存管理机制，从操作系统的进程控制块池中申请一个空闲的进程控制块，用来描述新进程的相关信息。

2. 初始化进程控制块：将申请到的进程控制块中的各项字段进行初始化，包括进程状态、进程ID、优先级等等。

3. 为进程分配资源：操作系统为新进程分配所需的资源，包括内存空间、文件描述符、打开的设备等等。

4. 创建进程的执行环境：操作系统根据新进程的执行要求，为其创建执行环境，包括代码段、数据段、堆栈等等。

5. 将新进程加入就绪队列：将创建好的进程加入就绪队列，让其等待调度器分配时间片。

撤销进程原语则是用来结束一个进程的运行。撤销进程原语的实现需要完成以下几个步骤：

1. 标记进程为撤销状态：将要撤销的进程的状态标记为撤销状态，表示该进程即将被终止。

2. 释放进程资源：将要撤销的进程所占用的资源全部释放，包括内存空间、文件描述符、打开的设备等等。

3. 删去进程控制块：将要撤销的进程的进程控制块从进程控制块池中删除，释放空间。

4. 终止该进程的执行：将正在执行的进程终止，并将处理器的控制权交给其他进程。

创建进程原语和撤销进程原语是操作系统中非常重要的基本操作，它们的正确实现对于保证操作系统的稳定和安全具有非常重要的意义。

 阻塞进程原语,唤醒进程原语

阻塞进程原语（也称为等待原语）是指在某些条件不满足的情况下暂停进程的执行，直到满足该条件为止。阻塞进程可以用于等待某个事件的发生，例如等待某个文件读取完成，等待某个网络连接建立等。阻塞进程原语的实现需要完成以下几个步骤：

（1）中断CPU，停止进程运行；

（2）将CPU的现行状态存放到PCB的CPU状态保 护区中；

（3）将该进程置阻塞状态，并把它插入到等待队列中；

（4）系统执行调度程序，将CPU分配给另一个就绪的进程。

唤醒进程原语（也称为通知原语）是指当某个条件满足时，唤醒被阻塞的进程继续执行。唤醒进程可以用于通知某个事件的发生，例如通知某个读写操作已经完成，通知某个消息已经到达等。唤醒进程原语的实现需要完成以下几个步骤：

（1）找到被唤醒进程的内部标识，让该进程脱离阻塞队列；

（2）将现行状态改变为就绪状态；

（3）插入就绪队列等待调度运行。

在操作系统中，通常使用信号量、互斥锁等机制来实现阻塞进程和唤醒进程的功能。其中，信号量可以用于控制进程的并发访问，互斥锁可以用于保护共享资源不被并发访问。

进程的挂起与激活原语 

挂起与激活原语可以被用来实现进程的同步和通信。例如，当多个进程共享一个资源时，可以利用挂起和激活原语控制它们的访问顺序，避免互相干扰。

 1.5进程互斥与同步：

我们把某段时间内只能允许一个进程使用的资源称为临界资源。

我们把访问临界资源的代码段称为临界区。（互斥进行）

进程互斥与同步

我们把在异步环境下并发执行的进程，因直接制约而需要相互等待、相互合作，以达到各进程按相互协调的速度执行的过程称为进程间的同步。      

把因间接制约而导致交替执行的过程称为进程间的互斥。

 进程互斥指的是多个进程在同一时间内不能同时访问共享资源，否则会出现冲突。例如，两个人同时想要使用厕所，但是只有一个厕所可用，这就是进程互斥

进程同步指的是多个进程在执行时需按照一定的顺序和时间进行协调，以保证数据的正确性和完整性。例如，多个工人在协作完成一个任务时，需要按照行动计划进行分工协作，确保每个人完成各自的工作后，整个任务能够顺利完成，这就是进程同步。 

互斥与同步的解决方法

• 软件方法（“忙等”问题,增加系统的额外开销）
• 硬件方法（屏藏中断、专用机器指令）（“忙等”问题）
• 信号量方法
• 管程方法
• 消息传递方法

同步机制

同步机制应遵循的准

• 空闲让进：其他进程均不处于临界区；
• 忙则等待：已有进程处于其临界区；
• 有限等待：等待进入临界区的进程不能"死等”
• 让权等待：不能进入临界区的进程，应释放CPU(如转换到等待状态)

三种同步机制：锁、信号量和管程。

 信号量机制

整型信号量

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

资源信号量,开关信号量,信号量初值为1的信号量我们也叫做互斥信号量

 记录型信号量

记录型信号量是一种类型的信号量，在操作系统中被用来实现同步和互斥的功能。与二进制信号量不同的是，记录型信号量可以拥有任意非负整数作为其值。

当进程或线程需要访问一段共享资源时，需要先将记录型信号量的值减一，表示资源已被占用。当资源使用完成后，需要将该信号量的值加一，表示该资源现在可以被其他进程或线程使用。

记录型信号量的实现需要对其值的更新进行原子操作，以避免多个进程或线程同时修改其值而导致的竞态条件。

记录型信号量可以被多个线程或进程同时访问，并且可以用于解决多种问题，如生产者-消费者问题、读者-写者问题和哲学家进餐问题等但是无法避免死锁等问题，

AND型信号量

AND型信号量是指只有当一组资源全部都可用时，进程才能够获取到这组资源。在操作系统中，AND型信号量可以用于同步多个进程之间对共享资源的访问，保证多个进程在访问共享资源时不会发生冲突或竞争，从而确保系统的正确性和稳定性。

AND型信号量的实现通常涉及到两个基本操作：

1. P操作：当一个进程需要使用一组资源时，首先需要执行P操作，即请求这组资源。如果这组资源全部可用，则分配给该进程，并将该资源标记为不可用；否则，该进程将被阻塞，等待这组资源全部可用。

2. V操作：当一个进程使用完一组资源时，需要执行V操作，即释放这组资源。如果这组资源全部被该进程占用，则将这组资源标记为可用，并唤醒等待这组资源的进程；否则，V操作无效。

AND型信号量的实现需要考虑资源的互斥性、同步性、死锁等问题，因此在实际应用中需要细心设计和实现，以保证系统的正确性和性能。

 信号量集

信号量是一种在操作系统中用于同步进程和线程的工具。信号量集是一个包含多个信号量的集合。

每个信号量集都有一个唯一的标识符和一个大小，以及一组信号量。每个信号量集中的每个信号量都有一个值，可以通过P操作（等待）和V操作（释放）来修改这个值。

P操作会检查信号量的值是否大于0，如果大于0，则将其减1并继续执行，否则阻塞等待直到信号量的值变为大于0为止。V操作会将信号量的值加1，并唤醒等待在该信号量上的任何进程或线程。

信号量集可以用于控制资源的分配和访问，以确保同一时刻只有一个进程或线程可以访问一种资源。例如，在使用共享内存时，可以使用信号量集来确保只有一个进程或线程可以访问该内存区域。

管程

Hansen给管程的定义是：一个管程定义了一个数据结构和在此数据结构上能为并发程序所执行的一组操作，这组操作能同步进程和改变管程中的数据。

一个管程主要由三部分组成：

①局部于该管程的共享数据，这些数据表示了相应资源的状态；

②局部于该管程的一组操作过程，每个过程完成对上述数据的某种规定操作；

③对局部于该管程的数据的初始化。

1.6进程互斥同步经典习题

生产者和消费者问题

生产者和消费者问题是一个经典的并发编程问题，它描述了多个线程对共享资源的访问和使用。该问题的目标是协调多个线程之间的操作，以避免死锁和竞争条件。

在该问题中，有两种类型的线程：生产者和消费者。生产者线程负责生成数据并将其放入共享缓冲区中，消费者线程则负责从共享缓冲区中取出数据并处理它们。共享缓冲区是一个有限大小的队列，生产者不能往队列满时继续添加数据，消费者也不能从空队列中取数据。

 改进

生产者和消费者问题例题

某寺庙，有小和尚、老和尚若干.庙内有一水缸，由小和尚提水入缸，供老和尚饮用。水缸可容纳30桶水，每次入水、取水仅为1桶，不可同时进行。水取自同一井中，水井径窄，每
次只能容纳一个水桶取水。设水桶个数为5个，试用信号量和wS操作给出老和尚和小和尚的活动。

 读者与写者问题

读者与写者问题是一个并发处理问题，其中一个访问共享资源的进程被称为写者，而其他访问该资源的进程被称为读者。这种情况下，写者需要独占地访问资源以进行写操作，而读者可以共享访问资源进行读操作。

这个问题的主要挑战是确保写者和读者之间的同步，以免发生冲突，从而导致资源的不一致性。如果一个写者正在写入资源，这时另一个写者进来，那么就会发生“丢失更新”情况，因为第二个写者的修改覆盖了第一个写者的修改。同样，在读者和写者之间交替的情况下，读者可以读取到不一致的资源状态。

 

 读者与写者问题例题

8、描述：独木桥问题：东西向汽车过独木桥，为了保证安全，只要桥上无车，则允许一方的汽车过桥，待另一方的汽车全部过完后，另一方的汽车才允许过桥。请用信号量和ws操作来写出汽车过独木桥问题的同步算法。

哲学家就餐问题

哲学家就餐问题（Dining Philosophers Problem）是一个经典的同步问题，用于解释在并发编程中的互斥和同步问题。

假设有五位哲学家坐在一张圆形桌子周围，每个哲学家前面都有一碗意大利面和一只叉子。哲学家只能在拿到两只叉子时才能进食，而每只叉子只能由左右两个哲学家共用。因此，如果每个哲学家都拿起他们左边的叉子，那么他们将陷入死锁状态，因为每个哲学家都在等待他们右边的叉子。为了解决这个问题，需要使用同步技术，如信号量和互斥锁，确保每个哲学家能够安全地拿起叉子进食，并且不会造成死锁或饥饿状态。

 1.7进程通信（了解）

进程区间同步与互斥是一种低级通信)用来控制进程执行速度。

共享存储器系统(Shared-Memory System)

• 基于共享数据结构的通信方式。
• 基于共享存储区的通信方式。

消息传递系统

操作系统的消息传递系统是一种机制，用于在不同的进程或线程之间传递数据或信号。这种机制使得进程或线程可以相互通信，并且可以在不同的计算机系统之间进行通信。

管道(Pipe)通信

管道(Pipe)是一种进程间通信(IPC)方式，也是一种单向通信的方式，数据流只能向一个方向流动，常用于父子进程或兄弟进程间通信。在操作系统中，管道可以通过创建一个文件描述符来实现通信。

客户机-服务器系统(Client-Server system)

略

• 私用信箱
• 公用信箱
• 共享信箱

1.8线程

• 引入线程的目的：减小程序在并发执行时的时空开销(进一步提高系统并发度而不增加系统开销)
• 是一个基本的CPU执行单元，也是程序执行流的最小单元

进程的两个基本属性

• 进程是一个可拥有资源的独立单位
• 进程同时又是一个可独立调度和分派的基本单位

线程——作为调度和分派的基本单位

二、相关习题

1、若P、V操作的信号量S初值为2，当前值为-1，则表示有()等待进程
A.0个
B.1个
C.2个
D.3个

B. 1个等待进程。因为当前值为-1，表示已有一个进程占用了资源，需要等待释放资源后才能执行。

 2、用P、V操作管理临界区时，信号量的初值定义为()
A.-1
B.0
C.1
D.任意值

答案为C.1。

P、V操作是信号量机制中常见的两种操作。其中P操作（wait操作）会尝试占有信号量并将其值减1，如果此时信号量的值小于0，则当前进程被阻塞，等待其他进程释放信号量；V操作（signal操作）会将信号量的值加1，并唤醒一个等待该信号量的进程（如果有的话）。

因此，如果信号量初值为负数，则进程在第一次尝试占有信号量时就会被阻塞，无法进入临界区，会导致程序出现死锁。如果信号量初值为0，则第一个进程能够占有信号量，但是如果没有进程释放信号量，其他进程会一直被阻塞，同样会导致死锁。因此，通常情况下信号量的初值应该为1。

 3.进程间的同步是指进程间在逻辑上的相互()关系
A.联接
B.制约
C.继续
D.调用

正确答案为B.制约。

进程间的同步是指在协作完成某个任务时，为了避免产生竞争条件，需要协调进程的执行顺序以及进程之间的数据传输。在进程间的同步中，必须通过一些机制来保证各个进程之间的执行顺序，并防止它们之间出现不可控的竞争关系。而这种协调机制就是进程间的制约关系。因此，选项B.制约是正确答案。

 4、对于两个并发进程，设互斥信号量为mutex,若mute=0,则（)
A.表示没有进程进入临界区
B.表示有一个进程进入临界区
C.表示有一个进程进入临界区，另一个进程等待进入
D.表示有两个进程进入临界区

解析：本题考查互斥信号量的性质，mutex初值为1，表示允许一个进程进入临界资源，当由一个进程进入临界区且没有进程等待进入时，mutex减1，变为0，|mutex|为等待进入的进程数。就此题而言，当mutex=1时表示没有进程进入临界区；当mutex=-1时表示有一个进程进入临界区，另一个进程等待进入，答案选B。

5.在多进程的系统中，为了保证公共变量的完整性，各进程应互斥进入临界区，所谓临界区是指()。
A:一个缓冲区
B:一段数据区
C:同步机制
D:一段程序

D: 一段程序。临界区是指在并发程序中访问共享资源的那部分程序。在多进程系统中，如果多个进程同时访问共享变量，就会出现竞争状态，可能会导致数据不一致或者损坏。因此，需要采用同步机制，确保在任意时刻只有一个进程能够进入临界区，这样就可以避免竞争状态。

 6.若有一售票厅只能容纳300人，当少于300人时，可以进入：否则，需在外等候。若将每一个
购票者作为一个进程，请用(wait)、(signal)操作编程，并写出信号量的初值。（强调：只有
一个购票窗口，每次只能为一位购票者服务)

 

7.描述：有一个阅览室，读者进入时必须先在一张登记表上登记。该表中每个表项代表阅览室
中的一个座位。读者离开时要销掉登记信息。阅览室共有50个座位。登记表每次仅允许一个读者
登记或注销。读者登记时发现登记表满，在阅览室外等待，直至有空位再登记进入。试用P、V
操作描述读者行为。
 

8.描述：设一辆公共汽车上，司机和售票员的活动分别是：司机：启动车辆，正常行车，到站停车；售票员：上乘客，关车门，售票，开车门，下乘客.在汽车不断地到站，停车，行驶的过程中，这两个活动有什么同步关系？并用wait和signal)原语操作实现它们的同步

 9.当时，进程从执行状态转变为就绪状态。 ()

A.进程被调度程序选中

B.时间片到

C.等待某一事件

D.等待的事件发生

根据题目描述，“进程从执行状态转变为就绪状态”，意味着进程在执行过程中被暂停，等待重新被调度执行。根据操作系统的基本原理，进程从执行状态转变为就绪状态通常发生在以下情况：

A. 进程被调度程序选中

当进程被操作系统的调度程序选中时，它会从就绪队列中被取出并进入执行状态。所以，选项A不符合题目要求。

B. 时间片到

在时间片轮询调度算法中，操作系统给每个进程分配一个固定的时间片，在该时间片内执行进程，当时间片用完时，进程就被暂停，重新进入就绪队列等待下一次调度。因此，选项B是正确的。

C. 等待某一事件

当进程需要等待某种事件发生时，例如等待I/O操作完成，进程会被暂停，进入阻塞状态，等待事件发生。因此，选项C不符合题目要求。

D. 等待的事件发生

当进程等待的事件发生时，它会从阻塞状态转变为就绪状态，并重新被调度执行。因此，选项D不符合题目要求。

综上所述，本题答案为B。

10.在进程状态转换时，下列转换时不可能发生的。()
A.就绪态->运行态
B.运行态->就绪态
C.运行态->阻塞态
D.阻塞态->运行态

A.就绪态->运行态，B.运行态->就绪态，C.运行态->阻塞态都是可能发生的状态转换，唯独D.阻塞态->运行态是不可能发生的状态转换。因为阻塞态表示进程正在等待某个事件的发生（如等待输入输出完成、等待资源分配等），必须先等待这些事件完成后才能进入就绪态等待CPU分配资源，即先从阻塞态转换为就绪态，再从就绪态转换为运行态。

11.一个进程释放一种资源将有可能导致一个或几个进程()
A.由就绪变运行
B.由运行变就绪
C.由阻塞变运行
D.由阻塞变就绪

D.由阻塞变就绪。当一个进程释放某种资源时，如果有其他进程在等待该资源，则这些进程将从阻塞状态变为就绪状态，等待CPU分配资源并进行运行。

12下列有可能导致一进程从运行变为就绪的事件是()
A.一次/O操作结束
B.运行进程需做/O操作
C,运行进程结束
D.出现了比现运行进程优先级更高的进程

答案是D。其他三个选项描述的是进程从阻塞（等待I/O）状态转换为就绪状态的情况，而D选项描述的是出现了优先级更高的进程的情况，可以导致当前正在运行的进程被抢占并从运行状态转换为就绪状态。

13.进程的并发性是指若干个进程()。
A.同时执行
B.在执行时间上是重叠的
C.在执行时间是不可重叠的.
D.共享系统资源

14以下工作中，【】不是创建进程所必须的。
A创建进程的PCB
B为进程分配内存
C为进程分配CPU
D将PCB插入就绪队列.

答案是C为进程分配CPU。创建进程时，首先需要创建进程控制块（PCB），用于存储进程相关的信息，包括进程状态、程序计数器、栈指针等，但不一定需要为进程分配CPU。为进程分配内存是为了给进程分配可执行内存空间，在该空间中存储数据和代码。将PCB插入就绪队列则是为了让进程能够被调度执行。然而，CPU的资源是由操作系统进行管理和分配的，进程只需要将PCB插入就绪队列等待CPU调度即可，不需要自己分配CPU。因此，C选项不是创建进程所必须的。

15系统中有5个用户进程且CPU工作于用户态，则处于就绪状态或阻塞状态的
进程数最多分别为【】。
A5,4
B4,0
C0,5
D4,5

16.设有10个进程共享一临界资源，为该临界资源设初值为1的互斥信号量，则该信号量的取值范围是【】。
A0-1
B-1-0
C-9-0
D-9-1.

答案：D

由于有10个进程共享一临界资源，因此最多只有一个进程能够访问该资源。初始互斥信号量的取值为1，表示该资源未被占用。当有一个进程访问该资源时，需要将信号量的值减1，表示该资源已被占用。-9表示还有9个进程需要等待因此，互斥信号量的取值范围为-9-1。

17.设与某资源相关联的信号量初值为3，当前值为1，若M表示可用资源数，N
表示等待该资源的进程数，则M和N分别是【】。·
A0,1
B1,0
C1,2
D2,0

答案是B。

信号量初值为3，当前值为1，表示该资源最多可以被占用3次，当前被占用2次，也就是还有1次可用,即还有资源可用，所以不存在等待进程N=0

18.为实现消息传递通信，在PCB中应该增加多个数据项，它们分别是(1)、(2)和(3)
A互斥信号量
B资源信号量
C消息读写原语
D消息队首指针
 19

.