【期末复习】 计算机操作系统

第一章 操作系统引论

历史上最重要的阶段可能会考选择填空，牢记三大特点，四大特征，五大功能

1.1 OS的目标和作用

1.2 OS的发展过程

1.3 OS的基本特性（必考）

并发 共享 虚拟 异步

1.4 OS的主要功能

? ? ? ? 后续都是一个大章

? ? ? ? 五个功能：处理机管理功能，存储器管理功能，设备管理功能，文件管理功能，OS与用户之间的接口

1.5 OS结构设计

? ? ? ? 无结构——模块结构——分层结构——客户端/服务器结构——面向对象——微内核

第一章计算题：

例1：有3个作业A,B,C，A是计算作业，B是检索作业，C是打印作业。3个作业单道运行时间分别为5min，15min，10min，假设可在15min内并行完成这3个作业，则单批，多批对应的资源利用率是多少？?

?

例2：同时运行A和B

????????程序A：磁带（30S）、CPU（10S）、磁盘（30S）、CPU（10S）、磁带（20S）
????????程序B：磁盘（20S）、CPU（30S）、磁带（40S）

????????假定：CPU、磁盘和磁带都能并行工作
????????试问：在单道和多道两种方式下，
????????1、程序A和B从投入运行到运行完成所用的时间分别是多少？
????????2、CPU、磁盘和磁带的利用率是多少？

第二章 进程的描述与控制

2.1 程序执行

2.2 进程的描述（重点）

2.4 进程同步（重点）

2.4 信号量机制（含大题）

? ? ? ? 信号量是一种只能进行PV操作的特殊变量。

? ? ? ? P(passeren 通过）：wait? ? -1 如果是0是则阻塞

? ? ? ? V(vrijgeven 释放）：signal +1

重点看生产者-消费者问题和哲学家进餐问题（后者比前者多一个死锁，其他类似）

建议先看本章计算题

2.6 进程通信（应该是新加的内容，题型很少）

进程的互斥与同步——低级进程通信（效率低）

2.7 线程

第二章计算题

????????桌上有一个空盘（缓冲区），一次只能放一个试过，爸爸可以放苹果也可以放橘子，儿子只吃橘子，女儿支持苹果。

????????不会的可以跳转视频听小姐姐讲：

【期末突击操作系统第二章】 【精准空降到 1:04:29】 https://www.bilibili.com/video/BV1mE411N7cm/?share_source=copy_web&vd_source=16df222690d7e88b3cb2f0bc73603dae&t=3869

第三章 处理机调度与死锁（含大题）

开始准备汗流浃背了

3.1 处理机调度的层次

高级调度/长程调度/作业调度：决定将外存上处于后备队列中那几个作业调入内存

低级调度/短程调度/进程调度：决定就绪队列中哪个进程获得处理机

中级调度/中程调度/内存调度：把内存中暂时不能运行的进程调入外存等待（即挂起）

?

3.2 作业与作业调度

主要看后面的题

（1）先来先服务（FCFS，first-come first served）

????????按照作业到达的先后进行调度

（2）短作业优先（SJF，Short Job First）

（3）高响应比优先（HRRN，Highest Response Ratio Next）

3.3 进程调度

对系统性能影响最大的一种处理机调度

抢占原则主要分一下3种（含其一即可）：优先权原则，短进程优先原则，时间片原则

（1）基于时间片的轮转（RR，Round Robin）

（2）优先级调度算法

（3）多级反馈队列（MFQ，Multileved Feedback queue）

3.5 死锁

死锁的定义：如果一组进程中的每一个进程都在等待仅由该组进程中其他进程才能引发的事件，称该组进程是死锁的。

3.6 预防死锁（了解即可）

3.7 避免死锁（重点）

????????安全状态：系统能按某种进程推进顺序为每一个进程分配其所需的资源，直至满足每个进程对资源的最大需求，是每一个进程都可以顺利的完成。

????????（人话：找到一个不死锁的顺序让所有进程都能拿到全部资源）

安全序列

银行家算法

第三章计算题

（1）FCFS

（2）SJF

（3）HRRN

（4）RR

（5）优先级 非抢占

（6）优先级 抢占

（7）银行家算法

第四章 存储器管理

主存储器也被称为内存

程序要在系统中运行，必须先装入内存

我们写的程序、作业的逻辑地址均是从0开始，然后装入内存之后的地址叫做物理地址。

碎片：现在用了0-100, 200-300，则100-200就是碎片

4.2程序的装入

4.3连续分配存储管理方式

4.4 对换

就是把打的运行不了的进程拿走放到外存（对换区），把小的运行的了的放进来

4.5 分页存储管理

将逻辑地址分成若干相等的项，称页面

将内存的物理地址分成若干相等的块，称物理块（或页框）

页和块大小相等

这个大小必须适中，必须是2的幂次方，通常是4KB-8KB

第四章计算题

例1：3个作业申请分配的内存空间分别为100K，30K，7K

当前空白区：

（1）FF（首次适应算法）

（2）NF（循环首次适应算法）

（3）BF（最佳适应算法）

例2：地址长32位，其中0-11为页内地址，12-31为页号

例3：已知逻辑地址为2170B，页面大小为1KB，求页号和页内地址

第五章 虚拟存储器

虚拟：实际上就64GB内存，但虚拟一下，你就感觉有128GB内存，但实际不变

怎么实现：在上一章分页的基础上，通过请求调入和置换，即10MB的程序，只需把最开始那1MB放进去，这部分用户案例，请求调入下1MB，然后将二者置换，以此类推完成该程序。

页表plus——请求页表：

缺页中断：每当要访问的页面不在内存是，便产生一次缺页中断，然后请求OS将所缺页调入内存。

5.2.1 请求分页中的内存分配（了解即可）

相当于给几个工厂分机器怎么分

5.2.2 页面调入策略（了解即可）

机器有了，加工原料怎么获取

5.3 页面置换算法（含计算题）

注意：页面中断次数 = 页面置换次数 + 分配的块数

（因为最开始那几次调入也发生了页面中断）

第五章计算题

例1：假定分配3个物理块，并考虑以下的页面引用串：

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

求页面置换次数和页面中断次数。

（1）最佳置换算法（OPT）

????????淘汰未来最长时间不用的

????????（属于理论上的算法，因为不可能提前知道所有顺序）

（2）先进先出（FIFO）

????????把停留时间最长的淘汰

（3）最近最久未使用的（LRU）

????????把最近中最久没用到的淘汰掉

第六章 设备管理

I/O系统管理的主要对象是I/O设备和相应的设备管理器

6.3 中断

没有中断，多道程序就不可能实现

6.4 设备驱动程序

6.6 用户层I/O软件（重点）

假脱机技术（Spooling）：将一台物理I/O设备虚拟成多台逻辑上的I/O（类似原来的虚拟存储器），在外存中开辟两个存储空间——输入井和输出井。

6.7 缓冲

分为单缓冲，双缓冲，循环缓冲，缓冲池

6.8 磁盘调度算法

第六章计算题

例1：现在都从100号磁道开始，顺序是55 58 39 18 90 160 150 38 184，求平均寻道时间。

（1）先来先服务（FCFS）

????????按顺序一个一个来

（2）最短寻道时间（SSTF）

????????选离上一个最近的

（3）扫描（SCAN）

????????先按大小排序，如1,2,3,5,6，假设现在从3开始，那下面先选近的3 2 1，然后再跑另一边，不过是5 6，不是 6 5

（4）循环扫描（CSCAN）

????????跟上一个一样只不过最后是6 5 即从最远端开始，而不是 5 6

第七章 文件管理

内存易失，断电即消失，所以得用外存，而文件管理可以帮助用户管理外存上的文件。

7.1 文件概述

数据项：

记录：

文件：

文件类型：

文件层次结构：

7.2 文件的逻辑结构

1）文件的逻辑结构：以用户角度观察到的文件组织形式

2）文件的物理结构：即存储结构

顺序文件：

最基本，最常见

记录寻址：

就是怎么访问“顺序文件”

7.2.4 索引文件

用于变长文件，即在原来的逻辑文件旁边建个索引表（索引号，长度，指针），指针指向逻辑文件中的对应文件

多个索引表文件就是建立多个索引表，但这里的索引表之间无联系。

7.2.5 索引顺序文件

跟索引文件一样，只不过对其中逻辑文件仍采用“顺序查找”方式（其实7.2.4也是这样）

7.3文件目录

就是我们理解的正在用的文件目录，要用到文件控制块FCB（File Control Block），一个FCB就是一个文件目录，里面不仅有基本信息，还有控制信息和使用信息。

整体分成（单级，两级，树形结构）目录

两级目录就是两个一级目录嵌套，树形就是树形状俄罗斯套娃。

第八章 磁盘存储器的管理

可以理解为超级外存，又大又快

8.1 外存的组织方式

连续组织方式：

链接组织方式：

索引组织方式：

多级索引方式和增量式索引方式：

8.2 文件存储空间的管理（可能含计算）

类似第四章内存分配，也是空白区，文件放空

空闲表法：

设置一个空闲盘块表，里面包含空闲盘区号和它有的空闲盘块数，使用FF，BF算法，不用WF算法。

空闲链表法：

上一个的链表版本，设置空闲盘块链和空闲盘区链

对一个好分配存取，多个就太慢了

位示图法：

成组链接法：

就是空闲链表法的俄罗斯套娃