网站开发的心得体会,文化网站建设,西安学建网站,想做网站文章目录1. 基本结构2. P,V操作3. 信号量的应用3.1 信号量实现进程互斥3.2 信号量实现前驱关系4. 用信号量解经典同步问题4.1 生产者消费者问题4.2 读者写者问题4.3 狒狒过桥问题4.4 理发师理发问题4.5 哲学家进餐问题信号量机制是Dijkstra提出的一种卓有成效的进程同步工具。信…
文章目录1. 基本结构2. P,V操作3. 信号量的应用3.1 信号量实现进程互斥3.2 信号量实现前驱关系4. 用信号量解经典同步问题4.1 生产者消费者问题4.2 读者写者问题4.3 狒狒过桥问题4.4 理发师理发问题4.5 哲学家进餐问题信号量机制是Dijkstra提出的一种卓有成效的进程同步工具。信号量有整形信号量、记录型信号量、AND型信号量等这里主要介绍我们常见的记录型信号量。1. 基本结构
typedef struct {int value; //信号量值struct process_cntrol_block *list; //阻塞队列
}semaphore;在应用信号量的时候信号量的值往往是临界资源的数量。当临界资源数量不足时新的进程就阻塞并插入到信号量阻塞队列中。
2. P,V操作
wait(S)和signal(S)操作是信号量机制的基本操作(通常称作PV操作)定义如下
wait(semaphore *S) {S-value--; //信号量的值减一if(S-value 0) block(S-list); //如果信号量的值小于零,进程阻塞signal(semaphore *S) {S-value; //信号量的值加一if(S-value 0) wakeup(S-list); //唤醒
}在实现进程同步时一般先将S-value的初值设定为临界资源的初始数量一旦进程要请求一个临界资源先对代表此进程的信号量执行P操作也就意味着资源数减一当该进程运行完毕时执行V操作意味着资源数加一。值得注意的是如果当前资源数量为0再有进程想请求临界资源就会在执行P操作时进入阻塞队列信号量值变为-1此后执行P操作的进程也都会被阻塞信号量的绝对值为阻塞的进程数目。
3. 信号量的应用
3.1 信号量实现进程互斥
有了P,V操作我们就能很简单的实现进程互斥。方法是设mutex为互斥信号量初值为1。在需要互斥的临界区前后分别使用P,V操作即可示意代码如下
semaphore mutex 1; //一般初值为1的信号量用来实现互斥
P_A() { //进程Awhile(1) {P(mutex);临界区V(mutex);剩余区}
}
P_B() { //进程Bwhile(1) {P(mutex);临界区V(mutex);剩余区}
}在互斥问题中我们可以把P操作理解成“上锁”把V操作理解成“解锁”当P_A和P_B两个进程并发执行时无论哪一个进程先执行到了P操作都会接下来执行P操作的进程阻塞直到前一个进程执行到了V操作为止这样就实现了临界区的互斥。
3.2 信号量实现前驱关系
思路如下为每一组想要实现前后关系的进程都分别定义一个信号量初值设为0把你想要先执行的进程后面加一个V操作想要后执行的进程前面加一个P操作。这样一来你想要后执行的进程如果先执行了就会因为执行了其前面的P操作而阻塞直到你想要先执行的进程执行完了执行V操作后才能解除阻塞继续执行。以上就是用信号量实现前驱关系的过程。 假如我们要实现四个语句S1,S2,S3,S4需要按照一定的顺序同步执行比如S1执行完S2S3才能执行S2,S3执行完了S4才能执行代码如下
p1() {S1; V(a); V(b);}
p2() {P(a); S2; V(c);}
p3() {P(b); S3; V(d);}
p4() {P(c); P(d); S4;}main() {semaphore a,b,c,d 0;cobeginp1();p2();p3();p4();coend
}4. 用信号量解经典同步问题
4.1 生产者消费者问题
假定生产者和消费者之间的公用缓冲池有n个缓冲区生产者可以向缓冲区生产一个产品消费者可以从缓冲区消耗一个产品注意生产者不能同时生产消费者也不能同时消费也不能同时生产和消费当缓冲区空时无法消费当缓冲区满时无法生产。请用信号量机制解决这一问题。 解法如下
semaphore mutex 1; //实现生产与消费、生产与生产、消费与消费
semaphore full 0, empty n; //full表示已用缓冲区数empty表示空缓冲区数
void producer() {while(1) {P(empty); //每次生产会减少一个空缓冲区如果没有空缓存区了就阻塞P(mutex); //保证互斥生产一个产品;V(mutex); //保证互斥V(full); //每次生产增加一个已用缓冲区}
}
void consumer() {while(1) {P(full); //每次消费会减少一个已用缓冲区如果没有已用缓存区了就阻塞P(mutex);消耗一个产品;V(mutex);V(empty); //每次生产增加一个空缓冲区}
}4.2 读者写者问题
假设一个文件可被多个进程共享我们允许多个进程同时读这个共享对象但是不允许一个进程写这个共享对象的同时别的进程进行读或写。换句话说读和读不互斥读和写互斥写和写互斥。请用信号量机制解决这一问题。 解法如下
semaphore rmutex, wmutex 1; //wmutex用以实现写进程与其它进程的互斥
int readcount 0; //记录读进程的数量
void reader() {while(1) {P(rmutex); //见下文解释if(readcount 0) P(wmutex); //第一个读进程去把写进程上锁readcount; V(rmutex); //见下文解释读者读;P(rmutex); //见下文解释readcount--;if(readcount 0) V(wmutex); //解锁V(rmutex); //见下文解释}
}
void writer() {while(1) {P(wmutex); //实现写进程与其他进程都互斥写者写;V(wmutex);}
}这个问题的程序中有个关键点就是明明读进程是不互斥的为什么还需要rmutex来实现if判断的互斥呢。原因如下当我们在进程互斥中使用条件语句和数值变化的时候如果不把那一段也实现互斥的话很有可能出问题比如在这段代码中要是不加第5行和第8行的话如果一个读进程执行完了第6行还没有执行第7行的readcount操作之前这个读进程被剥夺了处理机换另一个读进程上处理机运行了那么另一个读进程就会阻塞在第6行的P操作上就无法实现多个读者一起读了10行和13行同理如果一个读进程执行完了第11行就被剥夺处理机换上另一个读进程也执行了11行这样readcount被连减两次那么这两个进程都能通过12行的if判断会执行两次V操作产生错误。
4.3 狒狒过桥问题
一个主修人类学、辅修计算机科学的学生参加了一个课题调查非洲狒狒是否能被教会理解死锁。他找到一处很深的峡谷在上边固定了一根横跨峡谷的绳索这样狒狒就可以攀住绳索越过峡谷。同一时刻可以有几只狒狒通过只要它们朝着相同的方向。但如果向东和向西的狒狒同时攀在绳索上则将发生死锁狒狒将被卡在中间因为它们无法在吊在峡谷上时从另一只的背上翻过去。如果一只狒狒想越过峡谷它必须看当前是否有别的狒狒正在逆向通过。使用信号量写一个避免死锁的程序来解决该问题。 解法如下
semaphore wmutex, emutex, mutex 1;
int wcount, ecount 0; //分别记录东西狒狒上绳索的个数
void west_monkey {while(1) {P(wmutex); //使if语句互斥if(wcount 0) P(mutex); //第一个西狒狒给东狒狒上锁wcount;V(wmutex); //使if语句互斥西狒狒过桥P(wmutex);wcount--;if(wcount 0) V(mutex);V(wmutex);}
}
void east_monkey { //和上面的一样while(1) {P(emutex);if(ecount 0) P(mutex);ecount;V(emutex);西狒狒过桥P(emutex);ecount--;if(ecount 0) V(mutex);V(emutex);}
}该问题属于读者写者问题的改进如果完全理解了读者写者问题的解法那么这个问题也能很快解决。东狒狒之间不互斥西狒狒之间不互斥东西狒狒之间互斥思路是第一个东狒狒给西狒狒上锁第一个西狒狒给东狒狒上锁注意if判断也要实现互斥。
4.4 理发师理发问题
理发店里有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客则理发师便在理发椅上睡觉。当一个顾客到来时他必须先叫醒理发师如果理发师正在理发时又有顾客来到则如果有空椅子可坐他们就坐下来等。如果没有空椅子他就离开。这里的问题是为理发师和顾客各编写一段程序来描述他们的行为要求不能带有竞争条件。 解法如下
semaphore customer, barber 0; //一开始没有顾客理发师也是睡着的
semaphore mutex 1; //互斥信号量
int empty N; //空椅子数量为N
void Barber() {while(1) {P(customer); //只有顾客进程的V执行后才能执行没有顾客就阻塞睡觉P(mutex); //把数量的变化实现互斥以免影响到顾客进程的if判断语句empty; //椅子上的顾客起身V(barber); //有了一个理发师可以理发V(mutex);理发;}
}
void Customer() {P(mutex);if(empty 0) {empty--; //不管是不是第一个顾客来了先得坐凳子上因为理发师在理发椅上睡觉呢V(customer); //增加一个顾客唤醒沉睡的理发师V(mutex); P(barber); //消耗一个理发师没有理发师就阻塞理发;} else {V(mutex);离开;}
}这道题本身不难但其中很多细节的实现需要实现比如座位是有上限的这样就不得不设置判断条件和计数来使超过N个的顾客离开而加入计数和判断条件后就又要实现其互斥增加了问题的复杂性。
4.5 哲学家进餐问题
五个哲学家共用一张圆桌分别坐在周围的五张椅子上在桌子上有五只碗和五只筷子他们的生活方式是交替地进行思考和进餐。平时一个哲学家进行思考饥饿时便试图取用其左右最靠近他的筷子只有在他拿到两只筷子时才能进餐。进餐毕放下筷子继续思考。请用信号量机制解决。 这是一个讲解死锁的时候的经典例子解决这道题的直接思路如下
semaphore chopstick[5] {1,1,1,1,1};
void philosopher() {while(1) {/*当哲学家饥饿时总是先拿左边的筷子再拿右边的筷子*/P(chopstick[i]);P(chopstick[(i1)%5]);吃饭;V(chopstick[i]);V(chopstick[(i1)%5]);}
}但是这样可能会出现死锁问题如果所有哲学家都拿起了左手边筷子五个进程就会死锁。对于避免哲学家进餐问题发生死锁的方法有很多这里只讲一种只有当同时一个哲学家能同时拿起左右两只筷子时才允许拿筷子解法如下
semaphore chopstick[5] {1,1,1,1,1};
semaphore mutex 1;
void philosopher() {while(1) {P(mutex);P(chopstick[i]);P(chopstick[(i1)%5]);V(mutex);吃饭;V(chopstick[i]);V(chopstick[(i1)%5]);}
}但仅仅这样做还是有问题如果一个哲学家获得了两只筷子开始进餐此时他左边或者右边的哲学家进入了临界区后被阻塞在第6行或者第7行那么其他的哲学家就无法进入临界区了也就是说这个时间只能有一个哲学家进餐但显然同一时间是可以有不相邻的两个哲学家同时进餐的。 对这个问题的更好解决方法可以去看Dijkstra在1965年给出的算法。
