用P、V操作写出一个不会出现死锁的哲学家进餐问题

用P、V操作写出一个不会出现死锁的哲学家进餐问题,第1张

哲学家就餐问题是一种典型的同步问题,它是由Dijkstra 提出并解决的。该问题描述

:有五个哲学家,他们的生活方式是交替的进行思考和进餐。哲学家们共用一张圆桌,

查看图片

设五个哲学家分别编号为A,B,C,D,E,桌子上放着五把筷子,筷子分别编号为 0,1,

2,3,4,桌子中央有一盘饭菜。五个哲学家都很有礼貌,都要等同时拿到身旁的两只筷子

才进餐,不然就只是等着继续思考,而且吃了一口之后又马上放下拿起的两根筷子,继续思

考。

用P V原语的方式实现

每个哲学家可用一个线程来模拟,信号量及其P、V操作的实现

定义一个semaphore 类 封装 P V原语模拟函数

(不妨设有6个哲学家,6只筷子, 每只筷子各对应一个信号量且每个信号量初始值应为1)/***********************semaphore.h*****************************

Semaphore类用于模拟信号量

用法如:Semaphore sem(1)

(1)要求初始信号量值非负

(2)信号量P操作: sem.P()

(3)信号量V操作: sem.V()

#ifndef SEMAPHORE_H

#define SEMAPHORE_H

#include <windows.h>

class Semaphore{

protected:

HANDLE sem

public:

//Semaphore()

//void SetValve(int SemValue)

Semaphore(unsigned int SemValue)

virtual ~Semaphore()

void P()

void V()

#endif

/*****************************semaphore.cpp************************************/

#include <windows.h>

#include <LIMITS.H>

#include <assert.h>

#include "semaphore.h"

Semaphore::Semaphore(unsigned int semValue){

if(semValue >LONG_MAX)

semValue = LONG_MAX

sem = CreateSemaphore(NULL,semValue,LONG_MAX,NULL)

Semaphore::~Semaphore(){

CloseHandle(sem)

void Semaphore::P(){

DWORD dw = WaitForSingleObject(sem, INFINITE)

assert(dw == WAIT_OBJECT_0)

void Semaphore::V(){

ReleaseSemaphore(sem,1,NULL)

/*****************************thread.h*************************************

通过startThread开启线程

startThread(PTHREAD_START func,void * param)

用法:

//定义一个PTHREAD_START类型的函数func

unsigned int WINAPI func (void * param){

//启动一个线程使其执行func函数

startThread(func,NULL)

#ifndef THREAD_H

#define THREAD_H

#include <windows.h>

#include <process.h>

from MSDN :

Start address of a routine that begins execution of a new thread.

For _beginthread, the calling convention is either __cdecl or __clrcall

for _beginthreadex, it is either __stdcall or __clrcall.

WINAPI即为__stdcall

typedef unsigned int (WINAPI *PTHREAD_START) (void *)

chBEGINTHREADEX is From <Windows Via C &C++>

#define chBEGINTHREADEX(psa, cbStackSize, pfnStartAddr, \

pvParam, dwCreateFlags, pdwThreadId) \

((HANDLE)_beginthreadex( \

(void *)(psa), \

(unsigned) (cbStackSize), \

(PTHREAD_START) (pfnStartAddr),\

(void *)(pvParam), \

(unsigned) (dwCreateFlags), \

(unsigned *)(pdwThreadId)))

// rename chBEGINTHREADEX to startThread for simplicity

#define startThread(pfnStartAddr,pvParam)\

chBEGINTHREADEX(NULL, 0, (pfnStartAddr),(pvParam), 0, NULL)

#endif

/*****************************main函数(主函数)************************************/

假设偶数号哲学家先拿左边的筷子,右边的哲学家先拿起右边的筷子。

#include <windows.h>

#include "semaphore.h"

#include "thread.h"

#include <iostream.h>

#include <stdio.h>

#define N 6//哲学家的个数

#define LEFT(i)(i+N-1)%N//左边的筷子

#define RIGHT(i) (i==N-1)?0:(i+N)%N //右边的筷子 编号为N的哲学家的右边的筷子编号为0

/*******************************初始化信号量**************************************/

Semaphore ChopStick[N]={Semaphore(1),Semaphore(1),Semaphore(1),Semaphore(1),Semaphore(1),Semaphore(1)}

/*******************************哲学家状态*******************************************/

void Eating(int Ph_Id)

printf("Philosopher%d: \tI'm eating......\t",(int)Ph_Id)

void Sleeping(int Ph_Id)

printf("Philosopher%d:\tI'm sleeping......\t",(int)Ph_Id)

Sleep(rand()%10000)

void Thinking(int Ph_Id)

printf("Philosopher%d: \tI'm thinking......\t",(int)Ph_Id)

if (pid%2 == 0) //偶数号哲学家

Thinking(pid) //等待中

ChopStick[LEFT(pid)].P() //先拿起左边的筷子,再拿起右边的筷子

ChopStick[RIGHT(pid)].P()

Eating(pid) //获得的两个信号量则eating

ChopStick[LEFT(pid)].V() //先后释放左右信号量

ChopStick[RIGHT(pid)].V()

printf("\n")

else if(pid%2==1 ) //奇数号哲学家

Thinking(pid)

ChopStick[RIGHT(pid)].P() //先拿起右边的筷子,再拿起左边的筷子

ChopStick[LEFT(pid)].P()

Eating(pid) //左右都得到筷子后则eating

ChopStick[RIGHT(pid)].V() //先后释放右左信号量

ChopStick[LEFT(pid)].V()

printf("\n")

Sleeping(pid) //吃完睡上一会儿

int main(){

HANDLE hPhilosopher[N] //为每个哲学家分配一个线程

int count =0

for (int Philosopher_id =0 Philosopher_id<NPhilosopher_id++) //开启线程

hPhilosopher[Philosopher_id] = startThread(Philosopher,Philosopher_id)

if(count>5)

break

::WaitForMultipleObjects(N,hPhilosopher,TRUE,INFINITE)

for (Philosopher_id = 0 Philosopher_id<NPhilosopher_id++)

CloseHandle(hPhilosopher[Philosopher_id])

一、简介

共享内存为在多个进程之间共享和传递数据提供了一种有效的方式。

但它本身并未提供同步机制。

在实际编程中,可以使用

信号量,

传递消息(使用管道或IPC消息),

生成信号,

条件变量,

等方法来提供读写之间的有效的同步机制。

本例程序使用信号量进行同步,

主要是因为它方便,使用广泛,且独立于进程。

本例程序实现了,

生产者进程:

每次读取YUV输入文件的一帧,

然后将其写到共享内存中。

消费者进程:

每次从共享内存中读到一帧,

处理后,

将其写到输出文件。

两个进程间使用信号量来保证同步处理每一帧。

本例程序很好地示范了共享内存和信号量的机制,

对于实际程序的开发很有意义。

二、生产者进程

common.h

用来设置一些测试用的基本参数。

/*

* \File

* common.h

*/

#ifndef __COMMON_H__

#define __COMMON_H__

#define TEST_FILE "coastguard_cif.yuv"

#define OUTPUT_FILE "coastguard_cif_trsd.yuv"

#define FYUV_WIDTH 352

#define FYUV_HEIGHT 288

#endif

共享内存相关的头文件。

shm_com.h

/*

* \File

* shm_com.h

* \Brief

*/

#ifndef __SHM_COM_H__

#define __SHM_COM_H__

#define SHM_SEED 1001

#define MAX_SHM_SIZE 2048*2048*3

typedef struct shared_use_st

{

int end_flag //用来标记进程间的内存共享是否结束: 0, 未结束; 1, 结束

char shm_sp[MAX_SHM_SIZE]//共享内存的空间

}shared_use_st

#endif

信号量的头文件

semaphore.h

/*

* \File

* semaphore.h

* \Brief

* semaphore operation

*/

#ifndef __SEMAPHORE_H__

#define __SEMAPHORE_H__

#define SEM_SEED 1000

union semun

{

int val

struct semid_ds *buf

unsigned short *array

}

int set_semvalue(int sem_id, int value)

void del_semvalue(int sem_id)

int semaphore_p(int sem_id)

int semaphore_v(int sem_id)

#endif

帧处理的头文件

frame.h

/*

* \File

* frame.h

* \Brief

*

*/

#ifndef __FRAME_H__

#define __FRAME_H__

#include "shm_com.h"

#define PIX_VALUE 1

typedef enum

{

YUV420,

YUV422,

YUV444,

RGB

}frame_type_e

typedef struct

{

int frm_w// width

int frm_h// height

frame_type_e frm_type

int frm_size

char *frm_comps

}frame_t, *frame_p

int init_frame(frame_p frame, int width, int height, frame_type_e type)

int free_frame(frame_p frame)

int read_frame_from_file(frame_p frame, FILE* fp)

int write_frame_into_file(FILE* fp, frame_p frame)

int read_frame_from_shm(frame_p frame, shared_use_st* shm)

int write_frame_into_shm(shared_use_st* shm, frame_p frame)

int crop_frame(frame_p frame, int l_offset, int t_offset, int c_w, int c_h)

#endif

生产者进程的基本流程:

打开输入文件并初始化帧

创建并初始化共享内存和信号量

然后每次读取一帧,

用信号量获取共享内存的权限后,

将读取的帧写入共享内存,

再释放共享内存的权限。

当处理完所有的帧后,

设置结束标志,

并释放相关的资源。

producer.c

/*

* \File

* producer.c

* \Brief

* Test shared-memory and message-queue

*/

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <errno.h>

#include <unistd.h>

#include <sys/shm.h>

#include <sys/sem.h>

#include "common.h"

#include "semaphore.h"

#include "shm_com.h"

#include "frame.h"

int main(char argc, char* argv[])

{

FILE* fp_in = NULL

frame_t frame

int frame_cnt = 0

int sem_id// semaphore id

int shm_id// shared-memory id

void* shared_memory = (void*)0

shared_use_st* shared_stuff

/* Open input file */

if ((fp_in = fopen(TEST_FILE, "rb")) <0 )

{

printf("Open input file failed: %s\n", TEST_FILE)

exit(EXIT_FAILURE)

}

/* Init frame */

init_frame(&frame, FYUV_WIDTH, FYUV_HEIGHT, YUV420)

printf("FRAME: w = %d, h = %d\n", frame.frm_w, frame.frm_h)

/* Create and init semaphore */

sem_id = semget((key_t)SEM_SEED, 1, 0666 | IPC_CREAT)

if (sem_id == -1)

{

fprintf(stderr, "semget failed.\n")

exit(EXIT_FAILURE)

}

/* Init shared-memory */

shm_id = shmget((key_t)SHM_SEED, sizeof(struct shared_use_st), 0666 | IPC_CREAT)

if (shm_id == -1)

{

fprintf(stderr, "shmget failed.\n")

exit(EXIT_FAILURE)

}

shared_memory = shmat(shm_id, (void*)0, 0)

if (shared_memory == (void*)-1)

{

fprintf(stderr, "shmat failed.\n")

exit(EXIT_FAILURE)

}

shared_stuff = (struct shared_use_st*)shared_memory

shared_stuff->end_flag = 0

printf("FRAME_CNT: %d\n", frame_cnt)

set_semvalue(sem_id, 1)

while (read_frame_from_file(&frame, fp_in) == 0)

{

semaphore_p(sem_id)

/* Write it into shared memory */

write_frame_into_shm(shared_stuff, &frame)

shared_stuff->end_flag = 0

semaphore_v(sem_id)

frame_cnt++

printf("FRAME_CNT: %d\n", frame_cnt)

}

semaphore_p(sem_id)

shared_stuff->end_flag = 1

semaphore_v(sem_id)

/* over */

printf("\nProducer over!\n")

fclose(fp_in)

free_frame(&frame)

del_semvalue(sem_id)

if (shmdt(shared_memory) == -1)

{

fprintf(stderr, "shmdt failed.\n")

exit(EXIT_FAILURE)

}

exit(EXIT_SUCCESS)

}

linux中的进程通信分为三个部分:低级通信,管道通信和进程间通信IPC(inter process communication)。linux的低级通信主要用来传递进程的控制信号——文件锁和软中断信号机制。linux的进程间通信IPC有三个部分——①信号量,②共享内存和③消息队列。以下是我编写的linux进程通信的C语言实现代码。操作系统为redhat9.0,编辑器为vi,编译器采用gcc。下面所有实现代码均已经通过测试,运行无误。

一.低级通信--信号通信

signal.c

#include

#include

#include

/*捕捉到信号sig之后,执行预先预定的动作函数*/

void sig_alarm(int sig)

{

printf("---the signal received is %d. /n", sig)

signal(SIGINT, SIG_DFL)//SIGINT终端中断信号,SIG_DFL:恢复默认行为,SIN_IGN:忽略信号

}

int main()

{

signal(SIGINT, sig_alarm)//捕捉终端中断信号

while(1)

{

printf("waiting here!/n")

sleep(1)

}

return 0

}

二.管道通信

pipe.c

#include

#define BUFFER_SIZE 30

int main()

{

int x

int fd[2]

char buf[BUFFER_SIZE]

char s[BUFFER_SIZE]

pipe(fd)//创建管道

while((x=fork())==-1)//创建管道失败时,进入循环

/*进入子进程,子进程向管道中写入一个字符串*/

if(x==0)

{

sprintf(buf,"This is an example of pipe!/n")

write(fd[1],buf,BUFFER_SIZE)

exit(0)

}

/*进入父进程,父进程从管道的另一端读出刚才写入的字符串*/

else

{

wait(0)//等待子进程结束

read(fd[0],s,BUFFER_SIZE)//读出字符串,并将其储存在char s[]中

printf("%s",s)//打印字符串

}

return 0

}

三.进程间通信——IPC

①信号量通信

sem.c

#include

#include

#include

#include types.h>

#include ipc.h>

#include sem.h>

/*联合体变量*/

union semun

{

int val//信号量初始值

struct semid_ds *buf

unsigned short int *array

struct seminfo *__buf

}

/*函数声明,信号量定义*/

static int set_semvalue(void)//设置信号量

static void del_semvalue(void)//删除信号量

static int semaphore_p(void)//执行P操作

static int semaphore_v(void)//执行V操作

static int sem_id//信号量标识符

int main(int argc, char *argv[])

{

int i

int pause_time

char op_char = 'O'

srand((unsigned int)getpid())

sem_id = semget((key_t)1234, 1, 0666 | IPC_CREAT)//创建一个信号量,IPC_CREAT表示创建一个新的信号量

/*如果有参数,设置信号量,修改字符*/

if (argc >1)

{

if (!set_semvalue())

{

fprintf(stderr, "Failed to initialize semaphore/n")

exit(EXIT_FAILURE)

}

op_char = 'X'

sleep(5)

}

for(i = 0i <10i++)

{

/*执行P操作*/

if (!semaphore_p())

exit(EXIT_FAILURE)

printf("%c", op_char)

fflush(stdout)

pause_time = rand() % 3

sleep(pause_time)

printf("%c", op_char)

fflush(stdout)

/*执行V操作*/

if (!semaphore_v())

exit(EXIT_FAILURE)

pause_time = rand() % 2

sleep(pause_time)

}

printf("/n%d - finished/n", getpid())

if (argc >1)

{

sleep(10)

del_semvalue()//删除信号量

}

exit(EXIT_SUCCESS)

}

/*设置信号量*/

static int set_semvalue(void)

{

union semun sem_union

sem_union.val = 1

if (semctl(sem_id, 0, SETVAL, sem_union) == -1)

return(0)

return(1)

}

/*删除信号量*/

static void del_semvalue(void)

{

union semun sem_union

if (semctl(sem_id, 0, IPC_RMID, sem_union) == -1)

fprintf(stderr, "Failed to delete semaphore/n")

}

/*执行P操作*/

static int semaphore_p(void)

{

struct sembuf sem_b

sem_b.sem_num = 0

sem_b.sem_op = -1/* P() */

sem_b.sem_flg = SEM_UNDO

if (semop(sem_id, &sem_b, 1) == -1)

{

fprintf(stderr, "semaphore_p failed/n")

return(0)

}

return(1)

}

/*执行V操作*/

static int semaphore_v(void)

{

struct sembuf sem_b

sem_b.sem_num = 0

sem_b.sem_op = 1/* V() */

sem_b.sem_flg = SEM_UNDO

if (semop(sem_id, &sem_b, 1) == -1)

{

fprintf(stderr, "semaphore_v failed/n")

return(0)

}

return(1)

}

②消息队列通信

send.c

#include

#include

#include

#include

#include

#include types.h>

#include ipc.h>

#include msg.h>

#define MAX_TEXT 512

/*用于消息收发的结构体--my_msg_type:消息类型,some_text:消息正文*/

struct my_msg_st

{

long int my_msg_type

char some_text[MAX_TEXT]

}

int main()

{

int running = 1//程序运行标识符

struct my_msg_st some_data

int msgid//消息队列标识符

char buffer[BUFSIZ]

/*创建与接受者相同的消息队列*/

msgid = msgget((key_t)1234, 0666 | IPC_CREAT)

if (msgid == -1)

{

fprintf(stderr, "msgget failed with error: %d/n", errno)

exit(EXIT_FAILURE)

}

/*向消息队列中发送消息*/

while(running)

{

printf("Enter some text: ")

fgets(buffer, BUFSIZ, stdin)

some_data.my_msg_type = 1

strcpy(some_data.some_text, buffer)

if (msgsnd(msgid, (void *)&some_data, MAX_TEXT, 0) == -1)

{

fprintf(stderr, "msgsnd failed/n")

exit(EXIT_FAILURE)

}

if (strncmp(buffer, "end", 3) == 0)

{

running = 0

}

}

exit(EXIT_SUCCESS)

}

receive.c

#include

#include

#include

#include

#include

#include types.h>

#include ipc.h>

#include msg.h>

/*用于消息收发的结构体--my_msg_type:消息类型,some_text:消息正文*/

struct my_msg_st

{

long int my_msg_type

char some_text[BUFSIZ]

}

int main()

{

int running = 1//程序运行标识符

int msgid//消息队列标识符

struct my_msg_st some_data

long int msg_to_receive = 0//接收消息的类型--0表示msgid队列上的第一个消息

/*创建消息队列*/

msgid = msgget((key_t)1234, 0666 | IPC_CREAT)

if (msgid == -1)

{

fprintf(stderr, "msgget failed with error: %d/n", errno)

exit(EXIT_FAILURE)

}

/*接收消息*/

while(running)

{

if (msgrcv(msgid, (void *)&some_data, BUFSIZ,msg_to_receive, 0) == -1)

{

fprintf(stderr, "msgrcv failed with error: %d/n", errno)

exit(EXIT_FAILURE)

}

printf("You wrote: %s", some_data.some_text)

if (strncmp(some_data.some_text, "end", 3) == 0)

{

running = 0

}

}

/*删除消息队列*/

if (msgctl(msgid, IPC_RMID, 0) == -1)

{

fprintf(stderr, "msgctl(IPC_RMID) failed/n")

exit(EXIT_FAILURE)

}

exit(EXIT_SUCCESS)

}

③共享内存通信

share.h

#define TEXT_SZ 2048 //申请共享内存大小

struct shared_use_st

{

int written_by_you//written_by_you为1时表示有数据写入,为0时表示数据已经被消费者提走

char some_text[TEXT_SZ]

}

producer.c

#include

#include

#include

#include

#include types.h>

#include ipc.h>

#include shm.h>

#include "share.h"

int main()

{

int running = 1//程序运行标志位

void *shared_memory = (void *)0

struct shared_use_st *shared_stuff

char buffer[BUFSIZ]

int shmid//共享内存标识符

/*创建共享内存*/

shmid = shmget((key_t)1234, sizeof(struct shared_use_st), 0666 | IPC_CREAT)

if (shmid == -1)

{

fprintf(stderr, "shmget failed/n")

exit(EXIT_FAILURE)

}

/*将共享内存连接到一个进程的地址空间中*/

shared_memory = shmat(shmid, (void *)0, 0)//指向共享内存第一个字节的指针

if (shared_memory == (void *)-1)

{

fprintf(stderr, "shmat failed/n")

exit(EXIT_FAILURE)

}

printf("Memory attached at %X/n", (int)shared_memory)

shared_stuff = (struct shared_use_st *)shared_memory

/*生产者写入数据*/

while(running)

{

while(shared_stuff->written_by_you == 1)

{

sleep(1)

printf("waiting for client.../n")

}

printf("Enter some text: ")

fgets(buffer, BUFSIZ, stdin)

strncpy(shared_stuff->some_text, buffer, TEXT_SZ)

shared_stuff->written_by_you = 1

if (strncmp(buffer, "end", 3) == 0)

{

running = 0

}

}

/*该函数用来将共享内存从当前进程中分离,仅使得当前进程不再能使用该共享内存*/

if (shmdt(shared_memory) == -1)

{

fprintf(stderr, "shmdt failed/n")

exit(EXIT_FAILURE)

}

printf("producer exit./n")

exit(EXIT_SUCCESS)

}

customer.c

#include

#include

#include

#include

#include types.h>

#include ipc.h>

#include shm.h>

#include "share.h"

int main()

{

int running = 1//程序运行标志位

void *shared_memory = (void *)0

struct shared_use_st *shared_stuff

int shmid//共享内存标识符

srand((unsigned int)getpid())

/*创建共享内存*/

shmid = shmget((key_t)1234, sizeof(struct shared_use_st), 0666 | IPC_CREAT)

if (shmid == -1)

{

fprintf(stderr, "shmget failed/n")

exit(EXIT_FAILURE)

}

/*将共享内存连接到一个进程的地址空间中*/

shared_memory = shmat(shmid, (void *)0, 0)//指向共享内存第一个字节的指针

if (shared_memory == (void *)-1)

{

fprintf(stderr, "shmat failed/n")

exit(EXIT_FAILURE)

}

printf("Memory attached at %X/n", (int)shared_memory)

shared_stuff = (struct shared_use_st *)shared_memory

shared_stuff->written_by_you = 0

/*消费者读取数据*/

while(running)

{

if (shared_stuff->written_by_you)

{

printf("You wrote: %s", shared_stuff->some_text)

sleep( rand() % 4 )

shared_stuff->written_by_you = 0

if (strncmp(shared_stuff->some_text, "end", 3) == 0)

{

running = 0

}

}

}

/*该函数用来将共享内存从当前进程中分离,仅使得当前进程不再能使用该共享内存*/

if (shmdt(shared_memory) == -1)

{

fprintf(stderr, "shmdt failed/n")

exit(EXIT_FAILURE)

}

/*将共享内存删除,所有进程均不能再访问该共享内存*/

if (shmctl(shmid, IPC_RMID, 0) == -1)

{

fprintf(stderr, "shmctl(IPC_RMID) failed/n")

exit(EXIT_FAILURE)

}

exit(EXIT_SUCCESS)

}

摘自:


欢迎分享,转载请注明来源:夏雨云

原文地址:https://www.xiayuyun.com/zonghe/123812.html

(0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
上一篇 2023-03-14
下一篇2023-03-14

发表评论

登录后才能评论

评论列表(0条)

    保存