OS

本章主要总结操作系统中的内存管理 随着技术的发展，内存的容量再不断增大，但是也不能把所有用户数据和程序一起装入内存，因此操作系统需要对内存空间进行合理的划分和有效的动态分配，从而提高系统的资源利用率。对内存的合理划分以及有效的动态划分就是内存管理的概念。 程序执行过程 每段程序执行前大致需要经过三个过程：编译 -> 链接 -> 装入 编译：将源代码通过编译器编译为一个个目标模块。 链接：将每个目标模块和所需库函数链接起来，形成一个完整的装入模块。 静态链接（装入前链接），即在装入内存之前把所有的模块和对应的库函数进行链接从而形成一个可执行程序，以后不会再拆开。 装入时动态链接，即在装入内存时，一边装入一边链接。 运行时动态链接，即在执行对应模块代码时，实时链接。 装入：将链接后形成的模块装入内存中。 绝对装入 => 程序相对地址和实际装入的物理地址相同。 可重定位装入 => 程序相对地址加一个重定位地址形成实际的物理地址。 动态运行时装入 => 在执行对应的模块时，才开始执行地址转换，地址转换的偏移量则从重定位寄存器中取出。 内存分配管理方式 连续分配方式：用户程序被分配进一个连续的内存空间 单一连续分配方式: 整个内存中只运行一道用户程序。 固定分区分配 内存被划分为若干个固定大小的区域。当有程序需要装入内存时，从分区说明表上寻找合适的内存区域并分配给它。 动态分区分配 => 不预先对内存进行分区，而是等程序装入内存时动态分区。 首次适应算法 最佳适应算法 最坏适应算法 邻近适应算法（首次适应算法的改进，即下一次分配内存是从上一次分配内存结束位置开始） 区分内部碎片还是外部碎片的关键在于：内存分区是提前分好还是运行时实时分配的。 对于前者，很容易理解每个内存分区就可以称之为“内”，所以就有了内部碎片的说话。 对于后者，由于没有提前分区，所以自然没有“内”的概念，那么所有的内存都是“外”，所以此时产生的碎片也称为外部碎片。 即固定分区会产生内部碎片，动态分区会产生外部碎片。 非连续分配方式 基本分页存储管理方式 => 一维表示即可，即给定一个地址，便可以算出它的页号以及偏移地址（因为页的大小是确定的） 基本分段存储管理方式 => 二维表示，因为每段的大小不同，导致一个地址无法算出其它信息，段号和段内位移地址要显式给出 段页式存储管理方式 => 对代码分段，对内存分页。 分页系统和分段系统的共同之处： 它们都有对应的“表”，分页系统是页表，分段系统是段表。当然对于表来说也有对应的寄存器（页表/段表寄存器） 它们都可以加入**快表（联想存储器 TLB）**来提高地址转移效率。 不同之处： 分页系统的地址可以进行一维表示，而分段系统的地址需要二维表示。 分段系统中的每段是具有一定逻辑意义的代码集合（比如一块函数定义），方便代码共享。 虚拟内存 局部性原理 => 高速缓存技术依赖的原理 时间局部性：程序中的某条指令一旦执行，不久后该指令可能再次执行；某数据被访问，不久后该数据可能再次被访问。产生时间局部性的原因是程序中往往含有大量的循环操作 空间局部性：一旦程序访问了某个存储单元，不久后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在某个区域。 虚拟存储器 根据局部性原理，程序装入时，可以只将程序的部分装入，其余部分留在外存。程序执行过程中，若程序不在内存中，则从外存中调入对应部分的程序代码，然后继续执行程序。另一方面，操作系统也把不再执行的代码重新换出到外存（实际情况是如果代码段没有被修改，则直接丢弃）。这样，系统好像就为用户提供了一个比内存大的多的存储器，称其为虚拟存储。 实现方式 请求分页存储管理 请求分段存储管理 请求段页式存储管理 它们都需要的硬件支持：...

在复试时，很少问及计算题，大多数都是的问题都是和概念直接相关，所以要深刻理解操作系统各个组成部分的概念。 本篇主要归纳操作系统的基本概念以及进程相关概念和算法 操作系统基本概念 首先需要知道操作系统在整个计算机系统中的定位： ​ 计算机系统大致可以分为四个部分（自底向上）：计算机硬件 -> 操作系统 -> 应用程序软件 -> 用户。 从上述结构可以轻易看到，操作系统管理着计算机的各个硬件，具体表现为对资源的合理调度，分配等，同时也为上层应用程序软件提供抽象出来的硬件功能。 综上所述，操作系统可以定义为控制和管理整个计算机的硬件和软件资源，并合理地组织，分配资源、调度工作，进而为用户和其它软件提供方便接口与环境的程序集合。 提炼一下，操作系统就是一系列程序的集合，不过这些程序有着上述管理功能。 特征（四大特征） 并发 => 注意并发和并行的区别。 共享 （两种共享方式，也对应着后续会提到的资源共享形式） 互斥共享 同时访问 虚拟 => 用逻辑的对应物去映射实际的物理设备，让用户在使用时感觉是在真正使用物理设备。 经典例子: 请求分页系统，SPOOLing技术 异步 => 进程以不可预知的速度向前执行（进程的异步性） 异步也是操作系统中需要进程控制的原因之一，因为要保证怎么个异步法，各个进程的最终结果都一样。 其中，**并发和共享是其它特性的基础，**它们两也相互依存。 管理的计算机资源（包括硬件和软件）分类 处理机管理 => 进程的调度与分配 存储器管理 => 内存管理 文件管理 => 文件的存储形式：逻辑存储和物理存储 I/O设备管理 => 外存相关概念以及相关管理 运行环境 CPU的状态分为两类：用户态（目态）和核心态（管态） 用户的程序运行在目态，而操作系统的内核运行在管态。有一些特殊的特权指令，只有在CPU处于管态时才能调用。 特权指令 -> 操作系统不允许用户直接调用的指令，比如I/O指令，置中断指令等等。 如果说用户程序必须使用特权指令的功能，则需要通过中断或异常操作来达到目的，即发生中断或异常时，CPU状态会从用户态转向核心态。 中断和异常 操作系统的发展过程大体上就是一个想法设法不断提高资源利用率的过程，而提高资源利用率就需要在程序并未使用某种资源时，把它对那种资源释放，而这一行为就需要通过中断来实现。 中断（外中断）：CPU执行指令以外的事情发生而引起的中断，即外中断不是由指令本身引起的（比如访问数组越界等），而是外界因素导致的（比如I/O中断，时间片中断），它和当前处理机正在运行的程序有关。 异常（内中断，陷入trap）：CPU执行指令时发生的错误异常事件。比如地址越界，请求分页系统的缺页以及专门的陷入指令（这个也是上述用户能够主动进入核心态的办法，也称为系统调用）。 ​ 系统调用的本质是用户把CPU的使用权交给了操作系统内核的程序，然后让内核程序去执行对应的特权指令，等执行完毕后，再把使用权返回。即关键指令的调用实质还是内核调用而不是用户直接调用。 进程管理 基本概念 在多道程序运行的系统中，由于程序直接“暴露在内存里”，所以导致程序没有封闭性，它们能够彼此看见对方内部的结构，甚至调用，这显然是不行的。于是为了方便描述程序和控制程序的并发，体现操作系统的并发性和共享性，所以引入了进程的概念。 进程（动态的）：是程序的一次执行过程（进程实体的运行过程），是CPU资源分配和调度的基本单位（引入线程之前） PCB（Process Control Block） 程序段 相关数据段 状态 创建态 就绪态 运行态 终止态 阻塞态 它们各自的定义这里不再描述。 需要说明的是，当进程从运行态变换到阻塞态时，是一个主动的行为（即自己需要去请求某个外设资源或等待某一事件发生而引起的阻塞），这是一种特殊的，由运行的用户态程序去调用操作系统内核过程的形式。 而从阻塞态转移到就绪态，这是一个被动过程，因为它需要外界信号进行触发。例如请求的外设已经完成了对应的任务，或是请求的某个资源已经空闲出来等。 进程通信 共享存储空间通信 -> 多个进程共享内存中的某块空间，当需要通信时，在内存中进行读写即可。 消息传递 -> 调用操作系统提供的消息传递方法进行进程通信，即通过发送消息和接受消息两个原语进行通信。 直接通信，即发送进程直接把消息发送给接收消息进程。 间接通信，即发送进程把消息发送给某个中间实体，使其成为一个信箱，而接受进程直接从实体中取消息即可，反之亦然。 管道通信 -> 由pipe文件来连接发消息进程和接受消息进程从而达到通信的目的。（消息查看2022王道考研操作系统P35） 线程 由于进程的切换会有较大的时空开销，于是考虑引入线程，从而提高系统的并发性能（因为线程切换所引起的时空开销要远远小于进程）。...