第一章 操作系统概论
操作系统是一种管理计算机系统资源，控制系统工作流程，方便用户使用计算机的系统软件。特权指令：只能由操作系统使用的指令，如果允许用户随便使用，有可能使系统系统陷入混乱非特权指令：用户只能使用非特权指令管态：（管理态、核心态）操作系统管理程序运行的状态,可以使用各种指令(特权和非特权指令)目态：（用户态）用户程序运行的状态,只能使用非特权指令
＊操作系统由哪两部分组成？各自功能？
核心(kernel)：负责管理计算机系统的资源,记录它们的状态,负责分配、使用和释放。外壳(shell)：计算机系统与用户之间的命令接口，用户通过它来使用计算机。外壳也称为命令解释程序。
操作系统的功能包括哪些？ 处理机管理 存储管理 设备管理 信息管理 用户接口
*试说明批处理系统、分时系统和实时系统的主要特征和适用场合
批处理操作系统：用户脱机使用计算机：作业提交后直到获得结果之前，用户无法与作业交互。作业成批处理。多道程序并行：充分利用系统资源（仅限多道批处理），往往用于大型计算中心，针对大型科学计算。
分时操作系统：多路性、独立性、交互性好。主要用于软件开发和运行小程序。
实时操作系统：及时性、高可靠性、专用性。用于过程控制（武器系统、工业控制）和事务处理（飞机订票系统、银行管理系统）。
第二章 操作系统用户界面
作业一个作业是指在一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所做的有关该次业务处理的全部工作。
*系统调用：是OS提供给编程人员的唯一接口 系统调用是由操作系统中的一段程序来完成特定功能的，属于一种特殊的过程调用。有的计算机系统中，把它称为广义指令。
*基本的作业调度算法有哪些？
先来先服务（FCFS）：按照作业进入系统的先后次序进行调度，先进入系统者先调度；即启动等待时间最长的作业。短作业优先（SJF）：以要求运行时间长短进行调度，即启动要求运行时间最短的作业。高响应比优先（HRF）：响应比最高的作业优先启动。
描述操作系统提供的两类用户接口（命令和系统调用）
程序接口（系统调用）程序接口是OS专门为用户程序设置的，也是用户程序取得OS服务的唯一途径 程序接口通常由各种各样的系统调用所组成。命令接口 作业控制一级的接口 联机用户接口：（交互式用户接口） 脱机用户接口：（批处理用户接口）
描述作业的四个状态
作业提交：作业的输入（从输入设备到外存）；作业收容（就绪）：作业输入（到外存）完成，系统为其建立JCB,等待调度运行；作业执行：分配资源，送入内存，被调度运行；作业完成：释放资源，完成作业输出；
第三章 进程管理
进程：一个具有一定独立功能的程序对某个数据集在处理机上的一次执行过程和分配资源的基本单位。
线程：作为CPU调度单位，引入线程的目的是提高系统的执行效率，减少处理机的空转时间和调度切换时间，以及便于管理。
临界资源硬件或软件（如外设、共享代码段、共享数据结构），多个进程在对其进行访问时（关键是进行写入或修改），必须互斥地进行。有些共享资源可以同时访问，如只读数据 间接制约 直接制约
临界区：进程中访问临界资源的一段代码。
＊信号量多道程序并发执行需要一个地位高于进程的管理者来解决公有资源的使用问题。OS可从进程管理者的角度来处理互斥的问题。
信号量就是OS提供的管理公有资源的有效手段。
原语 由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(proberen)和increment(verhogen)），是一种卓有成效的进程同步机制
死锁是指系统中多个进程无限制地等待永远不会发生的条件
一组并发进程互斥执行（进入临界区）时，应满足的准则是什么？
空闲则入：其他进程均不处于临界区；忙则等待：已有一进程处于其临界区；有限等待：等待进入临界区的进程不能无限等待；让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态），不阻止其它进程进入。
＊进程PCB包含哪些信息？
进程描述信息：进程标识符(process ID)，唯一，通常是一个整数；进程名，通常基于可执行文件名（不唯一）；用户标识符(user ID)；
进程家族关系
进程控制信息：当前状态；优先级(priority)；代码执行入口地址；程序的外存地址；运行统计信息（执行时间、页面调度）；进程间同步和通信信息；阻塞原因
资源管理信息：虚拟地址空间的现状、打开文件列表
CPU现场保护结构：寄存器值（通用、程序计数器PC、状态PSW）
＊线程的优点
减小并发执行的时间和空间开销（线程的创建、退出和调度），因此容许在系统中建立更多的线程来提高并发程度。
线程的创建时间比进程短；线程的终止时间比进程短；同进程内的线程切换时间比进程短；由于同进程内线程间共享内存和文件资源，可直接进行不通过内核的通信；
生产者－消费者问题问题描述：若干进程通过有限的共享缓冲区交换数据。其中，"生产者"进程不断写入，而"消费者"进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。full是"满"数目，初值为0，empty是"空"数目，初值为N。实际上，full和empty是同一个含义：full + empty == N mutex用于访问缓冲区时的互斥，初值是1 每个进程中各个P操作的次序是重要的：先检查资源数目，再检查是否(访问缓冲区)互斥――否则可能死锁
读者－写者问题问题描述：对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个“读－写”互斥，“写－写”互斥，"读－读"允许 采用信号量机制：Wmutex表示"允许写"，初值是1。公共变量Rcount表示“正在读”的进程数，初值是0；
Rmutex表示对Rcount的互斥操作，初值是1。
阐述死锁产生的四个必要条件及三种解决方法 只有4个条件都满足时，才会出现死锁。
资源互斥使用：任一时刻只允许一个进程使用资源 部分分配：进程在请求其余资源时，不主动释放已经占用的资源
不可剥夺性：进程已经占用的资源，不会被强制剥夺 环路等待：环路中的每一条边是进程在请求另一进程已经占有的资源。
| 方法 | 资源分配策略 | 各种可能模式 | 主要优点 | 主要缺点 |
| 预防 Prevention | 保守的；宁可资源闲置（从机制上使死锁条件不成立） | 一次请求所有资源<条件1> | 适用于作突发式处理的进程；不必剥夺 | 效率低；进程初始化时间延长 剥夺次数过多；多次对资源重新起动 不便灵活申请新资源 |
| 资源剥夺<条件3> | 适用于状态可以保存和恢复的资源 |
| 资源按序申请<条件4> | 可以在编译时（而不必在运行时）就进行检查 |
| 避免 Avoidance | 是“预防”和“检测”的折衷（在运行时判断是否可能死锁） | 寻找可能的安全的运行顺序 | 不必进行剥夺 | 使用条件：必须知道将来的资源需求；进程可能会长时间阻塞 |
| 检测 Detection | 宽松的；只要允许，就分配资源 | 定期检查死锁是否已经发生 | 不延长进程初始化时间；允许对死锁进行现场处理 | 通过剥夺解除死锁，造成损失 |
第四章：处理机管理
高级调度也称为作业调度或宏观调度，以作业为调度单位。高级调度的时间尺度通常是分钟、小时或天
中级调度涉及进程在内外存间的交换，从存储器资源管理的角度看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间，将当前进程所需部分换入到内存（指令和数据必须在内存里才能被处理机直接访问）
低级调度也称微观调度，从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态，低级调度的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效
可剥夺式：当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用
第五章：存储管理
逻辑地址：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用逻辑地址的形式。
物理地址：内存中存储单元的地址，物理地址可直接寻址。
地址映射：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址,也称为地址重定位。
覆盖：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间
交换: 暂停执行内存中的进程，将整个进程的地址空间保存到外存的交换区中（换出swap out），而将外存中由阻塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列（换入swap in）在程序装入时，不必将其全部读入到内存，而只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行。
虚拟存储器：局部性原理：程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。引入：在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统，将相应的页或段调入到内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的页或段调出保存在外存上，从而腾出空间存放将要装入的程序以及将要调入的页或段。只需程序的一部分在内存就可执行。虚拟存储器的容量：与计算机的地址结构和寻址方式决定，设指令中地址长度为n，则虚拟存储器的容量可达2n，这只是个理论值，实际上还要受内存和外存容量限制。优点：为用户提供一个独享、透明、很大的虚拟内存。缺点：实现较复杂，需要硬件支持。
联想寄存器：可按内容并行查找的快速寄存器。比内存贵，容量小。缺页率：表示“缺页次数 / 内存访问次数”(比率)
分区管理中，内存分配算法有哪四种?
1.最先匹配法(first-fit)：按分区的先后次序，从头查找，找到符合要求的第一个分区
–该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。
–但随着低端分区不断划分而产生较多小分区，每次分配时查找时间开销会增大。
2.次匹配法(next-fit)：按分区的先后次序，从上次分配的分区起查找（到最后分区时再回到开头），找到符合要求的第一个分区
–该算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大的空闲分区不易保留。
3.最佳匹配法(best-fit)：找到其大小与要求相差最小的空闲分区
–从个别来看，外碎片较小，但从整体来看，会形成较多外碎片。较大的空闲分区可以被保留。
4.最坏匹配法(worst-fit)：找到最大的空闲分区
–基本不留下小空闲分区，但较大的空闲分区不被保留。
页式存储管理的优、缺点？
l.优点：–没有外碎片，每个内碎片不超过页大小。–一个程序不必连续存放。–由于页的大小相等，内存的分配、回收简单。
2.缺点：程序要求全部装入内存，才能执行。
段式存储管理的优、缺点？
l.优点：–没有内碎片，外碎片可以通过内存紧缩来消除。–便于改变进程占用空间的大小。
2.缺点：–程要求全部装入内存
页式管理和段式管理的比较
l.分页是出于系统管理的需要，分段是出于用户应用的需要。
–一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。
2.页大小是系统固定的，而段大小则通常不固定。
3.逻辑地址表示：
–分页是一维的，各个模块在链接时必须组织成同一个地址空间；–分段是二维的，各个模块在链接时可以每个段组织成一个地址空间。
4.通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。
扩充内存的方法有几种?各自优缺点?实现内存扩充的三种技术：覆盖技术 交换技术 虚拟存储器
覆盖技术引入：其目标是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。
原理：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。将程序的必要部分（常用功能）的代码和数据常驻内存；
可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），在需要用到时才装入到内存；
不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。(即不同时用的模块可共用一个分区)
缺点：编程时必须划分程序模块和确定程序模块之间的覆�**叵担黾颖喑谈丛佣�,增加用户的不透明性。
从外存装入覆盖文件，以时间延长来换取空间节省。
交换技术引入：多个程序并发执行，可以将暂时不能执行的进程送到外存中，从而获得空闲内存空间来装入新程序，或读入保存在外存中而目前到达就绪状态的进程。交换单位为整个进程的地址空间。常用于多道程序系统或小型分时系统中，与分区存储管理配合使用。
进程暂时不能执行的可能原因：处于阻塞状态或低优先级（确保高优先级程序执行）；
原理：暂停执行内存中的进程，将整个进程的地址空间保存到外存的交换区中（换出swap out），而将外存中由阻塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列（换入swap in）。
优点：增加并发运行的程序数目，并且给用户提供较快的响应时间；换入和换出由操作系统完成，对用户完全透明。
缺点：对换入和换出的控制增加处理机开销；程序整个地址空间都进行传送，没有考虑执行过程中地址访问统计特性。
注：覆盖技术在同一进程地址空间进行，而交换在整个系统范围内进行。
虚拟存储器
局部性原理：程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。
引入：在程序装入时，不必将其全部读入到内存，而只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行。
在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统，将相应的页或段调入到内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的页或段调出保存在外存上，从而腾出空间存放将要装入的程序以及将要调入的页或段。只需程序的一部分在内存就可执行。
虚拟存储器的容量：与计算机的地址结构和寻址方式决定，设指令中地址长度为n，则虚拟存储器的容量可达2n，这只是个理论值，实际上还要受内存和外存容量限制。
优点：为用户提供一个独享、透明、很大的虚拟内存。缺点：实现较复杂，需要硬件支持。
l.请求页式管理中,进程页表中中断位、修改位、引用位的各自作用？请求页式管理中页表项应该包括哪些信息?
标志位：中断位（interrupt bit，是内存页还是外存页，也称存在位，present bit ），修改位(modified bit)
访问统计：在近期内被访问的次数，或最近一次访问到现在的时间间隔，如引用位 外存地址
*内碎片和外碎片的概念,各种存储管理策略中的碎片情况
内碎片:是指页面内部没有被使用的存储区域，在页式存储方式中，会出现内碎片。
外碎片:是指没有得到分配权的存储区域，在段式存储方式中，会产生外碎片
固定分区：优点：易于实现，开销小。缺点：内碎片造成浪费 分区总数固定，限制了并发执行的程序数目。信息共享困难
动态分区：优点：无内碎片；内存利用率高于固定分区，可装入更多进程。缺点：有外碎片；分配、回收较固定分区复杂；信息共享困难。
静态页式：优点：没有外碎片，每个内碎片不超过页大小。一个程序不必连续存放。由于页的大小相等，内存的分配、回收简单。
缺点：程序要求全部装入内存，才能执行
静态段式：优点：没有内碎片，外碎片可以通过内存紧缩来消除。缺点：进程要求全部装入内存。
第六章 文件系统
文件：文件是具有符号名的数据项的集合。文件名是文件的标识符号。文件包括两部分文件体和文件说明
文件系统是操作系统中管理文件的机构，提供文件存储和访问功能。
目录：操作系统将若干个文件说明放在一张表格中，称该表格为文件目录，其中每一个表目（文件说明）称为目录项
1.描述目录的几种组织结构特点
一级目录：整个目录组织是一个线性结构，系统中的所有文件都建立在一张目录表中。它主要用于单用户操作系统。它具有如下的特点：结构简单；文件多时，目录检索时间长；有命名冲突：如重名(多个文件有相同的文件名) 或别名(一个文件有多个不同的文件名)
二级目录：在根目录下，每个用户对应一个目录（第二级目录）；在用户目录下是该用户的文件，而不再有下级目录。适用于多用户系统，各用户可有自己的专用目录。
多级目录：或称为树状目录。在文件数目较多时，便于系统和用户将文件分散管理。适用于较大的文件系统管理。目录级别太多时，会增加路径检索时间。目录名：可以修改。目录树：中间结点是目录，叶子结点是目录或文件。目录的上下级关系：当前目录、父目录、子目录、根目录等；路径：每个目录或文件，可以由根目录开始依次经由的各级目录名，加上最终的目录名或文件名来表示；
2.描述文件的几种物理结构特点
连续文件（顺序文件）：逻辑上连续，物理上也连续。存在外部碎片问题，外存利用率低，文件修改困难，不利于文件插入和删除。
串联文件（链接文件）：逻辑上连续，物理上不连续，将存储某个文件的物理块用链表链接起来，形成单向链表。优点：提高了磁盘空间利用率,不存在外部碎片问题，有利于文件插入和删除，有利于文件动态扩充. 缺点：存取速度慢，不利于文件的随机访问。
索引文件：物理上不连续，系统为每个文件建一张索引表，包含文件逻辑块与物理块的对应关系。 即可顺序访问，又可随机访问，外存利用率高，只是索引表占一定空间
第七章 设备管理
单缓冲：一个缓冲区，CPU和外设轮流使用，一方处理完之后接着等待对方处理。
双缓冲：两个缓冲区，CPU和外设都可以连续处理而无需等待对方。要求CPU和外设的速度相近。
环形缓冲：多个缓冲区，CPU和外设的处理速度可以相差较大。
缓冲池这是一种双方向缓冲技术；缓冲区整体利用率高
假脱机技术(SPOOLing, Simultaneous Peripheral Operation On Line,即外部设备同时联机操作,也称为虚拟设备技术)可把独享设备转变成具有共享特征的虚拟设备，从而提高设备利用率。
l.SPOOLING技术的原理？
SPOOLing程序和外设进行数据交换，可以称为“实际I/O”。一方面，SPOOLing程序预先从外设输入数据并加以缓冲(放在输入井中)，在以后需要的时候输入到应用程序；另一方面，SPOOLing程序接受应用程序的输出数据并加以缓冲(放在输出井中) ，在以后适当的时候输出到外设。应用程序进行I/O操作时，只是和SPOOLing程序交换数据，可以称为"虚拟I/O"。这时虚拟I/O实际上是从SPOOLing程序的缓冲池中读出数据或把数据送入缓冲池，而不是跟实际的外设进行I/O操作。
2.两种设备分配方式（静态和动态分配）优缺点
设备分配方式：各有优缺点
静态分配：在进程分创建时分配，在进程退出时释放；不会出现死锁；设备利用率不高；
动态分配：在进程执行过程中根据需要分配，使用结束后释放；需要考虑死锁问题,有利于提高设备利用率
设备驱动程序的作用
驱动程序是I/O处理功能的低级系统例程。它具有如下特征：
中转数据和控制：不是数据和控制的源端和目的端（应用程序和设备）
与硬件特性密切相关：通常由硬件厂商提供。
向上屏蔽设备细节：不同类型设备通常其设备驱动程序接口不同，同类设备的接口相同。因此，同类设备的不同型号，只要更换设备驱动程序则可由OS使用。
