管程

为什么要引入管程

• 信号量机制存在的问题 : 编写程序困难, 易出错.
  • 必须要线操作之后V, 后操作之前P; 必须要先检查后进入 (先同步, 后互斥)
• 能不能设计一种机制, 让程序员写程序时不需要关注复杂的PV操作,写代码更轻松
• 管程 : 一种高级同步机制 (为了改进信号量而产生)

管程的定义和基本特征

• 管程是一个特殊的软件模块, 由以下部分构成

  • 局部于管程的共享数据结构说明 (私有属性)
  • 对噶i数据结构进行操作的一组过程 (公有方法)
  • 对局部于管程的共享数据设置的初始值的语句 (属性初始化)
  • 一个名字 (类名)

• 管程的基本特征:

  • 局部于管程的数据只能被局部于管程的方法所访问
  • 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
  • 每次仅允许一个进程在管程内执行某个内部过程hbb

用管程解决生产者消费者问题

Java中类似与管程的机制

总结

• 管程使用了封装的思想, 将互斥同步等一系列复杂的操作(什么时候P什么时候V, 死锁等情况, 在内部都被处理好了, 程序员不必关系)隐藏在了管程内部, 对外只提供了一个简单的接口.
  

死锁

什么是死锁

• 死锁 : 各进程互相等待对方手里的资源, 导致各进程都阻塞, 无法向前推进的现象.
  • 发生死锁后, 若无外力干涉, 这些进程都无法向前推进

死锁, 饥饿, 死循环

• 死锁 : 各进程互相等待对方手里的资源, 导致各进程都阻塞, 无法向前推进的现象
• 饥饿 由于长期得不到想要的资源, 某进程无法向前推进的现象.
  • 比如: 短进程(SPF)优先算法中, 若有源源不断的短进程到来, 则长进程将一直得不到处理机, 从而发生饥饿
• 死循环 : 某进程执行过程中一直跳不出某个循环的现象.
  • 有时因为程序逻辑BUG, 有时是程序员故意设计

共同点 : 都是进程无法继续向前推进的现象.

死锁产生的必要条件

发生死锁, 必然有下面四个条件, 缺少一个, 死锁都会被解除

• 互斥条件 : 只有对 必须互斥使用的资源 的争抢才会导致死锁 (如哲学家的筷子, 打印机设备), 想内存, 扬声器这些可以让多个进程使用的资源不会导致死锁 (因为进程不用阻塞等待这种资源)

• 不剥夺条件 : 进程所获得的资源在未使用完之前, 不能由其他进程强行夺走, 只能主动释放

• 请求和保持条件 : 进程已经保持了至少一种资源, 但又提出了新的资源请求, 而该资源又被其他进程占有. 此时进程被阻塞, 有对自己占有的资源保持不放

• 循环等待 : 存在一种进程资源的循环等待链. 链中每个进程已获得的资源同时被下一个进程所请求

• 互斥使用, 不可剥夺, 循环等待, 占有且等待.

• 发生死锁时 一定有循环等待, 但是发生循环等待时未必死锁 (循环等待是死锁的必要条件)

  • 如果同类资源数>1, 即使有循环等待, 也未必发生死锁. 但如果系统中每个资源都只有一个, 那循环等待就是死锁的充分必要条件.

什么时候会发生死锁

• 对系统不可剥夺资源的竞争 : 各进程对不可剥夺的资源(打印机)的竞争可能引起死锁. 对可剥夺资源的竞争不会导致死锁CPU)
• 进程推进顺序非法 : 请求和释放资源的顺序不当, 也会导致死锁.
• 信号量使用不当也会导致死锁 : 如生产者-消费者模型中的PV顺序错误

死锁的处理策略

• 预防死锁 : 破坏死锁四个必要条件中的一个或几个
• 避免死锁 : 用某种方法防止系统进入不安全的状态, 从而避免死锁 (银行家算法)
• 死锁的检测和解除. 允许死锁发生, 不过操作系统会负责检测死锁的发生, 然后采取某种措施解除死锁.

总结

死锁的处理

预防死锁

破坏互斥条件

• 互斥条件 : 只有对互斥使用的资源的争抢才会导致死锁

  • (这是必要条件, 只有他不一定成立, 因为CPU也是互斥使用的但是可剥夺资源, )

• 如果把只能互斥使用的资源 改造为 可共享使用的资源, 则系统不会进入死锁状态

  • SPOOLing技术, 操作系统可以采用SPOOLing技术把独占设备在逻辑上改造成共享设备. 比如SPOOLing技术把打印机改造为共享设备

• 缺点 : 并不是所有的资源都可以改成可共享的资源, 并且为了系统安全, 很多地方还必须保护这种互斥性. 因此, 很多时候无法破坏互斥条件
  

破坏不剥夺条件

• 不剥夺条件 : 进程所获得的资源未使用完之前, 不可被其他进程强行夺走, 只能主动释放.

• 方案一

  • 当某个进程请求新的资源得不到满足时, 它必须立即释放保持的所有资源, 待以后需要时重新申请. (舍己为人)

• 方案二

  • 当某个进程需要的资源被其他进程占有时, 有操作系统协调, 将想要的资源强行剥夺.需要考虑各进程优先级, 处理机强行剥夺资源给优先级高的进程先使用. (找关系走后门)

• 缺点

  • 实现复杂
  • 主动释放已获得的资源可能造成前一阶段工作的失效. 因此这种方法只适用于易保存和易恢复状态的资源. (如CPU)
  • 反复的申请和释放资源会增加系统开销, 降低系统吞吐量
  • 如果采用方案一: 只要暂时的不到某种资源就放弃之前获得的所有资源, 以后再重新申请, 可能会造成一直发生这样的情况, 而导致饥饿

破坏请求和保持条件

• 请求和保持条件 : 进程已经保持了一些资源, 又提出了新的资源请求. 而这些新的资源被其他进程占有. 此时进程阻塞, 对已有的资源保持不放.

• 静态分配 : 进程运行前一次申请完所需要的所有资源, 在它的资源得不到满足前, 不让他投入运行. 一旦投入运行后, 这些资源就一直归他所有. 该进程不会再请求任何资源.

• 缺点

  • 有些资源可能只需要使用很短时间, 因此如果进程运行的整个过程都一直保持着所有资源, 就会造成严重的资源浪费, 资源利用率低.
  • 可能导致某些进程饥饿

• 如果源源不断来A, B进程, 资源1,2一直没有同时空闲的时候, 会造成C继承阻塞

破坏循环等待条件

• 循环等待条件 : 存在一种进程资源的循环等待链. 链中每个进程已获得的资源同时被下一个进程所请求

• 采用顺序资源分配法 : 首先给系统中的资源编号, 规定每个进程必须按编号递增的顺序请求资源, 同类资源(编号相同的资源) 一次申请完 (不能之后申请到大编号后, 又回来过申请这种小编号. 过了这村没这店)

• 原理分析 : 一个进程只有占有小编号的资源时, 才有资格申请更大编号的资源. 按此规则, 已持有编号资源的进程不可能逆向地回来申请小编号资源, 从而不会产生循环等待.

• 缺点

  • 不方便增加新的设备, 因为可能需要重新分配所有编号
  • 进程实际使用资源的顺序可能和编号递增的顺序不一致. 造成资源浪费 (一些未来需要使用目前暂时不需要使用的资源, 也需要被申请占用)
  • 必须按规定次序申请资源, 用户编程器麻烦

总结

避免死锁

什么是安全序列

• 安全序列 : 如果系统按照这种序列分配资源, 则每个进程都能顺利完成. 只要能找出一个安全序列, 系统就是安全状态. 安全序列可能有多个

• 如果分配了资源后, 系统中找不出任何一个安全序列, 系统就进入了不安全状态. 就意味着之后可能所有进程都无法顺利执行下去.

  • 如果有些进程提前归还了一些资源, 那系统也有可能重新回到安全状态, 不过我们在资源分配之前总是要考虑最坏亲情况.

• 如果系统处于安全状态, 就一定不会发生死锁. 如果系统进入了不安全状态, 就可能发生死锁

  • (处于不安全状态未必发生死锁, 但是发生了死锁一定处于不安全状态)

• 因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态, 以此决定是否答应资源分配请求. 银行家算法核心

银行家算法

• 荷兰学者Dijkstra为银行系统设计, 以确保银行在发放现金时, 不会发生不能满足所有客户需要的情况. 后来该算法用于操作系统中, 避免死锁
• 核心思想 : 在进程提出资源申请时, 先预判此次分配是否会导致系统进入不安全状态. 如果会进入不安全状态, 就暂时不答应这次请求, 让该进程先阻塞等待.

总结

死锁的检测和解除

死锁的检测

• 为了能对系统是否已经发生了死锁进行检测, 必须
  • 用某种数据结构来保存资源的请求和分配信息
  • 提供一种算法, 利用上述信息来检测系统是否已进入死锁状态
  • (数据结构用来保存数据, 算法用来对数据进行处理分析)

• 如果不能消除所有变, 那么此时就发生了死锁.
• 最终还连着边的那些进程就是处于死锁状态的进程

死锁的解除

总结

• 不阻塞 : 申请的资源可以被分配