Modern Operating System (II)

同步原语

文件系统

8 同步原语

同步原语synchronization primitive：正确高效处理多线程多核等的同步问题的抽象
- 将海量数据根据核心数量划分，从而能够在同一时间分配子任务到多个核心上并行处理，并最终收集这些子任务的处理结果。
- 意味着对共享资源的并发访问。
- 生产者：处理这些划分数据的线程
- 消费者：收集处理结果的线程
- 多核CPU：任务可以被划分给不同CPU核心上的线程同时处理
- 单核CPU：多线程可能营造每个线程在单独CPU上的“假象”

互斥锁

竞争冒险race hazard：程序的正确性依赖于特定的执行顺序的情况
互斥访问mutual exclusion：任意时刻只允许至多一个线程thread访问的方式
临界区critical section：保证互斥访问共享资源的代码区域
- 在同一时刻，至多只有一个线程可以执行临界区中的代码
- 在临界区内，一个线程可以安全地对共享资源进行操作
临界区问题：如何通过设计协议来保证互斥访问临界区的问题
- 适用范围
  - 多核并行，多核多线程
  - 单核多线程
- 流程
  1
  2
  3
  4
  5
  while True:
  --- 申请进入临界区 ---
  临界区
  --- 标识退出临界区 ---
  other(); # 其他代码
- 软件实现的要求
  
  算法设计
  1. 互斥访问
  2. 有限等待
  3. 空闲让进
- 硬件实现
  
  （单核）关闭中断，但不适用于多核
  - 线程thread进入临界区关闭中断，离开临界区后再开启中断

软件实现：皮特森算法

经典皮特森算法只能用于两个线程的情况

Micha Hofri扩展了皮特森算法，使其能够被使用与任意数量的线程

皮特森算法要求CPU严格按照程序顺序执行访存操作

bool flag[2] = { false };// flag[0]->thread_0 ; flag[1]->thread_1
int turn;

--- Thread 0 ---
while(true) {
  flag[0] = true;
  turn = 1;
  while (flag[1]==true && turn==1);
  critical_section();//临界区
  flag[0] = false;
  other_code();//其他代码
}

--- Thread 1 ---
while(true) {
  flag[1] = true;
  turn = 0;
  while(flag[0]==true && trun == 0);
  critical_section();//临界区
  flag[1] = false;
  other_code();//其他代码
}

软硬件结合：原子操作 –> 互斥锁

原子操作atomic operation：指不可被打断的一个或一系列操作，要么这一系列指令都执行完成，要么这一系列指令一条都没有执行，不会出现执行到一半的状态。

常见原子操作：比较与置换Compare-And-Swap, CAS，拿取并累加Fetch-And-Add, FAA

CAS和FFA类C代码的实现（只是用来说明功能，C代码本身不具备原子性）

int CAS(int *addr, int expected, int new_value) {
  if (*addr == expected) *addr = new_value;
  else expected = *addr;
  return expected;
}
int FFA(int *addr, int add_value) {
  int tmp = *addr;
  *addr = tmp + add_value;
  return tmp;
}

更新遗失loss update

Intel x86-64平台内联汇编实现原子操作

Intel平台通过lock前缀来实现操作的原子性

atomic_CAS解析
1
2
3
4
if *addr == expected:
*addr = new_value
else:
expected = *addr
比较地址addr处的值*addr和expected，如果相等：*addr = new_value；否则：expected = *addr

int atomic_CAS(int *addr, int expected, int new_value) {
  asm volatile("lock cmpxchg %[new], %[ptr]"
              :"+a"(expected), [ptr] "+m"(*addr)
              :[new] "r"(new_value)
              :"memory");
  return expected;
}

ARM平台基于Load-Link/Store-Conditional (LL/SC)指令组合‘
- ARMv8.1支持了LSE(Large System Extension)，可以使用单条指令完成原子操作
  - Load-Link：
    - 监视器monitor

互斥锁mutex lock

自旋锁spin lock：基于原子的CAS实现

此处不考虑访存操作乱序的问题

满足 2 项，无法确保公平性

互斥访问

有限等待

空闲让进

实现简单，低时延高效率

异构（ARM移动CPU大小核架构，小核运行频率低与大核竞争不易拿到锁），无法保证公平性

# implementation of spin lock by C language
# lock == 1 : 有人拿了锁
# lock == 0 : 该锁空闲

void lock_init(int *lock) {
  *lock = 0;//初始化自旋锁
}

void lock(int *lock) {
  while(atomic_CAS(lock, 0, 1) != 0);//循环忙等
--+
  +-> 判断lock是否空闲,如果空闲,则上锁;不空闲,则一直在循环中等待
  +-> if lock==0 -> lock=1,return 0
  +-> if lock==1 -> expected=lock=1,return 1
--+
}

void unlock(int *lock) {
  *lock = 0;
}

排号自旋锁（或排号锁）ticket lock：利用原子的FFA实现

按照竞争者申请锁的顺序传递锁，锁的竞争者组成了FIFO等待队列

## 此处没有考虑 integer overflow
struct lock {
  volatile int owner;//当前lock持有者序号
  volatile int next;//下一个要分发lock的竞争者的序号
}

void lock_init(struct lock *lock) {
  //初始化排号锁
  lock->owner = 0;
  lock->next = 0;
}

void lock(struct lock *lock) {
  //拿取自己的序号
  volatile int my_ticket = atomic_FAA(&lock->next, 1);// 取号排队
  while (lock->owner != my_ticket);//循环忙等,如果
}

void unlock(struct lock*lock) {
  //传递给下一个竞争者
  lock->owner++;
}

条件变量

循环等待busy looping：如剩余资源为0时，producer会陷入循环等待/循环忙直到consumer释放空位。
- 需要挂起/唤醒机制 —> 避免busy looping导致CPU资源浪费
- 引入条件变量condition variable
Condition Variable 提供了两个接口：cond_wait and cond_signal
- cond_wait ：用于挂起当前process
- cond_signal：用于唤醒等待在该condition variable上的线程thread

生产者消费者问题：基于condition variable

使用互斥锁保护计数器：empty_cnt_lock保护empty_slot，filled_cnt_lock保护filled_slot

使用条件变量时必须配合mutex lock使用

cond_wait在挂起当前thread的同时，该互斥锁mutex lock会被原子地释放

挂起的线程被唤醒后，其会在cond_wait返回之前重新获取互斥锁mutex lock

int empty_slot = 5; ---> 公共变量,由锁 empty_cnt_lock 保护
int filled_slot = 0; ---> 公共变量,由锁 filled_cnt_lock 保护

struct cond empty_cond; ---> 条件变量:生产者 --> 缓冲区无空位
struct lock empty_cnt_lock;
struct cond filled_cond; ---> 条件变量:消费者 --> 缓冲区无数据
struct lock filled_cnt_lock;

void producer(void) {
    int new_msg;
    while(true) {
        new_msg = produce_new();
//        
        lock(&empty_cnt_lock);
        	while(empty_slot==0)
                cond_wait(&empty_cond, &empty_cnt_lock); 
        			--> 当有新的空位产生时候,消费者会利用cond_signal操作唤醒等待在empty_cond上的
                     --> 生产者
        	empty_slot--;
        unlock(&empty_cnt_lock);
        
        buffer_add_safe(new_msg);
        
        lock(&filled_cnt_lock);
        	filled_slot++;
        	cond_signal(&filled_cond); --> 唤醒等待的消费者
        unlock(&filled_cnt_lock);
  }
}
void consumer(void) {
    int cur_msg;
    while(true) {
        lock(&filled_cnt_lock);
        	while(filled_slot==0)
                cond_wait(&filled_cond, &filled_cnt_lock);
        	filled_slot--;
        unlock(&filled_cnt_lock);
        
        cur_msg = buffer_remove_safe();
        
        lock(&empty_cnt_lock);
        	empty_slot++;
        	cond_signal(&empty_cond);
        unlock(&empty_cnt_lock);
    }
}

条件变量的实现

struct cond {
    struct thread *wait_list; --> 记录等待在该条件变量上的线程
}

void cond_wait(struct cond *cond, struct lock*mutex) {
    list_append(cond->wait_list, thread_self()); --> 将当前线程thread_self()加入等待队列
    atomic_block_unlock(mutex); --> 原子地挂起并同时释放锁,这两步必须是原子的
             --> 此时已经挂起并且释放了锁
             --> 这个过程应由OS辅助完成,Linux kernel 通过 futex 机制实现该功能
        
    lock(mutex); --> 重新获得互斥锁
                 --> 该步骤是接收到cond_signal唤醒挂起的线程后紧接着执行的
}

void cond_signal(struct cond *cond) {
    if(!list_empty(cond->wait_list))
        wakeup(list_remove(cond->wait_list)); --> OS提供的唤醒服务
}

void cond_broadcast(struct cond *cond) {
    while(!list_empty(cond->wait_list))
        wakeup(list_remove(cond->wait_list));
} --> 条件变量一般提供广播操作用来唤醒所有等待在条件变量上的线程`thread`

信号量

信号量semaphore：在不同线程之间充当信号灯，根据剩余资源数量控制不同线程的执行或者等待

除了初始化，只支持两种操作用来更新，信号量又叫做PV原语
- init：初始化工作，即赋予信号量semaphore初始值
- P (荷兰语 Proberen 检验)：wait
- V (荷兰语 Verhogen 自增)：signal

信号量用来【辅助控制多个线程访问 有限数量 的 共享资源 的】，只允许三个不同的操作对齐值进行修改init, wait(P) and signal(V)

信号量的角度：
- 消耗共享资源的线程：wait –> 等待资源就绪
- 产生/释放共享资源的线程：signal –> 通知资源就绪，即被释放的资源的量
资源角度
- 对于producer【共享资源】是空闲空间free space
- 对于consumer【共享资源】是已占用的空间

生产者消费者问题

sem_t empty_slot;
sem_t filled_slot; --> 两个信号量
void producer(void) {
    int new_msg;
    while(true) {
        new_msg = produce_new();
        wait(&empty_slot); --> P
        	buffer_add_safe(new_msg);
        signal(&filled_slot); --> V
    }
}
void consumer(void) {
    int cur_msg;
    while(true) {
        wait(&filled_slot); --> P
        	cur_msg = buffer_remove_safe();
        signal(&empty_slot); --> V
        	consume_msg(cur_msg);
    }
}

信号量的实现

只有一个资源被释放时，同时通知多个thread是不明智的策略，应让多余的thread挂起并放弃CPU
使用condition variable和mutex lock实现semaphore
该实现不能保证thread按照调用wait的顺序依次拿到资源，但并不会破坏对有限等待的保证

struct sem {
    int value; --> value>=0,无thread等待,value=剩余资源数量
          --> value<0,有thread等待,|value|=number of threads which are waiting
    int wakeup; --> 有线程等待时可用资源数量,亦即应该唤醒的thread数量
          --> wakeup>=0
    struct lock sem_lock;
    struct cond sem_cond;
}

void wait(struct sem*s) {
    lock(&s->sem_lock);//上锁
    s->value--;

---------------- if value>=0,有空闲资源,wait执行完毕
    	if(s->value<0) {
            do {
                cond_wait(&s->sem_cond, &s->sem_lock);
            }while(s->wakeup==0); --> do...while 语句很关键,先排队后检查
               					--> 避免了某一线程调用完signal
                				--> 立即调用wait导致其他thread进入无线等待中
            s->wakeup--;
        }
---------------- if value<0,value不能表示当前可用资源数量,需要检查wakeup;
---------------- if wakeup>0,有可用资源(只不过需要排队);
---------------- if wakeup==0,没有可用资源,此时需要挂起

    unlock(&s->sem_lock);
}

void signal(struct sem *s) {
    lock(&sem_lock);
    	s->value++;
    	if (s->value<=0) { 
--> 当s->value<=0时(还是已经++过的value值,说明value原本是负数)
--> 此时有thread等待,因此添加的资源也体现在wakeup上
--> 正因为此时有thread等待,所以增加wakeup的值并唤醒这些正在等待的
--> 线程的其中一个来利用新增加的资源
            s->wakeup++;
            cond_signal(&s->sem_cond); 
--> wakeup资源增多,即唤醒之前wakeup=0导致的挂起等待
--> 至少wakeup=1,因此之前因为wakeup=0挂起的线程也被唤醒了
        }
    unlock(&sem_lock);
}

summary

信号量：协调多个线程对一系列共享资源的有序操作
信号量与互斥锁：
- 区别较大
条件变量与信号量：
- 信号量是由条件变量，互斥锁，以及计数器实现的
- 计数器是信号量的核心，用于表示当前可用资源的数量
条件变量与互斥锁：
- 互斥锁mutex lock：解决临界区问题，保证互斥访问共享资源
- 条件变量condition variable：提供【挂起 / 唤醒】机制，避免循环等待busy looping，节省CPU资源
- 二者搭配使用

读写锁

对共享资源的读操作是不互斥的
只需要保证写共享数据的线程和读共享数据的线程不能同时执行即可，读写锁reader writer lock即解决此问题的一种同步原语synchronization primitive
critical seection：
- 读临界区：可写，可读
- 写临界区：（别的）不可写，不可读

reader writer lock使用

struct rwlock lock;
char data[SIZE];

void reader(void) {
    lock_reader(&lock);
    read_data(data); --> 读临界区
    unlock_reader(&lock); 
}

void writer(void) {
    lock_writer(&lock);
    update_data(data); --> 写临界区
    unlock_writer(&lock);
}

reader writer lock实现

倾向性：

偏向读者的读写锁：读者优先，读者直接进入，写者等待所有读者离开临界区之后再进入临界区

reader与writer互斥

writer与writer互斥

偏向写者的读写锁：写者优先，即读者写者同时准备进入时，先等待之前所有读者离开临界区，之后写者进入，写者离开后读者再进入

有新的writer到达后阻塞新的reader

偏向读者reader的读写锁

原则：只要有一个reader就把writer的给锁上

---> 偏向读者reader的读写锁 <---
---> reader和writer不共享锁 <---
struct rwlock {
    int reader_cnt; --> 记录当前reader数
    struct lock reader_lock; --> 对reader_cnt进行更新的互斥锁
    struct lock writer_lock;
};

void lock_reader(struct rwlock *lock) {
    lock(&lock->reader_lock);
    	lock->reader_cnt ++;
    	if(lock->reader_cnt==1) -->第一个读者,即有读者时就不能有写者进入临界区
            lock(&lock->writer_lock); -->因此锁住写者writer,阻塞后续writer
    unlock(&lock->reader_lock);
} --> 可以有多个reader同时进入critical section,但一旦有writer就需要等待临界区的读者全部离开后才可以进入临界区

void unlock_reader(struct rwlock *lock) {
    lock(&lock->reader_lock);
    	lock->reader_cnt--;
    	if(lock->reader_cnt==0) --> 最后一个读者
            unlock(&lock->writer_lock);
    unlock(&lock->reader_lock);
}

void lock_writer(struct rwlock *lock) {
    lock(&lock->writer_lock);
}

void unlock_writer(struct rwlock *lock) {
    unlock(&lock->writer_lock);
}

偏向写者writer的读写锁

外锁rwlock结构体内部借助了mutex lock来实现对外锁本身元数据reader_cnt和has_writer的保护

锁中的精华部分依然在条件变量的应用上

cond_wait

cond_signal

读者不用等待读者，只需要等待写者 —> 一个while

写者既要等待读者，又要等待写者 —> 两个while

等reader就用reader_cond；等writer就用writer_cond

释放unlock时需要唤醒等待自己的线程

reader unlock –> 唤醒一个等待自己的writer –> cond_signal

writer unlock –>唤醒所有等待自己的reader和writer –> cond_broadcast

---> 偏向读者writer的读写锁 <---
---> reader和writer共享锁 <---
struct rwlock {
    volatile int reader_cnt; --> 记录当前reader数
    volatile bool has_writer; --> 表示当前是否有writer到达
        					--> reader_cnt和has_writer属于metadata
    struct lock lock; --> 共享lock,要求读者和写者在操作元数据前得到该锁
    struct cond reader_cond;
    struct cond writer_cond;
}

void lock_reader(struct rwlock *rwlock) {
    lock(&rwlock->lock);
    	while(rwlock->has_writer==true)
            cond_wait(&rwlock->writer_cond, &rwlock->lock);
   						   --> 该reader进入之前只要有writer,或者
                             --> 有writer排队期望得到lock(即使没有进入临界区)
                             --> 就挂起reader
    	rwlock->reader_cnt++;
    unlock(&rwlock->lock);
}

void unlock_reader(struct rwlock *rwlock) {
    lock(&rwlock->lock);
    	rwlock->reader_cnt--;
    	if (rwlock->reader_cnt == 0)
            cond_signal(&rwlock->reader_cond);
						--> 由于reader和writer是冲突的因此
                          --> 要等到
    unlock(&rwlock->lock);	
}

void lock_writer(struct rwlock *rwlock) {
    lock(&rwlock->lock);
    	while(rwlock->has_writer == true)
            cond_wait(&rwlock->writer_cond, &rwlock->lock); --> 等待前面的writer
    	rwlock->has_writer = true; -->提前声明,避免后续的reader抢占
    	while(rwlock->reader_cnt>0)
            cond_wait(&rwlock->reader_cond, &rwlock->lock); --> 等待前面的reader
    unlock(&rwlock->lock);
}

void unlock_writer(struct rwlock *rwlock) {
    lock(&rwlock->lock);
    	rwlock->has_writer = false;
    	cond_broadcast(&rwlock->writer_cond); 
    				--> 广播释放所有的挂起在writer_cond上的thread
                      --> 包括等待ta的所有writer和所有reader
    unlock(&rwlock->lock);
}

summary

偏向reader：提高读者reader之间的并行度，但写延迟较高
偏向writer：写延迟低，读者reader并行度低

RCU

读写锁允许多个读者同时进入读临界区，但写者会阻塞读者，读者仍然需要在关键路径上添加读者锁，造成性能开销

目的：让读者再写者更新时，要么读到旧的值，要么读到新的值，而不能观察到任何中间结果

RCU (Read-Copy Update)：
- 允许多个reader进入critical section
- writer不会阻塞reader
- reader不需要使用额外的同步原语synchronization primitive保护reader critical section
主流CPU提供对【地址对齐】的单一读写操作的原子性保证
- ARM中被称为single copy atomicity单拷贝原子性
- 支持【位宽】一般与CPU位宽一致
- 64-bitCPU保证【地址对齐的64位数据】的读写操作的原子性：如0x5118,0x6730，即二进制下后三位均为0，16进制下最低四位为8或0
- 写者writer需要更新的数据大小往往超过64-bit限制，为此RCU引入了一种【订阅 / 发布】机制，利用对64-bit pointer的读写原子性，让writer能够【原子的】更改任意大小的数据
【订阅 / 发布】机制
- 对64-bit pointer的更新操作是可以由hardware保障【原子性】的
- 【发布】接口：写，rcu_assign_pointer
- 【订阅】接口：读，rcu_dereference
- 因为处理器可能会【让没有依赖关系的访存操作】乱序执行，但【发布/订阅】可以保证读写按照应当出现的顺序执行，即【将保证顺序的操作打包成两个接口，便于开发者使用】
通过【订阅 / 发布】机制，读者和写者可以【互不阻塞】地执行critical section的内容

宽限期grace period：为了确定何时能回收资源（由于读写互不阻塞了）

API: synchronize_rcu用来阻塞写者到宽限期结束

pointer: [旧值] --update(更新)--> [新值] --free(回收旧值)--> [旧值无效,新值有效]
grace period: 从writer更新指针到最后一个可能观察到旧值的reader离开的时间段
pointer update时,此时有一些reader进入critical section,它们是有可能观察到旧值的,
因此为了避免旧值释放后reader读取旧值会产生危险,需要等这些可能读取旧值的reader全部
离开critical section后才能释放旧值

管程

线程安全thread-safe：某个函数、函数库在多线程环境中被调用时，能够正确地使用synchronization primitive保护多个thread对共享变量的访问与修改
管程Monitor：包含两部分内容：一部分为共享的数据，一部分是操作共享数据的函数，（data + function适合封装成class，因此管程monitor一般用于面向对象的程序中）monitor保证在同一时刻最多只有一个操作者能够进入管程的保护区域访问共享数据

同步带来的问题

死锁

当有多个（两个及以上）线程为有限的资源竞争时，有的线程就会因为在某一时刻没有空闲资源而陷入等待。
死锁deadlock：这一组中的每一个线程都在等待组内其他线程释放资源从而造成无限等待
必要条件：
- 互斥访问
- 持有并等待
- 资源非抢占
- 循环等待

死锁避免算法

银行家算法（By Edsger Dijkstra），又称为【安全性检查】

每次分配给线程新的资源时都进行安全性检查

安全性检查即假设满足上分配，在分配后的状态下寻找满足安全性的线程：分配给所有所需资源并假设执行完后并释放所需资源（标记执行结束），继续寻找下一个满足的线程，由此得到一个安全序列。如果存在【未标记结束】的线程且该线程处于【非安全状态】（无法满足其资源分配需求），那么就是不安全的；否则，是安全的。

只有在安全性检查通过之后，线程的请求才能够得到满足。

安全性状态就意味着系统【假设满足当前线程分配需求】后，可以找到一个【安全序列】。

In system, there are [M] categories of resources and [N] threads.
Available[M]; 全局可利用资源,每一种资源的当前可用量;
Max[N][M]; 最大需求量;
Allocation[N][M]; 已分配的;
Need[N][M]; 还需要的;

活锁

活锁livelock：基于【不允许持有并等待】，即一旦发现要等待，就释放所有持有的资源，但可能造成【动态死锁】（取决于调度器），即活锁。

优先级反转

优先级反转priority inversion：由于同步导致线程执行顺序违反预设优先级的问题。

1
2
3

priority: A > B > C
* C持有锁, A等待C的锁, 此时B抢占CPU导致A被B阻塞
* 反转的不是C和A, 而是指A在等锁的过程中, 与该锁无关且优先级低于A的线程抢占了CPU使得其与A的优先级产生的反转

实时操作系统中，priority inversion造成后果十分严重
为了避免优先级反转，最直接的方法是使用【不可抢占临界区协议Non-preemptive Critical section Protocolm NCP】
现代操作系统中，最常采用的方法是【优先级继承协议Priority Inheritance Protocol, PIP】
- 高优先级等待锁时，会使锁的持有者继承其优先级，从而避免该锁的临界区被低优先级的任务打断
【优先级置顶协议Priority Ceiling Protocol, PCP】：将获取锁的线程的优先级置位可能竞争该锁的线程中的最高优先级（需要由线程提前告知操作系统）
- 即时优先级置顶协议Immediate PCP, IPCP：拿到锁时即将优先级置为【可能】竞争该锁的线程中的最高优先级
- 原生优先级置顶协议Original PCP, OPCP：在真的有其他的线程竞争该资源时提升优先级
NCP和IPCP实现难度小
PIP和OPCP实现难度大，需要监视已被获取的锁，在其他线程尝试获取该锁时提升拥有者的优先级

Linux中的futex

futex (Fast User-space muTEX)机制：

提出背景：原condition variable是与一个基于busy looping的mutex lock搭配使用的，条件变量是为了避免【循环等待】而提出的，但其此前依赖的【互斥锁】是基于【循环等待】实现的；如果在【互斥锁】为了优化而避免【循环等待】，则其实现中需要引入【条件变量】，就会造成实现复杂、开销很大的情况

因此，Linux采用futex机制实现的互斥锁
1. 避免互斥锁中的【循环等待】
2. 实现条件变量Condition Variable等各类同步原语
  - 如Condition Variable的实现里的atomic_block_unlock(mutex); --> 原子地挂起并同时释放锁,这两步必须是原子的是通过嫁接到futex_wait接口实现的
- 竞争程度较低时，直接使用【原子操作】加锁
- 竞争程度较高时，APP能够通过syscall挂起并等待后续【锁持有者】唤醒
  - 而原始lock是通过【循环等待】实现的，这里【不依赖】条件变量来在lock内部实现【挂起 / 唤醒】
  - OS会为每个等待的uaddr维护一个FIFO队列，当不同线程调用futex_wait等待在相同的uaddr上时，线程会被加入该队列中，等待接下来被futex_wake唤醒

futex接口（简化版）

futex_wait(uaddr, val); --> 等待
    * 如果地址[uaddr]上的值与[val]相等,挂起
futex_wake(uaddr); --> 唤醒
    * 唤醒之前因futex_wait在[uaddr]上挂起的线程

futex实现lock和unlock

void futex_wait(int *uaddr, int val);
void futex_wake(int *uaddr);

struct lock {
    int val;
    int waiters;
}

void lock(struct lock *lock) {
    while(atomic_CAS(&lock->val, 0, 1) != 0) { 
        		--> 如果lock->val == 0, lock->val=1, return 0
                    --> 空闲,变占用,返回空闲状态0
                 --> 如果lock->val == 1, return 1
                    --> 占用,返回占用状态1
        /*lock非空闲,进入循环*/
        atomic_FAA(&lock->waiters, 1);
        futex_wait(&lock->val, 1); --> 进入kernel尝试挂起
            --> kernel会为每一个等待uaddr维护一个FIFO Queue
            --> 将该线程插入kernel的 Waiting Queue
            --> 等待接下来被 futex_wait唤醒
        atomic_FAA(&lock->waiters, -1); --> 唤醒后等待着减一
    }
}

void unlock(struct lock *lock) {
    lock->val = 0;
    if (lock->waiters != 0)
        futex_wake(&lock->val);
}

Linux保证了不同futex操作的互斥性，多个futex操作之间只可能先后发生

条件变量（简化版）

[7]和[8]应该是绑定执行即【原子的】，此处通过futex机制，如果[7]结束后有线程进入cond_signal即改变了cond->value，此时通过新旧值对比，如果相同，futex_wait挂起等待满足原子性，如果不同则重新获得锁（相当于什么都没有发生）返回，由此实现要么[7] and [8]都一起执行，要么都不执行的原子性

struct cond {
    unsigned value;
}

void cond_wait(struct cond *cond, struct lock *mutex) {
    unsigned local = cond->value;
    unlock(mutex);
    futex_wait(&cond->value, local);//如果
    lock(mutex);
}

void cond_signal(struct cond *cond) {
    cond->value += 1;//更新
    futex_wake(&cond->value);
}

9 文件系统

机械硬盘Hard Disk Drive (HDD)、固态硬盘Solid-State Drive (SSD)
文件数据file data、文件元数据file metadata
块设备block device
块block：块设备读写的最小单元，大小一般为512字节或4KB
虚拟文件系统Virtual File System (VFS)
- 页缓存page cache
- inode缓存icache
- 目录项缓存dcache
inode : index node
文件类型（一部分）
- 常规文件regular file
- 目录文件directory file
- 符号链接文件symbolic link file
- FIFO文件：以队列形式传递数据，又称命名管道
- 套接字文件：用于传递数据，比FIFO更加灵活
- 字符设备文件
- 块设备文件
目录：一种特殊的类型的文件（即目录本身也是一种文件），记录了文件名到inode号的映射
文件名不是文件的metadata
硬链接hard link
符号链接（软链接）soft link
- ln -s file slink 为file创建名为slink的软链接
- 符号链接文件保留的是一个字符串，表示一个文件路径
- 只支持读操作
文件系统的存储布局

只有文件数据区域被用来存放应用程序的数据，因此文件系统所显示的可用大小 < 存储设备总容量
- 超级块super block
- 块分配信息
  
  标记文件数据块区域各个块的使用情况
  - 位图bitmap
- inode分配信息
  
  标记**inode表的各个inode**的使用情况
- inode表
  - 以数组array的形式保存了整个文件系统中所有的inode结构
  - inode号：inode在此表中的索引
  - 文件系统中对inode的引用只需要使用inode号即可，无需保存inode结构在存储设备中的偏移量offset
  - inode表的大小在文件系统创建时已经固定，因此文件系统所能保存的最大文件数量受此限制
- 文件数据块
虚拟文件系统VFS (Virtual File System)：对多种File System协调，允许它们在同一个OS上共同工作
- Linux VFS (Virtual Filesystem Switch)
  - VFS超级块
  - VFS的inode：VFS维护了一个inode缓存（icache），该缓存使用Hash表保存了OS的所有的inode的结构
  - VFS的文件数据管理
    - 基数树radix tree
  - VFS的目录项
    - VFS在内存中为目录项维护了一个缓存，目录项缓存（dcache）

VFS和文件系统的交互

1	VFS ---(read-modify-write)--- File System

Linux VFS 定义文件系统应提供的方法的形式：函数指针function pointer

>>>回调函数
函数指针作为某个函数的参数,函数指针变量可以作为某个函数的参数来使用的，回调函数就是一个通过函数指针调用的函数。简单讲：回调函数是由别人的函数执行时调用你实现的函数。
>>>以下是来自知乎作者常溪玲的解说：
你到一个商店买东西，刚好你要的东西没有货，于是你在店员那里留下了你的电话，过了几天店里有货了，店员就打了你的电话，然后你接到电话后就到店里去取了货。在这个例子里，你的电话号码就叫回调函数，你把电话留给店员就叫登记回调函数，店里后来有货了叫做触发了回调关联的事件，店员给你打电话叫做调用回调函数，你到店里去取货叫做响应回调事件。

Linux and its VFS : 实现文件读写等操作(OS(kernel) --- APP(user))

路径解析

open：文件路径 —> 文件描述符file descriptor
- open —libc—> SYS_open（系统调用）—> VFS
- VFS对路径进行拆分得到一系列文件名（包含目录名），如果是绝对路径就从根目录开始查找，如果是相对路径，就从当前.目录（即工作目录）开始查找，查找过程中包括一系列权限检查，是否为目录检查等检查过程。
  1
  2
  3
  # 应用程序可以使用 getcwd 和 chdir 获取和修改当前工作目录
  getcwd
  chdir
- 路径解析完成后得到一个inode，但不直接返回给app，而是在inode上添加了一层抽象，即文件描述符file descriptor
文件描述符

实际上是一个integer，由VFS进行维护
- VFS为每一个process维护一个文件描述符表file descriptor table，以文件描述符fd (file descriptor)为索引index，保存一组文件描述结构
相对路径：不以/开头的路径，均为相对路径
页缓存：Linux kernel 将读缓存和写缓冲区的功能合并起来管理，称为页缓存

持久化和性能权衡之产物：文件系统将是否使用页缓存机制的判断和选择权交予APP

APP可以通过打开文件时附带O_DIRECT标志，提示文件系统不要使用页缓存 –> 直接I/O

页缓存 –> 缓存I/O
```
    flowchart 
        meta1(从存储设备中读取数据\n创建新的缓存页) --> clean_page((干净页))
        meta2(缓存页被回收) --- clean_page
        clean_page -->|修改缓存页中的数据| dirty_page((脏页))
        dirty_page -->|页中数据被写会存储设备| clean_page
```
Linux 在页缓存的基础上实现了文件的内存映射机制

文件内存映射：mmap接口

;--- POSIX 文件内存映射接口 ---;

/* 提供映射的目标虚拟地址, 长度, 属性, 标志位, 文件描述符, 起始位置在文件中的偏移量 */
void *mmap(void *addr, size_t len, int prot, int flags, int fildes, off_t off);

/* msync是请求VFS对指定内存映射区域进行同步写回操作 */
int msync(void *addr, size_t len, int flags);

/* 当所有操作完成之后, APP可以调用munmap, 移除指定的虚拟内存地址区域上的内存映射 */
int munmap(void *addr, size_t len);

挂载mounting是指由操作系统使一个存储设备（诸如硬盘、CD-ROM或共享资源）上的电脑档案和目录可供用户通过计算机的文件系统访问的一个过程。一般来说，当计算机关机时，每个已挂载存储都将经历一次卸载，以确保所有排队的数据被写入，并保证介质上文件系统结构的完整性。
- linux操作系统将所有的设备都看作文件，它将整个计算机的资源都整合成一个大的文件目录。我们要访问存储设备中的文件，必须将文件所在的分区挂载到一个已存在的目录上，然后通过访问这个目录来访问存储设备。挂载就是把设备放在一个目录下，让系统知道怎么管理这个设备里的文件，了解这个存储设备的可读写特性之类的过程。
- 我们不是有/dev/sdb1吗，直接对它操作不就行了？这不是它的目录吗？
- 这不是它的目录。虽然/dev是个目录，但/dev/sdb1不是目录。可以发现ls/dev/sdb1无法执行。/dev/sdb1，是一个类似指针的东西，指向这个分区的原始数据块。mount前，系统并不知道这个数据块哪部分数据代表文件，如何对它们操作。
- 这时提问者使用了 mount /dev/sdb1 ~/Share/ ，把新硬盘的区sdb1挂载到工作目录的~/Share/文件夹下，之后访问这个~/Share/文件夹就相当于访问这个硬盘2的sdb1分区了。对/Share/的任何操作，都相当于对sdb1里文件的操作。这也就是挂载的作用：使用户可以访问这个分区（磁盘）。
每个文件系统都有一个根目录，但应用程序所使用的路径通常只有一个根目录。
Linux 的VFS维护一个统一的VFS文件系统树，OS启动时会有一个根文件系统，如FS0
- 在根文件系统的基础上，其他文件系统可以被自由地挂载到VFS的任何一个目录之上，这些作为挂载目标的目录，便称为挂载点
- Linux通过三种结构体vfsmount (挂载文件系统信息)、mountpoint (挂载点信息)、mount (挂载文件系统结构体, 且包含了前两种)，其VFS可以灵活地挂载多种文件系统，让各种不同的文件系统可以在相同的操作系统下工作。
伪文件系统pseudo file system：Linux实现的一些不用于保存文件数据的文件系统
- 作用之一：允许用户user态应用程序通过读取文件的方式对读取内核提供的信息，并通过写入文件的方式对操作系统内核进行配置和调整
FAT文件系统
- FATFile Allocation Table：文件分配表
- 簇cluster（对应于之前所说的块block）：逻辑存储单元，每个簇对应于物理存储上的一个或多个存储扇区sector
- 簇号：每个簇对应的地址
- FAT是一个由簇号组成的数组，且FAT中记录的簇号，为逻辑上的下一个簇的簇号（类比单链表）
NTFSNew Technology File System
- 主文件表MFT (Master File Table)
- 稀疏文件sparse file：存在大片连续为0（所有比特位均为0）的数据的文件
FUSE与用户态文件系统
- FUSE模块：为了能让其他应用程序使用用户态文件系统提供的服务，宏内核中需要加入支持相应功能的模块，比较流行和常用的是FUSE模块和框架
  - 存在问题：性能较差

Ganliber's Home

OS Notes Part(II)

Modern Operating System (II)

8 同步原语

互斥锁

条件变量

信号量

summary

读写锁

summary

RCU

管程

同步带来的问题

死锁

死锁避免算法

活锁

优先级反转

Linux中的futex

9 文件系统