一、程序顺序执行时的特征
(一)、顺序性:处理机的操作严格按程序规定顺序执行
(二)、封闭性:程序一旦开始执行其计算结果不受外界因素影响。
(三)、可再現性:程序执行只要初始条件一样不论如何停顿,重复执行多少次结果都一样
进程是进程实体的运行过程,是系统进行资源分配和调喥的一个独立单位
①、可并发执行的程序在一个数据集合上的一次执行过程。
③、是一个程序与其数据一道通过处理机的执行所发生的活动
(一)、结构性特征,进程的根本——PCB
1、进程实质上是进程实体的一次有生命期的执行过程程序只是静态的一组有序指令。
1、多個进程实体同存于内存中在一段时间内同时运行。
2、有PCB的程序才能并发
进程是动态的,程序是静态的:程序是有序代码的集合;进程昰程序的执行
进程是暂时的,程序是永久的:进程是一个状态变化的过程程序可长久保存。
进程的组成包括程序、数据和进程控制块(进程各种控制信息)
(四)、进程与程序的对应关系:
都可1对n。通过多次执行一个程序可对应多个进程;通过调用关系,一个进程鈳包括多个程序
进程执行时的间断性,决定了其具有多种状态把握各进程所属的状态对进程控制至关重要。与进程执行相关的各种共享资源有:CPU、存储器、I/O设备、时间片
注意体会这些资源在进程状态变化中对进程运行的影响
六、进程的三种基本状态
(一)、就绪状态(Ready)
進程获得除CPU之外的所有必需资源,一旦得到CPU控制权可立即运行。
进程已获得所有运行必需的资源正在处理机上执行。
正在执行的进程甴于发生某事件(请求I/O、申请缓冲、时间片到)而暂时无法执行时便放弃CPU后暂停
*进程实体:代码段+数据段+PCB
*进程控制块(Process Control Block)定义:存放进程的管理和控制信息的数据结构称为进程控制块。
*进程控制块是进程存在的唯一标志
七、进程控制块(PCB)中的信息
(一)、进程标识符信息
(二)、处理机状态信息
一、进程控制的基本过程:
(三)、进程的阻塞与唤醒
(四)、进程的挂起和激活
(一)、申请空白PCB
(二)、為新进程分配资源
(三)、初始化进程控制块
标识符(包括父进程的)、程序计数器指向程序入口地址就绪态、优先级等信息的填写。
(四)、将新进程插入就绪队列
*原语是由若干指令构成的原子操作过程作为整体实现功能,不可被打断
(一)、引起进程阻塞和唤醒嘚事件
1、请求系统服务的满足情况
2、启动某种需等待(I/O)操作
3、合作需要的新数据尚未到达
4、执行某功能的进程暂时无新工作可做(如发送數据进程)
(二)、阻塞和唤醒过程
由进程调用阻塞原语阻塞自己,是主动行为:
1、将PCB中的状态改为阻塞
2、该PCB加入到阻塞队列中
3、转进程调喥将处理机分配给另一进程
4、进行进程切换,即根据两切换进程的PCB保护与重新设置处理机状态。
挂起原语将指定进程或阻塞进程挂起
(一)、检查被挂起进程的状态,活动就绪则改为静止就绪活动阻塞则改为静止阻塞
(二)、将该PCB复制到内存(方便检查)/外存(对換)指定区域
(三)、若挂起的进程是执行态,则需重新进行进程调度
*注意:进程只能挂起自己或其子孙进程。
一、进程间的两种制约關系:
间接相互制约关系:主要源于资源共享,表现为进程A---打印机资源---进程B(互斥)
直接相互制约关系:主要源于进程合作表现为进程A写緩冲---进程B读缓冲(有序)
二、进程同步的一些基本概念:
(一)、进程同步的主要任务:使并发执行的诸进程之间能有效地共享资源和相互合作,从而使程序的执行具有可再现性
(二)、临界资源:一次仅允许一个进程使用的资源。
(三)、临界区:每个进程中访问临界資源的那段代码
(四)、同步机制应遵循的规则:
1、空闲让进:资源使用最基本原则
2、忙则等待:保证互斥
3、有限等待:合适时被唤醒防止死等
4、让权等待:能主动释放CPU防止忙等
(一)、信号量定义为一个整型量;
(二)、根据初始情况赋相应的值;
(三)、仅能通过两個原子操作来访问。
四、整型信号量符合“有限等待”原则但不符合“让权等待”原则
(一)、符合“有限等待”:
signal释放资源后当CPU被分配给等待进程后,等待进程仍可继续执行可以符合“有限等待”。
(二)、不符合“让权等待”:
1、整型信号量的wait操作当s ≤0时,当前進程会占着CPU不断测试;
2、信号量原语不能被打断这个占有CPU的进程会一直不断的占据CPU循环下去,陷入忙等
五、 记录型信号量
1、不仅要有徝的处理,还有队列的处理此时形成记录型数据结构,包括两部分:
(2)、进程链表L(链接所有等待进程)
(2)、Value≤0其绝对值表示等待使鼡该资源的进程数,即在该信号量队列上排队的PCB的个数
3、先修改资源数,再判断处理
4、建立一个信号量必须经过说明,包括:
(1)、信号量所代表的意义;
(3)、建立相应的数据结构以便指向等待使用临界区的进程。
(1)、互斥信号量mutex初值为1;
(2)、每个进程中将临堺区代码置于P(mutex)和V(mutex)原语之间
(3)、必须成对使用P和V原语(在同一进程中)不能次序错误、重复或遗漏:
(二)、实现进程间的前趋关系(囿序)
1、对于前趋关系的理解:
并发执行的进程P1和P2中,分别有代码C1和C2要求C1要在C2开始前完成;
(1)、信号量值为0的点是限制的关键所在;
(2)、成对使用P和V原语(在有先后关系的两个进程中),不能次序错误、重复或遗漏否则同步顺序出错。
一些应用往往需要两个或多个共享资源而不是前述的一个资源。进程同时要求的共享资源越多发生死锁可能性越大。
一次性分配给进程所需资源用完一起释放。Wait操莋时对它所有需要的资源都要判断有AND条件,故称“AND同步”、“同时wait”
1、每次只能获得或释放一个单位的资源,低效;
2、某些时候资源汾配有下限的限制;
修改:在大于等于2可分配设置的下界值t前提下每次可分配d个。
(二)、两个操作原语:
1、AND信号量机制上加以扩充烸种资源参数有三:
①、S 为信号量(现有值);
②、t 为下限值(现有不能少于该条件);
(三)、只有一个信号量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操作的位置
(四)、检查代码,模拟机器运行体验信号量的变化和程序运行过程是否正确。
一、 生产者—消费者问题
(一)、使鼡场景:多个生产者和消费者对n个缓冲区的使用
1、无论生产者、消费者使用缓冲池时应保证互斥使用(互斥信号量mutex )
2、生产者和消费者間交叉有序:
①、有序的控制最根源在产品数量上。
注意:empty、full两者有天然的数量关系在PV控制下值不断变化,但在值等于0的点上是控制顺序的关键
2、控制顺序的信号量empty和full的wait和signal操作,成对地出现在不同的进程中
3、在每个程序中的多个wait操作顺序不能颠倒。且应先执行对资源信号量的wait操作再执行对互斥信号量的wait操作,否则可能引起进程死锁
4、模拟交替执行过程,检查控制是否正确
(一)、原题:五个哲學家共用一张圆桌,分别坐在周围的五张椅子上在桌子上有五只碗和五只筷子,他们的生活方式是交替地进行思考和进餐平时,一个哲学家进行思考饥饿时便试图取用其左右最靠近他的筷子,只有在他拿到两只筷子时才能进餐进餐毕,放下筷子继续思考
(二)、記录型信号量解决哲学家进餐问题
1、筷子是临界资源,在一段时间内只允许一个哲学家使用
2、所有信号量均被初始化为1。
(三)、就餐迉锁问题——解决方法:
1、数量控制:限制并发执行的进程数
2、一刀切:采用AND信号量
(一)、一个数据文件被多个进程共享。
(二)、匼理的同步关系是:
1、多个读进程可同时读;
2、Writer进程与任何其他进程(包括Reader进程或其他Writer进程)不允许同时访问文件
(三)、解决读者问題的关键:除第1读者,其他读者不申请读写互斥信号量防止读者间互斥。
先抢到棋盘者先下然后轮流下子
(一)、无法用单纯的信号量操作完成,因为初始值无法设置固定值
(二)、利用互斥信号量与特殊标志变量的结合使用实现有序控制。
(一)、共享变量count的使用需要互斥
(二)、注意if分支加入后P、V操作配对核对清楚
将共享变量及对共享变量能够进行的所有操作集中在一个模块中。(把信号量及其操作原语“封装”在一个对象内部)
(二)、对局部变量操作的一组过程
(三)、对局部变量进行初始化的语句
(一)、任何进程只能通过调用管程提供的过程入口才能进入管程访问共享数据;(就如同使用临界资源,就要先通过其信号量的申请)
(二)、任何时刻,仅允许一个进程在管程中执行某个内部过程
(一)、局部于管程的变量有两种:
2.条件变量(用于控制进程阻塞和唤醒)
①、类似信号量变量,但不取具体值;相当于每个阻塞队列的队列指针
②、对条件变量的操作需结合对普通变量的条件判断,从而控制进程状态
进程同步的阻塞和唤醒控制
一、进程通信是指进程之间的信息交换。
1、低级通信——进程之间的互斥和同步
信号量机制是有效的同步工具泹作为通信工具缺点如下:
①、效率低(通信量少)
②、通信对用户不透明(程序员实现,操作系统只提供共享存储器供代码操作)
用户矗接利用操作系统提供的一组通信命令高效地传送大量数据的通信方式。(操作系统隐藏了进程通信的细节对用户透明,减少了通信程序编制上的复杂性)
(一)、共享存储器系统(操作存储区方式)
相互通信的进程共享某些数据结构或共享存储区,进程之间能够通過这些空间进行通信
1、基于共享数据结构的通信方式(低级)
2、基于共享存储区的通信方式(高级)
(二)、消息传递系统(发--收方式)
1、最广泛使用的一种,进程间的数据交换以格式化的消息为单位。屏蔽底层复杂操作
2、单机:操作系统底层编程中的消息传递系统調用;
3、计算机网络:消息称为报文。程序员直接利用系统提供的一组通信命令(原语)进行通信(④客户机-服务器系统)
(三)、管道通信(中间文件方式)
1、所谓“管道”,是指用于连接一读进程和一写进程以实现通信的一个共享文件又名pipe文件。
2、向共享文件输入的写進程以字符流形式将大量的数据送入管道;而接收管道输出的读进程则从管道中接收(读)数据
2、远程过程调用(远程方法调用)
3、RPC应用开發步骤
三、 消息传递通信的实现方法
发送进程利用OS所提供的发送命令(原语),直接把消息发送给目标进程此时,发送进程和接收进程嘟以显式方式提供对方的标识符通常利用系统通信命令(原语):
基于共享数据结构的实体用来暂存发送给目标进程的消息;接收进程則从该实体中,取出对方发送给自己的消息通常把这种实体称为信箱。(消息在信箱中可以安全地保存只允许核准的目标用户随时读取。既可实时通信又可非实时通信。)
系统为信箱通信提供原语:
2.信箱消息的发送和接收
进程之间利用信箱进行通信时必须使用共享信箱。
四、信箱通信时发送进程和接收进程间有四种关系:
五、消息传递系统的实现
单机和网络环境下的高级进程通信广泛采用“消息传遞”方式需要考虑的问题:
(一)、通信链路的建立
1.计算机网络环境下,用原语显式建立/拆除链路
2.单机系统只须利用系统原语进程间鏈路由系统自动管理。
1.单机系统发送与接收进程在同一台机器,环境相同故格式简单;
2.网络环境下受不同目标机器的环境和长距离信息传输等因素的影响,消息格式较复杂消息常是“大头+正文”
(三)、同步方式(如何控制发送和接收的状态)
1.发送进程阻塞、接收进程阻塞(无缓冲紧密同步)
2.发送进程不阻塞、接收进程阻塞(服务器程序)
3.发送进程和接收进程均不阻塞(缓冲队列)
多线程OS中,一个进程包括多个线程每个线程都是利用CPU的基本单位。
(一)、轻型实体:只需一点必不可少的、能保证独立运行的资源(TCB)
(二)、独立調度和分派的基本单位:调度切换迅速且开销小。
(四)、共享进程资源:同进程中的线程可共享相同的进程地址空间、已打开文件、信號量机构等
二、线程的信息(TCB管理什么信息)
标识符、运行状态、优先级、寄存器状态、堆栈、专有存储器、信号屏蔽等。
在多线程OS中应用程序启动时,通常只有一个线程(初始化线程)在执行它根据需要再创建若干线程。
利用线程创建函数(或系统调用)提供相应参数。線程创建函数执行完后返回一个线程标识符供以后使用。
1.不立即释放资源只有当进程中的其它线程执行分离函数后,资源才分离出来能被其它线程利用
2.被终止而未释放资源的线程仍可被需要它的线程调用,使其重新恢复运行
(一)、一个应用程序有多个任务或功能需要同时进行处理,就最适合多线程机制
(二)、应用情况举例:
1.网络软件,需要同时进行用户界面响应、收数据、发数据
2.网络下载笁具:多线程下载的下载工具
*五、线程与进程的比较
(一)、调度:线程作为CPU调度的基本单位,而进程只作为其它资源分配单位
(二)、并发性:进程之间可以并发,实质上是不同进程中的两个线程并发一个进程的多个线程之间亦可并发。
(三)、拥有资源:进程间资源相互独立;同一进程的各线程间共享某进程内的线程在其它进程不可见
(四)、系统开销:线程上下文切换在同进程环境下上下文切換要快得多。因为同进程内线程间共享内存地址和打开的文件资源;
1.比较简单的控制线程互斥访问资源;
2.适用于高频度使用的关键共享數据和程序段;
2.锁保证互斥进入临界区,但利用条件变量使线程阻塞
3.注意不满足条件时wait条件变量:
②.进程阻塞在条件变量指向队列中
③.被唤醒后要重新再设互斥锁
用于同进程的线程间同步,数据结构存放在应用程序的地址空间属于特定进程,OS感知不到其存在
用于不同進程间或不同进程中线程的同步,数据结构由OS管理存放在受保护的系统存储区。
*注:互斥锁是为了上锁而优化的;条件变量是为了等待洏优化的;信号灯即可用于上锁也可用于等待,因而可能导致更多的开销和更高的复杂性三种机制适用逐渐复杂的同步情况