Modern Operating System (I)

前几章内容暂省略

内存管理

进程与线程

操作系统调度

进程间通信

4 内存管理

转址旁路缓存TLB (Translation Lookaside Buffer)
- TLB命中：TLB hit
- TLB未命中：TLB miss
AArch64 (based on ARMv8.0) 架构：4级页表
- 最小页：有4KB,16KB,64KB,可通过TCR_EL1进行配置
一种TLB刷新机制：为TLB缓存项打”标签”来减少程序切换时TLB刷新的开销
- ASID (Address Space IDentifier)：基于aarch64
- PCID (Process Context IDentifier)：基于x86-64
换页page swapping
- 换出swap out
- 换入swap in
缺页异常page fault
预取prefetching机制：发生swap in时，预测还有哪些页即将被访问，提前将其换入物理内存，减少page fault
按需页分配demand paging
- 未分配状态
- 已分配但未映射至物理内存状态（初次访问时出发page fault）
- 区分两种状态：
  - Linux中，程序的虚拟内存空间由多个虚拟内存区域构成，即VMA (Virtual Memory Area)：含beginning VA，ending VA，访问权限等信息。
  - P -> page fault
    - P属于VMA：已分配未映射
    - P不属于VMA：未分配
页替换策略
- MIN/OPT (Minimum / Optimal 最优策略)
- FIFO (First-In First-Out)
- Second Chance
- LRU (Least Recently Used)：基于程序过去频繁访问的页后续也可能被访问
- MRU (Most Recently Used)：基于程序不会反复访问相同地址情况
- clock algorithm：时钟算法策略
工作集模型working set model
- 基于：优先将非工作集中的页换出
- 工作集时钟算法：
  - 维护2个状态：上次使用时间和访问位
  - 定期检查算时间间隔
共享内存shared memory
- 写时拷贝copy-on-write
- 内存去重memory deduplication
  - 定期扫描相同内容的物理页，找到映射对应的虚拟页，保留一个物理页，其余通过copy-on-write映射到该物理页，释放其他物理页。
  - 如Linux的KSM (Kernel Same-page Merging)机制
  - 性能下降产生延迟，资源利用率提高
内存压缩
- 如Linux的zswap机制，zswap区域（仍属于内存区域）：为内存换页过程提供缓冲区
- 更加高效的磁盘批量I/O
大页huge page
- Linux提供透明大页transparent huge page机制：自动将一个应用程序中连续的4KB内存页合并成2MB的内存页
- 提高效率（减少TLB项，提高TLB命中率），可能浪费物理内存资源
内存碎片fragmentation
- 内部碎片internal fragmentation
- 外部碎片external fragmentation
伙伴系统buddy system
- 减少外部碎片
SLAB分配器
- 减少内部碎片
- 包括SLAB，SLUB，SLOB
- linux-2.6.23之后内核默认采用SLUB分配器（依赖于伙伴系统）
常用空闲链表
- 隐式空闲链表implicit free list
- 显式空闲链表explicit free list
- 分离空闲链表segregated free list

5 进程与线程

process

进程控制块PCB (Process Control Block)
僵尸进程zombie
进程管理：
- 进程组process group：进程的集合 —> 进程组标识符tgid (In Linux PCB)
- 会话session：进程组的集合
  
  根据执行状态划分为：
  - 前台进程组foreground thread group
  - 后台进程组background thread group
- process group和session主要用于shell环境的中的进程管理
  - 进程id -> PID
  - 进程组id -> GID
  - 会话id -> SID
控制中断进程controlling terminal

thread

用户态线程user-level thread
内核态线程kernel-level thread
多线程模型multithreading model
线程控制块Thread Control Block
NPTLNative POSIX Thread Library：自Linux 2.6引入的线程库，沿用至今

fiber

完全在用户态下完成

抢占式多任务处理preemptive multitasking
合作式多任务处理cooperative multitasking
(Windows) TLS(Fiber Local Storage) ：纤程本地存储，用来为每个纤程保存同一变量的私有拷贝
协程coroutine：为了便于与操作系统提供的纤程支持相区分，程序语言提供的纤程支持称为协程

6 操作系统调度

优先级priority
时间片time slice
截止时间deadline
任务调度/CPU调度task scheduling
线程thread是调度器的调度对象，又叫做任务task
- 运行队列run queue
- Linux使用的调度器会用红黑树实现运行队列
确定调度指标what ——> 做出调度决策how
- 调度指标
  - 分类
    - 性能相关指标
      - 批处理任务
        
        吞吐量：单位时间内处理的任务数量
        
        周转时间：任务从被发起直到执行结束所需的时间
      - 交互式任务
        
        响应时间：任务从被发起直至第一次向用户返回输出以响应用户所需的时间
      - 调度开销：做出决策的时间应该尽可能短
    - 非性能指标：公平性、资源利用率
    - 任务场景需求：实时性、能耗
  - 权衡
    - 调度开销和调度效果
    - 优先级和公平性
    - 性能与能耗
  - 调度机制
    - 进程调度process scheduling机制
      - 长期调度long-term scheduling/job scheduling
        
        限制系统中真正被用来进行短期调度管理的进程数量，避免短期调度的开销过大
        
        根据进程使用的资源类型，分类：计算密集型CPU-bound和I/O密集型I/O-bound
      - 短期调度short-term scheduling/job scheduling
        
        实际做出调度决策的机制
        
        负责进程在预备，运行，阻塞状态间的转换
      - 中期调度medium-term scheduling/job scheduling
        
        长短期调度 —> based on CPU and I/O resource
        
        中期调度 —> based on memory
        
        中期调度也是换页机制的一部分，当系统中内存使用量过大，就会触发换页机制，挂起处于预备状态的/阻碍状态的进程，置为挂起预备状态/挂起阻塞状态并放入挂起运行队列/挂起阻塞队列
        
        引入无法被短期调度执行的两个状态
        
        挂起预备状态suspended ready
        
        挂起阻塞状态suspended blocking
    - 批处理队列batch queue
    - 阻塞队列blocking queue
- 调度决策

7 进程间通信

进程间通信Inter-Process Communication (IPC)
消息message：一种常见通信数据的抽象，包含一个头部header和一个数据段payload
- header : 魔数magic number，状态state，消息长度message length，验证码verification code等
- payload : 纯数据（如字符串string），系统资源（如文件描述符file descriptor）
消息传递基本接口：
- Send(message)
- Recv(message)
- RPC(req_message, resp_message) —> 远程过程调用：Remote Procedure Call
- Reply(resp_message)
内存重映射memory remapping
IPC Classification
- 单向（管道，信号等）和双向（RPC）
- 同步（阻塞进程直到该IPC操作完成）和异步（非阻塞的，进程发起一次操作即可返回，不需要等待其完成）
  - 同步：被调用者callee处理请求时，调用者caller会处于block的状态，当callee执行完任务后，控制流会切回caller
    - 一般是双向IPC（或RPC）
  - 异步：多个并行的控制流，异步IPC通常通过【轮询内存状态】或【注册回调函数】（如果kernel支持的话）来获取返回结果。
超时机制
- 拒绝服务denial-of-service
通信连接管理
- 直接通信：通信的process一方需要显示地标识另一方
- 间接通信：通过一个中间信箱完成通信，每一个信箱有一个唯一的标识符，共享信箱交换message，进程间连接的建立发生在共享一个信箱时候。（如管道）
权限检查机制
- 微内核，如seL4等微内核系统的Capability机制
- 宏内核，如Linux，将【IPC安全检查机制】和【文件检查】结合在一起
System V进程间通信：即【宏内核】下的三种进程间通信机制：
- System V消息队列
- System V信号量
- System V共享内存

System V通信的权限管理：在Linux等宏内核中是基于文件File的权限检查机制

访问模式mode

权限检查

Linux对IPC进行权限管理的IPC_PERM结构，类似文件的【访问模式】，权限检查机制确保安全性

# uid 用户标识符
  # gid 用户组标识符
  struct ipc_perm {
    key_t key; // 进程可以根据key来索引到一个IPC对象
    uid_t uid; // owner uid
    gid_t gid; // owner gid
    uid_t cuid; // creator uid
    gid_t cgid; // creator gid
    mode_t mode; // 访问模式
  }

继承
- 除了命名服务外的另外一种常见的【分发权限】的方式
Linux中，匿名管道 —> 用于父子进程之间的通信，内核通过在fork时复制copy文件描述符表File Descriptor Table来建立父子进程之间的连接

命名服务

naming server

【权限分发】通过一个用户态的服务——命名服务实现
过程：
1. 各个服务（如文件系统服务，数据库系统服务等）向naming server注册自己的服务名。
2. 客户端进程向naming server上查询当前服务，并选择所需要的服务去尝试获取权限。
3. 是否分发权限，是由naming server和对应的服务端进程（如文件系统进程，网络系统进程，数据库进程）根据特定的策略（如无条件，需要私钥签名的证书）来判断的。
优点：
- 各个服务不再是kernel中的ID等抽象的表示，而是对应用更友好的名字name
naming server一般在用户态

宏内核`IPC`

管道pipe

System V：常指宏内核下三种具体的IPC机制

消息队列

信号量

共享内存

Linux信号机制

套接字socket机制

IPC机制	数据抽象	参与者	方向	内核实现
管道`pipe`	字节流	两个进程	单向	通常是`FIFO`缓冲区管理数据，分为匿名管道和命名管道
消息队列`MQ`	消息	多进程	单向双向	队列的组织方式，通过【文件权限】管理对队列的访问
信号量`semaphore`	计数器	多进程	单向双向	内核`kernel`维护共享计数器，通过文件权限管理对计数器的访问
共享内存`chm`	内存区间	多进程	单向双向	内核维护共享内存的内存区间，通过文件的权限来管理对共享内存的访问
信号`signal`	事件编号	多进程	单向	为线程/进程维护【信号等待队列】，通过用户 / 组等的权限管理信号的操作
套接字`socket`	数据报文	两个进程	单向双向	有基于`IP + port`和基于`file path`的寻址方式，利用网络栈来管理通信

管道

匿名管道：通过pipe的系统调用创建

父子进程
命名管道：通过mkfifo命令创建 —> 指定一个全局文件名

远距离进程（任意两个进程）

`System V` 消息队列

发送和接收message的接口是kernel提供的
kernel从system memory中分配一个队列数据结构，作为消息message的内核对象
MQ基本操作：
1
In Linux, the following operations are defined as system call.
- msgget：允许进程获取已有消息队列的连接，或者创建一个新的消息队列
- msgsnd：发消息
- msgrcv：收消息
- msgctl：可以控制和管理一个消息队列，如修改消息队列的权限信息，或删除消息队列
消息发送和消息接收一般是【非阻塞的】
Linux kernel实现：
- 【系统管理员】通常可以配置【单个消息】single message的最大空间、【单个消息队列】single MQ的最大空间、全系统的消息队列个数
- 通常建议使用【共享内存机制】传递长消息，而非使用MQ
- 消息在用户态和内核态之间传递时，会有拷贝开销：
  - copy_from_user
  - copy_to_user

`System V` 信号量

通过对信号量的PV操作限制可以保证执行顺序
关键：封装一个计数器

`System V` 共享内存

在Linux的系统设计中，将共享内存的机制封装在了一个特殊的文件系统中（即共享内存文件系统shm 文件系统），实际中使用tmpfs实现

	* kernel 为全局所有的共享内存维护一个全局队列结构,由结构体 [shmid_kernel] 组成
	* IPC key (全局唯一) --> struct shmid_kernel

struct shmid_kernel {
    ...
    struct file file;--> VFS struct inode 
                     --> 一段共享物理内存页的集合(也就是共享内存对应的物理内存)
    ...
}

[process1] and [process2]
    * By shm_at (kernel API)---> Reflect [shared memory] to [Virtual Address Space]
    * kernel会为process1和process2分配两个VMA(Virtual Memory Area)结构体,均指向file
    * 两个VMA对应的虚拟地址可以不同, 只需要映射到相同的物理内存
    * 支持任意数量的进程共享同一个共享内存区域, 只需要为它们分配[指向 struct file 的VMA]即可
    * 取消映射(detach操作)只会影响当前进程的映射

shm : shared memory
shm_at: 建立对共享内存的映射的接口
shm_dt: 取消共享内存和虚拟内存之间的映射的接口

信号`IPC`

信号signal：具备【单向的事件通知】能力（信号量semaphore有通知能力，但需要进程主动查询计数器的状态或陷入阻塞状态等待通知）
信号传递信息很短，只有一个编号，且由kernel传递
Linux早起使用信号有31（1~31号）个，后续POSIX标准引入了编号32~64的其他信号
- 传统信号称为【常规信号】
  - 进程多次收到，kernel只会记录一次
- POSIX引入称为【实时信号】
  - 进程多次收到，kernel不会丢弃相同信号时间
Linux：kernel会为每个进程和线程准备一个【信号事件等待队列】
- 一个进程内的多个线程
  - 共享该进程的【信号事件队列】
  - 拥有自己私有的【等待队列】
Linux提供了一个专门的系统调用sigprocmask：允许用户程序设置对特定信号的阻塞block状态
- 信号阻塞，Linux不会再触发该信号对应的handler function，直到该信号被解除block，信号阻塞不阻碍信号被添加到等待队列上
signal既用于IPC也用于进程管理
内核对信号的处理
- 时机：通常是kernel执行完exception, interrupt, syscall返回用户态的时刻
- 方式：
  - 忽略
  - 用户处理函数：调用【用户注册】的【信号处理函数】
  - 内核默认处理函数：调用【默认】的【内核处理函数】
- Linux信号内核与用户态之间的切换
  
  步骤2Linux完成从内核到用户态的切换后（转向handler），就会把【相关栈状态】和【上下文】清空，所以为了避免执行完handler返回时无法恢复到当初系统调用时候用户态的上下文等，在切换到用户态执行handler时，Linux会将【syscall的返回值】和【此前的用户态的上下文（PC，register等）】保存在【用户栈】上。因此步骤4就会从用户栈上提取上下文等信息以恢复到当初系统调用时候的环境。
```
    flowchart TD    
    subgraph usr
    B(调用syscall1)
    C(handler) --> D(sigreturn)
    end
    
    subgraph kern
    A1(syscall1) --> A2(ret_to_user)
    A3(sigreturn) --> A4(ret_to_user)
    end
    
    B -->|1.用户态进程系统调用进入内核态| A1
    A2 -->|2.内核态处理完系统调用时,\n发现有signal,于是切换到\n用户态处理函数位置,让其处理信号事件| C
    D --> |3.信号处理完后,信号处理函数\n会通过系统调用sigreturn返回内核.\n该系统调用的主要作用即辅助内核\n恢复到被信号打断之前的上下文context|A3
    A4 --> |4.继续完成在系统调用被打断时的任务,\n即syscall返回时回到原用户态|B
```
可重入reentrant函数：允许多个任务（☞对信号事件的响应和处理）并发使用，而不必担心【共享数据】的错误
- 实现可重入函数的前提
  - 不使用static data或者static data只读
  - 尽量只是用local data
  - 在必须使用全局共享数据的时候，需要保护对全局数据的访问（防止死锁）
  - 避免在函数中修改自己的代码
  - 不调用【不可重入函数】，很多常见的库函数的实现（如malloc）都是不可重入的

套接字

客户端通过【地址】找到要调用的服务端进程
- IP + port：通信双方通常使用【本地回环地址127.0.0.1】，然后各自绑定在不同的端口上，OS网络协议栈可以识别回环地址，将通信转发到目标端口对应的进程
- UNIX domain socket：本地文件系统的一个路径
协议
- 传输控制协议TCP : Transmission Control Protocol
  - 可靠性好
  - （数据丢失情况下）数据重传
  - （数据乱序到达情况下）数据顺序维护
- 用户数据报协议UDP : User Datagram Protocol
  - 简单
  - 传输性能较好

Linux套接字

socket(int domain, int type, int protocol);
* domain: 寻址方式, [IP + port] or [local path];
* type: 通信方式, [SOCK_STREAM](数据流,对应[TCP]) or [SOCK_DGRAM](数据报,对应[UDP])
* protocol: 定义协议相关配置, [TCP] or [UDP];

Ganliber's Home

OS Notes Part(I)

Modern Operating System (I)

4 内存管理

5 进程与线程

process

thread

fiber

6 操作系统调度

7 进程间通信

命名服务

宏内核`IPC`

管道

`System V` 消息队列

`System V` 信号量

`System V` 共享内存

信号`IPC`

套接字

Modern Operating System (I)

4 内存管理

5 进程与线程

process

thread

fiber

6 操作系统调度

7 进程间通信

命名服务

宏内核IPC

管道

System V 消息队列

System V 信号量

System V 共享内存

信号IPC

套接字

宏内核`IPC`

`System V` 消息队列

`System V` 信号量

`System V` 共享内存

信号`IPC`