09-并发控制：同步

希望可以控制顺序

• 控制并发，使得 “两个或两个以上随时间变化的量在变化过程中保持一定的相对关系”

1.开始同时执行

2.最后等待同时执行

互相已知

从一个简单状态到另一个简单状态（状态分支聚起来）

简单->复杂->简单……..

先到先等，先完成等待

sync

每个线程都有wait_next_beat等待下一个拍子再执行

1
2
3
4
5

void wait_next_beat() {
retry:
    if (!next_beat_has_come) {
        goto retry;
    }

同步（synchronization）指的是多个线程在执行时保持协调，以确保它们在预期的时间点上执行特定的操作。具体来说，这里的同步是指：

1. 开始时间一致：确保某些操作在多个线程中同时开始。例如，wait_next_beat 函数确保 T_player 线程在预期的节拍时开始播放音符。
2. 协调执行：确保线程在执行过程中保持协调。例如，release_beat函数由 T_conductor线程调用，以通知 T_player线程可以继续到下一个节拍。

在这个代码中，T_conductor线程通过调用 release_beat来增加节拍计数 n，而 T_player线程通过 wait_next_beat来等待节拍计数达到预期值，从而实现同步。

生产者-消费者问题

共享缓冲区

打印左括号的条件：缓冲区未满就可以

打印右括号的条件：当前有左括号就可以

等到达成同步条件再执行

错误1：ready是共享变量，可能已经在解锁时被其他线程改变了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void T_produce() {
    while (1) {
retry:
        mutex_lock(&lk);
        int ready = (depth < n);
        mutex_unlock(&lk);
        if (!ready) goto retry;
		
        // assert(depth < n);

        mutex_lock(&lk);
        printf("(");
        depth++;
        mutex_unlock(&lk);
    }
}

正确:但是如果条件不满足，就会不断锁上再解锁，浪费资源

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void T_produce(){
	while(1){
retry:
        mutex_lock(&lk);
        if(!(deepth < n)){
			mutex_unlock(&lk);
           	goto retry;
        }
    
    	assert(depth < n);

        printf("(");
        depth++;
        mutex_unlock(&lk);
    }
}

条件变量

1
2

#define CANPRODUCE (depth < n)
#define CANCONSUME (depth > 0)

不符合条件时，睡眠，等待被唤醒

生产者和消费者是两个不同的线程

所以以下是错误的，因为生产者和消费者的条件变量不相同，唤醒不一定满足自己的条件，所以会使断言不一定正确（详见ostep）

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void T_produce() {
    while (1) {
        mutex_lock(&lk);
        if (!CAN_PRODUCE) {
            cond_wait(&cv, &lk);
        }
       // assert(CAN_PRODUCE);
        printf("(");
        depth++;

        cond_signal(&cv);
        mutex_unlock(&lk);
    }
}

条件变量的正确使用，每次改动后都通知所有线程

1
2
3
4
5
6
7
8

mutex_lock(&mutex);
while (!COND)
{  
    wait(&cv, &mutex); 
} 
assert(cond);
...
mutex_unlock(&mutex); 

并行编程的本质

把任务分解

生成有向无环图

并行计算，每个节点满足条件就计算

拓扑排序，计算

打印鱼

把状态图画出来，根据状态图得到条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

const char roles[] = ".<<<<<<<>>>>>>>______";
//每个线程获得一个字符，如果太少就不能等到下一个状态，就会阻塞
void fish_thread(int id) {
    char role = roles[id];
    while (1) {
        mutex_lock(&lk);
        while (!can_print(role)) {
            cond_wait(&cv, &lk);
        }

        putchar(role); // Not lock-protected

        current = next(role);
        assert(current);
        cond_broadcast(&cv);
        mutex_unlock(&lk);
    }
}

13-应对并发 Bugs (动态程序分析：应对死锁、死局和死线)

运行时lock ordering检查（动态分析）

应对死锁，给锁编号，构建图

形成环，就有循环等待，就有可能死锁

对上锁的顺序进行一个闭包运算

同一行分配的锁就是同一个锁（近似）

data race

基本原理就是不同线程对同一变量，至少有一个是写操作

编译加-fsanitize=thread线程消毒器

12-并发 Bugs (死锁、数据竞争、原子性/顺序违反)

死锁产生的必要条件

• Atomicity violation，本应原子完成不被打断的代码被打断
• Order violation，本应按某个顺序完成的未能被正确同步

ABA

例如mysql里的解引用指针和将指针置为空的两个线程，也是一种数据

14-操作系统上的进程 (fork/execve/exit)

立即复制状态机

• 包括

  所有

  信息的完整拷贝

  • 每一个字节的内存
  • 打开的文件 (共享)
  • ……
  • 复制失败返回 -1
    • errno 会返回错误原因 (man fork)

如何区分两个状态机？

• 新创建进程返回 0
• 执行 fork 的进程返回子进程的进程号

系统调用的返回值放在rax中

1
2
3
4

f(){
	f | f &
}
f

printf缓冲区在每一个进程的内存里，fork会一起复制

遇到了粘贴时乱码问题

execve把当前的进程重置成一个可执行文件描述状态机的初始状态

第三个参数是环境变量

fork默认直接把环境变量会继承

strace的使用

./demo当前目录下的程序

15-(入侵) 进程的地址空间

状态机里有什么

registers

memory

gdb就可以暂停查看

1

fa1e0ff3

1

f3 0f 1e fa

在内存中显示以小端为首

地址空间是否可读写

在proc/pid/maps里都给出了，连续的一段一段的,每一段都给出了权限

1
2
3
4
5

564af047d000-564af0494000 r--p 00000000 08:20 31005                      /usr/bin/zsh
564af0494000-564af0552000 r-xp 00017000 08:20 31005                      /usr/bin/zsh
564af0552000-564af056d000 r--p 000d5000 08:20 31005                      /usr/bin/zsh
564af056d000-564af056f000 r--p 000ef000 08:20 31005                      /usr/bin/zsh
564af056f000-564af0575000 rw-p 000f1000 08:20 31005                      /usr/bin/zsh

更可读

1

pmap [pid]

创建不同的数组，分配的内存是不一样的

在栈上，在堆上，

不进入内核的系统调用gettimeofday(2)

从操作系统读数据

只有syscall指令可以改变地址空间（增删改）

看看man 5 proc手册

mmap可以分配内存，控制权限

python执行时遇到ModuleNotFoundError: No module named 'hexdump'0

原因是sudo执行时的环境变量不一样

wsl显示全为0

gdb调试，可以把要调试的程序的内存空间放进自己的内存空间

变速齿轮

hook，劫持相关代码

16-系统调用和 UNIX Shell (pipe; xv6 shell)

虚拟化，syscall

操作系统对象：文件和设备，

指针只能指向程序的内存空间

指向操作系统对象的指针（就是文件描述符），在linux中everything is a file

访问对象用指针open, close,read/write(解引用),lseek,dup等

复习指针

windows中文件描述符时handle，句柄

管道，IPC

写口，读口

管道是进程之间的同步机制

通信不仅可以用来传送数据，还可以用来同步

匿名管道

1

pipefd[0] refers to the read  end  of the  pipe.  pipefd[1] refers to the write end  of the  pipe.

fork复制时，管道也被复制了

指针也完成了浅拷贝

shell连接I/O设备和人

<(command)把命令变成文件

ctrl + z切换后台

jobs查看后台，fg %1切换后台到前台

shell可以调用syscall

17-C 标准库设计与实现 (_start; offsetof; printf; environ; malloc/free)

pipe,就是生产者消费者

看man 7 pipe

操作系统把硬件虚拟化成系统调用，对象+API

1

echo $(which musl-gcc)

19-可执行文件：静态链接和加载

execve（加载）把当前的进程重置成指定可执行文件的初始状态

可执行文件：一个状态机初始状态的数据结构

里面规定了加载该可执行文件后地址空间里该有什么数据（寄存器，代码段等）

状态：内存和寄存器

elf为了性能丧失了阅读友好性

magic number是什么

Magic number一般是指硬写到代码里的整数常量，数值是编程者自己指定的，其他人不知道数值有什么具体意义，表示不明觉厉，就称作magic number。

a.out

设计一个可读的可执行文件，需要什么（代码，符号，重定位）

FLE 加载器：只做一件事

• 将一段字节序列复制到地址空间中
  • 赋予可读、可写、可执行权限
• 然后跳转到 _start 执行

ELF 并没有多做多少

• 将多段字节序列复制到地址空间中
  • 分别赋予可读/可写/可执行权限
• 然后跳转到指定的 entry (默认为 _start) 执行

#!/bin/bash

1
2

#!A B C
THIS

argc[0] = A

argv[1] = B C

argv[2]该 程序的名称

20-动态链接和加载

libc.o静态链接

容易浪费空间

libc.so动态链接

生成位置无关代码，使用中间的table存放函数地址

借助编译器完成

用多个线程链接库，验证只有一个副本

是链接的同一份

地址空间是怎么分配的（虚拟内存）

动态链接（查表）

编译时，函数调用 = 查表(把函数调用替换成查表)

编译时，动态链接库调用 = 查表

1

call  *TABLE[printf@symtab] 

链接时，收集所有符号，“生成” 符号信息和相关代码：

1
2
3
4
5
6
7
8
9

#define foo@symtab     1
#define printf@symtab  2 
... 
void *TABLE[N_SYMBOLS]; 
void load(struct loader *ld) {    
    TABLE[foo@symtab] = ld->resolve("foo");    
    TABLE[foo@printf] = ld->resolve("printf");    
    ... 
} 

1
2
3
4
5

LOAD("libc.dl")
LOAD("libhello.dl")
IMPORT(hello)
IMPORT(exit)
EXPORT(_start)

gdb过程dlbox main.s

加载符号表，递归调用dlopen,调用libc.dl，导出符号，

putchar,exit填到全局的符号表，

解析第二个符号，libhello.dl

….

动态解析hello,hello不在main.dl里，是?

调用dlsym检查符号表，找到hello把地址填入符号表

执行DSYM(exit)

1

#define DSYM(sym)   *sym(%rip)

找到空位把符号填入符号表

前面的存放地址和函数名的表项，就是 GOT (Global Offset Table)

因为call 的偏移量是64位，跳不到远处

所以使用plt,作为中转，先跳到plt中，plt中存放GOT对应函数的地址

再次跳转到对应函数

数据的链接，plt怎么解决数据链接的问题

get_x会查表

get_y直接得到地址（hidden）

编译器默认extern变量来自另外一个共享库单元（保守）

gpt对objdump反汇编的分析

总结

1. 变量 x：
   • 默认可见性（visibility("default")）。
   • 使用 mov 指令，通过符号表获取地址。
   • 可被其他模块或共享库访问。
2. 变量 y：
   • 隐藏可见性（visibility("hidden")）。
   • 使用 lea 指令，直接计算地址，无需符号表查找。
   • 仅在当前模块内部可见，无法被外部访问。
3. 性能影响：
   • 隐藏符号（y）链接效率更高，因为不需要符号表查找。
   • 默认可见性符号（x）灵活性更强，但动态链接时可能会引入额外开销。

23-处理器调度 (xv6 上下文切换；处理器调度：机制和策略)

由用户态，执行syscall

跳转到内核态代码，寄存器保存，切换页表和栈

调度策略

1

taskset -c 3 nice -n 19 yes > /dev/null & taskset -c 3 nice -n 9 yes > /dev/null 

nice值相差10，占用cpu时间相差1倍

上下文切换是机制，策略是选择哪个进程执行

动态优先级，CPU密集型的优先级逐渐降低，交互型的优先级逐渐增加

动态优先级实现的虚拟时间是什么原理，为什么“好人”和“坏人”会相差几倍

进程的nice值越小（优先级越高），权重越大，在实际运行时间相同的情况下，虚拟运行时间越短，进程累计的虚拟运行时间增加得越慢，在红黑树中向右移动的速度越慢，被调度器选中的机会越大，被分配的运行时间相对越多。随着优先级高进程的虚拟运行时间增长，低优先级的进程也会有机会被调度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/*
 * Nice levels are multiplicative, with a gentle 10% change for every
 * nice level changed. I.e. when a CPU-bound task goes from nice 0 to
 * nice 1, it will get ~10% less CPU time than another CPU-bound task
 * that remained on nice 0.
 *
 * The "10% effect" is relative and cumulative: from _any_ nice level,
 * if you go up 1 level, it's -10% CPU usage, if you go down 1 level
 * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
 * If a task goes up by ~10% and another task goes down by ~10% then
 * the relative distance between them is ~25%.)
 */
static const int prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

Linux CFS调度器 vruntime 的计算_linux vruntime-CSDN博客

CFS，完全公平调度，记录每个进程运行时间，每次都切换到运行时间最少的进程。

红黑树