操作系统课件复件 习题课_第1页
操作系统课件复件 习题课_第2页
操作系统课件复件 习题课_第3页
操作系统课件复件 习题课_第4页
操作系统课件复件 习题课_第5页
已阅读5页,还剩23页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

例1 修改书上读者优先的程序为读写公平 varrc integer w mutex semaphore rc 0 w 1 mutex 1 procedurereadbeginP mutex rc rc 1 ifrc 1thenP w V mutex 读文件 P mutex rc rc 1 ifrc 0thenV w V mutex end procedurewitebeginP w 写文件 V w end 分析 读写公平 即一旦有写者到达 后续的读者必须等待 无论是否有读者在读 而在写者前到达的读者可以继续执行 可以增加一个信号量 用于在写者到达后封锁后续的读者 r 1 P r V r P r V r 例2 用PV操作解决读者和写者之间的同步问题 且写者优先 分析 1 增加一个写者计数器writecount 为了对该计数器进行互斥访问 增加信号量wmutex 2 设置信号量x 使一个读者和一个写者竞争访问文件 只要在x上等待的写者能继续执行 其他写者便可以直接竞争写者之间文件的互斥访问权 从而实现写者优先 intreadcount writecount semaphoremutex 1 wmutex 1 rwmutex 1 x 1 voidreader while 1 p x p rmutex readcount if readcount 1 p rwmutex v rmutex v x readdata p rmutex readcount If readcount 0 v rwmutex v rmutex intreadcount writecount semaphoremutex 1 wmutex 1 rwmutex 1 x 1 voidwriter while 1 p wmutex writecount if writecount 1 p x v wmutex p rwmutex writedata v rwmutex p wmutex writecount If writecount 0 v x v wmutex 例3 改进书上的哲学家进餐算法 通过限制同时进餐的人数来防止死锁 分析1 可引入一个额外的信号量mutex来控制对临界资源叉子的访问权 初值为1分析2 引入一个初值为4的信号量来限制同时进餐的人数 semaphorefork 5 semaphorecount 4 for inti 0 i 5 i fork i 1 cobeginprocessphiosopher i i 0 1 2 3 4 while true think P count P fork i P fork i 1 5 eat V fork i V fork i 1 5 v count coend 例4 现有四个进程 R1 R2 W1和W2 它们共享可以存放一个数的缓冲区B 进程R1每次把从键盘上读入的一个数存到缓冲区B中 供进程W1打印输出 进程R2每次把从磁盘上读一个数存放到缓冲区B中 供进程W2打印输出 怎样用P V操作协调四个并发进程的工作 设信号量e f1 f2 其初值分别为e 1 f1 0 f2 0 R1 R2 W1 W2 例5 设有3个并发执行的进程 输入进程Pi 计算进程Pc和输出进程Po 其中进程Pi不断地从键盘读入整数 放入缓冲区Buf1 Pc按输入顺序从Buf1中取数据 每次取出2个整数 计算其和 将结果放入缓冲区Buf2 Po负责将Buf2中的数据按顺序输出 设缓冲区Buf1 Buf2可存放的整数个数分别为m n m n 0 要求利用信号量的P V操作写出进程Pi Pc Po的算法 设信号量e1 f1 e2 f2 其初值分别为 e1 m f1 0 e2 n f2 03个并发进程分别为 例6 举例说明P V操作为什么要求设计成原语 即对同一信号量上的操作必须互斥 1 设信号量S的初值为1 当一个P操作执行完S S 1后 S的值为0 该P操作不应被阻塞 但若P操作不是一个原语 也就是说在一个P操作执行过程中可以由另一个P操作同时 则这时的S的值为 1 这是第一个P操作将会被阻塞 这样的P操作不符合P操作的语义 2 设信号量S的初值为 1 当一个V操作执行完S S 1后 S的值为0 该V操作应该唤醒一个被P操作阻塞得进程 但若V操作不是一个原语 也就是说在一个V操作执行的过程中可以有另一个V操作同时在执行 加入第2个V操作在第1个V操作执行判断语句IFS 0前夜执行了S S 1操作 则这时的S值为1 这时第1个操作将不再去唤醒被阻塞得进程 这样的V操作不符合V操作的语义 3 同样地 当P操作的执行过程中插入了V操作 也会出现不符合原语语义的情况 例如 在P操作执行完 后 的值为 经判断 该进程应该被阻塞 但若要在进行判断后阻塞进程前执行完另外 操作 则该 操作并没有可以唤醒的被阻塞得进程 而当 操作执行完后继续执行 操作时 该 操作仍将阻塞该进程 这一进程将不被唤醒 对于 操作的执行过程中插入了 操作 也会出现不符合原语语义的情况 例如 在 操作执行完 后 的值为 该进程无需唤醒其他进程 但若在进行判断前执行了一个 操作 则在后续操作中需要唤醒一个阻塞进程 例7 试分析m个生产者n个消费者共享K缓冲区问题中各信号量 empty full mutex 的取值范围 empty m k full n k mutex k 1 1 例8 用P V原语实现东西向单行道上车辆的正确行驶 当有车自东向西方向 或自西向东方向 行驶 另一方向上的车辆须等待 同一方向上的车可以连续通过 当某一方向上已经没有车辆在单行道上行驶时 另一方向上的车辆即可以进入单行道 请完善这个程序 可参考读写者问题 beginmutex1 mutex2 wait semaphore mutex1 mutex2 wati 1 eastcount westcount integereastcount 0 westcount 0cobegineast west west east coend processeast west begin eastcount eastcount 1 ifeastcount 1then 通过单行道 eastcount eastcount 1 ifeastcount 0then V mutex1 end P mutex1 V mutex1 P wait P mutex1 V wait processwest east begin westcount westcount 1 Ifwestcount 1then 通过单行道 westcount westcount 1 Ifwestcount 0then V mutex2 end P mutex2 V mutex2 P wait P mutex2 V wait 例9 设有8个进程M1 M2 M8 它们有如图所示的优先关系 试用PV操作实现这些进程间的同步 M1 M2 M3 M4 M5 M6 M8 M7 例10假定系统有4个同类资源和3个进程 进程每次只申请或释放1个资源 每个进程最大资源需求量为2 请问这个系统为什么不会发生死锁 解 由于每个进程最多需要2个资源 最坏情况下 每个进程获得1个 系统还剩1个 这1个资源 无论分给谁 都能完成 完成进程释放资源后 使剩余进程也完成 故系统不会发生死锁 证明 假定每个进程最多申请x个资源 最坏情况下 每个进程都得到 x 1 个资源 显然 这时系统剩余的资源数量为M N x 1 只要系统这时还有一个剩余资源 就可使其中的一个进程获得所需的全部资源 该进程运行结束后释放资源 就可使其他进程得到全部资源的满足 因此 当M N x 1 1时系统不会发生死锁 化解这个不等式为Nx 1 M N 例11假定系统有N个进程共享M个单位资源 进程每次只申请或释放1个单位资源 每个进程的最大需求不超过M 所有进程的需求总和小于M N 试证明为什么这种情况不会发生死锁 例12 某寺庙 有小 老和尚若干 有一水缸 由小和尚提水入缸供老和尚饮用 水缸可容纳10桶水 水取自同一井中 水井很窄 每次只能容纳一个水桶打水 水桶总数为3个 每次入 取缸水仅为1桶水 且不可同时进行 试给出有关取水 入水的算法描述 empty full mutex1 mutex2 S semaphore empty 10 full 0 mutex1 1 mutex2 1 s 3 cobegin从井中提水者 beginL P s P mutex1 从井中提水 V mutex1 P empty P mutex2 提水入缸 V mutex2 V full V s gotoL end end 从缸中取水者 beginL1 P s P full P mutex2 从缸中取水 V empty V s gotoL1 end 1 进程的 同步 和 互斥 反映了进程间 和 的关系 2 产生死锁的四个必要条件是 3 在操作系统中 信号量是表示 的物理实体 它是一个与 有关的整型变量 其值仅能由 原语来改变 4 每执行一次P原语 信号量的数值S减1 如果S 0 该进程 若S 0 则 该进程 并把它插入该 对应的 队列中 例13 填空题 6 每执行一次V原语 信号量的数值S加1 如果 Q进程继续执行 如果S 0 则从对应的 队列中移出一个进程R 该进程状态变为 7 利用信号量实现进程的 应为临界区设置一个信号量mutex 其初值为 表示该资源尚未使用 临界区应置于 和 原语之间 8 在多道环境下 由于进程的并发执行 一段程序为多个进程共享时 要求在执行的过程中 该段程序的指令和数据不能被 这样的程序段称为 例14 选择题1 在非剥夺调度方式下 运行进程执行V原语之后 其状态 A 不变 B 要变 C 可能要变 D 可能不变 2 当对信号量进行V原操作之后 A 当S0 要唤醒一个就绪进程 C 当S 0 要唤醒一个等待进程 D 当S 0 要唤醒一个就绪进程 6 在下列叙述中 错误的一条是 A 进程被撤消时 只需释放该进程的PCB就可以了 因为PCB是进程存在的唯一标志 B 进程的互斥和同步都能用P V原语实现 C 用户程序中执行系统调用命令时 处理机的状态字将发生改变 D 设备独立性是指用户在编程时 所使用的设备与实际设备无关 7 正在运行的进程在信号量S上作P操作之后 当S 0 进程将进入信号量的 A 等待队列 B 提交队列 C 后备队列 D 就

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论