技术/笔记/操作系统原理课程笔记
技术 / 笔记27 分钟 读完 (大约 4095 个字)

技术/笔记/操作系统原理课程笔记

OS 课程笔记

第一章 绪论

操作系统的定义

操作系统是一个大型的程序系统，它负责计算机系统软、硬件资源的分配；控制和协调并发活动；提供用户接口，使用户获得良好的工作环境。

操作系统的特征

  • 并发
  • 共享
  • 不确定性

多道程序设计技术

  • 定义

    • 在计算机主存中同时存放几道相互独立的程序。这些程序在管理程序控制之下，相互穿插地运行。当某道程序因某种原因不能继续运行下去时(如等待外部设备传输数据)，管理程序便将另一道程序投入运行。

  • 特征

    • 多道
    • 微观上串行
    • 宏观上并行

  • 应用

    • 批处理操作系统（系统吞吐率高：脱机操作 、多道运行、 合理搭配作业；作业周转时间长，用户使用不方便）

  • 依赖

    • 通道技术和中断技术

  • 多道程序工作示例

多道程序工作示例

分时技术

  • 定义
    • 所谓分时技术，是把处理机时间划分成很短的时间片(如几百毫秒)轮转地分配给各个应用程序使用，如果某个程序在分配的时间片用完之前计算还未完成，该程序就暂时中断，等待下一轮继续计算。
  • 应用
    • 分时操作系统（独占性、并行性、交互性）

第二章 结构与硬件支持

处理机的态

  • 定义

    • 处理机的态，又称为处理机的特权级，是中央处理机的工作状态。当前处理机正在执行哪类程序，决定处理机的态。

  • 分类

    • 核态：操作系统的管理程序执行时机器所处的状态，又称处理机的特权级。在此状态下处理机可使用全部指令(包括一组特权指令)；使用全部系统资源(包括整个存储区域)。
    • 管态：管态比核态的权限低，在此状态下允许使用一些用户态下不能使用的资源，但不能使用修改CPU状态的指令。无核态时，管态执行核态的全部功能。
    • 用户态（目态）：用户程序执行时机器所处的状态称为用户态。在此状态下禁止使用特权指令，不能直接取用资源与改变机器状态，并且只允许用户程序访问自己的存储区域。
    管态 用户态
    操作系统的程序执行 用户程序执行
    使用全部指令 禁止使用特权指令
    使用全部系统资源 只允许用户程序
    整个存储区域 访问自己的存储区域

  • 特权指令集

    ① 涉及外部设备的输入/输出指令

    ② **修改特殊寄存器的指令：**存取用于主存保护的寄存器等

    ③ **改变机器状态的指令:**开/关中断、进程切换、停机指令等

  • 状态切换

① 用户态到管态

  1. 管理程序调用

  2. 中断

  3. 用户进程产生错误（内部中断）

  4. 用户程序企图执行特权指令

② 管态到用户态

​ 从核态转回用户态用一条指令实现，这条指令也是特权指令。一般情况下是中断返回指令。

中断

  • 概念
    • 所谓中断是指某个事件 (例如电源掉电、定点加法溢出或I/O传输结束等) 发生时，系统中止现行程序的运行、引出处理事件程序对该事件进行处理，处理完毕后返回断点继续执行的过程。
  • 按中断源分类

① 中断： 由处理机外部事件引起的中断，包括输入输出中断、外中断。（x86中称为异步中断）

② 俘获： 由处理机内部事件引起的中断，包括访管中断、程序性中断、机器故障中断。（x86中称为异常）

优先级：俘获 > 中断

第三章 用户接口

  • 命令接口

    • 操作命令

  • 程序接口

    • 系统功能调用

  • 系统调用与库函数

    • 系统调用代码属于OS，库函数由软件开发商提供，由编译工具链入用户程序
    • 系统调用代码的执行引起CPU状态的变化：用户态 => 核心态
    • 库函数的执行不会引起CPU状态的变化：用户态
    • 系统调用封装成库函数

  • 访管中断

    • 当处理机执行到访管指令时发生中断，该中断称为访管中断，它表示正在运行的程序对操作系统的某种需求。

第四章 进程管理

并发程序

  • 定义
    • 若干个程序段同时在系统中运行，这些程序段的执行在时间上是重叠的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重叠是很小的一部分，也称这几个程序段是并发执行的。
  • 并行记号
1
2
3
4
/*表示S1,S2,....Sn这n个语句是可以并发执行的*/
cobegin
	S1;S2;...;Sn;
coend
  • 先后次序图

  1. 对n个用户作业的处理

    1
    2
    3
    4
    作业1：  I1   C1   P1
    作业2：  I2   C2   P2
    		...
    作业n：  In   Cn   Pn
多用户系统中操作的先后次序图

  1. 誊抄 (g: get, c: copy, p: put)

    三个并发程序誊抄方案 誊抄先后次序图
  • 特点
    • 失去了程序的封闭性和可再现性
    • 程序与计算不再一一对应
    • 程序并发执行的相对制约

进程

  • 定义

    • 进程，即是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。

  • 进程与程序的区别
    ① 程序是静态的概念，进程是动态的概念；
    ② 进程是一个独立运行的活动单位；
    ③ 进程是竞争系统资源的基本单位；
    ④ 一个程序可以对应多个进程，一个进程至少包含一个程序

进程变迁

  • 状态：就绪、等待、运行

  • 状态变迁

    • 变迁原因

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      就绪 --> 运行
         	调度程序选择一个新的进程运行
         	
      运行 --> 就绪
      	运行进程用完了时间片
      	运行进程被中断，因为一高优先级进程处于就绪状态 
      	
      运行 --> 等待
       	当一进程必须等待时
      	OS尚未完成服务
      	对一资源的访问尚不能进行
      	初始化I/O 且必须等待结果
      	
      等待 --> 就绪
      	当所等待的事件发生时

    • 因果变迁

      因果变迁

进程描述

  • 进程控制块 PCB
    • 定义：描述进程与其他进程、系统资源的关系以及进程在各个不同时期所处的状态的数据结构
    • 作用：进程与PCB是一一对应的，系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志
  • 进程的组成
    • 程序和数据
    • PCB

进程控制

  • 控制原语
    • 创建、撤销、阻塞（等待）、唤醒

互斥与同步机制

  • 临界资源、临界区

    • 一次仅允许一个进程使用的资源称为临界资源；硬件：如输入机、打印机、磁带机等；软件：如公用变量、数据、表格、队列等
    • 进程中对公共变量 (或存储区)进行审查与修改的程序段，称为相对于该公共变量的临界区。
    • 准则
    1
    2
    3
    4
    5
    有空让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入。
    无空等待：不允许两个以上的进程同时进入互斥区。
    多中择一：当没有进程在临界区，而同时有多个进程要求进入临界区，只能让其中之一进入临界区，其他进程必须等待。
    有限等待：任何进入互斥区的要求应在有限时间内得到满足。
    让权等待：当进程不能进入临界区时，应立即释放CPU，避免进程忙等待。

  • 上锁原语、开锁原语 (0为无锁，1为上锁)

  • P、V 操作原语

  • 进程流图

    • 示例
    进程流图示例

  • 两类同步问题解决方案

    • 一般的合作问题：画进程流图，对pi设置si信号灯表示pi是否可以开始
    • 共享缓冲区的合作问题（生产者-消费者问题）：设置有界缓冲区互斥锁、满个数、空个数三个信号灯

进程通信

  • P、V 原语：简单的同步信号通讯

  • 共享内存

  • 消息通信

  • 管道

  • socket: 不同（相同）主机间进程通信

线程

第五章 资源分配与调度

数据结构

  • 资源信息块结构（后面几章中的处理及资源信息块、主存资源信息块、设备资源信息块等都类似这种结构）

分配策略

  • 先请求先服务
  • 优先调度

死锁

  • 产生死锁的必要条件

    ① 互斥条件

    涉及的资源是非共享的，即为临界资源。

    ② 不剥夺条件

    进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走。

    ③ 部分分配

    进程每次申请它所需要的一部分资源。在等待一新资源的同时，进程继续占用已分配到的资源。

    ④ 环路条件

    存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中下一个进程所请求。

  • 死锁定理

    • 如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁。
    • 如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件。

  • 预防死锁

    • 静态预防：在作业调度时为选中的作业分配它所需要的所有资源，当资源一旦分配给该作业后，在其整个运行期间这些资源为它独占。
    • 动态预防
      • 有序资源分配法（破坏环路条件）：给不同类的资源编号，进程必须按照编号升序请求资源，且申请同一类资源时必须一次申请完
      • 银行家算法：申请者事先说明对各类资源的最大需求量。在进程活动期间动态申请某类资源时，由系统审查现有该类资源的数目是否能满足当前进程的最大需求量，如能满足就予以分配，否则拒绝。
      • 安全序列的定义：指系统能按某种进程推进顺序（Pi1，Pi2，。。。Pin）为每个进程分配其所需的资源，直至每个并发进程都能达到获得最大资源而顺序完成，此时称(Pi1，Pi2，。。。Pin）为安全序列。
      • 能找到安全序列的状态为安全状态。

第六章 处理机调度

  • 作业调度算法
    • 先来先服务
    • 短作业优先
    • 响应比高者优先
      • 响应比=响应时间/计算时间=1+等待时间/计算时间\text{响应比} = \text{响应时间} / \text{计算时间} = 1 + \text{等待时间} / \text{计算时间}
    • 优先数
  • 进程调度算法
    • 调度方式：剥夺、非剥夺
    • 优先数调度算法
      • 静态优先数
      • 动态优先数
    • 循环轮转调度算法
      • 简单循环轮转
      • 可变时间片循环轮转
      • 多重时间片循环轮转
  • 调度用的进程状态变迁图
    • 调度效果：优先照顾IO量大的进程；适当照顾计算量大的进程。
调度用的进程状态变迁图示例

第七章 主存管理

基本概念

  • 虚实分离

    • 逻辑地址、程序地址空间
    • 物理地址、主存空间

  • 地址映射

    • 静态地址映射（编译/装入时映射）
    • 动态地址映射（运行时）

  • 存储保护

    • 上下界法
    • 基地址-限长法

分区存储管理

  • 分区分配数据结构
主存资源信息块和分区描述器 空闲区队列结构
  • 放置策略 （选择空闲区的策略）
    • 首次适应算法 （空闲区队列按地址由低到高排列）
    • 最佳适应算法 （空闲区队列按大小由小到大排列）
    • 最坏适应算法 （空闲区队列按大小由大到小排列）

页式存储管理

  • 页式地址变换
  • 请调策略
    • 扩充页表功能 —— 中断位 辅存地址
    • 缺页处理
  • 淘汰策略
    • 扩充页表功能 —— 引用位 改变位
    • 抖动
    • 置换算法
      • 先进先出算法
      • 最久未使用 LRU 算法 （计数法、多位寄存器法、栈方法）
      • LRU 近似算法 （时钟）

第八章 设备管理

  • 设备独立性
    • 所谓设备独立性是指，用户在程序中使用的设备与实际使用的设备无关，也就是在用户程序中仅使用逻辑设备名。
  • 缓冲技术
    • 双缓冲、环形缓冲、缓冲池
  • 磁盘调度算法
    • 先来先服务 FCFS
    • 最短寻道优先 SSTF
    • 扫描算法 SCAN
    • 循环扫描算法 CSCAN
  • 设备分配
    • 独享分配
    • 共享分配
    • 虚拟分配
    • Spooling 系统
      • 利用通道和中断技术，在主机控制之下，由通道完成输入输出工作。系统提供一个软件系统 (包括预输入程序、缓输出程序、井管理程序、预输入表、缓输出表)。它提供输入收存和输出发送的功能，使外部设备可以并行操作。这一软件系统称为SPOOLING系统

第九章 文件系统

文件的逻辑结构

  • 流式文件
    • 流式文件是相关的有序字符的集合，是无结构的。流式文件是按信息的个数或以特殊字符为界进行存取的。
  • 记录式文件
    • 记录式文件是一种有结构的文件。这种文件在逻辑上总是被看成一组连续顺序的记录的集合。
    • 按照每个记录长度是否固定分为：定长记录、变长记录

文件的物理结构

  • 连续文件

    连续文件结构

  • 串联文件

串联文件物理结构

  • FAT 文件 （采用文件分配表，将串联文件中的勾链字集中在一起存放，通常从磁盘第二个扇区开始存放）

    • FATX 中的 X 表示一个块号（簇号）占多少位
    • 以FAT16为例，勾链字0000H表示空闲块，FFFFH表示结尾
    FAT 文件物理结构

  • 索引文件

    • 多级索引
      • 直接索引
      • 一级、二级、三级间接索引
    • Unix 系统的 i 结点
索引文件物理结构

默认情况下一个磁盘块的大小为 512 Byte，一个块号占据 2 Byte

  • Unix 7

    • i_addr[8]
    • 小型文件 i_addr[0...7] 直接索引，8×512B8 \times 512B
    • 大型文件 i_addr[0...6] 一级间接索引，i_addr[7] 空置，7×256×256B7 \times 256 \times 256B
    • 巨型文件 i_addr[0...6] 一级间接索引，i_addr[7] 二级间接索引，(7×256+2562)×512B(7\times256 + 256^2 )\times512B

  • Unix System V

    • i_addr[13]
    • i_addr[0...9] 直接索引
    • i_addr[10] 一级间接索引
    • i_addr[11] 二级间接索引
    • i_addr[12] 三级间接索引

  • 空闲块管理之成组链接法

    • 结构：s_nfree 为空闲块数，s_free为空闲块号数组（大小为100），s_free[0] 比较特殊因为它不仅仅是某个空闲块号而且它所指向的空闲块又是一个空闲块索引表
    成组链接结构
    • 分配-释放算法
    成组链接算法

文件目录

  • 一级文件目录

  • 树型文件目录

  • 硬链接和软链接

#

喜欢这篇文章？打赏一下作者吧

×