本仓库为操作系统三次课程项目以及期末复习笔记

1.资源分配器：管理分配资源

2.控制程序：控制用户程序和I/O设备的执行

3.内核程序：一直在运行的程序（其他的都是应用程序）

• 方便性（向上）
• 有效性（向下）

1.批处理系统：

• 简单批处理
• 多道程序批处理：充分利用CPU资源，但缺少人机交互性

2.分时系统：粒度变小，提升了作业内部的并发度

3.PC系统

4.并行系统

5.实时系统

由底层硬件、软件技术和上层应用需求的发展而推动的

1.一个设备控制器负责一类设备，每个设备控制器都有自己本地缓冲区

2.CPU负责设备控制器缓冲区与内存间进行数据交换

3.IO设备与CPU可并发执行

4.设备控制器通过中断通知CPU其操作完成

1.同步方式

2.异步方式

1.可编程I/O：占用CPU时间

2.中断机制：中断处理器

3.直接内存存取（DMA）：DMA控制器自动控制成块数据在内存和I/O单元间的传送

4.通道技术：独立于中央处理器，专门负责数据I/O传输的处理机，又称为I/O处理机

1.从上到下依次为：寄存器、高速缓存、主存储器、硬磁盘存储器、磁带等

2.主存：唯一能被CPU直接访问的大型存储媒体

1.所有的I/O指令都是特权指令

2.确保用户程序永远无法以monitor模式获得计算机的控制权

1.基址寄存器

2.界限寄存器

定时器等

• 进程管理
• 主存管理
• 辅存管理
• I/O管理
• 文件管理
• 保护系统
• ...

1.程序执行

2.I/O操作

3.文件系统控制

...

1.系统调用提供了进程与操作系统间的接口

2.通常以汇编语言指令的形式提供

系统调用向操作系统传递参数的方法：

1.通过寄存器来传递参数

2.将参数放在内存的块或表中，并将块的地址作为参数传递给寄存器

3.将参数放在堆栈中，通过操作系统弹出堆栈

1.最粗略划分的OS结构：

• 用户和用户程序
• 外围（系统调用接口）
• 核心

2.稍细的划分和核心单一结构模型：

• 外围：
  • 用户和用户程序
  • 实用程序
  • 命令解释器
• 核心：文件系统、设备管理、CPU管理、内存管理

3.核心层次结构模型：

• 人（用户）
• 应用软件/其他系统软件/操作系统实用程序（使用方式接口、系统文件接口、命令接口）
• 命令解释器（命令方式接口）
• 文件系统（系统调用接口）
• 设备管理
• 内存管理
• CPU管理

其中：文件系统~CPU管理为操作系统核心，内存管理和CPU管理为核心

微内核结构是以微内核为OS核心，以客户/服务器为基础，采用面向对象程序设计特征，是当今最有发展前途的OS结构

• 精心设计的、能实现现代OS核心功能的小型内核
• 不是完整操作系统，只为构建通用OS提供基础
• 提供一些基本功能，如进程管理、存储器管理、进程间通信、低级I/O功能等

1.进程是程序的执行

2.进程执行必须按照一定顺序进行

• PCB
• 程序
• 数据

1.进程是由程序和数据两部分组成的

2.进程有生命周期，程序是相对长久的

3.程序是静态的，进程是动态的

4.进程具有创建其他进程功能，而程序没有

• 并发性
• 动态性：最基本的特征
• 独立性
• 交互性
• 异步性
• 结构性

• 新建状态
• 运行状态
• 等待状态
• 就绪状态
• 终止状态

是进程存在的唯一表示

1.系统把所有PCB组织在一起，并放在内存固定区域，就构成了PCB表

• 链表
• 索引表

2.PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度

1.高级调度：

• 作业调度或宏观调度
• 时间尺寸通常是分钟、小时或天

2.中级调度：

• 涉及进程在内外存间的交换
• 从存储器资源管理的角度来看，把进程部分或全部换出到外存上，可为当前运行进程提供所需内存空间

3.低级调度：

• 也称微观调度
• 从处理机资源分配角度看，处理机需要经常选择就绪进程或线程进入运行状态

1.非剥夺方式

2.剥夺方式

1.进程创建原语create()

2.进程撤销原语exit()

...

1.相交进程和无关进程：

• 相交进程：指多个并发进程在逻辑上有某种联系
• 无关进程：即不相交进程，在逻辑上无任何联系的进程

2.直接作用和间接作用：

• 直接作用：进程间的相互联系是有意识的安排的，只发生在相交进程间（同步、通信）
• 间接作用：进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程间，也可发生在无关进程间（互斥）

并发进程互相共享对方的私有资源而引起的直接制约

• 进程间因竞争共享共有资源而引起的间接制约关系，称为互斥
• 间接是指：各并发进程的速度受公有资源制约，而不是进程间直接制约

1.低级通信：只能传递状态和整数值

• 传送信息量小
• 编程复杂

2.高级通信：能够传送任意数量的数据

• 共享存储区
• 管道
• 消息缓冲

1.通过共享数据结构或者共享存储区进行通信

2.两种实现类型：

• 共享数据结构：效率低，适合传递少量数据
• 共享存储区：高级通信方式，可传输大量数据

1.最广泛的通信机制

2.两种类型：

• 直接通信：如消息缓冲通信方式
• 间接通信：如信箱通信方式

也称共享文件方式，基于文件系统，文件作为缓冲传输介质

• 进程的两个基本特征：
  • 资源分配的独立单位
  • 调度的基本单位
• 将进程资源分配和调度分开，引入线程

1.有时称为轻量级进程

2.进程中的一个运行实体、执行单元、执行体

3.一个CPU调度单位、调度实体

4.可以被内核控制，也可以被用户控制

1.基本上不拥有系统资源，存储所在进程的内存和其他资源

2.只包含一些如程序计数器、寄存器和一组栈

3.TCB：线程控制块

4.不运行时保存上下文

创建一个新线程或者线程创建线程

线程阻塞，处理器调度其他就绪线程

1.进程内多个线程共享地址空间以及大部分数据

2.启动一个线程所花费的空远远小于启动一个进程所花费的时间

3.进程内线程间彼此切换所需的时间远远小于进程间切换所需要的时间

1.不同进程只能通过通信方式进行数据共享，通信方式费时，而且不容易实现

2.同一进程内的线程共享内存和文件，相互通信无需调用内核，线程数据可以直接为其他线程所用

1.优点：

• 线程切换不调用核心
• 调度算法是应用程序特定的算法
• 可运行在任何操作系统上

2.缺点：

• 进程阻塞，进程中所有线程将被阻塞
• 进程内不同线程不能同时运行于不同处理器上

1.优点：

• 对多处理器，核心可同时调度同一进程的多个线程
• 阻塞是在线程一级完成

2.缺点：同一进程内线程切换调用内核，速度下降

• 多对一
• 一对一
• 多对多

调度程序从内存中就绪可执行的进程里选择一个，并为其中之一分配CPU

• 当一个进程从运行状态切换到等待状态
• 当一个进程从运行状态切换到就绪状态
• 当一个进程从等待状态切换到就绪状态
• 当一个进程终止时

1.一个模块，将CPU的控制交由调度程序所选择的进程

2.功能：

• 切换上下文
• 切换到用户模式
• 跳转到用户程序的合适位置以重新启动这个程序

3.分派延迟：分派程序停止一个进程而启动另一个进程执行所要花费的时间

• CPU利用率
• 吞吐量
• 周转时间
• 等待时间
• 响应时间

• 最大CPU利用率
• 最大吞吐量
• 最小周转时间
• 最小等待时间
• 最小响应时间

• 先到先服务调度（FCFS）
• 最短作业优先调度（SJF）：平均等待时间最小
  • 非抢占式
  • 抢占式：最短剩余作业优先（SRTF）
• 优先级调度算法：可能产生饥饿问题
• RR轮转调度算法：
  • 周转时间大于SJF算法
  • 响应时间好于SJF算法
• 多级反馈队列调度算法

• 多个进程并发访问和操作同一数据且执行结果与访问发生的特定顺序有关，称为竞争条件
• 共享数据的并发访问可能导致数据不一致
• 维护数据的一致性需要能够保证协作进程顺利执行的机制

系统中某些资源一次只允许一个进程使用，这样的资源称为临界资源或互斥资源

进程中涉及到临界资源的程序段叫临界区

• 空闲让进
• 无空等待
• 多中择一
• 优先等待
• 让权等待

• 单标志位法
• 双标志位法
• ...

• Test-and-Set指令
• Swap指令
• 开关中断指令

PV操作

掌握第一类读写者问题即可

1.一组阻塞进程分别占有一定的资源并等待另外一些已经被同组其他进程所占有的资源

2.资源竞争，竞争可能产生死锁，但不一定会死锁

• 互斥
• 持有并等待
• 非抢占
• 循环等待

1.如果图不存在环，则不存在死锁

2.如果图包含环，则：

• 如果每种资源类型只有一个实例，则死锁
• 如果每种资源类型存在若干个实例，则只是有可能会发生死锁

当出现死锁四个必要条件，只要确保至少一个必要条件不成立，就能预防死锁发生

通过资源分配图判断

有两个方法：

• 终止进程方法：简单的终止一个或多个进程以打破循环等待
• 资源抢占方法：从一个或多个死锁进程那里抢占一个或多个资源

• 编译：编译程序将用户代码编译成若干个目标模块
• 链接：将编译后形成的一组目标模块，以及所需库函数链接在一起，形成完整装入模块
• 装入：将装入模块装入内存

编译$$\to$$链接$$\to$$装入

• 符号：源程序中
• 可重定位的地址：目标模块
• 绝对地址：内存映像

1.静态链接：在程序运行之前，将各目标模块及所需函数链接成为一个完整的装入模块，以后不再拆开

2.装入时动态链接：在装入内存时，将目标模块变装入边链接

3.运行时动态链接：在程序执行过程中，需要该目标模块时才进行链接

将逻辑空间映射到物理空间

地址再定位技术：

1. 将逻辑空间和物理内存空间对应起来的过程
2. 地址在定位由操作系统中的装入程序来完成

常用程序装入技术：

• 绝对装入技术
• 可重定位装入技术

• 也称为固定地址再定位
• 程序地址再定位在执行之前被确定，也就是在编译链接时直接指定程序在执行时访问的实际存储器地址
• 程序地址空间和内存地址空间是一一对应的

可执行文件中列出各个需要重定位的地址单元和相对地址值，装入时再根据所定位的内存地址去修改每个重定位地址项，添加相应偏移量

两种地址再定位方式：

• 静态再定位：装入程序在程序执行之前进行地址再定位，一旦地址定位完成后，程序执行期间不会发生变化
• 动态再定位：程序在装入内存时，不修改逻辑地址，在访问物理内存之前，再实时将逻辑地址转换成物理地址

1.充分利用内存

2.解决程序空间比实际空间大的问题

3.存储保护与安全

4.方便用户使用

...

• 存储分配和回收
• 存储器扩充
• 存储共享和存储保护

• 连续内存分配方法：
  • 单一连续存储管理
  • 分区存储管理
• 离散内存分配方法
  • 分页存储管理（分配单位是页）
  • 段式存储管理（分配单位是段）
  • 段页式存储管理
• 虚拟存储器

过时了，只能用于单用户、单任务的操作系统

分为两种：固定分区分配和动态分区分配

把内存分为大小相等或不等的分区，每个进程占用一个或几个分区；操作系统占用其中一个分区

• 适用于多道程序系统和分时系统
• 支持多个程序并发执行

• 可能存在内碎片和外碎片
• 难以进行内存分区的共享

分区表：一张全局表，记录有哪些内存块

内存划分为若干个固定大小的连续分区

• 内存利用率提高
• 可以支持多道程序
• 实现简单

• 程序必须预先能估计要占用多大的内存空间
• 内碎片造成浪费
• 分区总数固定，限制了并发执行的程序数目

动态创建分区

没有内碎片，存在外碎片

• 最先适配算法
• 循环最先适配算法
• 最佳适配算法
• 最坏适配算法

存在问题

碎片问题，解决方法：紧凑技术

分区保护问题

• 界限寄存器
• 保护键

借助大容量辅存在逻辑上实现内存扩充，以解决内存容量不足的问题

• 覆盖技术
• 交换技术

1.交换方式：

• 整体交换
  • 交换以整个进程为单位，也称为进程交换
  • 目的是解决内存紧张， 进一步提高内存利用率
• 部分交换
  • 以分页、分段交换为基础，也称为页面交换、分段交换
  • 目的是支持虚拟存储系统

2.优点：

• 增加并发运行的程序数目
• 给用户提供适当的响应时间
• 编写程序时不影响程序结构

3.缺点：换入和换出的控制增加处理机开销

1.划分用户空间：

• 把用户程序按逻辑页划分成大小相等的部分，称为页（虚页）
• 由系统自动完成，一般页大小为2的整数次幂

2.划分内存空间：

• 按页的大小划分为大小相等的区域，称为内存块（物理页面、页框、实页）

3.分配内存：以页为单位进行分配，并按任务页数多少来分配

进程页表

• 系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系
• 页表放在内存，属于进程的现场信息

物理页面表

• 整个系统有一个物理页面表，描述物理内存空间的分配使用状况

请求表

• 整个系统有一个请求表，描述各个进程页表位置和大小，也可结合到各进程PCB里

1. 计算一个任务所需的物理页面块数N
2. 查位示图，看看是否还有N个空闲页面块
3. 如果有足够空闲块，则页表长度设为N，可填入PCB中；申请页表区，把页表始址填入PCB
4. 依次分配N个空闲块，将块号和页号填入页表
5. 修改位示图

多级页表的页目录表中每一项存的是页表的块号！页表的页表项存的是物理地址块号！

• 页表始址寄存器
• 页表长度寄存器
• 联想寄存器——快表
  • 为缩短查找时间，可将页表从内存装入到关联存储器（TLB），按内容查找，即逻辑页号$$\to$$物理页号

• 优点：
  • 解决了碎片问题
  • 便于管理
• 缺点：
  • 不易实现程序共享
  • 不便于动态连接

• 方便编程
• 信息共享
• 信息保护
• 动态增长
• ...

1.划分用户空间：

• 按程序自身逻辑关系划分为若干个程序段
• 每个程序段都有一个段名，且有一个短号
• 段号从0开始，每一段从0开始编址，段内地址是连续的

2.划分内存空间：

• 内存空间被动态的划分为若干个长度不相同的区域，这些区域被称为物理段
• 每个物理段由起始地址和长度确定

3.分配内存：

• 以段为单位分配内存，每一个段在内存中占据连续空间
• 各段之间可以不连续存放

进程段表

• 记录了段号、段的首地址、段长度
• 每一个进程设置一个段表，放在内存，属于进程现场信息

系统段表

• 系统内所有占用段

空闲段表

• 记录空闲段起始地址和长度，可以结合到系统段表中

内存分配算法

首先适配，最佳适配...

• 段表始址寄存器
• 段表长度寄存器
• 联想寄存器

• 优点
  • 便于动态申请内存
  • 管理和使用统一化
  • 便于共享
  • 便于动态链接
• 缺点：产生外碎片

• 进程空间：段式划分
• 内存空间：页式管理
• 页为单位进行分配

• 段表
• 页表
• 空闲块管理同页式管理
• 内存分配同页式管理

1.程序装入时：只需要将当前需要执行的部分页或段读入到内存

2.程序执行中：

• 待执行的指令或访问的数据不在内存（缺页或缺段），则处理器同志操作系统将相应的页或段调入到内存，然后继续执行程序
• 操作系统可将暂不使用的页或段调出保存在外存上，腾出空间存放将要装入的程序以及将要调入的页或段

• 存放大的程序
• 提供大的用户空间
• 更多程序并发执行
• 易于开发

1.不连续性：

• 物理内存分配的不连续性
• 虚拟地址空间使用的不连续性

2.部分交换

3.大空间：提供大范围的虚拟地址空间，其总容量不超过物理内存和外存交换区容量

• 请求页式管理机制
• 请求段式管理机制

• 只在页面需要时，才将其载入内存
• 需要更少的输入输出
• 更小的内存
• 更多的用户

页表结构：

• 采用两级或多级页表
• 为缩短查找时间，多级页表中的每级都可以装入到联想存储器中，并按照Cache原理进行更新

• 先进先出算法（FIFO）
• 最佳算法（OPT）
• 最近最久未使用算法（LRU）
• 最不常用算法（LFU）
• 轮转算法（clock）

1. 请求调页：只调入发生缺页时所需的页面
2. 预调页：发生缺页需要调入某页时，一次调入该页以及相邻的几个页

页面调入来源

• 交换区
  • 进程装入时，将全部页面复制到交换区，以后总是从交换区调入
  • 调入速度快，要求交换区空间大
• 文件区
  • 未被修改的页面，直接从文件去读入，被置换时不需调出
  • 已被修改的页面，被置换时需调出到交换区，以后从交换区调入

1.请求调出：同上

2.预调出

1.虚拟页式管理中给进程分配的物理页面数目

2.确定方式：

• 固定分配
• 可变分配

3.置换范围：

• 局部置换
• 全局置换

4.常驻集大小和置换范围的配合策略：

• 固定分配+局部置换
• 可变分配+局部置换
• 可变分配+全局置换

• 存储信息和检索信息

  • 能够存储大量的信息
  • 长期保存信息
  • 可以共享信息

• 解决方法

  • 文件
  • 文件系统

• 文件

  • 信息以一种单元，即文件形式存储在磁盘或其他外部介质上
  • 文件是一组带标识的、在逻辑上有完整意义的信息项的序列
  • 文件是通过操作系统来管理的，文件内容由文件建立者和使用者解释

• 文件系统

  • 用户观点：文件系统如何呈现在其面前
  • 操作系统观点：文件目录怎样实现、怎样管理存储空间、文件存储位置、磁盘实际运作方式

• 文件系统功能：

  • 是操作系统中统一管理信息资源的一种软件

  • 管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并且方便用户使用

  • 具体来说：统一管理文件的存储空间，实施存储空间的分配与回收

  • 实现文件的按名存取：

    名字空间 $$\to $$映射$$\to$$存储空间

  • 实施文件信息的共享，并提供文件保护和保密措施

  • 向用户提供方便实用的接口

  • 系统维护及向用户提供有关信息

  • 文件系统的执行效率

  • 提供与I/O的统一接口

• 名称
• 类型；由OS和程序定义
• 位置：指向设备和设备上文件位置的指针
• 大小
• 保护
• 时间、日期和用户表示
• ...

• create
• write
• read
• delete
• ...

• 对不同文件进行管理，提高系统效率
• 提高用户界面友好型

• 按信息保存期限分类：临时文件/永久文件/档案文件
• 按文件保护方式分类：只读文件/读写文件/可执行文件
• 按文件性质和拥堵分类：系统文件/用户文件/库文件
• 按文件的逻辑结构分类：流式文件、记录式文件
• 按文件的物理结构分类：顺序文件、链接文件、索引文件

从用户角度研究文件的组织形式：

• 无结构文件
• 有结构文件

1. 无结构文件（流式文件）
   • 构成文件的基本单位是字符，文件是有逻辑无意义的、无结构的一串字符的集合
   • 好处：提供很大的灵活性
2. 有结构文件（记录文件）
   • 文件是由若干个记录组成，是一个固定长度记录的序列，每条记录有其内部结构，每个记录有一个键，可按键进行查找

从系统角度来看文件，从文件在物理介质上的存放方式来研究文件

• 连续（顺序）结构
• 链接结构
• 索引结构

1. 连续结构：文件信息存放在若干连续的物理块中
   • 优点：简单；支持顺序存取和随机存取；顺序存取速度快；所需的磁盘寻道次数和寻道时间最少
   • 缺点：文件不能动态增长；预留空间浪费；重新分配和移动；不利于文件插入和删除；外碎片问题；存储压缩技术
2. 链接结构：
   • 优点：提高了磁盘空间利用率，不存在外碎片问题；有利于文件插入和删除；有利于文件动态扩充
   • 缺点：存取速度慢，不适于随机存取；可靠性问题，如指针出错；更多寻道次数和寻道时间；链接指针占用一定空间
3. 索引结构：
   • 文件信息存放在不连续物理块中，系统为每个文件建立一个专用数据结构——索引表，并将这些块的块号存放在一个索引表中
   • 一个索引表就是磁盘块地址数组，其中第i个条目指向文件第i块
   • 优点：既能顺序存取，又能随机存取；满足了文件动态增长、插入和删除的要求
   • 缺点：较多的寻道次数和寻道时间；索引表本身带来了系统开销

索引表组织

1.链接模式：一个盘块一个索引表，多个索引表链接在一起

2.多级索引：将一个大文件的所有索引表（二级索引）的地址放在另一个索引表（一级索引）中

3.综合模式：

• 每个文件索引表为13个索引项，每项2个字节。最前面10项直接登记存放文件信息的物理块号（直接寻址）
• 如果文件大于10块，则利用第11项指向一个物理块，该块中最多可放256个文件物理块的块号（一次间接寻址）。对于更大的文件还可利用第12和第13项作为二次和三次间接寻址

文件控制块（FCB）

• 文件控制块是操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息（文件属性）
• 文件控制块是文件存在的标志

文件目录

把所有FCB组织在一起，就构成了文件目录，即文件控制块的有序集合

• 目录项：构成文件目录的项目（目录项就是FCB）
• 目录文件：为实现对文件目录的管理，通常将文件目录以文件形式保存在外存，这个文件就叫做目录文件

• 高效性
• 重命名
• 逻辑组
• ...

1. 优点：简单，易实现
2. 缺点：
   • 命名问题
   • 逻辑组

1.目录检索

2.文件寻址

1.目的：加快目录检索

2.方法：采用目录项分解法，把FCB分成两部分

• 符号目录项：文件名，文件号
• 基本目录项：除文件名以外的所有项目

• 空闲块表：所有空闲块记录在一个表中
• 空闲块链表：把所有空闲块链成一个链

• 位示图

• 成组链接法

• 系统文件表：系统打开文件表（整个系统一张）放在内存，用于保存已打开文件的FCB文件号、共享计数、修改标志

• 用户文件表：每个进程一个，进程的PCB中，记录了用户打开文件表的位置

• 提供设置和修改对用户文件存取权限的服务
• 提供建立、修改、改变、删除目录的服务
• 提供文件共享，设置访问路径的服务
• 提供创建、打开、读、写、关闭、撤销文件等服务
• 文件系统维护

• create()
• open()
• read()
• ...

操作系统通常应包括下列五大功能模块：

• 处理器管理。当多个程序同时运行时，解决处理器(CPU)时间的分配问题。
• 作业管理。完成某个独立任务的程序及其所需的数据组成一个作业。作业管理的任务主要是为用户提供一个使用计算机的界面使其方便地运行自己的作业，并对所有进入系统的作业进行调度和控制，尽可能高效地利用整个系统的资源。
• 存储器管理。为各个程序及其使用的数据分配存储空间，并保证它们互不干扰。
• 设备管理。根据用户提出使用设备的请求进行设备分配，同时还能随时接收设备的请求（称为中断），如要求输入信息。
• 文件管理。主要负责文件的存储、检索、共享和保护，为用户提供文件操作的方便。