课程名称：课程设计（UNIX程序设计）
设计题目：利用信号量机制解决哲学家进餐问题
姓名：
专业：网络工程
班级：
学号：
计算机科学与技术学院
网络系
2013年12月28日
设计项目：利用信号量机制解决哲学家进餐问题
一、选题背景
1965年，数学家迪杰斯特拉提出，并成为经典的IPC问题—哲学家进餐问题。该问题的简单描述如下：五个哲学家围坐在一张圆桌周围，每个哲学家面前都一盘通心粉。由于通心粉很滑，需要两把叉子才能夹住。哲学家的生活中有两种交替活动时段，吃饭（EATING）和思考（THINKING）。当一个哲学家觉得饿了时，他就试图分两次去取左手边和右手边的叉子，每次拿一把，但不分次序。如果成功拿到两把叉子，就进入吃饭状态，吃完后放下叉子继续思考。
二、设计思路
1.每个哲学家的行为活动状态为两种：进餐（EATING）和思考（THINKING）。因此创建一个有5个元素的状态数组，每个数组元素的状态值为EATING或者THINKING。
2.五个哲学家围坐成一圈，每两个人中间有一个叉子，即每个哲学家的边和右边有一个叉子，但这个叉子需要和旁边的邻居竞争使用。对于每一个哲学家来说，其只有成功获得两个叉子，才能进入进餐状态。在进完餐后，需要成功放下手中的两个叉子，才能进入思考的状态。换个角度的描述就是，每个哲学家查询左右边的邻居当前状态，如果左右的邻居当前状态都为THINKING，则该哲学家可以进餐；如果左右邻居当前状态不都是THINKING，则哲学家不能进餐。因此可以为每一个哲学家设置一个信号量，来描述哲学家的活动状态。
3.因为五只叉子做多只能允许两个哲学家进餐，所以可以将桌子作为一个临界资源。通过设置一个互斥信号量来限制对临界资源的访问数。
4.创建两个动作函数，对应于每个哲学家的获取两把叉子和放下两把叉子的动作。而每个动作都需要对互斥信号量和哲学家信号量进行访问操作，因此创建原子操作P和原子操作V，来执行对信号量的消耗和释放操作。
5.利用父进程创建五个子进程来模拟五个哲学家，在每个子进程中执行PHILOSOPHER （phi_num）函数来模拟每个哲学家进入哲学家进餐问题活动。
三、主要问题的解决方法和关键技术
1.共享状态数组问题。
问题描述：因为状态数组是共享的，而每个模拟哲学家的子进程是相互独立的，有自己的地址空间，在进程之间共享使用状态数组出现问题。
解决方法：父进程通过利用UNIX系统进程通信机制中共享内存机制的shmget()和shmat系统调用创建一个共享内存区，并将状态数组地址链接到进程地址空间，成功的解决了该问题。
2.信号量创建及初始化问题
问题描述：整个程序使用两个不同的信号量，一个是记录型信号量数组，一个是互斥信号量，并且在信号量创建初就需要对信号量进行初始化，这样才能保证接下来的子进程运行时，五个子进程面对的是相同值的信号量数组。
解决方法：父进程通过利用UNIX系统进程通信机制中信号量机制的semget（）系统调用和semctl()系统调用，成功创建一个五元素的信号量数组和一个元素的信号量数组，并将其在初始为设计的初始值，保证了程序后续操作的正确。
3.P和V原子操作问题
问题描述：在子进程中的对信号量的操作必须是原子操作P和V，而且由于在动作函数中需要调用P和V原子操作，所以必须保证P和V操作的原子性，否则函数之间参数的传递将出现不一致。
解决方法：利用UNIX系统进程通信机制中信号量机制的semop（）系统调用，封装P和V操作函数，保证了函数的原子性。
4.进程创建的准确时刻问题
问题描述：根据设计的描述，程序是通过五个子进程来模拟五个哲学家，但对进程创建的先后顺序没有要求，又由于进程分配到时间片是有限的，并且在创建的过程中要保证五个子进程都是统一父进程创建的，所以对于进程的创建时刻不太容易确定。
解决方法：利用的UNIX系统的进程创建fork（）系统调用，创建一个有五个子进程的进程扇，成功的解决创建准确时刻问题
5.哲学家动作函数编译问题
问题描述：在哲学家的三个动作函数中需要对两个类型的信号量进行操作，所以不可避免的需要调用P和V原子操作。尽管在动作函数定义之前，已经声明了P和V函数。但是由于其原子性，在动作函数中直接使用P，V函数导致了严重的编译错误问题。
解决方法：通过在各个函数参数列表中添加需要指向将使用的P和V函数指针，并在使用时采用（*P）和（*V）形式来解除引用操作，成功的解决了编译错误问题。
四、程序流程图
约定：
Take_forks 函数动作 TKFK
Put_forks 函数动作 PTFK
Test 函数动作 TEST
THINKING 思考状态 THINK
EATING 进餐状态 EAT
五、原程序清单
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 5
#define LEFT(i) (i+N-1)%N
#define RIGHT(i) (i+1)%N
#define THINKING 0
#define EATING 1
//#include"behavior_philosophy.h"
void philosopher(int , char*, int , int , void (*)(int, int), void (*)(int, int)); void take_forks(int , char* , int , int ,void (*)(int, int), void (*)(int, int)); void put_forks(int , char* , int , int ,void (*)(int, int), void (*)(int, int)); void test(int , char* , int ,void (*)(int, int));
void think(int );
void eat(int );
void P(int , int );
void V(int , int );
/*------------------------哲学家动作-----------------*/
void philosopher(int i, char* state, int sem_phiid, int sem_mutexid, void (*P)(int, int), void (*V)(int, int)){
sleep(1);
think(i);
while(1){
take_forks(i, state, sem_phiid, sem_mutexid, P, V);
eat(i);
put_forks(i, state, sem_phiid, sem_mutexid, P, V);
think(i);
}
}
void take_forks(int i, char* state, int sem_phiid, int sem_mutexid, void (*P)(int, int) , void (*V)(int, int)){
(*P)(sem_mutexid, 0);
state[i] = THINKING;
test(i, state, sem_phiid, V);
(*V)(sem_mutexid, 0);
(*P)(sem_phiid, i);
}
void put_forks(int i, char* state, int sem_phiid, int sem_mutexid,void (*P)(int,
int), void (*V)(int, int)){
(*P)(sem_mutexid, 0);
state[i] = THINKING;
test(LEFT(i), state, sem_phiid, V);
test(RIGHT(i), state, sem_phiid, V);
(*V)(sem_mutexid, 0);
}
void test(int i, char* state, int sem_phiid,void (*V)(int, int)){
if(state[i] == THINKING && state[LEFT(i)] != EATING && state[RIGHT(i)]!=EATING){
state[i] = EATING;
(*V)(sem_phiid, i);
}
}
void think(int i){
printf("philosopher:%d>>>>>is THINKING.\n", i);
}
void eat(int i){
printf("I'm philosopher:%d>>>>>is EATING.and will eating %d seconds!\n", i, sleep(2));
}
/*---------------------P,V原子操作------------*/
void P(int semid, int index){
struct sembuf sema_buffer;
sema_buffer.sem_num = index;
sema_buffer.sem_op = -1;
sema_buffer.sem_flg = SEM_UNDO;
semop(semid, &sema_buffer, 1);
}
void V(int semid, int index){
struct sembuf sema_buf;
sema_buf.sem_num = index;
sema_buf.sem_op = 1;
sema_buf.sem_flg = SEM_UNDO;
semop(semid, &sema_buf, 1);
}
/*-----------------------------------------------------------*/
int main( )
{
/*-------------------------创建信号量操作----------------*/ int sem_phiid;
sem_phiid = semget(1008, 5, 0666|IPC_CREAT);
assert(sem_phiid>=0);
unsigned short array[5] = {0, 0, 0, 0, 0};
union semun{
int val;
unsigned short *array;
}semopts;
semopts.array=array;
int ret1 = semctl(sem_phiid, 0, SETALL, semopts);
assert(ret1 == 0);
int sem_mutexid;
sem_mutexid = semget(0x225, 1, 0666|IPC_CREAT);
assert(sem_mutexid >= 0);
semopts.val = 1;
int ret2 = semctl(sem_mutexid, 0, SETVAL, semopts); assert(ret2 == 0);
/*------------------初始化共享内存-----------------------*/ int shmid;
char* state;
if((shmid = shmget(IPC_PRIVATE, N, 0600|IPC_CREAT)) == -1){ semctl(sem_phiid, 0, IPC_RMID, 0);
semctl(sem_mutexid, 0, IPC_RMID, 0);
perror("shmget faild!");
exit(1);
}
if((state = shmat(shmid, 0, 0)) == (char *)-1){
semctl(sem_phiid, 0, IPC_RMID, 0);
semctl(sem_mutexid, 0, IPC_RMID, 0);
perror("shmat faild!");
exit(1);
}
/*-----------------------------------------------*/
int i, phinum;
pid_t pid;
for(i=0; i<5; i++){
while((pid = fork()) == -1);
if(!pid){
phinum = i;
signal(SIGINT, SIG_DFL);
break;
}
}
if(pid>0){
while(wait((int *)0) == -1);
semctl(sem_phiid, 0, IPC_RMID, 0);
semctl(sem_mutexid, 0, IPC_RMID, 0);
shmdt(state);
printf("Hi, GAME OVER!");
}
else
philosopher(phinum, state, sem_phiid, sem_mutexid, P, V); }
六、程序运行结果
截图一
截图二
截图三
七、设计总结
这次课程设计通过利用UNIX系统的信号量机制和共享内存机制，编写一个解决哲学家进餐问题的程序，感觉有很多收获，主要体现在以下几点：
（1）很好的复习了UNIX系统编程课上所学的知识，尤其是对unix进程通信机制中信号量机制和共享内存机制有了实践和更深的认识。
（2）练习了C编程，尤其是对函数指针有了更深的认识。
（3）复习了操作系统进程通信的原理。
实验一 一、实验名称：哲学家就餐问题的实现 二、实验学时：2 三、实验内容和目的： 实验目的：实现哲学家就餐问题，要求不能出现死锁。通过本实验熟悉Linux系统的基本环境，了解Linux下进程和线程的实现。 实验内容：在Unix系统下实现教材2.4.2节中所描述的哲学家就餐问题。要求显示出每个哲学家的工作状态，如吃饭，思考。连续运行30次以上都未出现死锁现象。 四、实验原理： 由Dijkstra提出并解决的哲学家进餐问题(The Dinning Philosophers Problem)是典型的同步问题。该问题是描述有五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐完毕，放下筷子继续思考。 五、实验器材（设备、元器件） （1）学生每人一台PC，安装WindowsXP/2000操作系统。 （2）局域网络环境。 （3）个人PC安装VMware虚拟机和Ubuntu系统。 六、实验内容：
（一）熟悉Ubuntu系统下的多线程编程。 （二）实现哲学家就餐问题 1. 算法思想 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子，而偶数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都生竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。 2. 流程图
3. 程序代码（重要代码请注释） #include
第3章部分习题答案 3.2. 为什么进程在进入临界区之前，应先执行"进入区"代码，在退出临界区后又执行"退出区"代码? 为了实现多个进程对临界资源的互斥访问，必须在临界区前面增加一段用于检查欲访问的临界资源是否正被访问的代码，如果未被访问，该进程便可进入临界区对资源进行访问，并设置正被访问标志，如果正被访问，则本进程不能进入临界区，实现这一功能的代码成为"进入区"代码；在退出临界区后，必须执行"退出区"代码，用于恢复未被访问标志. 3.3 同步机构应遵循哪些基本准则?为什么? a. 空闲让进. b. 忙则等待. c. 有限等待. d. 让权等待. 3.6你认为整型信号量机制和记录型信号量机制，是否完全遵循了同步机构的四条准则? a. 在整型信号量机制中，未遵循"让权等待"的准则. b. 记录型信号量机制完全遵循了同步机构的"空闲让进,忙则等待,有限等待,让权等待"四条准则. 3.9在生产者－消费者问题中，如果缺少了signal(full)或signal(empty),对执行结果会有何影响? 生产者－消费者问题可描述如下: var mutex,empty,full: semaphore:=1,n,0; buffer: array[0,...,n-1] of item; in,out: integer:=0,0; begin parbegin producer: begin repeat . . produce an item in nextp; . . wait(empty); wait(mutex); buffer(in):=nextp; in:=(in+1) mod n; signal(mutex); /* ************** */ signal(full); /* ************** */ until false; end consumer: begin repeat wait(full); wait(mutex); nextc:=buffer(out); out:=(out+1) mod n; signal(mutex); /* ************** */
#include 第1章习题及解答略 第2&6章习题及解答 1.判断正误 (1)凡频谱是离散的信号必然是周期信号。( ×)准周期信号 (2)任何周期信号都由频率不同，但成整倍数比的离散的谐波叠加而成。( ×) (3)周期信号的频谱是离散的，非周期信号的频谱也是离散的。( ×) (4)周期单位脉冲序列的频谱仍为周期单位脉冲序列。( √) (5)非周期变化的信号就是随机信号。( ×)准周期信号 (6)非周期信号的幅值谱表示的是其幅值谱密度与时间的函数关系。( ×) (7)信号在时域上波形有所变化，必然引起频谱的相应变化。( ×) (8)各态历经随机过程是平稳随机过程。( √) (9)平稳随机过程的时间平均统计特征等于该过程的集合平均统计特征。( √) (10)非周期信号的频谱都是连续的。( ×) 准周期信号 (11)单位脉冲信号的频谱是无限带宽谱（√） (12)直流信号的频谱是冲击谱（√） 2.选择正确答案填空 (1)描述周期信号的数学工具是(B )。 A.相关函数 B. 傅里叶级数 C. 拉普拉斯变换 D. 傅里叶变换 (2)描述非周期信号的数学工具是( C)。 A.三角函数 B. 拉普拉斯变换 C. 傅里叶变换 D. 傅里叶级数 (3) 将时域信号进行时移，则频域信号将会( D ) A.扩展 B. 压缩 C. 不变 D. 仅有相移 (4) 瞬变信号的傅里叶变换的模的平方的意义为( C ) A.信号的一个频率分量的能量 B. 在f 处的微笑频宽内，频率分量的能量与频宽之比 C. 在f 处单位频宽中所具有的功率 (5) 概率密度函数是在（C ）域，相关函数是在（A ）域，功率谱密度函数是 在（ D ）域描述随机信号。 A.时间 B. 空间 C. 幅值 D. 频率 (6) 白噪声信号的自相关函数是（C ） A.相关函数 B. 奇函数 C. 偶函数 D. 不存在 6.4已知被测模拟量最大输出幅值为±5V ，要求AD 转换输出最大误差不大于5mv ，应选用多少位的AD 转换器？ 解：量化误差5mv=±0.5LSB=125*5.012* 5.0-±=-±n n V FS 解得n=9 6.6 模拟信号DFT ，请问采样时间间隔Δt 、采样点数N 、频率分辨率Δf 三者之间的关系？并回答如下问题： (1) 为什么采样频率Δf 必须至少为被分析信号中最高频率成分的2倍才能避免混淆？ (2) 当采样频率确定后，频谱中应该出现的最高频率是多少？ (3) 频谱中的谱线根数是否与时域中的采样点数相同？对于频谱分析来说有用的谱线根数是多少？ 计算机操作系统典型例题解析之三 【例1】分配到必要的资源并获得处理机时的进程状态是（B ）。A、就绪状态B、执行状态 C、阻塞状态D、新状态 分析：进程有三种基本状态：就绪状态、执行状态和阻塞状态。当进程已分配到除CPU以外的所有必要的资源后，只要能再获得处理机便可立即执行，这时的状态称为就绪状态；处于就绪状态的进程如果获得了处理机，其状态转换为执行状态；进程因发生某种事件（如I/O请求、申请缓冲空间等）而暂停执行时的状态，亦即进程的执行受到阻塞，故称这种状态为阻塞状态；而新状态是指创建了进程但尚未把它插入到就绪队列前的状态。所以本题的答案是B。 【例2】挂起的进程被激活，应该使用（C）原语。 A、Create B、Suspend C、Active D、Wakeup 分析：在不少系统中，进程除了三种基本状态外，又增加了一些新的状态，其中最重要的是挂起状态。“挂起”的实质是使进程不能继续执行，即使挂起后的进程处于就绪状态，它也不能参加对CPU的竞争，进程的挂起调用Suspend（）原语。因此，被挂起的进程处于静止状态，相反，没有挂起的进程则处于活动状态。而且，处于静止状态的进程，只有通过“激活”动作，调用Active（）原语，才能转换成活动状态，调入内存。所以本题的答案是C。 【例3】任何时刻总是让具有最高优先数的进程占用处理器，此时采用的进程调度算法是（D）。A非抢占式的优先数调度算法B、时间片轮转调度算法C、先来先服务调度算法D、抢占式的优先 数调度算法 分析：“让具有最高优先数的进程占用处理器”，我们可以知道，采用的进程调度算法是优先数调度算法，但是我们还要进一步分析是抢占式的还是非抢占式的。“任何时刻总让”，通过这句话我们知道采用的是抢占式的，所以本题的答案是D。 【例4】若P、V操作的信号量S初值为2，当前值为－1，则表示有（B）等待进程。A、0个B、1个C、2个D、3个分析：信号量的初始值表示系统中资源的数目，每次的Wait操作意味着进程请求一个单位的资源，信号量进行减1的操作，当信号量小于0时，表示资源已分配完毕，进程自我阻塞。因此，如果信号量小于0，那么信号量的绝对值就代表当前阻塞进程的个数。所以本题的答案是B。 【例5】发生死锁的必要条件有四个，要预防死锁的发生，可以破坏这四个必要条件，但破坏（A）条件是不太实际的。 A、互斥 B、请求和保 C、不剥夺 D、环路等待 分析：预防死锁是指通过破坏死锁的某个必要条件来防止死锁的发生。四个必要条件中，后三个条件都可以被破坏，而第一个条件，即“互斥”条件，对某些像打印机这样的设备，可通过SPOOLing技术予以破坏，但其他资源，因受它们的固有特性的限制，该条件不仅不能被破坏，反而应加以保证。所以本题的答案是A。 【例6】有m个进程共享同一临界资源，若使用信号量机制实现对临界资源的互斥访问，则信号量值的变化范围是1 至1－m。 操作系统 实验报告 实验名称：哲学家就餐问题 班级：信卓1201班 姓名：钟远维 学号：U201213500 日期：2014年10月30日 一、实验目的 1、熟练使用VC6.0编译环境，调试并正确运行程序。 2、理解哲学家就餐问题中出现的问题，进而掌握死锁的必要条件。 3、理解源程序中产生和防止死锁的算法，及相关窗口操作。 4、熟悉哲学家就餐问题流程并写出其伪代码 二、实验内容 有五个哲学家围坐在一圆桌旁（如图1），桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子。每个哲学家的行为是思考，感到饥饿，然后吃通心粉。为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子。 图1 图2 三、实验要求 1、程序需有防止死锁发生采取的措施； 2、程序要有产生死锁的分配方式； 四、实验算法实现 1、不发生死锁的方式 由源码gChopstickState[iLeftChopstick] = iPhilosopher; gChopstickState[iRightChopstick] = iPhilosopher; 知基本思路是要么一下子占用两支筷子要么不占用，先确定两只筷子均没被占用才获取筷子，这样就打破了死锁的必要条件。 伪代码如下; var mutexleftchopstick,mutexrightchopstick; beging: resting; waiting; p(mutexleftchopstick); //先改变左手筷子信号量 p(mutexrightchopstick); //马上改变右手筷子信号量 GetResource(leftchopstick,rightchopstick); //同时占用左右手筷子 eating; v(mutexleftchopstick); //释放资源 v(mutexrightchopstick); end 2、发生死锁的方式 基本思路是有筷子即占用，看似效率很高，但因为资源有限，且不可抢占，很容易发生死锁。 源码理解: gDinerState[iPhilosopher] = WAITING; //wants chopsticks result = WaitForSingleObject(gchopStick[iLeftChopstick], INFINITE); gChopstickState[iLeftChopstick] = iPhilosopher; //得到左手筷子 Sleep(P_DELAY/4); //休眠状态 gDinerState[iPhilosopher] = WAITING; //继续等待另一只手筷子 result = WaitForSingleObject(gchopStick[iRightChopstick], INFINITE); gChopstickState[iRightChopstick] = iPhilosopher; //直到等到右手筷子 伪码书写： var mutexleftchopstick,mutexrightchopstick; beging: 操作系统哲学家问题实验报告 实验报告三 实验名称:一、调试验证“有限缓冲”经典同步问题 二、利用Java同步解决“哲学家进餐”问题 日期：2015-11-5 班级：13级计科学号: 姓名： 一、实验目的 1.了解信号量的使用 2.掌握正确使用同步机制的方法 3.实现生产者消费者进程的互斥与同步 4.实现java同步解决“哲学家进餐”问题 二、实验内容 1.调试验证“有限缓冲”经典同步问题 2.利用Java同步解决“哲学家进餐”问题 三、项目要求与分析 1.“有限缓冲”经典同步问题 （1）问题描述 有一群生产者进程在生产产品，此产品提供给消费者去消费。为使生产者和消 费者进程能并发执行，在它们之间设置一 个具有n个缓冲池，生产者进程可将它所 生产的产品放入一个缓冲池中，消费者进 程可从一个缓冲区取得一个产品消费。 （2）问题分析 设两个同步信号量:一个说明空缓冲区的数目，用empty表示，初值为有界缓 冲区的大小N，另一个说明已用缓冲区的 数目，用full表示，初值为0。由于在 执行生产活动和消费活动中要对有界缓 冲区进行操作。有界缓冲区是一个临界资 源，必须互斥使用，所以另外还需要设置 一个互斥信号量mutex，其初值为1。2.“哲学家进餐”问题 （1）问题描述 假如所有的哲学家都同时拿起左侧筷子，看到右侧筷子不可用，又都放下左 侧筷子，等一会儿，又同时拿起左侧筷子，如此这般，永远重复。对于这种情况，即 所有的程序都在无限制地运行，但是都无 法得到任何进展，即出现饿死，所有的哲 学家都吃不上饭。 规定在拿起左侧的筷子后，先检查右面的筷子是否可用。如果不可用，则放下左 侧的筷子，等一段时间后再重复整个过 程。 （2）问题分析 当出现以下情形，在某一瞬间，所有的哲学家都同时启用这个算法，拿起左侧 课程设计报告书 课程名称：计算机操作系统 题目：用多线程同步方法解决哲学家就餐问题系名： 专业班级： 姓名： 学号： 指导教师: 2016 年 6 月 24 日 武汉华夏理工学院信息工程系 课程设计任务书 课程名称：操作系统原理课程设计指导教师： 班级名称：开课系、教研室：自动化与计算机 一、课程设计目的与任务 操作系统课程设计是《操作系统原理》课程的后续实践课程，旨在通过一周的实践训练，加深学生对理论课程中操作系统概念，原理和方法的理解，加强学生综合运用操作系统原理、Linux系统、C语言程序设计技术进行实际问题处理的能力，进一步提高学生进行分析问题 和解决问题的能力，包含系统分析、系统设计、系统实现和系统测试的能力。 学生将在指导老师的指导下，完成从需求分析，系统设计，编码到测试的全过程。 二、课程设计的内容与基本要求 1、课程设计题目 用多线程同步方法解决哲学家就餐问题 2、课程设计内容 本课程设计要求在Linux操作系统，GCC编译环境下开发。 用c/c++语言在Linux操作系统环境下，通过研究Linux的线程机制和信号量实现哲学家就餐问题的并发控制。为避免死锁，可采用只许4个哲学家入席且桌上有5支筷子的办法。几把椅子可用连续存储单元。 1 每个哲学家取得一双筷子开始用餐后，即时显示“Dining…”和该哲学家的标识符以 及餐桌上有几位哲学家及其所坐的位置。 2 设定共有10个哲学家需用餐。每位用餐耗时10秒钟以上。 3 多个哲学家须共享操作函数代码。 提示: 1 有界缓冲区/连续存储区可用数组实现。 2 编译命令可用： gcc -lpthread -o 目标文件名源文件名 3 多线程编程方法参见电子文档。 3、设计报告撰写格式要求： 1设计题目与要求 2 设计思想 3系统结构 4 数据结构的说明和模块的算法流程图 5 使用说明书（即用户手册）：内容包含如何登录、退出、读、写等操作说明 6 运行结果和结果分析（其中包括实验的检查结果、程序的运行情况） 7 自我评价与总结 8 附录：程序清单，注意加注释（包括关键字、方法、变量等），在每个模块前加注释； 哲学家进餐问题代码(JAVA) (2010-10-12 15:24:12) 转载 标签： 分类：Java it 问题描述： 一个哲学家围坐在一张圆桌周围，每个哲学家面前都有一碟通心面。由于面条很滑，所以 要两把叉子才能夹住。相邻两个碟子之间有一把叉子。 哲学家的生活包括两种活动：即吃饭和思考。当一个哲学家觉得饿时，他就试图分两次去 取他左边和右边的叉子，每次拿一把，但不分次序。如果成功地获得了两把叉子，他就开 始吃饭，吃完以后放下叉子继续思考。 问题是： 为每一个哲学家写一段程序描述其行为。要求不能死锁。 class kuai{ String name; boolean Enable = true; public kuai(String name) { https://www.doczj.com/doc/ba11116039.html, = name; } public synchronized void pickup() { this.Enable =false; } public synchronized void putdown() { this.Enable =true; this.notifyAll(); } } class Philosopher extends Thread { String name; kuai left; kuai right; public Philosopher(String name, kuai l, kuai r) { https://www.doczj.com/doc/ba11116039.html, = name; left = l; right = r; } public void run() { if(left.Enable) { left.pickup(); } else { while(!left.Enable) { 试用用信号量机制描述两人下象棋的过程。 两人下象棋的过程可以概括为：一开始只能是“红先黑后”，以后两人要循环轮流走子，直至某一方获胜或双方和棋为 止。? 这是个只有一个生产者和一个消费者的生产者——消费者问题，是个典型的“你等我，我也等你”的问题。红方是总的前趋任务——生产者进程，黑方是总的后继任务——消费者进程，但由于下棋过程必须轮流走子，所以红黑双方的生产者消费者身份会轮流改变。棋盘则是生产者与消费者共享的缓冲。?要求：只描述对弈过程，对棋盘的访问不做描述。二人对弈过程是个纯粹的同步过程 ①所用信号量设臵如下： Ⅰ）同步信号量hei，初值为1，表示黑方已走子,开始时可使红方先行不受阻。 Ⅱ）同步信号量hong，初值为0，表示红方尚未走子，开始时可使黑方先行受阻。 用信号量机制描述的二人下象棋过程如下 有一个阅览室，共有100个座位，读者进入时必须先在一张登记表上登记，该表为每一座位列一表目，包括座号和读者姓名等，读者离开时要消掉登记的信息，试问： （1）为描述读者的动作，应编写几个程序，设臵几个进程？（2）试用P、V操作描述读者进程之间的同步关系。分析：?读者的动作都是一样的：登记进入阅览室，阅读， 撤消登记离开阅览室，因此可写一个程序，设n个进程。 ?读者共享的资源有阅览室的座位和登记表，因此诸 个读者进程之间有两种互斥制约关系，需设2个信号量来实现：? seat：用于实现诸读者对阅览室的空闲座位的互斥 竞争，初值为100； ? mutex：用于实现诸读者对登记表的互斥访问，初值 为1 (1)可写一个程序，设n个进程 (2)读者进程readeri(i=1,2,3,……)描述如下： P（seat）; /*申请空座位*/ P（mutex）; /*申请登记*/ 登记； V（mutex） /*允许其他读者登记*/ 阅读； P（mutex）; /*申请撤消登记*/ 撤消登记； V（mutex）; /*允许其他读者撤消登记*/ V（seat）; /*释放座位，允许他人进入*/ 南昌大学实验报告 学生姓名：倪焕学号：8000114018 专业班级：软件工程141班 实验类型：■验证□综合□设计□创新实验日期：2016.5.24 实验成绩： 一、实验项目名称 哲学家就餐问题 二、实验目的 利用PV操作解决哲学家就餐问题 三、软硬件环境 软件：Visual Studio2010 硬件：PC机一台 四、实验内容结果 //哲学家就餐问题的解法 #include 操作系统实习 报告 一、设计目的： 死锁是进程并发执行过程中可能出现的现象，所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局。哲学家就餐问题是描述死锁的经典例子。为了防止死锁，可以采用资源预分配法或者资源按序分配法。资源预分配法是指进程在运行前一次性地向系统申请它所需要的全部资源，如果系统当前不能够满足进程的全部资源请求，则不分配资源, 此进程暂不投入运行，如果系统当前能够满足进程的全部资源请求, 则一次性地将所申请的资源全部分配给申请进程。 二、设计内容 哲学家进餐问题的模拟。 三、开发环境 windows环境，Myeclipse平台。 四、分析设计 ＜一＞实验原理 哲学家进餐问题描述的是五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五只碗和五只筷子。他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右的最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐完毕放下筷子继续思考。 由于：①只有拿到两只筷子时，哲学家才能吃饭；②如果筷子已经在他人手上，则该哲学家必须等到他人吃完之后才能拿到筷子；③任何一个哲学家在自己 没有拿到两只筷子吃饭之前，决不放下自己手中的筷子。则可能出现五个哲学家都饥饿时都拿着一直筷子。这样就可能五个哲学家都用不上餐。 该问题可用记录型信号量解决，经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用，为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量组成信号量数组。当哲学家饥饿时总是先拿其左边的筷子，成功后，再去拿右边的筷子，又成功后方可就餐。进餐完，又先放下他左边的筷子，再放下右边筷子。这个算法可以保证不会有两个相邻的哲学家同时就餐，但有可能引起死锁。 对于死锁问题可采取这样的几种解决方法： (1)至多只允许四个哲学家同时进餐，以保证至少有一个哲学家可以进餐，最终总会释放出他所用过的两只筷子，从而可使更多的哲学家进餐； (2)仅当左右两只筷子均可用时，才允许哲学家拿起筷子就餐 (3)规定奇数号哲学家先拿起右边筷子，然后再去拿左边筷子，而偶数号哲学家则相反。 (4)把筷子顺序编号0, 1, 2, 3, 4，给每个哲学家分配筷子时，必须依从小号到大号（或者相反顺序）进行。 在本次实习里采用第二种方法解决该问题。 ＜二＞数据及程序结构 总共创建有四个类：哲学家进餐问题类，Philosopher类，ChopstickArray 类，Chopstick类。 Chopstick类来表示筷子，其中包括的布尔型成员变量available来表示该筷子是否可用，成员方法setnum()获取其编号；boolean型成员方法isAvailable()返回其当前available的值。setAvailable(boolean available)这一成员方法是对筷子的available的值进行设置，即设置筷子是否可用。 ChopstickArray类用其中的数组chopsticks[i]来存放五只筷子，并通过哲学家的编号及筷子的编号确定该筷子属于当前哲学家的左右哪边的筷子。 Philosopher类，用来描述哲学家，通过实现Runnable接口的方式来创建线程对象，该类中的方法thinking()，eating()来描述哲学家的状态。通过使用关键词synchronized来给共享资源即Philosopher对象上锁，当一个线问程访问Philosopher中的Thinking()时锁定Philosopher对象，这时其他线程就无法访问其另一个方法eating()，即说明哲学家不能同时处于思考和吃饭的状态中。 public synchronized void thinking() { if(state) /* 如果在思考,说明这个哲学家两边的筷子没用 */ { chopstickArray.getnum(num).setAvailable(true); chopstickArray.getLast(num).setAvailable(true); /*这时哲学家两边的筷子只为可用*/ 潍坊学院计算机工程学院 课程设计说明书 课程名称：____操作系统课程设计_________________设计项目：____哲学家就餐问题____________________学生姓名：_____XXXXXX _________________________学号：____ ___________________专业：______计算机科学与技术________________班级：______一班___________________________指导教师：_______ ___________________________ _2016年__3___月 一、任务与具体要求 哲学家有N个，规定全体到齐后开始讨论，在讨论的间隙哲学家进餐，每人进餐时都需使用刀、叉合一把，所有哲学家刀和叉都拿到后才能进餐。哲学家的人数、餐桌上的布置自行设定，实现刀和叉的互斥使用算法的程序实现。 二、设计说明书包括的内容 1.需求分析 2.系统概要设计 3.系统详细设计 4.系统的主要源代码 5.系统测试及调试 6.总结 7.主要参考文献 三、应完成的图纸 四、评语及成绩 指导教师（签字）_____________ ________年____月____日目录 一、需求分析 __________________________________________________________ 1 二、系统概要设计 ______________________________________________________ 2 三、系统详细设计 ______________________________________________________ 3 四、系统的主要源代码 __________________________________________________ 4 五、系统测试及调试 ____________________________________________________ 9 六、总结 _____________________________________________________________ 13 七、主要参考文献 _____________________________________________________ 13 6. 算法题（共32个题目） 200348. 在信号量机制中，若P（S）操作是可中断的，则会有什么问题？ 此题答案为：答： P（S）的操作如下： Begin S.Value:= S.Value-1; ① If S.Value<0 Then ② Begin Insert(*,S.L); Block(*) ③ End End. 若P（S）可中断的，例如进程A在执行了语句①之后从CPU上退 下了，假定此时S.Value＝0；这时换另一进程B，B又将S.Value 的值减1使之为－1，在执行语句③时，B被阻塞；然后又换回A执行，由于A的"断点"是语句①之后，当它执行语句②时，由于这时S.Value已经是－1，故进程继续执行而被阻塞。这就出现了错误： 本来A操作P（S）操作后，S.Value＝0，是不应该被阻塞的，现在却被阻塞了。 200350. 何谓临界区？下面给出的两个进程互斥的算法是安全的吗？为什么？ ＃define true; # define false; Int flag[2]; flag[1]=flag[2]=false; enter-crtsec(i) int i; { While(flag[1-i]) flag[i]=true; } feave-crtsec(i) Int i; { flag[i]=false; } process I; … Enter-crtsec(i); In critical section; Leave-crtsec(i); 此题答案为：答：一次仅允许一个进程使用的资源称为临界资源，在进程中对临界资源访问的程序段称为临界区。 从概念上讲，系统中各进程在逻辑上是独立的，它们可以按各自的速度向前推进。但由于它们共享某些临界资源，因而产生了临界区问题。对于具有临界区问题的并发进程，它们之间必须互斥，以保证不会同时进入临界区。 这种算法不是安全的。因为，在进入临界区的enter-crtsec（）不是一个原语操作，如果两个进程同时执行完其循环（此前两个flag均为false），则这两个进程可同时进入临界区。 200353. 某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题： （1）用P、V操作管理这些并发进程时，应怎样定义信号量？写出信号量的初值以及信号量各种取值的含义。 （2）根据所定义的信号量，把应执行的P、V操作填入下述程序中，以保证进程能够正确地并发执行。 Cobegin PROCESS Pi(i=1,2,…) Begin 进入售票厅； 购票； 退出； End; 实践15 哲学家进餐问题 1.实践内容说明 （1）在函数中使用图形方式显示哲学家进餐问题,每个哲学家使用一个线程控制,随机进行进餐或者思考,使用互斥量与事件进行同步与互斥控制。 2.程序性质 （1）Windows 与控制台混合应用程序 （2）多线程 3.运行环境设置 (1)建立项目在Visual C++ 6、0 开发环境,单击New 菜单,弹出New 对话框; 在New 对话框中选择Project 标签切换至Project 标签页; 在Project 标签页得项目列表中选择Win32 Application 选项,Location 输入框输入项目所在得路径,或者单击输入框右侧得按钮,在弹出得Choose Directory 对话框中选择项目所在得磁盘分区与所在得目录;在Project 标签页得Project name 输入框中输入项目名称; Project 标签页中得其她选项保持默认选择(单选框Create new workspace 前有黑点, Platforms 选项框中Win32 前打勾),完成设置界面如图10 所示。 图10 设置项目为Windows 应用 完成设置后单击OK,New 对话框关闭,弹出Win32 Console Application –Step 1 of 1 对话框。在Win32 Console Application –Step 1 of 1 对话框中选择An empty project 单选项。Win32 Console Application –Step 1 of 1 对话框如图11 所示。 图11 说明刚建立得项目为空项目 完成Win32 Console Application –Step 1 of 1 对话框后单击Finish 按钮,Win32 Console Application –Step 1 of 1 对话框关闭,弹出New Project Information 对话框。New Project Information 对话框中显示了当前建立项目得一些信息。New Project Information 对话框如图12 所示。 图12 显示新项目信息 单击New Project Information 对话框中得OK 按钮,关闭New Project Information 对话框, 项目建立步骤完成。 (2)建立文件单击File 菜单中得New 菜单项,弹出New 对话框。在New 对话框中单击Files 标签,切换至Files 标签页; 在Files 标签页得文件列表中选择C++ Source File 选项,在File 输入框中输入文件名。New 对话框设置如图13 所示。 实验一哲学家就餐问题 一、实验目的 1.熟练使用VC++6.0编译环境，调试并正确运行程序。 2.熟悉哲学家就餐问题流程。 3.理解哲学家就餐问题中出现的问题，进而掌握死锁的必要条件。 4.熟悉源程序中产生和防止死锁的算法，及其相关窗口操作。 二、实验原理 1.问题描述： 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每 两人之间放一只筷子，每个哲学家的行为时思考，饥饿，然后吃通心粉，每个哲学 家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边取筷子。 2.防止死锁发生的分配方式： 仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子。这样要么一次占有两 只筷子（所有线程需要的资源）进行下一步吃通心粉，然后释放所有的资源；要么 不占用资源，这样就不可能产生死锁了。 3.产生死锁的分配方式： 当筷子（资源）可用时，先分配左边的筷子，等待一会后再分配右边的筷子，由于 这个过程中，左边的筷子一直没有释放，就可能产生死锁了。 4.程序运行说明： 程序运行过程中会弹出一个MessageBox提示操作者操作： 1）第一个对话框用于选择运行模式 a．选择yes表示采用的是运行的防止死锁的方式，这样的话整个程序可以一直运行下去，不会产生死锁。 b．选择no表示运行产生死锁的方式会弹出第二个对话框。 2）第二个对话框用于选择运行时，线程运行的时间 a．选择yes线程时间比较短，很快就可以死锁。 b．选择no线程时间跟选择yes时的时间差不多，产生死锁的时间稍微长一点。 三、实验过程及分析 1.PhilosopherThread(LPVOID pVoid)函数伪代码 1）不死锁方式 Var mutexleftchopstick,mutexrightchopstick; Beging: Resting; Waiting; P{mutexleftchopstick}; P{mutexrightchopstick}; GetResource{leftchopstick,rightchopstick}; Eating; V{mutexleftchopstick}; 第三章进程管理练习题 一、选择题 1．如果信号量S的值是0，此时进程A执行P（S）操作，那么，进程A会（）。 A．继续运行 B．进入阻塞态，让出CPU C．进入就绪态，让出CPU D．继续运行，并唤醒S队列头上的等待进程 2. 正在运行的进程在信号量S上操作P操作之后，当S<0，进程将进入信号量的（）。 A.等待队列 B.提交队列 C.后备队列 D.就绪队列 3．在非剥夺调度方式下，运行进程执行V原语后，其状态（）。 A.不变 B.要变 C.可能要变 D.可能不变 4. 一个进程被唤醒，意味着（）。 A.改进程重新占有了CPU B.进程状态变为就绪 C.它的优先权变为最大 D.其PCB移至就绪队列的队首 5.. 系统感知进程的唯一实体是（）。 A.JCB B.FCB C.PCB D.SJT 6. 一进程在某一时刻具有（）。 A.一种状态 B.二种状态 C.三种状态 D.四种状态 7. 进程从运行状态变为等待的原因可能是（）。 A.输入/输出事件发生 B.时间片到 C.输入/输出事件完成 D.某个进程被唤醒 8. 进程创建原语的任务是（）。 A.为进程编制程序 B.为进程建立PCB表 C.为进程分配CPU D.为进程分配所需的各种资源 9. 进程被创建后即进入（）排队。 A.阻塞队列 B.就绪队列 C.缓冲队列 D.运行队列 10．在操作系统中，进程是一个具有一定独立功能的程序在某个数据集上的一次。 A)等待活动 B)运行活动 C)单独操作 D)关联操作 11．下面对进程的描述中，错误的是。 A)进程是动态的概念 B)进程执行需要处理机 C)进程是有生命期的 D)进程是指令的集合 /*inux进程的实现:哲学家就餐问题在 linux 上的程序实现 设有5个哲学家,共享一张放油把椅子的桌子,每人分得一吧椅子.但是桌子上总共只有5支筷子,在每个人两边分开各放一支.哲学家只有在肚子饥饿时才试图分两次从两边拾起筷子就餐. 就餐条件是: 1)哲学家想吃饭时,先提出吃饭的要求; 2)提出吃饭要求,并拿到2支筷子后,方可吃饭; 3)如果筷子已被他人获得,则必须等待该人吃完饭之后才能获取该筷子; 4)任一哲学家在自己未拿到2支筷子吃饭之前,决不放下手中的筷子; 5)刚开始就餐时,只允许2个哲学家请求吃饭. 试问: 1)描述一个保证不会出现两个邻座同时要求吃饭的算法; 2)描述一个既没有两邻座同时吃饭,又没有人饿死的算法; 3)在什么情况下,5个哲学家全都吃不上饭? 哲学家进餐问题是典型的同步问题.它是由Dijkstra提出并解决的.该问题是描述有五个哲学家,他们的生活方式是交替地进行思考和进餐.哲学家们共用一张圆桌,分别坐在周围的五张椅子上.在圆桌上有五个碗和五支筷子,平时一个哲学家进行思考,饥饿时便试图取用其左右岁靠近他的筷子,只有在他拿到两支筷子时才能进餐.进餐完毕,放下筷子继续思考. */ #include 机制习题解答(DOC)
计算机操作系统典型例题解析之三
哲学家就餐问题报告
操作系统哲学家问题
用多线程同步方法解决哲学家就餐问题报告
哲学家进餐问题代码
信号量互斥题目
哲学家就餐问题实验报告
操作系统哲学家进餐问题
操作系统课程设计-哲学家进餐问题
计算机操作系统算法题(最全)
实践 哲学家进餐问题
实验一 哲学家就餐问题
操作系统练习题三四五章
哲学家就餐问题
相关主题
文本预览