系统调用

fork

创建一个原有进程的精确副本。

被复制的东西：

• 所有的文件描述符
• 所有的寄存器

没被复制的东西：

• 程序正文

在fork后，原有的进程和其副本（父与子）就分开了。

返回值，用来在进程里区分谁是父谁是子：

• 在子进程中该值为0
• 在父进程中等于子进程的PID

shell为例：

while(true) {
    type_prompt();
    read_command(cmd, params);
    if(fork()!=0) {
        // 父
        waitpid(-1, &status, 0);
    } else {
        // 子
        execve(command, params, 0);
    }
}

waitpid

参数：

• 子进程PID，填-1就是任意一个子进程PID
• status（statloc）子进程的返回状态码
• 一般为0

exec

使得整个核心映像（core image）被一个文件所替代。

参数：将要执行的文件名、一个指向变量数组的指针、一个指向环境数组的指针（通常为0）

例子：

cp file1 file2

execve(cp, [file1, file2], 0)

main(argc, argv, envp)

argc为3，argv[0]为cp，argv[1]为file1，argv[2]为file2；没有envp。

exit(status)

status是用户指定的，status其实就是waitpid的staloc，子进程设定的status最终可以告诉父进程。

link

在unix中，每个文件都有唯一的编号（i-node）。

每个目录有一个i-node到文件名的表。

link时，是在指向目录里面创建一个新条目，i-node为原文件的i-node，文件名都link参数里指定的文件名。

目录和i-node是双向指向的，i-node也存有一个表，记录了指向该i-node的目录项。

进程和线程

进程模型

CPU利用率

• t1, 一个进程等待I/O操作的时间
• t, 一个进程停留在内存中时间
• p, 一个进程等待I/O操作的时间与其停留在内存中时间的比。
• n为同时存在的进程数量

利用率 = \( 1 - p^{n}\)

这是简单模型，只适用于进程之间互相独立。例如对于单CPU，即使进程就绪，但已有一个进程正在被CPU处理，那么还是会等待。

用户空间线程

优缺点：

内核空间线程

调度程序激活机制 和 上行调用（upcall)

IPC：信号量

• 创建信号量：sem_t *sem_open(const char *name, int oflag, 权限, 初始值)。返回值：返回一个信号量对象，若失败，则返回SEM_FAILED，并设置errno。man page
• P(down)操作，即int sem_wait(sem_t *sem)，检查信号量的值是不是大于0，若大于0，则减1并返回；若等于0，则进程睡眠，sem_wait阻塞不返回；非阻塞版本是sem_trywait，用返回值EAGAIN代替阻塞；限时的down操作是sem_timedwait，使得阻塞不是永久的。返回值：0代表成功，-1代表失败，并设置errno。
• V(up)操作，即int sem_post(sem_t *sem),对信号量加1，若是从0变1，那么那些阻塞在这个信号量的进程或线程会被唤醒。返回值同P。V操作是怎么都不会阻塞的。
• 本进程关闭信号量：int sem_close(sem_t *sem)。没什么特别的。
• 真·销毁信号量：sem_unlink，前提是open了信号量的进程已经调用了close或者已经结束了进程（调用了exit或者main函数返回），如果还没close就调用，那么没效果。

github代码实例，双信号量实现父进程和子进程的同步。

信号量2个能力：

• 实现互斥量
• 实现计数

IPC：futex 快速用户空间互斥

• linux特有
• 实现了基本的锁（很像互斥锁），但避免了陷入内核
• 内核服务：提供一个等待队列，它允许多个进程在一个锁上等待。把进程放到等待队列代价很大（系统调用）。
• 避免锁争用：没有争用时，futex完全在用户空间工作；加锁时，如果锁没有被锁，那么直接加锁成功，不需要陷入内核；如果已经被锁了，执行系统调用把线程放到等待队列（不自旋）。

IPC：管程 montior

原因：为了更易于编写正确的程序。

• 管程是编程语言的组成部分，能不能用管程得看是什么语言，例如java
• 任一时刻管程中只能有一个活跃进程
• 进程可在任何需要的时候调用管程中的过程（procdeure)
• 进入管程是的互斥由编译器负责，出错的可能性要小得多
• 写管程的人无需关心编译器是如何实现互斥的，只需知道将所有临界区转换成管程即可

IPC：消息传递

其实就是用socket来实现IPC。

IPC：屏障 barrier

概念上像是gpu渲染一帧，n个gpu核都在计算它负责的像素点，有的快有的慢，但必须全部核的任务都处理完毕，才能进入下一个阶段。

IPC：无锁化，RCU（读取-复制-更新）

调度

何时进行调度

1. 创建一个新进程后，需要决定是运行父进程还是运行子进程。可以任意决定。
2. 一个进程退出时必须做出调度决策。必须从就绪进程集合选择另外某个进程。
3. 当一个进程阻塞在I/O和信号量上或由于其他原因阻塞是，必须选择其他进程运行。阻塞原因会成为选择的因素，然而调度程序并不拥有做出这种相关考虑的必要信息。
4. 在一个I/O中断发生时，必须做出调度决策。可能等待I/O的进程变成就绪了，有三种可能，让新就绪进程运行；继续当前进程的运行；让别的进程运行。

根据如何处理时钟中断，可以把调度算法分2类：

• 非抢占式：进程自己释放CPU时/阻塞时，才会切换到别的进程。即时钟中断不会进行调度。
• 抢占式：让进程运行某个固定时段的最大值，然后挂起它，调度别的进程继续运行。前提是有时钟，不然就得用非抢占式的调度算法。

根据环境选择算法：

• 批处理。适合用非抢占式调度。一个进程需要运行长时间。也就减少了进程切换，优化了性能。
• 交互式。适合抢占式。
• 服务器。适合抢占式。
• 实时系统。一般是非抢占式。

调度算法目标

适用所有环境的目标：

• 公平
• 策略强制执行。即调度进程有一些优先级策略
• 平衡。保证系统的所有部分都忙碌

批处理系统的测量指标：

• 吞吐量：每小时完成的作业数量
• 周转时间：一个作业从提交到完成的统计平均时间

能够使吞吐量最大化的调度算法不一定就有最小的周转时间。例如，系统优先处理大量小作业导致长作业无法被处理，这样有做大的吞吐量但平均周转时间无限长。

交互式系统：

• 最小响应时间。能够让所有的交互式请求首先运行的则是好服务。
• 均衡性。满足用户的期望（这个概念比较模糊）

交互式系统的调度

轮转调度(round robin)

• 每个进程被分配一个时间片（quantum)。注意，进程可在时间片花完前提前结束运行，例如阻塞了。
• 时间片过小，容易发生抢占，过多的切换进程，降低CPU效率；
• 时间片太长，则引起对短的交互请求的响应时间变长。
• 一般为20~50ms

优先级调度

每个进程加一个优先级属性，优先级大的先执行完，再执行次优先的。

问题：只按优先级来执行进程的话，低优先级进程可能永远都不会被执行。

解决方法：

• 被执行的进程的优先级每个时钟滴答减1，直到低于次优先级进程时切换。
• 最大时间片法，用完时间片就轮到次优先的进程

优先级的赋予：

• 静态：人工分配，例如商业计算中心，高优先级的任务价格高
• 动态：根据 1/f公式分配优先级。例如在50ms的时间片中只使用2ms就挂起的进程，优先级为1/(2/50) = 25。

变种：按优先级分类，然后用轮转调度，高优先级的进程组里的进程集合轮转调度，优先执行，都执行完时切换到次优先级组。

多级队列

基于上面的优先级分类，设计了多级队列调度。

原理是：属于最高优先级类的进程运行一个时间片，属于次高优先级类的进程运行2个时间片，再次一级运行4个时间片；当进程用完分配的时间片后，它被移送到下一类。

例子：假设一个进程要完成计算任务总共需要100个时间片。一开始被分配1个时间片，然后就被换出，下次到它时获得2个时间片，又被换出。总共经历了1、2、4、8、16、32、64个优先级类。在64优先级类的第37个时间片就完成了工作。总共用了7次进程上下文切换。要比轮转算法轮转100次要高效。

最短进程优先

最短路程含义是进入运行到挂起的时间间隔最短，这种进程优先处理，对实时系统挺友好。例如交互式进程，每条用户命令相当于一次短作业。

但如何知道这个作业将执行多久呢？方法是用过去的数据来做预测，\( T = aT_{0} + (1 - a)T_{1} \)。

保证调度

也是绝对公平的调度。有两种情况：

• 多用户同时登录工作。每个用户可获得CPU的1/n的处理能力。
• n个进程在运行的单用户系统。每个进程获得CPU的1/n的处理能力。不过这种情况需要记录每个进程从创建以来已累积获得的CPU时间。因为没有时间片的概念，所以进程实际获得的运行时间和理应获得的时间可能会不一致，此时可以算一个比值（优先级），使得较亏的进程可以先运行。

彩票调度

即给每个进程发一些彩票。调度时，随机抽一张彩票，哪个进程持有这张彩票就被执行。

可以给某个进程赋予比别人多的彩票数量，来提高优先级(中奖几率)。

公平分享调度

这个是对于多用户环境而言的。每个用户的所有进程占x%的时间。有点像上面的保证调度。

调度策略参数化

例如一个数据库父进程下面有多个子进程，父进程才知道怎么调度子进程才是最优。那么就可以设计一种参数化调度机制，让父进程向内核设置参数，如子进程优先级，更好地做调度。

线程调度

要分用户级线程和内核级线程两种情况。

经典IPC问题

页面置换算法

最优页面置换算法

基于2点：

• 当缺页中断(page fault)发生时，有些页面在内存中，其中有一个页面（包含紧接着的下一条指令的那个页面）将很快被访问，其他页面则可能要10、100、1000条指令后才会访问，这个指令数就是标记
• 最优页面置换，就是置换掉标记最大的页面

然而无法实现，因为操作系统无法知道各个页面下一次将在什么时候被访问。

不过可以作为性能对比工具，例如弄个仿真程序，先跟踪一遍所有页面的访问情况，然后第二次运行则可以用第一次的数据来跑出最优页面置换算法。之后再用其他算法也跑一下，从而做对比。不过此方案问题在于是针对某个特定程序而言的。

最近未使用页面置换算法（NRU，not recently used）

首先每个页面设置2个状态位:

• R位，被访问时设置
• W位，被写入时设置

算法：

当启动一个进程时，它的所有页面的两个位都由操作系统设置成0，R位被定期地清零（比如每次时钟中断时）以区别最近没有被访问的页面和被访问的页面。

当发生缺页中断时，操作系统检查所有的页面并根据它们当前的R位和M位的值，把它们分为4类：

1. 没有被访问，没有被修改
2. 没有被访问，被修改
3. 被访问，没有被修改
4. 被访问，被修改

本算法随机地从类编号最小的非空类中挑选一个页面淘汰。

先进先出置换算法 FIFO

页面按照访问时间顺序组成链表，每次发生缺页中断时直接从表头的页面干掉，并把新页面放到表尾。

问题在于常用页面也可能会被淘汰，

第二次机会页面置换算法

这个是 FIFO的改进：要淘汰时，检查最老页面的R位，如果是0，那么可以置换掉；如果是1，那么就是最近访问过的，把R位设0，并移动到链表末端。

如果所有页面都被访问过了，那么退化为普通的FIFO。

时钟页面置换算法

上面的算法的问题在于要经常在链表移动页面。改进方法：改成环形链表，一个指针指向最老的页面。

当发生缺页中断时：

• 检查指针指向的页面，若R位为0，则淘汰该页面，把新页面放入这个位置，指针移动到下一个位置；
• 若R为1，则清除R位，指针还是++，重复这个过程直到找到一个R为0的页面。

最近最少使用算法（LRU）

在缺页中断发生时，置换未使用时间最长的页面。

假设还是用链表，要达到LRU，需要每次访问内存都更新链表：在链表中找到这个页面，删除它，然后把它移动到表头。

不用链表，有别的方案：

每个页表存一个属性：指令计数器，每条指令执行完后加1；当发生缺页中断时，检查所有页表项的计数器值，找到值最小的页面，就是最近最少使用的页面了。这是基于硬件的方案。

软件实现的LRU

NFU（Not Frequently Used，最不常用）算法：

内存里做一个表，把每个页面和一个软件计数器相关联，初值为0，每次时钟中断时，操作系统扫描内存中所有的页面，把每个页面的R位的值加到计数器上，这个计数器大体跟踪了各个页面被访问的频繁程度。发生缺页中断时，淘汰计数器值最小的页面。

改进的NFU——Aging老化算法：

因为NFU对旧状态记忆得太深，不能应对快速变化的程序状态，有可能根据计数器淘汰了最经常访问的页面。可以修改一下：

• 在R位被加进计数器前，计数器右移一位（除2）；
• 将R位加到计数器最左端的位而不是最右端的位；

发生缺页中断还是淘汰计数器值最小的页面。老化算法的问题在于计数器只有有限位，限制了它对过往状态的记忆能力。

基本工作集页面置换算法

• 工作集：一个进程当前正在使用的页面的集合称为它的工作集。
• 颠簸：如果内存太小不足以容纳整个工作集，那么每执行几条指令就会发生一次缺页中断
• 预先调页：在进程运行前预先装入其工作集页面

工作集的严格定义：在任一时刻t，都存在一个集合，它包含所有最近k次内存访问所访问过的页面，称为w(k,t)

w是k的单调非递减函数，且会收敛到一个稳定的范围。预先调页原理就是基于以下推测：程序上次结束时w有一个稳定范围，可预先装下这个范围的工作集。

实现条件：操作系统必须跟踪哪些页面在工作集中。

基于工作集的页面置换算法：当发生缺页中断时，淘汰一个不在工作集的页面。精确地统计工作集，就是确定一个k值。

问题：工作集的计算不容易。2种方案：

• 按使用频率计。成本比较高。k还是按次数的k。
• 按执行时间计。k变成秒数r，工作集变成在过去的r秒实际运行时间(使用了CPU的时间)中进程所访问页面的集合。

缺页中断时，需要扫描整个页表，找出适合的页面来淘汰。

工作集时钟页面置换算法

上面的算法问题在于需要扫描整个页表来淘汰页面。

改进（类似前面的时钟页面置换算法）:

建立一个以页框为元素的循环表。每次缺页中断时，首先检查指针指向的页面，如果R为1，则把R改为0，并把指针++，重复这个逻辑；R为0时，如果指针当前页面的生存时间大于r，并且页面是干净的（M=0），它就不在工作集中且磁盘上有一个有效的副本，置换替换掉此页框即可，如果M为1，为了避免写磁盘操作引起进程切换，指针继续++，检查下一个页。

总结

最好的算法是：

• 老化算法（LRU）
• 工作集时钟算法

分页系统的设计问题

进程之间的内存竞争

考虑多个进程的页面置换算法称为全局算法，反之就是局部算法。

全局算法一般是基于PFF，page fault frequency，缺页中断率，它指出了何时增加或减少分配给一个进程的页面，但却完全没有说明在发生缺页中断时应该替换掉哪一个页面。仅控制分配集的大小。

PFF的测量：PFFF = (当前1秒的PFF + 旧PFF）/ 2

负载控制

问题：即使是使用最优页面置换算法，也可能会发生颠簸，如内存不足的时候。

解决方案：将一部分进程交换到磁盘，释放他们所占有的所有页面。

页面大小

有公式可以算页面大小，对于平均进程大小为1MB，每个页表项为8B的系统，最优页面是4KB。一般范围是到64KB。

分离指令空间和数据空间

地址空间太小时，拆成2个空间就会改善情况。不过现在64位系统的地址空间很大，拆2个空间是因为别的原因了。

共享页面&共享库&内存映射文件

原因：避免在内存中有一个页面的两个副本。

策略：共享I空间。

还有问题：释放页面要考虑有没别的进程在使用这个页面。所以共享页面要有特殊的数据结构来记录。

其他问题：fork调用，理应拷贝数据段，但就会产生大量副本。解决方法是写时复制COW。

共享库就是DLL了，不过有个问题是地址。共享库要用相对地址，办法是编译时设置参数。

内存映射文件，应该就是共享内存了。

清除策略

弄个分页守护进程（paging daemon），定时被唤醒检查内存、看是不是要置换掉页面，如果已修改，那么要写硬盘，如果未修改且硬盘有副本，则直接清除。

有关实现

缺页中断处理流程

1. 硬件陷入内核，在堆栈中保存程序计数器。大多数机器将当前指令的各种状态信息保存在特殊的CPU寄存器中。
2. 启动一个汇编代码例程保存通用寄存器和其他易失的信息，以免被操作系统破坏。这个例程将操作系统作为一个函数来调用。
3. 当操作系统发现一个缺页中断时，尝试发现需要哪个虚拟页面。通常一个硬件寄存器包含了这一信息，如果没有的话，操作系统必须检索程序计数器，取出这条指令，用软件分析这条指令，看看它在缺页中断时正在做什么。
4. 一旦知道了发生缺页中断的虚拟地址，操作系统检査这个地址是否有效，并检査存取与保护是否一致。如果不一致，向进程发出一个信号或杀掉该进程(segment fault！)。如果地址有效且没有保护错误发生，系统则检査是否有空闲页框。如果没有空闲页框，执行页面置换算法寻找一个页面来淘汰。
5. 如果选择的页框“脏”了，安排该页写回磁盘，并发生一次上下文切换，挂起产生缺页中断的进程，让其他进程运行直至磁盘传输结束。无论如何，该页框被标记为忙，以免因为其他原因而被其他进程占用。
6. —旦页框“干净”后（无论是立刻还是在写回磁盘后），操作系统査找所需页面在磁盘上的地址，通过磁盘播作将其装入，该页面正在被装入时，产生缺页中断的进程仍然被挂起，并且如果有其他可运行的用户进程，则选择另一个用户进程运行„
7. 当磁盘中断发生时，表明该页已经被装人，页表已经更新并可以反映它的位置，页框也被标记为正常状态。
8. 恢复发生缺页中断指令以前的状态，程序计数器重新指向这条指令。
9. 调度引发缺页中断的进程，操作系统返回调用它的汇编语言例程。
10. 该例程恢复寄存器和其他状态信息，返回到用户空间继续执行，就好像缺页中断没有发生过一样。

指令备份

即怎么记忆发生中断的指令位置，以及怎么恢复。方法是在执行一条指令前用一个寄存器备份这条指令。

锁页面

例如缺页中断时把别的进程的缓冲区的页面置换掉了，别的进程如果用DMA传输数据中，就会覆盖掉了刚被装入的页面，全乱了。解决方法是对页面加锁。

后备存储

即置换页面，把页面放到硬盘哪里的问题。

方法：设立一个交换分区，专门来做这个事情。具体而言要3个区：正文、堆栈、数据。

分段

现在x86-64都去掉分段机制了，目测没有学习的必要。

文件系统

• 主引导记录：磁盘的0号扇区（Master Bot Record, MBR)，用来引导计算机
• 分区表：在MBR的末尾，给出了每个分区的起始和结束地址
• 活动分区：分区表的某一个分区被定为活动分区

启动流程：

1. 计算机被引导
2. BIOS读入并执行MBR
3. MBR确定活动分区
4. MBR读入活动分区的第一个块（引导块）
5. 引导块中的程序将装在该分区中的操作系统

Note：为统一起见，每个分区都从一个引导块开始，即使它不含有一个可启动的操作系统

文件的实现

• 连续分配。读取速度快，但容易产生碎片。存储时就需要知道文件大小。
• 链表分配。随机读取速度慢。指针占用一些字节，导致一些效率问题。
• 文件分配表FAT。在内存中弄一张表，用来获取磁盘块链表信息，从而避免了在磁盘块头存节点信息。随机读取速度变快。问题是如果块大小才1KB，但是磁盘空间1T，内存分配表就需要10亿个项，假设每项3个字节，就需要3GB内存。
• i节点。是对FAT的改进，把链表信息存到磁盘上形成一个i节点文件，打开某个文件时把i节点文件信息载入到内存。i节点的唯一问题是定长大小的话，怎么动态扩容。

目录的实现

目录系统主要功能：把文件名映射成定位文件数据所需的信息

• 目录：一堆目录项，kv对
• 目录项：k是文件名，v可以随意，一般是i节点号

问题：文件名不定长。定长的话容易浪费空间。

解决方案:

1. 让目录项大小不一致。问题一是如果移走一个文件会导致出现大小不定的空隙，二是目录项可能会跨页面，在读取文件名时可能会发生缺页中断。
2. 目录项大小一致，但把文件名移出目录项，放到目录最后的堆里。但就要对堆进行管理。

共享文件

• 硬链接：创建直接与目标文件关联的i节点。删除文件操作会变得复杂。
• 符号链接：创建一个符号文件（类型link），文件中只包含所链接的文件的路径。删除文件没什么大问题。额外开销时是要通过路径找到目标文件的i节点，以及符号文件本身还是要有一个i节点和一个磁盘块放路径，毕竟还是个文件。

文件系统

mmap

https://blog.csdn.net/hj605635529/article/details/73163513

https://blog.csdn.net/luckywang1103/article/details/50619251