1. OS的概念、特性​

概念​

操作系统是计算机系统中的一个系统软件，是一些程序模块的集合。

特性​

1. 并发/并行
2. 共享：操作系统与多个用户程序共同使用计算机系统中资源，其中分为：
   • 互斥共享：资源不能同时使用。
   • 同时共享：资源可以同时使用。
3. 虚拟：一个物理实体映射为若干个对应逻辑实体（分时或分空间）。存储器中每个进程都有独立的虚拟地址空间（存代码、数据、堆栈）。
4. 随机：OS要对不可预测的事件进行响应处理。

2. OS的功能​

1. 资源分配​

• 静态分配策略：把进程所有需要的资源先都分配给它，但这可能导致资源浪费。
• 动态分配策略：进程什么时候需要资源就什么时候分配，如果该资源已被占用，进程会阻塞并进入相应的等待队列。

2. 资源管理​

• 进程/线程管理
• 存储管理
• 文件管理
• 设备管理
• 用户接口管理

3. OS的发展历史及分类​

1) 批处理操作系统​

工作方式​

1. 用户将作业（作业：由作业说明书、用户程序、数据组成，且通常为卡片形式，输入设备为卡片机）交给系统操作员。
2. 系统操作员将多个作业组成一批作业，输入到计算机系统中，形成一个自动转接的连续作业流。
3. 启动OS。
4. OS自动执行每个作业，用户无法干预。
5. 执行结果交给用户。

追求目标​

• 提高资源利用率，增加作业处理吞吐量。

总体过程​

• 从卡片机读入用户作业和编译链接程序，编译链接生成可执行程序，执行程序并输出执行结果。

问题​

• 慢速I/O设备与CPU处理速度差异过大，导致CPU在等待数据时空闲。

2) Spooling技术​

利用磁盘做缓冲，将输入、计算、输出分别组成独立的任务流，使I/O和计算并行（假脱机：磁盘在高效的计算机上）。

工作流程​

1. 用户作业输入磁盘输入。
2. 按照某种调度策略，选几个搭配得当的作业调入内存。
3. 作业运行结果输出到磁盘的输出。
4. 运行结果从输出井到打印机。

备注：输入输出只到输入或输出井，主机不用直接与慢速的I/O打交道，能提高效率和速度。

现代打印机仍然使用这种技术。

应用Spooling技术后：

3) 分时操作系统​

工作方式​

多个终端（只有I/O设备没有计算能力）连接到同一主机中，然后OS将CPU时间分成若干个片段，OS以时间片为单位，轮流为每个终端用户服务，每次服务使用掉一个时间片。

追求目标​

• 及时响应。
• 响应时间：指从终端发出命令到系统给予回答所经历的时间。

4) 实时操作系统​

指计算机能及时响应外部时间请求，在规定的严格时间内完成对该事件的处理。

追求目标​

• 对外部请求在严格时间范围内做出响应。

---

第二章 OS硬件环境

1. 管态与目态​

通常CPU执行两种不同性质的程序：一种是操作 系统内核程序；另一种是 用户自编程序或系统外层的应用程序。对操作系统而言，这两种程序的作用不同，前者是后者的管理者，因此“管理程序”要执行一些特权指令(不允许用户直接使用的指令，如I/O指令、置中断指令等），而“被管理程序”出于安全考虑不能执行这些指令。所以我们将机器分为两种状态，通过状态的切换来保护操作系统程序。

• 管态(核心态、系统态)：在此状态下，CPU可以执行指令系统的全集，是一种具有较高特权的执行状态，可以访问所有寄存器和存储区。另外OS内核通常是运行在系统态的，进程控制是由OS内核实现。
• 目态(用户态)：在此状态下，CPU只能执行非特权指令。可访问指定的寄存器和存储区，只具有较低的特权。一般的用户程序在此状态下执行。

2. 多级存储体系​

原因​

计算机采用多级存储，主要是基于 容量、速度、成本 这三个因素考虑的。

多级存储结构 从上到下，容量越来越大，速度越来越慢，成本越来越低；

同时这种多级存储的模式有利于计算机CPU发挥其性能，还解决了数据存储的问题；

因为外存虽然成本低，但是比较慢；它的运行频率、工作频率，数据的传送情况都是比较慢的；

寄存器虽然速度很快，但是成本高，容量小；

Cache​

Cache是现代计算机在CPU和主存之间设置的一个高速、小容量的缓冲存储器，填补了CPU和主存在速度上的巨大差距，可用用于提高整个计算机系统的性能。

Cache先被访问，如果不命中，内存后被访问

cache 映射​

◆ 直接映像 ➢ 某一主存块只能固定映射到某一缓冲块 ◆ 全相联映像 ➢ 某一主存块能映射到任一缓冲块 ◆ 组相联 ➢ 某一主存块只能映射到某一缓冲组中的任一块

靠近CPU的Cache要求高速，采用直接相联或路数较少的组相联；中间层次采用组相联；距离CPU最远的Cache采用全相联，对利用率强调越高。

cache 优化​

cache例题1

多级cache例题1

①强制性失效：当第一次访问一个块时，需要从下一级存储器中调入Cache，这种失效称为强制性失效。也称为冷启动失效或首次访问失效。强制性失效发生在对初始空Cache的访问中。 ②容量失效：由于Cache容量有限，使得程序执行所需的块不能全部调入Cache中，所以当某些块被替换后如果重新被访问就会发生失效。这种失效就称为容量失效。 ③冲突失效：在组相联或直接映像Cache中，多个块映像到同一组（个）块中，则会出现该组中的某一个块被别的块替换后又被重新访问的情况，这就发生了冲突失效。冲突失效也称为碰撞失效或干扰失效。

关于Cache失效的一些结论：

①Cache容量对失效的影响：强制性失效不受到Cache容量的影响，但是容量失效随着容量的增加而减少； ②相联度对失效的影响：强制性失效和容量失效不受相联度的影响，但是相联度越高冲突失效就越少； ③经验规则：大小为N的直接映像Cache的失效率约等于大小为N/2的2路组相联Cache的失效率。

虚拟存储​

虚拟存储器的分块​

虚存的分块方式：虚存的分块可以分为段式、页式和段页式三种。采用哪一种分块方式对操作系统的性能具有很大的影响。 ①页式分块：页式虚存把空间划分为大小相同的页面，其中每个存储单元的地址都是单一、固定长度的地址字，由页号和页内位移两部分组成。 ②段式分块：往往是按照程序的逻辑结构进行划分，段的长度可变。这种方式中地址一般用两个字表示：一个是段号，另一个是段内位移。 ③段页式分块：同时采用段式和页式，也就是将每个段划分为若干个页面。这种方式不仅保持了段作为逻辑单元的优点，又简化了替换操作的实现。

---

第三章 用户接口与作业管理

作业的概念，作业级接口与程序级接口​

1. 作业的概念​

作业就是用户一次请求计算机系统为用户完成任务所做工业的综合

2. 接口​

• **程序级接口：**系统为用户在程序一级提供有关服务而设置的，由一组系统调用命令组成
• 作业级接口: 系统为用户提供的各种命令接口，用户利用这些操作命令来组织和控制作业的执行或管理计算机系统

JCB；作业的状态及转换​

作业状态及转换​

一个作业在其生命周期内会经历多个状态，这些状态的变化反映了作业当前所处的阶段。常见的作业状态包括：

• 提交状态：当用户将作业提交给系统后，作业处于提交状态。此时，作业的信息正在进入外存的“作业收容井”中。
• 后备状态：作业已全部进入外存，等待被调度进入内存。在此状态下，系统为作业创建了作业控制块（JCB），记录了作业的各种属性和状态信息。
• 执行状态：作业被选中加载到内存中开始执行。这个阶段可能包括编译、链接、装入和实际运行等子阶段。一旦作业进入了执行状态，它就处于宏观上的运行中。
• 完成状态：作业已经执行完毕，所有资源已经被回收，作业结果可能已经输出。此时作业处于完成状态，等待最终的数据输出或删除。

作业控制块(JCB)​

作业控制块（JCB）是作业在系统中存在的唯一标志，它记录了与该作业有关的所有必要信息。JCB的内容通常包含以下方面：

• 作业标识：如作业号、用户名等。
• 作业类型：CPU繁忙型、I/O繁忙型、批量型、终端型等。
• 作业状态：反映作业当前的状态，如后备、执行、完成等。
• 资源需求：作业所需的内存大小、I/O设备类型和数量等。
• 优先级：根据作业的性质设定的优先级。
• 其他信息：如预计运行时间、实际运行时间、收费标准等。

JCB对于作业管理和调度至关重要，因为它是操作系统了解作业需求并据此进行决策的基础。每当作业的状态发生变化时，相应的JCB也会更新，以反映最新的作业状态。

作业调度算法：FCFS/SJF/HRN​

1. 先来先服务​

原理：按照作业到达系统的顺序进行调度，即最早到达的作业最先得到处理。

优点：实现简单，公平性好。 缺点：如果长作业位于队首，则短作业可能需要等待很长时间，导致平均周转时间较长。

例题： 假设有以下四个作业按如下时间提交给系统：

• 作业A：提交时刻10:00，运行时间2小时
• 作业B：提交时刻10:06，运行时间1小时
• 作业C：提交时刻10:15，运行时间0.25小时

使用FCFS算法计算它们的平均周转时间和平均带权周转时间。

解答：

• 作业A开始时间10:00，结束时间12:00，周转时间2小时，带权周转时间1
• 作业B开始时间12:00，结束时间13:00，周转时间2.9小时，带权周转时间2.9
• 作业C开始时间13:00，结束时间13:15，周转时间3小时，带权周转时间12

平均周转时间 = (2 + 2.9 + 3) / 3 ≈ 2.63 小时 平均带权周转时间 = (1 + 2.9 + 12) / 3 ≈ 5.30 小时

2. 短作业优先​

原理：选择估计运行时间最短的作业优先执行。

优点：可以减少平均等待时间，提高系统响应速度。 缺点：可能导致长作业长时间得不到执行，造成“饥饿”现象。

例题： 假设同样有上述三个作业，使用SJF算法计算它们的平均周转时间和平均带权周转时间。

解答：

• 作业A开始时间10:00，结束时间12:00，周转时间2小时，带权周转时间1
• 作业B开始时间12:15，结束时间13:15，周转时间3.1小时，带权周转时间3.1
• 作业A开始时间12:00，结束时间12:15，周转时间2小时，带权周转时间8

平均周转时间 = (2 + 3.1 + 2) / 3 小时 平均带权周转时间 = (1 + 3.1 + 8) / 3 小时

3. 高响应比优先​

原理：根据作业的响应比来决定调度顺序，响应比定义为 (等待时间 + 作业长度) / 作业长度。

优点：平衡了等待时间和作业长度，防止饥饿现象。 缺点：需要动态计算响应比，增加了系统开销。

例题： 假设有四个作业提交给系统，其信息如下：

• 作业D：提交时刻8:00，运行时间2小时
• 作业E：提交时刻8:30，运行时间0.5小时
• 作业F：提交时刻9:00，运行时间0.1小时
• 作业G：提交时刻9:30，运行时间0.2小时

使用HRRN算法计算它们的平均周转时间和平均带权周转时间。

解答：

• 作业D完成时间10:00
• 作业F完成时间10:06
• 作业E完成时间10:36
• 作业G完成时间10:46

作业D周转时间2小时，带权周转时间1 作业F周转时间0.1小时，带权周转时间1 作业E周转时间1.5小时，带权周转时间3 作业G周转时间1.2小时，带权周转时间6

平均周转时间 = (2 + 0.1 + 1.5 + 1.2) / 4 = 1.2 小时 平均带权周转时间 = (1 + 1 + 3 + 6) / 4 = 2.75 小时

系统调用（访管中断）​

访管指令是一条可以在用户态（又称目态）下执行的指令。在用户程序中，因要求操作系统提供服务而有意识地使用访管中断，从而产生一个中断事件（自愿中断），将操作系统转换为核心态，称为访管中断。访管中断由访管指令产生，程序员使用访管指令向操作系统请求服务。

---

第四章 进程管理

1. 程序的顺序执行的特点；多道程序并发执行的特点​

顺序执行时​

1.顺序性：严格的按照顺序执行

2.封闭性：程序运行时独占全机资源 资源状态只有本程序才能改变它，程序一旦开始执行，不受外界影响

3.可再现性：无论如何执行 都可缺获得相同的结果

并发执行时​

1.间断性：由于资源有限，并发执行的程序存在相互制约的关系

2.失去封闭性：并发执行的程序共享计算机资源，这些资源的状态由这些程序改变

3.不可再现性：并发执行的程序执行的顺序不同可能有不同的执行结果

3个点分别对立

1. 顺序性 -> 间断性, 程序执行相互制约
2. 封闭性 -> 失去封闭性, 资源状态随程序进行改变
3. 可再现性 -> 不可再现性, 每次执行都可能结果不同

2. 进程的状态及变迁​

状态变迁​

1. 运行态 → 等待态 当一个运行程序 因某件时间受阻 时，如申请资源被占用、启动数据传输未完成等，其状态会变迁； 详细点就是 请求外部传输：一个程序在运行时需要进行打印，提出外部请求使用打印机，然后从运行态变迁为等待态；

2. 等待态 → 就绪态 当所等待的事件发生时，如得到被申请资源、数据传输完成，其状态会由等待变为就绪；

3. 就绪态 → 运行态 当一个就绪程序获得CPU时，其状态就由就绪态变为运行态；

4. 运行态 → 就绪态 运行进程被剥夺处理器资源； 在分时操作系统中，该程序 用完了系统分配的时间片； 或者 出现高优先级别的其他进程；

5. 就绪态 → 等待态 不是全错，还是有可能的； 可能有，只是 现在的OS一般都没有这个变迁；

6. 等待态 → 运行态

   全错；这个变迁是绝对没有的；

3. 进程调度与时间片​

例题

4. 进程控制​

• 阻塞原语:

  • 进程的阻塞是要靠调用阻塞原语来实现。
  • 阻塞原语在进程期待某事件发生，但没有发生时(或所需资源尚不具备时)，被该进程调用来阻塞自己。(所以可以发现，阻塞常常是一种自我阻塞的过程，类似于人的欲望得不到满足，就降低要求)

• 唤醒原语:

  • 事件发生进程 和 被唤醒进程 之间是合作关系，唤醒原语既可被系统进程调用，也可被事件发生进程调用。(当然，进程不能够被自己唤醒，需要 “外界的激励” )

• 挂起原语与激活原语:

  • 挂起原语即可由进程自己也可由其他进程调用，但激活原语却只能由其他进程调用。

5. pv操作​

pv

6. 进程间通信​

• 管道(pipe)

  管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。

• 有名管道 (namedpipe)

  有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。

• 信号量(semaphore)

  信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。

• 消息队列(messagequeue)

  消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。

• 信号 (sinal)

  信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。

• 共享内存(shared memory)

  共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。

• 套接字(socket)

  套接口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同设备及其间的进程通信。

7. 死锁​

产生条件​

1. 互斥条件 ： 指进程对所分配的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直到占有资源的进程用完后释放资源。

2. 占有且等待条件 ： 指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程阻塞，但它不会释放自己已经占有的资源。

3. 非抢占条件 ： 指进程已经获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

满足以上三个条件可能会产生死锁，但如果只有这三个条件，则不一定产生死锁。对死锁的产生，还需要第四个条件。

4. 循环等待条件 : 存在一个封闭的进程链，使得每个资源至少占有此链中下一个进程所需要的一个资源。

解决​

1. 破坏“互斥“条件 就是在系统里取消互斥。若资源不被一个进程独占使用，那么死锁是肯定不会发生的。但一般来说，第一个条件是不可能被禁止的，比如打印机等临界资源只能互斥使用。

2. 破坏“占有并等待”条件 就是在系统中不允许进程在已获得某种资源的情况下，申请其他资源，要求进程一次性地请求所有需要的资源，并且阻塞这个进程直到所有请求都同时满足。

   这样做有几个个缺陷，会很低效：

   一个进程可能被阻塞很长时间，等待满足其所有的资源请求，而实际上，只要有一部分资源，它就可以继续执行。 分配给一个进程的资源可能有相当长的一段时间处于不可用状态，并且再次期间，它们不能被其他进程使用。 一个进程可能事先并不会知道它所需要的所有资源。

3. 破坏“非抢占“条件 如果占有某些资源的一个进程进行进一步资源请求被拒绝，则该进程必须释放它最初占用的资源，如果有必要，可再次请求这些资源和另外的资源。 另一种方法是，要求两个进程不具有相同的优先级时才能有效预防死锁。即如果一个进程请求当前另外一个进程占有的一个资源，则操作系统可以抢占另一个进程，要求它释放资源。

上述这两种方法只有在资源状态可以很容易地保存和恢复的情况下（如处理器），比较实用。

4. 破坏“循环等待“条件​

   循环等待条件可以通过定义资源类型的线性顺序来预防。如果一个进程已经分配到了R 类型的资源，那么接下来请求的资源只能是那些排在R 类型之后的资源类型。

8. 银行家算法​

银行家算法

---

第五章 存储管理

1. 页面置换算法​

页面置换算法

存储管理​

存储管理

碎片回收​

• 碎片紧凑

  • 实现方式：通过移动分配给进程的内存分区，以合并外部碎片。

• 分区对换

  • 抢占并回收处于等待状态进程的分区，以增大可用内存空间

• 伙伴系统

  • 空闲块按大小和起始位置组织称二维数组；
  • 初始状态时，只有一个大小为的空闲块；

  分配过程：

  • 由小到大在空闲块数组中找最小的可用空闲块；
  • 如果空闲块过大，对可用空闲块进行二等分，一个放入空闲块列表，另一块继续比较，直到得到合适的可用空闲块

2. 段页式内存​

段页式内存

---

第六章 文件系统

1. 有结构文件的逻辑结构​

顺序文件​

顺序文件：文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。各个记录在物理上可以顺序存储或链式存储。

定长记录的顺序文件，若物理上采用顺序存储，则可实现随机存取；若能再保证记录的顺序结构，则可实现快速检索（即根据关键字快速找到对应记录）

一般来说，考试题目中所说的“顺序文件”指的是物理上顺序存储的顺序文件。可见，顺序文件的缺点是增加/删除一个记录比较困难（如果是串结构则相对简单）

索引文件​

索引表本身是定长记录的顺序文件。因此可以快速找到第i个记录对应的索引项。可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找。每当要增加/删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。

另外，可以用不同的数据项建立多个索引表。如：

学生信息表中，可用关键字“学号”建立一张索引表。也可用“姓名”建立一张索引表。这样就可以根据“姓名”快速地检索文件了。

（Eg：SQL就支持根据某个数据项建立索引的功能）

索引顺序文件​

索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是：并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。

索引顺序文件（检索效率分析）​

若一个顺序文件有10000个记录，则根据关键字检索文件，只能从头开始顺序查找（这里指的并不是定长记录、顺序结构的顺序文件），平均须查找5000个记录。

若采用索引顺序文件结构，可把10000个记录分为√10000 = 100 组，每组100个记录。则需要先顺序查找索引表找到分组（共100个分组，因此索引表长度为100，平均需要查50次），找到分组后，再在分组中顺序查找记录（每个分组100个记录，因此平均需要查50次）。可见，采用索引顺序文件结构后，平均查找次数减少为50+50 = 100次。同理，若文件共有106个记录，则可分为1000个分组，每个分组1000个记录。根据关键字检索一个记录平均需要查找500+500 = 1000次。这个查找次数依然很多，如何解决呢？

多级索引顺序文件​

为了进一步提高检索效率，可以为顺序文件建立多级索引表。例如，对于一个含106个记录的文件，可先为该文件建立一张低级索引表，每100个记录为一组，故低级索引表中共有10000个表项（即10000个定长记录），再把这10000个定长记录分组，每组100个，为其建立顶级索引表，故顶级索引表中共有100个表项。

2. 文件目录​

---

第七章 设备管理

1. 设备的分类；设备控制（I/O 4方式）；设备管理的功能；高速缓存
2. 虚拟设备技术；SPOOLing技术；（输入井输出井，预输入缓输出）
3. 设备独立性