操作系统

操作系统方法及总结，文件，进程，处理机，处理器，设备，各项管理。

操作系统

• 操作系统概述
  • 操作系统特性
    • 并发性（最重要的特性）
    • 共享性
    • 虚拟性
    • 异步性
  • 操作系统目标：
    • 有效性
    • 方便性
    • 可扩充性
    • 开放性
  • 操作系统的发展
    • 无操作系统的计算机系统
      • 人工操作方式
      • 脱机输入/输出方式
    • 批处理系统（目的：提高系统资源利用率）
      • 单道批处理系统
      • 多道批处理系统
    • 分时系统
      • 多路性（同时性）
      • 独立性
      • 及时性
      • 交互性
    • 实时系统
      • 多路性（同时性）
      • 独立性
      • 及时性
      • 交互性
      • 可靠性
    • 微机操作系统
      • 单用户单任务 MS-DOS
      • 单用户多任务 Windows7等
      • 多用户多任务 Unix和Linux
    • 网络操作系统 Netware
  • 操作系统功能
    • 处理机管理
    • 存储器管理
    • 设备管理
    • 文件管理
    • 操作系统与用户之间的接口
      • 用户接口
        • 联机用户接口：能实现用户与计算机的交互
        • 脱机用户接口：专为批处理作业用户提供，不能实现用户与计算机的交互
      • 程序接口
        • 程序接口是操作系统专门为用户程序设置的，由一组系统调用组成，系统调用是一个能完成特定功能的子程序，是操作系统与应用程序之间的接口，系统调用是用户程序取得操作系统服务的唯一途径
          • 系统调用步骤
            • 传递系统调用参数
            • 执行陷入命令
            • 执行相应的服务程序
            • 返回用户态
  • 操作系统的结构
    • 无结构OS
    • 模块化结构OS（无需模块法，树形结构）
    • 分层式结构操作系统：穿越多个层次，增加了系统的通信开销
    • 微内核操作系统
      • 足够小的内核
      • 基于C/S模式
      • 策略与机制分离
      • 面向对象
• 进程管理
  • 进程
    • 程序段
    • 数据段
    • PCB
      • （进程存在的唯一标志，常驻内存）
      • 描述信息
      • 控制信息
      • 资源管理信息
      • CPU现场保护结构
  • 进程特点
    • 并发
    • 动态
    • 独立
    • 异步
  • 进程控制
    • 创建进程的方式
      • 由系统程序模块统一创建
      • 由父进程创建
    • 引起进程终止的事件
      • 正常结束
      • 异常结束
      • 外界干预
    • 用于进程控制的原语（不允许被中断，在管态下执行，常驻内存）
      • 创建原语
      • 撤消原语
      • 阻塞原语
      • 唤醒原语
  • 进程通信
    • 低级通信
      • 互斥
      • 同步
    • 高级通信
      • 共享存储器系统
        • 共享数据结构（少量数据）
        • 共享存储区（大量数据）
      • 消息传递
        • 直接通信
          • Send原语
          • Receive原语
        • 间接通信
          • 私用信箱
          • 公用信箱
          • 共享信箱
      • 管道通信
        • 管道，是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又称pipe文件。管道是单向的。首创于Unix系统
        • 读进程视管道文件为输入文件，从管道中接收数据
        • 写进程视管道文件为输出文件，以字符流的形式把大量数据送入管道
  • 进程之间的关系
    • 直接制约（同步）：由于进程之间的相互合作引起
    • 间接制约（互斥）：由于进程间共享临界资源引起
  • 进程同步
    • 进程同步应遵循的规则
      • 空闲让进
      • 忙则等待
      • 有限等待
      • 让权等待
    • 进程同步工具
      • 信号量
      • 管程（资源管理模块）
• 处理机调度
  • 分级调度层次
    • 高级调度/作业调度/宏观调度：从外存调入内存
    • 中级调度：存储器管理中的对换，内存管理和扩容
    • 低级调度/进程调度/微观调度
  • 进程调度算法
    • 先来先服务（FCFS，First Come First Served）：有利于长作业，不利于短作业
    • 短作业/进程优先 SJF/SPF
    • 高优先权优先调度算法
      • 静态优先权
      • 动态优先权（高响应比优先HRN Highest Response-ratio Next）
    • 基于时间片的轮转调度
      • 时间片轮转法（RR）
      • 多级反馈队列调度算法
  • 实时调度
    • 分类
      • 非抢占
      • 抢占
        • 基于时钟中断
        • 立即抢占
    • 常用算法
      • 最早截止时间优先：EDF
      • 最低松弛度优先：LLF
  • 死锁
    • 死锁产生的原因
      • 竞争有限资源
      • 进程间推进顺序非法
    • 死锁产生的必要条件
      • 互斥条件（不可破坏）
      • 请求和保持条件（破坏方法：一次性分配/静态分配）
      • 不可剥夺（破坏方法：可剥夺）
      • 环路等待（破坏方法：有序分配资源）
    • 死锁处理
      • 预防
        • 破坏必要条件
      • 避免
        • 银行家算法找安全序列
      • 检测
        • 资源分配图简化
      • 解除
        • 撤销或挂起进程
• 存储器管理
  • 程序装入与重定位
    • 绝对装入：逻辑地址=实际内存地址 地址变换发生在编译时，只适用于单道程序环境
    • 可重定位/静态重定位：地址变换发生在装入时 逻辑地址不等于物理地址，地址变换在装入时一次性完成，不再改变。
    • 动态运行时装入/动态重定位：地址变换发生在程序执行期间（程序地址在执行过程中可以改变）
  • 连续内存分配
    • 单一连续分配：只能用于单用户，单任务的操作系统中
    • 固定分区分配：分区大小可以不等但预先固定不可更改，存在内部碎片
    • 动态分区分配算法（存在外部碎片）
      • 首次适应：地址递增 从头找 查找开销大 留下碎片
      • 循环首次适应：地址递增 从当前位置找 缺乏大空闲区
      • 最佳适应：大小递增 从头找 留下碎片
      • 最坏适应：大小递减 从头找 缺乏大空闲区
    • 可重定位分区分配（动态重定位分区分配）：动态分区分配+拼接/紧凑
  • 分页和分段存储管理（离散内存分配）使系统无需紧凑就能解决碎片问题
    • 60页
    • 分页存储管理
      • 页大小相等，物理块（页框）可以不相邻
      • 逻辑地址连续
      • 需要硬件支持（PTR页表寄存器）
      • 会产生内部碎片，不会产生外部碎片
    • 分段储存管理
      • 段大小不等，每段在一个连续的地址空间，各个段可以离散分布在内存
      • 逻辑地址可以不连续
      • 地址空间是二维的
      • 分段会产生外部碎片，但是分段管理有回收内存机制，可以减少外部碎片
    • 段页式存储管理
      • 需三次访问内存
  • 页面置换算法
    • 最佳置换算法（OPT，Optimal）
    • 先进先出（FIFO）：会出现Belady现象
    • 最近最久未使用（LRU）
    • Clock置换（NRU）
    • 其它
      • LFU（最少使用）
      • PBA（页面缓冲算法）
• 设备管理
  • IO设备类型
    • 按传输速率
      • 低速：键盘鼠标
      • 中速：打印机
      • 高速：磁盘
    • 按信息交换单位
      • 块设备
      • 字符设备
    • 按共享属性
      • 独占设备
      • 共享设备
      • 虚拟设备
  • 设备控制器组成
    • 设备控制器与CPU的接口
    • 设备控制器与设备的接口
    • IO逻辑
  • IO软件层次
    • 用户层软件
    • 设备独立性软件
      • 逻辑设备表LUT：将逻辑设备名称转换为物理设备名称
    • 设备驱动程序
    • 中断处理程序
  • IO控制方式
    • 程序IO（串行）
    • 中断驱动（并行）以字节为单位
    • DMA（并行）以数据块为单位
    • IO通道 （并行） 以一组数据块为单位
      • 字节多路
      • 数组选择
      • 数组多路
  • 中断
    • 基本概念
      • 中断源：引起中断发生的事件
      • 中断请求：中断源向CPU发出的请求中断处理信号
      • 中断响应
    • 分类
      • 中断和陷阱的主要区别如下：①陷阱通常由处理机正在执行的现行指令引起，而中断则是由与现行指令无关的中断源引起的；②陷阱处理程序提供的服务为当前进程所用，而中断处理程序提供的服务则不是为了当前进程的。③CPU在执行完一条指令之后，下一条指令开始之前响应中断，而在一条指令执行中也可以响应陷阱。例如执行指令非法时，尽管被执行的非法指令不能执行结束，但CPU仍可对其进行处理。
      • 外中断（中断）
        • I/O设备发出的I/O中断
        • 外部信号中断
        • 定时器引起的时钟中断
        • 调试程序中设置的断点
      • 内中断（陷阱/异常）
        • 运算错误如：地址非法、校验错误、页面失效、存取访问控制错误、算术操作溢出、数据格式非法、除数为零、非法指令
        • 用户程序执行特权指令
        • 及从用户态到核心态的切换
        • 分时系统中的时间片中断
        • 缺页中断
  • 缓冲（缓冲池在内存）
    • 优点
      • 缓和CPU与I/O设备间速度不匹配的矛盾
      • 减少中断CPU的次数，放宽对中断响应时间的限制
      • 提高CPU和I/O设备之间的并行性
      • 减少磁盘IO次数
    • 分类
      • 单缓冲 Max(T1，T3)+T2
      • 双缓冲 Max(T1，T2，T3)
  • 设备分配
    • 数据结构
      • 设备控制表（DCT） 至少有一张
      • 控制器控制表（COCT）
      • 通道控制表（CHCT）
      • 系统设备表（SDT） 只有一个
    • 设备分配算法
      • 先来先服务
      • 高优先级优先
    • SPOOLing技术（以空间换时间）
      • 提高IO速度
      • 将独占设备改造为共享设备
      • 实现了虚拟设备功能
  • 磁盘管理
    • 磁盘调度
      • 先来先服务（FCFS，First Come First Served）
      • 最短寻道时间优先（SSTF，Shortest Seek Time First）
      • 扫描（SCAN）算法（电梯调度）
      • 循环扫描（CSCAN）算法
    • 磁盘容错技术
      • 第一级容错技术SFT-I 防止因磁盘表面缺陷所造成的数据丢失
      • 第二级容错技术SFT-II 防止由磁盘驱动器和磁盘控制器故障所导致的系统不能正常工作
        • 磁盘镜像：一个磁盘控制器，两个磁盘驱动器
        • 磁盘双工：两个磁盘驱动器，两个磁盘控制器
      • 基于集群技术的容错功能SFT-III
        • 双机热备份模式：一台作为主服务器，另一台作为备份服务器
        • 双机互为备份的模式：两台服务器均为在线服务器
        • 公用磁盘模式：消除了信息的复制时间，因而减少了网络和服务器的开销
• 文件管理
  • 分类
    • 按用途
      • 系统文件：由系统软件构成的文件
      • 用户文件：由用户的源代码、目标文件、可执行文件或数据等所构成的文件
      • 库文件：由标准子例程及常用的例程等所构成的文件
  • 文件的基本操作
    • 创建
    • 删除
    • 读
    • 写
    • 截断
    • 设置读写位置
  • 文件结构
    • 逻辑结构
      • 有结构文件
        • 根据记录的长度
          • 定长记录
          • 变长记录
        • 文件组织方式
          • 索引文件
          • 顺序文件
          • 索引顺序文件
      • 无结构文件（流式文件） 例：目标代码文件，源程序文件
    • 物理结构（存储结构）
      • 顺序结构
      • 链式结构
      • 索引结构
  • 外存分配方式
    • 连续分配：快、需要知道文件长度
    • 链接分配：慢、增删改方便
      • 隐式链接：可靠性差
      • 显式链接：一个磁盘有一张链接表，即文件分配表（FAT）
    • 索引分配
      • 单级索引：对于小文件采用索引分配方式时，其索引块的利用率极低
      • 多级索引
      • 混合索引（Unix）
  • 文件存储空间管理
    • 空闲表：连续分配方式
    • 空闲链表
    • 位示图
    • 成组链接（Unix）
  • 目录管理
    • 文件控制块FCB（存储索引表或索引表的地址）
      • 包含
        • 基本信息
        • 存取控制信息
        • 使用信息
    • 目录结构
      • 单级目录结构
      • 两级目录
        • 用户文件目录UFD
        • 主文件目录MFD
      • 多级目录
  • 文件共享
    • 基于索引节点的共享方式：文件主无法删除被他人共享的文件
    • 利用符号链实现文件共享：删除原文件，链接文件不会被删除，只是失效
  • 文件安全管理
    • （1）系统级：用户需注册登记并配有口令，每次使用系统时，都需要进行登录，然后输入用户口令，方能进入系统
    • （2）用户级：系统对用户分类并限定各类用户对目录和文件的访问权限。
    • （3）目录级：系统对目录的操作权限加以限定，如读（R）、写（W）、查看（X）等。
    • （4）文件级：系统设置文件属性来控制用户对文件的访问，通常可设置的属性有：执行、隐藏、只读、读写、共享、系统。
• Unix
  • Unix和Linux是多用户多任务操作系统
  • Unix系统采用文件名和文件说明信息分离开的办法，文件说明信息形成索引结点（i结点），目录中的每个目录项仅由文件名和对应的i结点的指针所构成，这样，每个盘块能存放的目录项数量增加可加快对文件目录的查找
  • 混合索引外存分配方式已在Unix系统中采用
  • 在Unix系统中，所有输入输出设备都被看作特殊文件
  • 在Unix系统中，所有的文件都被看作是流式文件。
  • 在Unix系统中采用的是成组链接法进行文件存储空间管理
    • Linux用位示图
  • 软中断的概念主要来源于Unix系统
  • 管道通信方式首创于Unix系统
  • Unix、Linux 和Windows都采用了多级目录结构