操作系统的笔记和总结，方便日后回顾用

操作系统基础

操作系统是介于硬件与应用程序之间的一层，它管理着计算机的硬件，让用户更加高效的使用计算机。用户只能通过操作系统的接口来使用硬件。用户既可以通过应用程序间接使用操作系统，也可以直接使用。

计算机最重要的东西就是CPU和内存，操作系通过进程管理CPU。对于Linux来说，万物都是I/O设备。所有的外部硬件都是通过I/O管理的。

总的来说，操作系统有两大重要的组成部分，一个是多进程视图，一个是文件视图。多进程视图中主要研究进程管理和内存管理，文件视图主要研究文件管理和IO管理。

系统启动

一切从操作系统的启动开始。当电源上电时，硬件电路会初始化PC的值为 0xFFFF0 ，内存中这一段地址是 BIOS，负责对程序的硬件进行检测。检测成功后，利用BIOS的输入功能将启动磁盘的启动扇区读入内存，将 PC 的值设置为 0x7C00，这一段是 bootsects.s（此时还不算是操作系统的启动）

PC：CPU中的程序计数器

当PC进入到 bootsect.s 中时，操作系统开始启动。bootsect.s 的作用是将启动的另一段程序 setup.s 读入内存、向显示器显示LOGO和正在启动信息、将操作系统内容读入内存。随后，PC将进入 setup.s

setup.s 的主要作用是读取硬件信息，并将操作系统从 16 位的实模式切换位 64 位的保护模式。从此之后，操作系统将以64位的模式进行工作。切换之后，PC将跳转到 head.s 文件

保护模式的PC的译码方式改变了。保护模式的PC查询 GDT 表，间接得到要访问的地址。

GDT：global decriptor table 全局描述表

head.s 的主要作用就是初始化 IDT表和 GDT表和页表。head.s 运行完毕后，PC将跳转到 0x0 地址处，也就是操作系统的函数 main.c。

IDT：interrupt decriptor table 中断描述表。

页表：主要作用是内存管理

setup.s 为了在保护模式下能跳转到 head.s 也进行了 IDT 和 GDT 表的初始化，不过 head.s 中的是临时建立的， head.s 是正式建立

main.c 负责初始化一些硬件表，初始化其他重要的数据结构，创建进程，启动 Shell

系统接口

为了保证系统内核的安全，应用程序是直接对硬件进行操作的，要想使用计算机硬件，只能通过操作系统的接口。这些接口函数由操作系统提供，同时又以函数的形式调用，因此称为系统调用。

系统调用连接了计算机硬件和应用程序

系统调用由 IEEE 指定的 POSIX 标准定义，常见的系统调用有 fork(), open(), read(), write() 等

为了实现这一目标，操作系统将内存设置了不同的权限（特权级），CPU在运行的时候通过硬件电路来检测特权级。CPU读取当前特权级（CPL）和目标特权级（DPL），将其比较，当 CPL <= DPL 时执行。

通过硬件电路是为了提高效率

特权级从小到大，权限越来越低。0是内核态，3是用户态。系统内核的 DPL 是0，CPU在运行用户代码是 CPL被设为 3 。因此无法直接访问内存地址。

CPL在CPU寄存器存放，DPL是 GDT 表中存放的数据

应用程序要访问内核态的数据就需要依赖于系统调用了。操作系统给应用程序留了一个 0x80 号中断作为应用程序进入操作系统的入口。以 C 语言的 printf 函数为例。printf 里面就有一段内联汇编，里面涉及到 0x80 中断，同时传入系统调用号来区别不同的系统调用

int write(int fd, const char *buf, off_t count) {
    long __res;
    __asm__volatile("int 0x80" : "=a"(__res) : ""(__NR_write)), "b"((long)(fd)), "c"((long)(buf)), "c"((long)(count));
    // __NR_write 就是系统调用号，"b"((long)(fd))表示将 fd 赋值给 %ebx
    // 核心就是使用 int 0x80 中断，然后将系统调用号传入
}

操作系统收到 int 0x80 后进行中断处理，根据系统调用号查询 IDT 表，跳转到相应的中断处理函数执行操作。跳转到中断处理函数后，CPL = 0，就可以进行对系统内核和硬件的操作了。总的来说就是一下步骤：

系统调用Linux命令

strace：查看进程调用了哪些系统调用

进程管理

进程管理其实就是对计算机CPU的管理。CPU的工作流程就是不断的取址执行、取址执行，给CPU一个初始地址就可以让它工作了

这样效率很低，一旦某个程序在进行I/O操作，CPU就必须等待硬件的读写完成。为了提高效率，有必要让CPU在不同的程序之间切换，多个程序同时出发，交替运行。在切换时要记录当前程序的相关信息以便切换回来能够恢复上下文，保存的这个数据结构就是 PCB（程序控制块）。这种在运行的程序就叫做进程

进程于程序的主要区别就是一个在运行，内存中有PCB，一个没有在运行

多进程视图

多进程的组织

一个进程会有不同的状态，操作系统是通过状态队列来管理多个进程的

进程主要有3种状态：就绪态、运行态、阻塞态

操作系统对每个状态有一个队列，队列中存放的就是一个个进程

1
2
3

运行态	  :  [PID=1,PC=...]
就绪态队列:	[PID=2,PC=...], [PID=4,PC=...]
阻塞态队列:	[PID=3,PC=...], [PID=5,PC=...]

根据发生的事件，各个程序在不同的状态中进行切换

运行态到就绪态的切换：当一个进程运行了很多时间，超过了操作系统给它分配的时间片后，这个进程将会被剥夺CPU，进入运行态
就绪态到运行态的切换：当CPU出现空闲，比如刚刚一个进程的CPU被剥夺，就会调用调度算法，在就绪态中找到一个进程，然后把这个进程变为运行态。
运行态到阻塞态的切换：当一个进程遇到例如IO操作这种操作，它就必须等待IO执行完毕才能执行下一条指令，此时CPU就空出，这个进程就从运行态变成了阻塞态
阻塞态到就绪态的切换：当IO操作执行完毕之后，设备将会给CPU发送一个中断信号。CPU收到中断信号之后查中断表，执行对应的中断处理函数，操作系统在中断处理函数中将唤醒阻塞态中对应的进程，这个进程就进入了就绪态。

进程间切换

本文底下 用户级线程 和 核心级线程 有更深的介绍

进程间分离

如果进程A要读取内存中的一段数据，进程B修改了这个数据，那么进程A就会得到错误的结果

为了防止这种事情的发生，操作系统进行了内存映射，在运行的时候查 GDT 表来实现地址的分离

进程间通信

最基本的模式就是两个进程在一块共享缓存区中读写

此时，如果一个进程还没执行完，就执行另外一个，此时就会出现错误

process1:
void A { a = file.read(); a += 3; file.write(a); }
						⬆ PC在此次跳转到process2，a就会发生错误
process2:
void B { b = file.read(); b *= 2; file.write(b); }

解决方法就是在执行 process1 的时候一次性执行完全。或者说设置共享缓冲区的控制权，让 process2 无法操作文件

本文底下 进程同步 有深入的介绍

进程切换

进程的切换包括两个部分，一个是指令流的切换，一个是资源的切换。而指令流刚好是CPU的切换，也是线程的切换。

线程

线程是同一个程序中的并行。这个程序的代码间共享的资源非常多，但是又有子程序交替执行的特点，就有了多线程的概念。

例如一个浏览器，既要通过网络下载，又要在客户端显示。一个比较好的实现方法就是网络下载和客户端显示同时开始，交替进行（两个线程并行）。这就需要支持多线程。

为了能恢复线程的上下文，线程也有一个记录 CPU 寄存器信息等资源的内容，成为 TCB（线程控制块）

不过由于资源的切换少，线程的切换比进程快很多。

线程有两类：用户级线程和内核级线程。用户级线程是应用程序自己实现多线程，在操作系统眼里还是单线程。而核心级线程是深入操作系统中，操作系统会分配相应的硬件资源。

MMU 是 CPU 中的共享储存管理部件（Memory Management unit）。进程切换不仅需要切换 PC 指针，还需要切换 MMU，而线程切换不需要切换 MMU

进程的切换就是在内核级线程的切换 + 映射表等资源的切换

用户级线程

多个线程共用一个栈时，跳转时要进行压栈存放下一步的 PC 值，这时多个线程的 PC 值就混在一起了。因此，一个线程对应一个栈

1
2
3
4
5
6
7
Thread1:
A { B(); ... }
B { Yield(Thread2); ... }
Thread2:
C { D(); ... }
D { Yield(Thread1); ... }
Stack: [ A B C D
Thread2 跳转回 Thread1 后，理想状态下将返回到 B，但是此时栈底是 D，将跳转到 D

用户级线程的核心是一个线程一个栈 以及 Yield()

应用程序想要切换时，调用 Yield() 函数即可。Yield() 会将当前栈指针 %rsp 和其他寄存器保存在 TCB 中，然后找到下一个线程的 TCB，然后取出新 TCB 中的 %rsp 完成栈的切换，并恢复上下文。

用户级线程的创建 就是在内存中分配一块地址给线程的栈和TCB，并初始化

用户级线程不是函数调用，在操作系统无多线程的时候有用，不过用户级线程无法处理一个线程堵塞导致其他线程卡死的现象。这种需要核心级线程解决

内核级线程

核心级线程需要由于涉及到操作系统，因此需要通过中断 int 0x80 进入操作系统内核，通过中断返回 iret 从操作系统返回到用户态代码。

如果一个线程继续使用一个栈，这个栈中可能存放着一些危险代码，内核在执行时会以内核态的特权级执行，因此不安全，需要将栈分为用户态的栈和内核态的栈。内核态的栈中存放着用户栈的首尾地址和中断进入内核前的 PC 值，以便能够回到原来的地方继续执行，同时内核栈中还存放在中断返回代码的地址。

内核级线程的切换包括代码的切换（PC指针的切换）、TCB的切换、用户栈的切换和内核栈的切换。PC指针压在栈中，切换的时候弹栈赋值；栈的切换主要是 %rsp 的变化。有5个步骤

进入操作系统核心。应用进程通过中断来到操作系统核心，将用户栈的首尾位置、PC指针位置等信息压入内核栈。执行中断处理函数。
用户代码
1
2
3
mov %eax, __NR_fork INT 0x80 #进入系统内核 mov res, %eax
接下来操作系统就会执行系统调用的函数 system_call

调用 schedule() ，找到下一个执行的线程的 TCB。找到下一个进程的过程在后面进程调度中会介绍

系统调用：system_cal

push %ds ... # 将CPU寄存器记录到内核栈中
call sys_fork
push %eax
...
cmpl $0 counter(%eax)	# 判断是否阻塞或超时
je schedule()		# 如果阻塞或超时就切换
ret_from_sys_call:

sys_fork 在后面内核级线程的创建会介绍

进行内核栈的切换。根据 TCB 的信息完成内核栈的切换

schedule:
	next = ...;
	call switch_to(next);
switch_to:
	TCB[curr].esp = %esp;
	%esp = TCB[next].esp;

中断返回。从内核态重新返回为用户态。
系统调用：system_cal
1
2
3
ret_from_sys_call: popl %eax ... # 将用户态还原 iret # 中断返回
进行用户栈的切换。根据中断返回将PC设置为内存栈中的PC，还原之前压入栈的寄存器。

内核级线程的创建 的关键是为TCB和内存栈申请内存，初始化TCB、内核栈、完成和用户栈的绑定

进程调度

应用程序有着不同的性质，一类对反馈性要求高，即希望CPU的切换时间短；另外一类对任务的周转时间要求高，就是希望任务能够尽快做完，即希望CPU给出充足的时间让它一次性做完。

操作系统的进程调用要尽量满足两种应用的需求。

常见的调度方法有以下一些部分

FCFS：先到先服务
SJF：短作业优先
RR：时间片轮转
多极队列调度
- 前台队列 RR
- 后台队列 SJF

在实际的操作系统中，使用的是 多极反馈队列调度。动态根据应用运行时间和等待时间调节进程的优先级

void schedule() {
    while(true) {
        foreach(task : taskqueue) {
            if(task.state == TASK_RUNNING && task.counter > c) { 
                next = task; c = task.counter; 
            } 
        }	// 在运行队列中找到最大count最大的那个
        if(next.counter == 0) {
            foreach(task : taskqueue) {
                // 增加时间，使得从就绪态到运行态的新进程和等的久的进程先执行
                task.counter = (task.counter >> 1) + task.priority;
            }	// 所有进程
        }	// 运行队列的时间片清零了
        else { break; }	// 这个进程的时间片还有剩余时间
    }
    switch_to(next);
}

进程同步

两个进程之间会存在合作依赖关系（例如消费者-生产者模型，生产者生产后消费者才能消费）。进程同步使得多个进程之间的合作合理有序，实现了两个进程之间的依赖关系。

操作系统是通过：一个进程在需要同步的时候停下，等待依赖进程。当依赖进程执行完毕后，该进行继续执行的办法实现进程同步。

通过对进程走走停停，来让多个进程步调一致，合理有序的推进，实现进程同步

应用进程在需要同步的地方将自己阻塞，等待信号；当各个进程协调一致了，就会发射一个信号给操作系统。操作系统收到信号后，会将进程唤醒。

信号量

信号量就是告诉应用进程在什么时候停，在什么时候走的一个信号。应用进程通过信号量的值来执行等待或唤醒操作。信号量的结构如下

struct semaphore {
    int value;	// 信号的量
    PCB *queue;	// 等待在该信号量上的进程队列
};
void P(semaphore s) {
    --s.value;
    if(s.value < 0) { sleep(s.queue); }
}	// 使用资源的进程通过该函数判断是否等待
void V(semaphore s) {
    ++s.value;
    if(s.value <= 0) { wake_up(s.queue); }
}	// 生产资源的进程通过该函数唤醒对应进程

其中，s.value 表示剩余资源的数量。消费者调用 P(s) 时，value < 0 说明生产者生产的资源不够，消费者需要等待；生产者调用 V(s) 时，value <= 0 说明有 1 - value 个进行正在等待，而此时生产了一个资源，需要唤醒一个进程消耗。

生产者-消费者模型是信号量的一个很好的应用

OS：

1
2
3

>semaphore full = 0;				// 占用缓冲区
>semaphore empty = BUFFER_SIZE;	// 空闲缓冲区
>semaphore entry = 1;			// 是否进行读写了

生产者：

>while(true) {
   P(empty);	// 判读是否有空闲缓冲区资源
   P(entry);	// 判断是否其他进程正在使用缓冲区
   buffer[i] = item; i = (i + 1) % BUFFER_SIZE;	// 写内容
   V(entry);	
   V(full);	// 生产后占用了的缓冲区会增加，空闲缓冲区减少
>}

消费者：

>while(true) {
   P(full);	// 判断缓冲区是否为空
   P(entry);	// 判断是否其他进程正在使用缓冲区
   item = buffer[o]; o = (o + 1) % BUFFER_SIZE;
   V(entry);
   V(empty);	// 生产后空闲缓冲区会增加，占用了的缓冲区会减少
>}

信号量的保护

信号量的语义必须是正确的，进程的交互才能继续完成。而对信号量的修改实在两条语句中，可能会被 CPU切换掉，导致信号量表示的信息与实际情况不一样。

操作系统的解决方案就是在更改信号量的地方设置临界区保护区

1
2
3

... (进入区代码)
++s.value;
... (退出区代码)

使得一次只有一个进程进入临界区。

有三种解决方式

软件解决：面包店算法：轮换 + 标记
- 轮换：每个进程一个序号，序号最小的进入
- 标记：进程离开是序号为0，不为0的序号为标记
硬件解决
- 开关中断法：在进入临界区后关掉CPU中断，不让指令切换，只适合单CPU
- 硬件原子指令法：把进入区代码用硬件实现，只需一条指令即可完成所有工作，不会发生在临界区切换指令的行为

面包片算法

while(true) {
    choosing[i] = true;	// 对 number[i]的保护
    number[i] = max(number.begin(), number.end()) + 1;// 序号小（先申请）的进程先执行
    choosing[i] = false;
    for(int j = 0; j < number.size(); ++j) {
        while(choosing[j]) { ; }	// 其他进程在未给number赋初值时就切出了
        while(number[j] != 0 && number[j] < number[i]) { ; }	// 有序号小的进程在队列中
    }
    ...	// 临界区代码
    number[i] = 0;	// 表示修改信号量执行完毕
}

临界区的代码需要满足互斥进入、有空让进和有限等待的要求

信号量的实现

在实际的操作系统中(Linux 0.11)，信号量的定义和上文所说的有所不同

上文用正负代表进程是否需要阻塞 / 唤醒。而在操作系统中，用 1 代表阻塞，用 0 代表唤醒

在唤醒时，一次性唤醒所有的进程，在阻塞时，将信号量置为 1

sleep_on(PCB *queue){
    PCB temp = *queue; *queue = current;	// 将当前PCB添加到信号量进程队列的队首
    current.state = TASK_BLOCK;				// 将当前PCB状态设置为阻塞
    schedule();								// 通过调度切换到下一个进程（有优先级）
    if(temp) {
        temp.state = TASK_RUN;				// 信号量进程队列的下一个进程设为就绪态
    }
}
wake_up(PCB *queue) {
    if(queue & queue.first()) { queue.first().state = 0; }	
}
P(semaphore s){
    cli();	// 进入区
    while(s.value && s.queue) { sleep_on(s.queue); }	// s = 1, 阻塞所有请求的进程
    s.value = 1;
    sti();	// 离开区
}

操作系统的实现方式将进程的切换用调度函数实现，考虑了优先级因素。

信号

信号的话是异常控制流中的一种，一般用来结束（kill）进程。通过 kill -l 命令可以查看所有的信号。

发送信号

通过 kill <PID> 可以发送 SIGTEM 信号，通过 Ctrl+C 可以发送 SIGINT 信号，C++ 中还提供了 kill() 函数来发送信号

#include<sys/types.h>
#include<string>
#include<iostream>
#include<csignal>
int main(int argc, char **argv){
    if(argc != 2) { std::cout << "[SendError]: Inpur Error!" << std::endl; }
    else {
        // 发射信号的函数，第一个参数是PID，第二个是信号
        kill(std::stoi(argv[1]), SIGINT);	
        std::cout << "[Send]: Send SIGINT to PID:" << argv[1] << std::endl;
    }
}

接收信号

#include<csignal>
#include<iostream>
void handler(int signal_number) { // 信号处理函数
    std::cout << "[Recive]: Caught SIGNAL " << signal_number << std::endl;
}
int main() {
    // 注册信号处理函数
    if(std::signal(SIGINT, handler) == SIG_ERR) {
        std::cout << "[ReciveError]" << std::endl;
    }
    while(true) {}	// 用来暂停
}

管道

管道就是把一个进程的输出当作另外一个进程的输入

匿名管道（PIPE）

匿名管道就是 cat test.cpp | grep include

在 C++ 中，可以通过

1
2
3

#include <unistd.h>
int pipe(int pipefd[2]); 
// 管道两端用fd[0]和fd[1]来描述，读的一端用fd[0]表示，写的一端用fd[1]表示。

创建匿名管道。父子进程中，一个进程通过写文件的方式操作管道，另外一个进程通过读文件的方式操作管道

匿名管道是在父子进程之间使用的。父进程在创造子进程前打开管道文件，然后产生子进程。此时子进程拷贝父进程的虚拟地址空间，父子进程在此时虚拟地址空间的映射的文件相同，能够访问这个管道文件。

这个管道只能在父子进程间使用，其他进程无法访问管道文件

有名管道（FIFO）

通过 mkfifo <fifo_name> 命令可以创建有名管道

1
2
3

int mkfifo(const char *pathname, mode_t mode);
// pathname：即将创建的FIFO文件路径，如果文件存在需要先删除。
// mode：和open()中的参数相同。

有名管道是一个文件，文件类型为 p ，此时这个文件相当于有了一个全局的名称，任何不想管的进程都可以进行访问。

消息队列

消息队列是由操作系统维护的以字节流为基本单位的一种进程通信机制。

相比于 FIFO，消息队列具有以下优点：

消息队列可以独立于读写进程存在，从而避免了 FIFO 中同步管道的打开和关闭时可能产生的困难；
避免了 FIFO 的同步阻塞问题，不需要进程自己提供同步方法；
读进程可以根据消息类型有选择地接收消息，而不像 FIFO 那样只能默认地接收。

共享内存

让多个进程的虚拟地址映射到同一个物理内存的地址，在多进程程序中，应该显示的使用

进程通讯机制(IPC)系统调用

文件I/O	IPC
`open()`	`msgget()`、`shmget()`、`semget()`
`read(),write()`	`msgsnd(), msgrcv()`、`shmat(), shmdt()`、`semop()`
`close()`	`msgctl()`、`shmctl()`、`semctl()`

死锁现象

当进程 $P_0$ 在某个时刻需要停下来等 $P_1$ 进程，而 $P_1$ 进程又需要停下来等待 $P_0$ 进程，这时候这两个进程都会因为在等待对方而停下来。两个进程因为进程同步而相互等待，无法继续执行的现象就叫做 死锁现象

解决死锁问题的方式有四种

死锁预防：就是限制死锁发生的条件
死锁避免：检测资源的请求，如果造成死锁则拒绝
死锁检测/恢复：每隔一段时间检测死锁发生与否，发生了则恢复
死锁忽略：不处理

出现原因

资源互斥：资源不等被共享，1 个资源只能 1 个进程用
不可剥夺：进程已经获得的资源，只能由这个进程释放
占有等待：已经得到了某个资源的进程可以再请求新的资源
循环等待：若干进程形成首尾相接的环状请求等待链

死锁预防

一次性请求所有资源（破环请求保持条件）：应用进程一次性请求所有可能需遇到的资源，之后就不存在请求资源等待其他进程了，这次请求由于没有占用任何资源，也不会造成死锁现象

资源的利用率低；而且应用程序需要对未来的需求有判断，编程比较困难
资源按顺序申请（破坏循环等待条件）：这样就不会形成环路了

造成资源的浪费

死锁避免

银行家算法 实现，通过判断是否存在一条可以执行下去的序列，进而判断这条请求是否造成死锁。如果存在一条序列，系统就处于 安全状态

操作系统会设置一个表，记录各个进程占有的资源、请求需要的资源和目前可以分配的资源

当目前操作系统有可分配的资源 $A:1,B:5,C:2,D:0$ 个时，当前的所有请求如下

进程占有资源请求资源请求后可分配资源执行顺序

$P_0$ $A:0,B:0,C:1,D:4$ $A:0,B:6,C:5,D:6$ $A:2,B:8,C:8,D:8$ 2

$P_1$ $A:1,B:4,C:3,D:2$ $A:1,B:9,C:4,D:2$ ×

$P_2$ $A:1,B:3,C:5,D:4$ $A:1,B:3,C:5,D:6$ $A:2,B:8,C:7,D:4$ 1

$P_3$ $A:1,B:0,C:0,D:0$ $A:1,B:7,C:5,D:0$ $A:3,B:8,C:8,D:8$ 3

进程	占有资源	请求资源	请求后可分配资源	执行顺序
$P_0$	$A:0,B:0,C:1,D:4$	$A:0,B:6,C:5,D:6$	$A:2,B:8,C:8,D:8$	2
$P_1$	$A:1,B:4,C:3,D:2$	$A:1,B:9,C:4,D:2$		×
$P_2$	$A:1,B:3,C:5,D:4$	$A:1,B:3,C:5,D:6$	$A:2,B:8,C:7,D:4$	1
$P_3$	$A:1,B:0,C:0,D:0$	$A:1,B:7,C:5,D:0$	$A:3,B:8,C:8,D:8$	3

vector<int> Available(m);	// m类资源对应可分配的资源数
vector<vector<int>> Need(n, vector(m));		// n个进程各自请求的资源数
vector<vector<int>> Allocation(n, vector(m));		// n个进程各自占有的资源数
vector<int> isFinish(n, false);	// 进程是否结束

while(true) {
    for(int i = 0; i < n; ++i) {
        bool isVaild = false;
        if(isFinish[i] == false) {
            for(int j = 0; j < m; ++j) { 
                if(Need[i][j] > Available[j]) { bool = false; break; } }
            if(isVaild) {
               	for(int j = 0; j < m; ++j) { Available[j] += Allocation[i][j]; }
                isFinish[i] = true;
            }
        }
        else { throw(); }
    }
}

请求出现时，先假装分配，任何调用银行家算法

死锁检测/恢复

定时检测或发现资源利用率低的时候检测。检测的算法和银行家算法一样

死锁忽略

一般 PC 机都使用死锁忽略，因为

死锁忽略处理代价小
死锁影响小，重启就可以解决
死锁预防让编程困难

进程管理Linux命令

PS：参看进程信息
TOP：类似于任务管理器，和 PS 差不多作用

内存管理

内存管理的核心就是要让程序存入内存中。

程序编译的时候，都是从0地址开始。而程序在运行时，肯会用到物理内存中的任意一处。因此，当程序变为进程的时候，就需要进行重定位。将编译器中的地址转换为实际的物理地址。

在编译和载入时重定位都存在自己的问题，因此在运行时重定位。（指令执行的时候把逻辑地址转换为物理地址）。这时候进程中的物理地址就相当于是 基址 + 偏移量，进程第一句地址就是基址，程序里的逻辑地址就相当于是 偏移量 。在CPU中，MMU负责内存地址的转换。

重定位就指的是把逻辑地址转换为物理地址的过程

这样在切换进程的时候，除了切换用户态栈、内核态栈、PC指针、PCB外，还需要切换基址寄存器来实现内存的切换。

内存分段

分段是因为在程序中，有些数据是常数，有些数据是代码，有些数据是变量。这些数据具有不同的属性，把不同属性的数据分开存放比较好。因此有了分段的概念

分段后一个基址就表示不了所有的数据，这时候，引入LDT（局部描述符表）。进行地址转换的时候就通过段号查询 LDT 表获取基址，然后通过基址+ 偏移来获得最终的地址。切换进程的时候，除了换掉进程管理的那些，还需要换掉 CPU 的 LDTR 寄存器。

例如常数和代码就是只读的，变量就是可读可写的

内存分页

进程执行前需要载入内存中，执行完之后要从内存中释放掉，而不同的进程占用的内存大小不同，因此就会有碎片。

当给一个进程分配新的内存时，有不同的分配方法：最差适配、最佳适配和最先适配。然而这些分配方法都只适用于特殊情况，因此引入了分页。

实现

将所有内存离散化，划分为一片一片固定大小的内存，应用程序使用时就给它完整的片，释放也是释放完整的片。这样就没有内存碎片的问题了，每个进程最多浪费其中一页。

为了能够还原出原来的程序，需要页表来记录这个进程每一页对应的物理地址。由于每一页都是固定的大小，因此根据偏移量可以计算出代码对应的页号，根据页号查询页表，找到对应的物理地址即可。

空间优化

页划分太细的话页表占据的空间就会很大。

采用多级页表。页表被分为两级，一个是页目录表，一个是页表。页目标中某一项完全没有使用，就不需要建立它的页表，这样就节省了空间

时间优化

采用快表。

把最近使用的页号和物理地址的对应关系用硬件记录下来，这样就节省了时间

总结

将物理内存分页并以页为单位进行内存分配，解决内存碎片的问题
分页后通过页表实现地址转换
采用多极页表降低存放页表造成的空间开销
采用快表降低多极页表造成的时间开销

段页结合

对应用程序来说，希望在操作系统中分段，把每个段分开存储，独立编址。对物理硬件来说，希望在操作系统中分页，提高物理内存的使用效率。因此，操作系统既要实现分段也要实现分页。

解决方法是，先将程序分段，并建立映射，储存在一个中间结构中，然后每一段在存储的时候分页存储在物理内存中，并建立页与页框的映射。

这个中间结构就是虚拟内存，虚拟内存是连接分段和分页的桥梁。

一个操作系统一个虚拟内存，一个进程一个虚拟地址空间

目前的操作系统放弃了分段，只保留了分页

内存的换入换出

对 64 位系统的每一个进程，其虚拟地址空间大小是18,446,744,073G，对32位系统，其虚拟地址空间的大小是4G。然而，实际的物理内存没有这么大，因此就需要时不时把内存中的数据释放掉，给下一个进程。然后等下次用到时再从硬盘中读取。

内存换入

内存换入的核心就是从硬盘中将数据移入物理内存，并将虚拟内存和物理内存进行关联。内存是一页一页的分配给内存的，同样也是一页一页从硬盘中调取的，因此内存换入是通过 申请调页 来实现的。

在页表中有一项用来表示这页内存是否在物理内存中。MMU在地址转换前会查看页表中的那个位置是否存在。如果存在就将转换后的地址发到地址总线；如果不存在，说明这一页不在物理内存中，就会申请调页。调页结束后将地址发送到地址总线。

请求调页

操作系统通过中断来实现。当不在内存中时，触发缺页中断。

中断处理函数会找到一块空闲的物理内存，然后把硬盘中对应的数据写入到那一页，然后修改页表建立联系。

void do_no_page(unsigned long error_code, unsigned long address) {
    address &= 0xfffff000;	// 找到对应的页
    page = get_free_page();
    bread_page(page, current->executable->i_dev, nr);	// 找到磁盘中当前运行的可执行程序，把那一页赋值到空闲页中
    put_page(page, address);	// 在页表中将空闲页与虚拟地址关联起来
}

内存换出

在上面 get_free_page() 中要找到一个空闲页。当物理内存全部填充满了就需要将一页内存换出了。而将哪一页换出则需要看采用了什么 页面换出算法

FIFO
LRU（Least Recently Used）算法：将最近最少使用的页置换出去。具体实现就是对每一页记录上次访问到现在的时间，时间最长的那一页就是需要置换出去的页。（该算法在实际过程中维护这个参数需要耗费太长的时间，不适用）
clock算法：近似的LRU算法。对每一个页维护一个 bool 类型的值 R。R 为 true 表示最近访问过；R 为 false 表示最近没访问过，有换下的风险。设置两个指针，一个移动快的指针负责更新最近使用的信息，一个移动慢的指针负责选出要换出的页。
- 快的指针 (扫描指针)：定期扫描所有的页面，将页面中所有页的 R 改为 false
- 慢的指针 (换出指针)：在缺页的时候工作，扫描页，将 R 为 false 的那一页换出

虚拟内存

虚拟内存的作用

保护了每个进程的地址空间不被其他进程破坏
虚拟内存为每个进程提供了相同的内存模型，便于内存的管理
虚拟内存能够让进程使用比物理内存大的内存空间

虚拟内存的使用（地址翻译）

CPU想要访问内存中的数据时，

将这个数据的虚拟地址（VA）发送给内存管理单元（MMU）
MMU拿到VA后，取出VA中的虚拟页表号VPN，然后再快表（TLB）中进行查询
如果在TLB中找到了VPN对应的物理页表项（PTE），则返回PTE给MMU

PTE的key是VPN，表项有物理页号、这块页的权限、这块页是否对应有物理内存等信息
如果在TLB中没有找到
1. 在内存中的页表中根据VPN进行查找。如果是多级页表，只有最底层的页表中存放的是PTE，其他级的页表存放着VTE，VA中分出多级VPN，然后一级一级的查找，最终查询到最底层的页表得到PTE
  
  VTE表的项目就是下一级页表的地址了
2. 将得到的PTE返回给MMU，MMU将新的到的PTE存放在TLB中
MMU对得到的PTE判断这块页是否对应有物理内存
如果有物理内存，计算PV
如果没有物理内存
1. MMU将触发一个缺页中断，CPU运行缺页中断对应的系统调用
2. 缺页处理函数判断这个地址是否合法、访问这个地址是否合法（此时是内核态）
3. 缺页处理函数选择一个牺牲页，如果这个牺牲页被修改过，就把它换出磁盘
4. 缺页处理函数换入新页，并更新内存和TLB中的PTE
5. MMU计算PV
根据PV对物理内存进行访问等操作

内存相关Linux命令

free

free 命令负责查看内存的使用情况

pi@raspberrypi:~ $ free -h
              total        used        free      shared  buff/cache   available
Mem:          1.8Gi       104Mi       1.5Gi       8.0Mi       250Mi       1.6Gi
Swap:          99Mi          0B        99Mi

-h 表示用人类友好的输出样式，不加就是以 k 为单位的显示

Mem 表示实际的物理内存大小，Swap 表示磁盘交换分区的大小
free 表示真正空闲的内存大小（不含缓存），share 表示多个进程共享的内存，buff/cache表示缓存的大小

pmap：查看进程的内存映射

IO管理

IO管理就是对外部设备的管理，操作系统将不同的外部设备统一抽象成了文件，对外设的使用，就是读写外设对应的文件。

操作系统中有几种类型的文件：普通文件、字符特殊文件和块特殊文件。字符特殊文件和块特殊文件对应外设。字符特殊文件用于输入输出（键鼠、显示器和网络），块特殊文件用于磁盘。

在管理外部设备时，有两条主线

CPU发送指令给外设
外设工作完后通过中断通知CPU

下面以显示器驱动为例介绍 CPU 发送命令给外设，以键盘为例介绍外设中断通知 CPU

文件管理

在 C++ 中，我们通过

1 2	`ofstream file("Demo.txt"); file << "Test" << endl;`

向 Demo.txt 文件输出 Test 文字。

而磁盘的使用是通过CHS（柱面cylinder、磁头magnetic head和扇区sector）这几个数据让磁头移动到对应的位置，然后读取磁盘上的数据。

操作系统通过一层层抽象，将CHS这些物理数据变成了路径名+文件名的形式。

生磁盘的使用

抽象1：从磁盘块到CHS

磁盘的访问每次都需要告诉磁盘驱动器CHS三个数值，这样十分麻烦，可以使用一个词 磁盘号 代替这些

由于磁盘花费时间：寻道（移动磁臂到指定柱面） > 磁头 > 扇区。因此磁盘中数据的排列要从扇区开始，转完了一个扇区，就到下一个磁头，再到下一个柱面。因此磁盘中的每一个位置 (C,H,S) 就都可以通过一个整数 sector 编码。其中，Sectors 表示一个扇区的大小，Headers 表示一个磁头的大小

$sector=C\times(\text{Headers}\times\text{Sectors})+H\times\text{Sectors}+S$

(C,H,S) 就很容易从 sector 反推出来了

$S=sector\%\text{Sectors}\\ H=sector/\text{Sectors}\%\text{Headers}\\ C=sector/\text{Sectors}/\text{Headers}$

由于磁盘的旋转速度很快，操作系统为了提高系统运行速度，一次性读取多个扇区，这多个扇区被叫做盘块。

$sector=blocknr\times\text{blocksize}$

其中，blocksize 就是盘块中扇区的大小

抽象2：多进程队列

上面描述了一个进程使用盘块的情景，多个盘块使用就需要考虑到调度问题，要考虑用哪一个进程访问，就需要调度。

因此进程向操作系统发出使用磁盘的请求，操作系统从请求队列中选择一个请求，读取出其中的盘块号，计算出CHS，然后通过 out 指令发送给磁盘控制器。

常见的磁盘调度算法有

FCFS：先来先服务
SSTF(Short seek time first)：最短寻道时间优先，不过这样对磁盘的请求服务机会会不均等
SCAN：磁盘调度扫描算法，向一个方向进行扫描，并处理经过的所有磁盘请求，位于中间的请求还是占便宜了
CSCAN：循环扫描算法，在SCAN的基础上当这个方向没有请求后，就迅速复位到另一个方向的最大请求位置

抽象3：高速缓存

由于程序具有一定的局部性，因此同一个文件可能会被多次访问，频繁访问磁盘会显著降低系统运行效率，因此可以把最近访问的数据存储到内存中，当用户请求的盘块号在高速缓存中，操作系统会直接将信息返回。

基于文件的磁盘的使用

抽象4：从文件到多进程队列

这层抽象处理 file << "Test" << endl; 语句。对用户来说，文件就是一个字符流，访问文件就是读取字符流，在文件中写内容就是在字符流中的某个位置添加字符。这一层就是通过字符流和它的偏移量来找到对应的盘块号。这层抽象的关键就是建立 (文件,偏移量) 到盘块号的映射。

这种映射有多种方式：

顺序存储（有些浪费）
链式存储（查询效率低）
索引存储

UNIX采用的是多极索引，小文件不索引，中等文件一级索引，大文件二级索引

在访问时，根据文件找到其FCB，然后根据偏移量的大小分别进行直接读取、一级索引、二级索引操作，得到系统的盘块号，然后根据盘块号计算CHS，进行数据的读取。而 file 变量与文件的 FCB有关

FCB也称为 iNode 。在 Linux 操作系统中，可以使用 df -i 查看 FCB 的使用情况

关于inode(index node)这里有一篇很好的文章：http://www.ruanyifeng.com/blog/2011/12/inode.html

抽象5：从文件名到文件

这层抽象处理从文件名找到FCB，即 ofstream file("Demo.txt");

磁盘在用户眼中是一颗目录树。因此，磁盘管理器和操作系统就需要将树构造出来。目录的信息存放在 FCB 中（目录和文件都有 FCB ）。每一层目录的FCB中都存放一个散列表，里面存放 <string name, int number> (key 是文件/目录名，value是文件的/目录的FCB号)。

进行目录解析时，例如当前目录为 /data 要进入子目录 /data/test ，操作系统会在 /data FCB中的 inode 数组中匹配 test ，得到 /data/test 的 FCB号，然后根据 FCB号就可以读到 /data/test 的 FCB，也就进入了 /data/test 目录，迭代下去就可以找到最终的文件。