操作系统是大学里非常重要的课程,对于科班出身的同学来说,把这门课程学号是非常必要的,下面我将我的课堂笔记整理好跟大家分享,虽然这些例子都是很简单的,代码也都能在网上找到,但是我想经过自己整理的代码,才能把知识固定在脑子里,希望我的笔记对大家操作系统的学习有利,特别是非科班出身而且对计算机感兴趣的同学;
正文:
信号量的本质是一种数据操作锁,它本身不具有数据交换的功能,而是通过控制其他的通信资源(文件,外部设备)来实现进程间通信,它本身只是一种外部资源的标识。信号量在此过程中负责数据操作的互斥、同步等功能。
当请求一个使用信号量来表示的资源时,进程需要先读取信号量的值来判断资源是否可用。大于0,资源可以请求,等于0,无资源可用,进程会进入睡眠状态直至资源可用。
信号量结构体:
struct{ unsigned short semval;
pid_t sempid;
unsigned short semncent;
.....
};
信号量的两个操作:
<!--[if !supportLists]-->1、<!--[endif]-->阻塞操作——Wait
<!--[if !supportLists]-->2、<!--[endif]-->唤醒操作——Signal
信号量分类
<!--[if !supportLists]-->1、<!--[endif]-->技数信号量:
使用范围:资源数量有多个(共享资源有多个备份,他们的使用是互斥的);
取值范围:大于1的整数值,
<!--[if !supportLists]-->2、<!--[endif]-->二元信号量:
取值范围:0、1
使用范围:实现互斥;
Semaphore S;
Wait(S):
Critical Section;
Signal(S);
二元信号量其实就是一个锁;
Wait——获取锁的钥匙
Signal——钥匙扔掉
二元信号量比较简单,比较复杂的计数信号量可以用二元信号量来实现:
Data Structures:
Int c;//计数信号量的取值
Binary-Semaphore S1,S2;//对C的操作要求互斥,S1作为C的互斥锁;
//S2做为技术信号量的wait的等待;
Initialization:
S1 = 1
S2 = 0
C = intial value of semaphore S;
Wait(C) operation
Wait(S1)l;
C--;
If(C<0){
Signal(S1);//唤醒S1
Wait(S2);
}
Signal(S1);
Signal(C) operation
Wait(S1);
C++;
If(C<=0)
Signal(S2);
Else
Signal(S1);
同步问题的例子
解决同步问题思路步骤:
参与者与规则;
资源:具体问题所涉及的资源,而这些资源一般都是共享的,资源的数量也是有限的;
继续处理前必须获得资源——技术信号量或者变量计数;
共享变量
必须保护访问——二元信号量;
<!--[if !supportLists]-->1、<!--[endif]-->有限缓存问题(生产者消费者问题):
问题描述:两个共享固定大小缓冲区的线程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。生产者的主要作用是生成一定量的数据放到缓冲区中,然后重复此过程。与此同时,消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据,消费者也不会在缓冲区中空时消耗数据。
游戏参与者:生产者、消费者
活动限制:共享一个固定大小的缓冲区;
对共享数据的访问要求:互斥(生产消费操作必须互斥),缓存区满后停止生产,有产品后才消费;
怎样保证互斥:设置一个信号量,用信号量保证互斥;
缓存区满后停止生产:获得空的缓存去单元,用一个计数信号量表示空的单元数,empty;
有生产后才消费:有一个“满”的资源才能进行消费;
一个生产者,一个消费者,公用一个缓冲区
定义两个同步信号量:
empty——表示缓冲区是否为空,初值为1。
full——表示缓冲区中是否为满,初值为0。
生产者进程
while(TRUE){
生产一个产品;
P(empty);
产品送往Buffer;
V(full);
}
消费者进程
while(TRUE){
P(full);
从Buffer取出一个产品;
V(empty);
消费该产品;
一个生产者,一个消费者,公用n个环形缓冲区
——N个缓冲区形成一个环形缓冲区要利用指针。缓冲区的指向则通过模运算得到。
empty——表示缓冲区是否为空,初值为n。
full——表示缓冲区中是否为满,初值为0。
设缓冲区的编号为1~n-1,定义两个指针in和out,分别是生产者进程和消费者进程使用的指针,指向下一个可用的缓冲区。
生产者进程
while(TRUE){
生产一个产品;
P(empty);
产品送往buffer(in);
in=(in+1)mod n;
V(full);
}
消费者进程
while(TRUE){
P(full);
从buffer(out)中取出产品;
out=(out+1)mod n;
V(empty);
消费该产品;
}
一组生产者,一组消费者,公用n个环形缓冲区
——在这种情况中,生产者与消费者存在同步关系,而且各个生产者之间、各个消费者之间存在互斥关系,他们必须互斥地访问缓冲区。
定义四个信号量:
empty——表示缓冲区是否为空,初值为n。
full——表示缓冲区中是否为满,初值为0。
mutex1——生产者之间的互斥信号量,初值为1。
mutex2——消费者之间的互斥信号量,初值为1。
设缓冲区的编号为1~n-1,定义两个指针in和out,分别是生产者进程和消费者进程使用的指针,指向下一个可用的缓冲区。
生产者进程
while(TRUE){
生产一个产品;
P(empty);
P(mutex1);
产品送往buffer(in);
in=(in+1)mod n;
V(mutex1);
V(full);
}
消费者进程
while(TRUE){
P(full);
P(mutex2);
从buffer(out)中取出产品;
out=(out+1)mod n;
V(mutex2);
V(empty);
<!--[if !supportLists]-->2、<!--[endif]-->读者\写者问题:
问题描述:读者—写者问题(Readers-Writers problem)也是一个经典的并发程序设计问题,是经常出现的一种同步问题。计算机系统中的数据(文件、记录)常被多个进程共享,但其中某些进程可能只要求读数据(称为读者Reader);另一些进程则要求修改数据(称为写者Writer)。就共享数据而言,Reader和Writer是两组并发进程共享一组数据区,要求:
游戏参与者:读者、写者
活动限制:读写操作是在同一个临界区;
对共享数据的访问要求:(互斥)读和写不能同时进行,允许多个读者同时执行读操作,不允许读者、写者同时操作,不允许多个写者同时操作;
许多个读者同时执行读操作,第一个读者解锁;最后一个读者加锁,使用一个计数器readcount来计算读者的数量;
Shared data
Semaphore mutex 保证读者对readcount访问的互斥
Wrt: 保证读写互斥
Readcount:记录读者数量
<!--[if !supportLists]-->3、<!--[endif]-->哲学家问题
问题描述:在餐桌旁的哲学家有两种操作,思考,就餐,餐桌上每个哲学家的右边有一只筷子,两只筷子才能就餐;
游戏参与者:哲学家
共享资源:筷子(二元信号量);
对共享数据的访问要求:每个筷子的使用是互斥的,每个哲学家只能使用身边的筷子;
哲学家就餐防止死锁:
当一个哲学家身边的两个筷子都可以用才可以允许它拿筷子;
给所有哲学家编号,奇数号的哲学家首先拿左边的筷子;偶数号的哲学家先拿右边的筷子;
如果哲学家总数已知,可以让控制最多让总数-1的哲学家就餐;
<!--[if !supportLists]-->4、<!--[endif]-->理发师问题:
问题描述:
<!--[if !supportLists]-->1、<!--[endif]-->休息的理发师是坐地自己专用的理发椅上,不会占用顾客的沙发;
<!--[if !supportLists]-->2、<!--[endif]-->处理休息状态的理发师可为在沙发上等待时间最长的顾客理发;
<!--[if !supportLists]-->3、<!--[endif]-->理发时间长短由理发师决定;
<!--[if !supportLists]-->4、<!--[endif]-->在站席区等待时间最长的顾客可坐到空闲的理发上;
<!--[if !supportLists]-->5、<!--[endif]-->任何时刻最多只能有一个理发师在收银。
游戏参与者:理发师,顾客
伪代码:
semaphore stand_capacity=5;
semaphore sofa=4;
semaphore barber_chair=3;
semaphore customer_ready=0;
semaphore mutex=3;
semaphore mutex1=1;
semaphore finished[3]={0,0,0};
semaphore leave_barberchair=0;
semaphore payment=0;
semaphore receipt=0;
void customer()
{
顾客:
int barber_number;
wait(stand_capacity); //等待进入理发店
enter_room(); //进入理发店
wait(sofa); //等待沙发
leave_stand_section(); //离开站席区
signal(stand_capacity);
sit_on_sofa(); //坐在沙发上
wait(barber_chair); //等待理发椅
get_up_sofa(); //离开沙发
signal(sofa);
wait(mutex1);
sit_on_barberchair(); //坐到理发椅上
signal(customer_ready);
barber_number=dequeue(); //得到理发师编号
signal(mutex1);
wait(finished[barber_number]); //等待理发结束
pay(); //付款
signal(payment); //付款
wait(receipt); //等待收据
get_up_barberchair(); //离开理发椅
signal(leave_barberchair); //发出离开理发椅信号
exit_shop(); //了离开理发店
}
对于理发师:
void barber(int i)
{
while(true)
{
wait(mutex1);
enqueue(i); //将该理发师的编号加入队列
signal(mutex1);
wait(customer_ready); //等待顾客准备好
wait(mutex);
cut_hair(); //理发
signal(mutex);
signal(finished[i]); //理发结束
wait(leave_barberchair); //等待顾客离开理发椅信号
signal(barber_chair); //释放barber_chair 信号
}
}
void cash() //收银
{
while(true)
{
wait(payment); //等待顾客付款
wait(mutex); //原子操作
get_pay(); //接受付款
give_receipt(); //给顾客收据
signal(mutex);
signal(receipt); //收银完毕,释放信号
}
}
6、过桥问题
问题:一座小桥(最多能承重两个人)横跨南北两岸,任意时刻同一方向只允许一个人过桥;南侧的桥段和北侧的桥段较窄只能一个人通过,桥中央一处宽敞,允许两个人通过或者休息。
游戏参与者:南北过桥者;
资源:桥的承重(对多两人,相当于资源的两个份额)
信号量使用:
Load:(技术信号量)
North:(二元信号量)
South:(二元信号量)
伪代码:
int countSN=0;
int countNS=0;
semaphore mutexSN=1;
semaphore mutexNS=1;
semaphore bridge=1;
6、和尚打水问题(生产消费变种):
问题描述:某寺庙,有小和尚和老和尚若干,有一个水缸,由小和尚提水入缸供老和尚饮用。水缸可以容纳10桶水,水取自同一口井中,由于水井口窄,每次只能容纳一个水桶取水。水桶总数为3个。每次入水、取水仅为一桶,且不可同时进行
信号量设置:
<!--[if !supportLists]-->1、<!--[endif]-->对于水缸——以一个水桶水为单位,empty=30、full = 0两个计数信号量
<!--[if !supportLists]-->2、<!--[endif]-->小和尚对缸操作:mutex-jar = 1二元信号量;
<!--[if !supportLists]-->3、<!--[endif]-->水桶个数(资源数):bucket = 5计数信号量
<!--[if !supportLists]-->4、<!--[endif]-->取水操作(每次入水、取水仅为一桶):互斥mutex-well = 1二元信号量;
伪代码:
7、一家人吃水果问题:
问题描述:桌子上有一只盘子,每次只能放一个水果,爸爸专向里面放苹果,妈妈放橘子,儿子专吃橘子,女儿专吃苹果,仅当盘子空闲时,爸爸妈妈才可以向里面放水果,仅当盘子里有自己需要的水果时,儿子女儿才可以从里面取出一只水果。
生产者消费者变种问题:
1、空间变为一个,不同的消费者需求不同;
2、信号量变化:Full——用两个信号量表示So=0、SA=0(表示橘子和苹果两种),empty=1不变;
伪代码:
int e=1,a=o=0;
main()
{father();
//son();
//daughter();/*三个为并发进程*/
}
father()
{while(1)
{ 洗水果
wait(e)
把水果放入盘子
if(水果是苹果)signal(a)
else signal(o)
}
}
son()
{while(1)
{wait(o)
从盘子里取桔子
signal(e)
吃桔子}
}
daughter()
{while(1)
{wait(a)
从盘子里取苹果
signal(e)
吃苹果}
}
相关推荐
分析哲学家进餐问题,p,v操作实现互斥与同步,分析记录性信号量的不足,并指出给改进方法 方法一:最多允许4人同时进餐; 方法二:分奇偶数进餐,以及AND型信号量解决该问题。 (免费下载,无需积分)
有五个哲学家围坐在一圆桌旁,桌中央有一盘通心粉,每人面前有一只空盘子,每两人之间放一只筷子每个哲学家的行为是思考,感到饥饿,然后吃通心粉.为了吃通心粉,每个哲学家必须拿到两只筷子,并且每个人只能直接从...
经典进程同步问题,如苹果桔子问题,哲学家问题,消费者问题...
操作系统中哲学家就餐问题和生产者消费者问题实验报告
进程同步模拟设计--哲学家就餐问题 进程同步异步
选择一个进程同步的经典问题,包括生产者消费者问题,写者问题,哲学家就餐问题和理发师睡眠问题,写一个程序来模拟。
课程完整报告 实现哲学家就餐问题 1)熟悉Ubuntu系统环境和...生产者和消费者之间必须保持同步原则:不允许消费者进程到一个空缓冲区去取产品;也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。
操作系统 哲学家问题 哲学家问题操作系统操作系统
操作及进程同步的实现哲学家就餐问题.pdf
进程同步互斥——不死锁哲学家问题 java实现。计算机系统原理,课程设计,(1)利用进程并发执行原理,采用奇数号哲学家先拿左叉子,偶数号哲学家先拿右叉子的算法解决哲学家就餐问题。 (2)利用java中Swing技术将...
操作系统实训报告进程同步和互斥通过实现哲学家进餐问题的同步深入了解和掌握进程同步和互斥的原理。哲学家有N个,也定全体到达后开始讨论:在讨论的间隙哲学家进餐,每人进餐时都需使用刀、叉各一把,所有哲学家刀...
生产者和消费者问题以及哲学家就餐问题,JAVA实现的程序.rar产者和消费者问题以及哲学家就餐问题,JAVA实现的程序.rar
gcc,典型同步问题,哲学家问题,消费者问题,读者写者问题
利用C语言程序模拟生产者-消费者问题和哲学家进餐问题。 实验设备及环境: Pc机一台,vc6.0 for windows 实验步骤: 1.以记录型信号量实现生产者-消费者问题; 2.利用AND信号量解决生产者-消费者问题; 3.利用记录...
有五个哲学家围坐在一圆桌旁,桌中央有一盘通心粉,每人面前有一只空盘子,每两人之间放一只筷子。每个哲学家的行为是思考,感到饥饿,然后吃通心粉。为了吃通心粉,每个哲学家必须拿到两只筷子,并且每个人只能直接...
实验一 进程同步互斥——不死锁的哲学家问题 (1)输入的形式和输入值的范围; 由于这个是一个按钮实现监控,界面提供视图的程序,所以并不需要别的附加的输入,只需要点击相应的按钮即可。按钮有开始、暂停、结束...
关于5个哲学家就餐线程同步问题的解决方法 此方法对左右手刀叉实行控制,防止了死锁,实现了线程的同步 注意5个以上的哲学家亦可用此方法解决
操作系统课程中模拟哲学家进餐问题的c++程序,MFC开发
操作系统哲学家问题代码,但最后结果好像稍微有点bug,发生原因不详,有时候重启就好了,怀疑是调试机本身系统问题
操作系统初学,关于信号量同步的实验报告,用三种方法避免哲学家进餐问题死锁,a:and信号量,b:控制进餐人数,c设置条件