Experimental environment: Implementation and application of semaphores
Experimental Tasks:
- Write programs under Ubuntu to solve producer-consumer problems with semaphores;
- Implement semaphores in linux-0.11 and test them with a producer-consumer program.
Solving producer-consumer problems with semaphores
Experimentation requirements: pc.c program needs to open a file buffer.txt as a shared buffer, buffer can only save up to 10 numbers at the same time; create a producer process and N consumer processes, where producer processes write consecutive integers to the buffer, 0, 1, 2,..., M, M>=500; The consumer process reads numbers from the buffer one at a time, deletes the read numbers from the buffer, and then outputs the process ID and numbers to standard output.
- Why do we need a semaphore?
- For producers, when the buffer is full, that is, when the number of free buffers is zero, the producer cannot continue to write to the buffer at this time, and must wait until there are consumers taking the number from the full buffer and there are free buffers again before the producer can write to the buffer.
- For consumers, when the buffer is empty, no number can be removed at this time. Consumers must wait until a producer writes a number to the buffer before consumers can take the number.And if more than one consumer wants to take the number from the buffer when the buffer is empty, they all need to wait. At this time, they need to record the number of consumers waiting so that when all the buffers are available, they can wake up all the waiting consumers to ensure that the number of consumers requesting the number is finally available.
- That is, when multiple processes need to work together, they need to use some information to determine if the current process needs to stop and wait, while other processes need to use this information to determine if a process is waiting, or if several processes are waiting to decide whether they need to wake up the waiting process.And this information is the semaphore.
- What does a semaphore do?
An integer variable SEM is set as a semaphore.The buffer is empty at this time, sem=0.Note the distinction between sem_wait and sem_post
- Consumer C1 requests are counted from buffer, cannot be fetched, sleep waiting.Sem=-1<0, indicating that a process is waiting for a lack of resources.
- Consumer C2 also requests a number from the buffer, which is still not available, and sleeps waiting.Sem=-2<0, which means two processes are waiting due to lack of resources.
- Producer P writes a number to the buffer, sem=sem+1=-1<=0, and wakes the head process C1 of the waiting queue, C1 is ready, C2 is still sleeping.
- Producer P continues to write a number to the buffer, sem=0<=0, and wakes up C2, C1, C2 are ready.
Thus, by judging the value of SEM and changing the value of sem, the rational and orderly progress of multi-process cooperation is guaranteed, which is the role of semaphores.
-
Semaphore implementation producer-consumer model ideas:
-
This program cycles through the first 10 digits of the read-write buffer. After the producer writes the number at position 10, he returns to the first position to continue writing. After the consumer reads the number at position 10, he returns to the first position.Use the method of redundancy of 10 to control the reading and writing position.
-
Read and write operations on buffers allow only one process and are protected using a mutex with a signal value of 1, or mutex.
-
Limiting the maximum number of buffers saved requires two semaphores to control together: empty as the buffer's remaining space resource, full as the buffer's used resource, and read-write of the file and the consumer's entire "consumption" process is an atomic operation that can't be interrupted, so use two semaphores to limit.
-
Semaphore correlation function
-
The function of sem_open() is to create a semaphore or to open an existing semaphore.If failed, the return value is NULL
Name is the name of the semaphore.Different processes can share the same semaphore by providing the same name.
Value is the initial value of a semaphore, which is valid only when a new semaphore is created, and is ignored in the rest of the case.
sem_t *sem_open(const char *name, int oflag,mode_t mode, unsigned int value);
-
sem_wait() is the P-atom operation of a semaphore.A return of 0 indicates success, and a return of -1 indicates failure.
If the value of the semaphore is greater than 0, the function returns immediately and executes down by subtracting one. If the semaphore is currently zero, the call will block or be subtracted until the semaphore becomes available to block the process.
int sem_wait(sem_t *sem);
-
sem_post() is the V-atom operation of a semaphore.If there is a process waiting for the sem, it will wake up one of them.A return of 0 indicates success, and a return of -1 indicates failure.
The sem_post function adds a "1" to the semaphore value, which is an unlock operation; it is an atomic operation.
int sem_post(sem_t *sem);
-
The function of sem_unlink() is to delete a semaphore named name.A return of 0 indicates success, and a return of -1 indicates failure.
int sem_unlink(const char *name);
-
The lseek() function changes the file offset of a file, and all open files have a current file offset that indicates the number of bytes from the beginning of the file to the current location of the file.Successfully returned a new offset, but failed to return -1.
SEEK_SET adds offset displacements after pointing the read and write positions to the file header.
SEEK_CUR adds offset displacements backwards in the current read-write position.
SEEK_END adds offset displacements after pointing the read and write positions to the end of the file.off_t lseek(int filedes, off_t offset, int whence);
Create a hollow file with lseek
- A hollow file is a section of the file that is empty.
- The middle of a normal file cannot be empty. write a file by moving the file pointer from the front to the back and writing it in turn.
- Skip a section backwards with lseek to form a hollow file.
- Hollow files are useful for multithreaded working together on files.When you need to create a large file, it takes a long time to create it one after the other from scratch, splitting the file into segments, with multiple threads operating each thread responsible for writing one segment.
ret = lseek(fd, 10, SEEK_SET);
-
Semaphore implementation producer consumer model code pc.c:
#include <unistd.h> #include <sys/types.h> #include <stdio.h> #include <stdlib.h> #include <fcntl.h> #include <sys/stat.h> #include <semaphore.h> #include <sys/types.h> #include <sys/wait.h> #define M 530 /*Total number typed*/ #define N 5 /*Number of consumer processes*/ #define BUFSIZE 10 /*Buffer size*/ int main() { sem_t *empty, *full, *mutex;/*3 Semaphores*/ int fd; /*Shared Buffer File Descriptor*/ int i,j,k,child; int data;/*Written data*/ pid_t pid; int buf_out = 0; /*Read location from buffer*/ int buf_in = 0; /*Write Buffer Location*/ /*Open semaphore*/ empty = sem_open("empty", O_CREAT|O_EXCL, 0644, BUFSIZE); /*Remaining resources, initialized to size*/ full = sem_open("full", O_CREAT|O_EXCL, 0644, 0); /*Resource used, initialized to 0*/ mutex = sem_open("mutex", O_CREAT|O_EXCL, 0644, 1); /*Mutex, initialized to 1*/ fd = open("buffer.txt", O_CREAT|O_TRUNC|O_RDWR,0666); lseek(fd,BUFSIZE*sizeof(int),SEEK_SET);/*Refreshed 40-byte buffer to hold 10 numbers*/ write(fd,(char *)&buf_out,sizeof(int));/*Save the read location in a buffer for communication between subprocesses*/ /*Producer Process*/ if((pid=fork())==0) { printf("I'm producer. pid = %d\n", getpid()); /*Cycle a few times as many products as you produce*/ for( i = 0 ; i < M; i++) { /*empty Greater than 0 for production*/ sem_wait(empty); sem_wait(mutex); /*Write a character*/ lseek(fd, buf_in*sizeof(int), SEEK_SET); write(fd,(char *)&i,sizeof(int)); /*Update write buffer position to be between 0-9*/ /*After a production cycle (file buffers can only hold BUFSIZE product numbers)*/ /*Relocate the location pointer of the buffer file to the top of the file.*/ buf_in = (buf_in + 1) % BUFSIZE; sem_post(mutex); sem_post(full);/*Resource++ is already used in the share to wake up consumer threads*/ } printf("producer end.\n"); fflush(stdout);/*Make sure the output is output to standard output immediately.*/ return 0; } else if(pid < 0) { perror("Fail to fork!\n"); return -1; } /*Consumer Process*/ for( j = 0; j < N ; j++ ) { if((pid=fork())==0) { for( k = 0; k < M/N; k++ ) { sem_wait(full);/*Resources already in use in the share -- 0 will block here at first*/ sem_wait(mutex); /*Get Read Location*/ lseek(fd,BUFSIZE*sizeof(int),SEEK_SET); read(fd,(char *)&buf_out,sizeof(int)); /*Read data*/ lseek(fd,buf_out*sizeof(int),SEEK_SET); read(fd,(char *)&data,sizeof(int)); /*Write Read Location*/ buf_out = (buf_out + 1) % BUFSIZE; lseek(fd,BUFSIZE*sizeof(int),SEEK_SET); write(fd,(char *)&buf_out,sizeof(int)); sem_post(mutex); sem_post(empty);/*Remaining resources in shared area++, wake up producer process*/ /*Consumption Resources*/ printf("%d: %d\n",getpid(),data); fflush(stdout); } printf("child-%d: pid = %d end.\n", j, getpid()); return 0; } else if(pid<0) { perror("Fail to fork!\n"); return -1; } } /*Recycle Thread Resources*/ child = N + 1; while(child--) wait(NULL); /*Release semaphore*/ sem_unlink("full"); sem_unlink("empty"); sem_unlink("mutex"); /*Release Resources*/ close(fd); return 0; }
Executed under ubuntu with the following results:
gcc pc.c -o pc -lpthread ./pc > 1.txt cat 1.txt | more
. . . . . . 
Implementing semaphores in linux-0.11
-
Create a new sem.h in the linux-0.11/include/linux directory, defining the semaphore's data structure, including saving the name and value attributes and a queue waiting for the process.
#ifndef _SEM_H #define _SEM_H #include <linux/sched.h> #define SEMTABLE_LEN 20 #define SEM_NAME_LEN 20 typedef struct semaphore { char name[SEM_NAME_LEN]; int value; struct task_struct *queue; } sem_t; extern sem_t semtable[SEMTABLE_LEN]; #endif
-
Create a new sem.c in the linux-0.11/kernel/sem.c directory to implement semaphores
Implementation of sem_open and sem_unlink functions:Because of the first parameter name of sem_open(), the logical address of the address space in which the application resides is passed in. If this address is accessed directly in the kernel, the data in the kernel space is accessed, not the user space.So get_fs_byte() is used to get the user space data.The get_fs_byte() function functions to obtain data in one byte of user space.Similarly, the parameter name of the sem_unlink() function is treated the same way.
The function sem_open() is to create a new semaphore or open an existing semaphore, first copy the parameter string from user space to kernel space, then compare the existing semaphores, and return the semaphore directly if the name is the same, otherwise create a new semaphore.The sem_unlink() function deletes a semaphore named name. To ensure that multiple semaphores of the system work properly in an array of a limited length, when the semaphore is deleted, the elements behind the array move forward to make room.
Implementation of the sem_wait() and sem_post() functions:You can refer to the lock_buffer() and unlock_buffer implementation provided in 6.4 of the experimental building.
The sem_wait() function is a P-atom operation. The function is to reduce the value of the semaphore by one. If the semaphore value is 0, the current process is blocked. The while cycle is used in sem_wait(), which guarantees that other processes are blocked all the time when the semaphore value is less than or equal to zero. The sem_post() function is a V-atom operation. The function is to add the value of the semaphore to one. If there are processes waiting for the semaphore, it is calledWake up one of them.Blocking and waking processes are implemented by the sleep_on() and wake_up() functions in kernel/sched.c, and their parameters are a structure pointer, struct task_struct *, which means that processes sleep or wake on a process PCB structure chain table to which the parameter refers.
The sleep_on() function parameter takes a pointer *p that is the header pointer to the waiting queue. Each time the function is executed, the pointer *tmp points to the original waiting queue and *p points to the current process, which inserts the current process into the header of the waiting queue, then sets the current process to sleep and executes schedule() for scheduling.The wake_up() function wakes up the process pointed to by *p.When a process wakes up, it returns to sleep_on() to continue execution, and it wakes up the process that *tmp points to, that is, the last process waiting for the queue.Execute in turn, and all processes waiting for the queue will be awakened.
The complete sem.c code is as follows:
#include <linux/sem.h> #include <linux/sched.h> #include <unistd.h> #include <asm/segment.h> #include <linux/tty.h> #include <linux/kernel.h> #include <linux/fdreg.h> #include <asm/system.h> #include <asm/io.h> //#include <string.h> sem_t semtable[SEMTABLE_LEN]; int cnt = 0; sem_t *sys_sem_open(const char *name,unsigned int value) { char kernelname[100]; /* It should be big enough */ int isExist = 0; int i=0; int name_cnt=0; while( get_fs_byte(name+name_cnt) != '\0') name_cnt++; if(name_cnt>SEM_NAME_LEN) return NULL; for(i=0;i<name_cnt;i++) /* Copy from user state to kernel state */ kernelname[i]=get_fs_byte(name+i); int name_len = strlen(kernelname); int sem_name_len =0; sem_t *p=NULL; for(i=0;i<cnt;i++) { sem_name_len = strlen(semtable[i].name); if(sem_name_len == name_len) { if( !strcmp(kernelname,semtable[i].name) ) { isExist = 1; break; } } } if(isExist == 1) { p=(sem_t*)(&semtable[i]); //printk("find previous name!\n"); } else { i=0; for(i=0;i<name_len;i++) { semtable[cnt].name[i]=kernelname[i]; } semtable[cnt].value = value; p=(sem_t*)(&semtable[cnt]); //printk("creat name!\n"); cnt++; } return p; } int sys_sem_wait(sem_t *sem) { cli(); while( sem->value <= 0 ) //Blocking all processes less than 0 sleep_on(&(sem->queue)); sem->value--; sti(); return 0; } int sys_sem_post(sem_t *sem) { cli(); sem->value++; if( (sem->value) <= 1) //Blocking less than 0, waking only for 1, guaranteeing waking only one process at a time wake_up(&(sem->queue)); sti(); return 0; } int sys_sem_unlink(const char *name) { char kernelname[100]; /* It should be big enough */ int isExist = 0; int i=0; int name_cnt=0; while( get_fs_byte(name+name_cnt) != '\0') name_cnt++; if(name_cnt>SEM_NAME_LEN) return NULL; for(i=0;i<name_cnt;i++) kernelname[i]=get_fs_byte(name+i); int name_len = strlen(name); int sem_name_len =0; for(i=0;i<cnt;i++) { sem_name_len = strlen(semtable[i].name); if(sem_name_len == name_len) { if( !strcmp(kernelname,semtable[i].name)) { isExist = 1; break; } } } if(isExist == 1) { int tmp=0; for(tmp=i;tmp<=cnt;tmp++) { semtable[tmp]=semtable[tmp+1]; } cnt = cnt-1; return 0; } else return -1; }
-
Modify/include/unistd.h to add the number of new system calls:
#define __NR_setregid 71 /* Add System Call Number */ #define __NR_whoami 72 /* Experiment 2 New */ #define __NR_iam 73 #define __NR_sem_open 74 /* Experimentation 5 New */ #define __NR_sem_wait 75 #define __NR_sem_post 76 #define __NR_sem_unlink 77
-
Modify/kernel/system_call.s to modify the sum and value of the total system call s:
nr_system_calls = 78
-
Modify/include/linux/sys.h to declare new functions
extern int sys_sem_open(); extern int sys_sem_wait(); extern int sys_sem_post(); extern int sys_sem_unlink(); fn_ptr sys_call_table[] = { //...sys_setreuid,sys_setregid,sys_whoami,sys_iam, sys_sem_open,sys_sem_wait,sys_sem_post,sys_sem_unlink };
-
Modify Makefile in linux-0.11/kernel directory
OBJS = sched.o system_call.o traps.o asm.o fork.o \ panic.o printk.o vsprintf.o sys.o exit.o \ signal.o mktime.o who.o sem.o // ... ### Dependencies: sem.s sem.o: sem.c ../include/linux/sem.h ../include/linux/kernel.h \ ../include/unistd.h
-
Recompile the kernel: make all
-
Modify pc.c for linux-0.11 runs:
Be careful:
(1). In the application of linux0.11 system, comments cannot be written//, they must be written/* */
(2) Variables cannot be defined in the middle of a program, for example, if i is to be defined at the beginning of a loop, all variables must be defined uniformly at the beginning.#define __LIBRARY__ #include <unistd.h> #include <sys/types.h> #include <fcntl.h> #include <stdio.h> #include <stdlib.h> #include <linux/sem.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); int main() { ... /*Open semaphore*/ if((mutex = sem_open("mutex",1)) == NULL) { perror("sem_open() error!\n"); return -1; } if((empty = sem_open("empty",10)) == NULL) { perror("sem_open() error!\n"); return -1; } if((full = sem_open("full",0)) == NULL) { perror("sem_open() error!\n"); return -1; } ... }
-
Copy the modified/usr/include/unistd.h and sem.h files and the newly modified pc.c into the linux-0.11 system to test the semaphore implementation.
sudo ./mount-hdc cp ./unistd.h ./hdc/usr/include/ cp ./sem.h ./hdc/usr/include/linux/ cp ./pc.c ./hdc/usr/root/ sudo umount hdc/
-
Launch the newly compiled linux-0.11 kernel and test the semaphore with pc.c
./run gcc -o pc pc.c ./pc > 1.txt sync
-
Close linux-0.11, mount virtual disks, view information output files
sudo ./mount-hdc sudo cp ./hdc/usr/root/1.txt ./ sudo chmod 777 1.txt cat 1.txt | more
. . . . . .
Experimental questions
Remove all semaphore-related code from pc.c. and run the program again. Has the execution changed?Why is that?When the designer of the experiment first wrote a producer-consumer program, he did so:
Producer() { P(Mutex); //mutex //Produce a product item; P(Empty); //Idle Cache Resource //Put the item in the free cache; V(Full); //Product Resources V(Mutex); } Consumer() { P(Mutex); P(Full); //Remove an assignment from the cache to the item; V(Empty); //Consumer product item; V(Mutex); }
Is this possible?If possible, how does it differ from the standard solution in terms of execution?If not, what's wrong with it that makes it impossible?
A:
Remove all the code related to the semaphore, run the program again, the execution effect has changed, and the output number order is completely confused.
Without semaphores, processes cannot work synchronously, and read and write files cannot be guaranteed to be atomic, sequential and abnormal.
The title code provided in the lab building is logically correct and the code that should be analyzed is shown above.
Analysis process:
- Suppose the Producer just finished producing a product and released Mutex, which is 1, when the cache is full and Empty is 0;
- Then the OS executes the scheduling, and if Producer gets the CPU again, it gets Mutex, making Mutex 0, Empty 0 blocked, Producer gives the CPU out and waits for Consumer to execute V(Empty);
- When Consumer gets the CPU, Mutex is still 0, blocking waiting for Producer to execute V(Mutex);
- Both hold resources needed by each other, causing deadlocks.
Reference link:
https://blog.csdn.net/weixin_41761478/article/details/100093113
https://blog.csdn.net/laoshuyudaohou/article/details/103842973
