OS2：知识点详解 - 江舟的博客

[TOC]

1.用户态和内核态，用户线程和内核线程；（笔记）

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

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

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

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

用户级线程与系统级线程

线程的调度与切换时间

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

系统调用

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

线程执行时间

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

2.单道批处理系统，多道批处理系统，分时系统，实时系统；（笔记）

3.fork()和exec()，另外还有waitpid()，execve()；（操作系统导论）

4.硬链接和符号链接，文件系统。(深入了解，不止于表面的复制和快捷方式)

5.进程间通信的三种方式的表现是什么？（通信的大概方式）

6.进程的三种调度指什么？

长期调度：选择一个进程进入内存的就绪队列

短期调度：从就绪队列中选择一个进程为其分配cpu。

中期调度：将进程从cpu或者内存中移除，换到外存交换区，降低多道程序设计的难度。

7.进程竞争内存时内存资源紧张的方案有哪些？

1).swapping。换出一部分内存到外存。

2).virtual memory。每个进程只装入一部分程序和数据。

8.讲述对于父进程和子进程的理解。

fork()：fork()复制当前进程的所有状态和资源，生成一个与父进程完全相同的子进程。

注：在父进程中，返回值是创建的子进程的PID，在子进程的返回值是0；返回值为负则创建失败。

wait()：父进程等待子进程终止再继续运行。成功时返回子进程的pid，没有子进程返回0；

exec()：子进程调用 exec() 执行新的程序，从而拥有自己独立的新代码段。

注：exec() 成功，不会有返回值，因为原来的进程已经被新程序替换，不执行后续代码。exec() 失败，返回值是 -1，原进程继续执行后续代码。

9.时钟页面置换算法，LRU近似的老化aging算法，工作集页面置换算法（工作集指最近k次访问近似最近多久时间内访问的页面），WSclock（工作集时钟，R和生存时间）

最好的页面置换算法是老化算法和工作集时钟算法，它们分别基于LRU和工作集，有良好的页面调度性能，可以有效实现。

10.系统调度

处理机调度

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

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

系统调度算法

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

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

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

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

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

11.经典同步问题（PV操作的基本含义,经典问题）

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);
    }
}

读者写者问题，生产者消费者问题，哲学家就餐问题等。

12.临界互斥的基本方法的理解。

（空闲让进，忙则等待，有限等待，让权等待）

I：软件上

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

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

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

(原子操作)

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

II：硬件上

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

2）硬件指令法。不满足”让权等待“，可能发生”饥饿“。

13.死锁（死锁预防，死锁避免，死锁检测，死锁解除，实际应对死锁的方法）

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

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

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

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

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

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

14.非连续分配的方式（基本分页存储管理，基本分段存储管理，段页式管理，TLB）

15.分段，分页，段页式优缺点

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

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

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

段页式：

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

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

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

以段为单位调入调出，以页为单位非连续存储

16.概念

地址映射和地址变换

地址映射：为保证程序正常运行，必须将虚拟空间中已链接和划分好的内容装入内存，并将虚拟地址映射为内存地址。

地址变换：要建立虚拟地址与内存地址的关系。

重定位：把进程地址空间中使用的逻辑地址变成内存中物理地址的过程。

静态地址重定位和动态地址重定位

静态地址重定位：在虚拟空间执行之前由装配程序完成地址映射工作。

动态地址重定位：在程序执行过程中，在CPU访问内存之前，将要访问的程序或数据地址转换成内存地址。

静态链接和动态链接

静态链接：为了程序正确执行，必须由连接装配程序把它们连接成一个可运行的目标程序。

问题：花费时间，浪费空间

动态链接：在程序开始运行时，只将主程序段装配好并调入内存，其它各段的装配是在主程序段的运行过程中逐步完成。每当需要调用一个新段时，再将这个新段装配好，并与主程序段链接

加载：通过某种加法运算来将逻辑地址转换为物理地址的过程。
临界资源：一次仅允许一个进程使用的共享资源，例如打印机、文件、内存等。临界资源的访问需要保证互斥和同步，以避免数据的破坏和冲突。
临界区：每个进程中访问临界资源的那段程序，例如读写文件、分配内存等。
同步：多个进程之间需要协调一致地执行，以保证数据的正确性和一致性。
互斥：多个进程在访问某一共享资源时，需要保证在同一时刻只能有一个进程对其进行操作，以避免数据的破坏和冲突。
调度：操作系统根据一定的算法，从就绪队列中选择一个进程，并将处理机分配给它运行，以实现进程的并发执行。
抖动：由于内存不足，导致操作系统频繁地进行页面置换，使得进程在运行和等待之间不断切换，从而降低了系统的性能。

抖动的原因是进程的工作集大小超过了可用的物理内存，使得缺页中断率过高。抖动的解决方法是增加物理内存、减少进程数、调整页面置换算法等。
死锁：指的是一组进程中的每个进程都在等待一个事件，而这个事件只能由该组中的另一个进程触发，从而导致所有进程都无法继续执行的状态。

17.进程特征

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

[操作系统

进程调度/切换时机、内核临界区与普通临界区_进程访问内核程序的临界区-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)

18.倒排页表

一般页表是通过虚拟地址映射寻找物理地址，虚拟地址的空间比物理地址要大，因此消耗的空间资源更多。

倒排页表则是通过物理地址映射虚拟地址，节约了空间资源，但是通过虚拟地址查找物理地址就变得困难，极其浪费时间。

有两种解决方案，一种是TLB存储最近常用的页表项，另一种是利用散列表存储虚拟地址。

19.虚拟内存的实现方式（按需调页，按需调段）

Demand Paging：只在页被需要时，才调入内存。

无效时——>发生中断（转24.页面故障处理）；不在内存中——>调入内存。

20.页缓冲算法

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

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

页缓冲算法的目的是：

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

21.帧分配算法

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

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

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

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

22.工作集模型原理

23.虚拟内存—交换技术（覆盖和交换）

操作系统原理：覆盖技术、交换技术、虚拟内存概要-CSDN博客

24.页面故障处理

当访问无效页时，会陷入OS

1.检查进程内部页表

Invalid reference —> abort 非法访问-〉终止

Just not in memory 不在内存中

2.找到一个空闲帧

3.换入页到该帧中

4.修改表

5.Set validation bit = v

6.重新开始因陷阱而中断的指令

25.页面置换算法（见9）

26.内核进行内存管理的方法（Buddy系统，Slab分配）

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

Buddy系统（产生碎片）

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

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

Slab分配器（不产生碎片）

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

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

文件目录 ：文件控制块(FCB)的有序集合，用于文件描述和文件控制，实现按名存取和文件信息共享与保护。

目录文件：为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，这个文件就叫目录文件

28.基本文件操作（read,write,等）

29.inode介绍

30.文件存储空间管理（空闲表法，空闲链表法，空闲盘区链，位示图法）

位示图法：n个块的磁盘需要n位位图，n/8字节的空间。

空闲文件目录是一张连续表，它要占用较大的辅存空间。

空闲块链，每次释放物理块时要完成拉链工作，虽然只是在一块中写一个字节，但其工作量与写一块相差无几。

位示图，分配时需要顺序扫描空闲区（标志为“0”），速度慢，而且物理块号并未在图中直接反映出来，需要进一步计算。

31.文件保护（口令保护，加密保护，访问控制）

32.磁盘调度算法（FCFS，SSTF，SCAN，LOOK调度算法，C-SCAN循环扫描算法，C-LOOK算法）

SCAN：磁盘的一端到另一端，到达后转向。(顶端，不循环)

C-SCAN：当磁头移到另一端时，会马上返回到磁盘开始，返回时不处理请求

LOOK：是改进的SCAN算法，处理过程与SCAN相似，只是每次都不运动到顶端，在最大磁道号和最小磁道号之间移动。

C-LOOK：n磁头只移动到一个方向上最远的请求为止，接着马上返回，而不是移动到磁盘的尽头

33.RAID廉价磁盘冗余阵列

定义：多个独立的物理硬盘按照不同的方式组合起来，形成一个虚拟的硬盘

存取方式：

并行存取方式：适用于大型的、以长时间顺序访问数据为特征的应用
独立存取方式：适用于数据存取频繁，每笔存取数据量较小的应用

镜像冗余的概念：磁盘镜像是一个简单的设备虚拟化技术，每个I/O操作都会在两个磁盘上执行，两个磁盘看起来就像一个磁盘一样。镜像冗余可以提高磁盘的读性能。

校验冗余的概念：根据冗余算法计算阵列中成员磁盘上数据的校验信息，将校验信息保存在其他的磁盘资源上。

热换：是指在不影响系统正常运转的情况下，用正常的磁盘物理替换RAID阵列中的失效磁盘。

RAID0：均匀分布在各个磁盘。

RAID1：镜像冗余，有2N个磁盘，100%冗余，空间利用率50%

RAID2：校验冗余，并行存取。（了解）

RAID3：校验冗余，分块（分成小块，同区域内块数多），读写性能好，并行存取，磁盘损坏时对整体吞吐量小。

RAID4：XOR校验数据，分块（分成大块），独立存取。

RAID5：独立存取，军训分散在阵列的磁盘，N+1个磁盘。（选学）

RAID6：奇偶校验，N+2个磁盘。（选学）

RAID10：先镜像再条带化=1+0（选学）

34.IO软件层次结构

IO软件层次结构:

用户级IO软件（与用户的调用接口）

设备独立性软件（执行所有设备公共的IO功能）

设备驱动（IO设备需要特定的代码控制）

中断处理

硬件。

设备独立性软件：功能

设备驱动的统一接口；缓冲；错误处理；独占设备的分配和释放；提供与设备无关的逻辑块。

35.IO控制方式（程序直接控制方式，中断控制方式，DMA控制方式，通道控制方式）

程序直接控制方式：用户进程直接控制内存或CPU和外围设备之间的信息传送。

但是CPU和外设速度差异大，不能实现并行，不能对外部异常做出响应

中断控制方式：（在以上前两者做出改变，减少CPU等待时间和提高并行工作程度）仅适合于中慢速设备。在高速外围设备中，中断可能由于来不及响应丢失数据；在希望成组数据交换时，多次中断速度也降低）。

对于大批量成组数据交换，可以利用DMA和通道方式。

DMA控制方式：在外围设备和内存中开辟直接的数据交换通路。

优势：1.相比中断每次缓冲区满让CPU处理，DMA会在所有数据块结束一次险处理，减少CPU处理次数。

2.中断中的数据传送每次有CPU控制处理，DMA自行处理，排除并行使CPU来不及处理或速度差距时发生的数据丢失。

但是DMA对设备的管理和控制更为复杂，消耗更多，DMA过多容易引起内存地址冲突，并且不经济。

通道控制方式：通道相当于一个功能单纯的处理机，只处理IO操作。有自己的运控部件和指令系统，没有专门的内存，通过“周期窃取”和主机共享内存。

以内存为中心，实现设备和内存直接交换数据的控制方式。

通道比DMA的自由度更高。DMA中每台设备至少需要一个DMA控制器，通道则是一个通道控制多台设备与内存进行数据交换，使得通道方式进一步减轻了CPU的工作负担和增加了计算机系统的并行工作程度。

36.缓冲技术

1）无缓冲。（缓冲区在用户空间从而导致页面池收缩，页面性能下降）

2）单缓冲。（内核中的缓冲区满时无法处理新字符）

3）双缓冲。（两个缓冲区交替使用）

4）其它：循环缓冲，缓冲池，

注：数据被缓冲太多次时，页面性能会下降。

比如：网络工作可能由于缓冲，进行了过多的复制操作，降低了传输速率。

37.pv操作（联合11）

进程同步与互斥的三种基本问题：

1.利用信号量实现同步：

Semaphore S=0;
P1(){
	x;
    V(S);
}
P2(){
    ...
	P(S);
    y;
    ...
}
//注：只有先执行P1语句中的x才能执行到P2中的y
//P2若是先执行到P(S),S为0，执行P操作会把进程P2堵塞，并放入堵塞队列；P1中的x执行完后，执行V操作，把P2从堵塞队列放回就绪队列，P2得到处理机，继续执行。

2.利用信号量实现进程互斥：

Semaphore S=0;
P1(){
	...
	P(S);
    P1进程的临界区;
    V(S);
    ...
}
P2(){
    ...
	P(S);
    P2进程的临界区;
    V(S);
    ...
}

3.利用信号量实现前驱关系：

思想有点像拓扑排序。在一个有向图中，某某是某某的前驱，为其提供资源，这种资源在该思想中用信号量表示。

经典同步问题

生产者消费者问题：

同步关系12：生产者放了消费者才能取（可取资源）；消费者取了生产者才能放（可放资源）。

生产者：
full=0;empty=1;
while(true){
	生产产品
	P(empty);
	将产品送到缓冲区
	V(full);
}

消费者：
while(true){
	P(full);
	从缓冲区取出产品
	V(empty);
	消费产品
}

读者/写者问题

进程关系分析：读操作可以同时进程，读写互斥，写写互斥。

mutex=1;
Reader：
while (true)  {
	P(mutex);
	read();
    V(mutex);
};

Writer：
while (true)  {
    P(mutex);
    write();
    V(mutex);
};

哲学家进餐问题

附：期末

日常作业考点：

进程管理：

选择：信号量和条件变量；进程的三种状态转换；进程和线程的差异；临界区和临界资源；用户态和内核态；系统调度；死锁。

大题：系统调度算法，银行家算法，pv操作

内存管理：

选择：死锁，抖动，重定位；页面置换算法；空闲区分配；段页式管理；多级页表；缺页；按需调页

大题：分页管理系统，段页式管理，倒排页表

文件管理：

选择：RAID；磁盘；文件和目录；软连接和硬链接。

大题：磁盘调度算法，磁盘访问。