大连网站程序开发,腾讯体育,兼职做网站系统,大足专业建站公司1、概念
1.1 进程同步与互斥
在多道程序环境下#xff0c;进程是并发执行的#xff08;并发执行是指两个或多个事件在某段时间间隔内并发#xff09;#xff0c;不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系#xff0c;引入了进程同步的概念。…1、概念
1.1 进程同步与互斥
在多道程序环境下进程是并发执行的并发执行是指两个或多个事件在某段时间间隔内并发不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系引入了进程同步的概念。
进程同步是直接制约关系指为完成某种任务而建立的两个或多个进程这些进程因为需要在某些位置上协调他们的工作次序而等待、传递信息所产生的的制约关系。源于他们之间的互相合作关系
进程互斥是间接制约关系当一个进程进入临界区使用临界资源时另一个进程必须等待当占用临界资源的进程退出临界区时另一个进程才允许去访问此临界资源。
临界资源是一次仅允许一个进程使用的资源临界资源的访问过程进入区在进入区要检查可否进入临界区并设置正在访问临界区的标识以阻止其他进程同时进入临界区退出区剩余区
临界区是访问临界临界资源的那段代码
同步机制准则
空闲让进临界区空闲时可以允许一个请求进入临界区的进程立即进入临界区
忙则等待当已有进程进入临界区时其他试图进入临界区的进程必须等待
有限等待对请求访问的进程应保证能在有限时间内进入临界区
让权等待当进程不能进入临界区时应立即释放处理器防止进程忙等待
1.2 信号量
信号量是一种功能较强的机制可以用来解决互斥与同步的问题它只能被两个标准的原语操作即为“P”和“V”操作P操作是信号量减1V操作是信号量加1
原语是指完成某种功能且不被分割、不被中断执行的操作序列
1整型信号量
整型信号量是来表示资源数目的整形量S只要S≤0就会不断测试并未遵循“让权等待”的准则而是使进程处于“忙等”状态。
P(S){while(S0){S S-1}
}V(S){SS1
}
2记录型信号量
记录型信号量机制是一种不存在“忙等”现象的进程同步机制除了表示资源数目的整型变量S外再增加一个进程链表L用于链接所有等待该资源的进程。
//定义结构体
typedef struct{int S;struct process *L;
}semaphore;void P(semaphore se){se.S--;if(se.S0){add this process to se;block(se); //调用block原语进行自我阻塞}
}void V(semaphore se){se.Sif (se.S0){remove a process P from se;wakeup(P); //调用wakeup原语唤醒链表中的第一个等待进程}
}
3分析进程同步和互斥问题的方法步骤
关系分析找出问题中的进程数并分析他们之间的同步和互斥关系整理思路找出解决问题的关键点并且根据做过的题目找出解决思路根据进程的操作流程确定P操作V操作的大致顺序设置信号量设置需要的信号量确定处置完善整理
4利用信号量实现进程同步
问题描述S为P1、P2两个进程的公共信号量初始值为0进程P2执行需要依赖进程P1中语句x的运行结果即只有当语句x执行完成之后语句y才可以执行。
semaphore S0;P1(){x; //先执行xV(S); //s
}P2(){P(x);y ;V(y);}
5利用信号量实现互斥
问题描述设S为实现进程P1、P2互斥的信号量由于每次只允许一个进程进入临界区设置S1即可用资源数为1当进程对信号量S进行P操作后进入临界区并在退出后该进程对该信号量执行V操作表示没有进程进入临界区可以让其他进程进入。设计如下
semaphore S1;P1(){P(S); //访问临界资源S--//进入临界区V(S);//访问结束S
}
P2(){P(S); //访问临界资源S--//进入临界区V(S);//访问结束S
}
2、经典问题
2.1 生产者-消费者
问题描述一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区只有缓冲区没满时生产者才能把消息放入到缓冲区否则必须等待只有缓冲区不空时消费者才能从中取出消息否则必须等待。由于缓冲区是临界资源它只允许一个生产者放入消息或者一个消费者从中取出消息。问题分析
1关系分析生产者和消费者对缓冲区访问是互斥生产者和消费者又是相互协作关系生产者生产之后才能消费属于同步关系
2整理思路只有生产者和消费者两个进程两个进程间存在着同步和互斥关系要解决互斥和同步PV操作的位置
3信号量设置:信号量mutex作为互斥信号量它用于控制互斥访问缓冲池互斥信号量初值为1信号量full用于记录当前缓冲池中“满”缓冲区数初值为0。信号量empty 用于记录当前缓冲池中“空”缓冲区数初值为n。
#define semaphore intsemaphore emptyn; //表示空缓冲区的个数
semaphore full0; //表示满缓冲区的个数semaphore mutex 1; //互斥信号量生产者和消费者共用缓冲区void Producer(){while(1) {produce a item; //生产数据P(empty); //空缓冲区的个数减1P(mutex); //互斥变量减1进入临界区add item to buffer; // 将item放入缓冲区V(mutex); //互斥量加1退出临界区V(full); //满缓冲区加1}
}
void Consumer(){P(full); // 同步判断缓冲区是否有生产者P(mutex); //互斥变量减1进入临界区remove item from buffer; //将item移除缓冲区V(mutex); //互斥量加1退出临界区V(empty); //空缓冲区加1consumer a item; //消费数据
}
2.2 分水果问题
问题描述桌子上有一个盘子每次只能想其中放入一个水果爸爸专向盘子中放苹果妈妈专向盘子中放橘子儿子专等吃盘子中的橘子女儿专等吃盘子中的苹果。只有盘子为空时爸爸或妈妈就可向盘子中放一个水果仅当盘子中有自己需要的水果时儿子或女儿可以从盘子中取出。问题分析
1关系分析。这里的关系稍复杂一些首先由每次只能向其中放入一只水果可知爸爸和妈妈是互斥关系。爸爸和女儿、妈妈和儿子是同步关系而且这两对进程必须连起来儿子和女儿之间没有互斥和同步关系因为他们是选择条件执行不可能并发
2整理思路。这里有4个进程实际上可以抽象为两个生产者和两个消费者被连接到大小为1的缓冲区上
3 信号量设置。首先设置信号量plate为互斥信号量表示是否允许向盘子放入水果初值为1表示允许放入且只允许放入一个。信号量 apple表示盘子中是否有苹果初值为0表示盘子为空不许取若apple1可以取。信号量orange表示盘子中是否有橘子初值为0表示盘子为空不许取若orange1可以取。
notes:生产者和消费者是生产者生产完把缓冲区释放消费者再去访问缓冲区分水果是放完水果标记盘子有水果才会去拿水果再释放盘子。
#define semaphore int
semaphore plate1; //互斥
semaphore apple0;
semaphore orange0;void dad(){while(1){//prepare an appleP(plate);put the apple on the plate;V(apple); //apple标记为1证明盘子有apple}
}void mom(){while(1){//prepare an orangeP(plate);put the orange on the plate;V(orange); //orange标记为1证明盘子有orange}
}void daughter(){while(1){P(apple) take an apple from the plate;V(plate); //plate标记为1证明可以放水果了eat the apple;}
}void son(){while(1){P(orange) take an orange from the plate;V(plate); //plate标记为1证明可以放水果了eat the orange;}
}
2.3 读者和写者问题
问题描述有读者和写者两组并发进程共享一个文件当两个或以上的读进程同时访问共享数据时不会产生副作用但若某个写进程和其他进程读进程或写进程同时访问共享数据时则可能导致数据不一致的错误。因此要求①允许多个读者可以同时对文件执行读操作②只允许一个写者往文件中写信息③任一写者在完成写操作之前不允许其他读者或写者工作④写者执行写操作前应让已有的读者和写者全部退出。问题分析
1关系分析有两个进程读者进程和写者进程写者和读者、写者和写者都是互斥的读者和读者是同步关系依次访问依次退出可以同时有多个读者在读
2整理思路写者是跟任何进程互斥用PV可以解决读者比较复杂除了实现与写者的互斥还要实现与其他读者的同步设计了一个计数器来判断当前是否有读者读文件同时不同读者对计数器的访问也应该是互斥的
3信号量设置首先设置信号量count为计数器用来记录当前读者数量初值为0; 设置rmutex为互斥信号量用于保护更新count变量时的互斥设置互斥信号量rw用于保证读者和写者的互斥访问。
#define semaphore int
semaphore rmutex1; //读者之间依次访问和退出的互斥量
semaphore wmutex1; //写者和读者的互斥量
int count0; //统计读者的数量void reader(){while(1){P(rmutex)if(count0) P(wmutex); //count0 意味着没有读者在读文件可以写文件先进行加锁count;V(rmutex)reading; //读者进入之后进行写文件P(mutex);count--;if(count0)V(wmutex); //count0证明读者已经读完退出文件可以写并将互斥量解锁V(rmutex); //释放互斥变量}
}void writer(){while(1){P(wmutex);writing;V(wmutex);}
}
2.4 哲学家进餐死锁
问题描述一张圆桌上坐着5名哲学家每两个哲学家之间的桌上摆一根筷子桌子的中间是一碗米饭如图2-10所示。哲学家们倾注毕生精力用于思考和进餐哲学家在思考时并不影响他人。只有当哲学家饥饿的时候才试图拿起左、 右两根筷子一根一根地拿起。如果筷子已在他人手上则需等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐当进餐完毕后放下筷子继续思考。补充饥饿和死锁的定义
“饥饿”并不表示系统一定死锁但至少有一个进程的执行被无限期推迟。“饥饿”与死锁的主要差别有
1进入“饥饿”状态的进程可以只有一个而由于循环等待条件而进入死锁状态的进程却必须大于或等于两个。
2处于“饥饿”状态的进程可以是一个就绪进程如静态优先权调度算法时的低优先权进程而处于死锁状态的进程则必定是阻塞进程。
问题分析
1关系分析5个哲学家和左右邻居对其中间的筷子访问是互斥关系
2整理思路本题的关键是如何让一个哲学家拿到左右两个筷子而不造成死锁或者饥饿现象。那么解决方法有两个一个是让他们同时拿两个筷子二是对每个哲学家的动作制定规则避免饥饿或者死锁现象的发生。
3信号量设置定义互斥信号量数组chopstick[5] {l, 1, 1, 1, 1}用于对5个筷子的互斥访问。对哲学家按顺序从04编号哲学家i左边的筷子编号为i哲学家右边的筷子编号(i1)%5。同时拿两边的筷子
#define semaphore int
semaphore chopstick[5]{1,1,1,1,1}Pi(){while(1){P(chopstick[i]); //拿左筷子P(chopstick[(i1)%5]); //拿右筷子eat; //进餐V(chopstick[i]); //放下左筷子V(chopstick[(i1)%5]); //放下右筷子think; //思考}}
该算法存在以下问题当五个哲学家都想要进餐分别拿起他们左边筷子的时候都恰好执行完P(chopstick[i]);)筷子已经被拿光了等到他们再想拿右边的筷子的时候执行 P(chopstick[(il)%5]);)就全被阻塞了这就出现了死锁。
为了防止死锁的发生可以对哲学家进程施加一些限制条件比如至多允许四个哲学家同时进餐;仅当一个哲学家左右两边的筷子都可用时才允许他抓起筷子;对哲学家顺序编号要求奇数号哲学家先抓左边的筷子然后再转他右边的筷子而偶数号哲学家刚好相反。正解制定规则如下假设釆用第二种方法当一个哲学家左右两边的筷子都可用时才允许他抓起筷子。
semaphore chopstick[5] {1,1,1,1,1}; //初始化信号量
semaphore mutexl; //设置取筷子的信号量
Pi(){ //i号哲学家的进程while(1){P (mutex) ; //在取筷子前获得互斥量P (chopstick [i]) ; //取左边筷子P (chopstick[ (i1) %5]) ; //取右边筷子V (mutex) ; //释放取筷子的信号量eat; //进餐V(chopstick[i] ) ; //放回左边筷子V(chopstick[ (il)%5]) ; //放回右边筷子think; // 思考}
}
参考内容
信号量整型、记录型信号量以及利用信号量实现进程互斥和前驱关系_C语言中文网
