本文最后更新于：2023年6月22日上午

知识补全计划

目前打算按以下顺序补完：操作系统：精髓与设计原理

x86汇编

相关网站：

操作系统：精髓与设计原理

由于本人已经学过其他教材讲解的操作系统，这里仅记录那些我认为重要的点,并且仅记录容易记录的、整体性的知识，细枝末节的知识就算了。

作者认为的与操作系统有关的各种知识分布图：

flowchart LR
 j([进程描述和控制])
 d([调度])
 n([内存管理])
 b([并发])
 i([I/O和文件管理])
 q([嵌入式])
 a([安全])
 f([分布式])
 j<-->d
 j<-->b
 n<-.->d
 n<-.->b
 n<-.->i
 n<-.->q
 n<-.->d
 d<-->i
 b<-.->a
 b<-->f
 i<-.->a
 q<-.->a
 a<-.->f

背景知识

系统概述

计算机俯视图：

指令执行

本书举了一个例子来描述指令的执行：

pc存储指令的地址，存储器相应地址的数值被存放到ir,ir解码把地址940的数据0003放入寄存器ac；之后pc自加1,301的5941被ir解码，使ac的数值与941地址的数值相加；302的2941被ir解码,ac的数被放入地址941中。

中断

在csapp中，一个令人印象深刻的标题叫做“信息就是位+上下文”，os通过执行上下文切换来提供“进程”这一虚拟概念，

同时,由于cpu主频远超i/o bus的主频，cpu在进行需要大量传输数据的工作时必然会处于空闲状态，因此如何在i/o阻塞时让cpu执行其他工作被叫做“中断”.本书给出了有中断和没有中断的效率对比:

简单的中断通过把必要的上下文压入栈来实现。多个中断通过定义中断优先级来实现。

存储

现代存储器出于cpu对不同区域数据的访问频率不同开发出了不同访问速度的硬件：

i/o

可编程i/o不具有与处理器的协同工作能力，不具有中断能力，而且处理器只能等待programmed i/o完成；中断驱动i/o显然具有与处理器协同工作的能力，且具有中断能力;DMA直接内存存取则是通过处理器对数据直接读写（通过使用dma模块）来高效完成多字i/o处理。

结构

现代计算机具有：

对称多处理器，在进行高并行处理时，这些处理器是等价的
多核计算机，通过在芯片上直接集成多个处理器、高速缓存来提高计算机的处理能力

os

现代操作系统往往提供程序开发、运行，i/o设备访问，文件访问控制，系统访问，错误检测和响应，监控资源等功能。同时，os必须被设计为易于移植的，其结构被描述为：

最早的os以串行方式处理需求，用户必须手动切换磁盘等来执行程序；在这之后简单批处理系统则通过在用户和硬件之间添加一个常驻内核的程序来帮助用户完成对系统的调度，并通过监控程序来实现对处理器的操作。多道批处理系统则实现了下图的功能：

也即同时处理多个程序（简单来讲）。分时系统则是实现了交互模式，即允许多个用户同时访问系统，其原因在于os控制每个用户程序在极短的时间内交替执行用户程序从而令用户感觉像是只有一个人在运行程序。现代操作系统在设计时，往往采用了多种方法，如只给内核最基本的功能（微内核）、分布式设计、采用多线程而不是多进程以及对称多处理的调度方式等.

一个os的系统可靠性被定义为从t=0到t=t时系统的正确运行概率，其平均失效时间，平均修复时间MTTR则指修复或替换错误所花费的平均时间,因此一个系统的可用性

现在操作系统主要分为windows,bsd,linux，mac这四类。其中linux是由很多模块组成的，这些可加载模块的两个重要特征是 动态连接和可堆叠模块.动态连接指内核模块可被随时加载连接到内核，或者随时被断开连接移除内存。可堆叠模块指模块按照层次结构排列,多个类似模块可移到单个模块中,便于模块加载。

进程

进程描述和控制

os要确保资源对所有程序可用，并且要在多个程序之间切换，保证资源能够得到充分利用，进程就是os为了方便管理而提出的概念。进程的基本元素是程序代码和相关数据集，在进程执行的任意时刻，可以由如下元素表示：

标识符：唯一的标识符号
状态：如运行，阻塞，就绪
优先级：进程之间的优先顺序
程序计数器：pc
内存指针：程序代码和进程相关数据的指针，以及与其他进程共享内存块的指针
上下文数据：执行进程时处理器的寄存器中的数据
I/O状态信息：显式i/o请求，分配的i/o设备和被进程使用的文件列表等
记账信息：包括处理器时间总和、使用的时钟数总和、时间限制、记账号等

这些信息被存储在进程控制块中：

五状态模型

os要对进程进行处理，考虑这样的情况：假设处理器以轮转方式操作进程，即以一种单个队列里先进先出的方式处理进程，那会怎样？显然，会存在一些处于非运行态但已经就绪的进程,不能只考虑”最老“的进程.作者提出了这样一个五状态模型：

运行态：进程执行
就绪态：进程做好准备，有机会就执行
阻塞态：进程在某些事件发生前不能执行
新建态：os尚未把他加入可执行进程组
退出态：os从可执行进程组中释放出的进程

挂起

对于五状态模型，我们可以按照多级队列、设置进程优先级等方式提高cpu的利用率。

但是还存在这样一种情况：内存中的所有进程都在等待i/o,此时cpu未进行对进程的任何处理，直至i/o完成才能继续。

为了更高效率的使用cpu,我们需要把等待i/o的一些进程挂起到内存之外，使cpu此时可以处理其他不需要i/o的进程。

这种 交换技术 是把内存中某个进程的一部分转移到磁盘中。

我们加入挂起状态后的模型如下：

就绪态
阻塞态
阻塞/挂起态
就绪/挂起态
新建态
运行态
退出态

操作系统控制表的通用结构：

进程控制块的元素：

上图从上到下分别是进程标识信息，进程状态信息，进程控制信息

进程控制

进程分为用户模式和内核模式。

在64位IA-64结构的intel itanium处理器中，就包含了一个current privilege level的2位字段去指示当前进程的特权级别。

在进程创建的时候，每一个进程都会有一个唯一的标识符，一些空间，os会初始化进程控制块，并做一些其他的操作。

那么进程之间如何切换呢？

进程切换即把控制权交给os,在由os进行处理，可以是中断（来自当前执行进程的外部）、陷阱（当前进程相关）以及系统的显式调用。对于普通中断，控制权会先被移交给中断处理器，中断处理器进行一些工作后在将控制权移交给相关的os例程。对于陷阱，os会先判断是否致命。系统调用则发生在如进程i/o时对用户态的处理。

由此分为模式切换以及进程切换两种切换模式。对于 模式切换 ，在发生中断时，pc被置为中欧你那个段处理程序的开始地址，从用户模式切换到内核模式，之后的做法取决于之后的信息。模式切换可以不改变进程的状态。对于进程切换，往往需要比模式切换更多的开销，os必须使进程的环境发生实质性变换。

线程

在之前的讨论中，进程的两个特点是资源所有权以及调度/执行权利，但在实际上，这两个特点是独立的，操作系统为了区分他们，通常将调度/执行权称为线程/轻量级进程，将资源所有权称为进程。所谓多线程，指的是os在单个进程内支持多个并发执行路径的能力。

在多线程环境中，进程被定义为一个资源分配单位以及一个保护单位，进程中的所有线程共享该进程的状态和资源。

书中举了这样一个例子，文件服务器对每一个新的文件请求都会创建一个新线程，实质上加快了系统处理的能力。

改变线程状态的四种基本操作是：

派生，新建进程时会为该进程派生一个线程，线程可以派生另一个线程，并提供相关指针，新线程存放在就绪队列中。实质上我觉得是一种虚拟化技术，通过派生把进程线程统一起来。
阻塞，和进程类似
解除阻塞
结束，线程结束时释放寄存器上下文以及栈

有一个叫RPC的以前没听过：

用户级线程以及内核级线程的直观表示：

user-level thread的优点在于对每一个应用程序都可以定制，可以对任何os制定不同的算法，但不可以利用多处理技术，相当于运行多个程序执行同一件事，无法利用多处理器的效率。书中列举了不同os的线程和进程之间的比例关系，

我比较好奇的是trix的M:N以及适用于分布式操作系统的1:M的ra操作系统。

现在讨论一下linux中的进程和线程管理。

linux的进程由一个task_struct数据结构表示，这个数据结构包含该进程的状态，调度信息，标识符，进程间通信，以及进程到其父进程、兄弟进程的链接，除此之外还包含时间信息、文件系统等。

linux实际上并不区分进程和线程，若两个进程共享相同的虚存，则可以把他们视为一个进程中的线程。其中线程并没有数据结构的定义。

linux中和每一个进程相关联的是一组命名空间，命名空间使得进程看起来像是系统上唯一的进程。当前linux有6中命名空间，

mnt,为进程提供文件系统层次结构的视图
uts,即unix timesharing，
ipc,隔离某些进程间通信资源，通过ipc可以控制进程间的通信
pid,隔离进程id空间，可以使不同pid命名空间的进程有相同的pid,如criu项目，就可以冻结一个正在运行的程序，把他放到硬盘中作为一个文件集。criu冻结的程序可以被恢复。
网络命名空间，用于隔离与网络相关的系统资源，包括网络设备，ip地址,ip路由表，端口号等。
用户命名空间，当一个进程克隆一个新进程的时候，可以为新进程一个新的用户命名空间，新的pid命名空间和其他所有命名空间。

并发性：互斥和同步

并发是解决多道程序设计技术、多处理器技术、分布式处理器技术的基础，相关术语：

并发的原理

考虑代码：

void echo(){
    chin=getchar();
    chout=chin;
    putchar(chout);
}

假如两个进程都用到该代码，os把该代码放到共享空间，那么假设在进程1调用echo时，putchar没有来得及执行，此时进程2调用echo,那么就会出现进程1的chin丢失的情况。

这意味着只有控制访问该变量的代码才能保护共享的全局变量。这意味着操作系统必须能够跟踪不同的进程，为进程分配释放并保护资源，同时必须保证一个进程的功能和输出结果必须与执行速度无关（硬件上实现类似功能的叫DR，生活上实现类似功能的叫菜鸟驿站）

进程交互：

进程竞争面临三个控制问题。

互斥，假设多个进程访问不可共享的资源如打印机，这时我们把打印机这种资源称为临界资源，使用临界资源的程序称为临界区，一次只允许一个程序在临界区中。由此产生另外两个控制问题，死锁以及饥饿。
死锁，即进程1和进程2分别占据资源r1,r2时，进程1需要再加上资源r2才能释放r1,进程2需要资源r1才能释放r2的情况。此时进程12都不会释放自己的资源。
饥饿指新加的进程3始终无法使用上述资源r1/r2的情况，也可以是os在分配资源时始终不分配给进程3的情况。

互斥——硬件

在早期的单处理器机器中，只需要保证临界区资源不被中断即可，通过在临界区之后启用中断来实现即可。代价是处理器只能交替执行程序，且只适合单处理器使用。

后来人们开始使用专用机器指令，这些指令保证了两个动作的原子性。常见的指令有compare&swap以及,这些指令不接受中断

compare&swap

int compare_and_swap(int *word,int testval,int newval){
    int oldval;
    oldval=*word;
    if(oldval==testval)*word=newval;
    return oldval;
}

基于这个指令的互斥规程是这样的：共享变量被初始化为0,唯一可以进入临界区的进程是发现共享变量为0的进程，其他进程则处于spin waiting的状态。

exchange:

void exhange(int  *reg,int *memory){
    int temp;
    temp=*memory;
    *memory=*reg;
    *reg=temp;
}

该指令的互斥规程类似于compare_and_swap

上述机器指令实现了对多个处理器以及多个临界区的处理，但仍然没有解决饥饿、死锁等问题。

常用的并发机制

信号量

基本思路是进程间通过信号量进行合作，首先把信号量初始化为非负数，semWait使操作数减一，semSignal使操作数加一，信号量为负数时执行semWait的进程被阻塞，而在信号量为负数的情况下每一个semSignal操作都会使等待进程中的一个进程解除阻塞。需要注意的是，每一个进程都可以执行smeWait以及semSignal,共享一个信号量；而为互斥量加锁的进程和为互斥量解锁的进程必须是同一个。