- 第2章 进程的描述与控制
- 2.1 进程的描述
- 2.2.3 挂起操作和进程状态的转换
- 2.2.4 进程管理中的数据结构
- 2.3 进程控制
- 2.3.1 操作系统内核
- 2.3.2 进程的创建
- 2.3.3 进程的终止
- 2.3.4 进程的阻塞与唤醒（浅学一下）
- 2.3.5 进程的挂起与激活（浅学一下）
- 2.4 进程同步
- 2.4.1 进程同步的基本概念
- 2.4.2 硬件同步机制（不学）
- 2.4.3 信号量机制
- 2.4.4 信号量的应用
- 2.4.5 管程机制（暂时不学）
- 2.5 经典进程的同步问题
- 2.5.1 生产者-消费者问题
- 2.5.2 哲学家就餐问题
- 2.6 进程通信
- 2.6.1 进程通信的类型
- 2.6.2 消息缓冲队列通信机制
- 2.7 线程的基本概念
- 2.7.1 线程的引入
- 2.7.2 线程与进程的比较（课后阅读）
- 2.7.3 线程的状态和线程控制块（课后阅读）
2.2.3 挂起操作和进程状态的转换示例：
1、若系统中没有运行进程，是否一定没有就绪进程？为什么？
答：是，只有就绪队列中无进程时，CPU才可能处于空闲状态。
2、若系统中既没有运行进程，也没有就绪进程，系统中是否就没有进程?为什么？
答：否，因为系统中的所有进程都可能处于死锁状态，或者是阻塞状态。
3、在采用优先级进程调度时，运行进程是否一定是系统中优先级最高的进程？为什么？
答：优先级最高的进程可能处在阻塞队列。
1、挂起操作
- 该进程处于静止状态；
- 如果进程正在执行，则将暂停执行
- 如果进程处于就绪状态，则将暂不接受调度；
- 对应操作：激活操作。
2、引入原因
- 终端用户的需要
- 父进程请求
- 负荷调节的需要
- 操作系统的需要
3、状态转换(了解即可，不考)
- 活动就绪→静止就绪
- 活动阻塞→静止阻塞
- 静止就绪→活动就绪
- 静止阻塞→活动阻塞
OS管理的四类数据结构：内存表、设备表、文件表、进程表
1、进程表（进程控制块）
- 是进程存在的唯一标志（类比学籍卡片）
- PCB常驻内存（操作系统启动后PCB就有，在系统区，内存里面的固定区域）
进程P 一一对应 PCB
Os 通过pcb管理 进程P
2、管理模式
- 线性方式
- 链接方式
- 索引方式（用得最多）
2.3 进程控制 2.3.1 操作系统内核
1、进程控制
- 进程管理中最基本的功能；
- 由OS的内核中的原语来实现的。
2、内核支撑功能
- 中断处理
内核最基本的功能操作，系统活动的基础； - 时钟管理
内核的一项基本功能；
如：时间片轮转调度、截至时间控制、最长运行时间控制 - 原语操作
原语(不可再分)：由若干条指令组成，用于完成一定功能的一个过程。
原子操作：一个操作中的所有动作要么全做，要么全不做。
1、进程树
- 描述一个进程的家族关系的有向树。
- 子进程可继承父的资源，撤消时应归还给父进程，父的撤消会撤消全部子进程。
作业：比程序更广泛的概念，通常由程序、数据和作业说明书构成
2、引起进程创建的事件
- 用户登录
为终端用户建立一进程 - 作业调度
为被调度的作业建立进程 - 提供服务
如要打印时建立打印进程 - 应用请求
由应用程序建立多个进程
3、进程的创建
- 申请空白PCB：一个系统的PCB是有限的
- 为新进程分配其运行所需的资源
- 初始化PCB
- 将新进程插入就绪队列
1、引起进程终止的事件
- 正常结束：Halt logoff
- 异常结束：Protect error overtime
- 外界干预：
系统员kil进程
父进程终止
父进程请求
2、进程的终止过程
- 检查进程状态
- 执行态→终止，且置调度标志为真
- 有无子孙需终止
- 归还资源给其父进程或系统
- 从PCB队列中移出PCB
阻塞和唤醒的关系：
1、进程在自己的执行过程中，阻塞自己。
2、进程在执行过程中，可以唤醒其他进程。
3、阻塞和唤醒必须是一一对应的！！
阻塞、唤醒一般由实现，而挂起与激活可由用户干预。
2.4 进程同步 2.4.1 进程同步的基本概念
现代os系统的一个主要特点：异步性。使得系统很混乱，程序执行具有不可再现性！！
示例：
1、同步：
- 并发进程在执行次序上的协调，以达到有效的资源共享和相互合作，使程序执行有可再现性。
- 间接相互制约关系：由于竞争相同资源引起的。
- 直接相互制约关系：由于相互合作而引起的。
2、临界资源
- 一次仅允许一个进程访问的资源。
- 引起不可再现性是因为临界资源没有互斥访问。
示例：
3、临界区
人们把在每个进程中访问临界资源的那段代码称为临界区(critical section)
4、遵循规则
- 空闲让进
表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。 - 忙则等待
已有进程进入临界区时，表明临界资源正在被访问，因而其它试图临界区的进程必须等待，以保证对临界资源的互斥访问。 - 有限等待
对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界----避免“死等” - 让权等待
让出CPU----避免“忙等”
信号量：整型信号量、记录型信号量、AND信号量、信号量集
1、整型信号量
- 把整型信号量定义为一个用于表示资源数目的整型量S;
- 仅能通过两个标准的原子操作wait(S)和signal(S)来访问；
- 这两个操作分别被称为wait(S)-P、signal(S)-V操作。
P操作：P(S):表示申请一个资源；
V操作：V(S):表示释放一个资源。
2、记录型信号量
- 整型信号量不遵循“让权等待”的准则，而使进程处于“忙等”状态；
- 除了用于代表资源数目的整型变量value外，还增加了一个进程链表指针list,用于链接所有等待的进程。
3、AND信号量
- 基本思想：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。
4、信号量集
- 当一次需要N个单位时，便要进行N次wait(S)操作。低效，容易死锁；
- 为了系统安全，当所申请的资源数量低于某一下限时，进行管制，不予分配。
1、实现互斥
- 公用互斥信号量mutex;
- N个共享该资源的进程的程序中，都要包含下列程序段。
示例：
2、实现前趋
示例
2.4.5 管程机制（暂时不学）课内问答
- 整型和记录型信号量机制的最大区别是什么？
答：让权等待- 分析记录型信号量取值范围及含义。
答：记录型信号量s.value
当>=0：表示系统当前可用的该类资源的数目。
当<0：其绝对值表示系统中因请求该类资源而被阻塞的进程数目（所以每个信号量都对应一个等待队列，即L)- 一个计算进程和一个打印进程并发执行，共用一个缓冲区，计算进程的计算结果放入缓冲区供打印进程打印输出，设二者的同步信号量为1，S2,且初值均为0，下边给出了两个进程之间的同步描述：
(1)上述同步描述存在什么问题，并指出原因；
答：会出现死锁；当计算进程执行P(S2)时阻塞，打印进程执行P(S1)时也阻塞，出现死锁；
(2)在信号量初值不变的情况下，请对计算进程进行修改，解决(1)中存在的问题。
答：将计算进程中的P(S2)与V(S1)互换位置。
2.5 经典进程的同步问题 2.5.1 生产者-消费者问题
生产者与消费者问题(Producer-consumer-relationship，即P_C问题)
实际上，是Dijikstra把广义同步问题抽象成P_C问题的抽象模型。
1、问题描述
- 互斥信号量mutex
使生产者与消费者进程互斥的去访问货架。 - 同步信号量empty-full
实现同步，即生产者不会无限生产商品，消费者不会无限消费商品。empty-full存在不同进程中。
2、注意要点
- 每个程序中实现互斥的P(mutex)，V(mutex)必须成对出现。
- Empty和full的P，V操作也必须成对出现，但它们处于不同的程序中。
- 每个程序中的多个P操作不能颠倒顺序，否则可能引起死锁。
3、思考
思考-问题1
- 如果P(empty)和P(mutex)互换位置；后果如何？
答：如果先P(mutex)，即生产者先得到货架；然后再P(empty)，看货架是不是空的。
如果货架是放满的 (empty=0)，那么生产者被阻塞，消费者得不到货架消费，也被阻塞，产生死锁。- 如果P(full)和P(mutex)互换位置；后果如何？
答：如果先P(mutex)，即消费者先得到货架；然后再P(full)，看货架是不是满的。
如果货架是空的 (full=0)，那么消费者被阻塞，生产者得不到货架上货，也被阻塞，产生死锁。
思考-问题2
- 如果V(full)和V(mutex)互换位置；后果如何？
答：- 如果V(empty)和V(mutex)互换位置；后果如何？
先V(mutex)，即先释放货架，提高资源利用率
4、案例
2.5.2 哲学家就餐问题示例：
- 有一空盘，允许存放一只水果。爸爸可向盘中放苹果，妈妈可向盘中放桔子，儿子专等盘中的桔子吃，女儿专等盘中的苹果吃。请用P、V原语实现爸爸、妈妈、儿子、女儿四个进程的同步。
问题分析：盘子空，mpfp就可放；放了后，dpsp就可取。
生产者：爸爸、妈妈
消费者：儿子、女儿
初值：Empty=1、Apple=0、Orange=0
答：加上P(mutex)，V(mutex)
1、要点
- 由Dijkstra提出并解决。
- 目的：解决资源紧张问题。
将每支筷子都看作临界资源，设置互斥信号量。
semaphore chopstick[5]=(1 1,1,1,1};
解决方案1 使用AND型信号量
1、原理：必须同时申请和释放资源
2、PV原语
解决方案2 限制个数
1、原理：x根筷子限制同时申请就餐的哲学家的个数，不超过x-1，不会发生死锁。
2、PV原语
eg：5个进程，每个进程需要3个资源，至少多少个资源才不会发生死锁
答：11个
最坏情况下5个进程，每个进程得到比它所需资源少1个资源，即每人得2个，共10个资源发生死锁，如果再多1个资源便不会发生死锁。
解决方案3 同时竞争同一个资源
1、原理
如果一个进程连第一个资源都没有抢到，也就不会去抢第二个。
让部分哲学家们争相同的第一只筷子。
奇数号哲学家顺时针申请，偶数号哲学家逆时针申请。
2、PV原语
题目练习
2.6 进程通信 2.6.1 进程通信的类型示例：
- 一个快餐厅有4名职员：
领班：接受顾客点菜；
厨师：准备顾客的饭菜；
包工：将做好的饭菜打包；
出纳员：收款并提交食品。
每个职员可被看作一个进程。
问：试用信号量实现四类工作人员正确并发运行的机制。
- 桌上有个能盛得下六块饼干的空盘子。爸爸不停地向盘中放梳打饼干或威化饼干，儿子不停的从盘中取出威化饼干享用，女儿不停的从盘中取出梳打饼干享用，规定三个人不能同时从盘子中取放饼干。
分析：
问题本质是一个能生产两种产品的生产者（父亲）向两个消费者（儿子和女儿)提供产品的同步问题。
信号量初值：empty=6;wafer=0;soda=0;mutex=1;
答：
3.一个理发店由一个有张沙发的等候室和一个放有一张理发椅的理发室组成，没有顾客要理发时，理发师便去睡觉，当一个顾客走进理发店时,如果所有的沙发 都已被占用，他便离开理发店，否则，如果理发师正在为其他顾客理发，则该顾客就找一张空沙发坐下等待；如果理发师因无顾客正在睡觉，则由新到的顾客唤醒理发师为其理发。在理发完成以后，顾客必须付费，直到理发师收费后才能离开理发店。
问题：
试用信号量实现这一同步问题。
分析：
设置一个整型变量count来对占用沙发的顾客计数；
设置5个信号量：
mutex=1:实现顾客进程对count变量的互斥访问；
empty=1:是否有空闲理发椅；
full=0:理发椅上是否坐有等待理发的顾客；
payment=0:等待付费；
receipt=0:等待收费；
答：
顾客：
理发师：
思考：
如果有多个理发师，并配有一名收银员，信号量该如何实现这一同步。
1、共享储存器
2、管道通信
1、线程定义
- 比进程更小的基本单位；
- 减少并发执行时的时空开销，进程的创建、撤消、切换较费时空，因它既是调度单位，又是资源拥有者。
- 线程是系统独立调度和分派的基本单位，其基本上不拥有系统资源，只有少量资源(P,寄存器，栈)，但共享其所属进程所拥有的全部资源。
2、引入线程目的：提高并发性
3、作用：分离进程的两个属性：调度和资源分配
- 线程：调度的单位不再是拥有资源的单位
- 进程：拥有资源的单位，不再频繁切换（进程
