操作系统专题讨论及小结

《操作系统专题讨论及小结》由会员分享，可在线阅读，更多相关《操作系统专题讨论及小结（8页珍藏版）》请在装配图网上搜索。

1、2011-2012第一学期操作系统专题讨论及小结系别： 管理系 学号： 0913011031 姓名： 马 明 专业： 信息管理与信息系统 成绩： 讨论题目：利用信号量机制解决进程同步和互斥问题提示：可从以下几个方面着手1、 先要明确一些重要概念（同步、互斥、直接制约、间接制约、临界区等）；2、 从系统和用户的角度阐述一下进程并发的重要性和必要性；3、 非信号量机制存在的问题（要有例证和分析）；4、 信号量机制的原理阐述；5、 解决同步与互斥问题的案例（最好是生活化的，要有分析）；6、 优点总结；7、 信号量机制总结8、 缺点和不足之处总结；注：以上内容涵盖到就可以，但条理要清晰，逻辑要合理，例

2、证要浅显易懂（最好有注释）。正文： 进程互斥是进程之间发生的一种间接性作用，一般是程序不希望的。通常的情况是两个或两个以上的进程需要同时访问某个共享变量。我们一般将发生能够问共享变量的程序段成为临界区。两个进程不能同时进入临界区，否则就会导致数据的不一致，产生与时间有关的错误。解决互斥问题应该满足互斥和公平两个原则，即任意时刻只能允许一个进程处于同一共享变量的临界区，而且不能让任一进程无限期地等待。互斥问题可以用硬件方法解决，我们不作展开；也可以用软件方法。 进程同步是进程之间直接的相互作用，是合作进程间有意识的行为典型的例子信号量是最早出现的用来解决进程同步与互斥问题的机制，包括一个称为信号

3、量的变量及对它进行的两个原语操作，每个信号量至少须记录两个信息：信号量的值和等待该信号量的进程队列。进程具有并发性。多个进程实体同存于内存中，在一段时间内可以同时运行。并发性是进程的重要特性，也是操作系统的重要特性。引入进程概念的目的，也正是为了描述和实现并发执行。系统中各个并发程序活动具有独立性的一面，但在两个并发程序活动之间有时也会有相互依赖和相互制约关系。程序之间的制约关系有两种：直接制约关系和间接制约关系。直接制约关系通常是在彼此之间有逻辑关系的两个并发执行的程序之间发生的，一般是由于各个程序段要求共享信息引起的。间接制约关系是由于两个并发程序段由于竞争使用同一资源引起的，得到资源的程

4、序段可以继续执行，得不到资源的程序段就只好暂停等待，直至获得可用资源时再继续运行。信号量原理案例分析： 利用记录型信号量解决哲学家进餐问题 经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。其描述如下： Var chopstick: array0, , 4 of semaphore;所有信号量均被初始化为1， 第i位哲学家的活动可描述为： repeat wait(chopsticki); wait(chopstick(i+1) mod 5); eat; signal(chopstick

5、i); signal(chopstick(i+1) mod 5); think; until false; 存在的问题？上述方法可以保证不会有两个相邻的哲学家同时进餐，但有可能产生死锁。 假如五个哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为0；当他们去取右边的筷子时都将因无筷子可拿而无限期等待。可采取以下几种解决方法： (1) 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。 (2) 仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。 (3) 规定奇数号哲学家先

6、拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。按此规定，将是1、 2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。 2. 利用AND信号量机制解决哲学家进餐问题 在哲学家进餐问题中，要求每个哲学家先获得两个临界资源(筷子)后方能进餐，这在本质上就是前面所介绍的AND同步问题，故用AND信号量机制可获得最简洁的解法。Var chopstick array 0, , 4 of semaphore =(1,1,1,1,1); processi repeat think; P(cho

7、pstick(i+1) mod 5, chopstick i); eat; V(chopstick (i+1) mod 5, chopstick i); until false;解决同步与互斥问题的案例同步互斥之生产者消费者问题 生产者消费者同步问题其实际上就是生活中同步、互斥问题的一个抽象模型，如多个进程合作解决文件打印的问题，汽车行驶过程中司机与售票员的活动问题，理发师理发问题等等。 要解决同步互斥问题，最主要的是理清楚活动者之间的同步关系，还有某些问题中变量的互斥问题。分析清楚之后就是设置信号量，设置几个，并且根据实际情况给出信号量的初值。 生产者消费者问题就是生产者进程向消费者进程提供

8、消息。生产者生产商品存入空缓冲区内，而消费者从缓冲区内取出产品并消费。1、 一个生产者P和一个消费者Q（其中只有同步问题）其同步关系为：（1） P进程不能向“满”的缓存区内存放产品，即仅当有一个空缓存区时才能放产品，设置信号量empty,初值为0，用于指示空缓存区数目。（2） Q进程不能从空的缓存区中取产品，设置信号量full，初值为0，用于指示满缓存区的数目。 注意：a）在P、V操作中，P、V操作必须成对出现；b）在互斥关系中P、V操作在同一进程内；c）在同步关系中P、V操作在不同的进程内。其同步问题解决如下： P: /生产者 repeat 生产一个产品; 送产品到缓冲区; V(full);

9、/释放一个满的缓冲区; P(empty); /申请一个空的缓冲区存放产品;until false;Q: /消费者repeatP(full);/申请一个满的缓存区取产品从缓存区取产品;V(empty);/产品取完后释放掉该空的缓存区消费产品;until false;2、 多个生产者和多个消费者多个生产者和消费者问题中，缓存区属于临界资源，它只允许一个生产者放入产品或者一个消费者从中取产品。生产者之间、生产者与消费者之间、消费者之间都必须互斥的使用缓冲区。其中既存在同步问题，又存在互斥问题。其同步关系为：（1） 至少有一个缓冲区已存入消息后，消费者才能从中提取消息，否则消费者必须等待。设置信号量e

10、mpty,初值为n，用于指示空缓冲区的数目；（2） 至少有一个缓存区是空的，生产者才能将消息存入缓冲区，否则生产者必须等待。设置信号量full,初值为0，用于指示满缓冲区的数目； 其互斥关系为：（1） 设置信号量mutex，初值为1，用于实现临界区的互斥；（2） 另设整型i,j,初值都为0，i用于指示空缓存区，j用于指示满缓存区。其程序如下：P: i=0; repeat生产产品;P(empty); / 申请一个空缓存区存放生产的产品P(mutex); 往bufferi中放产品;i=(i+1) mod k;V(mutex);V(full); /释放一个满的缓存区until false;注意红色两

11、个P操作的顺序不能颠倒。如果将两个P操作，即P(full)和P(mutex)互换位置，或者P(empty)和P(mutex)互换位置，都可能引起死锁。考虑系统中缓冲区全满前时，若一生产者进程先执行了P(mutex)操作并获得成功，当再执行P(empty)操作时，它将因失败而进入阻塞状态，它期待消费者执行V(empty)来唤醒自己。在此之前，它不可能执行V(mutex)操作，从而使企图通过P(mutex)进入自己的临界区的其他生产者和所有的消费者进程全部进入阻塞状态，从而引起系统死锁。类似地，消费者进程若先执行P(mutex)，后执行P(full)，同样可能造成死锁。V(full)和V(mute

12、x)互换位置，或者V(empty)和V(mutcx)互换位置，则不会引起死锁，其影响只是使临界资源的释放略为推迟一些。Q：j=0;repeatP(full);P(mutex);从bufferi中取产品;j=(j+1) mod k;V(mutex);V(empty);消费产品;until false;优缺点总结： 信号量机制:一个信号量只能置一次初值，以后只能对之进行p操作或v操作。由此也可以看到，信号量机制必须有公共内存，不能用于分布式操作系统，这是它最大的弱点。自旋锁:旋锁是为了保护共享资源提出的一种锁机制。调用者申请的资源如果被占用，即自旋锁被已经被别的执行单元保持，则调用者一直循环在那里

13、看是否该自旋锁的保持着已经释放了锁自旋锁是一种比较低级的保护数据结构和代码片段的原始方式，可能会引起以下两个问题;（1）死锁（2）过多地占用CPU资源管程：信号量机制功能强大，但使用时对信号量的操作分散，而且难以控制，读写和维护都很困难。因此后来又提出了一种集中式同步进程管程。其基本思想是将共享变量和对它们的操作集中在一个模块中，操作系统或并发程序就由这样的模块构成。这样模块之间联系清晰，便于维护和修改，易于保证正确性。会合：进程直接进行相互作用分布式系统:由于在分布式操作系统中没有公共内存，因此参数全为值参， 而且不可为指针。信号量（Semaphore）及PV操作优：PV操作能够实现对临界区

14、的管理要求；实现简单；允许使用它的代码休眠，持有锁的时间可相对较长。缺：一个信号量只能置一次初值，以后只能对之进行p操作或v操作。由此也可以看到，信号量机制必须有公共内存，不能用于分布式操作系统，这是它最大的弱点。信号量机制功能强大，但使用时对信号量的操作分散，而且难以控制，读写和维护都很困难。加重了程序员的编码负担；核心操作P-V分散在各用户程序的代码中，不易控制和管理；一旦错误，后果严重，且不易发现和纠正。自旋锁:优：旋锁是为了保护共享资源提出的一种锁机制； 调用者申请的资源如果被占用，即自旋锁已经被别的执行单元保持，则调用者一直循环在那里看是否该自旋锁的保持者已经释放了锁； 低开销；安全

15、和高效；缺：自旋锁是一种比较低级的保护数据结构和代码片段的原始方式，可能会引起以下两个问题;（1）死锁（2）过多地占用CPU资源传统自旋锁由于无序竞争会导致“公平性”问题管程：优： 集中式同步进程管程。其基本思想是将共享变量和对它们的操作集中在一个模块中，操作系统或并发程序就由这样的模块构成。这样模块之间联系清晰，便于维护和修改，易于保证正确性。缺：如果一个分布式系统具有多个CPU，并且每个CPU拥有自己的私有内存，它们通过一个局域网相连，那么这些原语将失效。而管程在少数几种编程语言之外又无法使用，并且，这些原语均未提供机器间的信息交换方法。会合：进程直接进行相互作用分布式系统:消息和rpc由于在分布式操作系统中没有公共内存，因此参数全为值参， 而且不可为指针。