操作系统复习 第二章
第二章 进程的描述与控制
程序的执行顺序
程序的顺序执行
一个具有独立功能的程序独占处理机，直到得到最终结果的过程
前驱图
一个有向无环图（DAG），用于描述进程间执行的前后的关系
节点：表示一个程序段或进程，或一条语句
有向边：节点之间的偏序或前驱关系
初始节点：没有前驱关系的点
终止节点：没有后继的节点
程序顺序执行的特性：
顺序性：处理机的操作严格按照顺序进行
封闭性：程序一旦开始执行，结果不受外因影响
可再现性：程序结果与执行速度无关，只与初始条件有关
程序的并发执行
内存中同时装入多道程序，他们共享系统资源，并发执行
特性：
间断性:程序并发执行时,由于它们共享资源或程序之间相互合作完成-项共同任务,因而使程序之间相互制约。相互制约导致并发程序具有”执行一暂停-执行”这种间断性的活动规律。
失去封闭性: 程序在并发执行时,多个程序共享资源,因而资源的状态将由多个程序来改变,致使程序的运行失去了封闭性。
不可再现性:程序在并发执行时,多次运行初始条件相同的同-一程序会得出不同的运行结果。
进程
定义：
程序段、数据段、PCB三部分构成了进程实体,简称”进程”。
注意：
进程是[程序J的「一次执行J
进程是一个程序及其数据在处理机上顺序执行时所发生的「活动」
进程是程序在一个「数据集合J」运行的过程
进程是系统进行「资源分配和调度J的- -个「独立」单位(或者说基本单位)
特征
动态性:进程的实质是程序的一次执行过程
- 进程是动态产生,动态消亡的,进程在其生命周期内,在3种基本状态之间转换
并发性:任何进程都可以同其他进程一起向前推进
独立性:进程是一个能独立运行的基本单位,同时也是系统分配资源和调度的独立单位
异步性:由于进程间的相互制约,使进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进
三种状态
就绪状态(Ready)
- 进程已获得除CPU之外的所有必需的资源,一旦得到CPU控制权,立即可以运行
运行状态(Running)
- 进程已获得运行所必需的资源，它正在处理机上执行。
阻塞状态(Blocked)
- 正在执行的进程由于发生某事件而暂时无法执行时,便放弃处理机而处于暂停状态,称该进程处于阻塞状态或等待状态。
其他状态
创建(New)
- 为了保证进程的调度必须在创建工作完成后进行,同时为了增加管理的灵活性, OS可以根据系统性能或主存容量的限制,推迟创建状态进程的提交,产生进程的创建状态。
终止( Terminated )
进程到达自然结束点、出现无法克服的错误、被操作系统所终结
等待操作系统善后处理,将其PCB清零,将PCB空间返还系统
挂起
有的系统有时希望能人为地把进程挂起,使之处于静止状态,以便研究其执行情况或对它进行修改。
挂起:把进程从内存转向外存
引入挂起操作的原因
终端用户的请求。
父进程请求。
负荷调节的需要。
操作系统的需要。
激活
- 对应挂起
进程管理中的数据结构
操作系统中，对每个资源和每个进程都设置了-个数据结构,用于表征其实体,称之为:资源信息表和进程信息表。
OS管理的这些数据结构分为四类:内存表、设备表、文件表、进程表。
进程控制块 PCB
PCB的作用是使一个在多道程序环境下不能独立运行的程序(含数据) ,成为一个能独立运行的基本单位, 一个能与其他进程并发执行的进程
PCB是进程存在的唯一标志
作用
作为独立运行基本单位的标志。
能实现间断性运行方式。
提供进程管理所需要的信息。
提供进程调度所需要的信息。
实现与其它进程的同步与通信。
内容
类型 内容 作用 标识信息 1 )外部标识为方便用户
2 )内部标识为方便系统标识一个进程 处理机状态(现场信息 ) 1 ) CPU通用/指令寄存器
2 ) CPU程序状态字PSW
3 )用户栈指针记录处理机现场信息,以备恢复之用 调度信息 1 )进程状态
2 )进程优先级
3 )调度所需信息
4)事件用户进程的调度管理 控制信息 1 )程序和数据地址
2 )进程同步和通信机制
3 )资源清单
4 )指向下一个进程的指针用于进程的控制管理 组织方式
线性方式：即将系统中所有的PCB都组织在一张线性表中,将该表的首址存放在内存的一个专用区域中。该方式实现简单、开销小,但每次查找时都需要扫描整张表,因此适合进程数目不多的系统
链接方式：把具有同一状态的PCB用其中的链接字链接成一个队列。
就绪队列
若干个堵塞队列
索引方式：系统根据所有进程的状态建立几张索引表,把各表的内存首地址记录在内存的专用单元中。索引表的表目中记录了相应状态的某个PCB在PCB表中的地址。
进程控制
进程控制是对系统中所有进程从产生、存在到消亡的全过程实行有效的管理和控制。
进程控制一般是由操作系统的内核来实现,内核在执行操作时,往往是通过执行各种原语操作来实现的。
操作系统内核
功能
支撑功能
中断管理
时钟管理
计时
时钟中断
原语操作
由若干条指令组成
用来完成某个特定功能
执行过程不会中断
资源管理功能
进程管理
存储器管理
设备管理
进程控制
原语种类
进程创建原语
进程撤销原语
阻塞原语
唤醒原语
挂起原语
激活原语
控制过程
更新PCB中的信息(如修改进程状态标识、将运行环境保存到PCB、从
PCB恢复运行环境)
➢所有的进程控制原语一定会修改进程状态标志
➢剥夺当前运行进程的CPU使用权必然需要保存其运行环境(玩游戏的存档)
➢某进程开始运行钱必然要恢复运行环境(玩游戏的读档)将PCB插入合适的队列
分配/回收资源
进程的创建
层次结构
在OS中允许一个进程创建另-个进程,通常把创建进程的进程称为父进程,而把被创建的进程称为子进程。
在UNIX中子进程可继续创建更多的孙进程,由此便形成了- -个进程的层次
结构。子进程可以继承父进程所拥有的资源，
当子进程被撤消时,应将其从父进程那里获得的资源归还给父进程。
在撤消父进程时,也必须同时撤消其所有的子进程。
Windows中不存在任何进程层次结构的概念
引起创建进程的事件
用户登录
作业调度
提供服务
应用请求
创建过程
申请进程标识,即申请空白PCB
为新进程分配内存和其它资源
初始化进程控制块
将创建的进程置于就绪队列
进程的终止
引起进程终止的事件
正常:
- 任务完成=> halt/ logs off指令=>中断
异常:
访问控制(存储越界、资源访问越界、指令越界)
运行超时、等待超时
被禁止的运算
I/O错误等
外界干预:
OS或用户干预
父进程请求
父进程终止
终止过程
根据被终止进程的标识符,从PCB集合中检索出该进程的PCB ,从中读出该进程的状态
若被终止进程正处于执行状态,应立即终止该进程的执行,并置调度标志为真，用于指示该进程被终止后应重新进行调度;
若该进程还有子孙进程,还应将其所有子孙进程也都予以终止，以防它们成为不可控的进程;
将被终止进程所拥有的全部资源或者归还给其父进程,或者归还给系统;
将被终止进程( PCB )从所在队列(或链表)中移出,等待其它程序来搜集信息。
进程的阻塞与唤醒
引起的事件
请求资源失败(如临界资源被占用，属于内部同步)
等待某种操作完成(如磁盘l/O操作,属于内部同步)
等待新数据的到来(如多进程协作时，属于外部同步)
等待新任务(如Deamon服务进程，属于外部同步)
进程的阻塞( block原语)
进程停止执行
状态改为“阻塞”
进程被插入阻塞队列
进程的唤醒( wakeup原语)
状态改为“就绪”
进程被插入就绪队列
进程的挂起与激活
挂起
当出现了引起进程挂起的事件时，比如,用户进程请求将自己挂起,或父进程请求将自己的某个子进程挂起，系统将利用挂起原语suspend( )将指定进程或处于阻塞状态的进程挂起。
挂起原语的执行过程:
检查被挂起进程的状态,若处于活动就绪状态,便将其改为静止就绪;对于活动阻塞状态的进程,则将之改为静止阻塞。
把该进程的PCB插入相应的挂起队列上,将程序段、数据段移除内存。最后,若被挂起的进程正在执行,则转向调度程序重新调度。
激活
当发生激活进程的事件时,若该进程驻留在外存而内存中已有足够的空间时,则可将在外存上处于静止就绪状态的进程换入内存。
系统将利用激活原语active( )将指定进程激活。
激活过程:
先将进程从外存调入内存,检查该进程的现行状态,若是静止就绪,便将之改为活动就绪;若为静止阻塞便将之改为活动阻塞。
假如采用的是抢占调度策略,则每当有新进程进入就绪队列时,应检查是否要进行重新调度,即由调度程序将被激活进程与当前进程进行优先级的比较,如果被激活进程的优先级更低,就不必重新调度;否则,立即剥夺当前进程的运行,把处理机分配给刚被激活的进程。
进程同步
引入进程的好处：支持多道程序并发,提高资源利用率
引入进程的缺点：系统更复杂,破坏了程序运行的封闭性和不可再现性
引入进程同步：对多个进程在执行次序上进行协调，使并发执行的进程之间能按照一定的规则共享系统资源,并能相互协作,使得程序的执行具有可再现性
两种形式的制约关系
间接相互制约：多个进程只能互斥执行
互斥：对某个系统资源，多个进程不能同时使用
临界资源：一段时间内只允许一个进程访问的资源
问题
- 死锁
直接相互制约：多个进程之间相互合作共同完成一件事
临界区：进程中访问临界资源的那段代码
访问临界区的程序设计为:
对欲访问的临界资源进行检查,
若此刻未被访问,设正在访问的标志——进入区
访问临界资源——临界区
将正在访问的标志恢复为未被访问的标志——退出区
其余部分——剩余区
同步机制应遵循的规则
空闲让进:当无进程在临界区时,任何有权使用临界区的进程可进入。
忙则等待:不允许两个以上的进程同时进入临界区。
有限等待:任何进入临界区的要求应在有限的时间内得到满足。
让权等待:处于等待状态的进程应放弃占用CPU ,以使其他进程有机会得到CPU的使用权。
硬件同步机制
关中断法(开关中断指令)也称为”硬件锁”, 是实现互斥最简单的方法。
做法:在进入锁测试之前关闭中断,直到完成锁测试并上锁之后才能打开中断。这样,进程在临界区执行期间,计算机系统不响应中断,从而不会引发调度,也就不会发生进程或线程切换。由此,保证了对锁的测试和关锁操作的连续性和完整性,有效地保证了互斥。
缺点:
滥用关中断权力可能导致严重后果;
关中断时间过长,会影响系统效率,限制了处理器交叉执行程序的能力;
关中断方法也不适用于多CPU系统,因为在一个处理器上关中断并不能防止进程在其它处理器上执行相同的临界段代码。
利用Test and Set指令实现互斥
做法：这是一种借助一条硬件指令一-‘ 测试并建立”指令TS(Test- and-Set)以实
现互斥的方法。在许多计算机中都提供了这种指令。缺点：
- 不符合“让权等待”原则
利用swap指令实现线程互斥
缺点：
- 不符合”让权等待“原则
信号量机制
1965年荷兰Dijkstra提出的信号量( Semaphores )是-种卓有成效的进程同步工具,在长期的应用中,得到了很大的发展,从整型信号量经过记录型信号量,进而发展为”信号量集”机制。
优点
信号量就是OS提供的管理公有资源的有效手段。
信号量代表可用资源实体的数量。
整型信号量
定义:把整型信号量定义为-个用于表示资源数目的整型量S ,除初始化外仅能通过两个原子操作wait(S),signal(S)来访问
原子操作P :
荷兰语”proberen”一-“检测” 之意。意味着请求分配一个单位资源
wait(S)
原子操作V :
荷兰语“verhogen”一- “增量”之意，意味着释放一个单位资源
signal(S)
记录型信号量
在信号量机制中，除了需要一个用于代表资源数目的整型变量value外 ,还应增加一个进程链表L，用于链接上述的所有等待进程。
记录型信号量是由于它采用”了记录型的数据结构而得名的。
AND型信号量
AND同步机制的基本思想是:将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程,待进程使用完后再一起释放。
只要尚有一个资源未能分配给进程,其它所有可能为之分配的资源,也不分配给他。
在wait操作中,增加了一个”AND”条件,故称为AND同步,或称为同时wait操作。
信号量集
一次申请多个单位的临界资源
资源数量低于预设下限值时不予分配
应用
利用信号量实现进程互斥
- 为使多个进程互斥的访问某临界资源,须为该资源设置一互斥信号量mutex ,并设其初始值为1 ,然后将各进程访问资源的临界区CS置于wait(mutex)和signal(mutex)之间即可。
利用信号量实现前驱关系
- 希望S1→S2 ,只需使进程P1和P2共享一个公用信号量S=0 ,将signal(S)放在语句S1后,将wait(S)放在语句S2前。
管程
信号量的缺点
同步操作分散:信号量机制中,同步操作分散在各个进程中,使用不当就可能导致各进程死锁(如P、V操作的次序错误、重复或遗漏) ;
易读性差:要了解对于一组共享变量及信号量的操作是否正确,必须通读整个系统
管程的优点
- 把分散在各进程中的临界区集中起来进行管理,并把系统中的共享资源用数据结构抽象地表示出来。由于临界区是访问共享资源的代码段,建立一个“秘书”程序管理来到的访问。”秘书” 每次仅让一个进程来访,这样既便于对共享资源的管理，又实现了互斥访问。
管程是由若干个公共变量和所有访问这些变量的过程所组成的一个特殊的模块或软件包
基本思想:
- 集中管理各进程中的临界区:管程把分散在各个进程中互斥地访问公共变量的那些临界区集中起来管理。
特点
管程的局部变量只能由该管程的过程存取;
系统保证进程只能互斥地调用管程中的过程。
条件变量
- 管程中对每个条件变量,都须予以说明, 其形式为: condition x, y。该变
量应置于wait和signal之前,即可表示为X.wait和X.signal。
- 管程中对每个条件变量,都须予以说明, 其形式为: condition x, y。该变
特征
模块化: 一个管程是一个基本程序单位，可以单独编译;
抽象数据类型:管程是一种特殊的数据类型,其中不仅有数据,而且有对数据进行操作的代码,是对数据和操作的封装。
信息掩蔽:管程如何实现其功能相对于外部程序是半透明的。
优点
安全性:共享变量外部不可见，只能由管程中的操作存取;
互斥性:管程在任何一个时刻只能有一个进程进入;
等待机制:设置有等待队列及相应的操作，对资源进行管理。
管程和进程的区别
设置目的不同:管程是对共享资源进行管理,进程是资源分配和执行的基本单位。
数据结构不同:管程定义公用数据结构,进程定义私有数据结构PCB。
存在方式不同:进程有生命周期，管程是操作系统固有的部分,没有生命周期。
执行方式不同:管程被进程调用,没有并发性,进程具有并发执行性。
进程通信
共享存储器系统
模式：
共享数据结构
进程公用某些数据结构,借以实现诸进程间的信息交换。
实现:公用数据结构的设置及对进程间同步的处理,都是程序员的职责。操作系统提供共享存储器
特点:低效。只适合传递相对少量的数据。
共享存储区
- 在存储器中划出一块共享存储区,诸进程可通过对共享存储区中数据的读或写
来实现通信。
- 在存储器中划出一块共享存储区,诸进程可通过对共享存储区中数据的读或写
管道通信系统
管道:指用于连接-个读进程和一个写进程以实现他们之间通信的一个打开的共享文件,又名pipe文件。
管道只能采取半双工通信,某一时间段内只能实现单向的传输。如果要实现双向同时通信,则需要设置两个管道各个进程要互斥的访问管道
数据以字节流的形式写入管道,当管道写满时,写进程的write()系统调用将会被阻塞,等待读进程将数据取走。当读进程将数据全部取走后,管道变空,此时读进程的read()系统调用将会被阻塞
消息传递系统
用格式化消息封装所需传输的数据,消息长度可以固定,也可以变化。
直接利用系统提供的一组通信命令(原语)进行通信。
操作系统隐藏了通信的实现细节,大大减化了通信程序编制的复杂性
应用广泛:微内核、多处理机系统、分布式系统、计算机网络等
消息传递系统的通信方式属于高级通信方式。又因其实现方式的不同而进一步分成
直接通信方式
发送进程利用OS提供的发送命令,直接把消息发送给目标进程。发送进程和接收进程都以显式方式提供对方的标识符。
通信原语:
Send(Receiver, message);发送一个消息给接收进程
Receive(Sender, message);接收Sender发来的消息
间接通信方式。
信箱用来暂存发送进程发送给目标进程的消息,接收进程则从信箱中取出发送给自己的消息。
消息在信箱中可安全保存,只允许核准的目标用户随时读取
利用信箱通信方式,既可实时通信,又可非实时通信。
通信原语:
Send (MailBox, Message) ;
Receive (MailBox, Message) ;
信箱可由操作系统创建,也可由用户进程创建,创建者是信箱的拥有者。
信箱分类:
私用信箱
公用信箱
共享信箱
客户-服务器系统
线程
线程的引入
进程的两个基本属性:
进程是一个可拥有资源的独立单位
进程同时又是一个可独立调度和分派的基本单位。
为使程序能并发执行,系统还必须进行以下的一系列操作。
创建进程
撤消进程
进程切换
这样系统必须为之付出较大的时空开销。因此应分开进程的两个属性。即对于作为调度和分派的基本单位,不同时作为拥有资源的单位，以”轻装上阵”,反之亦然。
进程切换过程
切换页目录以使用新的地址空间
切换内核栈和硬件上下文
线程
线程(thread)是一个可执行的实体单元。它代替以往的进程,成为现代操作系统中处理机调度的基本单位。
特性
调度的基本单位
同一进程中的线程切换不会引起进程切换
不同进程中的线程切换必然引起进程切换
并发性
拥有资源
独立性
系统开销
支持多处理机系统
线程运行的三个状态
执行状态,表示线程正获得处理机而运行;
就绪状态，指线程已具备了各种执行条件, 一旦获得CPU便可执行的状态;
阻塞状态,指线程在执行中因某事件而受阻,处于暂停执行时的状态。
线程控制块TCB
线程标识符;
组寄存器，它包括程序计数器PC、状态寄存器和通用寄存器;
线程运行状态,用于描述线程正处于何种运行状态;
优先级，描述线程执行的优先程度;
线程专有存储区，用于线程切换时存放现场保护信息,和相关统计信息;
信号屏蔽，即对某些信号加以屏蔽。
堆栈,用来保存局部变量和返回地址。
- 用户栈和核心栈
用户级线程
定义
用户级线程仅存在于用户空间中。对于这种线程的创建、撤消、线程之间的同步与通信等功能,都无须利用系统调用来实现。
对于用户级线程的切换,通常是发生在一个应用进程的诸多线程之间,无须内核的支持。
切换的规则远比进程调度和切换的规则简单
实现
用于管理和控制线程的函数(过程)的集合,其中包括用于创建和撤消线程的函数、线程同步和通信的函数以及实现线程调度的函数等
➢pthread_ creat , pthread_ exit , pthread_ join , pthread_ yield运行时系统中的所有函数都驻留在用户空间,并作为用户级线程与内核之间的接口。
优点
线程切换不需要转换到内核空间
调度算法可以是进程专用的
用户级线程的实现与OS平台无关
用户线程不占用内核内存,本身的内核空间开销也更小一些,可以节约资源
缺点
系统调用的阻塞问题。当线程执行一个系统调用时,不仅该线程被阻塞,而且,进程内的所有线程会被阻塞。而在内核支持线程方式中则进程中的其它线程仍然可以运行。
在单纯的用户级线程实现方式中,多线程应用不能利用多处理机进行多重处理的优点,内核每次分配给一个进程的仅有一个CPU ,因此,进程中仅有一个线程能执行,在该线程放弃CPU之前,其它线程只能等待。
内核支持线程KST
定义
在内核的支持下运行的，即无论是用户进程中的线程,还是系统进程中的线程,他,们的创建、撤消和切换等,也是依靠内核实现的。
在内核空间还为每一个内核支持线程设置了一 个线程控制块 ,内核是根据该控制块而感知某线程的存在的,并对其加以控制。
实现
- 在支持线程的OS中,系统在创建进程时,便为他分配一个任务数据区,包括若干线程控制块空间。
优点
在多处理器系统中,内核能够同时调度同-进程的多个线程并行执行。
一个线程被阻塞,内核可以调度该进程的其它线程运行,也可以运行其它进程中的线程。
线程切换比较快,开销小。
内核本身也可以采用多线程技术,提高执行速度和效率
缺点
- 在同一进程间的线程控制权转移时,用户级与核心级的切换开销很大。
组合方式
内核支持多线程的建立、调度和管理,同时,也允许用户应用程序建立、调度和管理用户级线程。
这种方式能够结合两者的优点,克服其各自的不足。