同步与互斥

习题解答:

?何谓与时间有关的错误? 举例说明之。

答：并发进程的执行实际上是进程活动的某种交叉，某些交叉次序可能得到错误结果。由于具体交叉的形成与进程的推进速度有关，而速度是时间的函数，因而将这种错误称为与时间有关的错误。

例如，两个并发进程的程序如下：

int n=0;

main( ){

创建进程A；

创建进程B；

}；

A( ){ while(1){ n++;

}

}; B( ){

while(1){

睡眠一段时间；printf(“%d”,n); n=0;

}

};

假设进程A被部署在公园入口的终端上，用来记录一段时间内进入公园的人数，进程B被部署在公园的控制中心，用来输出一段时间内进入公园的总人数。进程A和进程B共享全局变量n，n表示记录下的人数。如果在进程B执行完打印语句后被进程A打断，进程A执行了若干次变量自增语句，之后进程B接着执行清0语句，那么进程A对n的累加丢失了，相当于进程B被打断的这段时间内进入公园的人没有被记录下来。发生与时间有关的错误。

?有人说，假设两个进程之间没有共享内存，则二者之间没有公共变量，这种说法准确吗? 说明原因。

答：如果只从用户空间考虑，这种说法是正确的。但从操作系统的角度来说并不准确。两个没有公共内存的用户进程可能同时（宏观）进入操作系统，并访问操作系统空间中的公共变

量。

?何谓忙式等待? 是否还有其它方式的等待? 比较它们之间的联系和差别。

答：不进入等待状态的等待称为忙式等待。另一种等待方式是阻塞式等待，进程得不到共享资源时将进入阻塞状态，让出CPU给其他进程使用。忙等待和阻塞式等待的相同之处在于进程都不具备继续向前推进的条件，不同之处在于处于忙等待的进程不主动放弃CPU，尽管CPU 可能被剥夺，因而是低效的；而处于阻塞状态的进程主动放弃CPU，因而是高效的。

?下列进程互斥方法哪些存在忙式等待问题?

（1）软件: 面包店算法(2) 硬件: TS指令(3) 关中断指令

答：（1）、（2）存在忙等待问题。

?为何开关中断进程互斥方法仅在单CPU系统中是有效的？

答：关中断方法不适用于多CPU系统，因为关中断只能保证CPU不由一个进程切换到另外一个进程，从而防止多个进程并发地进入公共临界区域。但即使关中断后，不同进程仍可以在不同CPU上并行执行关于同一组共享变量的临界区代码.

?在多处理机系统中，软件互斥方法是否有效？为什么？

答：依然有效。多处理机并行与单处理并发之间的差别在于程序交叉的粒度，单处理机机环境中进程交叉发生在指令之间，多处理机环境中进程交叉发生在指令周期之间。由于纯软件互斥算法并不依赖特殊的硬件指令(如test_and_set)，指令之间的交叉与指令周期之间的交叉结果相同。

?试分析临界区域的大小与系统并发性之间的关系。

答：关于同一组变量的临界区域是不能并发执行的代码，临界区越大，并发性越差，因而编写并发程序应尽量缩小临界区域范围。

?设CR1是关于一组共享变量SV1的临界区域，CR2是关于另外一组共享变量SV2的临

界区域，当进程P1进入CR1时，进程P2是否可以进入CR2? 为什么?

答：可以。因为互斥是在变量级别上的，多个进程同时进入关于不同变量的临界区不会引起与时间有关的错误。

?Lamport面包店互斥算法是否会出现饿死情况?

不会，该算法是公平的。假定系统中共有n个进程，每个想要进入临界区域的进程(线程)在最坏的情况下需要等待其它n-1个进程进入并离开临界区域之后即可获得进入临界区域的机会，因而存在(忙式)等待的上界。

?试用信号灯和PV操作实现临界区语句:

region <共享变量> do <语句>

变量类型<共享变量>

答：

semaphore s=1;

P(s);

<语句>

V(s);

11. 由V操作唤醒的进程是否一定能够直接进入运行状态? 举例说明之。

答：否。一般来说，唤醒是将进程状态由等待状态变成就绪状态，而就绪进程何时获得处理机则是由系统的处理机调度策略确定的。如果采用抢占式优先级调度算法，并且被唤醒的进程是当前系统中优先级最高的进程，那么该进程将被调度执行，其状态变成运行态。如果该进程不是系统中优先级最高的进程或系统采用其它调度算法，那么该进程不会被调度执行，其状态将维持在就绪态。

12. 设S1和S2为两个信号灯变量，下列八组P、V操作哪些可以同时进行? 哪些不能同时进行? 为什么?

(1)P(S1)，P(S2)(2)P(S1)，V(S2)

(3)V(S1)，P(S2)(4)V(S1)，V(S2)

(5)P(S1)，P(S1)(6)P(S2)，V(S2)

(7)V(S1)，P(S1)(8)V(S2)，V(S2)

答：能同时进行的包括：(1)、(2)、(3)、(4)。这些操作涉及不同信号灯变量，属于关于不同组共享变量的临界区。不能同时进行的包括：(5)、(6)、(7)、(8)。这些操作涉及相同的信号灯变量，属于关于同一组共享变量的临界区。

13. 对于生产者—消费者问题，假设缓冲区是无界的，试用信号灯与PV操作给出解法。

答：由于是无界缓冲区，所以生产者不会因得不到缓冲区而被阻塞，不需要对空缓冲区进行管理，可以去掉在有界缓冲区中用来管理空缓冲区的信号量及其PV操作。

semaphore mutex_in=1;

semaphore mutex_out=1;

semaphore empty=0;

int in=0，out=0;

生产者活动：

while(1){

produce next product;

P(mutex_in);

add the product to buffer[in]; in++;

v(mutex_in);

V(empty);

} 消费者活动：

while(1){

P(empty);

P(mutex_out);

take the product from buffer[out]; out++;

V(mutex_out);

}

14. 设有一个可以装A、B两种物品的仓库，其容量无限大，但要求仓库中A、B两种物品的数量满足下述不等式:

-M≤A物品数量－B物品数量≤N

其中M和N为正整数。试用信号灯和PV操作描述A、B两种物品的入库过程。

答：已知条件 -M≤A物品数量－B物品数量≤N可以拆成两个不等式，即

A物品数量－B物品数量≤N，

B物品数量－A物品数量≤M。

这两个不等式的含义是：仓库中A物品可以比B物品多，但不能超过N个；Ｂ物品可以比A 物品多，但不能超过M个。

semaphore a=n;

semaphore b=m;

void main(){

createprocess(A,…);

createprocess(B,…);

}

A物品入库：void A(){ while(1){ P(a);

A物品入库; V(b);

}

} B物品入库：void B(){ while(1){ P(b);

B物品入库; V(a);

}

}

15. 试用信号灯与PV操作实现司机与售票员之间的同步问题。设公共汽车上有一个司机和一个售票员，其活动如下图

所示。

为了安全起见，显然要求: (1)关车门后方能启动车辆；(2)到站停车后方能开车门。亦即“启动车辆”这一活动应当在“关车门”这一活动之后，“开车门”这一活动应当在“到站停车”这一活动之后。

解：如果进程P2尚未推进到②处时，进程P1已经推进到①处，则P1应等待直到P2推进到②处为止；同样，如果进程P1尚未推进到③处时，进程P2已经推进到④处，则P2应等待直到P1推进到③处为止。如果进程P1在①处发生了等待，则当进程P2执行到②处时应将P1唤醒；同样，如果进程P2在④处发生了等待，则当进程P2执行到③处时应将P1唤醒。用信号量和P、V操作解决这一问题，需要定义两个信号量，一个信号量start表示是否允许司机启动车辆，另一个信号量open表示是否允许售票员开车门。初始状态是车停在始发站，车门开着，等待乘客上车。因此，两个信号量的初值都是0。

semaphore start=0;

semaphore open=0;

司机的活动: P1: do{

P(start); 启动车辆; 正常行车; 到站停车;

V(open); 售票员的活动: P2: do{

关车门;

V(start);

售票;

P(open);

开车门;

}while (1); }while (1);

16. 设有A、B、C三组进程，它们互斥地使用某一独占型资源R，使用前申请，使用后释放。资源分配原则如下:

(1) 当只有一组申请进程时，该组申请进程依次获得R；

(2) 当有两组申请进程时，各组申请进程交替获得R，组内申请进程依次获得R；

(3) 当有三组申请进程时，各组申请进程轮流获得R，组内申请进程依次获得R。

试用信号灯和PV操作分别给出各组进程的申请活动程序段和释放活动程序段。

解：

int free=1;//设备状态标志

semaphore mutex=1;

semaphore qa=qb=qc=0; //各组等待队列

int counta=countb=countc=0;//等待队列长度

A组申请：

P(mutex);

if(free==1){ free=0;

V(mutex);

}

else{

counta++;

V(mutex);

P(qa); A组释放：

P(mutex);

if(countb>0){ countb--;

V(qb);

}else{

if(countc>0){ countc--;

V(qc);

}else{

} if(counta>0){

counta--

V(qa);

}else{

free=1;

}

}

}

}

A组进程活动可以给出B组和C组进程活动。

17. 设自行车生产线上有一只箱子，其中有N个位置(N≥3)，每个位置可存放一个车架或一个车轮; 又设有三个工人，其活动分别为:

工人1活动：

do {

加工一个车架; 车架放入箱中; }while(1) 工人2活动：

do {

加工一个车轮;

车轮放入箱中;

}while(1)

工人3活动：

do {

箱中取一车架;

箱中取二车轮;

组装为一台车;

}while(1)

试分别用信号灯与PV操作、管程、会合实现三个工人的合作，要求解中不含死锁。

解：用信号灯与PV操作实现三个工人的合作，管程与会合解法可仿照给出。

首先不考虑死锁问题，工人1与工人3、工人2与工人3构成生产者与消费者关系，这两对生产/消费关系通过共同的缓冲区相联系。从资源的角度来看，箱子中的空位置相当于工人1和工人2的资源，而车架和车轮相当于工人3的资源。定义三个信号灯如下：

semaphore empty=N;//空位置

semaphore wheel=0;//车轮semaphore frame=0;//车架三位工人的活动分别为：

工人1活动：

do {

加工一个车架; P(empty);

车架放入箱中; V(frame);

}while(1) 工人2活动：

do {

加工一个车轮;

P(empty);

车轮放入箱中;

V(wheel);

}while(1)

工人3活动：

do {

P(frame);

箱中取一车架;

V(empty);

P(wheel);

P(wheel);

箱中取二车轮;

V(empty);

V(empty);

组装为一台车;

}while(1)

分析上述解法易见，当工人1推进速度较快时，箱中空位置可能完全被车架占满或只留有一个存放车轮的位置，而当此时工人3同时取2个车轮时将无法得到，而工人2又无法将新加工的车轮放入箱中；当工人2推进速度较快时，箱中空位置可能完全被车轮占满，而当此时工人3取车架时将无法得到，而工人1又无法将新加工的车架放入箱中。上述两种情况都意味着死锁。

为防止死锁的发生，箱中车架的数量不可超过N-2，车轮的数量不可超过N-1，这些限制可以用两个信号灯来表达。

semaphore s1=N-2;

semaphore s2=N-1;

如此，可以给出不含死锁的完整解法如下：

工人1活动：

do {

加工一个车架; P(s1);

P(empty);

车架放入箱中; V(frame);

}while(1) 工人2活动：

do {

加工一个车轮;

P(s2);

P(empty);

车轮放入箱中;

V(wheel);

}while(1)

工人3活动：

do {

P(frame);

箱中取一车架;

V(empty);

V(s1);

P(wheel);

P(wheel);

箱中取二车轮;

V(empty);

V(empty);

V(s2);

V(s2);

组装为一台车;

}while(1)

详细描述还应考虑对箱子单元的描述以及访问互斥问题。建议车架放在箱子的一端，车轮放在箱子的另一端，车架与车轮都采用后进先出的管理方式。

18. 一座小桥(最多只能承重两个人)横跨南北两岸，任意时刻同一方向只允许一人过桥，南侧桥段和北侧桥段较窄只能通过一人，桥中央一处宽敞，允许两个人通过或歇息。试用信号灯和PV操作写出南、北两岸过桥的同步算法。

解：桥上可能没有人，也可能有一人，也可能有两人。

(a) 两人同时过桥(b) 两人都到中间(c) 南(北)来者到北(南)段

共需要三个信号量，load用来控制桥上人数，初值为2，表示桥上最多有2人；north用来控制北段桥的使用，初值为1，用于对北段桥互斥；south用来控制南段桥的使用，初值为1，用于对南段桥互斥。

semaphore load=2; semaphore north=1; semaphore south=1;

tosouth(){ P(load);

P(north); 过北段桥; 到桥中间; V(north); P(south); 过南段桥; 到达南岸

V(south); V(load); } tonorth(){ P(load);

P(south); 过南段桥; 到桥中间

V(south); P(north); 过北段桥; 到达北岸

V(north); V(load); }

19.某寺庙，有小和尚、老和尚若干．庙内有一水缸，由小和尚提水入缸，供老和尚饮用。水缸可容纳 30 桶水，每次入水、取水仅为1桶，不可同时进行。水取自同一井中，水井径窄，每次只能容纳一个水桶取水。设水桶个数为5个，试用信号灯和PV操作给出老和尚和小和尚的活动。

semaphore empty=30;// 表示缸中目前还能装多少桶水，初始时能装30桶水

semaphore full=0;// 表示缸中有多少桶水，初始时缸中没有水

semaphore buckets=5;// 表示有多少只空桶可用，初始时有5只桶可用

semaphore mutex_well=1;// 用于实现对井的互斥操作

semaphore mutex_bigjar=1; // 用于实现对缸的互斥操作

young_monk(){

while(1){

P(empty);

P(buckets);

go to the well;

P(mutex_well);

get water;

V(mutex_well);

go to the temple;

P(mutex_bigjar);

pure the water into the big jar; V(mutex_bigjar);

V(buckets);

V(full);

}

} old_monk(){ while(){

P(full);

P(buckets);

P(mutex_bigjar); get water;

V(mutex_bigjar); drink water;

V(buckets);

V(empty);

}

}

20. 设系统中有5台类型相同的打印机，依次编号为1～5。又设系统中有n个使用打印机的进程，使用前申请，使用后释放。每个进程有一个进程标识，用于区别不同的进程。每个进程还有一个优先数，不同进程的优先数各异。当有多个进程同时申请时，按照进程优先数由高到低的次序实施分配。试用信号灯和PV操作实现对于打印机资源的管理，即要求编写如下函数和过程:

(1) 函数 require(pid，pri): 申请一台打印机。参数pid为进程标识，其值为1到n的整数; pri为进程优先数，其值为正整数; 函数返回值为所申请到打印机的编号，其值为1到5的整数;

(2) 过程 return(prnt): 释放一台打印机。参数prnt为所释放打印机的编号，其值为1到5的整数。

解：

#define N 5

bool flag[N+1];//flag[0]表示可用打印机数,

//flag[i]表示第i号打印机的状态（1<=i<=N），0表示占用，1表示空闲

PCB *queue=NULL;//进程阻塞队列

semaphore mutex_flag=1;//用于对flag数组的互斥操作

semaphore mutex_queue=1;//用于对阻塞队列的互斥操作

process(int i,int priority){

int print;

print=require(i,priority);

use print;

return(print);

}

int require(int pid,int priority){

P(mutex_flag);

if(flag[0]>0){

flag[0]--;

for(int i=1;i

if(flag[i]==1){

flag[i]=0;

break;

}

V(mutex_flag);

return i;

}

else{

V(mutex_flag);

p(mutex_queue);

将进程pid按其优先数插入到等待队列queue中；V(mutex_queue);

}

}

return(int print){

P(mutex_flag);

if(queue==NULL){

flag[0]++;

flag[print]=1;

V(mutex_flag);

}

else{

V(mutex_flag);

p(mutex_queue);

将print分配给queue队首进程；

queue下移；

V(mutex_queue);

}

}

21. 试用管程实现单一资源的管理。解：

TYPE single_resource=MONITOR; Var state: (free,used);//资源状态q: condition;//等待队列

define require, release; PROCEDURE require;

BEGIN

IF state=used THEN

wait(q);

state:=used;

END;

PROCEDURE release;

BEGIN

state:=free;

signal(q);

END;

BEGIN state:=free END;

22. 虽然管程是互斥进入的，但管程中定义的外部子程序必须是可再入的，试说明原因。

答：管程互斥是在变量级别的，同一管程类型可以有多个实例，而管程内部子程序只在管程类型定义时生成一套代码，为保障对不同管程变量的操作具有相同语义，管程外部子程序必须是可再入的。

23. 编写一个管程，使得调用进程能够等待若干指定时间单位(ticks)．可以假定有一个硬件实时钟，每隔一个tick时间单位调用该管程一次。

解：两个外部过程：sleep用于进程等待指定时间，tick用于时钟中断记数和唤醒等待进程。TYPE sleep_interval=MONITOR;

Var count: integer;//tick计数

q: condition;//等待队列

define sleep, tick;

PROCEDURE sleep(interval:integer);

BEGIN

count:=interval

wait(q);

END;

PROCEDURE tick;

BEGIN

count:=count-1;

IF count=0 THEN

signal(q);

END;

BEGIN END;

24. 管程与会合这两种同步机制之间的主要差别何在?

答：管程与会合都属于集中式结构化同步机制，但二者的实现机理完全不同。管程是被动性语言成分，管程本身不能占有处理机，管程外部子程序是由调用进程占有处理机执行的。会合是主动性语言成分，一个任务调用另一任务中的入口时，入口代码是由被调用任务自己占有处理机执行的。

25. 试用会合给出读写问题的解法，要求写者优先．

解：定义一个任务，包含如下四个入口：start_read,finish_read, start_write,finish_write。该问题的关键是：strat_write的入口条件不应考虑当前读者情况，当会合发生后再判断当前是否有读者，并与其finish_read会合。这里显然需要accept 语句的嵌套。

task readers_and_writers is

start_read;

finish_read;

start_write;

finish_write;

end readers_and_writers;

task body readers_and_writers is

read_count,write_count:integer;

read_count:=0;

write_count:=0;

loop

select

when write_count=0 =>

accept start_read do

read_count:=read_count+1;

end start_read

or when read_count>0 =>

accept finish_read do

read_count:=read_count-1;

end finish_read;

or when write_count=0 =>//也许当前有读者accept start_write do

while read_count>0 do//等待读者读完

accept finish_read do

read_count:=read_count-1

end finish_read

end while

write_count:=write_count+1;

end start_write

or when write_count>0 =>

accept finish_write do

write_count:=write_count-1;

end finish_write

end select;

end loop;

end readers_and_writers;

26. 关于读者/写者问题,有人给出如下改进解法: semaphore r_w_w, mutex, s; (初值均为1)

int count; (初值为0)

读者活动：

P(s);

P(mutex); count++;

if (count= =1) P(r_w_w);

V(mutex);

V(s);

{读操作}

P(mutex); count--;

If (count= =0) V(r_w_w);

V(mutex); 写者活动：P(s);

P(r_w_w); {写操作} V(r_w_w); V(s);

分析上述改进算法的调度效果。

答：由于s以及读者和写者对s的操作，读者和写者都不会无限等待，因而算法不会出现饿死现象，是一个公平的解法

进程间的同步和互斥-

实验报告 1、实验名称 进程间的互斥和同步 2、小组成员：姓名+学号 3、实验目的 Linux命名信号量实现进程间的互斥和同步 4、实验背景知识 进程同步也是进程之间直接的制约关系，是为完成某种任务而建立的两个或多个线程，这个线程需要在某些位置上协调他们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系来源于他们之间的合作。比如说进程A需要从缓冲区读取进程B产生的信息，当缓冲区为空时，进程B因为读取不到信息而被阻塞。而当进程A产生信息放入缓冲区时，进程B才会被唤醒。 进程互斥是进程之间的间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待。只有当使用临界资源的进程退出临界区后，这个进程才会解除阻塞状态。比如进程B需要访问打印机，但此时进程A占有了打印机，进程B会被阻塞，直到进程A释放了打印机资源,进程B才可以继续执行。 5、实验步骤演示 大概步骤： 先进行单次同步，把信号量先初始化为0，创建一个命名信号量，设置信号捕捉处理代码，安装捕捉信号；其次使用信号量进行同步和互斥的操作。 详细步骤： 1.创建一个命名信号量，sem = sem_open(SEM_NAME, OPEN_FLAG, OPEN_MODE, INIT_V); 2.创建子进程，pid = fork(); 3.V操作，sem_post(sem); 4.P操作，sem_wait(sem); 5.等待子进程结束，wait(&status); 6.删掉在系统创建的信号量，sem_unlink(SEM_NAME); 7.彻底销毁打开的信号量，sem_close(sem);

8.信号捕捉处理，static void myhandler(void); 9.迭代同步,两个信号量，开始时一个为1，一个为0，一个进程执行完换另一个执行； 10.安装捕捉信号，signal(SIGINT,(void *)myhandler ); 11.创建一个命名信号量：sem1 = sem_open(SEM_NAME1, OPEN_FLAG, OPEN_MODE, 1);sem2 = sem_open(SEM_NAME2, OPEN_FLAG, OPEN_MODE, 0); 12.创建子进程，pid = fork(); 13.if(0 == pid) P操作：sem_wait(sem1); V操作：sem_post(sem2); 14.if(0 < pid) P操作：sem_wait(sem2); V操作：sem_post(sem1); 15.static void mysem(char *str) { int i = 0; //P操作 sem_wait(sem); while('\0' != str[i]) { printf("%c\n", str[i++]); sleep(1); } //V操作 sem_post(sem); } 进程排斥,在临界区设置PV操作 16.创建一个命名信号量，sem = sem_open(SEM_NAME, OPEN_FLAG, OPEN_MODE, INIT_V); 17.if(0 == pid) { mysem("abcd"); } 18.if(0 < pid) { mysem("1234"); //等待子进程结束 wait(&status); //删掉在系统创建的信号量 sem_unlink(SEM_NAME); //彻底销毁打开的信号量 sem_close(sem); } 说明： 命名信号量不带内存共享,编译时要带库文件-lpthread或-lrt

实验四 同步与互斥 Linux实验报告

实验四同步与互斥 【实验目的和要求】 1、掌握进程（线程）的同步与互斥。 2、掌握生产者消费者问题的实现方法。 3、掌握多线程编程方法。 【实验内容】 实现生产者消费者问题 1、有一个仓库，生产者负责生产产品，并放入仓库，消费者会从仓库中拿走产品(消费)。 2、仓库中每次只能入一个(生产者或消费者)。 3、仓库中可存放产品的数量最多10个,当仓库放满时，生产者不能再放入产品。 4、当仓库空时，消费者不能从中取出产品。 5、生产、消费速度不同。 【实验原理】 1、信号量mutex提供对缓冲池访问的互斥要求并初始化为1，信号量empty和 full分别用来表示空缓冲项和满缓冲项的个数，信号量empty初始化为n，信号量full初始化为0。 2、定义如下结构及数据： 定义缓冲区内的数据类型：typedef int buffer_item; 缓冲区：buffer_item buffer[BUFFER_SIZE];

对缓冲区操作的变量：int in,out; 信号量mutex提供了对缓冲池访问的互斥要求：pthread_mutex_t mutex; 信号量empty和full分别表示空缓冲顶和满缓冲顶的个数：sem_t empty,full; 可以设定生产者的生产速度及消费者的消费速度：int pro_speed,con_speed; 对缓冲区操作的自增函数：#define inc(k) if(k < BUFFER_SIZE) k = k+1;else k=0 3、并定义了如下实现问题的函数模块： 将生产的产品放入缓冲区： int insert_item(buffer_item item) 从缓冲区内移走一个产品： int remove_item(buffer_item *item) 生产者进程：void *producer(void *param) 消费者进程：void *consumer(void *param) 生产者结构进程消费者结构进程 【程序代码】 //sx.c #include

Windows下进程同步与互斥

实验进程同步与互斥 一、实验目的 1．掌握基本的同步与互斥算法，理解生产者消费者模型。 2．学习使用Windows 2000/XP中基本的同步对象，掌握相关API的使用方法。 3．了解Windows 2000/XP中多线程的并发执行机制，实现进程的同步与互斥。 二、实验内容及要求 1．实验内容 以生产者/消费者模型为依据，在Windows 2000环境下创建一个控制台进程，在该进程中创建n个线程模拟生产者和消费者，实现进程(线程)的同步与互斥。 2．实验要求 ●学习并理解生产者/消费者模型及其同步/互斥规则； ●学习了解Windows同步对象及其特性； ●熟悉实验环境，掌握相关API的使用方法； ●设计程序，实现生产者/消费者进程(线程)的同步与互斥； ●提交实验报告。 三、相关知识介绍 1．同步对象 同步对象是指Windows中用于实现同步与互斥的实体，包括信号量(Semaphore)、互斥量(Mutex)、临界区(Critical Section)和事件(Events)等。本实验中使用到信号量、互斥量和临界区三个同步对象。 同步对象的使用步骤： ●创建/初始化同步对象。 ●请求同步对象，进入临界区(互斥量上锁)。 ●释放同步对象(互斥量解锁)。 这些对象在一个线程中创建，在其他线程中都可以使用，实现同步与互斥。 2．相关API的功能及使用 我们利用Windows SDK提供的API编程实现实验题目要求，而VC中包含有Windows SDK的所有工具和定义。要使用这些API，需要包含堆这些函数进行说明的SDK头文件——最常见的是Windows.h(特殊的API调用还需要包含其他头文件)。 下面给出的是本实验使用到的API的功能和使用方法简单介绍。 (1) CreateThread ●功能——创建一个在调用进程的地址空间中执行的线程 ●格式 HANDLE CreateThread( LPSECURITY_ATTRIBUTES lpThreadAttributes, DWORD dwStackSize, LPTHREAD_START_ROUTINE lpStartAddress,

操作系统实验-进程同步与互斥

实验四：进程的管道通信 实验题目 进程的管道通信 实验目的 加深对进程概念的理解，明确进程和程序的区别。学习进程创建的过程，进一步认识进程并发执行的实质。分析进程争用资源的现象，学习解决进程互斥的方法。学习解决进程同步的方法。掌握Linux系统中进程间通过管道通信的具体实现 实验内容 使用系统调用pipe()建立一条管道，系统调用fork()分别创建两个子进程，它们分别向管道写一句话，如： Child process1 is sending a message! Child process2 is sending a message! 父进程分别从管道读出来自两个子进程的信息，显示在屏幕上。 当然，仅仅通过屏幕上输出这两句话还不能说明实现了进程的管道通信，为了能够更好的证明和显示出进程的同步互斥和通信，在其中要加入必要的跟踪条件，如一定的输出语句等，来反映程序的并发执行情况 实验要求 这是一个设计型实验，要求自行、独立编制程序。两个子进程要并发执行。实现管道的互斥使用。当一个子进程正在对管道进行写操

作时，另一个欲写入管道的子进程必须等待。使用系统调用lockf(fd[1],1,0)实现对管道的加锁操作，用lockf(fd[1],0,0)解除对管道的锁定。实现父子进程的同步，当父进程试图从一空管道中读取数据时，便进入等待状态，直到子进程将数据写入管道返回后，才将其唤醒。 为了清楚的反应进程的同步，在子进程完成相应的操作后，调用sleep()函数睡眠一段时间（程序中定为3s）。父进程先执行wait()函数，当有子进程执行完毕后，会得到子进程的返回结果并清理子进程。若子进程没执行完，父进程一直执行wait()进行监听，知道有一个子进程执行完成为僵尸进程。 程序中用到的系统调用 因为程序时在linux系统上进行编写的，所以其中要利用到相关的linux提供的系统调用。 所用到的系统调用包含在如下头文件中。 #include #include #include #include #include #include fork() 用于创一个子进程。 格式：int fork();

同步与互斥

习题解答: ?何谓与时间有关的错误? 举例说明之。 答：并发进程的执行实际上是进程活动的某种交叉，某些交叉次序可能得到错误结果。由于具体交叉的形成与进程的推进速度有关，而速度是时间的函数，因而将这种错误称为与时间有关的错误。 例如，两个并发进程的程序如下： int n=0; main( ){ 创建进程A； 创建进程B； }； A( ){ while(1){ n++; } }; B( ){ while(1){ 睡眠一段时间；printf(“%d”,n); n=0; } }; 假设进程A被部署在公园入口的终端上，用来记录一段时间内进入公园的人数，进程B被部署在公园的控制中心，用来输出一段时间内进入公园的总人数。进程A和进程B共享全局变量n，n表示记录下的人数。如果在进程B执行完打印语句后被进程A打断，进程A执行了若干次变量自增语句，之后进程B接着执行清0语句，那么进程A对n的累加丢失了，相当于进程B被打断的这段时间内进入公园的人没有被记录下来。发生与时间有关的错误。 ?有人说，假设两个进程之间没有共享内存，则二者之间没有公共变量，这种说法准确吗? 说明原因。 答：如果只从用户空间考虑，这种说法是正确的。但从操作系统的角度来说并不准确。两个没有公共内存的用户进程可能同时（宏观）进入操作系统，并访问操作系统空间中的公共变

量。 ?何谓忙式等待? 是否还有其它方式的等待? 比较它们之间的联系和差别。 答：不进入等待状态的等待称为忙式等待。另一种等待方式是阻塞式等待，进程得不到共享资源时将进入阻塞状态，让出CPU给其他进程使用。忙等待和阻塞式等待的相同之处在于进程都不具备继续向前推进的条件，不同之处在于处于忙等待的进程不主动放弃CPU，尽管CPU 可能被剥夺，因而是低效的；而处于阻塞状态的进程主动放弃CPU，因而是高效的。 ?下列进程互斥方法哪些存在忙式等待问题? （1）软件: 面包店算法(2) 硬件: TS指令(3) 关中断指令 答：（1）、（2）存在忙等待问题。 ?为何开关中断进程互斥方法仅在单CPU系统中是有效的？ 答：关中断方法不适用于多CPU系统，因为关中断只能保证CPU不由一个进程切换到另外一个进程，从而防止多个进程并发地进入公共临界区域。但即使关中断后，不同进程仍可以在不同CPU上并行执行关于同一组共享变量的临界区代码. ?在多处理机系统中，软件互斥方法是否有效？为什么？ 答：依然有效。多处理机并行与单处理并发之间的差别在于程序交叉的粒度，单处理机机环境中进程交叉发生在指令之间，多处理机环境中进程交叉发生在指令周期之间。由于纯软件互斥算法并不依赖特殊的硬件指令(如test_and_set)，指令之间的交叉与指令周期之间的交叉结果相同。 ?试分析临界区域的大小与系统并发性之间的关系。 答：关于同一组变量的临界区域是不能并发执行的代码，临界区越大，并发性越差，因而编写并发程序应尽量缩小临界区域范围。 ?设CR1是关于一组共享变量SV1的临界区域，CR2是关于另外一组共享变量SV2的临

进程同步与互斥汇总

进程同步与互斥

进程的PV操作 在操作系统中，P、V操作是进程管理中的难点。这是1968年荷兰人Dijkstra 给出的一种解决并发进程间互斥和同步关系的通用方法。 1. P、V操作的意义 定义了信号量及其上的P操作和V操作，来实现并发进程间的同步和互斥，甚至可以用来管理资源的分配。P、V操作因交换的信息量少，属于进程的低级通信。 2. 什么是信号量？ 信号量（semaphore）是由一个值和一个指针构成的数据结构。值为整型变

量，表示信息量的值；指针指向进程控制块（PCB）队列的队头，表示等待该信号量的下一个进程。如下图所示。 信号量的一般结构及PCB队列 信号量的值与相应资源的使用情况有关。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。注意，信号量的初值不能为负，且其值只能由P、V操作来改变。 3. P、V操作的含义 P、V操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量S进行操作，具体定义如下： P（S）： ①将信号量S的值减1，即S=S-1； ②如果S≥0，则该进程继续执行；否则该进程状态置为阻塞状态，进程PCB 排入信号量PCB队列末尾，放弃CPU，等待V操作的执行。 V（S）： ①将信号量S的值加1，即S=S+1； ②如果S≤0，释放信号量队列中第一个PCB所对应的进程，将进程状态由阻塞态改为就绪态。执行V操作的进程继续执行。 一般来说，信号量S≥0时，S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S的值减1；当S<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个V操作意味着释放一个单位资源，因此S的值加1；若S≤0，表示有某些进程正在等待该资源，因此要唤醒一个阻塞状态的进程，使之成为就绪状态。 4. 利用信号量和P、V操作实现进程互斥 一般地，n个进程利用信号量和P、V操作实现进程互斥的一般模型如下： 进程P 1进程P 2 ……进程Pn …… …… …… P（S）； P（S）； P（S）； 临界区；临界区；临界区； V（S）； V（S）； V（S）； …… …… …… …… 其中S是互斥信号量，初值为1。 使用P、V操作实现进程互斥时应该注意的问题是： （1）每个程序中，用户实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查P、V操作的成对性。 （2）P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。 （3）互斥信号量的初值一般为1。 由于用于互斥的信号量sem与所有的并发进程有关，所以称之为公有信号量。公有信号量的值反映了公有资源的数量。只要把临界区置于P(sem)和V(sem)

同步和互斥的区别_

同步和互斥的区别

信号量互斥量条件变量 同步和互斥 一、信号量：用于进程间通信（linux中用于线程） 独立于进程在两个进程中都要初始化，若一个已创建，则另一个获取可以执行多次v操作，然后再执行p操作 信号量的一些概念： 以下是信号灯（量)的一些概念: 信号灯与互斥锁和条件变量的主要不同在于”灯”的概念，灯亮则意味着资源可用，灯灭则意味着不可用。如果说后两中同步方式侧重于”等待”操作，即资源不可用的话，信号灯机制则侧重于点灯，即告知资源可用；没有等待线程的解锁或激发条件都是没有意义的，而没有等待灯亮的线程的点灯操作则有效，且能保持灯亮状态。当然，这样的操作原语也意味着更多的开销。 信号灯的应用除了灯亮/灯灭这种二元灯以外，也可以采用大于1的灯数，以表示资源数大于1，这时可以称之为多元灯。 二、互斥量：（用于在线程间的通信） 1、在一个进程中创建 三、信号量与互斥量的区别 1. 互斥量用于线程的互斥，信号量用于线程的同步。 这是互斥量和信号量的根本区别，也就是互斥和同步之间的区别。

互斥：是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源 以上区别是主要想记住的。 note:信号量可以用来实现互斥量的功能 2. 互斥量值只能为0/1，信号量值可以为非负整数。 也就是说，一个互斥量只能用于一个资源的互斥访问，它不能实现多个资源的多线程互斥问题。信号量可以实现多个同类资源的多线程互斥和同步。当信号量为单值信号量是，也可以完成一个资源的互斥访问。3、互斥量的加锁和解锁必须由同一线程分别对应使用，信号量可以由一个线程释放，另一个线程得到。 4、作用域 信号量: 进程间或线程间(linux仅线程间) 互斥锁: 线程间 5、上锁时 信号量: 只要信号量的value大于0，其他线程就可以sem_wait(p操作-1)成功，成功后信号量的value减一。若value值不大于0，则

实验一 进程同步与互斥

实验一进程同步与互斥 一、实验目的 1．掌握基本的同步与互斥算法，理解生产者消费者模型。 2．学习使用Windows 2000/XP中基本的同步对象，掌握相关API的使用方法。 3．了解Windows 2000/XP中多线程的并发执行机制，实现进程的同步与互斥。 二、实验内容及要求 1．实验内容 以生产者/消费者模型为依据，在Windows 2000环境下创建一个控制台进程，在该进程 中创建n个线程模拟生产者和消费者，实现进程(线程)的同步与互斥。 2．实验要求 , 学习并理解生产者/消费者模型及其同步/互斥规则； , 学习了解Windows同步对象及其特性； , 熟悉实验环境，掌握相关API的使用方法； , 设计程序，实现生产者/消费者进程(线程)的同步与互斥； , 提交实验报告。 三、相关知识介绍 1．同步对象 同步对象是指Windows中用于实现同步与互斥的实体，包括信号量(Semaphore)、互斥量(Mutex)、临界区(Critical Section)和事件(Events)等。本实验中使用到信号量、互斥量和临

界区三个同步对象。 同步对象的使用步骤： , 创建/初始化同步对象。 , 请求同步对象，进入临界区(互斥量上锁)。 , 释放同步对象(互斥量解锁)。 这些对象在一个线程中创建，在其他线程中都可以使用，实现同步与互斥。 2．相关API的功能及使用 我们利用Windows SDK提供的API编程实现实验题目要求，而VC中包含有Windows SDK的所有工具和定义。要使用这些API，需要包含堆这些函数进行说明的SDK头文件——最常见的是Windows.h(特殊的API调用还需要包含其他头文件)。 下面给出的是本实验使用到的API的功能和使用方法简单介绍。 (1) CreateThread , 功能——创建一个在调用进程的地址空间中执行的线程 , 格式 HANDLE CreateThread( LPSECURITY_ATTRIBUTES lpThreadAttributes, DWORD dwStackSize, LPTHREAD_START_ROUTINE lpStartAddress, LPVOID lpParamiter, DWORD dwCreationFlags, Lpdword lpThread ); , 参数说明 lpThreadAttributes——指向一个LPSECURITY_ATTRIBUTES(新线程的安全性描述符)。

同步和互斥的区别

信号量互斥量条件变量 同步和互斥 一、信号量：用于进程间通信（linux中用于线程） 独立于进程在两个进程中都要初始化，若一个已创建，则另一个获取可以执行多次v操作，然后再执行p操作 信号量的一些概念： 以下是信号灯（量)的一些概念: 信号灯与互斥锁和条件变量的主要不同在于”灯”的概念，灯亮则意味着资源可用，灯灭则意味着不可用。如果说后两中同步方式侧重于”等待”操作，即资源不可用的话，信号灯机制则侧重于点灯，即告知资源可用；没有等待线程的解锁或激发条件都是没有意义的，而没有等待灯亮的线程的点灯操作则有效，且能保持灯亮状态。当然，这样的操作原语也意味着更多的开销。 信号灯的应用除了灯亮/灯灭这种二元灯以外，也可以采用大于1的灯数，以表示资源数大于1，这时可以称之为多元灯。 二、互斥量：（用于在线程间的通信） 1、在一个进程中创建 三、信号量与互斥量的区别 1. 互斥量用于线程的互斥，信号量用于线程的同步。 这是互斥量和信号量的根本区别，也就是互斥和同步之间的区别。

互斥：是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源 以上区别是主要想记住的。 note:信号量可以用来实现互斥量的功能 2. 互斥量值只能为0/1，信号量值可以为非负整数。 也就是说，一个互斥量只能用于一个资源的互斥访问，它不能实现多个资源的多线程互斥问题。信号量可以实现多个同类资源的多线程互斥和同步。当信号量为单值信号量是，也可以完成一个资源的互斥访问。3、互斥量的加锁和解锁必须由同一线程分别对应使用，信号量可以由一个线程释放，另一个线程得到。 4、作用域 信号量: 进程间或线程间(linux仅线程间) 互斥锁: 线程间 5、上锁时 信号量: 只要信号量的value大于0，其他线程就可以sem_wait(p操作-1)成功，成功后信号量的value减一。若value值不大于0，则sem_wait

同步和互斥的概念

2 同步概念 内核中的同步和进程之间的同步要相似之处，要介绍它首先需要了解竞争条件与临界区的概念（race condition & critical area）当两个以上的进程要读写同一个共享的数据，而且最后的执行结果依赖于进程执行的顺序的时候，我们说存在一种竞争条件。而进程中访问共享数据的那一部分代码就被称为临界区。我们可以通过保证两个进程不在同一时刻处于临界区内，从而抑制竞争条件的发生，实现这一目的的技术就是同步技术。在前面叙述竞争条件的时候，所举的例子都是进程，而更通用的说法应该是代码路径，每一个代码路径都在CPU 上独立运行，它们之间不存在明确的调用关系。在内核中，这样的代码路径称为内核控制路径。 同步 所谓同步，就是在发出一个功能调用时，在没有得到结果之前，该调用就不返回。也就是必须一件一件事做,等前一件做完了才能做下一件事.就像早上起床后,先洗涮,然后才能吃饭,不能在洗涮没有完成时,就开始吃饭.按照这个定义，其实绝大多数函数都是同步调用（例如sin,isdigit等）。但是一般而言，我们在说同步、异步的时候，特指那些需要其他部件协作或者需要一定时间完成的任务。最常见的例子就是SendMessage。该函数发送一个消息给某个窗口，在对方处理完消息之前，这个函数不返回。当对方处理完毕以后，该函数才把消息处理函数所返回的LRESULT值返回给调用者。 异步 异步的概念和同步相对。当一个异步过程调用发出后，调用者不能立刻得到结果。实际处理这个调用的部件在完成后，通过状态、通知和回调来通知调用者。以CAsycSocket类为例（注意，CSocket从CAsyncSocket派生，但是起功能已经由异步转化为同步），当一个客户端通过调用Connect函数发出一个连接请求后，调用者线程立刻可以朝下运行。当连接真正建立起来以后，socket底层会发送一个消息通知该对象。这里提到执行部件和调用者通过三种途径返回结果：状态、通知和回调。可以使用哪一种依赖于执行部件的实现，除非执行部件提供多种选择，否则不受调用者控制。如果执行部件用状态来通知，那么调用者就需要每隔一定时间检查一次，效率就很低（有些初学多线程编程的人，总喜欢用一个循环去检查某个变量的值，这其实是一种很严重的错误）。如果是使用通知的方式，效率则很高，因为执行部件几乎不需要做额外的操作。至于回调函数，其实和通知没太多区别。

操作系统-同步互斥

操作系统-同步互斥 并发执行，在我们串行执行的pc上的含义，是指两部分的程序代码，可能以任意的次序执行。如果它们对共享对象进行了修改，如果汇编指令的执行顺序不同，就可能产生不同的结果，这样就有问题，必须对程序的执行过程进行控制。这个本质也提供了一种我们分析一段程序是否需要人工控制的标准:考虑两个程序的汇编级的指令混合，结果会如何？ 进程之间的关系主要有两种，同步与互斥。所谓互斥，是指散步在不同进程之间的若干程序片断，当某个进程运行其中一个程序片段时，其它进程就不能运行它们之中的任一程序片段，只能等到该进程运行完这个程序片段后才可以运行。所谓同步，是指散步在不同进程之间的若干程序片断，它们的运行必须严格按照规定的某种先后次序来运行，这种先后次序依赖于要完成的特定的任务。也就是说同步是指两个进程为完成某项任务，必须进行协作，有前后次序的等待关系。 互斥：是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。当多个进程访问或操作同一个数据，且执行结果与访问的特定顺序有关，称为竞争条件。为了防止这种竞争，必须确保一段时间内只有一个进程能够操作这个数据。为了实现这种保证，就需要一定形式的进程间同步。实现互斥有这样一些方法，禁止中断，执行测试和设置操作，禁止调度，使用信号量。 同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。 同步机制有critical sections(关键区域、临界区域），mutex(互斥器），semaphore(信号量），event(事件）。 临界区:通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。 互斥量:为协调共同对一个共享资源的单独访问而设计的。 信号量:为控制一个具有有限数量用户资源而设计，允许多个线程同时使用共享资源，这与操作系统中的PV操作相同。 事件:用来通知线程有一些事件已发生，从而启动后继任务的开始。 临界区，进程中有一个代码段，在该段中，进程可能改变共同变量，当某一个进程进入临界区后，不允许其他进程再进入。因此临界区的执行在时间上互斥。 互斥器，跟临界区很相似，只有拥有互斥对象的线程才具有访问资源的权限，由于互斥对象只有一个，因此就决定了任何情况下此共享资源都不会同时被多个线程所访问。当前占据资源的线程在任务处理完后应将拥有的互斥对象交出，以便其他线程在获得后得以访问资源。互斥量比临界区复杂。因为使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享，而且可以在不同应用程序的线程之间实现对资源的安全共享。 信号量，允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目。在用CreateSemaphore（）创建信号量时即要同时指出允许的最大资源计数和当前可用资源计数。一般是将当前可用资源计数设置为最大资源计数，每增加一个线程对共享资源的访问，当前可用资源计数就会减1，只要当前可用资源计数是大于0的，就可以发出信号量信号。但是当前可用计数减小到0时则说明当前占用资源的线程数已经

操作系统同步互斥习题

信号量的PV操作是如何定义的？试说明信号量的PV操作的物理意义。 参考答案：P（S）：将信号量S减1，若结果大于或等于0，则该进程继续执行；若结果小于0，则该进程被阻塞，并将其插入到该信号量的等待队列中，然后转去调度另一进程。 V（S）：将信号量S加1，若结果大于0，则该进程继续执行；若结果小于或等于0，则从该信号量的等待队列中移出一个进程，使其从阻塞状态变为就绪状态，并插入到就绪队列中，然后返回当前进程继续执行。 PV操作的物理含义：信号量S值的大小表示某类资源的数量。当S>0时，其值表示当前可供分配的资源数目；当S<0时，其绝对值表示S信号量的等待队列中的进程数目。每执行一次P操作，S值减1，表示请求分配一个资源，若S≥0，表示可以为进程分配资源，即允许进程进入其临界区；若S<0，表示已没有资源可供分配，申请资源的进程被阻塞，并插入S的等待队列中，S的绝对值表示等待队列中进程的数目，此时CPU将重新进行调度。每执行一次V操作，S值加1，表示释放一个资源，若S>0，表示等待队列为空；若S≤0，则表示等待队列中有因申请不到相应资源而被阻塞的进程，于是唤醒其中一个进程，并将其插入就绪队列。无论以上哪种情况，执行V操作的进程都可继续运行。 1、设公共汽车上，司机和售票员的活动分别是： 司机的活动：启动车辆； 正常行车； 到站停车； 售票员的活动： 关车门； 售票； 开车门； 在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用P、V操作实现它们的同步。 设两个信号量S和C，初值为S＝0；C＝0； 司机：L1：正常行车售票员：L2：售票 到站停车P（S） V（S）开车门 P（C）关车门 启动开车V（C） GO TO L1 GO TO L2 2、请用PV操作实现他们之间的同步关系： （1）桌上一个盘子，只能放一只水果。爸爸放苹果，妈妈放桔子，儿子只吃桔子，女儿只吃苹果。 （2）桌上一个盘子，只能放一只水果。爸爸放苹果，妈妈放桔子，儿子吃桔子、苹果。 参考答案： 第一步：确定进程 4个进程Father（爸爸）、Mother（妈妈）、Son（儿子）、Daughter（女儿） Father进程： 将苹果放入盘中

同步互斥问题求解

1 图书馆阅览室问题 问题描述：假定阅览室最多可同时容纳100个人阅读，读者进入时，必须在阅览室门口的一个登记表上登记，内容包括姓名、座号等，离开时要撤掉登记内容。用P、V操作描述读者进程的同步算法。 (分析：读者有任意多个，但进入阅览室阅读最多为100人，为此可设一个信号量s，代表空座位的数目；另登记表为临界资源，需设一个用于互斥的信号量mutex,防止2个及以上的读者进程同时对此表访问。对于每个读者的动作包括进入、阅读、离开。) struct semaphore s,mutex=100,1; cobegin void readeri(void) (i=1,2,…,k) { while(TRUE){ P(s); P(mutex); 查登记表，置某座位为占用； V(mutex); …… reading; …… P(mutex); 查登记表，置某座位为空; V(mutex); V(s);} } coend 2吃水果问题 问题描述：桌上有一只盘子，每次只能放一个水果，爸爸专向盘中放苹果，妈妈专向盘中放桔子，儿子专等吃盘里的桔子，女儿专等吃盘里的苹果。只要盘子空，则爸爸或妈妈可向盘中放水果，仅当盘中有自己需要的水果时，儿子或女儿可从中取出，请给出四人之间的同步关系，并用PV操作实现四人正确活动的程序。 解：四人之间的关系：1爸爸，妈妈要互斥使用盘子，所以两者之间是互斥关系；2爸爸放的苹果，女儿吃，所以两者是同步关系；3妈妈放的桔子，儿子吃，所以两者也是同步关系。 struct semaphore s,sp,so=1,0,0; cobegin void father (void) { while(TRUE){ have an apple; P(s); put an apple; V(sp);}

互斥与同步的解决方法

互斥与同步的解决方法 =硬件方法 ---采用软件方法实现进程互斥使用临界资源是很困难的，他们通常能实现两个进程的互斥，很难控制多个进程的互斥。 ---算法设计需要非常小心，否则可能出现死锁，或互斥失败等严重问题。 ---软件方法始终不能解决忙等现象，降低系统效率， ---硬件发放包括屏蔽中断和专用机器指令。 +屏蔽中断 ---由于进程切换需要依赖中断来实现，如果屏蔽中断则不会出现进程切换。 ---因此，为了实现对临界资源的互斥使用，可以在进程进入临界区之前，屏蔽中断，当进程退出临界区时，打开系统中断。 ---中断被屏蔽以后，系统时钟中断也被屏蔽。处理机将不会被切换到其它进程。 ---于是，一旦屏蔽中断，进程就可以检查和修改共享内存区中的数据，而不必担心其他进程介入，其伪代码如下： Repeat ＜屏蔽中断＞； ＜临界区＞； ＜打开中断＞； ＜其余部分＞； Forever。 ---这种方法约束条件太强，付出的代价太大。 ---因为中断被屏蔽以后，系统将无法响应任何外部请求，也不会响应当前执行进程的任何异常及系统故障，严重的降低了处理机性能。 ---这种方法仅对单处理机系统有效，如果系统有两个或多个共享内存的处理机，屏蔽中断仅仅对执行本指令的处理机有效，其他处理机仍将继续运行，并可以访问共享内存空间。 =专用机器指令 ---利用一些专用机器指令也能实现互斥，机器指令在一个指令周期内执行，不会受到其他指令的干扰，也不会被中断。 ---Test and Set指令就是较长用的一种机器指令，其定义如下：·testset指令 Function testset(var i:integer):Boolean; Begin If i =0 then Begin i:=1; testset:=true; end

同步与互斥

2．3进程互斥与同步 1.进程互斥 （1）临界资源：临界资源是指每次仅允许一个进程访问的资源。 属于临界资源的硬件有打印机、磁带机等,软件有消息缓冲队列、变量、数组、缓冲区等。诸进程间应采取互斥方式，实现对这种资源的共享。 （2）每个进程中访问临界资源的那段代码称为临界区 （3）在操作系统中，当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一 进程才被允许去访问些临界资源。我们称进程之间的这种相互 制约关系为互斥。 （4）使用临界区的标准： 每次至多有一个进程处于临界区；进程在临界区停留有限时间； 2.互斥的实现方法 （1）利用锁机机制实现互斥 0资源可用，1资源已被占用 进入临界区之前动作（关锁操作） A考察锁位的值 B如果原来的值为0，将锁位置成1 C如果原来的值为1，则返回第一步再考察 当进程使用完资源后，应将锁位置成0，开锁操作

（2）P、V操作实现互斥 信号量（s,q）s是一个具有非负初值的整型变量，q是一个初始状态为空的队列，s表示系统中某类资源的数目，当其值大于0时，表示系统中可用资源的数目，当其值小于0时，其绝对值表示系统中因请求该类资源而被阴塞的进程数目。 P、V操作为两条原语 P操作P操作记为P（S），其中S为一信号量，它执行是主要完成下述动作： S=S-1 若S≥0,则进程继续运行 若S<0,则该进程被阴塞，并将它插入该信号量的等待队列中。 V操作V操作记为V（S）S为一信号量，它执行时主要完成下述动作： S=S+1 若S>0，则进程继续执行。 若S≤0，则从信号量等待队列中移出第一个进程，使其变为就绪状态，然后再返回原进程继续执行。 2.同步 所谓进程同步是指对多个相关进程在执行次序上的协调。这些进程相互合作，在一些关键点上可能需要互相等待或互通消息。

经典进程同步互斥问题集

【例1】有三个进程PA 、PB 和PC 协作解决文件打印问题：PA 将文件记录从磁盘读入内存的缓冲区1中，每执行一次读一个记录；PB 将缓冲区1中的内容复制到缓冲区2中，每执行一次复制一个记录；PC 将缓冲区2中的内容打印出来，每执行一次打印一个记录。缓冲区的大小与记录大小一样。请用信号量来保证文件的正确打印。 答：该文件打印过程的同步算法可描述如下： 【例2】进程A1、A2、…An1通过m 个缓冲区向进程B1、B2、…Bn2不断地发送消息。发送和接收工作遵循如下规则： （1）每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小与消息长度一样。 （2）对于每一个消息，B1、B2、…Bn2都需各接收一次，读入自己的数据区内。 （3）m 个缓冲区都满时，发送进程等待；没有可读的消息时，接收进程等待。 试用wait,signal 操作描述它们的同步关系。 分析：本题是生产者－消费者问题的一个变形。由于每个缓冲区都只写一次，但要读n2次，故我们可将每个缓冲区看成是由n2格组成的。只有当某个缓冲区的n2 格都空闲时，才允许写入，

而且写一次缓冲区相当于将该缓冲区的n2格全部写一遍。Bj 进程从缓冲中取消息时，它只取相应缓冲的第j 格。由于每个Bj 取消息的速度不同，故需为它们分别设置指针outj ，用来指示从哪个缓冲区的第j 格中取消息。 答：我们将每个缓冲区看成是由n2格组成的，可为本题设置下列信号量：mutex,初值为1，用来实现对缓冲区的互斥访问；empty[i](i=1,…,n2)，初值均为m ，每个empty[i]对应于缓冲池的第i 格中的所有空闲缓冲区；full[i](i=1,…,n2)，初值均为0，对应缓冲池第i 格中装有消息的缓冲区。另外还需要提供整型变量in 用来指示将消息放入哪个缓冲区，outj(j=1,…,n2)用来指示Bj 从哪个缓冲区中取消息，这些变量的初值均为0。Ai,Bj 的算法描述如下： 【例3】设有两个生产者进程A 、B 和一个销售进程C ，他们共享一个无限大的仓库，生产者每次循环生产一个产品，然后入库供销售者销售；销售者每次循环从仓库中取出一个产品进行销售。如果不允许同时入库，也不允许边入库边出库，而且要求生产A 产品和B 产品的件数满足以下关系： －n ≤A 的件数－B 的件数≤m 其中n 、m 是正整数，但对仓库中A 产品和B 产品的件数无上述要求，请用信号量机制写出A 、 B 、 C 三个进程的工作流程。 分析：本题中存在着以下的同步和互斥关系：（1）生产者A 、B 和消费者C 之间，不能同时将产品入库和出库，故仓库是一个临界资源。（2）两个生产者之间必须进行同步。当生产者的A 、B 产品的件数之差大于等于m 时，生产者A 必须等待；小于等于－n 时，生产者B 必须等待。这种关系可想象成有两种令牌，分别跟允许A 和B 生产的产品数量相关，A 和B 必须取得对应的令牌后才能生产产品，故这两类令牌也就是两种临界资源。（3）生产者和销售者之间也必有进行同步，只有当生产者生产出产品并入库后，销售者才能进行销售。 答：为了互斥地入库和出库，需为仓库设置一初值为1的互斥信号量mutex ；为了使生产的产品件数满足：－n ≤A 的件数－B 的件数≤m ，需设置两个信号量，其中SAB 表示当前允许A 生产

操作系统同步互斥练习题

操作系统同步试题 1、设公共汽车上，司机和售票员的活动分别是： 司机的活动：启动车辆； 正常行车； 到站停车； 售票员的活动： 关车门； 售票； 开车门； 在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用P、V操作实现它们的同步。 设两个信号量S和C，初值为S＝0；C＝0； 司机：L1：正常行车售票员：L2：售票 到站停车P（S） V（S）开车门 P（C）关车门 启动开车V（C） GO TO L1 GO TO L2 2、桌子上有一个空盘子，允许存放一只水果，爸爸可以向盘中放苹果，妈妈向盘子中放橘子，女儿专门吃盘子中的苹果，儿子专门吃盘子中的橘子。规定当盘子空的时候一次只能放一只水果，请用信号量实现他们之间的同步与互斥。 S, S1, S2 :semaphore=1,0,0; Cobegin: Process Father: Begin: L1: P(S); Put Apple; V(S1)； GO TO L1； End； Process Mother: Begin: L2: P(S); Put Orange; V(S2)； GO TO L2； End； Process Son: Begin: L3: P(S2); Get Orange;

V(S)； GO TO L1； End； Process Daughter: Begin: L4: P(S1); Get Apple; V(S)； GO TO L4； End； CoEnd; 2、写者优先的“读者――写者”问题： 1）共享读 2）互斥写、读写互斥 3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者） wmutex:semaphore=1 //读者与写者之间、写者与写者之间互斥使用共享数据S：semaphore=1 //当至少有一个写者准备访问共享数据时，它可使后续 的读者等待写完成 S2：semaphor＝1 //阻塞第二个以后的等待读者 readcount,writecount: semaphore = 0,0; //当前读者数量、写者数量 mutex1 :semaphore = 1 //多个读者互斥使用readcount mutex2 :semaphore = 1 //多个写者互斥使用writecount Cobegin: Reader: begin Repeat Wait（S2）； wait(S); wait(mutex1) if readcount=0 then wait(wmutex); readcount++; signal (mutex1); signal(S); signal（S2）； reading… wait(mutex1); readcount--; if readcount=0 then signal(wmutex); signal(mutex1); until false; begin; writer: begin repeat;

线程的同步和互斥问题

实验二线程的同步和互斥问题 一．实验内容： 编写程序实现并发线程之间的同步和互斥问题。 线程间的互斥：并发执行的线程共享某些类临界资源，对临界资源的访问应当采取互斥的机制。 线程间的同步：并发执行的线程间通常存在相互制约的关系，线程必须遵循一定的规则来执行，同步机制可以协调相互制约的关系。 二．实验目的和要求 1）了解进程同步与互斥的概念，掌握编写进程同步、互斥的实例。 2）解决一类典型的进程间同步问题，如生产者-消费者问题，读者-写者问题等。 三．实验方法和步骤 1．实验方法 掌握同步与互斥的机制，选取合适的问题，给出演示程序的设计思想，包括流程图的形式；选取C、C++、VC、JA V A等计算机语言，编程调试，最终给出运行正确的程序。 2．程序设计 （1）线程间互斥： 分析问题，创建多个线程，找出临界资源，划出正确的临界区，根据互斥机制的操作模式，编写程序。 互斥机制的操作模式： p(mutex);/*关锁*/ 临界区的操作； v(mutex);/*开锁*/ （2）线程间同步——读者-写者问题示例： 在Windows 2000 环境下，创建一个包含n 个线程的控制台进程。用这n 个线程来表示n个读者或写者。每个线程按相应测试数据文件的要求，进行读写操作。请用信号量机制分别实现读者优先和写者优先的读者-写者问题。 读者-写者问题的读写操作限制：

1）写-写互斥；2）读-写互斥；3）读-读允许； 运行结果显示要求：要求在每个线程创建、发出读写操作申请、开始读写操作和结束读写操作时分别显示一行提示信息，以确信所有处理都遵守相应的读写操作限制。 测试数据文件格式 测试数据文件包括n 行测试数据，分别描述创建的n 个线程是读者还是写者，以及读写操作的开始时间和持续时间。每行测试数据包括四个字段，各字段间用空格分隔。第一字段为一个正整数，表示线程序号。第二字段表示相应线程角色，R 表示读者是，W 表示写者。 第三字段为一个正数，表示读写操作的开始时间。线程创建后，延时相应时间（单位为秒）后发出对共享资源的读写申请。第四字段为一个正数，表示读写操作的持续时间。当线程读写申请成功后，开始对共享资源的读写操作，该操作持续相应时间后结束，并释放共享资源。 下面是一个测试数据文件的例子： 1 R 3 5 2 W 4 5 3 R 5 2 4 R 6 5 5 W 5.1 3 与实验相关的API 介绍 在本实验中可能涉及的API 有： 线程控制： CreateThread 完成线程创建，在调用进程的地址空间上创建一个线程，以执行指定的函 数；它的返回值为所创建线程的句柄。 HANDLE CreateThread（ LPSECURITY_ATTRIBUTES lpThreadAttributes, // SD DWORD dwStackSize, // initial stack size LPTHREAD_START_ROUTINE lpStartAddress, // thread function