HIT oslab之实验6 信号量的实现和应用

ゝ一纸荒年。 2022-11-13 13:26 201阅读 0赞

# 一、实验内容 #

1.在Ubuntu中编写程序，用信号量解决生产者–消费者问题；  
2.在Linux-0.11中实现信号量，用生产者—消费者程序检验之。

# 二、编写应用程序`pc.c`，解决经典的生产者—消费者问题 #

1.要求

*  建立一个生产者进程，N 个消费者进程（N>1）；
 *  用文件A建立一个共享缓冲区；
 *  生产者进程依次向缓冲区写入整数 0,1,2,…,M，M>=500；
 *  消费者进程从缓冲区读数，每次读一个，并将读出的数字从缓冲区删除，然后将本进程 ID 和 + 数字重定向输出到文件B；
 *  缓冲区同时最多只能保存 10 个数。

> 将读出的数字从缓冲区删除，涉及到数字的移动，比较繁琐，偏离了主题–信号量的实现和应用；我采用**记录读写位置的方式**实现，详见下述源码。

2.pc.c的源码及注释

#define __LIBRARY__ //使用了_syscalln
    
    #include <stdio.h>  //使用了printf()
    #include <sem.h> //信号量的头文件
    /* open(),write(),fsync(),lseek()*/
    #include <sys/types.h>
    #include <sys/stat.h>
    #include <fcntl.h>
    #include <unistd.h>
    
    _syscall2(sem_t*,sem_open,const char*,name,unsigned int,value);
    _syscall1(int,sem_wait,sem_t*,sem);
    _syscall1(int,sem_post,sem_t*,sem);
    _syscall1(int,sem_unlink,const char*,name);
    
    #define name_size 32 //信号量名字长度的最大值
    #define BUFSIZE 10 //缓冲区大小
    #define CONSUMER_NUM 4 //消费者进程数
    #define MAX_NUM 500 //为了测试方便，item_num最大为500
    
    sem_t *empty, *full, *mutex;
    
    //目前的读位置，父进程把第1个消费者进程的read_place置为0;
    int read_place;
    int fd_rp; //打开读位置文件的返回值, 将read_place写入文件，以让消费者进程们共享。
    
    int fd;  //打开文件的返回值，返回0表示成功。
    
    void producer() {
        
    	//目前的写位置
    	int write_place = 0;
    
    	//生产一个产品 item；
    	int item_num = 0;
    
    	while(item_num <= MAX_NUM) {
        
    		//test是否有空闲的缓存资源
    		sem_wait(empty);            // P(Empty);
    
    		//通过互斥信号量，实现互斥访问
    		sem_wait(mutex);           //   P(Mutex);
    
    		//将item放到空闲缓存中
    		lseek(fd, write_place, SEEK_SET);
    		write(fd, &item_num, sizeof(int));
    		write_place = lseek(fd, 0, SEEK_CUR);
    		//fsync(fd); //将fd所指的文件数据，由系统缓冲区写回磁盘，以确保数据同步,linux-0.11不支持
    		sync();
    		item_num++;
    		
    		sem_post(mutex);            //V(Mutex);
    
    		//增加产品资源
    		sem_post(full);             //V(Full);
    	}	
    }
    
    void consumer() {
        
    	int item_num;
    	do{
        
    		//test是否有产品资源
    	    sem_wait(full);               //P(Full);
    
    		//互斥访问
    	    sem_wait(mutex);                 //P(Mutex);
    		
    		/* 从文件读取当前的读位置*/
    		lseek(fd_rp, 0, SEEK_SET);
    		read(fd_rp, &read_place, sizeof(int));
    
    		/* 如果有消费者进程读到了MAX_NUM，那么之后的消费者进程就没必要读了*/
    		if(read_place == -1) {
        
    			sem_post(mutex);
    			break;
    		}
    		
    		//从缓冲区取出1个产品赋值给item；并未实现将item从缓冲区删除
    		lseek(fd, read_place, SEEK_SET);
    		read(fd, &item_num, sizeof(int));
    		
    		read_place = item_num == MAX_NUM ? -1 : lseek(fd, 0, SEEK_CUR);
    		
    		/* 接下来的读位置保存到文件中 */
    		lseek(fd_rp, 0, SEEK_SET);
    		write(fd_rp, &read_place, sizeof(int));
    		sync();
    		
    		//在屏幕输出item
    		printf("%d: %d\n", gedpid(), item_num);
    		fflush(stdout);
    		
    		sem_post(mutex);                  //V(Mutex);
    
    		//增加空闲的缓存资源
    		sem_post(empty);                   //V(Empty);
    				
    	}while(item_num < MAX_NUM);
    	
    	/*
    	**1.第1个消费者，因为item_num == MAX_NUM而退出循环，
    	**此时full = 0, 所以其他消费者会阻塞在sem_wait(full);中
    	**2.所以需要消费者通过sem_post(full);将其他消费者唤醒，并通过break;退出循环
    	*/
    	sem_post(full);
    }
    
    int main() {
        
    
    	/* 确保每个信号量有不同的名字；*/
    	char empty_name[name_size];
    	char full_name[name_size];
    	char mutex_name[name_size];
    
    	int i;
    
    	/* linux-0.11不支持snprintf
    	snprintf(empty_name, name_size, "/%ld_empty", (long)getpid());
    	snprintf(full_name, name_size, "/%ld_full", (long)getpid());
    	snprintf(mutex_name, name_size, "/%ld_mutex", (long)getpid());
    	*/
    	
    	sprintf(empty_name, "/%ld_empty", (long)getpid());    
        sprintf(full_name, "/%ld_full", (long)getpid());
        sprintf(mutex_name, "/%ld_mutex", (long)getpid());
    	
    	/* 创建信号量 */
    	empty = sem_open(empty_name, BUFSIZE);
    	full = sem_open(full_name, 0);
    	mutex = sem_open(mutex_name, 1);
    
    	//打开一个文件作为共享缓冲区
    	fd = open("share.file", O_CREAT | O_RDWR, 0666); //0666是一个八进制数
    
    	/* 生产者进程 */
    	if(!fork()) {
        
    		producer();
    		exit(0);
    	}
    	
    	//打开一个文件记录读位置
    	fd_rp = open("read_place.txt", O_CREAT | O_RDWR, 0666);
    
    	/* 消费者进程 */
    	//int i;  不允许在这个地方定义；
    	for(i = 0; i < CONSUMER_NUM; i++) {
        
    		if(i = 0) {
        
    			read_place = 0;
    			lseek(fd_rp, 0, SEEK_SET);
    			write(fd_rp, &read_place, sizeof(int));
    		}
    		if(!fork()) {
        
    			consumer();
    			exit(0);
    		}
    	}
    	
    	//父进程等待所有子进程结束
    	while(wait(NULL) != -1);
    	
    	/* 释放任何信号量相关的资源 */
    	sem_unlink(empty_name);
    	sem_unlink(full_name);
    	sem_unlink(mutex_name);
    
    	//关闭打开的文件
    	close(fd);
    	close(fd_rp);
    	return 0;	
    }

3.Linux-0.11上的pc.c

#define __LIBRARY__
    
    #include <stdio.h>
    #include <sem.h>
    #include <sys/types.h>
    #include <sys/stat.h>
    #include <fcntl.h>
    #include <unistd.h>
    
    _syscall2(sem_t*,sem_open,const char*,name,unsigned int,value);
    _syscall1(int,sem_wait,sem_t*,sem);
    _syscall1(int,sem_post,sem_t*,sem);
    _syscall1(int,sem_unlink,const char*,name);
    
    #define name_size 32
    #define BUFSIZE 10
    #define CONSUMER_NUM 4
    #define MAX_NUM 500
    
    sem_t *empty, *full, *mutex;
    
    int read_place;
    int fd_rp;
    
    int fd; 
    
    void producer() {
        
    	int write_place = 0;
    
    	int item_num = 0;
    
    	while(item_num <= MAX_NUM) {
        
    		
    		sem_wait(empty);           
    
    		sem_wait(mutex);          
    
    		lseek(fd, write_place, SEEK_SET);
    		write(fd, &item_num, sizeof(int));
    		write_place = lseek(fd, 0, SEEK_CUR); 
    		sync(); 
    		item_num++;
    		sem_post(mutex); 
    
    		sem_post(full); 
    		
    	}	
    }
    
    void consumer() {
        
    	int item_num;
    	
    	do{
        
    		
    	    	sem_wait(full); 
    
    	    	sem_wait(mutex); 
    	    			
    		lseek(fd_rp, 0, SEEK_SET);
    		read(fd_rp, &read_place, sizeof(int));
    		
    		if(read_place == -1) {
        
    			sem_post(mutex);
    			break;
    		}
    
    		lseek(fd, read_place, SEEK_SET); 
    		read(fd, &item_num, sizeof(int));
    
    		read_place = item_num == MAX_NUM ? -1 : lseek(fd, 0, SEEK_CUR);
    		lseek(fd_rp, 0, SEEK_SET);
    		write(fd_rp, &read_place, sizeof(int));
    		sync();
    
    		printf("%d: %d\n", getpid(), item_num);
    		fflush(stdout);
    
    		sem_post(mutex); 
    
    		sem_post(empty);
    		
    	}while(item_num < MAX_NUM);
    	
    	sem_post(full);
    }
    
    int main() {
        
    
    	char empty_name[name_size];
    	char full_name[name_size];
    	char mutex_name[name_size];
    	
    	int i;
    
    	sprintf(empty_name, "/%ld_empty", (long)getpid());    
        	sprintf(full_name, "/%ld_full", (long)getpid());
        	sprintf(mutex_name, "/%ld_mutex", (long)getpid());
    
    	empty = sem_open(empty_name, BUFSIZE);
    	full = sem_open(full_name, 0);
    	mutex = sem_open(mutex_name, 1);
    
    	fd = open("share.file", O_CREAT | O_RDWR, 0666); 
    
    	if(!fork()) {
        
    		producer();
    		exit(0);
    	}
    	
    	fd_rp = open("read_place.txt", O_CREAT | O_RDWR, 0666);
    	
    	for(i = 0; i < CONSUMER_NUM; i++) {
        
    		if(i == 0) {
        
    			read_place = 0;
    			lseek(fd_rp, 0, SEEK_SET);
    			write(fd_rp, &read_place, sizeof(int));
    		}
    		if(!fork()) {
        
    			consumer();
    			exit(0);
    		}
    	}
    	
    	while(wait(NULL) != -1);
    	
    	sem_unlink(empty_name);
    	sem_unlink(full_name);
    	sem_unlink(mutex_name);
    
    	close(fd);
    	close(fd_rp);
    	return 0;	
    }

> ①`注意`：有中文注释会导致编译时报奇怪的错。  
> ②对`0666`的解释  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70]

# 三、在Linux-0.11实现信号量 #

1.在`/kernel/sem.c`(先新建sem.c)中实现如下系统调用函数

sem_t *sys_sem_open(const char *name, unsigned int value);
    int sys_sem_wait(sem_t *sem);
    int sys_sem_post(sem_t *sem);
    int sys_sem_unlink(const char *name);

> POSIX信号量有两种形式：命名的和未命名的。本次实验采用的是**命名信号量**。

2.准备工作  
(1)在`include/sem.h`中定义sem\_t等结构体

#ifndef _SEM_H_
    #define _SEM_H_
    
    #include <linux/sched.h> //用到了task_struct
    
    /* 定义因某种信号量而阻塞的队列 */
    #define QUE_LEN 16
    struct semaphore_queue {
        
    	int front;
    	int rear;
    	struct task_struct *wait_tasks[QUE_LEN]; //信号量表征资源的使用情况，进程因缺少资源而阻塞，挂在该信号量的等待队列上；
    };
    typedef struct semaphore_queue sem_queue;
    
    /* 定义sem_t */
    struct semaphore_t {
        
    	int value;  //信号量的值
    	int occupied; //是否被使用了
    	char name[32];   //信号量的名字
    	struct semaphore_queue wait_queue;
    };
    
    typedef struct semaphore_t sem_t;
    
    #endif

> 该头文件也要传到linux-0.11的include目录中。

(2)实现`三、1.`中的4个系统调用函数  
①[流程见“二、2.”][2.]  
②`kernel/sem.c`的源码及注释

//#include <unistd.h> //包括了sem_t的定义等
    #include <sem.h> //sem_t的定义的等
    #include <linux/sched.h> //使用了schedule函数
    #include <linux/kernel.h> //使用了printk函数
    #include <asm/system.h> //cli(), sti(), 实现原子操作
    #include <asm/segment.h> //使用了get_fs_byte函数
    
    #define NAME_SIZE 32
    
    /* 信号量本质就是一种结构体，所以要消耗内存资源，故是有限的 */
    //用数组来管理
    #define SEM_COUNT 32
    sem_t semaphores[SEM_COUNT];
    
    /* 判断某信号量的等待队列是否已满 */
    //循环队列：空1个位置，以判断队满
    int is_full(sem_queue *q) {
        
    	if((q->rear+1) % QUE_LEN == q->front) 
    		return 1; //1表示满了
    	else return 0;
    }
    
    /* 进程被阻塞，挂到某个信号量的等待队列中；*/
    int insert_task(struct task_struct *p, sem_queue *q) {
        
    	if(is_full(q)) {
        
    		printk("Queue is full!\n");
    		return -1; //插入失败
    	}
    	else {
        
    		//入队操作
    		q->wait_tasks[q->rear] = p;
    		q->rear = (q->rear + 1) % QUE_LEN;
    		return 1;  //插入成功
    	}
    }
    
    /* 判断某信号量的等待队列是否为空 */
    int is_empty(sem_queue *q) {
        
    	return q->rear == q->front ? 1 : 0; //1表示为空
    }
    
    
    /* 获得循环队列的第1个任务 */
    struct task_struct *get_task(sem_queue *q) {
        
    	if(is_empty(q)) {
        
    		printk("Queue is empty!\n");
    		return NULL;
    	}
    	else {
        
    		struct task_struct *tmp = q->wait_tasks[q->front];
    		q->front = (q->front + 1) % QUE_LEN;
    		return tmp;
    	}
    }
    
    /* 判断信号量是否已经打开了 */
    //信号量的名字是唯一的，所以根据名字来判断
    int is_sem_opened(const char *name, int name_size) {
        
    	int i;
    	for(i = 0; i < SEM_COUNT; i++) {
        
    			if(semaphores[i].occupied == 1) {
        
    				int j;
    				int flag = 1; //表示名字匹配上了
    				for(j = 0; j < name_size; j++) {
        
    					if(name[j] != semaphores[i].name[j]) {
        
    						flag = 0;
    						break;
    					}
    				}
    				if(flag) return i;
    			}
    	}
    	return -1; //没打开。
    }
    
    /* 初始化信号量的等待队列 */
    void init_queue(sem_queue *q) {
        
    	q->front = q->rear = 0;
    }
    
    /* 打开(申请)信号量资源 */
    sem_t *sys_sem_open(const char *name, unsigned int value) {
        
    	char sem_name[NAME_SIZE];
    	int i;
    	for(i = 0; i < NAME_SIZE; i++) {
        
    		char c = get_fs_byte(name + i);
    		sem_name[i] = c;
    		if(c == '\0') break;
    	}
    	if(i == NAME_SIZE) {
        
    		printk("The name of semaphore is too long!\n");
    		return NULL;
    	}
    	int id;
    	if((id = is_sem_opened(sem_name, i)) != -1) {
        
    		//打开了
    		return &semaphores[id];
    	}
    	/* 没打开，则打开 */
    	int j;
    	for(j = 0; j < SEM_COUNT; j++) {
        
    		if(semaphores[j].occupied == 0) {
        
    			/* 复制名字 */
    			int tmp;
    			for(tmp = 0; tmp <= i; tmp++) {
        
    				semaphores[j].name[tmp] = sem_name[tmp];
    			}
    
    			semaphores[j].occupied = 1;
    			semaphores[j].value = value;
    			
    			//初始化该信号量的等待队列
    			init_queue(&(semaphores[j].wait_queue));
    			return &semaphores[j];
    		}
    	}
    
    	/* 信号量数组已经满了 */
    	printk("Numbers of semaphores are limited!\n");
    	return NULL;
    }
    
    /* 释放信号量资源 */
    int sys_sem_unlink(const char *name) {
        
    	char sem_name[NAME_SIZE];
    	int i;
    	for(i = 0; i < NAME_SIZE; i++) {
        
    		char c = get_fs_byte(name + i);
    		sem_name[i] = c;
    		if(c == '\0') break;
    	}
    	if(i == NAME_SIZE) {
        
    		printk("The name of semaphore is too long!\n");
    		return -1;
    	}
    	
    	/* 判断是否打开了 */
    	int id;
    	if((id = is_sem_opened(sem_name, i)) != -1) {
        
    		//打开了，才释放
    		semaphores[id].occupied = 0;
    		return 0;
    	}
    	return -1;
    }
    
    /* P操作 */
    int sys_sem_wait(sem_t *sem) {
        
    	cli();
    	sem->value--;
    	if(sem->value < 0) {
        
    		current->state = TASK_UNINTERRUPTIBLE;
    		insert_task(current, &(sem->wait_queue));
    		schedule();
    	}
    	sti();
    	return 0;
    }
    
    /* V操作 */
    int sys_sem_post(sem_t *sem) {
        
    	cli();
    	sem->value++;
    	if(sem->value <= 0) {
        
    		struct task_struct *p = get_task(&(sem->wait_queue));
    		if(p != NULL) {
        
    			p->state = TASK_RUNNING;
    		}
    	}
    	sti();
    	return 0;
    }

# 四、验证 #

1.运行结果截图  
![在这里插入图片描述][20210328205333951.png]  
![在这里插入图片描述][2021032820535182.png]

> 我的运行结果还是挺奇怪的，4个消费者进程竟然是轮流输出数字？  
> 和`kernel/sem.c`的实现方式有关

2.实验中遇到的奇怪问题  
(1)share.file  
![在这里插入图片描述][20210328205605473.png]

> 生产者确实输出500就结束运行了，而只有生产者会向share.file写入数字，那么为啥500之后又出现了数字？迫不得已，我只能用-1作为读结束的标志。

(2)实验5 基于内核栈切换的进程切换  
在实验5的基础上进行本次实验，编译会报奇怪的错误。  
说明基于内核栈切换的进程切换存在问题（简单情况没问题，复杂情况大概率有问题）。

# 五、参考资料 #

1.[HIT oslab之实验6，对编写sem.c帮助大][HIT oslab_6_sem.c]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70]: /images/20221022/3eab52d357604334a6147bf6e279ea91.png
[2.]: https://blog.csdn.net/weixin_37477009/article/details/114548301
[20210328205333951.png]: /images/20221022/f67dfcad1d994bf3b9a9f250f9d0db55.png
[2021032820535182.png]: https://img-blog.csdnimg.cn/2021032820535182.png
[20210328205605473.png]: https://img-blog.csdnimg.cn/20210328205605473.png
[HIT oslab_6_sem.c]: https://github.com/hoverwinter/HIT-OSLab/blob/master/lab4/pc.c