《操作系统4同步软硬件方法》由会员分享，可在线阅读，更多相关《操作系统4同步软硬件方法（21页珍藏版）》请在金锄头文库上搜索。
1、20114.1/213.3 3.3 进程同步进程同步3.3.1 3.3.1 进程同步的基本概念进程同步的基本概念3.3.2 3.3.2 信号量信号量(semaphore)(semaphore)3.3.3 3.3.3 经典进程同步问题经典进程同步问题3.3.4 3.3.4 进程间通信进程间通信疵泛喀启桂哨根埠浪惟动蔽名手草辛栓禁狱桓刷续勇曹失芽瘫晋解仙俊沿操作系统4-同步软硬件方法操作系统4-同步软硬件方法操作系统20114.2/21正常行车到站停车开车售票开车门关车门司机售票员合作合作合作合作进程间的合作关系进程间的合作关系盎援仟渴兑慨姜痊樱育邢梢团刹夫裔返再柳敝似侗铣榷尺怕瘩弦膳看鲁杭操作系
2、统4-同步软硬件方法操作系统4-同步软硬件方法操作系统20114.3/21打印进程打印进程1打印进程打印进程2打印打印打印打印获得打印数据获得打印数据获得打印数据获得打印数据竞争竞争进程间竞争资源进程间竞争资源抒肢贰他拙计继驮掀骋夹强僚咋棚澄刁魔剐报自鹃牌覆绅捆村职摧遂槽怜操作系统4-同步软硬件方法操作系统4-同步软硬件方法操作系统20114.4/21计算进程计算进程打印进程打印进程计算结果送到计算结果送到Buffer从从Buffer中取数中取数Buffer竞争竞争竞争竞争完成数据计算完成数据计算打印打印通知打印进程打印通知打印进程打印通知计算进程通知计算进程送下一个数送下一个数合作与竞争合作
3、与竞争合作合作合作合作诡菏粥蓟劲沛奠悉疯泪坤咳粤肇懈甭兜佩甸果女泰范熬逸燃告统溜炮湾芦操作系统4-同步软硬件方法操作系统4-同步软硬件方法操作系统20114.5/21司机与售票员司机与售票员多个打印者多个打印者计算者与打印者计算者与打印者进程间存在两种关系进程间存在两种关系协调好这些关系的过程协调好这些关系的过程进程的同步进程的同步操作顺序冲突操作顺序冲突共享外设、内存（变共享外设、内存（变量）等资源量）等资源妆区亥忧乃逗交贯价瘫慑登昧唤观闺素逮瑟岔未舞峭野瑞华凹霉辈瞒巫鄂操作系统4-同步软硬件方法操作系统4-同步软硬件方法操作系统20114.6/21F竞争资源关系：竞争资源关系： 进程同步的
4、主要任务：保证诸进程能进程同步的主要任务：保证诸进程能互斥互斥地地访问临界资源访问临界资源F相互合作关系：相互合作关系：进程同步的主要任务：保证相互合作的诸进进程同步的主要任务：保证相互合作的诸进程在执行次序上的协调程在执行次序上的协调同步同步。3.3.1 3.3.1 进程同步的基本概念进程同步的基本概念曳卡眼绰悼群氢纽呕炒伺缓际摄能床茅管实焰缉闹都捏手旋哪屯脂纹灼研操作系统4-同步软硬件方法操作系统4-同步软硬件方法操作系统20114.7/21计算进程打印进程计算结果送到Buffer从Buffer中取数Buffer互斥互斥向打印进程发信号向打印进程发信号通知其从通知其从Buffer里取数里取
5、数Buffer空？空？否是完成数据计算完成数据计算打印打印向计算进程发信号向计算进程发信号通知其向通知其向Buffer送数送数Buffer空？空？否是协调计算进程与打印进程的同步计算进程与打印进程的同步该擎范捕砌廊帜选毛似浆掀答炙森北斌糯迎茁惜农姚歼臼赁娱篇遣攘嘿鞘操作系统4-同步软硬件方法操作系统4-同步软硬件方法操作系统20114.8/211.1.临界资源临界资源 对于计算机中的有些软硬件资源，当多个进程对其进对于计算机中的有些软硬件资源，当多个进程对其进行访问时（关键是进行写入或修改），必须互斥地进行访问时（关键是进行写入或修改），必须互斥地进行，这些一次只允许一个进程使用的资源称为行，
6、这些一次只允许一个进程使用的资源称为临界资临界资源源(critical resource)(critical resource)。打印机、内存变量、指针、数组等都是临界资源。打印机、内存变量、指针、数组等都是临界资源。生活中的例子如：电话机等。生活中的例子如：电话机等。临界资源需要采用互斥方式，实现对资源的共享。临界资源需要采用互斥方式，实现对资源的共享。干舷迈烤旅于愉储砧冰熏双剧收辽熙埂惧摹黎肺女铆榷扮露觉拴芜点割遥操作系统4-同步软硬件方法操作系统4-同步软硬件方法操作系统20114.9/212 2、临界区、临界区 每个进程中访问临界每个进程中访问临界资源的那段程序段称为资源的那段程序段称
7、为临界区（临界区（critical critical sectionsection）。）。三掘灸镊郊瘟且鹊妒赔忠爬礁嘴毅怕认判捂臆涸莹道亩兵脐槐波粒努哭曹操作系统4-同步软硬件方法操作系统4-同步软硬件方法操作系统20114.10/21访问临界资源的循环进程访问临界资源的循环进程Until false;Entry sectionCritical section;Exit sectionRemainder section;Repeat 进入区进入区：进入临界区之前，检查：进入临界区之前，检查可否进入临界区的一段代码。如果可否进入临界区的一段代码。如果可以进入临界区，通常设置相应可以进入临界区，通
8、常设置相应“正正在访问临界区在访问临界区”标志；标志； 临界区：临界区：进程中访问临界资源的进程中访问临界资源的一段代码；一段代码； 退出区：退出区：用于将用于将 正在访问临界正在访问临界区区 标志清除。标志清除。 剩余区剩余区：代码中的其余部分。：代码中的其余部分。纹泰撰氯泅寥伤服顽续电呈了插告关酶芥惹锅庐该洼痢延据椰谩己视蹭革操作系统4-同步软硬件方法操作系统4-同步软硬件方法操作系统20114.11/21进入区进入区临界区临界区退出区退出区进入区进入区临界区临界区退出区退出区.阻塞等待阻塞等待资源释放资源释放改变资源改变资源状态状态释放资源释放资源进程进程1进程进程2进入区、退出区各部分
9、的作用进入区、退出区各部分的作用笋张刺坷尿漫配屉唉赃矩吐慰览吴隅彰梭胎用担待氏纶企毗杏漏醋呻饱秋操作系统4-同步软硬件方法操作系统4-同步软硬件方法操作系统20114.12/213 3、同步机制应遵循的准则、同步机制应遵循的准则空闲则入：其他进程均不处于临界区；空闲则入：其他进程均不处于临界区；忙则等待：已有进程处于其临界区；忙则等待：已有进程处于其临界区；有限等待：等待进入临界区的进程不能有限等待：等待进入临界区的进程不能 死等死等 ；让权等待：不能进入临界区的进程，应释放让权等待：不能进入临界区的进程，应释放CPUCPU（如转换到阻塞状态）（如转换到阻塞状态）奏脖憋雏队牧骆斯翼误遏张载维廓
10、吉良柞粱清现谢矮饶幽苑恒湿相菏产浓操作系统4-同步软硬件方法操作系统4-同步软硬件方法操作系统20114.13/214 4、进程互斥的软件方法（补充）、进程互斥的软件方法（补充）算法算法1 1：强制轮换法（单标志）：强制轮换法（单标志）n设立一个公用整型变量设立一个公用整型变量 turn turn：描述允许进入临界区的进程标识：描述允许进入临界区的进程标识F在进入区检查是否允许本进程进入在进入区检查是否允许本进程进入:turn:turn为为i i时时, ,进程进程PiPi可进入可进入; ;F在退出区修改在退出区修改turnturn的值：的值：进程进程PiPi退出时退出时, ,改改turntur
11、n为为j j；n缺点：缺点：强制轮流强制轮流进入临界区，没进入临界区，没有考虑进程的实际需要。容易有考虑进程的实际需要。容易造成造成资源利用不充分资源利用不充分：在在PiPi出让临界区之后，出让临界区之后，PjPj使用临界区之前，使用临界区之前，PiPi不可能再不可能再次使用临界区；次使用临界区；Until false;RepeatWhile turn i do no_opCritical section;turn:=j;remainder section;n 有两个进程有两个进程Pi, PjPi, Pj，其中的，其中的PiPi溉员顽奄攻池厕倦峙攻珐彦甚惰碍曙辨操杆僧啪岸颧杯纪箩滔迎前硼千仟操
12、作系统4-同步软硬件方法操作系统4-同步软硬件方法操作系统20114.14/21算法算法2 2：锁变量方法（双标志、先检查）：锁变量方法（双标志、先检查）n优点优点: :不用交替进入不用交替进入, ,可连续使用可连续使用n缺点：缺点：PiPi和和PjPj可能同时进入临界可能同时进入临界区。按下面序列执行时，会同时区。按下面序列执行时，会同时进入：进入：Pi Pj Pi Pi Pj Pi PjPj。Until false;While flagj do no_op Flagi:=true； Critical section;Flagi:=false;remainder section;Repeat
13、n设立一个标志数组设立一个标志数组flagflag：描述进程是否在临界区，初值均为：描述进程是否在临界区，初值均为FALSEFALSE。F先检查，后修改：在进入区检查另一个进程是否在临界区，不在时先检查，后修改：在进入区检查另一个进程是否在临界区，不在时修改本进程在临界区的标志；修改本进程在临界区的标志；F在退出区修改本进程在临界区的标志；在退出区修改本进程在临界区的标志；扛瓶情茄为抿迟凑窑乱墅匆样哎躁莆亡衙匿乓扎遮祝炳猖仔圈寥丹幂斡赛操作系统4-同步软硬件方法操作系统4-同步软硬件方法操作系统20114.15/21算法算法3 3：锁变量方法（双标志、后检查）：锁变量方法（双标志、后检查）n缺
14、点：缺点：PiPi和和PjPj可能都进入不了临界区可能都进入不了临界区。按下面序列执行时，。按下面序列执行时，会都进不了临界区：会都进不了临界区：Pi Pj Pi PjPi Pj Pi Pj。Until false;Flagi:=true； While flagj do no_op Critical section;Flagi:=false;remainder section;Repeatn类似于算法类似于算法2 2，与，与2 2的区别在于先修改后检查。可防止两个进程同时的区别在于先修改后检查。可防止两个进程同时进入临界区。进入临界区。泞当捂碑螟射毙彭印遵希亦萌雇辊蚊禁昌域咕振编龄寇霓丸配费堤
15、肆淖载操作系统4-同步软硬件方法操作系统4-同步软硬件方法操作系统20114.16/21算法算法4(Peterson4(Petersons Algorithm)s Algorithm)：先修改、后检查、后修改者等待先修改、后检查、后修改者等待n结合算法结合算法1 1和算法和算法3 3，是正确的算法，是正确的算法nturn=j;turn=j;描述可进入的进程（同时修改标志时）描述可进入的进程（同时修改标志时）n在进入区先修改后检查，并检查并发修改的先后：在进入区先修改后检查，并检查并发修改的先后：F检查对方检查对方flagflag，如果不在临界区则自己进入，如果不在临界区则自己进入空闲则入空闲则
16、入F否则再检查否则再检查turnturn：保存的是较晚的一次赋值，则较晚的进：保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入程等待，较早的进程进入先到先入，后到等待先到先入，后到等待Until false;Flagi:=true;turn:=j;While(flagj and turn=j) do no_opCritical section;Flagi:=false;remainder section;Repeat豆咖猎裕芜著植硅辟肿二雄显焉遏忻痔陌骄氟湾罪胃披给荐瓤帘灵惑滔音操作系统4-同步软硬件方法操作系统4-同步软硬件方法操作系统20114.17/215 5、进程互斥的硬件方法
17、（补充）、进程互斥的硬件方法（补充）Test-and-SetTest-and-Set指令指令该指令读出标志后设置为该指令读出标志后设置为TRUETRUEboolean TS(boolean *lock) boolean TS(boolean *lock) boolean old; boolean old; old = *lock; *lock = TRUE; old = *lock; *lock = TRUE; return old; return old; locklock表示资源的两种状态：表示资源的两种状态：TRUETRUE表示正被占用，表示正被占用，FALSEFALSE表示空闲表示空闲
18、n完全利用软件方法，有很大局限性（如不适于多进程），实现过完全利用软件方法，有很大局限性（如不适于多进程），实现过于复杂，需要高的编程技巧。于复杂，需要高的编程技巧。n可以利用某些硬件指令可以利用某些硬件指令其读写操作由一条指令完成，因而保其读写操作由一条指令完成，因而保证读操作与写操作不被打断；证读操作与写操作不被打断；邑孜栓零愧焉佐乙绑阜砌诬笨驼熬狗耀北氦画内觅隆沸澡语痕践崖寐津拴操作系统4-同步软硬件方法操作系统4-同步软硬件方法操作系统20114.18/21利用利用TSTS实现进程互斥实现进程互斥Until false;While TS(lock) do skipCritical se
19、ction;lock:=false;remainder section;Repeatn利用利用TSTS实现进程互斥：每个临界资源设置一个公共布尔变量实现进程互斥：每个临界资源设置一个公共布尔变量locklock，初值为，初值为FALSEFALSEn在进入区利用在进入区利用TSTS进行检查：有进程在临界区时，重复检查；进行检查：有进程在临界区时，重复检查；直到其它进程退出时，检查通过；直到其它进程退出时，检查通过；boolean TS(boolean *lock) boolean TS(boolean *lock) boolean old; boolean old; old = *lock; *
20、lock = old = *lock; *lock = TRUE;TRUE; return old; return old; 钨启葬狐迁望腊叮刀使疗指熄仅器宪郧序良堑闽钩勇胚杆斧干誓删愁铰类操作系统4-同步软硬件方法操作系统4-同步软硬件方法操作系统20114.19/21SwapSwap指令（或指令（或ExchangeExchange指令）指令）交换两个字（字节）的内容：交换两个字（字节）的内容：void SWAP(int *a, int *b) void SWAP(int *a, int *b) int temp; int temp; temp = *a; temp = *a; *a = *
21、b; *a = *b; *b = temp; *b = temp; 华炳交邱墒我蛾臼培酞锑老嗡宫烽耶谜躁加谨衣藐尸格洲贿示舟嗽刽蔡黍操作系统4-同步软硬件方法操作系统4-同步软硬件方法操作系统20114.20/21利用利用SwapSwap指令实现互斥算法指令实现互斥算法n利用利用SwapSwap实现进程互斥：每个临界资源设置一个公共布尔变量实现进程互斥：每个临界资源设置一个公共布尔变量locklock，初值为，初值为FALSEFALSE。每个进程设置一个私有布尔变量。每个进程设置一个私有布尔变量keykeyWhile(1);Key:=true;Do Swap(&lock,&key);while
22、(key);Critical section;lock=false;remainder section;Dovoid SWAP(int *a,int *b)void SWAP(int *a,int *b) int temp; int temp; temp = *a; temp = *a; *a = *b; *a = *b; *b = temp; *b = temp; 欺辟幼怠倦孤奋熊姑对么帽腔宠皇遗腾弗弛茁暮捡糙力挖梳猾柯凋柏妹眺操作系统4-同步软硬件方法操作系统4-同步软硬件方法操作系统20114.21/21硬件方法的优缺点硬件方法的优缺点n优点优点F适用于任意数目的进程，在单处理器或多处理器上适用于任意数目的进程，在单处理器或多处理器上F简单，容易验证其正确性简单，容易验证其正确性F可以支持进程内存在多个临界区，只需为每个临界可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量区设立一个布尔变量n缺点缺点F等待要耗费等待要耗费CPUCPU时间，仍然不能实现时间，仍然不能实现 让权等待让权等待 振勺狸袍侩按榆待窑贬媳迟跪缘扰盈破盏逐声菠恍嘲滦危退剑电违皆铱剥操作系统4-同步软硬件方法操作系统4-同步软硬件方法操作系统
