Experiment 4-Implementation and application of semaphore

Implementation and application of semaphore

Corresponding experiment manual: https://hoverwinter.gitbooks.io/hit-oslab-manual/content/sy4_sem.html

Supplementary knowledge

Semaphore operations

Reference links:

• https://c.biancheng.net/view/8632.html

• https://www.cnblogs.com/Suzkfly/p/14351449.html

• head File:

  #include<fcntl.h>
  #include<sys/stat.h>
  #include<semaphore.h>
  

• Operation function:

  //Open the named semaphore
  sem_t * sem_open(const char * name,
  int oflag,
  mode_t mode,
  unsigned int value);
  //Close the semaphore
  int sem_close(sem_t * sem);
  //Delete semaphore file
  int sem_unlink(const cahr * name);
  //test semaphore
  int sem_wait(sem_t * sem);
  //Semaphore + +
  int sem_post(sem_t * sem);
  

C language file operation under Linux

Reference links:

• https://blog.csdn.net/Mculover666/article/details/104817798

• head File:

  #include <sys/types.h> //Defines some common data types, such as size_t
  #include <fcntl.h> //Defines open, creat and other functions, as well as macro definitions indicating file permissions
  #include <unistd.h> //Definition of read, write, close, lseek and other functions
  #include <errno.h> //Definitions related to the global variable errno
  #include <sys/ioctl.h> //The ioctl function is defined
  

• Operation function:

  //Open file
  int open(const char * path, int flags, mode_t mode)
  //read file
  size_t read(int fd, void * buf, size_t count);
  //Write to file
  size_t write(int fd, const void * buf, sieze_t count);
  //Close file
  int close(int fd);
  

Experimental code and results

Ubuntu uses semaphores to solve the consumer-producer problem

#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<errno.h>
#include<semaphore.h>
#include<fcntl.h>
#include<sys/stat.h>
#include<sys/types.h>
#include<sys/ioctl.h>
#include<sys/wait.h>

#define PRODUCER 1
#define CUSTOMER 5
#defineBUFF_SIZE 10
#define NUMBER 500

sem_t * full, * empty, * mutex;
int fd; //File descriptor

int main()
{<!-- -->
    int i, j, k;
    int data;
    pid_t p; //process descriptor
    int buff_out = 0; //The position read from the buffer
    int buff_in = 0; //The position to read into the buffer
    char file_name[] = {<!-- -->"buffer.txt"};

    //Open the semaphore
    if ((empty = sem_open("sys_empty", O_RDWR | O_CREAT, 0666, BUFF_SIZE )) == SEM_FAILED) {<!-- -->
printf("fail to sem_open the semaphore : empty\
");
return -1;
}
if ((full = sem_open("sys_full", O_RDWR | O_CREAT, 0666, 0)) == SEM_FAILED) {<!-- -->
printf("fail to sem_open the semaphore : full\
");
return -1;
}
if ((mutex = sem_open("sys_mutex", O_RDWR | O_CREAT, 0666, 1)) == SEM_FAILED) {<!-- -->
printf("fail to sem_open the semaphore : mutex\
");
return -1;
}

    //open a file
    fd = open(file_name, O_RDWR | O_CREAT, 0664);
    //Save the reading position buff_out
    lseek(fd, BUFF_SIZE * sizeof(int), SEEK_SET);
    write(fd, (char *) & amp;buff_out, sizeof(int));

    //Producer process
    if ((p = fork()) == 0) {<!-- -->
printf("This is the Producer (pid : %d)\
", getpid());
for (i = 0;i < NUMBER;i + + ) {<!-- -->
sem_wait(empty);
sem_wait(mutex);
//write integer
            printf("producer (pid : %d) write : %d\
", getpid(), i);
            lseek(fd, buff_in * sizeof(int), SEEK_SET);
            write(fd, (char *) & amp;i, sizeof(int));
            buff_in = (buff_in + 1) % BUFF_SIZE;

sem_post(mutex);
sem_post(full);
}
return 0;
}
else if (p < 0) {<!-- -->
printf("Fail to fork the Producer\
");
return -1;
}

    //Consumer process
    for (j = 0;j < CUSTOMER;j + + ) {<!-- -->
if ((p = fork()) == 0) {<!-- -->
            printf("This is the Customer (pid : %d)\
", getpid());
for (k = 0;k < NUMBER / CUSTOMER;k + + ) {<!-- -->
                sem_wait(full);
sem_wait(mutex);
//File operations
//Get the reading position
                lseek(fd, BUFF_SIZE * sizeof(int), SEEK_SET);
                read(fd, (char *) & amp;buff_out, sizeof(int));
                //Read data
                lseek(fd, buff_out * sizeof(int), SEEK_SET);
                read(fd, (char *) & amp;data, sizeof(int));
                printf("customer (pid : %d) read -> %d\
", getpid(), data);
                //Write the reading position
                buff_out = (buff_out + 1) % BUFF_SIZE;
                lseek(fd, BUFF_SIZE * sizeof(int), SEEK_SET);
                write(fd, (char *) & amp;buff_out, sizeof(int));
sem_post(mutex);
sem_post(empty);
            }
return 0;
}
else if (p < 0) {<!-- -->
printf("Fail to fork the Customer (num : %d)\
", i);
return -1;
}
}

    //process waits
wait(NULL);
//Release the semaphore
sem_unlink("sys_empty");
sem_unlink("sys_full");
sem_unlink("sys_mutex");
//Close file
close(fd);

printf("\r the pc.c is finished\
");
return 0;
}

Implementing semaphores in Linux-0.11

In include/unistd.h, add:

...
#define __NR_sem_open 72
#define __NR_sem_wait 73
#define __NR_sem_post 74
#define __NR_sem_unlink 75

#define QUE_LEN 16
#define SEM_FAILED (void*) 0
struct semaphore_queue
{<!-- -->
int front;
int rear;
struct task_struct *wait_tasks[QUE_LEN];
};
typedef struct semaphore_queue sem_queue;

struct semaphore_t
{<!-- -->
    int value;
    int occupied;
    char name[16];
    struct semaphore_queue wait_queue;
};
typedef struct semaphore_t sem_t;
...

In include/linux/sys.h, add:

...
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_sem_open,sys_sem_wait,sys_sem_post,sys_sem_unlink};

In kernel/system_call.s, modify:

nr_system_calls = 76

Create new krenel/sem.c:

#define __LIBRARY__
#include <unistd.h>
#include <linux/sched.h>
#include <linux/kernel.h>
#include <asm/segment.h>
#include <asm/system.h>

#defineSEM_COUNT 32
sem_t semaphores[SEM_COUNT];
/* Queue related operations, rear is always the next position to be written, and front is always the first element of the queue*/
void init_queue(sem_queue* q)
{<!-- -->
    q->front = q->rear = 0;
}

int is_empty(sem_queue* q)
{<!-- -->
return q->front == q->rear?1:0;
}
/*Leave the flag QUE_LEN-1 unused to determine whether it is slow*/
int is_full(sem_queue* q)
{<!-- -->
return (q->rear + 1)%QUE_LEN == q->front?1:0;
}
/*Get the first task at the head of the queue*/
struct task_struct * get_task(sem_queue* q)
{<!-- -->
if(is_empty(q))
{<!-- -->
printk("Queue is empty!\
");
return NULL;
}
struct task_struct *tmp = q->wait_tasks[q->front];
q->front = (q->front + 1)%QUE_LEN;
return tmp;
}
/*Insert the task into the end of the queue*/
int insert_task(struct task_struct *p,sem_queue* q)
{<!-- -->
// printk("Insert %d",p->pid);
if(is_full(q))
{<!-- -->
printk("Queue is full!\
");
return -1;
}
q->wait_tasks[q->rear] = p;
q->rear = (q->rear + 1)%QUE_LEN;
return 1;
}
/*Whether the semaphore has been opened, it is the return position*/
int sem_location(const char* name)
{<!-- -->
    int i;
    for(i = 0;i < SEM_COUNT; i + + )
    {<!-- -->
        if(strcmp(name,semaphores[i].name) == 0 & amp; & amp; semaphores[i].occupied == 1)
        {<!-- -->
            return i;
        }
    }
    return -1;
}
/*Open semaphore*/
sem_t* sys_sem_open(const char* name, unsigned int value)
{<!-- -->
char tmp[16];
char c;
int i;
for( i = 0; i<16; i + + )
{<!-- -->
c = get_fs_byte(name + i);
tmp[i] = c;
if(c =='\0') break;
}
if(c >= 16)
{<!-- -->
printk("Semaphore name is too long!");
return NULL;
}
if((i = sem_location(tmp)) != -1)
{<!-- -->
return &semaphores[i];
}
for(i = 0;i< SEM_COUNT; i + + )
{<!-- -->
if(!semaphores[i].occupied)
{<!-- -->
strcpy(semaphores[i].name,tmp);
semaphores[i].occupied = 1;
semaphores[i].value = value;
init_queue( & amp;(semaphores[i].wait_queue));
// printk("%d %d %d %s\
",semaphores[i].occupied,i,semaphores[i].value,semaphores[i].name);
// printk("%p\
", & amp;semaphores[i]);
return &semaphores[i];
}
}
printk("Numbers of semaphores are limited!\
");
return NULL;
}
/*P atomic operations*/
int sys_sem_wait(sem_t* sem)
{<!-- -->
cli();
sem->value--;
if(sem->value < 0)
{<!-- -->
/*See sleep_on*/
current->state = TASK_UNINTERRUPTIBLE;
insert_task(current, & amp;(sem->wait_queue));
schedule();
}
sti();
return 0;
}
/*V atomic operations*/
int sys_sem_post(sem_t* sem)
{<!-- -->
cli();
struct task_struct *p;
sem->value + + ;
if(sem->value <= 0)
{<!-- -->
p = get_task( & amp;(sem->wait_queue));
if(p != NULL)
{<!-- -->
(*p).state = TASK_RUNNING;
}
}
sti();
return 0;
}
/*Release semaphore*/
int sys_sem_unlink(const char *name)
{<!-- -->
    char tmp[16];
    char c;
int i;
for( i = 0; i<16; i + + )
{<!-- -->
c = get_fs_byte(name + i);
tmp[i] = c;
if(c =='\0') break;
}
if(c >= 16)
{<!-- -->
printk("Semphore name is too long!");
return -1;
}
    int ret = sem_location(tmp);
    if(ret != -1)
    {<!-- -->
    semaphores[ret].value = 0;
    strcpy(semaphores[ret].name,"\0");
    semaphores[ret].occupied = 0;
    return 0;
    }
    return -1;
}

Use semaphores to solve the producer-consumer problem in Linux-0.11

Write test program pc.c:

#define __LIBRARY__
#include <unistd.h>
#include <sys/types.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.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 NUMBER 520 /*Type the total number*/
#define CHILD 5 /*Number of consumer processes*/
#define BUFSIZE 10 /*buffer size*/

sem_t *empty, *full, *mutex;
int fno; /*file descriptor*/

int main()
{<!-- -->
    int i,j,k;
    int data;
    pid_t p;
    int buf_out = 0; /*Read position from buffer*/
    int buf_in = 0; /*Write buffer location*/
    /*Open semaphore*/
    if((mutex = sem_open("carmutex",1)) == SEM_FAILED)
    {<!-- -->
        perror("sem_open() error!\
");
        return -1;
    }
    if((empty = sem_open("carempty",10)) == SEM_FAILED)
    {<!-- -->
        perror("sem_open() error!\
");
        return -1;
    }
    if((full = sem_open("carfull",0)) == SEM_FAILED)
    {<!-- -->
        perror("sem_open() error!\
");
        return -1;
    }
    fno = open("buffer.dat",O_CREAT|O_RDWR|O_TRUNC,0666);
    /* Store the position to be read in the buffer to facilitate communication between child processes */
    lseek(fno,10*sizeof(int),SEEK_SET);
    write(fno,(char *) & amp;buf_out,sizeof(int));
    /*Producer process*/
    if((p=fork())==0)
    {<!-- -->
        for( i = 0 ; i < NUMBER; i + + )
        {<!-- -->
            sem_wait(empty);
            sem_wait(mutex);
            /*Write a character*/
            lseek(fno, buf_in*sizeof(int), SEEK_SET);
            write(fno,(char *) & amp;i,sizeof(int));
            buf_in = (buf_in + 1)% BUFSIZE;
            printf("producer (pid : %d) write -> %d\
", getpid(), i);

            sem_post(mutex);
            sem_post(full);
        }
        return 0;
    }else if(p < 0)
    {<!-- -->
        perror("Fail to fork!\
");
        return -1;
    }

    for( j = 0; j < CHILD ; j + + )
    {<!-- -->
        if((p=fork())==0)
        {<!-- -->
            for( k = 0; k < NUMBER/CHILD; k + + )
            {<!-- -->
                sem_wait(full);
                sem_wait(mutex);
                /*Get the reading position*/
                lseek(fno,10*sizeof(int),SEEK_SET);
                read(fno,(char *) & amp;buf_out,sizeof(int));
                /*Read data*/
                lseek(fno,buf_out*sizeof(int),SEEK_SET);
                read(fno,(char *) & amp;data,sizeof(int));
                /*Write the read position*/
                buf_out = (buf_out + 1) % BUFSIZE;
                lseek(fno,10*sizeof(int),SEEK_SET);
                write(fno,(char *) & amp;buf_out,sizeof(int));
                printf("customer (pid : %d) read -> %d\
", getpid(), data);
                fflush(stdout);

                sem_post(mutex);
                sem_post(empty);
            }
           return 0;
        }else if(p<0)
        {<!-- -->
            perror("Fail to fork!\
");
            return -1;
        }
    }
    wait(NULL);
    /*Release semaphore*/
    sem_unlink("carfull");
    sem_unlink("carempty");
    sem_unlink("carmutex");
    /*Release resources*/
    close(fno);
printf("\
THE PROCESS DONE!\
");
    return 0;
}