操作系统复习二

操作系统复习二

# 一、程序的顺序执行

程序顺序执行时的特征

• 顺序性：按照程序结构所指定的次序
• 封闭性：运行时候独占处理机资源，运行结果不受外界影响
• 可再现性：初始条件相同，结果相同

# 二、程序的并发执行及其特征

定义：程序的并发执行是指上一组在逻辑上互相独立的程序或程序段在执行时间上客观上相互重叠，即一个程序或程序段的执行尚未结束，另一个程序 (段) 的执行已经开始的执行方式

• 并发：在一段时间内的同时进行
• 并行：在同一物理时刻的同时

并发执行时的特征：

• 间断性 (相互制约性): 一个程序可能走到中途停下来，失去原有的时序关系
• 失去封闭性：多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性
• 不可再现性：程序在并发执行时，由于失去了封闭性，导致失去其可再现性

# 三、进程

1、进程的定义：进程是程序的一次执行

2、进程的特征：

• 动态性

  • 进程对应程序的执行
  • 进程是动态产生：创建 -> 运行 -> 消亡
  • 进程在其生命周期内，在三种基本状态之间相互转换

• 独立性：各进程的地址空间相互独立，除非采用进程间通信手段

• 并发性：指多个进程实体同存于内存中，且能在一段时间内同步运行

• 异步性：每个进程都以其相对独立的不可预知的速度向前推进

• 结构化：进程 = 代码段 + 数据段 + PCB

※例题：

(1) 进程是一个程序在某个数据集上的一次执行，所以不同进程对应不同的程序。

进程是程序在某数据集上的一次执行，但是不同进程可以对应同一程序，即多次运行同一代码段

(2) 程序顺序执行和并发执行有什么不同？

顺序执行：一个独立功能的程序独占 CPU 直到得到最终结果的过程。其过程具有顺序性，封闭性，可再现性

并发执行：一组在逻辑上相互独立的程序或程序段在执行过程中，其执行时间在客观上相互重叠，即一个程序段的执行尚未结束，另一个程序段的执行已经开始的执行方式。其过程具有间断性，失去封闭性，不可再现性。

(3) 用户程序必须在进程中运行。

只有进程才可以运行，程序只是代码段，经过编译链接成 exe 文件后，exe 文件才是可以运行的进程

(4) 两次打开 Word 字处理程序，编辑同一片文章，因为程序一样，数据一样，所以系统中运行的这两个 Word 字处理程序是同一进程。

错误，进程的标识符是 PCB，这两个进程的代码段一样，但是控制进程的 PCB 不一样，因此这是两个不同的进程

3、进程的组成：

进程 = 程序 + 数据 + 进程控制块 PCB

• 程序是进程的不可缺少的组成部分
• 数据是进程处理的对象
• 进程控制块是进程的控制结构，包含了进程的描述信息，控制信息和资源信息以及现场保护，是进程的唯一标识，系统通过 PCB 来管理和控制进程

通常的程序无法并发执行，为了使程序能够并发执行，应为其配置一进程控制模块，即 PCB

进程控制模块 PCB：

• 进程控制模块是由 OS 维护的用来记录进程相关信息和管理进程而设置的一个专门的数据结构
• PCB 结构的全部或部分常驻内存
• PCB 随进程的创建而填写，随进程的撤销而释放，有生命周期
• 系统利用 PCB 来控制和管理进程，所以 PCB 是系统感知进程存在的唯一标识
• 进程与 PCB 是一一对应的

进程与程序的区别：

• 进程是动态的，程序是静态的
• 进程是暂时的，程序是永久的
• 进程与程序的组成不同：进程的组成包括程序，数据和进程控制块
• 进程与程序的对应关系：通过多次执行，一个程序对应多个进程；通过调用关系，一个进程可包括多个程序
• 进程具有并行特征，程序没有
• 进程是竞争计算机资源的基本单位

4、进程的基本状态：

• 就绪态：已分配到除 CPU 以外的所有必要的资源。多个排成一队称为就绪队列

• 执行态：指进程已获得处理机，其程序正在运行；在单处理机系统中，只能有一个进程处于执行状态；在多处理机系统中，则可能有多个进程处于执行状态

• 阻塞态：进程因发生某事件（如请求 I/O、申请缓冲空间等）而暂停执行时的状态。通常将处于阻塞状态的进程排成一个队列，称为阻塞队列

• 创建状态：OS 已完成为创建一新进程所必要的工作

  • 已构造了进程标识符
  • 已创建了管理进程所需的表格

• 终止状态：

  • 终止后进程移入该状态
  • 不再有执行资格
  • 表格和其他信息暂时保留

• 挂起状态：把一个进程从内存转到外存

  • 挂起进程的目的：
    • 提高处理机效率：就绪进程表为空时，OS 将阻塞进程从内存中挂起到磁盘的挂起队列，再从该队列选择另一进程进入内存，或者接受一个新进程的请求
    • 为了运行提供足够内存：资源紧张时，暂停某些进程
    • 用于调试

5、进程三种基本状态转换：

• 就绪 -> 运行：调度程序选择一个新的进程运行

• 运行 -> 就绪：

  • 运行进程用完了时间片
  • 运行进程被中断，因某一高优先级进程处于就绪状态

• 运行 -> 等待：当某一进程等待一事件发生时，如：

  • 请求系统服务
  • 无新工作可做

• 等待 -> 就绪：当所等待的事件发生时

挂起进程模型状态及其转换:

• 就绪状态 (Ready): 进程在内存且立即进入运行状态

• 阻塞状态 (Blocked): 进程在内存，并等待某事件的发生

• 就绪挂起状态 (Ready,suspend): 进程在外存，但只要进入内存，即可运行

• 阻塞挂起状态 (Blocked,suspend): 进程在外存并等待某时间的出现

• 挂起 (Suspend):

  • 阻塞到阻塞挂起：没有进程处于就绪状态或就绪进程要求更多内存资源时，会进行这种转换，以纳入新进程或运行就绪进程
  • 就绪到就绪挂起：当有高优先级（系统认为会很快就绪的）进程和低优先级就绪进程，系统会选择挂起低优先级就绪进程
  • 运行到就绪挂起：对抢先式分时系统，当有高优先级阻塞挂起进程因事件出现且进入就绪挂起时，系统更可能会把运行进程转到就绪挂起状态

• 激活 (Activate):

  • 就绪挂起到就绪：没有就绪进程或挂起就绪进程优先级高于就绪进程时，就会进行这种转换
  • 阻塞挂起到阻塞：当一个进程释放足够内存时，系统会把一个高优先级阻塞挂起（系统认为很快出现所等待的事件）进程转换为阻塞状态

※思考题：

(1) 如果系统由 N 个进程，运行的进程最多有几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？

运行最多一个，最少 0 个；就绪最多 N-1 个，最少 0 个，等待最多 N 个，最少 0 个

6、进程控制的功能：完成进程状态的转换

原语：由若干条指令构成的原子操作，作为一个整体而不可分割，要么全都完成，要么全都不做

进程创建原语：

• fork: 产生新进程，新进程的系统上下文来自现有进程，但上下文会有不同
• spawn: 产生新进程，创建新进程并加载新程序
• exec: 不产生新进程，加载新程序并覆盖自身

进程撤销原语：Destroy

进程阻塞原语：Block

进程唤醒原语：Wakeup

进程挂起原语：Suspend

进程激活原语：Activate

# 四、进程同步

一组并发进程执行时存在两种相互制约关系：进程互斥和进程同步

临界资源：在一段时间内只允许一个进程访问的资源

临界区的定义与进入：

• 临界区：把每个进程中访问临界资源的那段代码称为临界区
• 进入区：在临界区前面增加一段用于进行临界资源检查的代码，称为进入区
• 退出去：将临界区正被访问的标志恢复为未被访问的标志
• 剩余区：其余部分

使用临界区遵循的准则：

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

解决进程互斥进入临界区的方法：

• 硬件同步机制

  • 关中断
  • 利用 Test-and-Set 指令实现互斥
  • 利用 Swap 指令实现进程互斥

• 软件同步机制

  • 算法一：单标志

    设立一个公共整形变量 turn，进入循环检查是否允许本进程进入：turn 为 i 时，进程 Pi 可以进入；在退出区修改进入进程标识：进程 Pi 退出时，改 turn 为进程 Pj 的标识 j；

    缺点：强制轮流进入临界区，容易造成资源利用不充分

  • 算法二：双标志、先检查

    在进入区检查另一个进程是否在临界区，不在时修改本进程在临界区的标志；在退出区修改本进程在临界区的标志；

    优点：不用交替进入，可连续使用

    缺点：Pi 和 Pj 可能同时进入临界区

  • 算法三：先修改再检查

    缺点：Pi 和 Pj 可能都进入不了临界区

利用信号量机制实现进程互斥：

信号量代表可用资源实体的数量，整形信号量除了初始化外，仅能通过两个标准操作 wait (S) 和 signal (S) 来访问，这两个操作被称为 P、V 操作：

• P(S):

  • S=S-1;
  • 若 S$\ge$0, 则调用 P (S) 的进程继续运行
  • 若 S<0, 则调用 P (S) 的进程被阻塞，并把它插入到等待信号量 S 的阻塞队列中

• V(S):

  • S=S+1
  • 若 S>0, 则调用 V (S) 的进程继续运行
  • 若 S$\le$0, 从等待信号量 S 的阻塞队列中唤醒头一个进程，然后调用 V (S) 的进程继续运行

• 注意点：

  • wait (S) 和 signal (S) 必须成对出现
  • 缺少 wait (S) 不能保证对临界资源的互斥访问
  • 缺少 signal (S) 将使临界资源永远不被释放，从而使等待该进程资源而阻塞的进程不再被唤醒
  • P、V 原语不能次序错误、重复或遗漏

※例题：

1、假设有一个成品仓库，总共能存放 8 台成品，生产者进程生产产品放入仓库，消费者进程从仓库中取出成品消费。为了防止积压，仓库满的时候就停止生产。由于仓库搬运设备只有一套，故成品的存放和取出只能分别执行，使用 P、V 操作来实现该方案。

信号量 s1=8,s2=0,mutex=1

	producer()
	{
	P(s1);// 看看仓库能不能装下成品，能产生 s1--，可以把 s1 看做仓库剩余空间
	producing;
	P(mutex);// 搬运设备的互斥
	moving;
	V(mutex);
	V(s2);// 通知消费者可以拿东西
	}
	consumer()
	{
	P(s2);// 有没有东西拿
	P(mutex);// 拿东西
	moving;
	V(mutex);
	V(s1);// 通知生产者拿了一个东西
	}

2、生产围棋的工人不小心把相等数量的黑子和白子混合装在一个盒子里，现在要用自动分拣系统把黑子和白子分开，改系统由两个并发执行的进程 PA 和 PB 组成，系统功能如下：PA 专拣黑子，PB 专拣白子；每个进程每次只拣一个子，当一个进程拣子时，不允许另一个进程去拣子；当一个进程拣了子 (黑子或白子) 后，必须让另一个进程去拣一个 (白子或黑子)。请回答：写出用 PV 操作时应定义的信号量和初值；根据定义的信号量，写出用 PV 操作管理两个并发进程的程序。

信号量 s1=1，s2=0

	P1() // 捡白子
	{
	while(1)
	{
	P(s1);
	picking white;
	V(s2);
	}
	}
	P2() // 捡黑子
	{
	while(1)
	{
	P(s2);
	picking black;
	V(s1);
	}
	}

3、一条小河上有一座独木桥，规定每次只允许一个人过桥，现在河东河西都有人要过桥，如果把每个过桥者看作一个进程，为保证安全，请用 PV 操作实现正确答案。(多个相同的进程可以用下标标示)

信号量 S=1，表示桥是否空闲

	PEW()// 从东到西
	{
	P(S);
	moving from east to west;
	V(S);
	}
	PWE()// 从西到东
	{
	P(S);
	moving from west to east;
	V(S);
	}

4、用 P、V 操作和信号量解决进程之间的同步互斥问题。有 n 个进程将字符读入 到一个容量为 80 的缓冲区中，（n>1）当缓冲区读入后，由另一个进程 Pb 负责一次取走这 80 个字符。这种过程循环往复，请写出 n 个读入进程（p1，p2，…pn）和 Pb 的动作序列。（可用文字或表达式来描述动作序列）（设 pi 每次读一个字符到缓冲区中。

信号量 empty=80,full=0,mutex=1

共享变量 buffer [80],cnt=0

	Producer-i() //i=1,2,...,n
	{
	while(1)
	{
	P(empty);
	P(mutex);
	buffer[cnt++]=newchar;
	if(count==80)
	V(full);
	V(mutex);
	}
	}
	consumer()
	{
	while(1)
	{
	P(full);
	P(mutex);
	for(int i=0;i<80;i++)
	read(buffer[i]);
	cnt=0;
	for(int i=0;i<80;i++)
	V(empty);
	V(mutex);
	}
	}

5、如图所示，系统中有三个进程 GET、PRO 和 PUT，共用两个缓冲区 BUF1 和 BUF2。假设 BUF1 中最多可放 11 个信息，现以放入了两个信息；BUF2 最多可放 5 个信息。GET 进程负责不断地将输入信息送入 BUF1 中，PRO 进程负责从 BUF1 中取出信息进行处理，并将处理结果送到 BUF2 中，PUT 进程负责从 BUF2 中读取结果并输出。试用 P-V 操作正确实现 GET、PRO、PUT 的同步与互斥。

$$\xrightarrow{GET}BUF1\xrightarrow{PRO}BUF2\xrightarrow{PUT}$$

信号量 empty1=9,full1=2,empty2=5,full2=0,mutex1=1,mutex2=1

	GET()
	{
	while(1)
	{
	P(emtpy1);
	P(mutex1);
	send info into BUF1;
	V(mutex1);
	V(full1);
	}
	}
	PRO()
	{
	while(1)
	{
	P(full1);
	P(mutex1);
	get info from BUF1;
	V(mutex1);
	V(empty1);
	P(mutex2);
	send info into BUF2;
	V(mutex2);
	V(full2);
	}
	}
	PUT()
	{
	while(1)
	{
	P(full2);
	P(mutex2);
	get info from BUF2;
	V(mutex2);
	V(empty2);
	}
	}

# 五、管程

用信号量可以实现进程间的同步，但由于信号量的控制分布在整个程序中，其正确性分析很困难

管程是管理进程间同步的机制，它保证进程互斥地访问共享变量，并方便地阻塞和唤醒进程

信号量同步的缺点：

• 同步操作分散
• 易读性差
• 不利于修改与维护
• 正确性难以保证

管程的基本思想：将信号量和操作原语封装在一个对象内部

管程定义：管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块

管程的主要特性：

• 模块化
• 抽象数据类型
• 信息封装

管程的实现要素：

• 管程中的共享变量在管程外部是不可见的，外部只能调用管程提供的接口间接访问管程中共享变量
• 为保证管程共享变量的数据完整性，规定管程互斥进入
• 管程中设有进程等待队列以及相应的等待及唤醒操作

管程中多个进程的进入：

当一个进入管程的进程执行等待操作时，它应该释放管程的互斥权（通俗上说就是 V (mutex)）；

当一个进入管程的进程执行唤醒操作时（如 P 唤醒 Q），管程中存在两个同时处于活动状态的进程，处理方法如下：

• P 等待，Q 继续，直到 Q 等待或退出
• Q 等待，P 继续，直到 P 等待或退出
• 规定唤醒为管程中最后一个可执行操作

条件变量形式：X.signal 和 X.wait

进程与管程的异同点：

• 设置进程和管程的目的不同：
  • 进程是为了解决程序并发运行问题而设立
  • 管程是为了解决进程的公共变量、共享资源的互斥使用问题而设置
• 系统管理数据结构：
  • 进程：PCB
  • 管程：等待队列
• 管程被进程调用
• 管程是操作系统的固有成分，无法创建和撤销

# 六、进程通信（优先级较低，了解即可）

1、进程通信：一个进程直接或通过某一机构发一条消息给另一进程，且据此来控制其他进程，我们将进程之间的这种信息交流称为进程通信

低级通信机制：PV 操作，传送的是控制信息

高级通信机制：能传送任意数量数据，可归结为四大类

• 共享储存系统
  • 原理：在内存中开辟一个共享区域，可以向其中写数据与读数据
• 消息传递系统
  • 一般是通过空闲缓冲区来交互信息
• 管道通信
  • socket
• 客户端 - 服务器系统

2、线程：

进程：资源分配单位

线程：CPU 调度单位，和进程一样有三种基本状态，简单来说，线程就是迷你版的进程

线程控制模块：TCB

进程和线程的关系：

• 线程是进程的一个组成部分。
• 进程的多线程都在进程的地址空间活动
• 资源是分配给进程的，不是分配给线程的，线程在执行过程中需要资源时，系统从进程的资源配额中扣除并分配给该线程
• 处理机调度的基本单位是线程
• 线程在执行过程中，需要同步