Operating System Concepts ——chapter 5——Process Synchronization

柔情只为你懂 2021-11-09 05:18 175阅读 0赞

# 临界区问题 #

# 硬件同步 #

硬件指令，一个指令执行过程中，不会被中断（原子操作）

## TestAndSet ##

boolean TestAndSet (boolean *target)
    {
    	boolean rv = *target;
    	*target = TRUE;
    	return rv;
    }
    
    while (true) 
    {
    	while ( TestAndSet (&lock )); 
      /* do nothing
      //      critical section
       lock = FALSE;
       //      remainder section
      }

TestAndSet 由硬件保证原子性。

## swap ##

# 信号量（semaphore） #

1.  更简单
2.  消除忙等的问题

信号量S是一个整数。  
只能通过两个标准的操作去修改S：

*  wait()
 *  signal()

wait(S)
    {
    	while(S<=0){do nothing}
    	S--
    }
    
    signal(S)
    {
    	S++;
    }

以上简单的信号量机制依然没有解决忙等的问题。  
无忙等问题的解决方案：

typedef struct {
        int value;
        struct process *list;
    }
    
    wait (semaphore *S){ 
        S->value--;
        if (S->value < 0) {
            add this process to S->list
            block();
        }
    }
    
    Signal (semaphore *S){
        S->value++;
        if (S->value <= 0) { //如果没有任何进程在等待，S=1
            remove a process P from S->list
            wakeup(P);
        }
    }

可以看出，之所以能解决忙等的问题，最关键的是引入了一个排队的队列。

# 死锁 deadLock #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMxNTY3MzM1_size_16_color_FFFFFF_t_70]

# 经典的同步问题 #

## 生产者消费者问题 ##

生产者消费者消费一个缓存区，所以缓存区是共享资源，需要设置共享互斥量：  
mutex=1

几种场景：  
缓存区全空，此时消费者依赖于生产者。  
缓存区全满，此时生产都依赖于消费者。

要判断这两种场景，需要定义两个新的信号量：  
empty=N  
full=0  
empty可以理解为unused  
full可以理解为used

最终的算法如下：  
while(true)  
\{  
//produce an item  
wait(empty);  
wait(mutex);

//add the item to the buffer
    
    signal(mutex);
    signal(full);

while(true)  
\{  
wait(full);  
wait(mutex);

//remove an item from the buffer
    
    signal(mutex);
    signal(empty);
    
    //consume the removed item

\}  
为什么需要引入full，empty两个信号量呢？我理解是因为消费者和生产者等待的是两种不同的条件：  
消费者等待的是不为全空（used不为0）  
生产者等待的是不为全满（unused不为0）  
其实用一个count变量，在mutex互斥的区域内，判断count是否为0和是否为BufferSize来分别判断是否全空或全满。  
但是，如果要使用信号量机制的话，信号量机制只能判断某个信息是否大于0，没办法去判断和BufferSize的大小，所以必须要用两个信号量。

那么用count和用信号量哪个好呢？没想明白。。。

## 读者写者问题 ##

1）多个写者互斥  
2）读/写互斥  
3）读者之间不互斥

Shared Data:  
1)Data set  
2)Semaphore mutex =1, ensure readcount is updated  
3)Semaphore wrt = 1  
4)Integer readcount initialized to 0

**Readerprocess**  
while (true)  
\{  
wait (mutex) ;  
readcount ++ ;  
if (readcount==1) wait (wrt) ;  
signal (mutex);

// reading is performed
    
    wait (mutex) ;
    readcount  - - ;
    if (readcount==0)  signal (wrt) ;
    signal (mutex) ;

**Writerprocess**  
while (true)  
\{  
wait (wrt) ;  
//writing  
signal (wrt) ;  
\}

## 哲学家进餐问题 ##

# 管程（monitors) #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMxNTY3MzM1_size_16_color_FFFFFF_t_70]: /images/20211109/e66147a222094987852ad076622878f8.png