OS1：知识点梳理 - 江舟的博客

目前对本文思路是在大纲的基础上，做题过程中对不熟悉的知识点进行扩展，12.28考试前每日更新。

—2023.12.23 19:05

多看书，研究概念，研究逻辑。

[TOC]

OS基础

1.计算机启动原理。

OS_1.3.pptx;

2.操作系统历史。（单道批，多道批，分时，实时操作系统）

OS_1.5.pptx;

3.Linux基础。

OS_3.1ppt;—OS_4.2.pptx;

（略过，暂时没看）

进程管理

4.进程

进程和程序
并发和并行
进程的概念和特征（结构特征，动态性，并发性，独立性，异步性）
进程的状态转换（创建态，中止态，就绪态，运行态，阻塞态）
进程间通信（共享存储，消息传递，管道通信）
进程调度（长期调度，短期调度，中期调度）
进程竞争内存资源紧张的方案（swapping，virtual memory）

二进制代码和常量存放于正文段，动态分配的存储区位于数据堆段，临时使用的变量位于数据栈段，进程优先级在PCB内。
进程的实体是代码、数据和PCB。PCB中包含的数据结构内容主要有四大类：进程标志信息、进程控制信息、进程资源信息、CPU现场信息。因此全局变量和PCB无关。

5.线程

线程的引入（减少进程切换和创建开销）
线程与进程的关系
用户级线程和内核级线程
多线程模型（实现和好处，多对一，一对一，多对多，二级模型，线程池）
fork()和exec()，另外还有waitpid()，execve()；

Q：

,用户级线程和内核线程的在中断时的区别。

A：用户级线程是有应用程序通过线程库实现，所有的线程管理工作都由应用程序负责，包括线程间的切换都无需操作系统的干预，但是只要一个线程堵塞，整个进程都会阻塞，并发度低。

内核级线程是由操作系统内核完成，因此它的切换需要在核心态完成，但是并发度高，一个线程堵塞其它的依然可以继续执行，但线程切换时候的成本高开销大。

另外，在系统调用时，用户级线程不能被系统所看到，因此以进程为单位，随着线程的增多，单个线程的执行时间会变少；但是内核级线程以线程为单位，可以得到良好的执行时间.
线程是CPU运行的一个基本单元：program counter 程序计数器，register set 寄存器集，stack space 栈空间

一个线程与它的对等线程共享：code section 代码段，data section 数据段，operating-system resources 操作系统资源

6.系统调度

cpu的调度可能发生在以下情况，运行到阻塞，阻塞到就绪（IO完成），运行到就绪（出现中断时）。
将CPU控制交由短期调度程序选择的进程，包括上下文切换，切换到用户模式，跳转到用户程序的合适为止以重新执行程序。
调度准则，评价指标
调度算法（FCFS（护航效果），SJF，最高响应比，优先级，轮转（合适时间片），多级反馈轮转（不同优先队列不同时间片））（SJF分为抢占和非抢占两种，没有特殊说明，默认非抢占）

CPU-I/O区间周期：进程执行由CPU执行和I/O等待周期组成。
CPU调度算法是操作系统用来选择下一个要执行的进程的的方法。
分时操作系统中进程调度算法中对普通进程常常采用的是优先级轮转法，请问如何保证不会有进程因为优先级太低而饥饿？

A: 采用动态调整进程优先级的方法。动态降低长时间占用 CPU 进程的优先级，低优先级的进程的优先级则相对升高，最终得到运行。

7.竞争与同步

同步与互斥
进入临界区的四个准则（空闲让进，忙则等待，有限等待，让权等待）
临界互斥基本方法
信号量机制（整形信号量，记录型信号量）
经典同步问题（理解PV操作）

Q：

临界互斥的基本方法的理解

A：

I：软件上

1）单标志法。进程一在访问完后会转交给进程二，但是如果进程二不想占用临界资源会导致临界区空闲。违反”空闲让进“原则。

2）双标志法先检查。在进程一想要进入临界区时会先检查是否有其它的进程想进入临界区，如果没有进程一会访问临界区。由于在检查后的切换时会划分一定的时间，这段时间如果进程二也检查结束，回导致同时进入临界区，违反“忙则等待”原则。

3）双标志法后检查。如果后检查的话，两个进程同时想进入临界区时，都会先打算进入再检查对方状态，然后两个进程相互谦让，最后导致“饥饿”现象，违反“空闲让进”和忙则等待“现象。

(原子操作)

4）皮特森算法。结合双标志法和但标志，二者同时想进入时发生孔融让梨。

II：硬件上

1）中断屏蔽法。仅对当前CPU有效，不适合多处理器。

2）硬件指令法。不满足”让权等待“，可能发生”饥饿“。
什么时候需要用mutex也就是互斥锁，分清同步和互斥？

A：mutex是一种操作系统提供的一种同步机制，用于保护多个线程共享的资源，防止数据的混乱和冲突。当多个线程需要访问同一个资源时，例如一个全局变量、一个文件、一个设备等，如果不加任何控制，可能会导致数据的不一致或者错误。为了解决这个问题，可以使用mutex来实现互斥访问，即一次只允许一个线程对资源进行操作，其他线程必须等待，直到该线程释放了资源。这样可以保证资源的完整性和正确性。

理解PV操作的含义

A：

P:(wait)
void  wait(semaphore S){
    S.value--;
    if(S.value<0){
         add this process to S.L;
         block();
    }
}
   
V:(signal)
void  signal(semaphore S){
    S.value++;
    if(S.value<=0){
         remove a process P from S.L;
         wakeup(P);
    }
}

8.死锁

死锁的产生必要条件（互斥，占有并等待，不可抢占，循环等待）
死锁预防（针对发生的必要条件）
死锁避免（银行家算法，去除死锁的可能性）
死锁检测和解除（检测：利用资源有向图；解除：进程终止，抢占资源（回退，饥饿））

Q：

实际中操作系统应对死锁的可行方法。

鸵鸟算法。因为处理死锁成本太高，而死锁出现的频率较低，故可以忽略死锁的发生。

(鸵鸟算法是一种不采取任何措施的方法，它假设死锁很少发生，或者死锁的代价可以接受)

Spooling 技术。假脱机技术。为临界资源增加一个等待队列，使其好像可以被共享使用，如打印机。

(Spooling 技术是一种预防死锁的方法，它通过使用缓冲区来存储临界资源的请求，从而避免了进程之间的互斥和占有并等待的条件。)

当死锁发生时，杀死运行时间较短的进程，损失较小，因为容易恢复。
死锁的产生、防止、避免、检测和解除 - 知乎 (zhihu.com)

内存管理

9.内存管理

基础背景
内存的构成
连接方式（静态连接，装入时动态连接，运行时动态连接）
装入方式（直接装入，静态重定位，动态重定位）
内存连续分配的方式（单一连续分配，固定分区分配，动态分区分配）
动态分区分配的算法（首次适应，最佳适应，最坏适应，邻近适应）
非连续分配的方式（基本分页存储管理，基本分段存储管理，段页式管理）（重点）

Q：

背景的简单介绍。

A：

程序必须放入内存的进程空间中才能被执行

CPU能直接访问的存储器只有内存和处理器内的寄存器

直接存取要求内存速度能够和CPU取址速度相匹配，大到能装下当前运行的程序和数据，否则CPU执行速度就会收到内存速度和容量的影响而得不到充分发挥。
最坏适应算法优先使用大分区的话，剩余的空间也多，从此减少碎片，但是不利于大进程。
理解分段分页的优缺点：

分页：提高内存利用率，用硬件机制实现，可以实现内存的动态分配，共享和保护（受到限制），对用户不可见。注意分页的大小时固定的，因此不利于数据的动态增长。

缺点：逻辑地址空间划分只简单依靠页面大小，缺乏内在逻辑性，导致一方面相关内容被分散到多页上，页面置换不当时容易造成内存抖动，另一方面不同性质的内容被分到同一页中，使得页面权限保护设置困难。

分段：便于编程，程序和数据的共享和保护，公共代码段可以通过映射共享到多个进程，动态链接实现方便，数据动态增长等。在内存中无法不连续存储，易形成内存外碎片，降低内存利用率。

段页式：

段是信息的逻辑单位，根据用户的需要划分，因此段对用户是可见的；页是信息的物理单位，是为了管理主存的方便而划分的，对用户是透明的。

页的大小固定不变，由系统决定。段的大小是不固定的，由其完成的功能决定。

由于段是信息的逻辑单位，因此便于存贮保护和信息的共享，页的保护和共享受到限制。

以段为单位调入调出，以页为单位非连续存储
多级页表优点的是减少页表所占的内存空间。
cache

10.虚拟内存

背景：虚拟空间和实地址空间
交换技术（覆盖技术和交换技术）
实现方式（请求式分页管理，请求式分段存储管理，请求式段页存储管理）
页面故障处理（重点）
页面置换算法（OPT，FIFO，LRU（Aging），**CLOCK**，**改进的时钟置换算法**）
页缓冲算法
帧分配（难点）
内核进行内存管理的方法（Buddy系统，Slab分配）（难点）
工作集
倒排页表

Aging老化算法与LRU类似。

老化算法与 LRU 相比，主要有两点区别：

（1）老化算法记录使用情况的寄存器只有有限位，比如 8 位，无法记录所有使用情况。

（2）同一时间间隔内只使用 0/1 区分页面使用情况，无法详细区别间隔内的具体时间

文件管理

11.File System Interface

文件分类：流式文件，记录式文件（顺序文件，索引文件，索引顺序文件）
文件目录结构（单级目录，两级目录，树形目录，无环图目录路径）
文件物理结构（连续分配，链接分配，显示链接，索引分配，多层索引）
inode
硬链接和符号链接

12.File System Implementation

文件存储空间管理（空闲表法，空闲链表法，空闲盘区链，位示图法）
文件保护（口令保护，加密保护，访问控制）

13.Mass-storage system

磁盘结构
磁盘调度算法（FCFS，SSTF，SCAN，LOOK调度算法，C-SCAN循环扫描算法，C-LOOK算法）
LVM
RAID（了解）

设备管理

14.IO System-Devices

IO设备分类（传输速率，信息交换单位，设备共享特性）
IO控制方式（程序直接控制方式，中断控制方式，DMA控制方式，通道控制方式）
缓冲技术

附录：

帧分配和页缓冲算法是两种不同的操作系统技术，它们都涉及到虚拟内存的管理，但是有不同的目的和方法。

1.帧分配

帧分配是指如何将物理内存中的页帧（固定大小的内存块）分配给需要内存的进程。

帧分配的目的是实现虚拟内存的映射，即让进程可以使用比物理内存更大的地址空间。

帧分配涉及到以下几个方面：

帧分配算法：决定给每个进程分配多少帧，以及如何选择被淘汰的帧。常见的帧分配算法有平均分配、按进程大小比例分配、按优先级分配等。
帧分配策略：决定是否允许进程抢占其他进程的帧。常见的帧分配策略有全局分配和局部分配。
帧分配类型：决定是否需要为函数创建堆栈帧。常见的帧分配类型有帧函数和叶函数。
帧分配对齐：决定是否需要使帧对齐到特定的边界。常见的帧分配对齐有基本对齐和扩展对齐。

2.页缓冲算法

页缓冲算法是一种操作系统中用于提高页面置换效率的方法。

它的基本思想是将被淘汰的页面暂时保存在内存中，而不是立即写回磁盘，以便在需要时快速调入。

页缓冲算法的目的是：

提高页面置换的速度：当一个页面被淘汰时，如果它已经被修改过，那么就将它放入已修改页列表中，而不是直接写回磁盘。这样可以节省磁盘I/O的时间，提高页面置换的速度。
减少磁盘的碎片：当一个页面被修改过后，它的内容可能和磁盘上的原始内容不一致，如果频繁地写回磁盘，可能会导致磁盘的碎片增加，影响磁盘的性能。通过将修改过的页面放入已修改页列表中，可以延迟写回磁盘的时间，减少磁盘的碎片。
提高页面的命中率：当一个页面被淘汰后，如果它很快又被访问，那么就可以在已修改页列表中查找它，如果找到了，就可以直接将它调入内存，而不需要再从磁盘读取。这样可以提高页面的命中率，减少缺页中断的次数。

3.内核的内存管理方法

内核进行内存管理的两个方法是Buddy系统和Slab分配，它们都是基于虚拟内存的管理技术，但有不同的目的和方法。

Buddy系统

是一种以页为单位管理和分配内存的方法，它的基本思想是将所有的空闲页框分组为不同的大小，每个大小都是2的幂次方，然后根据需要分配或合并相邻的页框。

Buddy系统的目的是实现虚拟内存的映射，即让进程可以使用比物理内存更大的地址空间。

Buddy系统涉及到以下几个方面：

帧分配算法：决定给每个进程分配多少帧，以及如何选择被淘汰的帧。常见的帧分配算法有平均分配、按进程大小比例分配、按优先级分配等。
帧分配策略：决定是否允许进程抢占其他进程的帧。常见的帧分配策略有全局分配和局部分配。
帧分配类型：决定是否需要为函数创建堆栈帧。常见的帧分配类型有帧函数和叶函数。
帧分配对齐：决定是否需要使帧对齐到特定的边界。常见的帧分配对齐有基本对齐和扩展对齐。

Slab分配器

是一种以字节为单位管理和分配内存的方法，它的基本思想是将从Buddy系统申请的大内存进一步细分成小内存分配。

Slab分配器的目的是提高小对象的分配效率，减少内存碎片，维护常用对象的缓存，提高CPU硬件缓存的利用率。

Slab分配器涉及到以下几个方面：

kmem_cache：是一个描述一种对象类型的高速缓存的结构，每种对象类型的高速缓存由一连串的slab构成，每个slab由一个或多个连续的物理页面组成。
slab：是Slab分配器的最小单位，它可以分为三种状态：slabs_full（完全分配的slab），slabs_partial（部分分配的slab），slabs_empty（空slab或没有对象被分配）。
object：是Slab分配器分配的最小对象，它是一个结构体实例，如i节点、PCB等，它可以被打包到slab中，并使用构造函数和析构函数进行初始化和清理。
slab着色：是一种尝试使不同slab中的对象使用CPU硬件缓存中不同行的方案，它通过将对象放置在slab中的不同起始偏移处，来减少对象之间的缓存冲突。

4.用户级线程与系统级线程

线程的调度与切换时间

用户级线程的切换通常发生在一个应用进程的多个线程之间，无须通过中断进入OS的内核，且切换规则也简单，因此其切换速度特别快。而核心级线程的切换时间相对比较慢。

系统调用

用户级线程调用系统调用时，内核不知道用户级线程的存在，只当作是整个进程行为，使进程等待并调度另一个进程执行，在内核完成系统调用而返回时，进程才能继续执行。而核心级线程则以线程为单位进行调度，当线程调度系统调用时，内核将其作为线程的行为，因此阻塞该线程，可以调度该进程中的其他线程执行。

线程执行时间

如果用户设置了用户级线程，系统调用是以进程为单位进行的，但随着进程中线程数目的增加，每个线程得到的执行时间就少。而如果设置的是核心级线程，则调度以线程为单位，因此可以获得良好的执行时间

关于指令：

用户态智能执行非特权指令。如果用户态的程序试图执行特权指令，会引发异常或错误。用户态的程序需要通过访管指令或者系统调用请求操作系统执行特权指令。

特权指令：只能在内核态执行的指令，它们通常涉及到系统资源的管理和保护，比如输入输出，中断控制，时钟设置等。

非特权指令：在用户态执行的指令，比如算法运算，数据运输，跳转，trap（访管），除法错误异常（非特权指令，在用户态执行，触发中断后会使CPU从用户态切换成内核态）。

明晰：非特权指令不是全程在用户态下发生，也可以在内核态下发生。特权指令只能在内核态发生。

5.系统调度算法

处理机调度

处理机调度是指操作系统根据一定的算法，从就绪队列中选择一个进程，并将处理机分配给它运行，以实现进程的并发执行。处理机调度的目的是提高处理机的利用率，提高系统的吞吐量和响应时间，以及保证系统的公平性和平衡性。

处理机调度可以分为三个层次：高级调度、中级调度和低级调度，分别对应作业调度、内存调度和进程调度。

系统调度算法

是操作系统用来选择下一个要执行的作业或者进程的方法。可分为两类：作业调度和进程调度。

作业调度是指从后备队列中选择一个或多个合适的作业，将它们调入内存，为它们创建进程。是外存和内存之间的调度，发生频率很低，使进程从创建态到就绪态的过程。

作业调度算法：1.先来先服务算法.2.短作业优先算法.3.高响应比优先算法.

进程调度是指从就绪队列中选择一个或多个合适的进程，将它们分配给处理器。是内存到cpu的调度，发生频率很高，使进程从就绪态到运行态的过程。

进程调度算法：1.时间片轮转算法。2.优先级调度算法。3.多级反馈队列算法。

6.进程的特征

结构特征：程序段，数据段，进程控制块PCB
动态性：最基本的特征，进程是动态产生，动态消亡的；进程在其生命周期内，在三种基本状态之间转换（就绪、等待和执行）。
并发性：任何进程都可以通其它进程一起向前推进。
独立性：进程是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调度的基本单位。
异步性：每个进程都以其相对独立的，不可预知的速度向前推进。

7.文章链接

[操作系统

进程调度/切换时机、内核临界区与普通临界区_进程访问内核程序的临界区-CSDN博客](https://katya.blog.csdn.net/article/details/127567073?spm=1001.2101.3001.6650.1&utm_medium=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~Rate-1-127567073-blog-126968683.235^v39^pc_relevant_anti_vip_base&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~Rate-1-127567073-blog-126968683.235^v39^pc_relevant_anti_vip_base&utm_relevant_index=2&ydreferer=aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dpbGxfQ2hlL2FydGljbGUvZGV0YWlscy8xMjY5Njg2ODM%3D)

8.基础概念

调度：操作系统根据一定的算法，从就绪队列中选择一个进程，并将处理机分配给它运行，以实现进程的并发执行。
同步：多个进程之间需要协调一致地执行，以保证数据的正确性和一致性。
互斥：多个进程在访问某一共享资源时，需要保证在同一时刻只能有一个进程对其进行操作，以避免数据的破坏和冲突。
抖动：由于内存不足，导致操作系统频繁地进行页面置换，使得进程在运行和等待之间不断切换，从而降低了系统的性能。

抖动的原因是进程的工作集大小超过了可用的物理内存，使得缺页中断率过高。抖动的解决方法是增加物理内存、减少进程数、调整页面置换算法等。
死锁：指的是一组进程中的每个进程都在等待一个事件，而这个事件只能由该组中的另一个进程触发，从而导致所有进程都无法继续执行的状态。
临界资源：一次仅允许一个进程使用的共享资源，例如打印机、文件、内存等。临界资源的访问需要保证互斥和同步，以避免数据的破坏和冲突。
临界区：每个进程中访问临界资源的那段程序，例如读写文件、分配内存等。
重定位：把进程地址空间中使用的逻辑地址变成内存中物理地址的过程。
加载：通过某种加法运算来将逻辑地址转换为物理地址的过程。

9.UNIX创建并执行新程序

fork()系统调用：fork()系统调用是 UNIX 系统中创建新进程的一种方法，它会复制当前进程的所有状态和资源，生成一个与父进程完全相同的子进程。子进程的唯一区别是它的进程号不同，以及 fork() 的返回值不同。
exec()系统调用：exec()系统调用是 UNIX 系统中执行新程序的一种方法，它会用新程序的代码和数据替换当前进程的代码和数据，从而改变当前进程的执行内容。exec() 系统调用有多种变体，如 execl(), execv(), execle(), execve() 等，它们的区别主要在于参数的传递方式和环境变量的设置方式。
fork()和exec()的组合：在 UNIX 系统中，通常使用 fork() 和 exec() 的组合来创建并执行新的程序。首先，父进程调用 fork() 产生一个与自己一模一样的子进程，然后，子进程调用 exec() 执行新的程序，从而拥有自己独立的新代码段。父进程可以继续执行原来的程序，或者等待子进程的结束。
fork()和exec()的返回值：

fork() 系统调用的返回值有三种情况：
- 如果 fork() 成功，那么在父进程中，返回值是子进程的进程号；在子进程中，返回值是 0。
- 如果 fork() 失败，那么在父进程中，返回值是 -1，同时设置 errno 变量表示错误原因；在子进程中，不会有返回值，因为子进程没有被创建。
- 如果 fork() 被信号中断，那么在父进程中，返回值是 -1，同时设置 errno 变量为 EINTR；在子进程中，不会有返回值，因为子进程没有被创建。 exec() 系统调用的返回值只有一种情况：
- 如果 exec() 成功，那么在执行 exec() 的进程中，不会有返回值，因为原来的进程已经被新程序替换，不会再执行后续的代码。
- 如果 exec() 失败，那么在执行 exec() 的进程中，返回值是 -1，同时设置 errno 变量表示错误原因，原来的进程继续执行后续的代码。

10.多级页表

逻辑地址：page

物理地址：page frame

注意：多级页表的出现主要并不是为了查找地址方便，而是减少页表所占用的过大空间。

11.倒排页表

倒排页表是一种存储虚拟页号和物理页框的映射关系的数据结构，它与常规页表相反，每个表项对应一个物理页框，而不是一个虚拟页号。

倒排页表的优点是减少了页表占用的内存空间，因为物理内存的大小一般远小于虚拟内存的大小。

倒排页表的缺点是增加了地址转换的时间和复杂度，因为需要使用散列函数和链表来查找匹配的表项。倒排页表还增加了进程间共享内存的难度，因为需要在表项中增加进程标识和链接指针。

tangthinker.work 虚拟内存

12.分区管理的交换技术和段式管理的请求式分段技术

13.请求式分段和覆盖技术

14.页面集置换算法中工作集置换算法的工作原理

主要参考来源：

1.天津大学邱铁操作系统原理ppt

2.操作系统复习文档