ALAN2000

操作系统习题课及实验室简介,2000年11月1日星期三 礼教213 Mr. Yang RuiDuo,内容简介,操作系统习题讲解 嵌入式操作系统简介 实验室简介 自由提问,操作系统习题讲解,主题：进程及其相关问题,1。程序、进程、线程,谈谈你对“程序”、“进程”、“线程”这三个概念的理解，尤其要注意它们的区别。考虑进程在运行、就绪、阻塞三种状态间的转换，其中哪些“转换”是不可能发生的？在哪些情况下，一个正在运行的进程会停止运行？请对比这些情况下停止运行的原因。,程序与进程之间的区别,进程更能真实地描述并发，而程序不能 进程是由程序和数据两部分组成的 程序是静态的，进程是动态的 进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的 一个程序可对应多个进程，反之亦然 进程具有创建其他进程的功能，而程序没有,进程和线程,进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位。 线程是CPU调度的最小单位。,运行,就绪,等待,进程的状态及其转换,问题： 进程有无如下状态转换，为什么？ （1）等待运行 （2）就绪等待 解答： （1）不能：等待就绪运行 （2）不能：就绪运行等待,FORK,采用一种你所熟悉的编程语言，编写一个过程，来模拟fork（创建进程）原语的功能。（可以自己定义所需的数据结构）,系统调用fork的算法,2.课本50页第20题,T/(T+取下整(T/Q)*S+S) T/(T+S); T/(T+S); T/(T+取上整(T/Q)*S) 50% 0,3.下列解决互斥的方法各有什么缺陷？,a) 关中断 b) 设置lock变量 c） Peterson算法,4.Sleep/Wake-up方法,如果简单的采用SLEEP/WAKE-UP方法（课本P28图210）来实现生产者消费者问题，有可能导致生产者和消费者同时处于睡眠状态。是什么原因导致了这个缺陷？改用信号量的方法（课本P30图211）能解决上述缺陷吗？若能，它是怎样解决的？若不能，你认为如何改进算法才能解决？,5.PV操作的问题,问题： 推广读写者问题中的消息缓冲处理。消息缓冲区为k个，有m个发送进程，n个接收进程，每个接收进程对发送来的消息都必须取一次,Type BufferType = Record msg:MessageType; count:integer; mutex:semaphore; 初值为1 empty: semaphore; 初值为1 full: array 1n of semaphore； 初值全为0 End Var mutex: semaphore; 初值为1 s: integer; 初值为0 buff: array 0k-1 of BufferType; k是缓冲区大小； n是接收进程个数 m是发送进程个数，通过 s 进行“写互斥” ,Procedure Sender_i(i:integer); i 为发送进程的标号 Var s0, j: integer; Begin Repeat P(mutex); s0:=s; s:=(s+1) mod k; V(mutex); P(buffs0.empty)； 在buffs0.msg中写信息； P(buffs0.mutex)； buffs0.count:=n; V(buffs0.mutex); For (j:=1 to n do) V(buffs0.fullj); Until false; End,Procedure Recvr(i:integer); i 为接收进程的标号 Var j: integer; Begin j:=0; Repeat P(buffj.fulli); 从buffj.msg中读信息； P(buffj.mutex)； buffj.count:= buffj.count-1; If (buffj.count=0) Then V(buffj.empty)； V(buffj.mutex); j:=(j+1) mod k Until false; End,6.读者写者的问题,第二类读者写者问题（写者优先） 1）共享读 2）互斥写、读写互斥 3）写者优先于读者（一旦有写者，则后续 读者必须等待，唤醒时优先考虑写者）,Var mutex: semaphore; 互斥信号量，初值为1 R : semaphore; 对应读者等待队列，初值为0 W: semaphore; 对应写者等待队列，初值为0 一般变量： Writing: Boolean; 初值false, 有写者正在写 rc : integer; 初值0, 共享读的读者数 rq : integer; 初值0,等待队列中读者数 wq : integer; 初值0,等待队列中写者数,Begin P(mutex); If (Writing OR wq0) Then Begin rq:=rq+1; V(mutex); P(R); P(mutex);resume End; rc:=rc+1; V(mutex); Read();,P(mutex); rc:=rc-1; If (rc=0 AND wq0) Then Begin wq:=wq-1; Writing:=true; V(mutex); V(W); End; Else V(mutex) ; End,读者进程,(a) 检测是否有写者并处理 (b) Inc(rc) (c) Read() (d) Dec(rc) (e) 处理写者等待队列,Begin P(mutex); If (Writing OR rc0) Then Begin wq:=wq+1; V(mutex); P(W); End; Else Begin Writing:=true; V(mutex); Write(); P(mutex); If (wq0) Then Begin wq:=wq-1; V(mutex); V(W); End Else,If (rq0) Then Begin Writing:=false; While (rq0) Begin rq:=rq-1; V(R) ; End End Else Begin Writing:=false; V(mutex); End End,写者进程,(a) 检测是否有进程正在读写 (b) Writing(T); Write(); Writing(F) (c) 处理写者等待队列;处理Reader等待队列,7。对PV操作的修改,对 P/V 操作定义作以下修改 P(s): s:=s-1; If s0 Then 将本进程插入相应队列末尾等待； V(s)： s:=s+1; If s=0 Then 从等待队列队尾取一个进程唤醒， 插入就绪队列,问题：,1）这样定义P、V操作是否有问题？ 不合理：先进后出；可能“无限等待” 2）用这样的P、V操作实现N个进程竞争使用某一共享变量的互斥机制。 思路：令等待队列中始终只有一个进程。 将 “栈” 变成 “队列” Var S:array 1n-1 of semaphore; n为进程数目；Si初值为i；Sn到 S1的作用好象是 n 层筛子 ,Procedure Pi; Var i:integer; Begin Repeat Pre_Do_it(); For i:=n-1 Downto 1 Do P(Si); Do_It_In_Critical_Section; For i:=1 To n-1 Do V(Si); Post_Do_it(); Until false; End,3）对于2）的解法，有无效率更高的方法。 如有，试问降低了多少复杂性？ 上述解法每次都需要做2n次P/V操作， 性能低下。采用二叉树的思想，改进如下：,S14,P14,S1,S2,S3,让信号量处于不同的层次上，每个信号量至多 控制两个进程（对两个进程进行同步）,P1,P2,P3,P4,Procedure P1; P2 is the same Begin Repeat P(S1); P(S3); Do_It(); V(S3); V(S1); Until false; End;,Procedure P3; P4 is the same Begin Repeat P(S2); P(S3); Do_It(); V(S3); V(S2); Until false; End;,不妨设有4个进程P1P4， Var S1, S2, S3: semaphore; 初值为1,假设共有2N个进程争用临界区； 时间复杂性： 2N vs N；空间复杂性： 2N vs 2N1,8.理发师问题,理发师问题 理发店里有一位理发师,一把理发椅和N把供等候理发的顾客坐的椅子.如果没有顾客,则理发师便在理发椅上睡觉.当一个顾客到来时,他必须先唤醒理发师.如果顾客到来时理发师正在理发，则如果有空椅子，可坐下来等；否则离开。,顾客进程 i: P(Sn);门外观望 P(mutex); 进门； V(mutex); V(S); 等候； 理发； V(Sn) P(mutex); 出门； V(mutex);,Var Sn: semaphore; 位子数目，初值为n S: semaphore; 理发师睡觉，初值为1 mutex: semaphore; 初值为1,理发师进程 ： Repeat P(S); P(mutex); 叫人理发； V(mutex); 理发； Until false;,9.用P.V操作来实现Receive原语:,Receive（S，M） Begin 根据S找发送进程,如果没找到出错返回; 申请缓冲区消息 P（s-m）； P(m-mutex); 将载有消息的缓冲区从消息链中取出; V(m-mutex); 把消息从M处copy到receiver的信息空间; P(b-mutex); 是缓冲区为空； V(b-mutex); V(s-b); End 其中s-b初值:n ;s-m初值:0,10.安全序列的问题,设系统中有4个进程P1，P2，P3和P4.在某一时刻系统状态如下： 最大需求量 已分配资源量 P1 6 2 P2 7 4 P3 3 2 P4 2 0 剩余资源量 1 系统是否处于安全状态？如是，则给出所有的进程安全序列. 如果进程P4申请2个资源，能否实施分配？为什么？,P3, P4, P2, P1 P3, P2, P4, P1 P3, P2, P1, P4 P4申请,不能分配，否则不安全 如果忽然所有的客户都申请最大限额，而银行家无法满足其中任何一个的要求，那么产生死锁。（p178) 从安全状态出发，系统能够保证所有进程都能够完成；而从不安全状态出发，不存在这样的保证。(p177),嵌入式系统的介绍,何为嵌入式系统？,嵌入式系统是指操作系统和功能软件集成于计算机硬件系统之中。简单的说就是系统的应用软件与系统的硬件一体化，类似与BIOS的工作方式。具有软件代码小，高度自动化，响应速度快等特点。特别适合于要求实时的和多任务的体系。,嵌入式实时多任务操作系统,实时多任务操作系统（Real Time Operating System)是根据操作系统的工作特性而言的。实时是指物理进程的真实时间。实时操作系统是指具有实时性，能支持实时控制系统工作的操作系统。首要任务是调度一切可利用的资源完成实时控制任务，其次才着眼于提高计算机系统的使用效率，重要特点是要满足对时间的限制和要求。,嵌入式实时多任务操作系统,对于分时操作系统，软件的执行在时间上的要求，并不严格，时间上的错误，一般不会造成灾难性的后果。,嵌入式实时多任务操作系统,实时操作系统的重要特点是具有系统的可确定性，即系统能对运行情况的最好和最坏等的情况能做出精确的估计。,实时操作系统的需求,实时操作系统一定要保证各类实时进程的正确运行 周期运行的实时进程 非周期的实时进程 不同优先级的实时进程 实时操作系统应该是抢先式多任务的 在实时操作系统中，在保证实时进程正确运行的基础上才考虑资源的有效利用,嵌人式实时操作系统 -RTOS应用无处不在,RTOS 的全球市场规模,据EMF报告1998和1999年全球嵌人式市场规模 1998 1999 单板 19.691亿美圆 21.879亿美圆 RTOS 3.054亿美圆 3.620亿美圆 开发工具 7.858亿美圆 9.184亿美圆 开发工具含ICE/JTAG，逻辑分析仪，编程器和软件编译器和调试器等,系统软件开发和研究人员应该具有的素质,精通操作系统原理 通过计算机操作系统专业课程的学习，熟悉操作系统的组成、结构，以及操作系统核心中的一些常用的数据结构和算法。 精通C语言和汇编语言 要求精通ANSI C，能够熟练使用gcc、make等工具；能够熟练使用i386的汇编语言，要求掌握Intel和AT&T两种汇编语言格式；能够使用C语言和汇编语言联合编程；对于C语言编译后生成的可执行文件，要求能够在汇编语言一级上理解。,系统软件开发和研究人员应该具有的素质,分析一种操作系统的核心代码,并且能够在汇编一级理解核心关键部分 分析Minix/Linux/FreeBSD/Rtems等的核心代码，从整体上把握一个操作系统