os10-实验四-经典的进程同步问题

例题1（北京大学1999年）有一个仓库，可以存放A和B两种产品，仓库的存储空间足够大，但要求：(1)一次只能存人一种产品（(A或B);(2)一N< A产品数量一B产品数量＜M其中，N和M是正整数。

试用“存放A’和‘存放B’以及P操作和V操作描述产品A和产品B的人库过程。

解答：应先将表达式转换成制约条件，不可在程序中直接使用该表达式将表达式分解为：B产品数量—A产品数量<NA产品数量—B产品数量＜M可这样理解：(1)若只放人A产品，而不放入B产品，则A产品最多可放M—1次便被阻塞，即A进程每操作一次就应当将计数器减1（计数器初值为M—1），当计数器值为0时，进程程A被阻塞；每当放入一个B产品，则可令A产品的计数器增加1，表明A产品可以多一次放入产品的机会；同理，(2)若只放人B产品，而不放入A产品，则B产品最多可；放N一1次便被阻塞，即A进程每操作一次就应当将计数器减1（计数器初值为N—1）。

当计数器值为0时，进程B被阻塞；每当放人一个A产品，则可令B产品的计数器增加1，表明B产品可以多一次放入产品的机会。

由此可见，该问题是一个同步控制问题。

又因为一次仅允许一种产品人库，设置信号量mutex控制粮进程互斥访问临界资源（仓库）。

过程如下：beginmutex:＝1;Sa := M-1;Sb := N-1；ParbeginA产品beginrepeatP (Sa)；P (mutex)；A人库；V (mutex)；V (Sb)；Until false;End;B产品beginrepeatP (Sb)；P (mutex)；B人库；V (mutex)；V (Sa)；Until false;End;rend;例题2（华中理工大学1999年试题）设公共汽车上，司机和售票员的活动分别是：司机：售票员：启动车辆上乘客正常行车关车门到站停车售票开车门下乘客在汽车不断地到站，停车，行驶过程中，这两个活动有什么同步关系？并用信号灯的P, V操作实现它们的同步。

进程同步——经典的同步问题本⽂为博主原创⽂章，未经博主允许不得转载涉及进程同步的⼀些概念：互斥与同步:临界资源（临界区）：指⼀次只能允许⼀个进程使⽤的共享资源称为临界资源；同步：指为完成某种任务⽽建⽴的两个和多个进程，这些进程在合作的过程中需要协调⼯作次序进⾏有序的访问⽽出现等待所产⽣的制约关系。

互斥：指两个或多个进程访问临界资源时只能⼀个进程访问，其他进程等待的⼀种相互制约的关系。

信号量与互斥量：信号量：本⾝是⼀个计数器，使⽤P，V两个操作来实现计数的减与加，当计数不⼤于0时，则进程进⼊睡眠状态，它⽤于为多个进程提供共享数据对象的访问。

互斥量：如果信号量只存在两个状态，那就不需要计数了，可以简化为加锁与解锁两个功能，这就是互斥量。

⼀、⽣产者与消费者问题问题描述：⼀组⽣产者进程和⼀组消费者进程共享⼀块初始为空，⼤⼩确定的缓冲区，只有当缓冲区为满时，⽣产者进程才可以把信息放⼊缓冲区，否则就要等待；只有缓存区不为空时，消费者进程才能从中取出消息，否则就要等待。

缓冲区⼀次只能⼀个进程访问（临界资源）。

问题分析：⽣产者与消费者进程对缓冲区的访问是互斥关系，⽽⽣产者与消费者本⾝⼜存在同步关系，即必须⽣成之后才能消费。

因⽽对于缓冲区的访问设置⼀个互斥量，再设置两个信号量⼀个记录空闲缓冲区单元，⼀个记录满缓冲区单元来实现⽣产者与消费者的同步。

问题解决：伪代码实现semaphore mutex=1;semaphore full=0; //满缓冲区单元semaphore empty=N; //空闲缓冲区单元prodecer(){while(1){P(empty);P(mutex);add_source++;V(mutex);V(full);}}consumer(){while(1){P(full);P(mutex);add_source--;V(mutex);V(empty);}}⼆、读者与写者问题问题描述：有读者与写者两个并发进程共享⼀个数据，两个或以上的读进程可以访问数据，但是⼀个写者进程访问数据与其他进程都互斥。

计算机科学与技术学院实验报告int msq_id;if((msq_id = get_ipc_id("/proc/sysvipc/msg",msq_h)) < 0 ) { if((msq_id = msgget(msq_h,msq_flg)) < 0){perror("messageQueue set error");exit(EXIT_FAILURE);}}return msq_id;}实验结果：分析：多进程的系统中避免不了进程间的相互关系。

进程互斥是进程之间发生的一种间接性作用，一般是程序不希望的。

通常的情况是两个或两个以上的进程需要同时访问某个共享变量。

我们一般将发生能够问共享变量的程序段称为临界区。

两个进程不能同时进入临界区，否则就会导致数据的不一致，产生与时间有关的错误。

解决互斥问题应该满足互斥和公平两个原则，即任意时刻只能允许一个进程处于同一共享变量的临界区，而且不能让任一进程无限期地等待。

进程同步是进程之间直接的相互作用，是合作进程间有意识的行为，典型的例子是公共汽车上司机与售票员的合作。

只有当售票员关门之后司机才能启动车辆，只有司机停车之后售票员才能开车门。

司机和售票员的行动需要一定的协调。

同样地，两个进程之间有时也有这样的依赖关系，因此我们也要有一定的同步机制保证它们的执行次序。

信号量机制就是其中的一种。

信号灯机制即利用pv操作来对信号量进行处理。

PV操作由P操作原语和V 操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下： P（S）：①将信号量S的值减1，即S=S-1；②如果S³0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。

V（S）：①将信号量S的值加1，即S=S+1；②如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。

PV操作的意义：我们用信号量及PV操作来实现进程的同步和互斥。

实验四生产者消费者实验：用信号量实现PV操作实验目的1、熟悉PV操作的实现原理。

2、了解进程间通信机制。

熟悉信号量机制。

使用信号量机制模拟实现PV操作，从而控制多个进程对共享资源的使用。

实验内容1、使用信号量机制来模拟实现PV操作。

2、编写一个简单的程序，使用该PV模拟操作控制多进程对共享资源的使用。

实验基础一、信号量基础1、进程间通信机制进程间通信机制包括共享内存(shared memory)、信号量(semaphores)和消息队列(Message Queue)等一系列进程通信方式。

System V IPC的进程间通信机制一个显著特点是：在内核中它的具体实例是以对象的形式出现的——被称之为IPC对象。

每个IPC对象在系统内核中都有一个惟一的标识符。

通过标识符内核可以正确地引用指定的IPC对象。

要注意的是，标识符的惟一性只在每一类的IPC对象内成立。

例如，一个消息队列和一个信号量的标识符可能相同，但是绝对不允许两个消息队列使用相同的标识符。

IPC对象在程序中通过关键字(key)来访问内核中的标识符。

与IPC对象标识符相同，关键字也是惟一的。

而且，如果要访问同一个IPC对象，客户和服务器就必须使用同一个关键字。

因此，建立IPC对象时要解决的首要的一个问题，就是如何构造新的关键字使之不与已有的关键字发生冲突，并能保证客户和服务器使用相同的关键字。

2、信号量信号量是一个计数器，用来控制多个进程对共享资源的使用。

进程为了获得共享资源，需要执行下列操作：(1) 测试控制该资源的信号量。

(2) 若此信号量的值为正，则进程可以使用该资源。

进程将信号量值减1，表示它使用了一个资源单位。

(3) 若此信号量的值为0，则进程进入睡眠状态，直至信号量值大于0。

若进程被唤醒后，它返回至(第(1)步)。

当进程不再使用由一个信息量控制的共享资源时，该信号量值增1。

如果有进程正在睡眠等待此信号量，则唤醒它们。

为了正确地实现信息量，信号量值的测试及减1操作应当是原子操作。

操作系统实验报告哈尔滨工程大学软件学院．第六讲进程的同步一、实验概述1. 实验名称实验系统的启动2. 实验目的1).使用EOS 的信号量编程解决生产者—消费者问题，理解进程同步的意义。

2).调试跟踪EOS 的信号量的工作过程，理解进程同步的原理。

3).修改EOS 的信号量算法，使之支持等待超时唤醒功能（有限等待），加深理解进程同步的原理。

3. 实验类型（验证、设计）验证4. 实验内容1).准备实验2).使用EOS的信号量解决生产者－消费者问题3).调试EOS信号量的工作过程①创建信号量②等待释放信号量③等待信号量（不阻塞）④释放信号量（不唤醒）⑤等待信号量（阻塞）⑥释放信号量（唤醒）4).修改EOS的信号量算法在目前EOS Kernel项目的ps/semaphore.c文件中，PsWaitForSemaphore函数的Milliseconds参数只能是INFINITE，PsReleaseSemaphore 函数的ReleaseCount 参数只能是1。

现在要求同时修改PsWaitForSemaphore函数和PsReleaseSemaphore 函数中的代码，使这两个参数能够真正起到作用，使信号量对象支持等待超时唤醒功能和批量释放功能。

二、实验环境操作系统：windows xp编译环境：OS Lab1三、实验过程1. 设计思路和流程图准备实验的信号量解决EOS使用整体试验流程图图3-1. 2函数开始ConsumerProducer函数开始函数开始mainProd对象Mutex创建ucer生产完Consumer费消数函毕？函数结束毕完结束信号Empty创建量对信号量对释Empty3-2.Main图函数流程图、生产者消费、消费者流程图32. 需要解决的问题及解答(1).思考在ps/semaphore.c文件内的PsWaitForSemaphore和PsReleaseSemaphore 函数中，为什么要使用原子操作？答：在执行等待信号量和释放信号量的时候，是不允许cpu响应外部中断的，如果此时cpu响应了外部中断，会产生不可预料的结果，无法正常完成原子操作。

操作系统实验报告——进程同步与互斥一、实验内容本实验主要内容是通过编写程序来实现进程的同步与互斥。

具体来说，是通过使用信号量来实现不同进程之间的同步和互斥。

我们将编写两个进程，一个进程负责打印奇数，另一个进程负责打印偶数，两个进程交替打印，要求打印的数字从1开始，直到100结束。

二、实验原理进程的同步是指多个进程之间按照一定的顺序执行，进程之间互相等待的关系。

而进程的互斥是指多个进程竞争同一个资源，需要通过其中一种方式来避免同时访问共享资源，以免造成数据错乱。

在本实验中，我们使用信号量来实现进程的同步与互斥。

信号量是一个计数器，用于表示一些共享资源的可用数量。

进程在访问共享资源时，需要先对信号量进行操作，当信号量大于0时，表示资源可用，进程可以访问；当信号量等于0时，表示资源不可用，进程需要等待。

进程同步的实现可以通过信号量的P操作与V操作来完成。

P操作用于申请资源，当资源可用时，将计数器减一，并进入临界区；V操作用于释放资源，当资源使用完毕时，将计数器加一，使等待资源的进程能够申请。

进程互斥的实现可以通过信号量的P操作与V操作结合临界区来完成。

当多个进程需要访问共享资源时，需要先进行P操作，进入临界区，访问完毕后进行V操作，离开临界区。

三、实验步骤1.首先，我们需要创建两个进程，一个进程负责打印奇数，另一个进程负责打印偶数。

2. 然后，我们创建一个共享变量count，用来记录打印的数字。

3. 接着，我们创建两个信号量odd和even，用来控制进程的同步与互斥。

odd信号量初始值为1，表示打印奇数的进程可以访问；even信号量初始值为0，表示打印偶数的进程需要等待。

4.编写奇数打印进程的代码，首先进行P操作，判断奇数信号量是否大于0，如果大于0，表示可以打印奇数。

5. 如果可以打印奇数，将count加一，并输出当前的奇数，然后进行V操作，释放偶数打印进程的等待。

6.同样的，编写偶数打印进程的代码，首先进行P操作，判断偶数信号量是否大于0，如果大于0，表示可以打印偶数。

进程的同步实验报告进程的同步实验报告引言：进程同步是操作系统中一个重要的概念，它涉及到多个进程之间的协调和合作。

在本次实验中，我们将通过一个简单的实例来探讨进程同步的概念和实现方式。

实验目的：通过实验，我们的目标是理解进程同步的概念，学习常见的同步机制，并通过编程实现一个简单的同步问题。

实验环境：本次实验使用了C语言作为编程语言，并在Linux操作系统上进行。

实验过程：我们的实验场景是一个餐厅，有一个厨师和多个服务员。

厨师负责烹饪菜品，服务员负责上菜给客人。

我们需要实现的是，服务员只有在厨师烹饪好一道菜之后才能上菜，否则需要等待。

首先，我们使用互斥锁来实现进程间的同步。

互斥锁是一种常见的同步机制，它可以确保在同一时间只有一个进程可以访问共享资源。

在我们的实验中，厨师和服务员都需要访问菜品资源，因此我们为菜品资源添加了一个互斥锁。

接下来，我们使用条件变量来实现进程间的等待和唤醒操作。

条件变量是一种同步机制，它可以让进程在某个条件满足时等待，直到被唤醒。

在我们的实验中，服务员需要等待厨师烹饪好菜品之后才能上菜，因此我们创建了一个条件变量，并在服务员的代码中使用了等待和唤醒操作。

实验结果：经过实验，我们成功地实现了进程间的同步。

在我们的实验场景中，厨师会不断地烹饪菜品，并在烹饪完成后通知服务员上菜。

服务员会等待厨师的通知，然后上菜给客人。

通过互斥锁和条件变量的使用，我们保证了服务员只会在厨师烹饪完成后才会上菜，避免了资源竞争和错误的上菜行为。

讨论与总结：通过本次实验，我们深入理解了进程同步的概念和实现方式。

互斥锁和条件变量是常见的同步机制，它们可以有效地解决进程间的竞争和协调问题。

在实际的操作系统中，进程同步是一个非常重要的概念，它保证了多个进程之间的正确执行和合作。

然而，进程同步也可能引发一些问题。

例如，如果互斥锁的使用不当，可能会导致死锁的发生。

死锁是一种进程无法继续执行的状态，它会导致系统的停滞。

进程同步问题
为保证多个进程有条不紊的运⾏，在多道程序系统中，加⼊进程同步机制。

单处理机系统的进程同步问题：
硬件同步机制
信号量同步机制
管程机制
1. 进程同步的基本概念：
1. 两种形式的制约关系
1. 间接相互制约关系：⽐如打印机资源，要互斥的访问
2. 直接相互制约关系：未完成某个任务，多个进程为了完成任务⽽合作，例如共享缓冲区
2. 临界资源
1. 访问临界资源应该互斥的访问
2. 消费者⽣产者问题
3. 临界区：不论硬件资源还是软件资源，多个进程必须互斥的对它进⾏访问，每个进程中访问临界资源的那段代码称为临界区
4. 同步机制应遵循的规则
1. 空闲让进
2. 忙则等待
3. 优先等待
4. 让权等待
2. 硬件同步机制
1. 关中断
2. test-and-set指令实现互斥
3. 利⽤swap指令实现互斥
3. 信号量机制
1. 整形信号量：
wait机制，当s<=0时，不断测试，该机制为遵循让权等待，⽽是陷⼊忙等状态
2. 记录型信号量
3. AND型信号量
4. 信号量机制
1.
5. 信号量的应⽤
1. 利⽤信号量实现进程互斥
2. 利⽤信号量实现前趋关系
6. 管程机制
1. 利⽤共享的数据抽象类型表⽰共享资源，并对共享数据类型定义⼀组操作
2. 管程组成
1. 管程名称
2. 局部于管理的共享数据结构说明
3. 对该数据结构上进⾏操作的⼀组过程
4. 对局部于管程的共享数据设置初始值的语句
3.。

操作系统实验4-4实验报告一、实验目的本次操作系统实验 4-4 的目的是深入了解和掌握操作系统中进程管理的相关知识和技术，通过实际操作和观察，加深对进程调度算法、进程同步与互斥等概念的理解，并提高解决实际问题的能力。

二、实验环境本次实验使用的操作系统为 Windows 10，编程环境为 Visual Studio 2019。

三、实验内容1、进程调度算法的实现先来先服务（FCFS）算法短作业优先（SJF）算法时间片轮转（RR）算法优先级调度算法2、进程同步与互斥的实现使用信号量实现生产者消费者问题使用互斥锁实现哲学家进餐问题四、实验步骤1、进程调度算法的实现先来先服务（FCFS）算法设计数据结构来表示进程，包括进程ID、到达时间、服务时间等。

按照进程到达的先后顺序将它们放入就绪队列。

从就绪队列中选择第一个进程进行处理，计算其完成时间、周转时间和带权周转时间。

短作业优先（SJF）算法在设计的数据结构中增加作业长度的字段。

每次从就绪队列中选择服务时间最短的进程进行处理。

计算相关的时间指标。

时间片轮转（RR）算法设定时间片的大小。

将就绪进程按照到达时间的先后顺序放入队列。

每个进程每次获得一个时间片的执行时间，若未完成则重新放入队列末尾。

优先级调度算法为每个进程设置优先级。

按照优先级的高低从就绪队列中选择进程执行。

2、进程同步与互斥的实现生产者消费者问题创建一个共享缓冲区。

生产者进程负责向缓冲区中生产数据，消费者进程从缓冲区中消费数据。

使用信号量来控制缓冲区的满和空状态，实现进程的同步。

哲学家进餐问题模拟多个哲学家围绕一张圆桌进餐的场景。

每个哲学家需要同时获取左右两边的筷子才能进餐。

使用互斥锁来保证筷子的互斥访问，避免死锁的发生。

五、实验结果与分析1、进程调度算法的结果与分析先来先服务（FCFS）算法优点：实现简单，公平对待每个进程。

缺点：对短作业不利，平均周转时间可能较长。

短作业优先（SJF）算法优点：能有效降低平均周转时间，提高系统的吞吐量。

进程同步问题总结进程同步是计算机科学中一个重要的概念，用于解决多个进程共享资源时可能出现的数据竞争和不一致性的问题。

在并发编程中，正确的进程同步机制对于保证系统的正确性和可靠性至关重要。

本文将总结常见的进程同步问题及其解决方案。

1. 互斥问题：当多个进程共享一个临界资源时，可能会发生互斥问题。

如果一个进程占用了临界资源，其他进程就无法使用该资源，导致资源的浪费和性能下降。

解决方案：（1）锁机制：通过使用锁（如互斥锁、自旋锁、读写锁）来保护临界资源。

一旦某个进程获得了锁，其他进程就需要等待，直到锁被释放。

（2）信号量：通过使用信号量来管理对临界资源的访问。

信号量可以用来限制同时访问资源的进程数量。

2. 死锁问题：当多个进程相互等待其他进程释放资源时，可能会发生死锁问题。

即使每个进程都只需要一个资源，但由于资源的分配不当，导致进程无法继续执行。

解决方案：（1）避免循环等待：对于进程需要的资源排序，使得每个进程按照同一种顺序请求资源，从而避免进程之间出现循环等待的情况。

（2）资源预分配：进程在开始执行之前，请求所有需要的资源。

这样可以避免在执行过程中发生资源竞争导致死锁。

（3）超时机制：设定一个等待时间，如果在该时间内没有获得所需资源，就主动释放已获得的资源，并重新开始执行。

3. 竞争条件问题：当多个进程同时竞争访问共享资源时，可能会出现竞争条件问题。

竞争条件指的是多个进程之间的执行顺序会影响最终的结果。

解决方案：（1）原子操作：通过原子操作来确保对共享资源的访问是原子性的，不可中断的。

例如使用原子锁或原子变量等。

（2）同步工具：使用同步工具，如条件变量、屏障等来协调多个进程的执行顺序，以避免竞争条件的出现。

（3）尽量避免共享数据：如果可能的话，尽量避免多个进程之间共享数据，减少竞争条件的发生。

4. 内存一致性问题：在分布式系统中，不同节点的内存可能存在一致性问题。

当一个进程修改了自己所在节点的内存，并且其他节点也有相应的副本时，就可能会出现读取到不一致数据的问题。

操作系统：进程同步三⼤经典问题⽇期：2019/4/15内容：进程同步；⽣产者与消费者；读写者；哲学家进餐；信号量机制。

⼀、⽣产者与消费者问题1.1 版本1代码void producer(){while (count == n);buff[in] = produce_item(); in = (in + 1) % n;count++;}void consumer(){while (count == 0) ;item = buff[out];print(item);out = (out + 1) % n; count--;}存在问题>>两个while循环⼀直在"忙等"，不符合进程同步的"让权等待"原则。

>>对于count变量的访问没有保护。

（需要加锁保护）1.2 版本2：使⽤信号量代码semaphore empty = n, full = 0; void producer(){while (true){wait(empty);buffer[in] = produce_item(); in = (in + 1) % n;signal(full);}}void consumer(){while (true){wait(full);item = buffer[out]; print(item);out = (out + 1) % n; signal(empty);}}存在问题>>如果有2个producer进程，empty>=2时，同时进⼊wait(empty)之后的临界区，对于buff的写和in的写产⽣竞争。

>>如果有2个consumer进程，full>=2时，同时进⼊wait(full)之后的临界区，对于out的写产⽣竞争。

1.3 版本3：临界区加锁（正确版本）代码semaphore pmutex = 1, cmutex = 1; semaphore empty = n, full = 0; void producer(){while (true){wait(empty);wait(pmutex);buff[in] = produce_item();in = (in + 1) % n;signal(pmutex);signal(full);}}void consumer(){while (true){wait(full);wait(cmutex);item = buff[out];print(item);out = (out + 1) % n; signal(cmutex);signal(empty);}}注：教材对于producer和consumer的临界区都使⽤了同⼀个mutex，表⽰producer和consumer互斥进⼊临界区。

进程同步练习题1.在公共汽车上，司机和售票员的工作流程如图所示。

为保证乘客的安全，司机和售票员应密切配合协调工作。

请用信号量来实现司机与售票员之间的同步。

司机售票员图司机和售票员工作流程图①约束：怎么密切配合协调工作才能保证安全呢？a)关车门之后再启动车辆；利用前驱图解释b)到站停车之后再开车门；②根据约束定义信号量；关车门和启动车辆需要一个信号量进行同步S1；到站停车和开车门之间需要一个信号量进行同步S2；③建立几个进程呢？a)为司机建立一个进程Driver；b)为售票员建立一个进程Conductor；Driver：Repeat启动车辆；正常行驶；到站停车；Until false;Conductor：Repeat关车门；售票；开车门；Until false;④加入同步关系：Driver：RepeatWait (s1);启动车辆；正常行驶；到站停车；Signal(s2)Until false;Conductor：Repeat关车门；Signal(s1);售票；Wait(s2)开车门；Until false;main(){Driver();Conductor ();}2.桌子上有一只盘子，盘子中只能放一只水果。

爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，一个儿子专等吃盘子中的橘子，一个女儿专等吃盘子中的苹果。

用PV操作实现他们之间的同步机制。

分析：①约束：a)爸爸和妈妈竞争盘子，往盘子放水果，爸爸在放时，妈妈等待，或者相反；b)爸爸和女儿要同步，即爸爸放完苹果之后通知女儿来吃；同时女儿吃完之后要通知盘子可用；c)妈妈和儿子要同步，即妈妈放完橘子之后通知儿子来吃；同时儿子吃完之后要通知盘子可用；②经上述分析可知：需要3个信号量：S1表示临界资源盘子，初值1；爸爸和女儿需要一个信号量进行同步S2=0 妈妈和儿子需要一个信号量进行同步S3=0;③建立进程？爸爸：妈妈：女儿：儿子：取一个苹果；取一个橘子；从盘子取一个苹果；从盘子取一个橘子；放入盘子；放入盘子吃苹果；吃橘子；Until false; Until false; Until false; Until false;④加入同步关系。