程序:是静态的,就是个存放在磁盘里的可执行文件,就是一系列的指令集合
进程:是动态的,是程序的一次执行过程
当进程被创建时,操作系统会为该进程分配一个唯一的、不重复的不同的pid(进程id)
这些信息都被保存在一个数据结构PCB中,即进程控制块,操作系统需要对各个并发运行的进程进行管理,但凡管理时所需要的信息,都会被放在PCB中
PCB是进程存在的唯一标志!当进程被创建时,操作系统为其创建PCB,当进程结束时,会回收其PCB。
程序段:程序的代码(指令序列)
数据段:运行过程中产生的各种数据(如:程序中定义的变量)
PCB是给操作系统用的
程序段、数据段是给进程自己用的
程序段、数据段、PCB三部分组成了进程实体(进程映像)
进程的定义为:进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位
动态性:进程是程序的一次执行过程,是动态的产生、变化和消亡的,进程最基本的特性
并发性:进程中有多个进程实体,各进程可并发执行
独立性:进程是能独立运行、独立获得资源、独立接受调度的基本单位
异步性:各进程按各自独立的、不可预知的速度向前推进,操作系统要提供“进程同步机制”来异步解决问题
结构性:每个进程都会配置一个PCB,从结构上看,进程由程序段、数据段、PCB组成
进程PCB中,会有一个变量state来表示进程的当前状态。如:1.表示创建态,2表示就绪态,3表示运行态……
主要功能是对系统中的所有进程实施有效的管理,它具有创建新进程、撤销已有进程、实现进程状态转换等功能
原语的执行具有原子性,即执行过程只能一气呵成,期间不允许被终端,可以用“关中断指令”和“开中断指令”这两个特权指令实现原子性。(内核程序,运行在核心态)
CPU执行了关中断指令后,就不再执行检查中断信号,直到执行开中断指令之后才会恢复检查。
创建原语:
引起进程创建的事件:
撤销原语:
引起进程终止的事件:
进程的阻塞:
进程的唤醒:
????????等待的事件发生
切换原语:
引起进程切换的事件:
进程间通信是指两个进程之间产生数据交互
为什么进程通信需要操作系统支持?
进程是分配系统资源的单位(包括内存地址空间),因此各进程拥有的内存地址空间相互独立,为了保证安全,一个进程不能直接访问另一个进程的地址空间
进程通信:共享存储、消息传递、管道通信
Linux中,如何实现共享内存
int shm_open(......);//通过 shm_open 系统调用,申请一片共享内存区
void * mmap(......);//通过 mmap 系统调用,将共享内存区映射到进程自己的地址空间
为避免出错,各个进程对共享空间的访问应该是互斥的
基于存储区的共享:操作系统在内存中划出一块共享存储区,数据的形式、存放位置都由通信进程控制,而不是操作系统。这种共享方式速度很快,是一种高级通信方式
进程间的数据交换以格式化的消息为单位,进程通过操作系统提供的额“发送消息/接收消息”两个原语进行数据交换。
有的进程可能需要同时做很多事情,而传统的进程只能串行的执行一系列程序,为此引入了线程,增加并发量
可以把线程理解为“轻量级进程“,线程是一个基本的CPU执行单元,也是程序执行流的最小单位
引入线程后,不仅是进程之间可以并发,进程内的各线程之间也可以并发,从而进一步提升了系统的并发度,使得一个进程内也可以并发处理各种任务
引入线程后,进程只作为除CPU之外的系统资源的分配单元
线程的属性:
操作系统只“看得见”内核级线程,因此只有内核级线程才是处理机分配的单位
TCB --- 线程控制块
当有一堆任务要处理,但由于资源有限,这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序,这就是“调度”研究的问题。
高级调度(作业调度)。按一定的原则从外存的作业后备队列中挑选一个作业调入内存,并创建进程。每个作业只调入一次,调出一次。作业调入时会建立PCB,调出时才撤销PCB。
低级调度(进程调度/处理机调度)一一按照某种策略从就绪队列中选取一个进程,将处理机分配给它。
进程调度是操作系统中最基本的一种调度,在一般的操作系统中都必须配置进程调度。
进程调度的频率很高,一般几十毫秒一次。
内存不够时,可将某些进程的数据调出外存。等内存空闲或者进程需要运行时再重新调入内存。
暂时调到外存等待的进程状态为挂起状态。被挂起的进程PCB会被组织成挂起队列
中级调度(内存调度)一一按照某种策略决定将哪个处于挂起状态的进程重新调入内存。
暂时调到外存等待的进程状态为挂起状态(挂起态,suspend),挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态,五状态模型→七状态模型
注意“挂起”和“阻塞”的区别,两种状态都是暂时不能获得CPU的服务,但挂起态是将进程映像调到外存去了,而阻塞态下进程映像还在内存中。有的操作系统会把就绪挂起、阻塞挂起分为两个挂起队列,甚至会根据阻塞原因不同再把阻塞挂起进程进一步细分为多个队列。
进程调度(低级调度),就是按照某种算法从就绪队列中选择一个进程为其分配处理机
进程在操作系统内核程序临界区中不能进行调度与切换 -------- √
(2012年联考真题)进程处于临界区时不能进行处理机调度 ----- ×
临界资源:一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。
临界区:访问临界资源的那段代码。
内核程序临界区一般是用来访问某种内核数据结构的,比如进程的就绪队列(由各就绪进程的PCB组成)
又称非抢占方式。即,只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达,当前进程依然会继续使用处理机,直到该进程终止或主动要求进入阻塞态。
实现简单,系统开销小但是无法及时处理紧急任务,适合于早期的批处理系统
又称抢占方式。当一个进程正在处理机上执行时,如果有一个更重要或更紧迫的进程需要使用处理机,则立即暂停正在执行的进程,将处理机分配给更重要紧迫的那个进程。
可以优先处理更紧急的进程,也可实现让各进程按时间片轮流执行的功能(通过时钟中断)。适合于分时操作系统、实时操作系统
“狭义的进程调度”与“进程切换”的区别:
狭义的进程调度指的是从就绪队列中选中一个要运行的进程。(这个进程可以是刚刚被暂停执行的进程,也可能是另一个进程,后一种情况就需要进程切换)
进程切换是指一个进程让出处理机,由另一个进程占用处理机的过程。
广义的进程调度包含了选择一个进程和进程切换两个步骤。
进程切换的过程主要完成了:
1.对原来运行进程各种数据的保存
2.对新的进程各种数据的恢复
(如:程序计数器、程序状态字、各种数据寄存器等处理机现场信息,这些信息一般保存在进程控制块)
注意:进程切换是有代价的,因此如果过于频繁的进行进程调度、切换,必然会使整个系统的效率降低,
使系统大部分时间都花在了进程切换上,而真正用于执行进程的时间减少。
不支持内核级线程的操作系统,调度程序的处理对象是进程
支持内核级线程的操作系统,调度程序的处理对象是内核线程
调度程序永远的备胎,没有其他就绪进程时,运行闲逛进程(idle)
闲逛进程的特性:
CPU利用率:指CPU“忙碌”的时间占总时间的比例。
利用率 = 忙碌的时间 / 总时间
Eg:某计算机只支持单道程序,某个作业刚开始需要在CPU上运行5秒,再用打印机打印输出5秒,之后再执行5秒,才能结束。在此过程中,CPU利用率、打印机利用率分别是多少?
CPU利用率=(5+5) / (5+5+5) = 66.66%
打印机利用率:5 / 15 = 3,33%
系统吞吐量:单位时间内完成作业的数量
系统吞吐量 = 总共完成了多少道作业 / 总共花了多少时间
Eg:某计算机系统处理完10道作业,共花费100秒,则系统吞吐量为?
10/100=0.1道/秒
对于计算机的用户来说,他很关心自己的作业从提交到完成花了多少间。
周转时间,是指从作业被提交给系统开始,到作业完成为止的这段时间间隔。
它包括四个部分:作业在外存后备队列上等待作业调度(高级调度)的时间、进程在就绪队列上等待进程调度(低级调度)的时间、进程在CPU上执行的时间、进程等待/O操作完成的时间。后三项在一个作业的整个处理过程中,可能发生多次。
(作业)周转时间 = 作业完成时间 - 作业提交时间 ---- 对于用户来说,更关心自己的单个作业的周转时间
平均周转时间 = 各作业周转时间之和 ---- 对于操作系统来说,更关心系统的整体表现,因此更关心所有作业周转时间的平均值
带权周转时间 = 作业周转时间 / 作业实际运行的时间 = 作业完成时间 - 作业提交时间 / 作业实际运行的时间 ?---- 带权周转时间必然 ?>= ?1,带权周转时间与周转时间都是越小越好
平均带权周转时间 = 各作业带权周转时间之和 / 作业数
等待时间,指进程/作业处于等待处理机状态时间之和,等待时间越长,用户满意度越低。
对于进程来说,等待时间就是指进程建立后等待被服务的时间之和,在等待/O完成的期间其实进程也是在被服务的,所以不计入等待时间。
对于作业来说,不仅要考虑建立进程后的等待时间,还要加上作业在外存后备队列中等待的时间。
一个作业总共需要被CPU服务多久,被/O设备服务多久一般是确定不变的,因此调度算法其实只会影响作业/进程的等待时间。当然,与前面指标类似,也有“平均等待时间”来评价整体性能。
响应时间,指从用户提交请求到首次产生响应所用的时间。
进程具有异步性的特征。异步性是指,各并发执行的进程以各自独立的、不可预知的速度向前推进。
读进程和写进程并发地运行,由于并发必然导致异步性,因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中,又必须按照“写数据→读数据”的顺序来执行的。
如何解决这种异步问题,就是“进程同步”所讨论的内容。
同步亦称直接制约关系,它是指为完成某种任务而建立的两个或多个进程,这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。
进程的“并发”需要“共享”的支持。各个并发执行的进程不可避免的需要共享一些系统资源(比如内存,又比如打印机、摄像头这样的/O设备)
我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备(比如摄像头、打印机)都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。
对临界资源的访问,必须互斥地进行。互斥,亦称间接制约关系。
进程互斥指当一个进程访问某临界资源时,另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束,释放该资源之后,另一个进程才能去访问临界资源。
为了实现对临界资源的互斥访问,同时保证系统整体性能,需要遵循以下原则:
1.空闲让进。临界区空闲时,可以允许一个请求进入临界区的进程立即进入临界区:
2.忙则等待。当已有进程进入临界区时,其他试图进入临界区的进程必须等待:
3.有限等待。对请求访问的进程,应保证能在有限时间内进入临界区(保证不会饥饿):
4.让权等待。当进程不能进入临界区时,应立即释放处理机,防止进程忙等待。
算法思想:两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予
只能按P0→P1→P0→P1→…这样轮流访问。这种必须“轮流访问”带来的问题是,如果此时允许进入临界区的进程是P0,而P0一直不访问临界区,那么虽然此时临界区空闲,但是并不允许P1访问。
因此,单标志法存在的主要问题是:违背“空闲让进”原则。
算法思想:设置一个布尔型数组ag,数组中各个元素用来标记各进程想进入临界区的意愿,比如“flag[o]=ture”意味着0号进程Po现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区,如果没有,则把自身对应的标志flag[)设为tue,之后开始访问临界区。
若按照①⑤②⑥③⑦…的顺序执行,PO 和 P1将会同时访问临界区。
因此,双标志先检查法的主要问题是:违反“忙则等待”原则。
原因在于,进入区的“检查”和“上锁”两个处理不是一气呵成的。“查”后,“上锁”前可能发生进程切换。
算法思想:双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”,但是这两个操作又无法一气呵成,因此导致了两个进程同时进入临界区的问题。因此,人们又想到先“上锁”后“检查”的方法,来避免上述问题。
若按照①⑤②⑥..的顺序执行,P0和P1将都无法进入临界?
因此,双标志后检查法虽然解决了“忙则等待”的问题,但是又违背了“空闲让进”和“有限等待”原则,会因各进程都长期无法访问临界资源而产生“饥饿”现象。
算法思想:结合双标志法、单标志法的思想。如果双方都争着想进入临界区,那可以让进程尝试“孔融让梨”(谦让)。做一个有礼貌的进程。
Peterson算法用软件方法解决了进程互斥问题,遵循了空闲让进、忙则等待、有限等待三个原则,但是依然未遵循让权等待的原则。
利用“开/关中断指令”实现(与原语的实现思想相同,即在某进程开始访问临界区到结束访问为止都不允许被中断,也就不能发生进程切换,因此也不可能发生两个同时访问临界区的情况)
优点:简单、高效
缺点:不适用于多处理机:只适用于操作系统内核进程,不适用于用户进程(因为开/关中断指令只能运行在内核态,这组指令如果能让用户随意使用会很危险)
简称TS指令,也有地方称为TestAndSetLock指令,或TSL指令
TSL指令是用硬件实现的,执行的过程不允许被中断,只能一气呵成。以是用c语言描述的逻辑
若刚开始lock是false,则TSL返回的old值为false,while循环条件不满足,直接跳过循环,进入临界区。若刚开始lock是true,则执行TLS后old返回的值为true,while循环条件满足,会一直循环,直到当前访问临界区的进程在退出区进行“解锁”
相比软件实现方法,TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。
优点:实现简单,无需像软件实现方法那样严格检查是否会有逻辑漏洞:适用于多处理机环境
缺点:不满足“让权等待”原则,暂时无法进入临界区的进程会占用CPU并循环执行TSL指令,从而导致“忙等”。
有的地方也叫Exchange指令,或简称XCHG指令。
Swap指令是用硬件实现的,执行的过程不允许被中断,只能一气呵成。以下是用c语言描述的逻辑
逻辑上来看Swap和TSL并无太大区别,都是先记录下此时临界区是否已经被上锁(记录在old变量上),再将上锁标记lock设置为true,最后检查old,如果old为false则说明之前没有别的进程对临界区上锁,则可跳出循环,进入临界区。
优点:实现简单,无需像软件实现方法那样严格检查是否会有逻辑漏洞:适用于多处理机环境
缺点:不满足“让权等待”原则,暂时无法进入临界区的进程会占用CPU并循环执行TSL指令,从而导致“忙等”。
1.互斥锁
解决临界区最简单的工具就是互斥锁(mutex lock)。一个进程在进入临界区时应获得锁;在退出临界区时释放锁。函数acquire()获得锁,而函数release()释放锁。每个互斥锁有一个布尔变量available,表示锁是否可用。如果锁是可用的,调用acqiure()会成功,且锁不再可用。当一个进程试图获取不可用的锁时,会被阻塞,直到锁被释放。
acquire0或release()的执行必须是原子操作,因此互斥锁通常采用使件机制来实现。
互斥锁的主要缺点是忙等待,当有一个进程在临界区中,任何其他进程在进入临界区时必须连续循环调用acquire()。当多个进程共享同一CPU时,就浪费了CPU周期。因此,互斥锁通常用于多处理器系统,一个线程可以在一个处理器上等待,不影响其他线程的执行。
需要连续循环忙等的互斥锁,都可称为自旋锁(spin lock),如TSL指令、swap指令、单标志法
特性:
用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作,从而很方便的实现了进程互斥、进程同步。
信号量其实就是一个变量(可以是一个整数,也可以是更复杂的记录型变量),可以用一个信号量来表示系统中某种资源的数量,比如:系统中只有一台打印机,就可以设置一个初值为1的信号量。
原语是一种特殊的程序段,其执行只能一气呵成,不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”,因此如果能把进入区、退出区的操作都用“原语”实现,使这些操作能“一气呵成”就能避免问题。
一对原语:wait(S)原语和signal((S)原语,可以把原语理解为我们自己写的函数,函数名分别为wait和signal,,括号里的信号量S其实就是函数调用时传入的一个参数。
wait、signal原语常简称为P、V操作(来自荷兰语proberen和verhogen)。因此,做题的时候常把wait(S)、signal(s)两个操作分别写为P(S)、V(S)
用一个整数型的变量作为信号量,用来表示系统中某种资源的数量
与普通整数变量的区别:对信号量的操作只有三种,即初始化、P操作、V操作
整型信号量的缺陷是存在“忙等”问题,因此人们又提出了“记录型信号量”,即用记录型数据结构表示的信号量。
在考研题目中wait(S)、signal(s)也可以记为P(S)、V(s),这对原语可用于实现系统资源的“申请”和“释放”。
S.value的初值表示系统中某种资源的数目。
对信号量S的一次P操作意味着进程请求一个单位的该类资源,因此需要执行S.vaue-,表示资源数减1,当S.value<0时表示该类资源已分配完毕,因此进程应调用block原语进行自我阻塞(当前运行的进程从运行态→阻塞态),主动放弃处理机,并插入该类资源的等待队列SL中。可见,该机制遵循了“让权等待”原则,不会出现“忙等”现象。
对信号量S的一次V操作意味着进程释放一个单位的该类资源,因此需要执行S.value+,表示资源数加1,若加1后仍是S.value<=0,表示依然有进程在等待该类资源,因此应调用wakeup原语唤醒等待队列中的第一个进程(被唤醒进程从阻塞态→就绪态)。
注意:对不同的临界资源需要设置不同的互斥信号量P、V操作必须成对出现。缺少P(mutex)就不能保证临界资源的互斥访问。缺少V(mutex)会导致资源永不被释放,等待进程永不被唤醒
要会自己定义记录型信号量,但如果题目中没特别说明,可以把信号量的声明简写成这种形式:semaphore mutex = 1;
用信号量实现进程同步:
若先执行到V(S)操作,则S后S=1。之后当执行到P(S)操作时,由于S=1,表示有可用资源,会执行S-,S的值变回0,P2进程不会执行block原语,而是继续往下执行代码4。若先执行到PS)操作,由于S=0,S-后S=-1,表示此时没有可用资源,因此P操作中会执行block原语,主动请求阻塞之后当执行完代码2,继而执行V(S)操作,S,使S变回0,由于此时有进程在该信号量对应的阻塞队列中,因此会在V操作中执行wakeup原语,唤醒P2进程。这样P2就可以继续执行代码4了
进程P1中有句代码S1,P2中有句代码S2,P3中有句代码S3.P6中有句代码S6。这些代码要求
按如下前驱图所示的顺序来执行:
其实每一对前驱关系都是一个进程同步问题(需要保证一前一后的操作)因此(前P后V)
1.要为每一对前驱关系各设置一个同步信号量
2.在“前操作”之后对相应的同步信号量执行V操作
3.在“后操作”之前对相应的同步信号量执行P操作
系统中有一组生产者进程和一组消费者进程,生产者进程每次生产一个产品放入缓冲区,消费者进程每次从缓冲区中取出一个产品并使用。(注:这里的“产品”理解为某种数据)
生产者、消费者共享一个初始为空、大小为的缓冲区。
只有缓冲区没满时,生产者才能把产品放入缓冲区,否则必须等待。(缓冲区没满→生产者生产)
只有缓冲区不空时,消费者才能从中取出产品,否则必须等待。(缓冲区没空→消费者消费)
缓冲区是临界资源,各进程必须互斥地访问。(互斥关系)
生产者、消费者共享一个初始为空、大小为n的缓冲区。
只有缓冲区没满时,生产者才能把产品放入缓冲区,否则必须等待。
只有缓冲区不空时,消费者才能从中取出产品,否则必须等待。
缓冲区是临界资源,各进程必须互斥地访问。
因此,实现互斥的P操作一定要在实现同步的P操作之后。
V操作不会导致进程阻塞,因此两个V操作顺序可以交换。
生产者消费者问题是一个互斥、同步的综合问题。
对于初学者来说最难的是发现题目中隐含的两对同步关系。
有时候是消费者需要等待生产者生产,有时候是生产者要等待消费者消费,这是两个不同的“一前一后问题”,因此也需要设置两个同步信号量。
桌子上有一只盘子,每次只能向其中放入一个水果。爸爸专向盘子中放苹果,妈妈专向盘子中放橘子,儿子专等着吃盘子中的橘子,女儿专等着吃盘子中的苹果。只有盘子空时,爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时,儿子或女儿可以从盘子中取出水果。用PV操作实现上述过程。
同步:前V后P
结论:即使不设置专门的互斥变量mutex,也不会出现多个进程同时访问盘子的现象
原因在于:本题中的缓冲区大小为1,在任何时刻,apple、orange、plate三个同步信号量中最多只有一个是1。因此在任何时刻最多只有一个进程的P操作不会被阻塞,并顺利地进入临界区
父亲P(plate),可以访问盘子→母亲P(plate),可以访问盘子→父亲在往盘子里放苹果,同时母亲也可以往盘子里放橘子。于是就出现了两个进程同时访问缓冲区的情况,有可能导致两个进程写入缓冲区的数据相互覆盖的情况。
因此,如果缓冲区大小大于1,就必须专门设置一个互斥信号量utex来保证互斥访问缓冲区。
总结:在生产者-消费者问题中,如果缓冲区大小为1,那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。当然,这不是绝对的,要具体问题具体分析。
建议:在考试中如果来不及仔细分析,可以加上互斥信号量,保证各进程一定会互斥地访问缓冲区。但需要注意的是,实现互斥的P操作一定要在实现同步的P操作之后,否则可能引起“死锁”
解决“多生产者-多消费者问题”的关键在于理清复杂的同步关系。
在分析同步问题(一前一后问题)的时候不能从单个进程行为的角度来分析,要把“一前一后”发生的事看做是两种“事件”的前后关系。
比如,如果从单个进程行为的角度来考虑的话,我们会有以下结论:
如果盘子里装有苹果,那么一定要女儿取走苹果后父亲或母亲才能再放入水果
如果盘子里装有橘子,那么一定要儿子取走橘子后父亲或母亲才能再放入水果
这么看是否就意味着要设置四个同步信号量分别实现这四个“一前一后”的关系了?
正确的分析方法应该从“事件”的角度来考虑,我们可以把上述四对“进程行为的前后关系”抽象为一对“事件的前后关系”
盘子变空事件→放入水果事件。“盘子变空事件”既可由儿子引发,也可由女儿引发;“放水果事件”
既可能是父亲执行,也可能是母亲执行。这样的话,就可以用一个同步信号量解决问题了
假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它,但是要卷起并抽掉一支烟,抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中,第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料,供应者每次将两种材料放桌子上,拥有剩下那种材料的抽烟者卷一根烟并抽掉它,并给供应者进程一个信号告诉完成了,供应者就会放另外两种材料再桌上,这个过程一直重复(让三个抽烟者轮流地抽烟)
组合一:纸+胶水
组合二:烟草+胶水
组合三:烟草+纸
同步关系(从事件的角度来分析):
桌上有组合一→第一个抽烟者取走东西
桌上有组合二→第二个抽烟者取走东西
桌上有组合三→第三个抽烟者取走东西
发出完成信号→供应者将下一个组合放到桌上
V操作顺序:“前V后P”
桌上有组合一→第一个抽烟者取走东西
桌上有组合二→第二个抽烟者取走东西
桌上有组合三→第三个抽烟者取走东西
发出完成信号→供应者将下一个组合放到桌上
吸烟者问题可以为我们解决“可以生产多个产品的单生产者”问题提供一个思路。
值得吸取的精华是:“轮流让各个吸烟者吸烟”必然需要“轮流的在桌上放上组合一、二、三”,注意体会我们是如何用一个整型变量i实现这个“轮流”过程的。
略
略
引入管程的目的无非就是要更方便地实现进程互斥和同步。
1.需要在管程中定义共享数据(如生产者消费者问题的缓冲区)
2.需要在管程中定义用于访问这些共享数据的“入口”一一其实就是一些函数(如生产者消费者问题中,可以定义一个函数用于将产品放入缓冲区,再定义一个函数用于从缓冲区取出产品)
3.只有通过这些特定的“入口”才能访问共享数据
4.管程中有很多“入口”,但是每次只能开放其中一个“入口”,并且只能让一个进程或线程进入(如生产者消费者问题中,各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。注意:这种互斥特性是由编译器负责实现的,程序员不用关心)
5.可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待(此时,该进程应先释放管程的使用权,也就是让出“入口”);可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。
程序员可以用某种特殊的语法定义一个管程(比如:monitor ProducerConsumer.end monitor;;)之后其他程序员就可以使用这个管程提供的特定“入口”很方便地使用实现进程同步/互斥了。
在并发环境下,各进程因竞争资源而造成的一种互相等待对方手里的资源,导致各进程都阻塞,都无法向前推进的现象,就是“死锁”发生死锁后若无外力干涉这些进程都将无法向前推进
产生死锁必须同时满足一下四个条件,只要其中任一条件不成立,死锁就不会发生。
注意!发生死锁时一定有循环等待,但是发生循环等待时未必死锁(循环等待是死锁的必要不充分条件)
互斥条件:只有对必须互斥使用的资源的争抢才会导致死锁
该策略的缺点:并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全,很多地方还必须保护这种互斥性。因此,很多时候都无法破坏互斥条件。
不剥夺条件:进程所获得的资源在未使用完之前,不能由其他进程强行夺走,只能主动释放。
破坏不剥夺条件:
该策略的缺点:
请求和保持条件: 进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源又被其他进程占有,此时请求进程被阻塞,但又对自己已有的资源保持不放。
可以采用静态分配方法,即进程在运行前一次申请完它所需要的全部资源,在它的资源未满足前,不让它投入运行。一旦投入运行后,这些资源就一直归它所有,该进程就不会再请求别的任何资源了
该策略实现起来简单,但也有明显的缺点:
有些资源可能只需要用很短的时间,因此如果进程的整个运行期间都一直保持着所有资源,就会造成严重的资源浪费,资源利用率极低。另外,该策略也有可能导致某些进程饥饿。
循环等待条件:存在一种进程资源的循环等待链,链中的每一个进程已获得的资源同时被下一个进程所请求。
可采用顺序资源分配法。首先给系统中的资源编号,规定每个进程必须按编号递增的顺序请求资源同类资源(即编号相同的资源)一次申请完。
原理分析:一个进程只有已占有小编号的资源时,才有资格申请更大编号的资源。按此规则,已持有大编号资源的进程不可能逆向地回来申请小编号的资源,从而就不会产生循环等待的现象。
假设系统中共有10个资源,编号为1,2,......10
该策略的缺点
所谓安全序列,就是指如果系统按照这种序列分配资源,则每个进程都能顺利完成。只要能找出一个安全序列,系统就是安全状态。当然,安全序列可能有多个。
如果分配了资源之后,系统中找不出任何一个安全序列,系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然,如果有进程提前归还了一些资源,那系统也有可能重新回到安全状态,不过我们在分配资源之前总是要考虑到最坏的情况。
如果系统处于安全状态,就一定不会发生死锁。如果系统进入不安全状态,就可能发生死锁(处于不安全状态未必就是发生了死锁,但发生死锁时一定是在不安全状态)
因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态,以此决定是否答应资源分配请求。这也是“银行家算法”的核心思想。
银行家算法是荷兰学者Dijkstra为银行系统设计的,以确保银行在发放现金贷款时,不会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中,用于避免死锁。
核心思想:在进程提出资源申请时,先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态,就暂时不答应这次请求,让该进程先阻塞等待。
安全性算法:
此时系统是否处于安全状态?
思路:尝试找出一个安全序列.{P1,P3,P0,P2,P4}
- 依次检查剩余可用资源(3,3,2)是否能满足各进程的需求可满足P1需求,将P1加入安全序列,并更新剩余可用资源值为(5,3,2)
- 依次检查剩余可用资源(5,3,2)是否能满足剩余进程(不包括己加入安全序列的进程)的需求可满足P3需求,将P3加入安全序列,并更新剩余可用资源值为(7,4,3)
- 依次检查剩余可用资源(7,4,3)是否能满足剩余进程(不包括已加入安全序列的进程)的需求.以此类推,共五次循环检查即可将5个进程都加入安全序列中,最终可得一个安全序列。
该算法称为安全性算法。可以很方便地用代码实现以上流程,每一轮检查都从编号较小的进程开始检查。
实际做题时可以更快速的得到安全序列。
实际做题(手算)时可用更快速的方法找到一个安全序列:
经对比发现,(3,3,2)可满足P1、P3,说明无论如何,这两个进程的资源需求一定是可以依次被满足的,因此P1、P3一定可以顺利的执行完,并归还资源。可把P1、P3先加入安全序列。
(2,0,0)+(2,1,1)+(3,3,2)=(7,4,3)剩下的P0、P2、P4都可被满足。同理,这些进程都可以加入安全序列。
于是,5个进程全部加入安全序列,说明此时系统处于安全状态,暂不可能发生死锁。
再看一个找不到安全序列的例子:
经对比发现,(3,3,2)可满足P1、P3,说明无论如何,这两个进程的资源需求一定是可以依次被满足的,因此P1、P3一定可以顺利的执行完,并归还资源。可把P1、P3先加入安全序列。(2,0,0)+(2,1,1)+(3,3,2)=(7,4,3)
剩下的P0需要(8,4,3),P2需要(6,5,0),P4需要(4,3,4),任何一个进程都不能被完全满足
于是,无法找到任何一个安全序列,说明此时系统处于不安全状态,有可能发生死锁。
银行家算法(矩阵Max):
假设系统中有n个进程,m种资源每个进程在运行前先声明对各种资源的最大需求数,则可用一个n*
m的矩阵(可用二维数组实现)表示所有进程对各种资源的最大需求数。不妨称为最大需求矩阵Max,Max[,j]=K表示进程Pi最多需要K个资源Ri。同理,系统可以用一个n*
m的分配矩阵Allocation表示对所有进程的资源分配情况。Max-Allocation=Need矩阵,表示各进程最多还需要多少各类资源。
另外,还要用一个长度为m的一维数组Available表示当前系统中还有多少可用资源
某进程P向系统申请资源,可用一个长度为m的一维数组Request表示本次申清的各种资源量。
数据结构:
长度为m的一维数组Available表示还有多少可用资源
n*
m矩阵Max表示各进程对资源的最大需求数
n*
m矩阵Allocation表示已经给各进程分配了多少资源
Max-Allocation=Need矩阵表示各进程最多还需要多少资源
用长度为m的一位数组Request表示进程此次申请的各种资源数
银行家算法步骤:
①检查此次申请是否超过了之前声明的最大需求数
②检查此时系统剩余的可用资源是否还能满足这次请求
③试探着分配,更改各数据结构
④用安全性算法检查此次分配是否会导致系统进入不安全状态
安全性算法步骤:
检查当前的剩余可用资源是否能满足某个进程的最大需求,如果可以,就把该进程加入安全序列,
并把该进程持有的资源全部回收。
不断重复上述过程,看最终是否能让所有进程都加入安全序列。
系统处于不安全状态未必死锁,但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁。
为了能对系统是否已发生了死锁进行检测,必须:
①用某种数据结构来保存资源的请求和分配信息:
②提供一种算法,利用上述信息来检测系统是否已进入死锁状态。
如果系统中剩余的可用资源数足够满足进程的需求,那么这个进程暂时是不会阻塞的,可以顺利地执行下去,如果这个进程执行结束了把资源归还系统,就可能使某些正在等待资源的进程被激活,并顺利地执行下去。相应的,这些被激活的进程执行完了之后又会归还一些资源,这样可能又会激活另外一些阻塞的进程.…
如果按上述过程分析,最终能消除所有边,就称这个图是可完全简化的。此时一定没有发生死锁(相当于能找到一个安全序列)
如果最终不能消除所有边,那么此时就是发生了死锁。
最终还连着边的那些进程就是处于死锁状态的进程。
一旦检测出死锁的发生,就应该立即解除死锁。
补充:并不是系统中所有的进程都是死锁状态,用死锁检测算法化简资源分配图后,还连着边的那些进程就是死锁进程
解除死锁的主要方法有:
如何决定对谁动手?
- 1.进程优先级
- 2.已执行多长时间
- 3.还要多久能完成
- 4.进程已经使用了多少资源
- 5.进程是交互式的还是批处理式的(优先批处理式)