操作系统学习笔记-ch6

临界区算法需要满足的四个条件 #

• 互斥（防止出错） Mutual Exclusion
  • 例如两边都绿灯
• 前进（防止饥饿） Progress
  • 如果临界区已经空闲，那么必须有进程能进来。
  • 即：有空让进
  • 例如红绿灯都是红的
• 有限等待（防止饥饿） Bounded Waiting
  • 在进程正在等待临界区空闲时，应该限制其让步的次数。这样防止它一直在让步，永远进不去。
  • 例如一边长期红，一边长期绿
• 让权等待（提升效率）
  • 当进程等待临界区空闲时，由于其一直死循环，而且什么也不做，只是占用CPU，显然是资源的浪费。
  • 如果等待的时候可以阻塞，就会进一步提升CPU效率。

Peterson算法1 #

• 满足有限等待

  • 因为在出临界区前， 把turn设置为对方
  • 这就导致双方是严格地轮流访问临界区的，即形如ABABABAB…
  • 显然，在对方用完后，必然会轮到自己。

• 满足互斥

  • 如果turn不在自己，那么无法进入临界区。这就限定死了。

• 不满足前进

  • 由于双方是严格轮流，不存在某一方连续访问两次临界区的情况。
  • 所以，假设A空闲，但是B刚访问过临界区，即便B想要访问临界区，也没法进入，因为A还没访问呢。
    • 显然，虽然临界区空闲，B却进不去。

• 代码

  int turn=i;
  
  //i:
  do{
      while(turn!=i);
      //CS
      turn=j;
      //RS
  }while(1);
  
  //j:
  do{
      while(turn!=j);
      //CS
      turn=i;
      //RS
  }while(1);
  
  

Peterson算法2（存在竞争条件，但是改进了前进性） #

• 基本思想：两个人要上厕所，但是厕所门口要先登记自己名字，再进入厕所；上完厕所要把自己名字的登记撤销。某人来上厕所，先登记上自己的名字。检查登记册，如果发现有别人的名字，自己就原地等待，直到那个人来把自己的名字撤销。然后自己就能开始上厕所了。

• 竞争条件：如果A来厕所，先登记了，然后B比较急，来插队了，也登记上自己名字，但是B发现上面有A的名字，所以等待；A在B等待时查看登记册发现上面有B的名字，等待；

• 不满足前进性：因为上述竞争条件的存在

• 满足互斥：因为使用了while(flag[i]!=0)，所以必然是互斥的

• 满足有限等待：如果抛弃竞争条件不谈，算法正常运行的情况下，显然是有限等待的，因为只要对方没有在使用，自己就可以使用。

• 相比Peterson算法1的进步：如果算法在没有竞争条件发生的情况下正常运行，那么他解决了前进性。因为这个算法不再是双方严格轮流了。

• 代码

  unordered_map<char,bool> flag;
  flag[i]=flag[j]=0;
  
  //i
  do{
      flag[i]=1;//先登记
      while(flag[j]==1);//如果登记册上有名字就等待
      //CS
      flag[i]=0;//使用完成，撤销登记
      //RS
  }while(1);
  
  //j
  do{
      flag[j]=1;
      while(flag[i]==1);
      //CS
      flag[j]=0;
      //RS
  }while(1);
  
  

Peterson算法3（满足了全部三个条件） #

• 可以一言以蔽之曰，综合了前两个算法的思想，我们称之为“登记—令牌协议。”

  • 注意，都是先登记了，然后紧接着把令牌给对方的。
  • 特点：在检测进入临界区的条件时，会发现如果对方具备执行条件，那么对方一定是turn和flag都有的。（虽然这个turn可能是紧跟着while的上一条语句给对方的。）
  • 因此注意，如果对方不想现在使用，那么自己虽然进来了，但是令牌实际上还在对方手里，因为是自己亲手给对方的（这个turn是紧跟着while的上一条语句给对方的。）。这不要紧，因为如果对方突然想来了，那么对方会把令牌给自己，并且陷入死循环。（因为自己在使用，则flag为真，且对方又把令牌给自己了，那么对方只能死循环了）

• 满足互斥：因为while中，要求了turn，且和另一条件AND连接。我们只需来关注turn，就能证明其互斥性：只要turn不是自己，那么自己就进不去。因为turn只可能取一个值。

  • 注意：因为是flag和turn做AND，这个条件来作为是否原地等待的判断依据。也就是说，只有对方同时拿到了turn和flag才可以进入临界区。但是turn只有一个取值（因为令牌只有一个），这就是问题的关键所在。

• 满足前进性：假设A想要进入临界区，B不打算进入，则显然A的flag是true，且其turn给了B。但是while循环中，flag和turn是AND连接，表明了需要原地等待的条件。但是这时候B的flag是false，所以不需原地等待，即便turn在对方（B）手里。A能正常进入临界区。

• 满足有限等待：假设A和B都想进入临界区，并且B先进去了。B在临界区中时，显然B有flag和turn。当B要出来时，B撤销自己的flag，此是A的等待状态循环不成立，A顺势进入，无缝衔接。B如果还想使用，那么需要先设自己的flag，并且设令牌turn为A，此时自然而然，while循环满足了（即flag和turn都到A手里了），需要等待了。

  • 即：如果A和B都想进，但是A被B抢先了，那么B出来一定会先让给A。不存在B连续使用临界区的情况。
  • 这也是综合了Peterson算法1的结果。

unordered_map<char,bool> flag; //登记
flag[i]=flag[j]=0;
int turn=i; //令牌

//i
do{
    flag[i]=1;//先登记
    turn=j;//紧接着把令牌给对方
    while(flag[j]&&turn==j);//如果对方有两件套，那么等待；如果对方没有两件套，要么是对方不想进入，那么自己可以进入；要么是令牌在自己手里，那么在两方都想进入的情况下，还是听令牌的，所以还是自己进入。
    //CS
    flag[i]=0;
    //RS
}while(1);

//j
do{
    flag[j]=1;
    turn=i;
    while(flag[i]&&turn==i);
    //CS
    flag[j]=0;
    //RS
}while(1);

开关中断 #

• 对于单处理器系统，如果在一段程序两边开启和关闭中断，那么可以保证原子性，这段代码可以不被打断地执行。
• 对于多处理器系统，各个处理器之间需要统一的中断消息传递，会有时间开销。效率过低。而且由于消息传输延迟，各个处理器进入关中断并不同时。

原子机器指令 #

• 为了实现对临界区的支持，现代设备都设计了一些原子机器指令。这些值令能原子地执行（因为硬件设计好了）。
• 例如：TestAndSet、Swap。

Test-And-Set #

函数 #

bool TestAndSet(bool * lock){
	bool ret=*lock;
    *lock=1; //如果锁是1，那么仍然是1；如果锁是0，那么顺便上锁。
    return ret;//返回查询到的锁的值。如果是1，那么等待；如果是0，那么说明空闲，并且自己已经上锁完成，可以直接进入临界区。
}

算法实现 #

bool TestAndSet(bool * lock);
Lock* lock;

//其中一个访问方的代码（注意，锁机制相比Peterson算法的进步有一点很明显，那就是不只支持双方访问了，而是支持多边访问了。而且，不再需要通过==硬编码==去区分双方。）
do{
    while(TestAndSet(lock));//查询锁状态，如果空闲那么顺便上锁，否则原地等待
    //CS
    *lock=0;//解锁
    //RS
}while(1);

Swap #

算法实现 #

void Swap(bool* a, bool* b);
Key* key;
Lock* lock;

//其中一个访问方的代码
do{
    *key=1;
    while(*key)Swap(key,lock);//如果key还是1，那么说明原来lock也是1，那么什么事情也没有发送；如果key变成了0，说明key取代了lock，且lock原来是0，现在被key换成了1.那么相当于自动上锁了，可以继续执行了。
    //CS
    *lock=0;//解锁
    //RS
}while(1);

信号量 #

• 信号量是一个整数，其一旦初始化初值，就不能直接访问和修改了，只能通过P即wait、V即signal进行减少和增加。这两个方法是原子的。
• 信号量支持让权等待。即：在等待时可以进入阻塞，而不像其他的算法必须始终占用CPU（因为要主动检查可用性。）。因为，信号量机制可以允许其他刚刚结束使用临界区的进程去唤醒那些等待的进程。
• 信号量通常是>=0的数字。因为其物理意义是临界资源剩余的数量。

信号量的wait和signal函数 #

void wait(Semaphore* s){
    while(s<=0);//test
    s--;//set
}
//wait函数使用了test-and-set的思想。如果当前临界资源数量（即其对应的信号量）<=0，那么说明没有资源了，就等待即可。一旦有了，那么就s--。
//可见，wait的函数是在保证有剩余临界资源的情况下，让信号量自减，表示拿走一份进行使用。

void signal(Semaphore* s){
    s++;
}
//可见，signal函数只有自增的功能，没有别的。（如果不考虑让权等待）

• 信号量分为binary信号量和counting信号量。前者又称互斥锁。它们的区别只在：前者的初值是1，后者的是任意>=2的整数。

自旋锁 #

• 如果采用上述算法，那么进程在等待临界资源的时候是一直循环的。
  • 好处：不需要上下文切换，比较迅速。因此如果大家使用临界资源的单次时间都较短，那么这种办法很好。
  • 对于多处理器系统有用：因为如果一个进程进入循环等待，另一些进程可以去其他处理器上运行。
  • 缺点：对于单处理器系统来说，空空占用CPU时间，浪费资源。

实现让权等待 #

• 应当定义新的信号量数据类型：把它定义为一个结构体，而非简单的整型。
• 包括以下域：
  • 整型：信号量的值。
  • 等待链表的头指针。这个链表里面是所有等待此信号量对应的临界资源的进程的代表。
• 包括以下方法：
  • block()：调用此方法的进程把自己阻塞。（主动睡眠）
  • wakeup(P)：将P进程从睡眠中唤醒。（被动唤醒）
    • 叫他起来干活：临界资源空出来了，可以安排给他用了。
• wait和signal实现方法的改变：
  • 如果没有临界资源了，调用wait的那个就仍然让信号量–（尽管已经<0），然后去阻塞了。
  • 如果有人调用signal，就先让信号量++。如果当前信号量<=0，就说明还有人在等待，那么去等待队列中唤醒一个出来，把临界资源给这个被唤醒的使用。
    • 在Unix中，为了系统的稳定性，一般是把队列中所有阻塞进程都唤醒，让他们去竞争这个多出来的资源。

void wait(Semaphore* s){
    s.value--;
    if(s.value<0){//说明在自减前，value已经<=0
        waitQueue.push(*this);
        block();//阻塞自己
    }
}

void signal(Semaphore* s){
    s++;
    if(s.value<=0){
        pid_t p=waitQueue.front();//这是优先级队列。队首的元素是特定的算法得出。
        p.pop();
        wakeup(p);//由使用完毕临界资源的进程调用signal，所以实际上是时用完临界资源的进程负责唤醒那些等待进程。
    }
}

• 注意：实现让权等待的信号量算法中，信号量可以<=0。此是的含义是：其绝对值是正在等待的进程的个数，或者说是等待队列的大小。

信号量导致死锁 #

• 死锁：例如两个进程无限等待。但是只有对方正常开始执行，才能发生让本方不再继续等待的事件。对于双方都是这样的。但是可惜双方都在等待“不再继续等待”的信号。

  • 要开锁，就需要看证明。但是证明被锁在了箱子里。开锁工人说要证明才能开锁，你说要开锁才能有证明。

• 死锁也是一种饥饿现象。因为它们在信号量的等待队列中迟迟不能得到移除和唤醒。

• 例如下列程序并发运行：

  Q=1;
  S=1;
  
  //进程1：
  wait(S);
  wait(Q);
  //...
  signal(S);
  signal(Q);
  
  //进程2：
  wait(Q);
  wait(S);
  //...
  signal(Q);
  signal(S);
  

  • 如果进程1在执行了wait(S)后，系统就调度进程2，那么这个程序就会发生死锁。
  • 相反，如果进程1幸运地执行完了前两行，那么程序不会死锁。

wait()和signal()在缓冲区问题中的新理解 #

• 如果设置两个信号量，一个是empty，代表缓冲区空信号，一个是full，代表缓冲区满信号：
  • 那么，生产者先wait(empty)，再生产到缓冲区，再signal(full)；
  • 消费值先wait(full)，再从缓冲区拿东西，再signal(empty)。
  • 可见，这里，signal就是发出特定信号，wait就是等待接收特定信号。
• 因此，我们为什么说是“信号量”：因为它本质上是一种信号，但是它又可以带有数量。

信号量的应用1：前趋图 #

• 对于每个节点，它们都表示需要进行的一步操作。
• 对于其入边，可以理解为需要的前提条件，所以每个入边都对应一个wait即可。
• 对于其出边，可以理解为其产出的结果，所以每个出边都对应发出一个signal即可，表示该结果已经产出，其他节点可能可以进行使用了。

信号量的应用2：有限缓冲问题（即生产者-消费者问题） #

解释 #

• in=(in+1)%N的含义：往缓冲区里放东西，总是顺序存放的。
• out=(out+1)%N的含义：从缓冲区里取东西，总是顺序取得的。
• 这两个顺序性，互相保证了对方的顺序性操作可以成立。否则，假设消费者随意取东西，那么就算in=(in+1)%N，那也不一定是空的。因为该新的空缓冲槽可能在别处。
• 互斥访问：对于临界资源，例如整个缓冲池，或共享计数器等。一定要保证互斥访问。
  • 在很多情况下，互斥访问可能没有必要保证。例如这个临界资源可能只会被一个进程访问。
  • 但是，加上一定是没错的，不加一定是不能保证不出错的。因为在超高并发的系统状态下，很可能出现未知问题。

信号量分类 #

• 信号量分类：
  • 从现在开始，信号量可以被我大致分为三类：互斥信号量、binary信号量（信号）、资源信号量。
  • 互斥信号量是一个binary信号量，为了保证临界资源的互斥访问。通常在临界区进入前紧接着使用wait，在临界区退出后紧接着使用signal。而且其一般命名为含有mutex的名称。
  • binary信号量又称信号。其代表等待一个事件的发生（wait）和发出信号以通知一个事件发生（signal）。
  • 资源信号量表征某种临界资源的剩余量。可以>1。如果是负数那就其绝对值是排队等待使用的人数。

资源释放 #

对于一个信号量，其wait和signal的次数必须一致（两两配对）。也就是说，使用了一个临界资源，那么也必须释放此临界资源。

同步和互斥的信号量的特点 #

• 互斥信号量出现在同一个角色的程序中，成对出现；
• 同步信号量出现在不同角色的程序中，交叉出现。

例子：什么是“不同程序交叉出现”

//A
while(1){
    wait(sa);
    //do something;
    signal(sb);
}

//B
while(1){
    wait(sb);
    //do something;
    signal(sa);
}

例子：什么是“同程序成对出现”

while(1){
    wait(mutex);
    //cs
    signal(mutex);
}

先同步，后互斥 #

考虑下面的消费者程序：

           while (true) {
              wait (full);
              wait (mutex);
              //  remove an item from  buffer
              //item=buffer[in];
              //out=(out+1)%N;
              signal (mutex);
              signal (empty);
             //  consume the removed item
           }

• 如果两个wait互换，则可能出现缓冲区里没东西呢，但是你先把mutex给占用了，也就是生产者无法访问临界资源（缓冲区）了，那full就不可能>0，那么整个就死锁了。

因此，如果不遵循“先同步，后互斥”的原则，那么会有很大可能引发死锁。

• 为什么一定要先同步：因为如果不同步，在并发的环境下可以说大家的执行是混乱的，那么获得mutex控制权也是混乱的。如果获得的不恰当，就会死锁。
• 交换两个signal的顺序，不会有问题。

信号量的应用3：读者-写者问题 #

解释 #

• 思路：
  • 写者在写的过程中，不允许有读者或写者来访问或书写；
  • 读者在读的过程中，不允许有写者来书写，但是允许更多读者来读；
  • 因此，给写者设定一个信号量wrt，这个信号量是信号型的。写者需要一个wrt信号才能进入书写，否则等待。第一个读者来了，也等待wrt信号。如果信号量=1，那么说明没有写者，那么直接读，并signal这个wrt来封锁写者；如果wrt=0，说明有写者在写，则应当等待。但是，对于后面的读者，不需要等待wrt信号，可以直接进来读。最后一个读者走后，要发出signal(wrt)，释放对内容的占用。这样一来，写者可以来写了（读者也一样，如果碰巧最后一个读者刚走，下一个读者就来了）。
  • 另外，注意读者计数器的作用是记录当前正在读的读者的个数。它主要用来确定该读者是否为第一个来的或最后一个走的，以做出等待wrt或释放wrt的操作。

代码 #

//writer
while(1){
    wait(wrt);
    //write...
    signal(wrt);
}

//reader
while(1){
    wait(mutex);
    readercntr++;
    if(readercntr==1){
        //第一个读者，需要等待其他写者写完
        wait(wrt);
    }
    signal(mutex);
    //read...
    wait(mutex);
    readercntr--;
    if(readercntr==0){
        //最后一个读者，需要释放这篇文章
        signal(wrt);
    }
    signal(mutex);
}

算法设计的思想 #

• 对于这个文章，有两种对象对于他互斥访问，一种是写者，一种是读者集合。
  • 读者集合：1个读者构成一个读者集合，n个读者也构成一个读者集合。无论读者的数量如何，对于这个文章的访问是等效的。
• 因此，可以把读者集合看成单个写者。这样，问题就转化成了写者之间的互斥访问问题了。
  • 于是，需要做的就是，如何把读者集合看成单个写者。这很简单，也就是对于第一个来的、最后一个走的这两个关键读者进行信号量的操作，其他读者不做任何要求即可。
    • 为什么是关键读者？因为它们的来去直接导致了读者集合的创建与删除。
    • 如何实现区分关键读者？设置readercntr即可。但是这个计数器一定要互斥访问。

读者优先问题 #

• 虽然把读者集合看成一个写者，但是这个写者要比一般的写者“长”很多。如果读者不断到来，那么这个“写者”会一直占用文章不放。这就导致真正的写者产生饥饿现象。
• 解决方式：如果真正的写者wait wrt了，就禁止后续读者来。

信号量的应用4：哲学家干饭问题 #

略。

信号量的应用5：摸鱼的托尼老师问题 #

• 和银行问题的区别：银行问题中，顾客如果发现座位满了，就等待。等有空座位了，就进入。但是理发师问题中，顾客发现座位没有了，就立即离开。
  • 这就导致：理发师问题中，不能使用信号量来表征座位数量，而是只能以临界资源来表示（用于计数）。

code #

// customer
while(1){
    wait(mutex);
    if(wait<seats){
        wait++;
        signal(mutex);
        signal(customer);//signal(A)
        wait(barberReady);//wait(B)
    }else{
        leave();
        signal(mutex);
    }
}

//barber
while(1){
    wait(customer);//wait(A)
    wait(mutex);
    wait--;
    signal(mutex);
    signal(barberReady);//signal(B)
    cut-hair();
}

• 注意，上述的注释：wait(A),signal(A),wait(B),signal(B)正是非常典型的不同程序交叉使用信号量实现的进程同步！上述的mutex正是同一程序成对使用的资源互斥！

信号量的应用6：抽烟者问题 #

cobegin和coend #

即“并发区开始”、“并发区结束”。