基础

进程上下文：进程的当前运行状态，包括程序计数器、通用寄存器、浮点寄存器、状态寄存器、用户栈、内核数据结构（页表、进程表、文件表）等

线程和进程的区别？

  • 调度：线程是调度的基本单位（PC，状态码，通用寄存器，线程栈及栈指针）；进程是拥有资源的基本单位（打开文件，堆，静态区，代码段等）。

  • 并发性：一个进程内多个线程可以并发（最好和CPU核数相等）；多个进程可以并发。

  • 拥有资源：线程不拥有系统资源，但一个进程的多个线程可以共享隶属进程的资源；进程是拥有资源的独立单位。

  • 系统开销：线程创建销毁只需要处理PC值，状态码，通用寄存器值，线程栈及栈指针即可；进程创建和销毁需要重新分配及销毁task_struct结构。

  • 子进程从父进程继承的内容

    • 用户号UIDs和用户组号GIDs
    • 环境Environment
    • 堆栈
    • 共享内存
    • 打开文件的描述符
    • 执行时关闭（Close-on-exec）标志
    • 信号（Signal）控制设定
    • 进程组号
    • 当前工作目录
    • 根目录
    • 文件方式创建屏蔽字
    • 资源限制
    • 控制终端

  • 子进程独有

    • 进程号PID
    • 不同的父进程号
    • 自己的文件描述符和目录流的拷贝
    • 子进程不继承父进程的进程正文（text），数据和其他锁定内存（memory locks）
    • 不继承异步输入和输出

父进程和子进程拥有独立的地址空间和PID参数。

子进程从父进程继承了用户号和用户组号，用户信息，目录信息，环境（表），打开的文件描述符，堆栈，（共享）内存等。

经过fork()以后，父进程和子进程拥有相同内容的代码段、数据段和用户堆栈，就像父进程把自己克隆了一遍。事实上，父进程只复制了自己的PCB块。而代码段，数据段和用户堆栈内存空间并没有复制一份，而是与子进程共享。只有当子进程在运行中出现写操作时，才会产生中断，并为子进程分配内存空间。由于父进程的PCB和子进程的一样，所以在PCB中断中所记录的父进程占有的资源，也是与子进程共享使用的。这里的“共享”一词意味着“竞争”

内存分布情况

从低地址到高地址：

  • 程序文件段，包括二进制可执行代码；
  • 已初始化数据段，包括静态常量；
  • 未初始化数据段，包括未初始化的静态变量；
  • 堆段，包括动态分配的内存，从低地址开始向上增长；
  • 文件映射段，包括动态库、共享内存等，从低地址开始向上增长（跟硬件和内核版本有关）
  • 栈段，包括局部变量和函数调用的上下文等。栈的大小是固定的，一般是 8 MB。当然系统也提供了 参数，以便我们自定义大小；

进程调度算法

  1. 先来先服务first-come first-serverd（FCFS）

  2. 短作业优先 shortest job first（SJF）

  3. 最短剩余时间优先 shortest remaining time next（SRTN）

    短作业优先的抢占式版本，按剩余运行时间顺序进行调度。当新作业到达时，会与当前进程剩余时间进行比较，若新作业运行时间更短则挂起当前进程，运行新的进程，否则新进程等待。

  4. 时间片轮转

  5. 优先级调度

    为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级

  6. 多级反馈队列

    多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不 同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。

    每个队列优先权也不同，最上面的优先权最高。因此只有上 一个队列没有进程在排队，才能调度当前队列上的进程。

    可视为时间片轮转调度算法和优先级调度算法的结合。

Linux进程间通信

  • 管道
    • 无名管道（内存）
    • 有名管道（FIFO文件）
  • 共享内存：最快的IPC方式
  • 消息队列：消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点
  • 套接字：适用于不同机器间进程通信
  • 信号
  • 信号量：是一个计数器

分页式存储管理

Ref：深入理解操作系统之——分页式存储管理

逻辑地址分为页号+ 页内偏移量，两者的长度根据页大小确定，若页大小为4KB（2^12B），则前20位表示页号，后12位表示页内偏移量。若页大小为2KB，则前21位表示页号，后11位表示页内偏移。（相当于$页号 = 逻辑地址 / 页大小$）

逻辑地址到物理地址的变换过程

  1. 进程访问某个逻辑地址时，分页地址机构自动将逻辑地址分为页号和页内地址
  2. 页号大于页表长度，越界错误
  3. 页表项的地址 p = 页表起始地址 F + 页号 P * 页表项大小 S，从而得到对应的物理块号 B
  4. 页和物理块的大小是一致的，所以 页内地址=块内地址
  5. 然后 物理地址 = 物理块号 B * 页大小 L + 页内地址
  6. 根据物理地址读取数据

例：某系统采用分页式存储管理，页大小为 2KB。已知进程 A 的逻辑地址空间为 4 个页，内存分配如下页表所示，求逻辑地址 4832 的物理地址。（所有数据都是十进制）

解：

2KB=2048B

页号 P=逻辑地址/页大小=4832/2048=2

页内地址 F=逻辑地址%页大小=4832%2048=736

根据页表查得 2 号页对应着 25 号物理块

物理地址 A=物理块号页大小 + 页内地址=252048+736=51936

快表

快表一般存放在 CPU 内部的高速缓冲存储器 Cache。

CPU 寻址时先到快表查询相应的页表项形成物理地址，如果查询不到，则到内存中查询，并将对应页表项调入到快表中。如果快表的存储空间已满，则需要通过算法找到一个暂时不再需要的页表项，将它换出内存。

二级页表

由于页表必须连续存放，并且需要常驻物理内存，当逻辑地址空间很大时，导致页表占用内存空间很大。

二级页表即是对页表本身采用分页式管理，对页表本身增加了一层页表管理。页的大小就是一个页表的大小，一个页表只能装在一个页中。

逻辑地址分成了三部分：顶级页号、次级页号和页内地址。

分段式存储管理

主要方便用户和程序员，以满足方便编程、信息保护和共享、动态增长及动态链接等多方面的需要。

分段逻辑地址结构

段表结构

地址变换机构

逻辑地址到物理地址的变换过程

① 从逻辑地址A中取出前几位为段号S，后几位为段内偏移量W。

② 比较段号S和段表长度M，若S≥M，则产生越界中断，否则继续执行。

③ 段表中段号S对应的段表项地址 = 段表始址F + 段号S * 段表项长度，取出该段表项的前几位得到段长C。若段内偏移量≥C，则产生越界中断，否则继续执行。

④取出段表项中该段的始址b，计算$E=b+W$，用得到的物理地址E去访问内存。

段页式管理

在段页式系统中，作业的地址空间首先被分成若干逻辑段，每段都有自己的段号，然后将每段分成若干大小固定的页。对内存空间的管理仍然和分页存储管理一样，将其分成若干和页面大小相同的存储块，对内存的分配以存储块为单位。

逻辑地址分为：段号、页号、页内偏移量

地址变换机构

动态分区分配算法

  1. 首次适应

    空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链( 或空闲分区表)，找到大小能满足要求的第一个空闲分区。每次都从低地址开始查找，找到第一个能满足大小的空闲分区。

  2. 最佳适应

    空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

  3. 最坏适应

    空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。（为了解决最佳适应算法的问题：产生太多难以利用的小碎片）

  4. 邻近适应

    空闲分区以地址递增的顺序排列(可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

    （首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。）

内存管理

操作系统进行内存管理时要做的事情？

  • 内存空间的分配与回收
  • 从逻辑上对内存空间进行扩充
  • 实现逻辑地址与物理地址的转换
  • 内存保护，保证各进程在各自存储空间内运行，互不干扰

操作系统经典问题

哲学家就餐问题

参考：哲学家进餐问题的三种解决方法(C++11)

leetcode：1226. 哲学家进餐 - 力扣（LeetCode）

三种方法

  • 同时拿起左右两只叉子才可以进餐
  • 限制进餐人数
  • 奇数先左后右，偶数先右后左

读者写者问题

读写锁/共享锁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * ===========================================================================
 *             读写锁 shared_mutex 的自定义，解决【读者-写者】问题
 * shared_mutex: 共享锁
 * shared_lock: 线程间可以同时使用
 * unique_lock: 线程独享
 * ===========================================================================
 */

class Counter {
public:
    Counter(int val = 0) : _value(val) {}

    int get() const {
        shared_lock<shared_mutex> lock(_mutex);
        return _value;
    }

    void increase() {
        unique_lock<shared_mutex> lock(_mutex);
        ++_value;
    }

    void reset() {
        unique_lock<shared_mutex> lock(_mutex);
        _value = 0;
    }

private:
    mutable std::shared_mutex _mutex;
    int _value;
};

mutex g_io_mutex;

void worker_shared_mutex(Counter& counter) {
    const int N = 3;
    for (int i = 0; i < N; i++) {
        counter.increase();
        int val = counter.get();

        unique_lock<mutex> lock(g_io_mutex);
        cout << "thread " << this_thread::get_id() << ": val = " << val << endl;
    }
}

void test_shared_mutex() {
    const int N = 2;
    vector<thread> threads;
    Counter counter(0);

    for (int i = 0; i < N; i++) {
        threads.emplace_back(&worker_shared_mutex, ref(counter));
    }

    for (thread& t : threads) {
        t.join();
    }
}

mutex

内存覆盖与内存交换

参考：内存覆盖和内存交换

守护进程、僵尸进程、孤儿进程

守护进程的创建

参考：守护进程(daemon)详解与创建

  1. fork()创建子进程，父进程exit()退出

    守护进程是脱离终端控制的，在形式上做到子进程与控制终端的分离，让子进程在后台执行

  2. 子进程调用setsid()创建新的会话

    子进程会复制父进程的会话期、进程组、控制终端，因此子进程并没有真正独立出来，通过设置新的会话组可使得子进程成为无终端的会话组组长，从而真正独立

  3. 再次fork()一个子进程，并让父进程退出

    进程虽已成为无终端的会话组组长，但此时仍能重新申请控制终端，需要fork()一个子进程，该子进程不是会话首进程，因此不能打开控制终端

  4. 子进程执行chdir()，让根目录成为子进程的工作目录

    子进程会复制父进程的当前工作目录，使得当前目录所在的文件系统无法卸载，需要将工作目录修改至根目录/

  5. 子进程调用umask()，设置进程的文件权限掩码为0

    子进程会复制父进程的文件掩码，使得没有文件的一些权限，因此需要将文件掩码设置为0

  6. 子进程关闭不需要的文件描述符

    子进程会复制父进程已打开的文件描述符，会导致文件系统无法卸载；且守护进程无法与控制终端通信，需要关闭0、1、2的文件描述符

  7. 守护进程退出

    通过kill关闭守护进程

僵尸进程

参考：https://www.cnblogs.com/anker/p/3271773.html

子进程先退出，父进程未退出，子进程必须等到父进程捕获到子进程的退出状态才能真正结束，而如果父进程没有调用wait()/waitpid()获取子进程的状态信息，会导致子进程成为僵尸进程。由于僵尸进程仍保存一定信息（进程号，退出状态，运行时间等），会造成资源浪费。

解决方法：

  1. SIGCHILD信号处理：子进程退出时向父进程发送SIGCHILD信号，父进程处理SIGCHILD信号。在信号处理函数中调用wait/waitpid处理僵尸进程。
  2. fork()两次：将子进程成为孤儿进程，从而其父进程变为init进程，通过init进程处理僵尸进程。

孤儿进程

父进程先退出，子进程还未退出，子进程会被init进程接收，并由init对其进行状态收集工作

磁盘调度算法

读写时间的影响因素：旋转时间、寻道时间、实际的数据传输时间。

寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。

  1. 先来先服务
  2. 最短寻道时间优先：优先调度与当前磁头所在磁道距离最近的磁道
  3. 电梯扫描算法：总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向

页面置换算法

  1. 最佳置换法（OPT）

    每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面

  2. 先进先出置换算法（FIFO）

    每次选择淘汰的页面是最早进入内存的页面，可能出现Belady 异常

  3. 最近最久未使用置换算法（LRU）

    每次淘汰的页面是最近最久未使用的页面

  4. 时钟置换算法（CLOCK）/ 最近未用算法（Not Recently Used）

    为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第x轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位 为0的页面，因此简单的CLOCK算法选择–个淘汰页面最多会经过两轮扫描）

  5. 改进的时钟置换算法

    在CLOCK的基础上，优先淘汰没有修改过的页面，避免I/O操作。

死锁

死锁产生的必要条件（缺一不可）：

  1. 互斥条件
  2. 不可剥夺条件
  3. 请求和保持条件
  4. 循环等待条件

死锁的处理方法：

  1. 鸵鸟策略：忽略死锁。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略

  2. 死锁检测与死锁恢复

    每种类型单个资源：检测有向图是否有环

    每种类型单个资源：

    死锁恢复：

    • 利用抢占恢复
    • 利用回滚恢复
    • 通过杀死进程恢复

  3. 死锁预防

    • 破坏互斥条件
    • 破坏不可剥夺条件
    • 破坏请求和保持条件
    • 破坏循环等待条件

  4. 死锁避免

    银行家算法：银行家算法

高并发的解决方案

  1. 应用数据与静态资源分离
  2. 客户端缓存
  3. 集群和分布式
  4. 反向代理

在执行malloc申请内存的时候，操作系统是怎么做的？

从操作系统层面上看，malloc是通过两个系统调用来实现的： brk和mmap。

  • brk是将进程数据段(.data)的最高地址指针向高处移动，这一步可以扩大进程在运行时的堆大小
  • mmap是在进程的虚拟地址空间中寻找一块空闲的虚拟内存，这一步可以获得一块可以操作的堆内 存。

通常，分配的内存小于128k时，使用brk调用来获得虚拟内存，大于128k时就使用mmap来获得虚拟内 存。

交换空间是在物理硬盘上划分出的一部分空间，在物理内存满时将数据交换到交换空间，是虚拟内存使用的硬盘空间。

抖动：刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，是频繁的页面调度行为。主要原因：进程频繁访问的页面数目高于可用的物理块数。

原子操作的实现

  • 总线锁：一个处理器在总线上输出LOCK#信号，使得其他处理器对内存的操作请求都会被阻塞，该处理器独占共享内存
  • 缓存锁：缓存锁是某个CPU对缓存数据进行更改时，会通知缓存了该数据的CPU抛弃缓存的数据或者从内存重新读取