海络网站,wordpress文章发布到专题,制作公司网页什么价位,wordpress怎么添加连接计算机操作系统——信号量机制与经典进程的同步问题
信号量机制 随着发展#xff0c;信号量从整型信号量经记录型信号量#xff0c;进而发展为“信号量集”机制。 一般来说#xff0c;信号量的值与相应的资源的使用情况有关。 信号量的值仅由P、V操作改变。 信号量的初值…计算机操作系统——信号量机制与经典进程的同步问题
信号量机制 随着发展信号量从整型信号量经记录型信号量进而发展为“信号量集”机制。 一般来说信号量的值与相应的资源的使用情况有关。 信号量的值仅由P、V操作改变。 信号量的初值大于等于0 S 0表示有S个可用资源 S 0表示无资源可用 S 0表示S等待队列中的进程个数
PV操作的优缺点
优点简单表达能力强用PV操作可解决任何同步互斥问题缺点不够安全使用不当会出现死锁遇到复杂同步互斥问题时实现复杂。
1.信号量机制——整型信号量
最初由Dijkstra把整型信号量定义为一个用于 表示资源数目的整型量S 它与一般整型量不同除初始化外仅能通过两个标准的原子操作Atomic Operationwait(S)和signal(S)来访问。很长时间以来这两个操作一直被分别称为P、V操作。
wait(S){while(S 0) ; /*do no-op*/S--;}
signal(S){S;}wait(S)和signal(S)是两个原子操作因此在执行时是不可中断的。当一个进程在修改某信号量时没有其他进程可同时对该信号量进行修改。在wait操作中对S值的测试和对S–操作时都不可断。
2.信号量机制——记录型信号量
整型信号量如果S一直小于等于0那就使处理机一直处于忙等状态。记录型信号量机制则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略之后又会出现多个进程等待访问同一临界资源的情况。
记录型信号量机制中除了需要一个用于代表资源数目的整型变量value外还应增加一个进程链表指针list用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。
typedef struct{int value;struct process_control_block *list;
}semaphore;wait(semaphore *S){S-value--;if(S-value0) block(S-list);
}signal(semaphore *S){S-value;if(S-value 0) wakeup(S-list);
}
3.信号量机制——AND型信号量
之前的进程互斥问题是针对各进程之间只共享一个临界资源而言的。在有些应用场合是一个进程需要先获得两个或更多的共享资源后才能执行其任务。假定现有两个进程A和B它们都要访问共享数据D和E。当然共享数据都应作为临界资源。为此可为这两个数据分别设置用于互斥的信号量Dmutex和Emutex并令它们的初值都是1。相应地在两个进程中都要包含两个对Dmutex和Emutex的操作。
process A:wait(Dmutex);wait(Emutex);process B:wait(Emutex);wait(Dmutex);若进程A和进程B按下述次序交替执行wait操作 process A : wait(Dmutex); 于是Dmutex0 process B : wait(Emutex); 于是Emutex0 process A : wait(Emutex); 于是Emutex-1 A阻塞 process B : wait(Dmutex); 于是Dmutex-1 B阻塞
A和B处于僵持进入死锁状态
AND同步机制的基本思想将进程在整个运行过程中需要的所有资源一次性全部地分配给进程待进程使用完后再一起释放。对若干个临界资源地分配采取原子操作方式要么把它所请求的资源全部分配到进程要么一个也不分配。
Swait(S1,S2, ... ,Sn){while(TRUE){if(Si1 ... Sn1){for(i1;in;i) Si--;break;}else{place the process in the waiting queue associated with the first Si found with Si1,and set the program count of this process to the beginning of Swait operation.}}
}Ssignal(S1,S2, ... ,Sn){while(TRUE){for(i1;in;i){Si;Remove all the process waiting in the queue associated with Si into the ready queue.}}
}经典进程的同步问题
一、生产者——消费者问题
解决互斥同步问题的主要步骤 分析清楚题目涉及的进程间制约关系。可能是一种也可能是两种设置信号量包括信号量的个数和初值写出信号量物理含义身临其境写算法并把PV操作加到程序适当之处 生产者消费者问题是一种同步问题的抽象描述。计算机系统中的每个进程都可以消费使用或生产释放某类资源。这里的资源可以是硬件资源也可以是软件资源。当某一进程使用某一资源时可以看作是消费称该进程是消费者。而当某一进程释放某一资源时它就相当于生产者。
生产者——消费者问题的分析
只要缓冲区未满生产者就可以把产品送入缓冲区。同步只要缓冲区为空消费者就可以从缓冲区中取走物品。同步缓冲池一次只能有一个进程访问。互斥
生产者——消费者问题信号量和变量的设置
由于有界缓冲池是一个临界资源必须互斥使用。另外还需要设置一个互斥信号量mutex其初值为1.应该设置两个同步信号量一个说明空缓冲区的数目用empty表示。初值为有界缓冲区的大小n另一个说明已满缓冲区的数目用full表示初值为0。变量缓冲池buffer[n-1]数组下标inout初值为0。
/*生产者*/
producer(){while(1){生产产品;P(empty); /*请求一个空闲缓冲区*/P(mutex);把产品放入缓冲池;in (m1) mod n;V(mutex);V(full); /*增加一个产品*/}
} /*消费者*/
consumer(){while(1){P(full); /*消耗一个产品*/ P(mutex);从缓冲区取出一个产品;V(mutex);V(empty); /*增加一个空闲缓冲区*/}
}生产者——消费者问题算法结论
PV操作必须成对出现。互斥的PV出现在同一进程。同步的PV出现在不同的进程。同步的P操作和互斥的P操作同时出现时先写同步P操作再写互斥P操作。 例题1桌子上有一个盘子最多允许存放一个水果。父亲只放苹果母亲只放橘子女儿只吃苹果儿子只吃橘子。用信号量PV写出父亲、母亲、女儿、儿子的同步算法。
信号量设置 empty(盘子空余空间)1apple(苹果)0orange(橘子)0
父亲father
father(){while(1){P(empty);放入苹果V(apple);}
}母亲mother
mother(){while(1){P(empty);放入橘子;V(orange)}
}女儿daughter
daughter(){while(){P(apple);吃苹果;V(empty);}
}儿子son
son(){while(1){P(orange);吃橘子;V(empty);}
}例题2桌子上有一个盘子最多允许存放两个水果。父亲只放苹果母亲只放橘子女儿只吃苹果儿子只吃橘子。用信号量PV写出父亲、母亲、女儿、儿子的同步算法。
增加互斥信号量mutex1
父亲father
father(){while(1){P(empty);P(mutex);放入苹果V(mutex);V(apple);}
}母亲mother
mother(){while(1){P(empty);P(mutex);放入橘子;V(mutex);V(orange)}
}女儿daughter
daughter(){while(){P(apple);吃苹果;V(empty);}
}儿子son
son(){while(1){P(orange);吃橘子;V(empty);}
}例题3某小型超市可容纳50人同时购物。入口处有篮子每个购物者从入口处拿一只篮子进入购物。出口处结账入口和出口是两个门并归还篮子出、入口禁止多人同时通过用信号量PV写出购物者的同步算法。
由题意可以看出该题中只有互斥操作。 信号量设置超市剩余空间empty50入口mutex11出口mutex21
购物者shopper
shopper(){while(1){P(empty); /*这里的P操作可以理解成请求申请一个空闲区域*/P(mutex1);从入口进入取一只篮子; /*入口只能一个人通过该动作执行的过程中不允许其他进程进入*/V(mutex1);购物;P(mutex2);从入口出去放下篮子;V(mutex2);V(empty); /*这里的V操作可以理解成归还释放一个空闲区域*/}
}例题4 信号量设置: 停车的信号量stop0开门的信号量door0
/*司机*/
driver(){while(1){P(door);启动车辆;正常行驶;到站停车;V(stop);}
}/*售票员*/
conductor(){while(1){关门; /*售票员先关门司机才能启动车辆*/V(door);售票;P(stop);开门;}
}二、哲学家进餐问题
有五个哲学家围坐在圆桌旁桌子中央放着火锅每人面前有一只空盘子每两人之间放一只筷子。每个哲学家的行为是思考感到饥饿然后吃火锅。为了吃火锅每个哲学家必须拿到两只筷子并且每个人只能直接从自己的左边或右边去取筷子。 设chopstick[5]为5 个信号量初值均为1
philosopheri:while(1){思考P(chopstick[i]);P(chopstick[(i1)%5]);吃火锅;V(chopstick[i]);V(chopstick[(i1)%5]);
}为防止死锁发生可采取得措施
最多允许4个哲学家同时去拿起左边得筷子。仅当一个哲学家左右两边得筷子都可用时才允许他拿筷子。给所有哲学家编号奇数号得哲学家必须首先拿起左边的筷子偶数号得哲学家则相反。
三、读者——写者问题
有两组并发进程读者和写者共享一组数据区要求1允许多个读者同时执行读操作2不允许读者、写者同时操作3不允许多个写者同时操作
读者——写者问题的问题分析
读者和写者、写者和写者之间即写者与其他进程之间互斥访问数据区。读者与读者可以同时访问设置一个整型信号量readcount表示正在读的进程数目该变量是可被多个读进程访问的临界资源。设wmutex用于读者和写者、写者和写者之间的互斥设rmutex用于对readcount这个临界资源的互斥访问。
wmutex用于读者和写者、写者和写者之间的互斥readcount表示正在读的读者数目rmutex用于对readcount这个临界资源的互斥访问设有两个信号量wmutex1,rmutex1另设一个全局变量readcount0
/*读者*/
while(1){P(rmutex);readcount;if(readcount1)P(wmutex);V(rmutex);读P(rmutex);readcount--;if(readcount0)V(wmutex);V()
}
