跳过了第四章：多线程编程 和 第五章：进程调度的内容，因为感觉这些内容更像是工具书，因此暂时略过。可能在后续学习过程中会进行重新学习。

临界区问题

通俗的讲， 临界区就是可能会同时被两个及以上的进程执行的代码区块
临界区问题就是有可能两个进程同时对该代码的内存进行了修改，但是由于汇编语言的执行存在先后问题，可能导致多种运行结果发生。
image.png
临界区解决的方案应满足如下三条要求：

  • 互斥：如果进程 P 在临界区内执行，那么其他进程不能在其临界区内执行
  • 进步（progress）：书上的翻译是这个，其实更好的意思是空闲让进：如果没有进程在其临界区内执行，并且有进程需要进入临界区。那么只有那些不在剩余区内执行的进程可以参加选择。
  • 有限等待：从一个进程做出进入临界区的请求知道这个请求允许为止、
    这三个要求也是证明一个方法能否解决临界区问题的证明手段。

    Peterson 解决方案

    这是一种基于软件的解决方案。
    Peterson 解决方案要求两个进程共享两个数据项 int turn; bool flag[2];
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    do{
    	flag[i] = true;
    	turn = j;//j表示另一个进程
    	while(flag[j] && turn == j);

    	////////////临界区///////////
    	flag[i] = false;

    	////////////剩余区///////////
    }while(true);
    需要注意的是，不同机器上执行 load 和 store 的汇编语言有所不同，因此不能确保该种方式运行在所有机器上。仅仅基于软件的解决方案是不够的，因此需要从硬件的角度进行解决。

    硬件同步

    在多处理器的情况下，禁止中断（在单处理器的情况下可行）这种解决方案是不可行的，消息要传递到所有的处理器，延迟进入临界区，降低系统效率。
    因此硬件层面上提供了一些特殊指令完成检测和修改字的内容。test_and_set() 和 ` compare_and_swap() `
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    ////////////test_and_set的定义
    bool test_and_set(bool *target){
    	bool rv = *target;
    	*target = true;

    	return rv;
    }

    /////////互斥实现
    do{
    	while(test_and_set(&lock))
    	/* do something */
    	/* 临界区 */
    	lock = false;
    	/* 剩余区 */
    }while(true);
    指令compare_and_swap需要三个操作数，返回变量value 的原始值，只有 *value == expected 时，value 才被赋新值。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    ////////////////compare_and_swap的定义
    int compare_and_swap(int *value, int expected, int new_value){
    	int temp = *value;
    	if(*value == expected)
    		*value = new_value;
    	return temp;
    }

    /////////互斥实现
    do{
    	while(compare_and_swap(&lock, 0, 1) != 0)
    	/* do something */
    	/* 临界区 */
    	lock = false;
    	/* 剩余区 */
    }while(true);

    互斥锁和信号量

    因为硬件层面的东西复杂且无法被程序员所使用。因此操作系统构建软件工具解决临界区问题。

    互斥锁

    最简单的工具就是互斥锁。一个进程在进入临界区时应得到(acquire())锁；在退出进程时释放(release())锁。互斥锁一般用硬件同步的compare_and_swap 和 test_and_set 来实现。
    当有一个进程在临界区中，任何其他进程在进入临界区时必须循环调用 acquire()，这种类型的锁也称为自旋锁。
    由于自旋锁在进程等待锁时，没有上下文切换的过程，因此当使用锁的时间较短时，可以使用，多用于处理器系统。

    信号量

    一个信号量 S 是一个整形变量，除了初始化之外只能通过两个标准原子操作 wait() 和 signal() 来访问
    1
    2
    3
    4
    5
    6
    7
    8
    9
    wait(S){
    	while(S <= 0)
    		//////wait
    	S--;
    }

    signal(S){
    	S++;
    }
    在没有提供互斥锁的基础上，可以使用二进制信号量（值只能是0 或 1）来提供互斥。

    信号量的实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    typedef struct{
    	int value;
    	struct process *list;
    }semaphore;

    wait(semaphore *S){
    	S->value--;
    	if(S->value < 0){
    		add this process to S->list;
    		block();
    	}
    }

    signal(smaphore *S){
    	S->value++;
    	if(S->value <= 0){
    		remove a process P from S->list;
    		wakeup(P);
    	}
    }
    对同一信号量，没有两个进程可以同时执行操作wait 和 signal ，对于多处理器系统，应该提供其他技术，以确保这两个操作单独执行。

    死锁

    两个或多个进程无限等待一个事件，而该事件只能由这些等待进程之一来产生。
    image.png
    通俗的说：A的前置是B， B的前置是A
    拓扑的说：成环！是环！

    管程

    管程结构确保每次只有一个进程在管程内处于活动状态，因此，程序员不需要明确编写同步约束。在处理某些同步问题时，如果现有的管程结构不够强大，则可以编写condition 结构定义附加的同步机制。
    image.png
    上面是一种管程模型

    多核系统的同步方式

    事务内存

事务内存的概念来自于数据库理论，其中一个内存读写操作的序列乘坐内存事务，如果事务中所有操作都完成了，内存事物就被提交，否则，就回滚。
传统上，用互斥锁完成这个操作，如下所示

1
2
3
4
5
void update(){
	acquire();
	/* modify shared data */
	release();
}

函数式编程

函数式语言并不维护状态，也就是说，一旦一个变量被定义和赋予了一个值，那么它的值是不可变的，即不能被修改。由于函数式编程不允许可变状态，因此不需要关心竞争条件和死锁等问题。
函数式语言有 Scala 和 Erlang 等，Java 和 C 是命令式编程。