第一章 概述

操作系统在干嘛，底层思想

第二章 进程管理

操作系统的最大作用，核心功能

第三章 内存管理

物理地址到逻辑地址的映射，脱离硬件第一步

第四章 文件管理

再封装管理各种数据，脱离硬件第二部，到达软件层面

第五章 I/O管理

联通硬件和软件，捋一下各种功能

第一章 计算机系统概述

目的：为什么要有操作系统，拿来干嘛？管理什么？

思想：有什么底层思想支撑操作系统的开发？

历史：操作系统是怎样一步一步发展起来的？

组成：操作系统运行机制，靠什么实现的？

操作：由底层思想可以延伸出什么基本操作？

状态：操作系统在运行过程中有哪些状态？

结构：操作系统的结构，和位于计算机哪个位置？

目的：为什么要有操作系统，拿来干嘛？管理什么？

概念、功能、管理、接口

思想：有什么底层思想支撑操作系统的开发？

并发、共享、虚拟、异步、封装

历史：操作系统是怎样一步一步发展起来的？

手工操作阶段、单道批处理、多道批处理、分时操作系统、实时操作系统、分布式、个人

组成：操作系统运行机制，靠什么实现的？

内核程序、自编程序、原语、时钟管理、中断机制

操作：由底层思想可以延伸出什么基本操作？

中断、异常、系统调用

状态：操作系统在运行过程中有哪些状态？

用户态、内核态

结构：操作系统的结构，和位于计算机哪个位置？

大内核、微内核、用户、应用程序、非内核功能、进程管理、存储管理、设备管理、时钟管理、中断处理、原语、裸机（纯硬件）

第二章 进程管理

2.1进程和线程

进程是什么？

进程的功能有哪些特征实现？

进程的状态有哪些，怎么转换？

进程是怎样控制的？

进程由什么组成？

进程间怎么通信？

线程是什么和进程有什么不一样？

线程有哪些，多线程有哪些？

进程是什么？

实现操作系统的并发性和共享性

进程的功能有哪些特征实现？

动态性、并发性、独立性、异步性、结构性

进程的状态有哪些，怎么转换？

运行态、就绪态、阻塞态、创建态、结束态

运行态可以返回就绪态，时间片结束

进程是怎样控制的？

进程创建（PCB）、进程终止（正常结束、异常结束、外界干预）、进程的阻塞和唤醒（阻塞原语、唤醒原语）、进程切换（内核态下完成）

进程由什么组成，组织方式有哪些？

进程控制块（进程描述信息、进程控制和管理信息、资源分配清单、处理及相关信息）、程序段（CPU执行程序代码段）、数据段（原始数据、中间数据、最终结果）

链接方式（PCB组成的队列）、索引方式（索引表）

进程间怎么通信？

共享存储、信息传递（原语）、管道通信（半双工）

线程是什么和进程有什么不一样？

进程是独立调度的基本单位，线程是支援的基本单位

线程有哪些，多线程有哪些？

用户级线程、内核级线程

多对一（效率高、一堵全堵、不能同时运行在处理机）、一对一（开销大）、多对多（提高并发性，又适当降低开销）

2.2调度

调度是什么，有哪些？

调度的使用时机在哪？

调度的方式有哪些？

调度的基本准则是什么？

加入调度后进程的基本状态变为哪七种？

典型调度算法有哪些？

调度是什么，有哪些？

合理的分配处理机

作业调度（高级调度，一次）、中级调度（内存调度，进出内存）、进程调度（低级调度，选取就绪队列）

调度的使用时机在哪？

不能切换的情况、可以切换的情况

调度的方式有哪些？

非剥夺调度方式、剥夺调度方式

调度的基本准则是什么？

CPU利用率（尽可能忙碌）、系统吞吐量（单位时间内处理的作业数量）、周转时间（作业提交到完成的时间）、等待时间（作业等待处理机的时间）、响应时间（提交到首次响应的时间）

加入调度后进程的基本状态多了什么？

就绪挂起、阻塞挂起

典型调度算法有哪些？

先来先服务（不利于IO繁忙型业务）

短作业优先算法（平均周转时间最短、饥饿）

优先级调度算法（饥饿）

高响应比算法（响应比 =（等待时间+要求服务时间）/ 要求服务时间 = 1 + 等待时间 / 要求服务时间）

时间片轮转法（分时系统）

多级反馈队列调度法（饥饿）

2.3互斥同步

临界资源

同步

互斥

信号量机制

管程

临界资源

只允许一个进程使用

同步

直接制约关系，相互合作

空闲让进、忙则等待、有限等待、让权等待

互斥

间接制约关系，一个访问临界区另一个不能访问

信号量机制

wait：资源-1、signal：资源+1

两个原语

互斥信号量mutex、进入区P（申请资源）、退出区V（释放资源）

管程

模块化

2.4死锁

定义

原因

策略

预防

避免

检测和解除

区别

定义

资源竞争造成的僵局，没有外力作用无法解除

原因和必要条件

资源竞争、顺序非法

互斥条件、不可剥夺条件、请求并保持条件、循环等待条件（你等我我等你）

预防

破坏某一个必要条件

破坏互斥条件（允许共享使用）、破坏不可剥夺条件（导致饥饿）、破坏请求并保持条件（一次申请完它所需要的全部资源）、破坏循环等待条件（顺序资源分配法）

避免

银行家算法（只分配给会进入安全状态的程序）

检测和解除

资源分配图，只要能约掉就不存在死锁。矩形表示资源节点，小圆代表资源数量。

资源剥夺法、撤销进程法、进程回退法

2.5 信号量机制的各种问题应用

生产者消费者问题

多生产者多消费者问题

吸烟者问题

读者-写者问题

哲学家问题

生产者消费者问题

互斥P一定要在同步P之后

否则会导致：我要放东西通过了，没人占用但满了放不进去，去到消费者，通道被生产者占住了，形成死锁
同步：查看缓存区容量和非空区
互斥：消费者和生产者不能同时使用缓存区

多生产者多消费者问题

互斥：前P后V

同步、前驱：前V后P

吸烟者问题

供应者到抽烟者一一对应，多个信号量

抽烟者抽完只有一种返回信号

读者-写者问题

写和读，写和写不能同时访问，但读和读可以同时访问

• 读优先：第一个读者先加两把锁，都关上，再打开互斥锁，让其他读者进行访问
• 写优先（相对优先）：第一个读者先加三把锁，都关上，再打开互斥锁和写优先锁，且先打开写优先锁，使只要读者读完就给写

哲学家问题

SB问题

第三章 内存管理

3.1 内存管理概念

为什么要有内存管理？

内存管理的功能是什么？

程序是怎么装入和链接的？

动态分区分配

分页

分段

为什么要有内存管理？

程序执行前需要先放到内存中才能被CPU处理——缓和CPU与硬盘之间的速度矛盾

内存管理的功能是什么？

内存空间的分配与回收、地址转换、内存空间的扩充、存储保护

分配与回收

连续分配管理方式：单一连续分配（低地址区，单用户、利用率低）、固定分区分配（固定划分相等或不等的区、内部碎片、多道程序、利用率低）、动态分区分配（根据大小建立分区、分区外部碎片、紧凑技术）

非连续分配管理方式：分页、分段

地址转换

绝对装入（单道程序阶段）：无操作系统

可重定位装入（静态重定位）（早期多道批处理阶段）：一次性全部装入，不能在内存中移动）

动态运行时装入（动态重定位）（现代操作系统）：当程序真正执行时才进行转换

地址转换过程：逻辑地址->界地址寄存器->重定位寄存器->物理地址

内存空间的扩充（覆盖、交换、虚拟）

覆盖技术：将用户空间分为一个固定区和若干覆盖区，活跃部分放在固定区，即将访问的段放在覆盖区。

交换技术：把磁盘空间分为文件区和对换区两部分，将处于等待状态的程序从内存中转移到辅存，暂时换出外存。

覆盖与交换区别：覆盖是在同一个程序或进程中的；交换是在==不同进程（或作业）==之间的

内存保护

CPU中设置上、下限寄存器，判断是否越界

重定位寄存器（基址寄存器）和界地址寄存器（限长寄存器）：重定位寄存器中包含最小物理地址值，界地址寄存器包含逻辑地址的最大值

程序是怎么装入和链接的？

步骤：编译（形成若干目标模块）、链接（目标模块与库函数链接）、装入（内存执行）

链接：静态链接（完整可执行）、装入时动态链接（边装入变链接）、运行时动态链接（需要时才链接）

装入：绝对装入（实际内存地址）、可重定位装入（相对地址）、动态运行时装入（需要时才地址转换）

动态分区分配

首次适应算法（不排序第一个）、最佳适应算法（容量递增顺序排列第一个、最多的外部碎片）、最坏适应算法（容量递减第一个、减少小碎片、不利于大工程）、邻近适应算法（上次结束位置查找，概率相同，所以容易把高地址大分区用完）

分页

第一步：分好块，在第几块第几个（页号P和页内偏移量W）

第二部：去问一下我的新家在哪，获得新家块（去页表寄存器看页表起始地址和判断，查页表找到内存块号）

第三步：新家号，在加上偏移量，就算出物理地址（内存块号加页内偏移W得到物理地址）

添加块表，直接省略第二步，因为如果有，直接就能查到内存块号

两级列表解决页表必须连续存储的问题

分段

页是信息的物理单位，完全是系统行为，对用户是不可见的。分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。

段是信息的逻辑单位，分段对用户是可见的，用户编程时需要显式地给出段名。分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。

3.2 虚拟内存管理

虚拟内存管理与传统存储管理的不同在哪？

什么是局部性原理？

虚拟内存是怎样实现的？

有哪些页面置换法？

有哪些页面分配策略？

抖动

工作集

虚拟内存管理与传统存储管理的不同在哪？

传统：作业必须一次性全部装入内存后，才能开始运行，作业装入内存后，一直驻留在内存中，任何部分不会被换出。

虚拟：基于局部性原理，程序的一部分装入内存，一部分留在外存，需要的时候将外存内容调入内存，就好像产生了一个巨大的内存空间

多次性（一次作业多次调入）、对换性（换进换出）、虚拟性（大于实际内存）

什么是局部性原理？

时间局部性

一条指令执行后，不就之后指令可能被再次执行，数据被访问后，不久后数据可能再次被访问

原因：程序中存在着大量的循环操作

时间局部性通过将最近使用的指令和数据存储在高速缓冲存储器中

空间局部性

一旦程序访问了某个存储单元，不久之后附近的存储单元也将被访问

原因：指令通常是顺序存放，顺序执行的，数据一般也是以向量、数组、表等形式簇聚存储的

空间局部性使用较大的高速缓存，将预取机制继承到高速缓存控制逻辑中实现

虚拟内存是怎样实现的？

请求分页存储管理、请求分段存储管理、请求段页式存储管理

一定容量的内存和外存、页表机制（或者段表机制）、中断机制、地址变换机制

有哪些页面置换法？

最佳置换算法（OPT）：选择永不使用或者最长时间内不再访问的页面进行淘汰，但是现实中是无法预知的

先进先出页面置换算法（FIFO ）：优先淘汰最早进入的页面，与进程的实际运行规律不匹配

最近最久未使用（LRU ）置换算法：选择最近最长时间没有被访问的页面进行淘汰，每个页面设置一个访问字段，用来标识上次被访问到现在经历的时间

时钟（CLOCK）置换算法：当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫 描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会 有访问位为0的页面，因此简单的CLOCK 算法选择一个淘汰页面最多会经过两轮扫描）

改进型CLOCK算法：使用位（访问位）的基础上增加修改位

有哪些页面分配策略？

固定分配局部置换

可变分配全局置换

可变分配局部置换

抖动

刚换出的页面又要换入内存

工作集

某段时间内，进程要访问的页面集合。

第四章 文件管理

4.1 文件管理

文件相关概念

文件逻辑结构

目录结构

文件共享

文件保护

文件系统的实现

文件相关概念

数据项、记录、文件

名称、标识符、类型、位置、大小、保护、时间

创建文件、写、读、文件重定位（文件寻址）、删除文件、截断文件

文件逻辑结构

无结构文件：流式文件，字符流组成

有结构文件（记录式文件）：顺序文件（效率高、增删改查难）、索引文件（定长、变长）、索引顺序文件（分组）、直接文件或散列文件（函数转换决定地址）

目录结构

单级目录（不能重名）、两级目录结构（不能分类）、多级目录结构（树形）、无环图目录结构（同一节点有向边，共享）

文件共享

基于索引节点的共享方式（硬链接）：直接指针指向文件，只要还有一个指针，文件（索引节点）就不能删除
利用符合链实现文件共享（软链接）：保存共享文件的路径（快捷方式），根据路径寻找文件。

文件保护

口令保护：用户请求访问时需要提供相应的口令，直接存储在系统内部不安全

加密保护：用户访问需要秘钥解密，加密和解密需要花费一定时间

访问控制：规定每个用户名及其所允许的访问类型

4.2 文件系统的实现

文件层结构

用户调用接口：文件系统为用户提供与文件及目录有关的调用

文件目录系统：管理文件目录，管理活跃文件目录表，管理读写状态信息表，管理用户进程的打开文件表，管理与组织存储设备上的文件目录结构，调用下一级存取控制模块。

存取控制验证：实现文件保护，将用户的访问请求与FCB中指示的访问控制权限进行比较，以确认访问的合法性

逻辑文件系统管理文件信息缓冲区：逻辑文件系统与文件信息缓冲区的主要功能是，根据文件的逻辑结构将用户要读写的逻辑记录转换成文件逻辑结构内的相应块号

物理文件系统:把逻辑记录所在的相对块号转换成实际的物理地址

辅助分配模块：管理辅存空间，负责分配辅存空闲空间和回收辅存空间

设备管理程序模块：分配设备，分配设备读写用缓冲区，磁盘调度，启动设备，处理设备中断，释放设备读写缓冲区，释放设备

目录实现

线性表、哈希表

文件分配方式

连续分配：每个文件在磁盘上占有一组连续的块，磁盘地址定义了磁盘上的一个线性排序。访存1次

链接分配：磁盘块分布在磁盘的任何地方，除最后一个盘块，其他盘块都有指向下一个盘块的指针

索引分配：索引分配解决了链接分配不能直接访问的问题，支持随机访问

文件存储空间管理

文件存储设备管理的实质是对空闲块的组织和管理，包括空闲块的组织、分配与回收等问题

空闲表法

属于连续分配方式，系统为空闲区建立一张空闲盘块表，每个空闲区第一个盘块号，该区的空闲盘块数等信息。

空闲链表法

将所有的空闲盘区拉成一条空闲链，根据构成链所有的基本元素不同，可以把链表分成两种形式

空闲盘块链：将磁盘上所有空闲空间以盘块为单位拉成一条链

空闲盘区链：将磁盘上所有空闲盘区拉成一条链

位示图法

采用二进制的一位来表示一个盘块的使用情况，磁盘上所有的盘块都有一个二进制位与之对应

成组链接法

UNIX使用，结合了空闲表和空闲链表法克服了表太大的缺点

把顺序的n个空闲扇区地址保存在第一个空闲扇区内，其后一个空闲扇区内则保存另一顺序空闲扇区的地址

4.3 磁盘管理

磁盘结构

磁盘、磁道（同心圆）、扇区（数据量相同）、盘面、柱面

磁头是否可移动

固定头磁盘∶磁头相对于盘片的径向方向固定

活动头磁盘：每个磁道一个磁头，磁头可以移动

盘片是否可更换

固定盘磁盘∶磁头臂可以来回伸缩定位磁道，磁盘永久固定在磁盘驱动器内

可换盘磁盘∶可以移动和替换

磁盘调度算法

读写时间组成

寻找时间（寻道时间）TS：在读/写数据前，将磁头移动到指定磁道所花的时间。

①启动磁头臂是需要时间的。假设耗时为s；

②移动磁头也是需要时间的。假设磁头匀速移动，每跨越一个磁道耗时为m，总共需要跨越n条磁道。则：寻道时间TS = s + m*n

延迟时间TR：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。

设磁盘转速为r（单位：转/秒，或转/分），则平均所需的延迟时间TR = （1/2）*（1/r） = 1/2r

传输时间Tt：从磁盘读出或向磁盘写入数据所经历的时间，假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节数为N。则：传输时间Tt = （1/r） * （b/N） = b/（rN）

先来先服务（FCFS）

按照进程请求访问磁盘的先后顺序进行调度

优点：公平实现简单

缺点：适用于少量进程访问，如果进程过多算法更倾向于随机调度

最短寻找时间优先（SSTF）

选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道

优点：性能强于先来先服务算法

缺点：容易产生饥饿现象

扫描算法（SCAN）

在磁头当前移动方向上选择与当前磁头所在的磁道距离最近的请求作为下一次服务对象，只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动，因此也叫电梯算法。

优点：寻道性能好，可以避免饥饿现象

缺点：对最近扫描过的区域不公平，访问局部性方面不如FCFS和SSTF好

循环扫描算法（c-SCAN）

磁头单向移动，回返时直接回到起始端，而不服务任何请求

LOOK与C-LOOK

在SCAN与C-SCAN算法的基础上规定了查看移动方向上是否有请求，如果没有就不会继续向前移动，而是直接改变方向（LOOK）或者直接回到第一个请求处（ C-LOOK）

磁盘管理

磁盘初始化

低级格式化：磁盘分扇区，为每个扇区采用特别的数据结构（头、数据区域、尾部组成），头部含有一些磁盘控制器所使用的信息

进一步格式化处理∶磁盘分区，对物理分区进行逻辑格式化（创建文件管理系统），包括空闲和已分配的空间及一个初始为空的目录

引导块

计算机启动时运行自举程序，初始化CPU寄存器、设备控制器和内存等，然后启动操作系统

组局程序通常保存在ROM中，在ROM中保留很小的自举块，完整的自举程序保存在启动块上拥有启动分区的磁盘称为启动磁盘或系统磁盘

坏块

无法使用的扇区

对于简单的磁盘，可以在逻辑格式化时（建立文件系统时）对整个磁盘进行坏块检查，标明哪些扇区是坏扇区，比如：在FAT表上标明

处理方式

简单磁盘：手动处理，对坏块进行标记，程序不会使用

复杂磁盘：控制器维护一个磁盘坏块链表，同时将一些块作为备用，用于替代坏块（扇区备用）

第五章 输入输出管理(IO)

I/O控制器的主要功能是什么？

I/O有哪些控制方式？

I/O有哪些层次结构？

核心子系统包含哪些？

假脱机

设备的分配与回收

缓冲区管理

I/O控制器的主要功能是什么？

接收和识别CPU发出的命令（要有控制寄存器）、向CPU报告设备的状态（状态寄存器）、数据交换（数据寄存器）、地址识别（由I/O逻辑实现）

I/O有哪些控制方式？

程序直接控制方式

计算机从外部设备读取数据到存储器，每次读一个字的数据，对读入的每个字，CPU都要对外没状态进行循环检查，知道确定该字已经在I设备控制器的数据寄存器中。

读写单位：字

优点：容易实现，操作简单

缺陷∶CPU高速性和IO设备的低速性的矛盾（降低了CPU的利用率），CPU和IO设备只能串行工作

中断驱动方式

允许IO设备主动打断CPU的运行并请求服务，进而解放CPU，使其向IO控制器发送读命令后可以继续做其他有用的工作

读写单位∶字

优点∶比程序直接控制方式有效

缺点：数据的传输必须要经过CPU，仍然后消耗CPU的时间

DMA方式

在IO设备和内存之间开辟直接的数据交换通路，彻底解放CPU

读写单位：数据块

设备直接送入内存

只有当一个或多个数据块开始和结束的时候，CPU才会进行干预

命令/状态寄存器（CR）：用于接收CPU发送的IO命令和有关控制信息或者设备状态

内存地址寄存器（MAR）：数据直接在设备与内存之间交互

数据寄存器（DR）：用于暂存从设备到内存或者从内存到设备的数据

数据计数器（DC） ：存放本次要传送的字（节）数

通道控制方式

设置一个专门负责输入/输出的处理机（DMA方式的发展），实现对一组数块的读写以及相关控制和管理为单位干预

读写单位：一组块

优点：有效的提高了系统资源利用率

缺点：实现较为复杂

DMA与通道的区别

DMA需要CPU来控制传输的数据块大小、传输的内存位置、而通道方式中这些信息是由通道控制的

DMA控制器对应一台设备与内存传递数据，通道可以控制多态设备与内存的数据交换

I/O有哪些层次结构？

用户层IO软件

实现与用户交互的接口，用户可以直接调用在用户层提供的，与IO操作有关的库函数，对设备进行操作

设备独立性软件

用于实现用户程序与设备驱动器的统一接口、设备命令、设备保护、差错控制及设备分配与释放，同时为设备管理与数据传送提供必要的存储空间

设备独立性也称为设备无关性，使得应用程序独立于具体使用的物理设备（使用逻辑设备名）

使用逻辑设备名的好处：增加设备分配的灵活性；易于实现IO重定向

主要功能

执行所有设备的公有操作（设备的分配与回收，逻辑设备名映射为物理设备名，对设备进行保护，进制用户直接访问设备），屏蔽设备之间数据交换的速度差异等

向用户层（文件层）提供统一接口∶无论哪种设备，他们向用户提供的接口都是相同的

设备驱动程序

与硬件直接相关，负责实现系统对设备发出的操作命令，驱动IO设备工作的驱动程序

中断处理程序

用于保存被中断进程的CPU环境，转入相应的中断处理程序进行处理，处理完并恢复被中断进程的现场后，返回被中断进程

硬件设备

IO设备通常包括一个机械部件和一个电子部件

核心子系统包含哪些？

设备独立性软件、设备驱动程序、中断处理程序

主要提供IO调度，缓冲与高速缓存，设备分配与回收，假脱机，设备保护和差错处理

假脱机

输入进程∶模拟脱机输入时的外围控制机，将用户要求的数据从输入机通过输入缓冲区送到输入并中，当CPU需要数据，直接将输出井中的数据送入内存

输出进程：模拟脱机输出时的外围控制机，把用户要求输出的数据先从内存送到输出井中，待输出设备空闲时，再将输出井中的数据经过输出缓冲区送到输出设备

通俗一点就是，如果设备被占用，我们就先把数据暂存一下，等到设备空闲了就把这些数据输送到设备中

设备的分配与回收

―根据用户IO请求分配设备，原则：充分发挥设备的使用效率，避免进程死锁

缓冲区管理

缓和CPU与IO之间的速度差异矛盾

单缓冲、双缓冲、循环缓冲、缓冲池

高速缓存与缓冲区对比

相同点

都介于高速设备和低速设备之间

不同

• 存放数据
  高速缓存：存放的是低速设备上的某些数据的复制数据
  缓冲区：存放的是低速设备传递给高速设备的数据，这些数据在低速设备上不一定有备份，这些数据再从缓冲区传送到高速设备
• 目的
  高速缓存∶高速缓存存放的是高速设备经常要访问的数据，如高速缓存中数据不在，高速设备就要访问低速设备
  高速设备和低速设备的通信都要经过缓冲区，高速设备永远不会去直接访问低速设备