# OS 恶补笔记 Part1 并发

# 前情回顾

复习下 OS 里的一些基本知识点:

# 并行 vs. 并发

并发性 (Concurrency): 同一时间段内执行多个任务 (but not necessarily simultaneously)。强调 “时间片段” 内的同时性，通过线程间的调度达到宏观上的 “同时进行”。
并行性 (Parallelism): 同一时刻执行多个任务。多 (核) 处理器出现后才有的概念，不同线程 (或指令片段) 在不同处理器上各自执行，实打实地同时进行。
没有并行，并发也是可能的。

# 多线程基础

# 一些基本概念

多线程的痛点：

1. 共享内存管理：原子性执行的实现。
2. 编译优化导致多线程代码顺序性丧失：“想当然” 的代码在编译器看来是另一回事，编译器 “更倾向于” 单线程程序。
3. 处理器执行期间行为的不可见性：现代 CPU 指令流水线规则复杂。

   线程惯性指在多线程编程中的一种错误的心理状态，它假定当前编写的代码执行完毕后会继续执行下一条代码。而实际上，在现代处理器中，线程随时（当该线程的时间片用完时）可能被处理器冻结，而处理器被另一线程抢占（这里指单处理器上的情况，在多处理器上，情况更加复杂）。

线程安全：一段代码能够正确地处理多个线程之间的公用变量，使程序功能正确完成。
可重入：一段代码在执行结束前，发生中断后再次被调用，能够顺利执行完毕而不发生错误。

C 标准库下的 printf 是线程安全的

可重入一定是线程安全的，反之不然。以下函数是线程安全的，但不是可重入的。

int increment_counter (){

	static int counter = 0;

	static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

	pthread_mutex_lock(&mutex);// 互斥锁保证了下面代码的原子性

	++counter;

	// 如果在这个位置发生中断，再次调用 increment_counter，则 mutex 将无法解锁

	int result = counter;	

	pthread_mutex_unlock(&mutex);

	return result;

}

实际上这种情况就需要信号量来控制了 (mutex type: PTHREAD_MUTEX_RECURSIVE)。

# 互斥算法 Peterson

从代码层面考虑实现共享内存的正确访问。

条件：同时最多 2 个线程的共享区访问；代码顺序性不被破坏

int x = 0, y = 0, turn = A;

void TA() {

    while (1) {

		x = 1;

		turn = B;

		while (y && turn == B) ;

		critical_section();

		x = 0; 

	} 

}

void TB() {

  	while (1) {

		y = 1;

		turn = A;

		while (x && turn == A) ;

		critical_section();

		y = 0; 

	}

}

证明方法：状态机
从初始状态 BFS，搜索到的状态空间不含有非法状态 (同时到达 critical_section) 即正确。

具体实现可以巧用 python 的 yield 语法，对需要分析的每行代码打检查点，暴力搜索状态空间。加上可视化画图直观分析。神乎其技！

真实情况：Peterson 算法在现代 CPU 上仍然无法保证互斥访问，由于处理器行为的不可见性。
得出结论：想要软件层面上实现原子性执行，做不到！没那个必要

# 真正的互斥

# 附

视频中出现的技 (qi) 术 (ji) 细 (yin) 节 (qiao) 没有太多时间记了。有时间了一定好好写一下。