作业系统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 ()而被暂停的行程