[OS]课堂笔记(1)

Posted on | In

jyy os-class 整理。

互斥

直观理解：线程==人 && 共享内存==物理世界；线程不想被打断

实现lock_t数据结构（一把排他性的锁）和lock/unlock API
状态机视角：lock返回会进入”locked”状态；unlock会清楚该状态 && 初始状态不能到达两个threads都进入locked的状态。
lock/unlock保护的区域为一个原子的黑盒子
黑盒子的代码不能随意并发，顺序要么1→2，要么2→1
先完成的黑盒子的内存访问在之后的黑盒子中可见

共享内存上的互斥

假设线程可以完成三种指令：
①load(读)
②store(写)
③thread-local(本地计算，其他线程不可见，如寄存器、堆栈)

load/store是原子的（状态机每次执行一条load/store）==> 不能同时读/写内存（只能干看/闭着眼睛写）

Peterson算法的问题

两个线程用Peterson算法可以简化为如下指令:

1
2
3
4
5
thread 1                                               thread 2                    
[1]store(x)                                            [1]store(y)//举自己旗子
[2]store(turn)                                         [2]store(turn)//挂对方牌子      
[3]load(y)                                             [3]load(x)//看对方旗子 
[4]load(turn)                                          [4]load(turn)//看门上牌子

然而处理器允许指令乱序，可能thread 1可能先load(y)，thread 2先load(x)，导致同时进入临界区。所以该算法在现代处理器上是错误的。

共享内存带来的更多问题

用内联汇编实现do_sum()并且禁止编译器优化

1
2
3
4
void do_sum(){
	for(int i = 0; i<1000000; i++)
		asm volitile("addq $1, %0": "=m"(sum))
}

然而结果仍然与预期不符。

由于现代处理器一次只能一次load/store，所以一条add实际被拆成了t=load(x); t++; store(x,t)，现代处理器下许多个这样的指令可能乱序执行，造成意想不到的结果。

另外，如果在两个处理器上执行，有可能thread 1已经执行了多次sum++，但数据仍在CPU1的store buffer中，未写入共享内存，而thread 2读sum时直接从共享内存中读。

状态机一步执行一个线程执行一条指令是错误的假设
编译器/处理器乱序
表面“原子”的一条指令并不原子

实现互斥

以下locked实现是错误的

1
2
3
4
5
6
7
8
9
void critical_section() {
     while (1)
[1]    if (!locked) {
[2]      locked = 1;
[3]      break;
       }
     // 进入临界区
[4]    locked = 0;
}

用状态机分析如下

需要一条”test-and-set”指令，使得t=load(locked);if(t==0) store(locked,1)可以同时执行。
原子指令：一次共享内存的load；向同一个共享内存地址store；以及一些本地运算
x86 lock指令前缀(lock addq)；xchg指令。

自旋锁

实现

1
2
3
4
5
6
7
8
9
10
int table = KEY;
void lock() {
  while (1) {
    int got = xchg(&table, NOTE);
    if (got == KEY) break;
  }
}
void unlock() {
  xchg(&table, KEY)
}

简化

1
2
3
4
5
6
7
8
int locked = 0;
void lock()   {
  while (xchg(&locked, 1)) ;//返回0表示得到钥匙
}

void unlock() {
  xchg(&locked, 0);
}

RISC-V：另一种原子操作设计

原子操作本质是：
load(x)
thread-local operation
store(x)

LR(load-reserved)/SC(store-conditional)，前者在共享内存上做了标记，后者会清楚内存上的所有标记。假设有两个threads分别执行f1(x)和f2(x)，证明最后的结果是f1(f2(x))即可：

数据竞争

两个不同线程的两个操作访问同一段内存，切至少有一个是store，其中没有原子操作间隔。
数据竞争=undefined behavior
编程时避免数据竞争<==>所有线程间的共享变量都被同一把互斥锁保护

0%