作业系统L6－同步

临界区间(critical section)

每一行程中的部分程序码，可以共同改变变数，更新表格，写入档案

区间结构

• 入口区段(entry section):临界区间入口
• 出口区段(exit section):临界区间出口
• 剩余区段(remainder section)
  

临界区间问题

条件

• 互斥(Mutual Exclusion):若有行程已在临界区间执行，其他行程不能再同区间执行
• 进行(Progress):被选择的行程不得被无限延迟下去
• 限制性等待(Bounded Waiting):一个行程被要求进入临界区间答应前，允许其他一个行程进入

问题解答

• 可抢先核心(preemptive kernels):核心模式执行时可抢先
• 不可抢先核心(nonpreemptive kernels):离开核心模式或自动交出CPU时才可抢先

同步硬体

锁(locking)

• 用於保护临界区间
• 单一处理器可停止中断，多处理器较没效率

同步软件

互斥锁(Mutex Lock)

• acquire():取得锁
• release():释放锁
• 忙碌等待(busy waiting)
• 自旋锁(spinlock)

号志(Semaphore)

• 不需要忙碌等待的同步工具
• 计数号志(Counting semaphore):不受限制的整数值
• 二元号志(Binary semaphore):数值可以是0,1，可用来取代互斥锁

无忙碌等待的号志

• 每个号志都有一个相关联的等待伫列
• 数值(整数型态)
• 指向串列的下一笔纪录
• 操作
  • block:把呼叫操作的行程放到适当的等候伫列
  • wakeup:移除等候伫列的一个行程，放到就绪伫列

死结和饥饿

• 死结(Dead Lock):两个以上的行程等待一个只能被等待的行程
• 饥饿(Starvation):无限期阻隔
• 优先权倒置(Priority Inversion):高优先权行程被低优先权行程锁把持造成排班问题，需用**优先权继承协定(priority-inheritance protocol)**解决

典型的同步问题

有限缓冲区问题

• n个缓冲区,每一个缓冲区保存一项资料

读取者-写入者问题

• 读取者:只能读取资料集;它们不能执行资料集
• 写入者:可以读和写资料集
• 允许许多读取者同时去读取共用资料
• 同一时间只有一个写入者可以存取资料

读取者-写入者问题的变形

• 除非有写入者已获得允许去使用共用资料，否则读取者不需保持等候状态
• 只要写入者准备好之後，需要尽快的撰写共用资料

哲学家进餐的问题(Dining-philosophers Problem)

• 需两枝筷子才能吃，吃完同时放下两枝筷子
  

监督程序

• 一种对於行程同步提供方便和有效机制的高阶使用一组操作资料的函数来封装资料
• 抽象资料型态(abstract data type,ADT):只能由程序内执行码存取的内部变数

条件变数

condition x, y;

• x.wait () :使用後的行程会被暂停，直到x.signal ()发生
• x.signal ():恢复因为x.wait ()而被暂停的行程