操作系统课件复件 习题课

例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 就