操作系统原理

• 操作系统
• • 计算机系统概述
  • • os特征
    • 不同时期的发展
    • 操作系统提供的接口
    • CPU状态
    • 操作系统内核
    • 系统调用
    • 体系结构
  • 进程管理
  • • 进程
    • 线程
    • 调度
    • 进程同步
    • 管理
    • 死锁
  • 内存管理
  • • 功能
    • 装入模块放入内存的方式
    • 内存保护的两种方法
    • 扩展内存
    • 管理内存的方式
  • 文件管理
  • • 文件
    • 目录结构
    • 文件共享
    • 文件保护
    • 文件系统层次结构
    • 目录实现
    • 文件分配方式
    • 文件存储空间管理
    • 磁盘
  • IO设备管理
  • • 分类
    • IO控制方式
    • IO子系统层次结构
    • IO管理内容
    • IO核心子系统

操作系统

计算机系统概述

os特征

• 并发

  • 同一时间里运行程序1和程序2…

• 共享

  • 互斥共享
  • 属性访问

• 虚拟

  • 空间复用技术-扩展内存
  • 时分复用技术-多个cpu

• 异步

  • 备进程向前推进的速度不相同

不同时期的发展

• 手工阶段

  • 用户独占全机，资源利用率低

• 单通道批处理系统

  • 各作业一次运行，无需人工

• 多道批处理

  • 资源利用率高，不提供人机交互功能

• 分时操作系统

  • 采用时间片方式，可人机交互

• 实时操作系统

  • 及时可靠

• 络操作系统

  • 络中的各种资源的共享及各台计算机通信

• 分布式操作系统

  • 分布性、并行性

• 个人计算机

操作系统提供的接口

• 命令接口

• 联机控制方式

  • 类似cmd命令窗口

• 脱机控制方式

  • 日常的编程

• 程序接口

  • 比如GUI

CPU状态

• 分类

  • 核心态
  • 用户态

• 用户态 –>核心态

  • 中断
  • 异常
  • 访管指令

操作系统内核

• 时钟管理

  • 计时
  • 进程切换（时间片轮转调度）

• 中断机制

• 原语

  • 比如设备驱动控制，cpu切换

• 系统中的数据结构及处理

  • 进程管理
  • 存储管理
  • 设备管理

系统调用

• 设备管理
• 文件管理
• 进程控制
• 进程通信
• 内存管理

体系结构

• 大内核体系结构
• 微内核体系结构

进程管理

进程

• 进程

  • 概念

    • 形象理解为程序的一次实验
    • 处理机分配资源的单位

  • 组成

    • 程序段

    • 数据段

    • PCB

      • 进程描述信息
      • 进程控制和管理信息
      • 资源分配清单
      • 处理机相关信息

  • 特征

    • 动态性

    • 并发性

      • 多个进程实体时存在于内存中

    • 独立性

      • 独立获得资源和独立接受调度的基本单位

    • 异步性

      • 进程之间互相制约使得进程具有执行的间断性

    • 结构性

  • 状态

    • 运行态
    • 就绪态
    • 阻塞态（等待态）

• 进程控制

  • 进程创建
  • 进程终止
  • 进程的阻塞和唤醒（阻塞为主动行为）
  • 进程切换

• 进程的通信

  • 共享存储

    • 采用同步互斥工具PV

      • 基于数据结构的共享
      • 基于存储区的共享

  • 消息传递（借助消息缓冲区）

    • 直接通信方式
    • 间接通信方式

  • 管道通信（半双工）

    • 管道是固定大小的缓冲区
    • 一边写，一边读没有问题

• 进程运行步骤

  • 编译

    • 由编译程序将用户源代码编译成若干目标模块

  • 链接

    • 由链接程序将编译后的目标模块及所需的库函数链接在一起形成一个完成的装入模块

    • 链接方式

      • 静态链接
      • 装入时动态链接
      • 运行时动态链接

    • 装入

      • 由装入程序将程序装入模块装入内存中运行

线程

• 特点

  • 不拥有系统资源，共享线程资源

  • 状态

    • 就绪
    • 阻塞
    • 运行

  • 处理机的独立调度单位

• 实现方式

  • 用户级线程
  • 内核级线程

• 引入目的

  • 增加多道程序并发展
  • 提高资源利用率和系统吞吐量
  • 增加程序的并发性

调度

• 调度的层次

  • 高级调度（作业调度）

    • 从外存中调入作业，分配给他们内存 ，必要资源，建立进程

  • 中级调度（内存调度）

    • 堵塞态 –> 挂起态 or 挂起态 –> 堵塞态

  • 低级调度（进程调度）

    • 分配处理机

• 调度的方式

  • 非剥夺式调度
  • 剥夺式调度

• 评价指标

  • CPU利用率
  • 系统吞吐量（单位时间CPU完成作业的数量）
  • 周转时间（从作业提交到完成）
  • 响应时间

• 调度算法

  • 先来先服务FCFS

    • 效率低
    • 不利于短作业
    • 适合CPU繁忙型，不适合I/O繁忙型作业

  • 短作业优先算法SJF

    • 饥饿发生
    • 未考虑作业的紧迫程度
    • 平均等待时间短

  • 优先级调度算法

    • 分类

      • 剥夺式优先调度算法
      • 非剥夺式优先调度算法

    • 原则

      • 系统进程 > 非交互型进程
      • 交互型进程 > 非交互型进程
      • IO型进程 > 计算型进程

  • 高响应比调度算法

    • 计算公式：响应比 = （等待时间 + 执行时间）/ 执行时间
    • 克服饥饿

  • 时间片轮算法（分时系统）

    • 时间片的长短确定

      • 系统响应时间
      • 就绪队列进程数目
      • 系统的处理能力

  • 多级反馈队列调度算法

进程同步

• 临界

  • 临界资源
  • 临界区

• 同步（直接制约关系）

  • 信 量实现同步

• 互斥（间接制约关系）

  • 实现方式

    • 软件

      • 单标志法

        • 违背空闲让进原则

      • 双标志先检查法

        • 违背忙则让进原则

      • 双标志后检查法

        • 产生饥饿现象

      • Peterson’s Algorithm

        • flag 解决临界资源的互斥访问
        • turn 解决饥饿现象

    • 硬件

      • 中断屏蔽方法

        • 方法

        • 特点

          • 限制了CPU交替执行的能力
          • 用户能力变大，居然能控制中断

      • 硬件指令方法

        • TestAndSet指令

          • 读出指定标志后设其为true
          • true表示被占有
          • 初值为false，空闲

        • Swap指令

          • 交换两个字节内容
          • 设置局部变量key

    • 信 量实现互斥

      • 整型信 量

        • 存在忙等

        • 操作

          • wait（占有资源）P操作
          • signal（释放资源）V操作

      • 记录型信 量

        • 操作

          • 资源数目value
          • 进程链表L（链接所有等待该资源的进程）

  • 进程互斥

    • 信 量实现

  • 经典同步问题（统一把P理解为消耗，V理解为释放）

    • 产生者-消费者问题
    • 写者读者问题
    • 哲学家问题
    • 吸烟者问题

管理

• 组成

  • 名称
  • 局部于管理内部的共享结构数据说明
  • 对该数据结构进行操作的一组过程（或函数）
  • 共享数据设置初始值

• 条件变量（进程阻塞的原因）

  • 操作

    • wait（正在调用管理程序的进程wait插入等待队列，释放管理）
    • signal（唤醒一个区x条件而阻塞的进程）

死锁

• 定义

  • 多个进程因竞争资源而造成的一种僵局

• 产生条件

  • 互斥条件

    • 排他性控制

  • 不剥夺条件

    • 该资源只能由本进程释放

  • 请求并保持条件

    • 进程已经保持一个资源，但提出新的资源请求

  • 循环等待条件

• 处理策略

  • 死锁预防

    • 闲置资源

  • 避免死锁

    • 寻找安全序列
    • 银行家算法

  • 死锁的检查

    • 定期检查，剥夺资源
    • 资源分配+死锁定理

  • 死锁的解除办法

    • 资源剥夺方法
    • 撤销进程法
    • 进程回退法

内存管理

功能

• 内存空间的分配与回收

• 地址转换

  • 逻辑地址到物理地址的转换

• 内存空间的扩充

  • 虚拟内存的应用

• 存储保护

  • 防止内存地址越界

装入模块放入内存的方式

• 绝对装入

  • 适合单道程序

• 可重定位装入

  • 静态重定位，适合多道程序

• 动态运行时装入

  • 动态重定位

内存保护的两种方法

• 在CPU中设置一对上下寄存器
• 采用重定位寄存器 + 界地址寄存器

扩展内存

• 多道程序环境下

  • 覆盖

    • 用户空间分为

      • 固定区
      • 若干覆盖区

  • 交换

    • 中级调度技术

• 虚拟内存管理

  • 局部性原理

    • 空间局部性
    • 时间局部性

  • 特征

    • 多次性
    • 对换性
    • 虚拟性

  • 管理内存的方式

    • 请求分页管理方式

      • 新增功能

        • 请求调页功能

        • 页面置换功能

          • 算法

            • 最佳置换算法
            • 先进先出算法
            • 最近最久未使用算法
            • 时钟置换算法
            • 改进时钟算法

        • 页面分配策略

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

        • 调入页面时机

          • 预调页面策略
          • 请求调页策略

      • 异常

        • 抖动

    • 请求分段存储方式

    • 请求段页式管理方式

  • 最大

    • 不超过计算机的地址位数

管理内存的方式

• 连续

  • 单一连续分配

  • 固定连续分配

    • 产生内部碎片
    • 无外部碎片

  • 动态连续分配

    • 产生外部碎片

    • 分配算法

      • 首次适应
      • 最佳适应
      • 最坏适应
      • 邻近适应算法

• 离散

  • 分页存储管理方式

    • 基本分页式存储管理方式

      • 单极分页

        • 类似固定分区技术，产生内部碎片
        • 逻辑结构分页 + 页内偏移量
        • 引入块表，加速地址变量

      • 二级分页

  • 分段存储管理方式

    • 基本分段式存储管理方式

      • 分段管理的地址空间是二段的

  • 段页式存储管理方式

文件管理

文件

• 分类

  • 流式文件

    • 无文件结构

  • 记录式文件

    • 一组相似的记录

      • 顺序文件
      • 索引文件
      • 索引顺序文件
      • 散列文件

• 基本操作

  • 创建文件

    • 分配空间
    • 在目录中记录该文件

  • 写文件

    • 分配指针

  • 读文件

  • 文件寻址

  • 删除文件

• 打开文件的关联信息

  • 文件指针
  • 文件打开技术
  • 文件磁盘位置
  • 访问权限

目录结构

• 数据结构

  • 文件控制块
  • 索引节点

• 操作

  • 搜索
  • 创建文件
  • 删除文件
  • 显示目录
  • 修改目录

• 结构

  • 单级目录结构
  • 两级目录结构
  • 多级目录结构（树形目录结构）
  • 无环图目录结构

文件共享

• 基于索引节点的共享方式（硬链接）

  • 链接到多个目录中

• 利用符 链实现文件共享（软链接）

  • 只存放路径link

文件保护

• 访问类型

  • 读
  • 写
  • 执行
  • 添加

• 访问控制

  • 控制用户身份

• 口令密码

文件系统层次结构

• 用户调用接口
• 文件目录系统
• 存取控制验证模块
• 逻辑文件系统与文件信息缓冲区
• 物理文件系统
• 设备管理程序模块

目录实现

• 线性列表
• 哈希表

文件分配方式

• 连续分配
• 链接分配
• 索引分配

文件存储空间管理

• 初始化

  • 目录区
  • 文件区

• 管理方法

  • 空闲表法
  • 空闲链表法
  • 位式图法

磁盘

• 磁盘地址

  • 柱面 * 盘面 * 扇区

• 读写操作时间

  • 寻道时间
  • 延迟时间
  • 传输时间

• 调度算法

  • 先来先服务
  • 最短寻道时间优先算法
  • 扫描算法/电梯算法
  • 循环扫描算法

• 磁盘管理

  • 磁盘初始化
  • 引导块
  • 坏块

IO设备管理

分类

• 块设备

  • eg：键盘

• 字符设备

  • eg：打印机

IO控制方式

• 程序直接控制

  • CPU资源浪费

• 中断驱动方式

• DMA方式

• 通道控制方式

IO子系统层次结构

• 用户层IO软件
• 设备独立性软件
• 设备驱动程序
• 中断处理程序
• 硬件设备

IO管理内容

• 状态跟踪
• 设备存取
• 设备分配
• 设备控制

IO核心子系统

• 服务

  • IO调度
  • 缓冲与高速缓存
  • 设备分配与回收
  • 假脱机
  • 设备保护与差错处理

• 高速缓存 + 缓冲区

  • 高速缓存

  • 缓冲区

    • 单缓冲
    • 双缓冲
    • 循环缓冲
    • 缓冲池

• 设备分配时数据结构

  • 设备控制表DCT
  • 控制器控制表COCT
  • 通道控制表CHCT
  • 系统设备表SDT

• SPOOling技术

  • 组成

    • 输入井输出井

      • 磁盘中

    • 输入缓冲区和输出缓冲区

      • 内存中

    • 输入进程和输出缓进程