《操作系统：设计与实现》学习笔记二

本系列是南京大学蒋炎岩老师的操作系统课程学习笔记

课程视频：B站合集

这两堂课开始讲并发编程了

并发入门

并发的基本单位就是线程，用之前讲的状态机视角来理解的话，每个线程都是一个状态机，有自己的栈和PC，状态机发生流转时可能从任意一个线程流转一步。当创建多个线程去执行程序时，操作系统会自动将它们放到多个CPU上执行

下面是一个实例程序，其中的thread.h库是老师用pthread封装后的简化版，create函数会将线程id作为参数去调用传入的函数，由于传入的是void*类型所以这里传入无参数的函数也没有问题

#include "thread.h"
#include <stdio.h>

void Ta() {
    while(1) {
        printf("a");
    }
}

void Tb() {
    while(1) {
        printf("b");
    }
}

int main() {
    create(Ta);
    create(Tb);
}

线程的内存共享性

对一个进程的多个线程来说，进程内的变量相当于全局变量，所有线程之间可以共享，以下程序可以证明这一点

#include "thread.h"

int x = 0;

void Thello(int id) {
  usleep(id * 100000);
  printf("Hello from thread #%c\n", "123456789ABCDEF"[x++]);
}

int main() {
  for (int i = 0; i < 10; i++) {
    create(Thello);
  }
}

// Output
Hello from thread #1
Hello from thread #2
Hello from thread #3
Hello from thread #4
Hello from thread #5
Hello from thread #6
Hello from thread #7
Hello from thread #8
Hello from thread #9
Hello from thread #A

可以看到，每个线程分别对x进行了加一操作，于是每个线程打印的信息不同

线程的独立堆栈

以下程序可以观察到线程的独立堆栈

#include "thread.h"

__thread char *base, *cur; // thread-local variables
__thread int id;

// objdump to see how thread-local variables are implemented
__attribute__((noinline)) void set_cur(void *ptr) { cur = ptr; }
__attribute__((noinline)) char *get_cur()         { return cur; }

void stackoverflow(int n) {
  set_cur(&n);
  if (n % 1024 == 0) {
    int sz = base - get_cur();
    printf("Stack size of T%d >= %d KB\n", id, sz / 1024);
  }
  stackoverflow(n + 1);
}

void Tprobe(int tid) {
  id = tid;
  base = (void *)&tid;
  stackoverflow(0);
}

int main() {
  setbuf(stdout, NULL);
  for (int i = 0; i < 4; i++) {
    create(Tprobe);
  }
}

传入Tprobe函数后，base会记录入参tid的初始地址，这个地址近似可以认为是线程的栈底（大概是rbp-8的位置）。然后stackoverflow函数会进行无限递归，每次递归时cur会记录传入参数n的地址，当递归到达一定次数时栈就会溢出，此时我们就可以通过计算base与cur的差值来大致估算线程的栈的大小

这里用到了TLS(Thread Local Storage)这样一个特性，这种类型的变量会在每个线程都保存一份，可以用objdump -d看看它的实现

0000000000001412 <Tprobe>:
    1412:	f3 0f 1e fa          	endbr64 
    1416:	55                   	push   %rbp
    1417:	48 89 e5             	mov    %rsp,%rbp
    141a:	48 83 ec 10          	sub    $0x10,%rsp
    141e:	89 7d fc             	mov    %edi,-0x4(%rbp)
    1421:	8b 45 fc             	mov    -0x4(%rbp),%eax
    1424:	64 89 04 25 f8 ff ff 	mov    %eax,%fs:0xfffffffffffffff8
    142b:	ff 
    142c:	48 8d 45 fc          	lea    -0x4(%rbp),%rax
    1430:	64 48 89 04 25 e8 ff 	mov    %rax,%fs:0xffffffffffffffe8
    1437:	ff ff 
    1439:	bf 00 00 00 00       	mov    $0x0,%edi
    143e:	e8 48 ff ff ff       	callq  138b <stackoverflow>
    1443:	90                   	nop
    1444:	c9                   	leaveq 
    1445:	c3                   	retq   

...

000000000000135c <set_cur>:
    135c:	f3 0f 1e fa          	endbr64 
    1360:	55                   	push   %rbp
    1361:	48 89 e5             	mov    %rsp,%rbp
    1364:	48 89 7d f8          	mov    %rdi,-0x8(%rbp)
    1368:	48 8b 45 f8          	mov    -0x8(%rbp),%rax
    136c:	64 48 89 04 25 f0 ff 	mov    %rax,%fs:0xfffffffffffffff0
    1373:	ff ff 
    1375:	90                   	nop
    1376:	5d                   	pop    %rbp
    1377:	c3                   	retq   

0000000000001378 <get_cur>:
    1378:	f3 0f 1e fa          	endbr64 
    137c:	55                   	push   %rbp
    137d:	48 89 e5             	mov    %rsp,%rbp
    1380:	64 48 8b 04 25 f0 ff 	mov    %fs:0xfffffffffffffff0,%rax
    1387:	ff ff 
    1389:	5d                   	pop    %rbp
    138a:	c3                   	retq   

注意1424，1430，136c和1380这几行，可以推断TLS变量在内存的布局如下：

%fs:0xfffffffffffffff0:
    fff8:   id
    fff0:   cur
    ffe8:   base

那么这个%fs是啥呢，STFW！The Linux Kernel Documentation有相关的介绍

The FS segment is commonly used to address Thread Local Storage (TLS). FS is usually managed by runtime code or a threading library. Variables declared with the ‘__thread’ storage class specifier are instantiated per thread and the compiler emits the FS: address prefix for accesses to these variables. Each thread has its own FS base address so common code can be used without complex address offset calculations to access the per thread instances. Applications should not use FS for other purposes when they use runtimes or threading libraries which manage the per thread FS.

如果用gdb调试相关的代码，会发现%fs的值一直是0，但是它会在不同的线程指向不同的地址，这是glibc通过调用arch_prctl系统调用设置%fs的基址实现的（详见源代码）。有趣的是Mac上的实现没有用到这个寄存器，而是在某个地址存放了一个函数的地址，然后这个函数会返回TLS的地址（在Mac上叫做TLV(Thread Local Variable)，通过lldb进行调试可以知道这个函数是libdyld.dylib中的tlv_get_addr函数，具体的实现有兴趣的朋友可以自行研究

(lldb) di
a.out`set_cur:
    0x100003db0 <+0>:  pushq  %rbp
    0x100003db1 <+1>:  movq   %rsp, %rbp
    0x100003db4 <+4>:  subq   $0x10, %rsp
    0x100003db8 <+8>:  movq   %rdi, -0x8(%rbp)
    0x100003dbc <+12>: movq   -0x8(%rbp), %rcx
->  0x100003dc0 <+16>: leaq   0x4241(%rip), %rdi        ; cur
    0x100003dc7 <+23>: callq  *(%rdi)
    0x100003dc9 <+25>: movq   %rcx, (%rax)
    0x100003dcc <+28>: addq   $0x10, %rsp
    0x100003dd0 <+32>: popq   %rbp
    0x100003dd1 <+33>: retq
    0x100003dd2 <+34>: nopw   %cs:(%rax,%rax)
    0x100003ddc <+44>: nopl   (%rax)

最后看一下stack-probe.c的输出，我们可以将其用管道连接到sort程序中，并指定-nk 6，表示以第6列从大到小排序

➜  Lec2 git:(master) ✗ ./a.out | sort -nk 6
...
Stack size of T3 >= 8064 KB
Stack size of T2 >= 8128 KB
Stack size of T3 >= 8128 KB
[1]    1693578 segmentation fault (core dumped)  ./a.out | 
       1693579 done                              sort -nk 6

于是我们大概就能推断出每个线程栈的大小是8192KB，也就是8MB，我们可以进行验证——输入ulimit -s可查看栈大小的限制，再加一个数字可以进行修改

➜  Lec2 git:(master) ✗ ulimit -s
8192

➜  Lec2 git:(master) ✗ ulimit -s 4096
➜  Lec2 git:(master) ✗ ./a.out | sort -nk 6
...
Stack size of T4 >= 3968 KB
Stack size of T3 >= 4032 KB
Stack size of T4 >= 4032 KB
[1]    1695347 segmentation fault (core dumped)  ./a.out | 
       1695348 done                              sort -nk 6

也可以在代码中调用setrlimit来进行更改

struct rlimit lim = (struct rlimit) {
    .rlim_cur = 4096 * 1024,
    .rlim_max = 4096 * 1024,
};
setrlimit(RLIMIT_STACK, &lim);

并发放弃

熟悉了并发编程的概念后，下面就要开始讲一些与以往的编程思维不太一样的地方了

原子性

由于并发的代码可能以任意的顺序交替执行，那么任意两条语句之间都可能被打断，并让其他线程执行，所以如果不做特殊处理的话，很容易发生多个线程同时访问/修改共享变量的场景，这种情况我们称为条件竞争（Condition Race）或者数据竞争（Data Race），比如下面的代码：

unsigned int balance = 100;
int Alipay_withdraw(int amt) {
  if (balance >= amt) {
    balance -= amt;
    return SUCCESS;
  } else {
    return FAIL;
  }
}

当线程1通过了balance >= amt的判断后，如果切换到线程2执行，并且也通过相同的判断，那么就会导致balance被扣除了两次amt，发生严重的后果

再看一个简单的求和代码，在多线程下就会变得不正常

#include <stdio.h>
#include "thread.h"

#define N 100000000
long sum = 0;

void Tsum() { for (int i = 0; i < N; i++) sum++; }

int main() {
  create(Tsum);
  create(Tsum);
  join();
  printf("sum = %ld\n", sum);
}


// Output
➜  Lec2 git:(master) ✗ while (true); do ./a.out; done
sum = 113964510
sum = 100299227
sum = 100099746
sum = 111208802
sum = 100114699
sum = 113526493
sum = 107981029
sum = 100025276
sum = 100927214
sum = 132680804
sum = 100027039
sum = 100733856
sum = 119730117
sum = 100241409
sum = 100177835
sum = 100235288
sum = 130663243

顺序性

还是刚才的求和的例子，如果加上不同的优化选项，情况就会不一样

➜  Lec2 git:(master) ✗ gcc -O1 sum.c -lpthread     
➜  Lec2 git:(master) ✗ ./a.out 
sum = 100000000
➜  Lec2 git:(master) ✗ gcc -O2 sum.c -lpthread
➜  Lec2 git:(master) ✗ ./a.out                
sum = 200000000

用反汇编看一下的话会发现，两种优化方法的等效代码分别如下：

// -O1
R[eax] = sum;
R[eax] += N;
sum = R[eax];

// -O2
sum += N;

由于编译器默认代码是单线程顺序执行的，有时候会使用内存来进行优化，在多线程下执行顺序不确定时就可能出问题

可见性

在多线程环境下，共享变量的可见性也会发生变化，例如以下代码

int x = 0, y = 0;

void T1() {
  x = 1;
  asm volatile("" : : "memory"); // compiler barrier
  printf("y = %d\n", y);
}

void T2() {
  y = 1;
  asm volatile("" : : "memory"); // compiler barrier
  printf("x = %d\n", x);
}

理想情况下，任意一个线程先执行，都应该输出(0, 1)或者(1, 0)，但是偶尔还是会出现奇怪的结果

➜  Lec2 git:(master) ✗ ./a.out | head -n 100000 | sort | uniq -c 
0 0 
0 1 
1 0 
1 1 

这是因为除了编译器，CPU也会帮助我们优化程序的性能。CPU会将汇编指令翻译成一个个更小的微处理操作，每个操作会经过Fetch Issue Execute Commit的阶段。同一周期内CPU会尽可能发射最多的操作，所以可能会出现“乱序执行，顺序提交”的现象

在现代CPU上，当x != y时对x y的内存读写可以任意交换顺序，所以对以下两条指令

mov $1, (x)
mov (y), %eax

CPU是能同时看到这两条指令的，如果第一条指令会发生cache miss，而第二条不会，那么它可能会先执行第二条指令，从而这个时候另一个CPU看到此时x还是0

上篇《操作系统：设计与实现》Lab0

下篇《操作系统：设计与实现》MiniLab2