地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。 1. 最佳置换算法(OPT)最佳置换算法(OPT, Optimal):每次选择淘汰的页面将是以后永不使用,或者在最长时间内不再被访问的页面,这样可以保证最低的缺页率。 最佳置换算法可以保证最低的缺页率,但实际上,只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此,最佳置换算法是无法实现的。 2. FIFO先进先出置换算法(FIFO):每次选择淘汰的页面是最早进入内存的页面 实现方法:把调入内存的页面根据调入的先后顺序排成一个队列,需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。 $系统为某进程分配了四个内存块，考虑到以下页面号引用串3, 2, 1, 0, 3, 2, 4 ,3, 2, 1, 0, 4 Belady 异常一一当为进程分配的物理块数增大时,缺页 ...

地址变换机构用于实现逻辑地址到物理地址转换的一组硬件机构 1. 基本地址变换机构基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的始址和页表长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。 设页面大小为 L，逻辑地址 A 到物理地址 E 的变换过程如下: 根据逻辑地址计算出页号、页内偏移量 判断页号是否越界：页表长度就是页表中页表项的个数，有多少个页表项就有多少个页面。如果页号P >= 页表长度 M，则抛出越界中断。否则，进入 (3) 查询页表，找到页号对应的页表项，确定页面存放的内存块号: 根据页号 P 和页表起始地址F得到该页号对应的页表项在内存块中的地址=页号P * 页表项大小 + 页表起始地址 F。通过页表项在内存块中的地址，找到这个页表项之后，便可以得到页表项中的内存块号，然后进入(4) 用内存块号和页内偏移量得到物理地址: b号内存块号（即 P 号页面）在内存中的起始地址=b*每个内存块的大小。然后得到物 ...

页表必须连续存放,因此当页表很大时,需要占用很多个连续的页框 将长长的页表进行分组,使每个内存块刚好可以放入一个分组 比如页面大小 4KB ,每个页表项 4B ,每个页面可存放 1K 个页表项,因此每 1K 个连续的页表项为一组,每组刚好占一个内存块,再将各组离散地放到各个内存块中 另外,要为离散分配的页表再建立一张页表,称为页目录表,或称外层页表,或称顶层页表 1. 两级页表原理单级页表的逻辑地址结构: 32 位逻辑地址空间，页表项大小为 4B，页面大小为 4KB，则页内地址占 12 位 31 $\cdots\cdots$ 12 11 $\cdots\cdots$ 0 页号 页内偏移量 二级页表的逻辑地址结构: 31 $ \cdots\cdots $ 22 21 $\cdots\cdots$ 12 11 $\cdots\cdots$ 0 一级页号 二级页号 页内偏移量 2.地址变换例: 将逻辑地址(0000000000,0000006004,111111121112)转换为物理地址(用十进制表示) 按照地址结构将逻辑地址拆分成三部分 ...

磁盘的结构一般由磁头(磁盘最昂贵的部分),盘面，磁道，扇区组成。一个盘有正反两面，磁道与磁道之间隔有一定距离。一个硬盘有多个磁盘，磁盘之间有两个磁头。 1. 磁盘结构传统的硬盘盘结构有一个或多个盘片，用于存储数据。中间有一个主轴，所有的盘片都绕着这个主轴转动。一个组合臂上面有多个磁头臂，每个磁头臂上面都有一个磁头，负责读写数据。 1.1. 盘面磁盘一般有一个或多个盘片。每个盘片可以有两面，即第一个盘片的正面为0面，反面为 1 面；第二个盘片的正面为 2 面…依次类推。磁头的编号也和盘面的编号是一样的，因此有多少个盘面就有多少个磁头。 盘面正视图如下图，磁头的传动臂只能在盘片的内外磁道之间移动。因此不管开机还是关机，磁头总是在盘片上面。关机时，磁头停在盘片上面，抖动容易划伤盘面造成数据损失，为了避免这样的情况，所以磁头都是停留在起停区的，起停区是没有数据的。 1.2. 磁道每个盘片的盘面被划分成多个狭窄的同心圆环，数据就存储在这样的同心圆环上面，我们将这样的圆环称为**磁道 (Track)**。每个盘面可以划分多个磁道，最外圈的磁道是0号磁道，向圆心增长依次为1磁道、2磁道…磁盘 ...

请求分页存储管理与基本分页存储管理的主要区别: 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。 为实现请求分页功能操作系统需要实现: 操作系统要提供请求调页功能，将缺失页面从外存调入内存 操作系统要提供页面置换的功能，将暂时用不到的页面换出外存 1. 页表机制与基本分页管理相比，请求分页管理中，为了实现“请求调页”，操作系统需要知道每个页面是否已经调入内存：如果还没调入，那么也需要知道该页面在外存中存放的位置。 当内存空间不够时，要实现“页面置换”，操作系统需要通过某些指标来决定到底换出哪个页面；有的页面没有被修改过，就不用再浪费时间写回外存。有的页面修改过，就需要将外存中的旧数据覆盖，因此，操作系统也需要记录各个页面是否被修改的信息。 请求分页存储管理的页表: 2. 缺页中断机构在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回 ...

动态分区分配是一种连续分配方法，为各进程分配的空间必须是连续分配方式，为各进程分配的空间必须是连续的一整片区域 1. 首次适应算法每次都从低地址开始査找,找到第一个能满足大小的空闲分区。 空闲分区以地址递増的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。 2. 最佳适应算法由于动态分区分配是一种连续分配方式,为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间,可以尽可能多地留下大片的空闲区,即,优先使用更小的空闲区。 空闲分区按容量递增次序链接。每次分配内存时顺序査找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区 3. 最坏适应算法为了解决最佳适应算法的问题一一即留下太多难以利用的小碎片,可以在每次分配时优先使用最大的连续空闲区,这样分配后剩余的空闲区就不会太小,更方便使用。 空闲分区按容量递减次序链接。每次分配内存时顺序査找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。 每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方 ...

传统存储管理暂时用不到的数据也会长期占用内存，导致内存利用率不高 传统存储管理特点: 一次性 作业必须一次性全部装入内存后才能开始运行，这会造成两个问题: 作业很大时，不能全部装入内存，导致大作业无法运行 当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。 驻留性 一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源。 可用虚拟存储技术解决问题 1. 局部性原理1.1. 时间局部性如果执行了程序中的某条指令,那么不久后这条指令很有可能再次执行;如果某个数据被访问过,不久之后该数据很可能再次被访问。(因为程序中存在大量的循环) 1.2. 空间局部性一旦程序访问了某个存储单元,在不久之后,其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的,并且程序的指令也是顺序地在内存中存放的) 高速缓冲技术的思想: 将近期会频繁访问到的数据放到更高速的存储器中，暂时用不到的数据 ...

为了防止文件共享可能会导致文件被破坏或未经核准的用户修改文件，文件系统必须控制用户对文件的存取，即解决对文件的读、写、执行的许可问题。为此，必须在文件系统中建立相应的文件保护机制。 文件保护通过口令保护、加密保护和访问控制等方式实现。其中，口令保护和加密保护是为了防止用户文件被他人存取或窃取，而访问控制则用于控制用户对文件的访问方式。 1. 口令保护为文件设置一个 “口令” (如: abc112233), 用户请求访问该文件时必须提供 “口令” 口令一般存放在文件对应的 FCB 或索引结点中。用户访问文件前需要先输入 “口令”,操作系统会将用户提供的口令与 FCB 中存储的口令进行对比,如果正确,则允许该用户访问文件 优点: 保存口令的空间开销不多,验证口令的时间开销也很小 缺点: 正确的 “口令” 存放在系统内部,不够安全 2. 加密保护使用某个 密码 对文件进行加密,在访问文件时需要提供正确的 密码 才能对文件进行正确的解密 举例简单的加密算法: 异或加密，密码 “01001” 文件解密 优点: 保密性强,不需要在系统中存储“密码” 缺点: 编码/译 ...

1. 分页&分段 优点 缺点 分页管理 内存空间利用率高，不会产生外部碎片，只会有少量的页内碎片 不方便按照逻辑模块实现信息的共享和保护 分段管理 很方便按照逻辑模块实现信息的共享和保护 如果段长过大，为其分配很大的连续空间会很不方便。另外，段式管理会产生外部碎片 分段管理中产生的外部碎片也可以用“紧凑”来解决，只是需要付出较大的时间代价 2. 段页式管理基于分段管理和分页管理的优缺点，提出了分页和分段管理的结合，产生了段页式管理 将进程按逻辑模块分段,再将各段分页(如每个页面4KB)再将内存空间分为大小相同的内存块/页框/页帧/物理块进程前将各页面分别装入各内存块中 3. 逻辑地址结构段页式系统的逻辑地址结构由段号、页号、页内地址（页内偏移量）组成。如: 31 $\cdots\cdots$ 16 15 $\cdots\cdots$ 12 11 $\cdots\cdots$ 0 段号 页号 页内偏移量 段号的位数决定了每个进程最多可以分几个段 页号位数决定了每个段最大有多少页 页内偏移量决定了页面大小、内存块大小是多少 “ ...

文件管理，由于系统的内存有限并且不能长期保存，故平时总是把它们以文件的形式存放在外存中，需要时再将它们调入内存。如何高效的对文件进行管理是操作系统实现的目标。 1. 什么是内存内存是用于存放数据的硬件。程序执行前需要先放到内存中才能被 CPU 处理。 思考: 在多道程序环境下,系统中会有多个程序并发执行,也就是说会有多个程序的数据需要同时放到内存中。那么,如何区分各个程序的数据是放在什么地方的呢? [给内存的存储单元编地址] 2. 进程运行的基本原理2.1. 指令的工作原理写的代码要翻译成 CPU 能识别的指令。这些指令会告诉 CPU 应该去内存的哪个地址存/取数据,这个数据应该做什么样的处理。 上面指令中直接给出了变量 x 的实际存放地址(物理地址)。但实际在生成机器指令的时候并不知道该进程的数据会被放到什么位置。所以编译生成的指令中一般是使用逻辑地址(相对地址） 2.2. 逻辑地址&物理地址宿舍四个人一起出去旅行，四个人的学号尾号分别是0、1、2、3。住酒店时酒店给你们安排了 4 个房号相连的房间。四个人按学号递增次序入住房间。比如 0、1、2、3 号同学 ...