临界区问题(critical-section problem)

1. Each concurrent(并发) process has a segment of code ,called a critical section,in which the process may be changing common variables(公共数据),updating a table ,wrinting a file ,and so on.
2. The important feature of the system is that ,when one process is executing in its critical section section no other process is allowed to execute in its critical section.That is,NO two processes are executing in their critical sections at the same time.

• 这句话的意思是，系统的一个重要特性是，当一个进程在其关键区域（critical section）执行时，不允许其他进程进入其关键区域执行。也就是说，没有两个进程会同时在各自的关键区域内执行。关键区域是指一个进程访问共享资源（例如共享文件或共享内存）的那部分代码，系统确保在任何时候，只有一个进程可以执行在关键区域内的代码，以防止数据冲突或不一致性。

3. The critical-section problem is to design a protocol(协议) that the processes can use to cooperate(协作).
4. 进程进出临界区协议

• 进入临界区前再entry section要请求许可。
• 离开临界区后再exit section要归还许可。
  

5. 临界区管理准则

• Mutual exclusion(Mutex):互斥，
  
• Progress:前进，在上面这个图中，只有一个p可以进入到临界区（这个动作就是前进）。
• Bounded waiting:有限等待。只可以从中选一个，并且当临界区有进程就无法进入。就要等待但不是无限的等待。

喂养金鱼

1. 并发执行有两种现象：顺序执行，交替执行，这里的交替执行是需要注意的。
   
2. 使用软件解决临界区管理

• 实现需要较高的编程技巧
• 两个进程的实现代码是不对称的，当处理超过2哥进程的时候，代码的复杂度会变得更大。

互斥锁

1. mutex locks

• Operating-systems designers build software tools to solve the critical-section problem. The simplest of these tool is the mutex lock.(操作系统设计者构建软件工具来解决临界区问题。其中最简单的工具是互斥锁。)
  • A process must acquire the lock before entering a critical section;
  • It must release the lock when it exits the critical section

2. 锁的基本操作

• 上锁
  • 等待锁至打开状态。
  • 获得锁并锁上
• 解锁
• 原子操作
  • Atomic operations mean the operation can NOT be interrupted while it's running.(原子操作意味着在其运行时无法被中断)
  • 原子操作（原语）是操作系统重要的组成部分，下面2条硬件指令都是原子操作，他们可以被用来实现对临界区的管理（也就是‘锁’）
    • test_and_set();
    • compare_and_swap()

3. 锁的实现

• test_and_set

bool ts(bool* target){
  bool result =*target;
  *target=false;
  return result;
}

bool available=true;
lock(){
  while(!ts(&available)) do nothing;
}

unlock(){
  available= true;
}

• ts函数设置是原子操作，就是在运行时候不可中断的.
• test_and_set，测试并设置，是这个的精髓。ts的返回值是availble的值，并都修改为false。当availble初始为true时候，就跳出while循环进入临界区并修改availble为false，那么其他线程就会进入到while循环，只有当执行到unlock（），available修改为true。
  

4. 忙式等待（busy waiting）

• 忙式等待是指占用CPU执行空循环实现等待
• 这种类型的互斥锁也被称为‘自旋锁’(spin lock)
• 缺点：浪费CPU周期，可以将进程插入等待队列以让出CPU的使用权；
• 优点：进程在等待时没有上下文切换，对于使用锁时间不长的进程，自旋锁还是可以接受的；在多处理器系统中，自旋锁的优势更加明显