LAB Semaphore Implementation Details

信号量的实现与应用

1. 实验内容
2. 实验过程
   • 实验结果
   • 实验分析
     1. 从生产者-Consumer problems see process synchronization
        1. 信号量实现进程同步
        2. 靠临界区保护信号量
           1. 竞争条件(Race Condition)
           2. Atomic access to critical section through lock mechanism
     2. 用信号量解决生产者-消费者问题
        1. use file as a shared buffer
        2. File offset synchronization of multiple consumer process readings and read end judgment
     3. 信号量的实现
        1. 信号量的组成
        2. Construction of waiting queue

实验内容

1. 在Ubuntu下编写程序,用信号量解决生产者-消费者问题
   在Ubuntu下编写应用程序pc.c,Solve the classic producer-消费者问题,完成下面的功能：

   • 建立一个生产者进程,N个消费者进程(N > 1)
   • 用文件建立一个共享缓冲区
   • 生产者进程依次向缓冲区写入整数0,1,2,…,M, M >= 500
   • 消费者进程从缓冲区读数,每次读一个,并将读出的数字从缓冲区删除,然后将本进程ID+digital output to stdout
   • 缓冲区同时最多只能保存10个数
     pc.c中将会用到sem_open(),sem_unlink(),sem_wait(),sem_post()Equivalent semaphore related system calls,请查阅相关文档.

2. 在0.11semaphore,用生产者-consumer program test
   Linux在0.11version has not implemented semaphore,LinusI leave this challenging job to you.If a set of copycat versions can be fully complied withPOSIXcanonical semaphore,Undoubtedly a sense of achievement.But time doesn't allow us to do that,So first get a set of abbreviated classesPOSIX信号量,Its prototypes and standards are not exactly the same,And only contains the following system calls：

   sem_t *sem_open(const char *name, unsigned int value);
   int sem_wait(sem_t *sem);
   int sem_post(sem_t *sem);
   int sem_unlink(const char *name);
   

   • sem_tis the semaphore type,Customize according to the needs of the implementation
   • sem_open
     function is to create a semaphore,或打开一个已经存在的信号量.
     nameis the name of the semaphore.Different processes can provide the samename而共享同一个信号量.如果该信号量不存在,就创建新的名为name的信号量;如果存在,就打开已经存在的名为name的信号量.
     valueis the initial value of the semaphore,仅当新建信号量时,此参数才有效,其余情况下它被忽略.
     当成功时,返回值是该信号量的唯一标识(比如,在内核的地址,ID等),Used by two other system calls.如失败,返回值是NULL.
   • sem_wait
     信号量的P原子操作.如果继续运行的条件不满足,则令调用进程等待在信号量sem上.
     返回0表示成功,返回-1表示失败.
   • sem_post
     信号量的V原子操作.如果有等待sem的进程,它会唤醒其中的一个.返回0表示成功,返回-1表示失败.
   • sem_unlink
     The function is to delete thename的信号量.返回0表示成功,返回-1表示失败.
     在kernel目录下新建sem.c文件实现如下功能.然后将pc.c从Ubuntu移植到0.11下,Test your own implemented semaphore.

3. 实验报告

   1. 在pc.c中去掉所有与信号量有关的代码,再运行程序,执行效果有变化吗？为什么会这样？
   2. 实验的设计者在第一次编写生产者-消费者程序的时候,是这么做的：

      Producer()
      {
              
          P(Mutex);  //互斥信号量
          生产一个产品item;
          P(Empty);  //空闲缓存资源
          将item放到空闲缓存中;
          V(Full);  //产品资源
          V(Mutex);
      }
      
      Consumer()
      {
              
          P(Mutex);  
          P(Full);  
          从缓存区取出一个赋值给item;
          V(Empty);
          消费产品item;
          V(Mutex);
      }
      

      这样可行吗？如果可行,那么它和标准解法在执行效果上会有什么不同？如果不可行,那么它有什么问题使它不可行？

实验过程

实验分析

1. 从生产者-Consumer problems see process synchronization

1.1 信号量实现进程同步

The producer is responsible for writing data to the buffer,Consumers producers write data removed from the buffer,The buffer is the shared resource for this process.If the producer has not written data to the buffer,The consumer reads from the buffer;Or the producer data write has not been completed,consumers read.In both cases, the consumer reads illegal data.如果缓冲区已满,The producer continues to write data to it,will overwrite data that has not been read by the consumer,造成数据丢失.Just like a multi-person project requires division of labor and coordination,The use of shared resources by multiple processes must also be synchronized.Process synchronization is to let the process stop where necessary,Wait for other processes to execute until certain conditions are met,再继续执行,To ensure that multiple processes of a reasonable and orderly.
on the producer-消费者问题,Process synchronization is to ensure：
对于生产者来说,当缓冲区满,That is, the number of free buffers is0时,At this point, the producer cannot continue to write data to the buffer,必须等待,Until a consumer has taken the number from the full buffer,There are free buffers again,The producer can only write data to the buffer.And when the buffer is full,There are multiple producers who want to write to the buffer,then they all have to wait,At this point, you need to record the number of waiting producers,so that after the buffer has free space,All waiting producers are woken up,Ensure that producers requesting writes can eventually write to the buffer.
对于消费者来说,当缓冲区空时,No numbers can be taken at this time,消费者必须等待,Until a producer writes to the buffer,Consumers can get.and if when the buffer is empty,There are multiple consumers who want to fetch data from the buffer,then they all have to wait,At this point, you need to record the number of waiting consumers,so that the buffer is available after,All waiting consumers are woken up,Ensure that consumers who request data can eventually get the data.
也就是说,When multiple processes need to work together,need some information,Determine whether the current process needs to stop and wait;同时,Other processes need to judge whether there is a process waiting based on this information,or there are several processes waiting,to decide whether to wake up the waiting process.And this information,就是信号量.
信号量是一个计数器,用于为多个进程提供对共享数据对象的访问.为了获得共享资源,进程需要执行下列操作：

1. 测试控制该资源的信号量.
2. 若此信号量的值为正,则进程可以使用该资源.在这种情况下,进程会将信号量值减1,Indicates that it uses a shared resource.
3. 否则,若此信号量的值为0,则进程进入休眠状态,直至信号量值大于0.如果有进程正在休眠等待此信号量,则唤醒它们.

When implementing a semaphore,Semaphore can take negative value,by the magnitude of this negative value,It can be known that several processes are sleeping waiting for this semaphore.比如下面的情况：
has an integer variablesem,as a semaphore.此时缓冲区为空,sem=0.

1. 消费者C1request to fetch data from buffer,不能取到,睡眠等待.sem=-1<0,Said there is a process for lack of resources and wait.
2. 消费者C2Also request from the buffer,睡眠等待.sem=-2<0,Indicates that two processes are waiting due to lack of resources.
3. 生产者Pwrite a number to the buffer,sem=sem+1=-1<=0,And wake up the head process waiting for the queueC1,C1处于就绪态,C2still in sleep waiting.
4. 生产者PContinue to write a number to the buffer,sem=0<=0,并唤醒C2,C1、C2就处于就绪状态.

1.2 靠临界区保护信号量

1.2.1 竞争条件(Race Condition)

In order to implement the semaphore correctly,Semaphore value test and addition and subtraction1操作应当是原子操作.Atomic operations are indivisible,Execution will not be interrupted by scheduling,也就是说,A sequence of instructions for atomic operations either completes in one execution,要么没有执行,Will not appear to execute part and be switched out.If the operation on the semaphore is not atomic,就会发生问题.我们考虑以下代码：

x++;	//x is an integer

该++operator is a post-increment operator,we all know what it does：获取当前的x值,把x值加1,把加1After the new value is saved tox中,The return value of this expression is the updatedx值.How the operation is compiled to machine code depends on the architecture,It might look as follows：

load x into reigster
add 1 to register
store register in x

Suppose there are two producers at the same time the number of resources available to the bufferfull进行full++操作,其中full = 5.The following is the desired output：

时间	生产者1	生产者2
1	把full加载到寄存器(5)
2	寄存器值加1(6)
3	assign register value tofull(6)
4		把full加载到寄存器(6)
5		寄存器加1(7)
6		assign register value tofull(7)

但是,We cannot avoid this situation：

时间	生产者1	生产者2
1	把full加载到寄存器(5)
2	寄存器值加1(6)
3		把full加载到寄存器中(5)
4	assign register value tofull(6)
5		寄存器加1(6)
6		assign register value tofull(6)

Many other combinations can also have undesired results.
full++is a race condition.竞争条件(race condition)是指：当多个进程都企图对共享数据进行某种处理,And the final result depends on the order in which the processes are run,We think a race condition has occurred.
Shared resources can be any of the following：系统硬件、Kernel resources or data in memory.The latter is the most common,data race(data reace).
The window in which the competition takes place——Code area that needs to be synchronized,称为临界区.The most fundamental source of competition is that the critical section is a window,在这个窗口内,Correct program behavior requires multiple processes not to execute alternately.To prevent race conditions,Need to synchronize access operation within this window,Ensure that multiple processes have mutually exclusive access to the critical section.That is to make the critical section an atomic operation.

1.2.2 Atomic access to critical section through lock mechanism

There are many techniques for achieving atomic access to critical sections,The most common technology is the lock.we define lock,and make sure to acquire that lock before entering the critical section.The lock implementation mechanism ensures that only one lock can be held at a time.If there is another process using the lock,New processes must wait before continuing.if not in critical section,就释放锁,make waiting process(如果有的话)hold the lock and continue execution.
There are several ways to implement locks：

1. 软件方法
   • for both processesPeterson算法
   • Bakery Algorithm for Multiple Processes
2. 硬件方法
   • 适用于单CPUThe switch interrupt method of
   • 硬件原子指令法

在Linux 0.11The simpler method is to block the clock interrupt by switching the interrupt,So as to avoid the scheduling caused by the time slice running out,to achieve atomic access to critical sections.但是开关中断的方法,只适合单CPU的情况,对于多CPU的情况,不适用.Linux 0.11就是单CPU,可以使用这种方法.

2. 用信号量解决生产者-消费者问题

2.1 use file as a shared buffer

Since the address space between processes is isolated,So multiple processes need to share data and need to use files or shared memory.Here files are used as a medium for producers and consumers to share data,open up in it10integer space as a shared buffer,从而实现数据共享.

2.2 File offset synchronization of multiple consumer readings and read end judgment

When multiple consumers read buffer data in a mutually exclusive manner,Correct file offset must be specified.假设消费者1The file offset at the end of the read is12.消费者2follow consumers1From the buffer,it needs to know the consumer1The position where the last read ended is12,and offset from file13continue reading the next digit.所以The file offset at the end of the last consumer read is the shared data that multiple consumers need to synchronize.For this purpose, an integer space from the beginning of the file is stored to store the value of the file offset at the end of the last consumer read..
and the producer is from0Start writing to the buffer in sequence,而消费者是从0开始读取的,Due to the function of the semaphore, it can ensure that the sequence of the producer's write data is to write from the beginning of the buffer after each time the buffer is full..So the number read by the consumer and the position of the number in the buffer/File offsets have a mathematical relationship.The producer exits after writing the last number,Multiple consumer processes follow the scheduling algorithm to randomly fetch numbers from the buffer,But only one consumer will read the last number written by the producer,The consumer knows that the reading has been completed until the last number is read,You can also quit.but the remaining consumers cannot read the last number,Therefore, it is impossible to judge whether the reading is over or not..
综上,The file offset at the end of the read can be replaced by the number read at the end of the last consumer read.这样,The mathematical relationship between the two is：

Read at the end of the file last time offset = (The number read at the end of the last read % 缓冲区的长度 + 1(文件偏移量0is used to save the read number) ) * sizeof(int)

同时,The remaining consumers who cannot read the last number can judge whether the reading is completed according to the number.

3. 信号量的实现

3.1 信号量的组成

1. 需要有一个整形变量value,as a counter for shared data.
2. need a waiting queue,Holds processes waiting for a shared resource when the resource is missing.
3. Requires a name to refer to the semaphore across multiple processes.

同时,The system needs to support multiple semaphores,Consider storing these semaphores in an array.这样,When creating a new semaphore, look for free space in the array to store the semaphore.When opening the semaphore with its name,Need to look up the name of the semaphore in the array.when deleting the semaphore,Need to delete the name of the semaphore and mark the array position occupied by the semaphore as available.

3.2 Construction of waiting queue

当前进程调用sem_wait()function for semaphoreP操作时,If the lack of resources you need to the current process blocking in the waiting queue;当调用sem_post()function for semaphoreV操作时,If there is a process blocked in the waiting queue,just wake up the team leader.So there are two ways to construct the waiting queue：First, create your own waiting queue,Then manually put the process that needs to be blocked into an uninterruptible sleep state,put it in the waiting queue.Or dequeue the team leader process that needs to be awakened,and put it from uninterruptible sleep to ready state;另外一种是利用Linux 0.11提供的sleep_on()The function implements the sleep of the process,用wake_up()函数唤醒进程,由于sleep_on()The function will use the sleeping process kernel stacktmpThe variable forms an implicit wait queue,So no need we wait queue in their structure.

1. Create your own waiting queue
   The following figure shows the use of arraysQ[n]来实现一个最多容纳n-1a way of queueing elements.该队列有一个属性Q.head指向队头元素,而属性Q.tail则指向下一个新元素将要插入的位置.队列中的元素存放在位置Q.head,Q.head+1,…,Q.tail-1,并在最后的位置“环绕”,It feels like the location1紧邻在位置nBack to form a ring.当Q.head == Q.tail时,队列为空.初始时有Q.head = Q.tail = 0.如果试图从空队列中删除一个元素,则队列发生下溢.当Q.head = Q.tail + 1时,队列是满的,At this point, if you try to insert an element,则队列发生上溢.

在sem_wait()When the current process needs to be blocked in thecurrent->stateset to uninterruptible sleep(TASK_UNINTERRUPTIBLE).在sem_post()Medium if the wait queue is not empty,dequeue the head process,and set its state to ready(TASK_RUNNING).
2. 利用sleep_onsleep and form a waiting queue,利用wake_up唤醒
关于sleep_onThe formation of the implicit waiting queue in the function can refer to the previous实验3：进程运行轨迹的跟踪与统计>实验过程>1. 进程状态的切换>4. 不可中断睡眠sleep_on 中的解释.
而wake_upThe function is only responsible for explicitly waking up the queue head process.After waking up the head of the queue,由sleep_onWake up subsequent processes in the queue one by one.
1. sem_wait实现
考虑到sleep_on()会形成一个隐式的等待队列,而wake_up()只要唤醒了等待队列的头结点,就可以依靠sleep_on()内部的判断语句：
c if (tmp) tmp->state = 0;
实现依次唤醒全部的等待进程.所以,sem_wait()的代码实现,必须考虑到这个情况.
参考linux 0.11内部的代码,对于进程是否需要等待的判断,不能用简单的if语句,而应该用while()语句.假设在sem_wait中使用if语句：
c if (sem->value < 0) sleep_on(&(sem->queue));
现在sem=-1,生产者往缓冲区写入了一个数,sem=0<=0,此时应该将等待队列队首的进程唤醒.当被唤醒的队首进程再次调度执行,从sleep_on()函数退出,won't do this againif判断,而直接从if语句退出,继续向下执行.而等待队列后面被唤醒的进程随后也会被调度执行,同样也不会执行if判断,退出if语句,继续向下执行,这显然是不应该的.因为生产者只往缓冲区写入了一个数,被等待队列的队首进程取走了,由于等待队列的队首进程已经取走了那个数,它应该已经将sem修改为sem=-1,其他等待的进程应该再次执行if判断,由于sem=-1<0,会继续睡眠.要让其他等待进程再次执行时,要重新进行判断,所以不能是if语句了,must be the followingwhile语句：
c while (sem->value < 0) sleep_on(&(sem->queue));
Below is my first implementationsem_wait()的代码：
c int sys_sem_wait(sem_t *sem) { cli(); sem->value--; while( sem->value < 0 ) sleep_on(&(sem->queue)) sti(); return 0; }
这么做的问题在于：If the current has two consumer blocked because of the buffer is empty,此时sem->value = -2.Then the producer puts a number into the empty buffer,执行sem_post操作,将value值加1,此时sem->value = -2+1 = -1 <= 0,Wake up team leader.Team leader process fromsleep_on函数退出,进入while (sem->value < 0)的判断,Since there is still a consumer blocking at this time,所以sem->value = -1,This causes the team leader process to be blocked again,Now obviously there is a number of desirable buffer,But the two consumers that were blocked before are still blocked,不能取数.出错的原因在于：信号量减1的语句,要放在while判断后面,因为执行while判断时,process may sleep,而这种情况下,There is no need to record how many processes are sleeping,因为sleep_onThe implicit waiting queue formed by the function has recorded the waiting situation of the process.
正确的sem_wait()代码如下：
c int sys_sem_wait(sem_t *sem) { cli(); while( sem->value <= 0 ) // sleep_on(&(sem->queue)); //The order of these two statements cannot be reversed,很重要,It's about whether the semaphore can sem->value--; //work correctly！！！ sti(); return 0; }

2. sem_post的实现    
    `sem_post`implementation must combine`sem_wait`的实现分析.Assume the current buffer is empty,no numbers,`sem->value = 0`.    
    消费者1执行`sem_wait`,due to semaphore reduction1的指令在while判断后面,此时`value = 0`,消费者1阻塞.    
    消费者2执行`sem_wait`,同样`value = 0`,消费者2阻塞.    
    生产者执行`sem_post`,信号量的值加1,此时`value = 1`,To wake up the queue head process consumer waiting on the queue1.所以`sem_post`中的if判断应该为：    
    ```c
    if (sem->value <= 1)
	    wake_up(&(sem->queue));
    ```
    消费者1执行,唤醒消费者2,跳出while判断,将信号量的值减1,此时`value = 0`.消费者1继续向下执行.    
    如果消费者2接着执行,Because producers into the buffer before the only have been a number of consumers1取走,所以此时`value = 0`,消费者2执行while判断,不满足条件,重新阻塞.    
    由此得到,`sem_post`The judgment condition for waking up the process is：`sem->value <= 1`.    
    `sem_post`实现如下：    
    ```c
    int sys_sem_post(sem_t *sem)
    {
	    cli();
	    sem->value++;
	    if( (sem->value) <= 1)
		    wake_up(&(sem->queue));
	    sti();
	    return 0;
    }
    ```