学习笔记

操作系统 可执行文件类型： Linux下面使用的ELF文件和Windows操作系统使用的PE文件都是从Unix系统的COFF文件格式演化来的。 操作系统作用： 1.资源的管理者：跟踪记录资源使用状况（数据结构）、确定资源分配策略（算法）、实施资源分配的分配和回收、提高资源利用率、保护资源使用、协调资源请求冲突。 2.向用户提供各种服务 3.对硬件机器的拓展：对硬件抽象，提高可移植性，为用户提供一个拓展的虚拟机器。 操作系统内核特征： 1.并发 2.共享 3.虚拟 4.异步 BIOS系统调用：提供基本的I/O功能，只能在实模式下访问。（系统的启动） 4题、40题 中断：硬件设备的请求。异步（感觉不到）。中断可以被打断 异常：非法指令或其他原因导致当前指令执行失败。同步。异常可以嵌套、可以打断 系统调用：应用程序主动向操作系统发出服务请求。同步或异步。间接访问系统调用

系统调用:堆栈切换保护内核安全性，特权级转换。 函数调用：常规调用没有堆栈切换。 17题 内存 32位总线，32个bit=四个字节，每个字节=8bit CPU：两级缓存 操作系统访问内存，缺页将访问外存（虚拟内存）速度逐渐变慢

操作系统内存管理方式： 1.重定位 2.分段 3.分页（基本单位） 4.虚拟存储 15题、25题 地址空间定义 物理地址：硬件支持的地址空间 逻辑地址：CPU运行的进程看到的地址

61题21** 连续内存分配 缺点：1.分配的物理内存必须连续2.存在外碎片和内碎片3.内存分配的动态修改困难4.内存利用率低 内存碎片： 内部碎片（分配单元内部未被使用，取决于分配单元大小是否取整） 外部碎片（分配单元之间未被利用） 11题 动态分区分配：程序加载时分配指定大小可变的分区（产生外部碎片） 动态分区分配策略：最先匹配（找第一个比想要的大的），最佳匹配（找比想要的大且大的最小的一个），最差匹配（找比想要的大且最大的一个）

62题 碎片整理（通过调整进程占用的分区位置来减少或避免分区碎片）： 1.碎片紧凑：合并外部碎片（条件：所有应用程序可动态重定位） 2.分区对换：抢占并回收正处于等待状态进程的分区，放置在外存中，以增加可用内存。

** 非连续内存分配 困难：1.虚拟地址和物理地址转换困难2.选择分配内存大小困难 1.段式存储管理： 2.页式存储管理： 3.段页式存储管理：每个段加一级页表 段页式：实现内存共享，通过指向相同的页表基址，实现进程间的段共享 页帧：（frame）把物理地址空间划分为大小相同的基本分配单位 大小：2的n次方，如512，4k=4096，8192 页面：（page）把逻辑地址空间划分为大小相同的基本分配单位 帧和页大小必须一致 页面到页帧：逻辑地址到物理地址； 页表 问题：1.访问一个内存单元需要两次内存访问2.页表可能很大 处理方法： 1.缓存：快表 2.间接访问：多级页表 9题、32题、33题 快表：缓存近期访问的页表项，在CPU中快速访问 多级页表：通过间接引用将页号分成k级，访问次数k+1次 反置页表：不让页表与逻辑地址大小相对应（多级页表），让页表与物理地址的大小相对应。

实际存储器访问速度 寄存器--高速缓存--内存--磁盘--磁带

10题、、20题、27题、28题、29题、55题 虚拟存储 覆盖：应用程序手动将（互不影响的附庸在一起）需要的指令和数据保存在内存中。 方法：依照程序逻辑结构，将程序划分为功能相互独立的模块，将不会同时执行的模块共享同一块内存区域。 不足：需要程序员划分模块并确定模块间的覆盖关系，增加编程复杂度。 原本读入一部分，之后再读入一部分，增加执行时间。 交换：操作系统自动把暂不执行的程序保存到外存。 方法：可以将暂时不能运行的程序放入外存（一个程序都不够用时） 可以换入换出的基本单位：整个进程的地址空间 不足：交换时机：当内存不足或有不足的可能时； 交换区大小：占用外存的储存空间 程序换入的重定位：（换入时可以换回原处）采用动态地址映射 动态地址映射：在程序运行期间，随着每条指令和数据的访问自动地，连续的进行映射。

虚拟存储：以页为单位自动装入更多更大程序。 37题 局部性原理：时间局部性、空间局部性、分支局部性（可以实现虚拟存储） 时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短的时期。 空间局部性：当前指令和邻近的几条指令，当前访问的数据和接下来要访问的数据集中在一个较小的区域内。 分支局部性：一条跳转指令的两次执行，很可能跳转到相同的内存位置（循环）。

利用了虚拟存储，小心缺页中断，好好编写程序 缺页或缺段：指令执行时指令或数据不在内存中。 虚拟存储基本原理： 1.装载程序时：只将当前指令执行需要的部分页或段装入内存。 2.缺页或缺段时：处理器（CPU)通知操作系统将相应的页或段调入内存中。 3.处理缺页或缺段异常：操作系统将内存中暂时不用的页或者段保存到外存。 实现方式：虚拟页式存储、虚拟段式存储（根据物理内存分配方式） 基本特征：不连续性（物理地址分配非连续性，虚拟地址空间使用非连续）、大用户空间（提供用户的虚拟内存大于实际物理内存）、部分交换（只对部分虚拟地址空间进行调入和调出）

虚拟页式存储：在页式存储管理基础上，增加请求调页和页面置换的算法 页表项结构：驻留位（该页是否在内存中）、修改位（内存中该位是否被修改过）、访问位（页面是否被访问过）、保护位（该页允许访问方式）

缺页异常（缺页中断） 处理流程：在外存中查找到页面q后 1.在内存中有空闲页面，直接分配一物理页帧，转到5 2.若无空闲页面，依据页面置换算法选择出被替换的物理页帧f，对应的逻辑页面p； 3.若p被修改过，则把它写回外存，若没有修改过则直接扔掉 4.修改p的页表项中的驻留位为0，说明已经不在内存中 5.将查找到的页面q装入物理页帧f 6.将需要访问的页q的驻留位修改为1，物理页帧号为f，表示已经在内存中 7.重新执行产生了缺页异常的指令

46题 虚拟存储中的外存管理： 做一个分区叫兑换区；交换空间：文件中采用特殊的格式来存储未被映射的页面 外存选择：代码段：可执行二进制文件。共享库：相应的目标文件存储。 其他段放入交换空间中。 虚拟页式存储性能：

57题 工作集置换算法：常驻集、工作集（每次访问完成）

缺页率置换算法：缺页中断时完成 缺页率：缺页次数/内存访问次数 或缺页平均时间间隔的倒数 物理页面在动态调整

47题 抖动和负载控制

1题、2题、3题、12题、13题 进程和线程 进程：一个具有一定独立功能的程序在一个数据集合上的一次动态执行的过程。 进程的组成：正在运行的一个程序的所有状态的信息。代码、数据、状态寄存器... 进程的特点：动态性、并发性、独立性、制约性 进程：操作系统处于执行状态程序的抽象 程序=文件（静态的可执行文件） 进程=程序+执行状态 同一个程序多次执行过程对应为不同进程。 进程是动态的，程序时静态的。 进程控制块（PCB）：操作系统管理和控制进程运行所需的信息集合。 进程状态：创建、执行、等待（请求并等待系统服务未完成、启动某种操作未完成、需要数据没到达）、抢占（高优先级）、唤醒、结束。 进程的切换： 三状态进程模型：就绪、运行、等待 挂起进程模型：处于挂起状态的进程映像在磁盘上。等待挂起、就绪挂起

30题 线程：进程内部进一步提高并发性。 线程是进程的一部分，描述指令流执行状态。它是进程中指令执行流的最小单位，是CPU调度的基本单位。 线程=进程-共享资源 缺点：一个线程崩溃，会导致其他所属进程的所有线程崩溃。

线程与进程的比较 进程是资源分配单位，线程是CPU调度单位。 进程拥有一个完整的资源平台，而线程只独享指令执行的必要资源。 线程和进程一样有三状态（就绪、运行、等待）及状态间的转换关系。 线程能减少并发执行的时间和空间开销。 时间：线程（进程中）的创建、终止、切换时间比进程短。 空间：同一进程各线程间的共享内存和文件资源，可不通过内核直接通信。

线程的实现： 用户线程：在用户空间实现。 内核线程：在内核中实现。 轻量级进程：轻权进程：内核支持的用户线程。

进程控制 进程切换（上下文切换）要求：切换前保存进程上下文，切换后恢复进程上下文，快速切换。 保存信息：寄存器、CPU状态、内存地址空间（一般不用保存） 进程创建 进程加载 进程等待与退出

处理机调度 进程切换：CPU资源的当前占用者的切换。 调度时机： 进程在CPU计算和I/O操作间交替 比较调度算法准则：CPU使用率（CPU处于忙碌状态的时间百分比）、吞吐量（单位时间完成的进程数量）、周转时间（进程从初始化到结束的总时间）、等待时间（进程在就绪队列中的总时间）、响应时间（从提交请求到产生响应所花费的总时间）

响应时间目标：减少响应时间、减少平均响应时间的波动 吞吐量目标：增加系统吞吐量（减少开销、提高系统资源的利用率）、减少等待时间 公平性目标：每个进程等待时间相同

周转时间=平均等待时间 调度算法： 先来先服务算法（FCFS）：依据进程进入就绪状态的先后顺序排序。 缺点：平均等待时间较差 短进程优先算法（SPN）：选择就绪队列中执行时间最短进程占用CPU进入运行状态。 短剩余时间优先：SPN的抢占算法 缺点：可能导致饥饿、需要预知未来（用历史的执行时间来预估未来的执行时间） 最高响应比优先算法（HRRN）：选择就绪队列中相应比R值最高的进程。 R=(W+S)/S=(等待时间+执行时间）/执行时间（避免了饥饿） 时间片轮转算法（RR）：时间片（分配处理机资源的基本时间单元） 时间片太大：退化成FCFS；时间片太小：大量上下文开销影响系统吞吐量 缺点：平均等待时间较差 多级队列调度算法（MQ）：就绪队列被划分为多个独立的子队列 多级反馈队列算法（MLFQ）：进程可以在不同队列间移动的多级队列算法 特征：CPU密集型进程的优先级下降很快，I/O密集型进程留在高优先级 公平共享调度算法（FSS）

实时调度： 优先级反置

调度准则