文章目录

• 一、操作系统概论
• • 概念
  • • 1、操作系统
    • 2、操作系统特征
    • • 1)并发性
      • 2)共享性
      • 3）虚拟：
      • 4）异步性
    • 3、研究操作系统的观点:
    • 4、操作系统的功能
    • • 1)进程管理(处理器管理)
      • 2)存储管理
      • 3)文件管理
      • 4)设备管理
      • 5）提供用户接口
  • 操作系统的体系结构
  • • 1、体系结构：
    • • (1)Windows操作系统的体系结构。
      • (2)UNIX操作系统的体系结构。
      • (3)Linux操作系统的体系结构。
      • (4)Android 操作系统的体系结构。
  • 操作系统的发展
  • 操作系统分类
  • 操作系统设计
  • • 1、在操作系统设计的过程中主要困难
    • 2、操作系统的设计过程
    • • (1)功能设计。
      • (2)算法设计。
      • (3)结构设计。
    • 3、操作系统的设计目标
    • 4、操作系统结构研究的目标:
    • 5、操作系统的结构:
    • • (1)整体式结构。
      • (2)层次式结构。
      • (3)微内核(客户/服务器)结构。
• 二、操作系统运行环境
• • 处理器
  • • 1 处理器内寄存器
    • 2 指令
    • • 1、指令执行的基本过程:
      • 2、指令的五类
      • • 1）访问存储器指令
        • 2）I/O指令
        • 3）算术逻辑指令（数据处理指令）
      • 4）控制转移指令
      • • 5）处理器控制指令
      • 3、特权指令和非特权指令
      • • 1）特权指令
        • 2）非特权指令
    • 3 管态和目态
    • • • 1）管态
        • 2）目态
    • 4 处理器工作状态的转换
    • • • 1）目态到管态的转换
        • 2）管态到目态的转换
  • 计算机系统硬件部件
  • • 1、存储器的类型
    • • 1）读写型的存储器
      • 2）只读型的存储器
    • 2、存储器的层次结构
    • 4、I/O结构
    • 5、DMA技术（直接内存访问（DMA，Direct Memory Access））
    • 6、缓冲技术
    • 7、时钟部件的原理
  • 中断机制
  • • 1、中断与异常的概念
    • 2、中断与异常的分类
    • • 1）典型的中断
      • • (1)时钟中断
        • (2)输入输出(I/0)中断
        • (3)控制台中断
        • (4)硬件故障中断
      • 2）典型的异常（异常发生的时间以及位置具有确定性）
      • • (1)程序性中断
        • (2)访管指令异常
    • 3、中断的处理
  • 系统调用
  • • 1、系统调用
    • 2、系统调用分类
    • 3、系统调用的处理过程
• 三、进程与线程
• • 多道程序设计
  • • 1、程序的顺序执行的特点
    • • (1)顺序性
      • (2)封闭性
      • (3)程序执行结果的确定性
      • (4)程序执行结果的可再现性
    • 2、程序的并发执行的特点:
    • • (1)在执行期间并发程序相互制约
      • (2)程序与计算不再一一对应。
      • (3)并发程序的执行结果不可再现。
      • (4)程序的并行执行与程序的并发执行。
    • 3、多道程序设计环境特点
    • • (1)独立性
      • (2)随机性
      • (3)资源共享性,
    • 4、多道程序设计的缺陷:
    • • (1)可能延长程序的执行时间
      • (2)系统效率的提高有一定限度
  • 进程
  • • 1、定义
    • 2、进程的特征
    • • (1)并发性
      • (2)动态性
      • (3)独立性
      • (4)交往性
      • (5)异步性
      • (6)结构性
    • 3、三状态进程模型
    • • (1)运行状态
      • (2)就绪状态
      • (3)等待状态
    • 4、五状态进程模型
    • 5、七状态进程模型
    • 6、进程控制块
    • 7、PCB组织方式：
    • • 1）线性方式
      • 2）索引方式
      • 3）链接方式
    • 8、进程的队列
    • • 1）就绪队列
      • 2）等待队列
      • 3）运行队列
    • 9、进程控制原语
    • 10、 UNIX 类操作系统中,父进程通过调用 fork 函数创建子进程。典型的步骤
    • • (1)为子进程分配一个空闲的 proe 结构(即进程描述符)
      • (2)赋于子进程唯一的标识 PID
      • (3)以一次一页的方式复制父进程用户地址空间
      • (4)获得子进程继承的共享资源的指针,如打开的文件和当前工作目录等
      • (5)子进程就绪,加人调度队列
      • (6)对子进程返回标识符 0；向父进程返回子进程的 PID
  • 线程
  • • 1、线程的定义
    • 2、线程实现机制
    • • （1）用户级线程
      • （2）内核级线程
      • （3）混合实现方式
  • 进程调度
  • • 1、进程调度的主要功能
    • 2、进程调度的时机
    • • (1)正在执行的进程运行完毕
      • (2)正在执行的进程于某种错误而终止
      • (3)时间片用完,即有一个进程从运行状态变为就绪状态
      • (4)正在执行的进程调用阻塞原语将自己阻塞起来,即一个进程从运行状态进入阻塞状态。
      • (5)创建了新的进程,即有一个新的进程进入就绪队列。
      • (6)正在执行的进程调用了唤醒原语操作激活了等待资源的进程,即一个等待状态的进程变为就绪状态。
    • 3、进程调度算法
    • • (1)先来先服务算法
      • (2)最短进程优先算法
      • (3)最短剩余时间优先算法
      • (4)最高响应比优先算法
      • (5)轮转算法
      • (6)最高优先级算法
      • (7)多级反馈队列算法
  • 系统内核
  • • 1、系统核心/系统内核【内核】
• 四、进程同步与互斥
• • 进程间相互作用
  • • 1）相关进程
    • 2）无关进程
  • 进程的同步与互斥
  • • 1、进程的同步
    • 2、进程的互斥
    • 3、临界区
    • 4、相关临界区
    • 5、系统对相关临界区的调度使用原则
  • 信号量及P、V操作
  • • 1、信号量
    • 2、P操作和 V操作定义
    • 3、用P、V操作实现进程之间的互斥
    • 4、用P、V操作实现进程之间的同步
  • 经典的进程同步问题
  • • 1、经典的进程同步问题:
    • • (1)简单生产者一一消费者问题
      • (2)多个生产者一一消费者问题
      • (3)读者——写者问题
  • 管程
  • • 1、管程的概念及组成
    • 2、管程具有三个主要的特性
    • • 1）模块化
      • 2）抽象数据类型
      • 3）信息隐蔽
  • 进程通信
  • • 1、解决进程之间的大量信息通信的问题方案
    • • 1）共享内存
      • 2）信息机制
      • 3）管道通信
• 五、死锁
• • 死锁的产生
  • • 1、死锁
    • 2、死锁产生的原因
    • • (1)竞争资源
      • (2)多道程序运行时,进程推进顺序不合理。
    • 3、死锁产生的必要条件
    • • (1)互斥条件
      • (2)不可剥夺条件
      • (3)请求和保持条件
      • (4)循环等待条件
    • 4、解决死锁的方法
    • • 1）预防死锁
      • 2）避免死锁
      • 3）检测与解除死锁
      • 4）忽略死锁
  • 死锁预防
  • • 1、预防死锁的策略
    • • (1)资源的静态分配策略
      • (2)资源的有序分配法
  • 死锁避免
  • • 1、死锁避免的基本思想
    • 2、安全状态与不安全状态
    • • 1）安全状态
      • 2）不安全状态
    • 3、银行家算法
  • 死锁的检测与解除
  • • 1、死锁检测的时机
    • 2、死锁检测的算法
    • 3、死锁的解除方法
    • • (1)剥夺资源
      • (2)撤销进程
  • 资源分配图
  • • 1、资源分配图
    • 2、死锁定理
    • • (1)如果资源分配图中没有环路,则系统没有死锁
      • (2)如果资源分配图中出现了环路,则系统中可能存在死锁
    • 3、资源分配图化简方法
    • • (1)在资源分配图中
      • (2)将P1所释放的资源分配给申请它们的进程即在资源分配图中将这些进程对资源的申请边改为分配边。
      • (3)重复(1)、(2)两步骤,直到找不到符合条件的进程结点。
  • 哲学家就餐问题
• 六、存储管理
• • 存储管理概述
  • • 1、内存空间
    • 2、内存分配有两种方式
    • • (1)静态分配
      • (2)动态分配
    • 3、存储共享
    • • 1）目的
      • • 通过代码共享节省内存空间，提高内在利用率。
        • 通过数据共享实现进程通信。
      • 2）存储保护的内容
    • 4、地址重定位
    • • 1）静态重定位
      • 2）动态重定位
  • 分区管理方案
  • • 1、固定分区
    • 2、可变分区
    • 3、紧缩技术
    • 4、内存分配表
    • • 1）已分配区表
      • 2）空闲区表
    • 5、操作系统查找和分配空闲区的三种分配算法
    • • (1)最先适应算法
      • (2)最优适应算法
      • (3)最坏适应算法
    • 6、分区管理方案的优缺点
    • • 1）优点
      • 2）缺点
  • 覆盖与交换技术
  • • 1、覆盖技术
    • 2、交换技术（对换技术）
  • 虚拟页式存储管理方案
  • • 1、虚拟存储技术的基本思想
    • 2、页式存储管理思想
    • 3、页表
    • 4、页表的分类
    • • (1)多级页表
      • (2)散列页表
      • (3)反置页表
    • 5、转换检测缓冲区(TLB)
    • 6、缺页异常处理过程
    • 7、页面调度策略
    • 8、页面置换算法
    • • (1)理想页面置换算法(OPT)
      • (2)先进先出页面置换算法(FIFO)
      • (3)第二次机会页面置换算法
      • (4)时钟页面置换算法(Clock)
      • (5)最近最少使用页面置换算法(LRU)
    • 9、影响缺页率的因素
    • • (1)分配给程序的物理页面数
      • (2)页面的大小
      • (3)程序编制方法
      • (4)页面调度算法
    • 10、虚拟页式存储管理的优缺点
    • • 1）优点
      • 2）缺点
• 七、文件系统
• • 文件系统的基本概念
  • • 1、文件
    • 2、文件名
    • 3、文件系统
    • • 功能
    • 4、外存储设备的特点
    • 5、文件常用的存取方法
    • • 1）顺序存取
      • 2）随机存取
    • 6、文件的分类
    • • (1)按文件的用途分类
      • (2)按文件的组织形式分类
      • (3)一些常见的文件分类方式
      • (4)UNIX类操作系统中文件的分类
  • 文件的逻辑结构和物理结构
  • • 1、设计文件逻辑结构的原则
    • • 1）易于操作
      • 2）查找快捷
      • 3）修改方便
      • 4）空间紧凑
    • 2、文件的逻辑结构
    • • 1）无结构的字符流式文件
      • 2）定长记录文件
      • 3）不定长记录文件构成的记录树
    • 3、文件的物理结构（逻辑）
    • • (1)顺序结构
      • (2)链接结构
      • (3)索引结构
  • 文件目录
  • • 1、文件控制块的内容
    • 2、文件目录
    • 3、目录项
    • 4、目录文件
    • 5、目录项分解法
    • 6、FAT文件系统三个版本
    • • FAT-12
      • FAT- 16
      • FAT-32
  • 文件存储空间管理
  • • 1、磁盘空间的分配回收算法
    • • (1)位示图
      • (2)空闲块表
      • (3)空闲块链表
    • 2、空闲块成组链接法
  • 实现文件系统的表目
  • • 1、表目
    • 2、在内存中所需的重要表目
    • • 1）系统打开文件表
      • 2）用户打开文件表
  • 文件及文件目录的操作
  • • 1、建立文件的具体步骤如下
    • • (1)检查参数的合法性
      • (2)检查同一目录下有无重名文件
      • (3)在目录中有无空闲位置
      • (4)填写目录项内容
      • (5)返回
    • 2、指针定位时,系统主要完成以下工作
  • 文件系统的性能
  • • 1、磁盘高速缓存的基本思想
  • 文件共享、保护和秘密
  • • 1、文件的共享
    • 2、从共享的时间段上看的有两种使用情况
    • 3、在文件共享的具体方式上，文件的共享形式
    • • (1)文件被多个用户使用
      • (2)文件被多个程序使用
      • (3)文件被多个程序使用
    • 4、常用的文件保密的措施
    • • (1)隐蔽文件目录
      • (2)设置口令
      • (3)使用密码
      • (4)病毒防范
• 八、 I/O设备管理
• • I/0设备管理的基本概念
  • • 1、输入输出设备(I/O) 【外部设备(Peripheral)】
    • 2、I/O设备管理的任务
    • • (1)I/O 设备的性能经常成为系统性能的瓶颈
      • (2)I/O 设备千变万化,对它们实现统一的管理,从而方便用户使用,是 I/0设备管理的另一项重要任务。
      • (3)用户对 I/O 设备的使用必须是安全的
    • 3、I/O设备分类
    • • (1)按设备的使用特性分类
      • (2)若以系统中信息组织方式来划分设备
      • (3)按设备使用可共享性分类
  • I/O硬件和I/O软件的组成
  • • 1、I/O硬件组成
    • 2、I/O软件组成
  • I/O设备控制方式
  • • 1、I/0设备的控制方式
    • • (1)程序控制方式。
      • (2)中断控制方式
      • (3)DMA 控制方式
      • (4)通道控制方式
  • 设备分配与回收
  • • 1、在设备分配算法的实现中,常采用的数据结构主要含四张表
    • • 1）系统设备表
      • 2）设备控制表
      • 3）控制器控制表
      • 4）通道控制表
    • 2、设备分配的总原则
    • 3、独占设备的分配方法
    • • 1）设备的绝对号与相对号
      • 2）设备的指定方式
      • 3）独占型设备的分配
      • 4）释放
    • 4、共享设备使用的具体方法
    • • (1)申请设备
      • (2)启动设备
      • (3)释放设备
  • 磁盘调度策略
  • • 1、信息传输时间
    • • (1)寻找时间
      • (2)延迟时间
      • (3)传送时间
    • 2、移臂调度算法
    • • 1）先来先服务算法
      • 2）最短寻找时间优先算法
      • 3）电梯调度算法
      • 4）单向扫描算法
  • 缓冲技术
  • • 1、缓冲技术（根据系统设置的缓冲区的个数）
    • • 单缓冲
      • 双缓冲
      • 多缓冲
      • 缓冲池
    • 2、在缓冲池中,有四种工作缓冲区
    • • (1)用于收容设备输人数据的收容输入缓冲区 hin
      • (2)用于提取设备输人数据的提取输入缓冲区 sin
      • (3)用于收容处理器输出数据的收容输出缓冲区 hout
      • (4)用于提取处理器输出数据的提取输出缓冲区 sout
  • 虚拟设备技术
  • • 1、虚拟设备技术（SPOOLing 技术）
    • 2、SPOOLing系统
    • • 1）括输人程序模块
      • 2）输出程序模块
      • 3）作业调度程序

一、操作系统概论

概念

1、操作系统

计算机系统中的一个系统软件，他是这样一些程序模块的集合；它们能有效地组织和管理计算机系统中的硬件及软件资源,合理地组织计算机工作流程,控制程序的执行,并向用户提供各种服务功能,使得用户能够灵活、方便、有效地使用计算机,并使整个计算机系统能高效地运行。

2、操作系统特征

1)并发性

并发性是指在计算机系统中同时存在若干个运行着的程序,从宏观上看,这些程序在同时向前推进。
计算机的并发性体现在两个方面：用户程序与用户程序之间并发执行;
用户程序与操作系统程序之间并发执行。

2)共享性

共享性是指操作系统程序与多个用户程序共用系统中的各种资源。这种共享性是在操作系统控制下实现的。
资源的共享性主要针对计算机系统中的如下几项重要资源：中央处理器、内存储器、外存储器、外部设备。在计算机系统中,对资源的共享一般有两种形式:互斥共享和同时共享。

3）虚拟：

是指通过某种技术把一个物理实体变成若干逻辑上的对应物。

4）异步性

即不确定性。同一程序和数据的多次运行可能得到不同的结果;程序的运行时间、运行顺序也具有不确定性;外部输入的请求、运行故障发生的时间难以预测。这些都是不确定性的表现。

3、研究操作系统的观点:

(1)软件的观点。
(2)资源管理的观点。
(3)进程的观点。
(4)虚机器的观点。
(5)服务提供者观点。

4、操作系统的功能

1)进程管理(处理器管理)

进程管理主要包括进程控制、进程同步进程间通信和调度等几方面的内容

2)存储管理

具体包据内存的分配与回收、存储保护和内在扩充三项存储管理功能。

3)文件管理

文件管理的任务是有效地支持文件的存储,检索和修改等操作,解决文件的共享、保密和保护问题,以使用户方便、安全地访问文件。

4)设备管理

设备管理主要完成用户的I/O请求，为用户分配I/O设备。为了完成这些任务，设备管理应具有以下功能：
（1）缓冲管理（2）设备分配（3）设备处理（4）设备独立性和虚拟设备。

5）提供用户接口

具备中断处理、错误处理等功能。操作系统的各功能之间并非是完全独立的,它们之间存在着相互依赖的关系。

操作系统的体系结构

1、体系结构：

(1)Windows操作系统的体系结构。

Windows 体系结构是分层的模块系统，主要层次有硬件抽象层HAL、内核、执行体和大量的子系统集合。

(2)UNIX操作系统的体系结构。

主要包括硬件、内核、系统调用接口、应用程序

(3)Linux操作系统的体系结构。

Linux 系统有四个主要部分，即内核、Shell、文件系统和用户应用程序。内核、Shell和文件系统形成了基本的操作系统结构，它们使得用户可以运行程序、管理文件并使用系统。

(4)Android 操作系统的体系结构。

Android 操作系统分为四层，从高层到低层分别是应用程序层、应用框架层、系统运行库层和 Linux 内核层。
操作系统的发展

操作系统的发展

操作系统的发展过程包括：手工操作、监控程序(早期批处理)、多道批处理、分时与实时系统UNIX通用操作系统、个人计算机操作系统、Andrid 操作系统。

操作系统分类

操作系统分类：按照用户界面的使用环境和功能特征的不同,一般可以把操作系统分为三种基本类型,即批处理系统、分时系统和实时系统。随着计算机体系结构的发展,又出现了许多类型的操作系统,它们是个人操作系统、网络操作系统、分布式操作系统和嵌入式操作系统。

操作系统设计

1、在操作系统设计的过程中主要困难

设计复杂程度高、正确性难以保证和研制周期长等问题。

2、操作系统的设计过程

(1)功能设计。

指的是根据系统的设计目标和使用要求，确定所设计的操作系统应具备哪些功能以及操作系统的类型。

(2)算法设计。

指的是根据计算机的性能和操作系统的功能,来选择和设计满足系统功能的算法和策略,并分析和估算其效能。

(3)结构设计。

指的是按照系统的功能和特性要求,选择合适的结构,使用相应结构设计方法将系统逐步地分解、抽象和综合,使操作系统结构清晰、简明、可靠、易读、易修改,而且使用方便,适应性强。

3、操作系统的设计目标

可靠性(正确性和健壮性)、高效性、易维护性(易读性易扩充性、易剪裁性、易修改性)、可移植性、安全性、简明性

4、操作系统结构研究的目标:

(1)系统模块化。
(2)模块标准化。
(3)通信规范化。

5、操作系统的结构:

(1)整体式结构。

我们把这种操作系统的结构称之为模块组合结构。它的主要优点是,结构紧密,接口简单直接,系统效率较高。模块组合法(或称无序模块法、模块接口法等)的缺点有:第一,模块间转接随便,各模块互相牵连,独立性差,系统结构不清晰。第二,数据基本上作为全程量处理,系统内所有模块的任一程序均可对其进行存取和修改，从而造成了各模块间有着更为隐蔽的关系。第三,由于模块组合结构常以大型表格为中心,为保证数据完整性,往往采用全局封中断办法,从而限制了系统的并发性，系统中实际存在的并发性也未能抽象出明确的概念，缺乏规格的描述方法。所以,这种结构的可适应性比较差。

(2)层次式结构。

层次式结构就是把操作系统的所有功能模块,按功能流图的调用次序,分别将这些模块排列成若干层,各层之间的模块只能是单向依赖或单向调用(如只允许上层或外层模块调用下层或内层模块)关系。

(3)微内核(客户/服务器)结构。

采用客户/服务器结构模式的典型操作系统有卡内基·梅隆大学研制的 Mach操作系统和 Windows NT 的早期版本。这种模式的优点在于,它将系统分成若干个小的并且自包含的分支(服务进程),每个分支运行在独立的用户进程中,相互之间通过规范一致的方式接收发送信息而联系起来。这种体系结构的缺陷主要是对于效率的考虑。

二、操作系统运行环境

处理器

处理器一般由运算器、控制器、一系列的寄存器以及高速缓存构成。其中运算器实现指令中的算术和逻辑运算，是计算机计算的核心。

1 处理器内寄存器

1）用户可见寄存器
2）控制和状态寄存器
通常用户可见寄存器对所有程序都是可用的,由机器语言直接引用。它一般包括数据寄存器(Data Register)、地址寄存器(Address Register)以及条件码寄存器。

2 指令

1、指令执行的基本过程:

1）处理器每次从存储器中读取一条指令并在取指令完成后,根据指令类别自动将程序计数器的值变成下一条指令的地址,通常是自增 1。
2）取到的指令被存储在处理器的指令寄存器中,处理器于是解释并执行这条指令。

2、指令的五类

1）访问存储器指令

负责处理器和存储器之间的数据传送

2）I/O指令

负责处理器和I/O模块之间的数据传送和命令发送

3）算术逻辑指令（数据处理指令）

用以执行有关数据的算术和逻辑操作

4）控制转移指令

可以指定一个新的指令的执行起点

5）处理器控制指令

用于修改处理器状态,改变处理器工作方式等

3、特权指令和非特权指令

1）特权指令

指令系统中那些只能由操作系统使用的指令，有特殊权限的指令。这些指令是不允许一般的用户使用的。

2）非特权指令

用户态下能使用的指令。为了防止用户程序使用特权指令。

3 管态和目态

多数系统将处理器工作状态划分为管态和目态。

1）管态

操作系统管理程序运行的状态,具有较高的特权级别,又称为内核态、特权态(特态)、系统态。

2）目态

用户程序运行时的状态,具有较低的特权级别,又称为用户态、普通态(普态)。

4 处理器工作状态的转换

1）目态到管态的转换

其转换的唯一途径是通过中断。中断响应时交换中断向量，新的中断向量中的 PSW（Program Status Word 程序状态字（也叫程序状态寄存器）） 的处理器状态位标志为管态。

2）管态到目态的转换

通过设置PSW 指令(修改程序状态字),实现从操作系统向用户程序的转换。

计算机系统硬件部件

1、存储器的类型

在微型计算机中使用的半导体存储器有若干种不同的类型。

1）读写型的存储器

可以把数据存入其中任一地址单元,并且可在以后的任何时候把数据读出来,或者重新存人新的数据的一种存储器

2）只读型的存储器

只能从其中读取数据,但不能随意地用普通的方法向其中写人数据。通常要向其中写人数据只能用特殊的方法进行

2、存储器的层次结构

计算机存储系统的设计主要考虑三个问题：容量、速度和成本
从整个系统来看,在计算机系统中的层次化的存储体系由寄存器、高速缓存、内存储器、硬盘存储器、磁带机和光盘存储器等装置构成。

4、I/O结构

在每台外部设备中都配有各自的I/0设备控制器,由I/0设备控制器分别控制各台外部设备的运行。
通道是独立于中央处理器的，专门负责数据1/0传输工作的处理单元。

5、DMA技术（直接内存访问（DMA，Direct Memory Access））

通过系统总线中的一个独立控制单元一一DMA控制器,自动地控制成块数据在内存和1/O单元之间的传送。

6、缓冲技术

用在外部设备与其他硬件部件之间的一种数据暂存技术,它利用存储器件在外部设备中设置了数据的一个存储区域，称为缓冲区。

7、时钟部件的原理

在电路中的晶体振荡器,每隔一定间隔产生固定的脉冲频率，时钟电路中的时钟寄存器依据时钟电路所产生的脉冲数，对时钟寄存器进行加1的工作。
时钟的用途可以分为绝对时钟和相对时钟。

中断机制

1、中断与异常的概念

中断是指处理器对系统中或系统外发生的异步事件的响应。异步事件是指无一定时序关系的随机发生的事件。中断是由外部事件引发的,而异常则是由正在执行的指令引发的。

2、中断与异常的分类

1）典型的中断

(1)时钟中断

由处理器内部的计时器产生,允许操作系统以一定规律执行函数，如时间片到时、硬件实时钟到时等。

(2)输入输出(I/0)中断

由I/O控制器产生,用于通知一个I/O操作的正常完成或者发生的错误。

(3)控制台中断

如系统操作员通过控制台发出命令等。

(4)硬件故障中断

由掉电、存储器校验错等硬件故障引起等.

2）典型的异常（异常发生的时间以及位置具有确定性）

(1)程序性中断

在某些条件下由指令执行结果产生，例如算术溢出、被零除、目态程序试图执行非法指令、访问不被允许访问的存储位置、虚拟存储中的缺页等。

(2)访管指令异常

目的是要求操作系统提供系统服务。

3、中断的处理

I/O中断、时钟中断、硬件故障中断、程序性中断和系统服务请求(自愿性中断)等。

系统调用

1、系统调用

用户在程序中调用操作系统所提供的一些子功能

2、系统调用分类

(1)进程控制类系统调用
(2)文件操作类系统调用
(3)进程通信类系统调用
(4)设备管理类系统调用
(5)信息维护类系统调用

3、系统调用的处理过程

三、进程与线程

多道程序设计

1、程序的顺序执行的特点

(1)顺序性

(2)封闭性

(3)程序执行结果的确定性

(4)程序执行结果的可再现性

2、程序的并发执行的特点:

指一个时间段中有几个程序都处于已启动运行到运行完毕之间，且这几个程序都是在同一个处理机上运行，但任一个时刻点上只有一个程序在处理机上运行。

(1)在执行期间并发程序相互制约

(2)程序与计算不再一一对应。

(3)并发程序的执行结果不可再现。

(4)程序的并行执行与程序的并发执行。

3、多道程序设计环境特点

(1)独立性

(2)随机性

(3)资源共享性,

4、多道程序设计的缺陷:

(1)可能延长程序的执行时间

(2)系统效率的提高有一定限度

进程

1、定义

进程是具有一定独立功能的程序在某个数据集合上的一次运行活动,是系统进行资源分配和调度的一个独立单位。程序是静态的,而进程是动态的。

进程由程序、数据和进程控制块三部分组成。

2、进程的特征

(1)并发性

(2)动态性

(3)独立性

(4)交往性

(5)异步性

(6)结构性

一个进程由程序、数据和进程控制块三部分组成

3、三状态进程模型

(1)运行状态

进程已获得处理器,并且在处理器上执行的状态。显然，在一个单处理器系统中,最多只有一个进处于运行态。

(2)就绪状态

进程已经具备运行条件,但由于没有获得处理器而不能运行所处的状态。一旦把处理器分配给它,该进程就可运行。处于就绪状态的进程可以是多个

(3)等待状态

也称阻塞状态或封锁状态,是指进程因等待某种事件发生而暂时不能运行的状态。

三种基本状态之间的转换：就绪一运行、运行一就绪、运行一等待、等待一就绪

4、五状态进程模型

5、七状态进程模型

6、进程控制块

进程控制块的内容可以分成调度信息和现场信息两大部分

7、PCB组织方式：

PCB进程控制块（PCB Process Control Block）【为了描述控制进程的运行，系统中存放进程的管理和控制信息的数据结构】，它是进程实体的一部分，是操作系统中最重要的记录性数据结构。它是进程管理和控制的最重要的数据结构，每一个进程均有一个PCB，在创建进程时，建立PCB，伴随进程运行的全过程，直到进程撤消而撤消。

1）线性方式

2）索引方式

3）链接方式

8、进程的队列

1）就绪队列

2）等待队列

3）运行队列

9、进程控制原语

创建进程、撤销进程、挂起进程、激活进程、阻塞进程、唤醒进程以及改变进程优先级等。

10、 UNIX 类操作系统中,父进程通过调用 fork 函数创建子进程。典型的步骤

(1)为子进程分配一个空闲的 proe 结构(即进程描述符)

(2)赋于子进程唯一的标识 PID

(3)以一次一页的方式复制父进程用户地址空间

(4)获得子进程继承的共享资源的指针,如打开的文件和当前工作目录等

(5)子进程就绪,加人调度队列

(6)对子进程返回标识符 0；向父进程返回子进程的 PID

线程

1、线程的定义

在引入线程的操作系统中,线程是进程中的一个实体,是处理器调度和分派的基本单位。

2、线程实现机制

（1）用户级线程

（2）内核级线程

（3）混合实现方式

进程调度

1、进程调度的主要功能

记录系统中所有进程的执行状况;根据一定的调度算法，从就绪队列中选出一个进程，准备把处理器分配给它;把处理器分配给进程。

2、进程调度的时机

(1)正在执行的进程运行完毕

(2)正在执行的进程于某种错误而终止

(3)时间片用完,即有一个进程从运行状态变为就绪状态

(4)正在执行的进程调用阻塞原语将自己阻塞起来,即一个进程从运行状态进入阻塞状态。

(5)创建了新的进程,即有一个新的进程进入就绪队列。

(6)正在执行的进程调用了唤醒原语操作激活了等待资源的进程,即一个等待状态的进程变为就绪状态。

3、进程调度算法

(1)先来先服务算法

(2)最短进程优先算法

(3)最短剩余时间优先算法

(4)最高响应比优先算法

响应比 Rp=(等待时间+预计运行时间)/预计运行时间=周转时间/预计运行时间。

(5)轮转算法

轮转(Round-Robin，RR)算法最早来自分时系统

将CPU的处理时间划分成一个个时间片，就绪队列中的诸进程轮流运行一个时间片。当时间片结束时，就强迫运行进程让出CPU,该进程进人就绪队列，等待下一-次调度。同时，进程调度又去选择就绪队列中的一个进程，分配给它一一个时间片，以投人运行。如此轮流调度，使得就绪队列中的所有进程在一个有限的时间T内都可以依次轮流获得一个时间片的处理机时间，从而满足了系统对用户分时响应的要求。

(6)最高优先级算法

(7)多级反馈队列算法

该法综合了先进先出调度算法、时间片轮转算法和可抢占式最高优先级算法的一种进程调度算法。

系统内核

1、系统核心/系统内核【内核】

把操作系统中提供支持系统运行的各种基本操作和基础功能的一组程序模块集中安排,形成一个操作系统的核心

通常,内核只占整个操作系统代码中的一小部分,内核是操作系统中最接近裸机的部分。

四、进程同步与互斥

进程间相互作用

1）相关进程

在逻辑上具有某种联系的进程

2）无关进程

在逻辑上没有任何联系的进程

并发进程相互之间可能是无关的,也可能是相关的。

进程的同步与互斥

1、进程的同步

进程之间一种直接的协同工作关系，一些进程相互合作,共同完成一项任务。

2、进程的互斥

在系统中,许多进程常常需要共享资源，而这些资源往往要求排他性的使用，即一次只能为一个进程服务,因此,各进程间只能互斥使用这些资源,进程间的这种关系就是进程的互斥。

3、临界区

若在系统中某些资源一次只允许一个进程使用,则这类资源成为临界资源或共享变量,而在进程中访问临界资源的程序称为临界区。

4、相关临界区

有若干进程共享某一临界区

5、系统对相关临界区的调度使用原则

(1)当临界区为空时,若有一个进程要求进人临界区,应允许它立即进人临界区—— 有空让进。
(2)若有一个进程已在临界区时,其他要求进入临界区的进程必须等待 ——无空等待
(3)当没有进程在临界区,而同时有多个进程要求进人临界区，只能让其中之一进入临界区,其他进程必须等待一一多中择一
(4)任一进程进人临界区的要求应在有限时间满足一一有限等待
(5)处于等待状态的进程应放弃占用处理器一一让权等待,

信号量及P、V操作

1、信号量

一种特殊的变量,它的表面形式是一个整型变量附加一个队列;而且,它只能被特殊的操作(即 P操作和 V操作)使用。P 操作和 V操作都是原语
设信号量为 S,S可以取不同的整数值。对信号量 S实施的 P操作和 V 操作,可分别用P(S)和 V(S)表示。

2、P操作和 V操作定义

//P操作
P(S)
{
    S=S-1;
    // 若 S<0,将该进程状态置为等待状态,然后将该进程的 PCB 插入相应的 S信号量等待队列末尾,直到有其他进程在 S 上执行 V 操作为止;
}
// V操作
V(S)
{
    S=S+1;
    // 若 S≤0,释放在 S 信号量队列中等待的一个进程,将其状态改变为就绪态，并将其插人就绪队列;然后,执行本操作的进程继续执行;
}

3、用P、V操作实现进程之间的互斥

假设有进程A、B竞争进人临界区，用P,V操作实现进程之间的互斥的程序可以
写成:
进程A 进程B
P(S) P(S)
临界区操作 临界区操作
V(S） V(S)

S的初值为1

4、用P、V操作实现进程之间的同步

考虑一种同步关系,其中有两个信号量 S1,和 S2,赋予它们的初值均为 0,S1,表示在一个缓冲区中是否装满信息,S2表示该缓冲区中信息是否取走。程序可写成:

经典的进程同步问题

1、经典的进程同步问题:

(1)简单生产者一一消费者问题

(2)多个生产者一一消费者问题

(3)读者——写者问题

管程

1、管程的概念及组成

一个管程是一个由过程、变量及数据结构等组成的一个集合,它们组成一个特殊的模块或软件包。一个管程由四个部分组成,它们是管程名称、共享数据的说明、对数据进行操作的一组过程和对共享数据赋初始值的语句

2、管程具有三个主要的特性

1）模块化

2）抽象数据类型

3）信息隐蔽

进程通信

1、解决进程之间的大量信息通信的问题方案

1）共享内存

2）信息机制

包括消息缓冲通信、信箱通信和管道通信

3）管道通信

通过共享文件进行通信

五、死锁

死锁的产生

1、死锁

多道程序系统中的一种现象，一组进程中的每一个进程均无限期地等待被该组进程中的另一个进程所占有且永远不会释放的资源。系统发生这种现象称为系统处于死锁状态,简称死锁。处于死锁状态的进程称为死锁进程。

2、死锁产生的原因

(1)竞争资源

系统资源在分配时出现失误,进程间对资源的相互争夺而造成僵局。
死锁是若干进程因使用资源不当而造成无法推进的现象。
按照资源的使用性质，一般把系统中的资源分成两类:
永久性资源(可重用资源)：是指系统中可供进程重复使用长期存在的资源,如内存、外部设备、处理器等硬件资源,以及各种数据文件、表格、共享程序代码等软件资源;
临时性资源(消耗性资源)：是指由某个进程所产生、只为另一个进程使用一次或经过短暂时间后便不再使用的资源。以上两种资源都可能导致死锁发生

(2)多道程序运行时,进程推进顺序不合理。

3、死锁产生的必要条件

(1)互斥条件

(2)不可剥夺条件

(3)请求和保持条件

(4)循环等待条件

4、解决死锁的方法

1）预防死锁

2）避免死锁

3）检测与解除死锁

4）忽略死锁

死锁预防

指在任何系统操作前(例如分配资源、调度进程等),事先评估系统的可能情况,严格采取措施使得死锁的四个必要条件不成立。死锁预防的基本思想是防范于未然。

1、预防死锁的策略

(1)资源的静态分配策略

(2)资源的有序分配法

采用资源有序分配策略，其基本思想是将系统中所有资源顺序编号。一般原则是：较为紧缺、稀少的资源的编号较大。进程申请资源时，必须严格按照资源编号的顺序进行,否则系统不予分配。即一个进程只有得到编号小的资源,才能申请编号较大的资源;释放资源时,应按编号递减的次序进行。

死锁避免

1、死锁避免的基本思想

系统对进程发出的每一个系统能够满足的资源申请进行动态检查,并根据检查结果决定是否分配资源;如果分配后系统可能发生死锁,则不予分配，否则予以分配。这是一种保证系统不进入死锁状态的动态策略。

2、安全状态与不安全状态

1）安全状态

如果存在一个由系统中所有进程构成的安全序列(P1,… ,Pn),则系统处于安全状态。一个进程序列(P1,… ,Pn)是安全的,如果对于其中每一个进程 Pi(1 ≤ i ≤ n)，它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(j<i)当前占有资源量之和。系统处于安全状态则不会发生死锁。

2）不安全状态

不存在任何一个安全序列

不安全状态不一定导致死锁,但死锁状态一定是不安全状态。即系统若处于不安全状态则可能发生死锁。

3、银行家算法

最著名的死锁避免算法是由 Dijkstra 等人提出来的银行家算法。操作系统按照银行家的规定为进程分配资源，进程首先提出对资源的最大需求量,当进程在执行中每次申请资源时,系统测试该进程已占用的资源与本次申请的资源数之和是否超过了该进程对资源的最大需求量、若超过则拒绝分配资源。若没有超过,则系统再测试来现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。这样做,能保证在任何时刻至少有一个进程可以得到所需要的全部资额而执行结束，执行结束后归还的资源加人到系统的剩余资源中，这些资源又至少可以满足另一个进程的最大需求,于是,可以保证系统中所有进程都能在有限的时间内得到需要的全部资源。

死锁的检测与解除

1、死锁检测的时机

死锁检测可以在任何一次资源分配后，也可以在每次调度后,或者利用定时器定时运行检测,还有一种方法是当系统中某个进程长期位于阻塞态或阻塞进程过多时,启动死锁检测程序。

2、死锁检测的算法

死锁检测的算法依不同的系统而不同

3、死锁的解除方法

(1)剥夺资源

经常使用的方法有:还原算法，即恢复计算结果和状态;建立检查点主要是用来恢复分配前的状态。

(2)撤销进程

撤销死锁进程,将它们占有的资源分配给另一些死锁进程，直到死锁解除为止。

资源分配图

1、资源分配图

资源分配图是一张有向图，一个系统资源分配图 SRAG 可定义为一个二元组,即SRAG=(V,E),其中 V是顶点的集合,而 E是有向边的集合

2、死锁定理

(1)如果资源分配图中没有环路,则系统没有死锁

(2)如果资源分配图中出现了环路,则系统中可能存在死锁

A) 如果处于环路中的每个资源类中均只包含一个资源实例,则环路的存在即意味着死锁的存在。此时，环路是死锁的充分必要条件。
B) 如果处于环路中的每个资源类中资源实例的个数不全为 1，则环路的存在是产生死锁的必要条件而不是充分条件。

3、资源分配图化简方法

(1)在资源分配图中

找出一个既非等待又非孤立的进程结点 P1 ，由于P1可获得它所需要的全部资源，且运行完后释放它所占有的全部资源，故可在资源分配图中消去P1， 所有的申请边和分配边,使之成为既无申请边又无分配边的孤立结点。

(2)将P1所释放的资源分配给申请它们的进程即在资源分配图中将这些进程对资源的申请边改为分配边。

(3)重复(1)、(2)两步骤,直到找不到符合条件的进程结点。

经过化简后,若能消去资源分配图中的所有边，使所有进程都成为孤立结点,则该图是可完全化简的;否则为不可化简的。

哲学家就餐问题

操作系统中关于进程同步与互斥的经典问题,也是涉及死锁的关键问题。

六、存储管理

存储管理概述

1、内存空间

由存储单元(字节或字)组成的一维连续的地址空间,简称内存空间。内存空间一般分为两部分:一部分是系统区,用以存储操作系统常驻内存部分,用户不能占用这部分空间;另一部分是用户区,分配给用户使用,用于装人并存储用户程序和数据,这部分的信息随时都在发生变化。存储管理实质上就是管理供用户使用的那部分空间。

2、内存分配有两种方式

(1)静态分配

程序要求的内存空间是在目标模块连接装入内存时确定并分配的，并且在程序运行过程中不允许再申请或在内存中“搬家”,即分配工作是在程序运行前一次性完成。

(2)动态分配

程序要求的基本内存空间是在目标模块装入时确定并分配的,但是程序运行过程中申请附加的内存空间或在内存中“搬家”,即分配工作可以在程序运行前及运行过程中逐步完成。

3、存储共享

两个或多个进程共用内存中相同区域,这样不仅能使多道程序动态地共享内存，提高内存利用率,而且还能共享内存中某个区域的信息。共享的内容包括代码共享和数据共享,特别是代码共享要求代码必须是纯代码。

1）目的

通过代码共享节省内存空间，提高内在利用率。

通过数据共享实现进程通信。

2）存储保护的内容

保护系统程序区不被用户有意或无意的侵犯；不允许用户想读写不属于自己地址空间的数据,如系统区地址空间、其他用户程序的地址空间。

4、地址重定位

把逻辑地址转换成绝对地址的工作称“地址重定位”或“地址转换”,又称“地址映射”。重定位的方式可以有“静态重定位”和“动态重定位”。

1）静态重定位

内存在装人程序时,要把程序中的指令地址和数据地址全部转换成绝对地址。由于地址转换工作是在程序开始执行前集中完成的，所以在程序执行过程中就无须再进行地址转换工作，这种地址转换方式称“静态重定位”

2）动态重定位

内存在装入程序时,不进行地址转换，而是直接把程序装入到分配的内存区域中。在程序执行过程中,每当执行一条指令时都由硬件的地址转换机构将指令中的逻辑地址转换成绝对地址。这种方式的地址转换是在程序执行时动态完成的,故称为“动态重定位”

分区管理方案

1、固定分区

系统先把内存划分成若干个大小固定的分区，一旦划分好,在系统运行期间便不再重新划分。为了满足不同程序的存储要求,各分区的大小可以不同由于每一分区的大小是固定的,就对可容纳程序的大小有所限制。因此,程序运行时必须提供对内存资源的最大申请量。

2、可变分区

系统不预先划分固定分区,而是在装入程序时划分内存分区,使为程序分配的分区的大小正好等于该程序的需求量,且分区的个数是可变的。显然,可变分区有较大的灵活性,较之固定分区能获得较好的内在利用率。

系统初启后,在内存中除操作系统区之外,其余空间为一个完整的大空闲区。当有型程序要求装人内存运行时,系统从该空闲区中划分出一块与程序大小相同的区域进行分配，当系就运行一段时间后,随着一系列的内存分配和回收。原来的一整块大空用区形成了若干占用区和空用闲区相间的布局。若有上下相邻的两块空闲区,系统应将它们合并成为一块连续的大空闲区。

3、紧缩技术

解决碎片问题的办法是在适当时刻进行碎片整理,通过移动内存中的程序,把所有空闲碎片合并成一个连续的大空闲区且放在内存的一端,而把所有程序占用区放在内存的另一端这一技术称为“紧缩技术”或“压缩技术”

4、内存分配表

由两张表格组成。

1）已分配区表

记录已装入的程序在内存中占用分区的起始地址和长度,用标志位指出占用分区的程序名。

2）空闲区表

记录内存中可供分配的空闲区的起始地址和长度,用标志位指出该分区是未分配的空闲区

5、操作系统查找和分配空闲区的三种分配算法

(1)最先适应算法

又称顺序分配算法,当接到内存申请时,顺序查找分区说明表,找到第一个满足申请长度的空闲区,将其分割并分配。此算法简单,可以快速做出分配决定。

(2)最优适应算法

当接到内存申请时，查找分区说明表,找到第一个能满足申请长度的最小空闲区,将其分割并分配。此算法最节约空间,因为它尽量不分割大的空闲区;其缺点是可能会形成很多很小的空闲区域,称作碎片。

(3)最坏适应算法

当接到内存申请时,查找分区说明表,找到能满足申请要求的最大的空闲区。该算法的基本思想是:在大空闲区中装人信息后,分割剩下的空闲区相对也很大,还能用于装人其他程序。

6、分区管理方案的优缺点

分区管理是实现多道程序设计的一种简单易行的存储管理技术。

1）优点

通过分区管理,内存真正成为了共享资源,有效地利用了处理器和 I/O 设备，从而提高了系统的吞吐量和缩短了周转时间。分区在管理算法比较简单,所采用的表格不多,实现起来比较容易，内存额外开销较少,存储保护措施也很简单。在内存利用率方面,可变分区的内存利用率比固定分区高。

2）缺点

内存使用仍不充分,并且存在着较为严重的碎片问题。虽然可以解决碎片问题,但需要移动大量信息,浪费了处理器时间。此外,分区管理不能为户提供“虚存”,即不能实现对内存的“扩充”,每一个用户程序的存储要求仍然受到物理储器实际存储容量的限制。分区管理要求运行程序一次全部装人内存之后,才能开始运行。这样，内存中可能包含有一些实际不使用的信息。

覆盖与交换技术

1、覆盖技术

一个程序的若干程序段，或几个程序的某些部分共享某一个存储空间。覆盖技术的实现是把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构使那些不会同时执行的程序段共享同一块内存区域。未执行的程序段先保存在磁盘上,当有关程序段的前一部分执行结束后,把后续程序段调入内存,覆盖前面的程序段。

2、交换技术（对换技术）

在分时系统中,用户的进程比内存能容纳的数量要多,这就需要在磁盘上保存那些内存放不下的进程。在需要运行这些进程时,再将它们装人内存。

在实际操作系统中使用交换技术需考虑的问题：换出进程的选择、交换时机的确定交换空间的分配、换人进程换回内存时位置的确定。

虚拟页式存储管理方案

1、虚拟存储技术的基本思想

利用大容量的外存来扩充内存,产生一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间,简称虚存,以便能够有效地支持多道程序系统的实现和大型程序运行的需要,从而增强系统的处理能力。

2、页式存储管理思想

页式存储管理思想首先由英国曼彻斯特大学提出，并在该校的 Atlas 计算机上使用。该技术近年来已广泛用于计算机系统中,支持页式存储管理的硬件部件通常称为“存储管理部件”

3、页表

页表指出该程序虚拟施址中的页号与所占用的物理页面号之间的对应关系。页表的长度由程序拥有的页面数而定,故每个程序的页表长度可能是不同的。
页表又是硬件进行地址转换的依据，每执行一条指令时按虚拟地址中的页号查页表，若页表中无此页号,则产生一个“地址销”的程序性中断事件。若页表中有此页号,则可得到对应的物理页面号,按计算公式可转换成访问的内存的物理地址。

4、页表的分类

(1)多级页表

大多数操作系统中采用二级页表,即由页表页和页目录一起构成进程页表。第一级表示页目录,保存页表页的地址;第二级表示页表页,保存物理页面号。

(2)散列页表

当地址空间大于 32 位时，一种常见的方法是使用以页号为散列值的散列页表。其中每个表项都包含一个链表,该链表中元素的散列值都指向同一个位置。这样,散列页表中的每个表项都包含三个字段:(a)虚拟页号;(b)所映射的页框号;©指向链表中下一个元素的指针。

(3)反置页表

在反置页表中,每个物理页框对应一个表项。每个表项包含与该页框相对应的虚拟页面地址,以及拥有该页面进程的信息。因此，整个系统中只存在一个页表,并且每个页框对应其中一个表项。由于一方面系统中只有一个页表,而另一方面系统中又存在着多个映射着物理内存的地址空间,因此需要在反置页表中存放地址空间标志符。

5、转换检测缓冲区(TLB)

利用高速缓冲存储器存储当前访问最频繁的少数活动页面的页号，这个高速缓冲存储器称为“转换检测缓冲区”,也称为“快表”

6、缺页异常处理过程

(1)根据当前执行指令中的逻辑地址查页表的有效位,判断该页是否在内存。
(2)该页标志为“0”,形成缺页异常。保留现场,中断装置通过交换 PSW 让操作系统的中断处理程序占用处理器。
(3)操作系统处理缺页异常,寻找一个空闲的页面。
(4)若有空闲页，则把磁盘上读出的信息装人该页面中
(5)修改页表及内存分配表,表示该页已在内存。
(6如果内存中无空用面,则按某种算法选择一个已在内存的页面,把它暂时调出存。若在执行中该页面已被修改过,则要把该页信息重新写回到磁盘上，否则不必重新回磁盘、当一页被暂时调出内存后,让出的内存空间用来存储当前需要使用的页面。面被调出或装入之后都要对页表及内存分配表作修改。
(7)恢复现场、重新执行被中断的指令。当重新执行该指令时，由于要访问的页面被装人内存、所以可正常执行下去。

7、页面调度策略

虚拟存储器系统通常定义三种策略来规定如何(或何时)进行页面调度:调入策略(请求调页和预调页)、置页策略和置换策略(固定分配局部换、可变分配全局置换和可变分配局部置换)

8、页面置换算法

(1)理想页面置换算法(OPT)

(2)先进先出页面置换算法(FIFO)

(3)第二次机会页面置换算法

(4)时钟页面置换算法(Clock)

(5)最近最少使用页面置换算法(LRU)

9、影响缺页率的因素

(1)分配给程序的物理页面数

(2)页面的大小

(3)程序编制方法

(4)页面调度算法

10、虚拟页式存储管理的优缺点

1）优点

由于它不要求进程的程序段和数据在内存中连续存放,从而有效地解决了碎片问题。这既提高了内存的利用率,又有利于组织多道程序执行。

2）缺点

存在页面空间的浪费问题。这是由于各种程序代码的长度是各不相同的,但页面的大小是定的,所以在每个程序的最后一页内总有一部分空间得不到利用。如果页面较大,则由此引起的存储空间的损失仍然较大。

七、文件系统

文件系统的基本概念

1、文件

一组带标识的、在逻辑上有完整意义的信息项的序列。

2、文件名

用户在创建文件时确定的,并在以后访问文件时使用。文件名通常由用户给定,它是一个字母数字串,有些系统规定必须是英文字母打头且允许一些其他的符号出现在文件名的非打头部分。

3、文件系统

操作系统中统一管理信息资源的一种软件。它管理文件的存储、检索、更新,提供安全可靠的共享和保护手段,并且方便用户使用。

功能

(1)统一管理文件的存储空间,实施存储空间的分配与回收。
(2)实现文件从名字空间到外存地址空间的映射。即实现文件的按名存取,以对用户透明的方式管理名字空间。
(3)实现文件信息的共享,并提供文件的保护和保密措施。
(4)向用户提供一个方便使用的接口(提供对文件系统操作命令,以及提供对文件的操作命令:信息存取、加工等)。
(5)系统维护及向用户提供有关信息。
(6)保持文件系统的执行效率。
文件系统在操作系统接口中占的比例最大,用户使用操作系统的感觉在很大程度上取决于对文件系统的使用效果。
(7)提供与I/0的统一接口

4、外存储设备的特点

在计算机系统中,外存储设备同内存相比较,一般有容量大、断电后仍可保存信息、速度较慢、成本较低等特点。

5、文件常用的存取方法

1）顺序存取

2）随机存取

6、文件的分类

(1)按文件的用途分类

系统文件、库函数文件、用户文件

(2)按文件的组织形式分类

普通文件、目录文件,特殊文件

(3)一些常见的文件分类方式

A）按文件的保护方式可划分为;只读文件、读写文件、可执行文件、无保护文件
B ）按信息的流向分类可划分为:输人文件、输出文件和输人输出文件等
C）接文件的存放时限可划分为:临时文件、永久文件和档案文件等。

临时文件,及有临时性信息的文件;永久性文件,即其信息需要长期保存的文件;档案文件,即保存在作为“档案”用的磁带或光盘等永久性介质上,以备查证和恢复时使用的文件。

D）按文件所使用的介质类型分类可划分为:磁盘文件、磁带文件、卡片文件和打印文件等，
E）按文件的组织结构分类。

(4)UNIX类操作系统中文件的分类

A)普通文件。这是内部无结构的一串平滑的字符所组成的文件
B)目录文件。这是由文件目录项所构成的文件。
C)特殊文件。在 UNIX 类操作系统中,把 I/O设备也看成是一种文件——特殊文件

文件的逻辑结构和物理结构

1、设计文件逻辑结构的原则

1）易于操作

2）查找快捷

3）修改方便

4）空间紧凑

2、文件的逻辑结构

用户所看到的文件的组织形式。
可以按逻辑结构把文件划分成三类:

1）无结构的字符流式文件

2）定长记录文件

3）不定长记录文件构成的记录树

定长记录文件和不定长记录文件可以统称为记录式文件。

3、文件的物理结构（逻辑）

文件在外存上的存储组织形式,它与存储介质的物理特性、文件的存取方法以及所采用的存储空间的分配方式都有关。

(1)顺序结构

又称连续结构,这是一种最简单的文件物理结构,它把逻辑上连续的文件信息依次存放在连续编号的物理块中。

(2)链接结构

文件的链接结构的实质就是为每个文件构造所使用磁盘块的链表。使用这种链接结构的文件,将逻辑上连续的文件分散存储在若干不连续的物理块中。

(3)索引结构

索引结构的文件把每个物理盘块的指针字,集中存储在称为索引表的数据结构中的内存索引表中。

文件目录

1、文件控制块的内容

文件名、文件号、用户名、文件地址、文件长度、文件类型、文件属性、共享计数、文件的建立日期、保存期限,最后修改日期、最后访问日期、口令、文件逻辑结构、文件物理结构,等等。

2、文件目录

在操作系统中,为了管理大量的文件,为每个文件都设置一个描述性数据结构——文件控制块，把所有文件的文件控制块有机地组织起来,就构成了文件控制块的一个有序集合,称为文件目录。

根据实际的需要,一般把文件目录设计成一级(单级)目录结构、二级目录结构和多领目录结构。

3、目录项

当用户建立一个新文件时,与该文件有关的一些信息与属性记录在该文件的文件控制块内。为了便于管理,通常将文件控制块做成定长数据结构的一个记录,存储在目录文件中。而这样的每一个记录称为目录项。

4、目录文件

多个文件的文件控制块集中在一起组成了文件的目录。通常,文件目录以文件的形式保存起来,这个文件就被称为目录文件。目录文件是每项记录长度固定的记录式文件。

5、目录项分解法

为加快目录检索可采用目录项分解法。
即把目录项分为两部分,符号目录项(次部)和基本目录项(主部)。其中,符号目录项包含文件名以及相应的文件号;而基本目录项包含了除文件名外文件控制块的其他全部信息。

6、FAT文件系统三个版本

取决于用多少二进制位表示磁盘块地址

FAT-12

FAT- 16

FAT-32

文件存储空间管理

1、磁盘空间的分配回收算法

(1)位示图

该法的基本思想是,利用一串二进制位(bit)的值来反映磁盘空间的分配使用情况

(2)空闲块表

空闲块表是专门为空闲块建立的一张表,该表记录外存储器全部空闲的物理块:包括每个空闲块的第一个空闲物理块号和该空闲块中空闲物理块的个数

(3)空闲块链表

将外存储器中所有的空闲物理块连成一个链表,用一个空闲块首指针向第一个空闲换,随后的每个空闲块中都含有指向下一个空闲快的指针，最后一块的指针为空，表示链尾,这样就构成了一个空闲块链表。

2、空闲块成组链接法

对链接表的一个改进方案是将 n 个空闲盘块的地址存储在第一个空闲块中。其余n-1个空闲盘块是实际空闲的。假设每 100 个空闲块为一。第一组的 100 个空闲块块号放在第二组的头一块中，而第二组的其余 99 块是完全空闲的。第二组的 100 个块号又放在第三组的头一块中，依次类推,组与组之间形成链接关系。在最后一组的块号中第2个单元填“0”,表示该块中指出的块号是最后一组的块号,空闲块链到此结束。在这个空闲块链中,不足 100块的一个组的块号,通常放在内存的一个专用块中。这种方式称为成组链接。

实现文件系统的表目

1、表目

当用户申请打开一个文件时,系统要在内存中为该用户保存一些必要的信息，这些信息以表格栏目中内容的形式出现。

2、在内存中所需的重要表目

1）系统打开文件表

2）用户打开文件表

文件及文件目录的操作

1、建立文件的具体步骤如下

(1)检查参数的合法性

文件名是否符合命名规则,若是,则进行下一步(2);否则报错,返回。

(2)检查同一目录下有无重名文件

若没有,则进行下一步(3);否则报错,返回。

(3)在目录中有无空闲位置

若有,则进行下一步(4);否则,不成功返回。有的系统可能要为此文件申请数据块空间(申请一部分或一次性全部申请)。

(4)填写目录项内容

包括文件名、用户名、存取权限、长度置零,首地址等

(5)返回

2、指针定位时,系统主要完成以下工作

(1)由 fd检查用户打开文件表,找到对应的人口
(2)将用户打开文件表中文件读写指针位置设为新指针的位置,供后继读写命令存取该指针处文件内容。

文件系统的性能

1、磁盘高速缓存的基本思想

系统在内存中保存一些磁盘块，这些磁盘块在逻辑上属于磁盘，内存的这一区域被称为块高速缓存。
运行时：系统检查所有的读请求,看所需的文件块是否在块高速缓存中。如果在，则可直接在内存中进行读操作;否则,首先要启动磁盘,将所需块读到高速缓存中,再复制到其他内存区域。如果内存中的高速缓存已满,则需要按照一定的算法淘汰一些较少使用的磁盘块，让出块高速缓存空间。

文件共享、保护和秘密

1、文件的共享

一个文件可以允许多个用户共同使用。
文件共享不仅是完成共同任务所必需,而且还带来许多好处:节省文件所占用的存储空间;免除系统复制文件的工作;减少用户大量重复性劳动;减少实际输入输出文件的次数。此外,利用文件共享可以实现进程间相互通信。

2、从共享的时间段上看的有两种使用情况

文件可以同时使用、文件不允许同时使用。

3、在文件共享的具体方式上，文件的共享形式

(1)文件被多个用户使用

由存取权限控制。

(2)文件被多个程序使用

但分别用自己的读写指针

(3)文件被多个程序使用

但共享读写指针。

4、常用的文件保密的措施

规定文件的使用权限在一定程度上可起到文件保密的作用,但是文件的使用权限可由用户设定或修改，因而单靠规定文件的使用权限不能达到文件保密的目的。
常用的文件保密的措施还有以下几种:

(1)隐蔽文件目录

(2)设置口令

(3)使用密码

(4)病毒防范

八、 I/O设备管理

I/0设备管理的基本概念

1、输入输出设备(I/O) 【外部设备(Peripheral)】

有时简称为设备或外设，包括计算机系统中除 CPU 和内存储器以外的所有的设备和装置。例如各种外部存储设备。在不同的上下文中，I/O 设备一词有广义和狭义两种含义,广义的 I/O 设备即上述定义,狭义的I/O设备不包括外存设备。

2、I/O设备管理的任务

(1)I/O 设备的性能经常成为系统性能的瓶颈

CPU 性能越强， I/O 设备性能同CPU性能不匹配的反差也就越大。如何解决这一矛盾是 I/O 设备管理的一项重要任务,操作系统主要通过缓冲技术、中断技术和虚拟技术来解决这一问题。

(2)I/O 设备千变万化,对它们实现统一的管理,从而方便用户使用,是 I/0设备管理的另一项重要任务。

(3)用户对 I/O 设备的使用必须是安全的

对于设备的使用者而言,由设备传送或管理的数据应该是安全和保密的,不能破坏或泄露;对于设备的拥有者而言,多用户多任务环境中的设备使用应该通过协调避免冲突,设备不能被破坏。如何保证安全正确地使用设备，也是设备管理的重要任务。

3、I/O设备分类

(1)按设备的使用特性分类

I/O 设备可分为输入设备、输出设备、交互式设备、存储设备等。

(2)若以系统中信息组织方式来划分设备

可把 I/O设备划分为字符设备和块设备

(3)按设备使用可共享性分类

可分为独占设备、共享设备和虚拟设备等。

I/O硬件和I/O软件的组成

1、I/O硬件组成

从硬件的角度看,I/O硬件由物理设备和电子部件两部分组成。物理设备是达成I/O硬件功能的物质基础,对操作系统而言更注重的是其电子部件的控制方式。

2、I/O软件组成

一般的I/O软件结构分为四层:中断处理程序、设备驱动程序、设备独立的操作系统软件和用户级软件（指在用户空间的I/O软件），从功能上看，设备独立层是I/O软件的主要部分，从代码量上看，设备驱动层是I/O软件的主要部分。

I/O设备控制方式

1、I/0设备的控制方式

(1)程序控制方式。

也称为PIO (Proremmed I/O,程控I/O)方式，是指由用户进程直接控制理器或内存和外周设备之间进行信息传送的方式,也称为”忙一等”方式，轮询方式或循环测试方式,这种方式的控制者是用户进程。

(2)中断控制方式

中断控制方式的处理过程如下;
A)处理器通过数据总线发出命令,启动外设工作,当前进程阻塞,调度程序调度其他进程。
B)外设数据准备好，置位中断请求触发器
C)若此时接口中断屏蔽触发器状态为非屏蔽状态,则接口向处理器发中断请求(IR)
D)处理器接受中断请求，且中断为允许中断状态，则中断判优电路工作。
E)中断判优电路对优先级最高的中断请求给予响应(INTA),处理器中断正在执行的其他进程,转而执行中断服务程序

(3)DMA 控制方式

DMA 方式的数据块传送过程可分为三个阶段:传送前预处理、数据传送、传送后处理。

(4)通道控制方式

按照信息交换方式的不同，一个系统中可以设立三种类型的通道,即选择通道、数组多路通道和字节多路通道。

设备分配与回收

1、在设备分配算法的实现中,常采用的数据结构主要含四张表

1）系统设备表

2）设备控制表

3）控制器控制表

4）通道控制表

2、设备分配的总原则

要充分发挥设备的使用效率,尽可能地让设备忙碌,但又要避免由于不合理的分配方法造成进程死锁

3、独占设备的分配方法

1）设备的绝对号与相对号

2）设备的指定方式

3）独占型设备的分配

4）释放

4、共享设备使用的具体方法

(1)申请设备

如设备被占用,进人设备等待队列,否则分配设备

(2)启动设备

I/0传输。

(3)释放设备

当设备结束,发出中断信号时,系统唤醒一个等待设备的进程

磁盘调度策略

1、信息传输时间

(1)寻找时间

磁头在移动臂带动下移动到指定柱面所花的时间。

(2)延迟时间

指定扇区旋转到磁头下所需的时间。

(3)传送时间

由磁头进行读写完成信息传送的时间。

2、移臂调度算法

1）先来先服务算法

2）最短寻找时间优先算法

3）电梯调度算法

4）单向扫描算法

缓冲技术

1、缓冲技术（根据系统设置的缓冲区的个数）

单缓冲

双缓冲

多缓冲

缓冲池

2、在缓冲池中,有四种工作缓冲区

(1)用于收容设备输人数据的收容输入缓冲区 hin

(2)用于提取设备输人数据的提取输入缓冲区 sin

(3)用于收容处理器输出数据的收容输出缓冲区 hout

(4)用于提取处理器输出数据的提取输出缓冲区 sout

虚拟设备技术

1、虚拟设备技术（SPOOLing 技术）

多道程序设计系统中处理独占I/O设备的一种方法,它可以提高设备利用率并缩短单个程序的响应时间。

2、SPOOLing系统

1）括输人程序模块

2）输出程序模块

3）作业调度程序

文章目录

• 一、操作系统概论
• • 概念
  • • 1、操作系统
    • 2、操作系统特征
    • • 1)并发性
      • 2)共享性
      • 3）虚拟：
      • 4）异步性
    • 3、研究操作系统的观点:
    • 4、操作系统的功能
    • • 1)进程管理(处理器管理)
      • 2)存储管理
      • 3)文件管理
      • 4)设备管理
      • 5）提供用户接口
  • 操作系统的体系结构
  • • 1、体系结构：
    • • (1)Windows操作系统的体系结构。
      • (2)UNIX操作系统的体系结构。
      • (3)Linux操作系统的体系结构。
      • (4)Android 操作系统的体系结构。
  • 操作系统的发展
  • 操作系统分类
  • 操作系统设计
  • • 1、在操作系统设计的过程中主要困难
    • 2、操作系统的设计过程
    • • (1)功能设计。
      • (2)算法设计。
      • (3)结构设计。
    • 3、操作系统的设计目标
    • 4、操作系统结构研究的目标:
    • 5、操作系统的结构:
    • • (1)整体式结构。
      • (2)层次式结构。
      • (3)微内核(客户/服务器)结构。
• 二、操作系统运行环境
• • 处理器
  • • 1 处理器内寄存器
    • 2 指令
    • • 1、指令执行的基本过程:
      • 2、指令的五类
      • • 1）访问存储器指令
        • 2）I/O指令
        • 3）算术逻辑指令（数据处理指令）
      • 4）控制转移指令
      • • 5）处理器控制指令
      • 3、特权指令和非特权指令
      • • 1）特权指令
        • 2）非特权指令
    • 3 管态和目态
    • • • 1）管态
        • 2）目态
    • 4 处理器工作状态的转换
    • • • 1）目态到管态的转换
        • 2）管态到目态的转换
  • 计算机系统硬件部件
  • • 1、存储器的类型
    • • 1）读写型的存储器
      • 2）只读型的存储器
    • 2、存储器的层次结构
    • 4、I/O结构
    • 5、DMA技术（直接内存访问（DMA，Direct Memory Access））
    • 6、缓冲技术
    • 7、时钟部件的原理
  • 中断机制
  • • 1、中断与异常的概念
    • 2、中断与异常的分类
    • • 1）典型的中断
      • • (1)时钟中断
        • (2)输入输出(I/0)中断
        • (3)控制台中断
        • (4)硬件故障中断
      • 2）典型的异常（异常发生的时间以及位置具有确定性）
      • • (1)程序性中断
        • (2)访管指令异常
    • 3、中断的处理
  • 系统调用
  • • 1、系统调用
    • 2、系统调用分类
    • 3、系统调用的处理过程
• 三、进程与线程
• • 多道程序设计
  • • 1、程序的顺序执行的特点
    • • (1)顺序性
      • (2)封闭性
      • (3)程序执行结果的确定性
      • (4)程序执行结果的可再现性
    • 2、程序的并发执行的特点:
    • • (1)在执行期间并发程序相互制约
      • (2)程序与计算不再一一对应。
      • (3)并发程序的执行结果不可再现。
      • (4)程序的并行执行与程序的并发执行。
    • 3、多道程序设计环境特点
    • • (1)独立性
      • (2)随机性
      • (3)资源共享性,
    • 4、多道程序设计的缺陷:
    • • (1)可能延长程序的执行时间
      • (2)系统效率的提高有一定限度
  • 进程
  • • 1、定义
    • 2、进程的特征
    • • (1)并发性
      • (2)动态性
      • (3)独立性
      • (4)交往性
      • (5)异步性
      • (6)结构性
    • 3、三状态进程模型
    • • (1)运行状态
      • (2)就绪状态
      • (3)等待状态
    • 4、五状态进程模型
    • 5、七状态进程模型
    • 6、进程控制块
    • 7、PCB组织方式：
    • • 1）线性方式
      • 2）索引方式
      • 3）链接方式
    • 8、进程的队列
    • • 1）就绪队列
      • 2）等待队列
      • 3）运行队列
    • 9、进程控制原语
    • 10、 UNIX 类操作系统中,父进程通过调用 fork 函数创建子进程。典型的步骤
    • • (1)为子进程分配一个空闲的 proe 结构(即进程描述符)
      • (2)赋于子进程唯一的标识 PID
      • (3)以一次一页的方式复制父进程用户地址空间
      • (4)获得子进程继承的共享资源的指针,如打开的文件和当前工作目录等
      • (5)子进程就绪,加人调度队列
      • (6)对子进程返回标识符 0；向父进程返回子进程的 PID
  • 线程
  • • 1、线程的定义
    • 2、线程实现机制
    • • （1）用户级线程
      • （2）内核级线程
      • （3）混合实现方式
  • 进程调度
  • • 1、进程调度的主要功能
    • 2、进程调度的时机
    • • (1)正在执行的进程运行完毕
      • (2)正在执行的进程于某种错误而终止
      • (3)时间片用完,即有一个进程从运行状态变为就绪状态
      • (4)正在执行的进程调用阻塞原语将自己阻塞起来,即一个进程从运行状态进入阻塞状态。
      • (5)创建了新的进程,即有一个新的进程进入就绪队列。
      • (6)正在执行的进程调用了唤醒原语操作激活了等待资源的进程,即一个等待状态的进程变为就绪状态。
    • 3、进程调度算法
    • • (1)先来先服务算法
      • (2)最短进程优先算法
      • (3)最短剩余时间优先算法
      • (4)最高响应比优先算法
      • (5)轮转算法
      • (6)最高优先级算法
      • (7)多级反馈队列算法
  • 系统内核
  • • 1、系统核心/系统内核【内核】
• 四、进程同步与互斥
• • 进程间相互作用
  • • 1）相关进程
    • 2）无关进程
  • 进程的同步与互斥
  • • 1、进程的同步
    • 2、进程的互斥
    • 3、临界区
    • 4、相关临界区
    • 5、系统对相关临界区的调度使用原则
  • 信号量及P、V操作
  • • 1、信号量
    • 2、P操作和 V操作定义
    • 3、用P、V操作实现进程之间的互斥
    • 4、用P、V操作实现进程之间的同步
  • 经典的进程同步问题
  • • 1、经典的进程同步问题:
    • • (1)简单生产者一一消费者问题
      • (2)多个生产者一一消费者问题
      • (3)读者——写者问题
  • 管程
  • • 1、管程的概念及组成
    • 2、管程具有三个主要的特性
    • • 1）模块化
      • 2）抽象数据类型
      • 3）信息隐蔽
  • 进程通信
  • • 1、解决进程之间的大量信息通信的问题方案
    • • 1）共享内存
      • 2）信息机制
      • 3）管道通信
• 五、死锁
• • 死锁的产生
  • • 1、死锁
    • 2、死锁产生的原因
    • • (1)竞争资源
      • (2)多道程序运行时,进程推进顺序不合理。
    • 3、死锁产生的必要条件
    • • (1)互斥条件
      • (2)不可剥夺条件
      • (3)请求和保持条件
      • (4)循环等待条件
    • 4、解决死锁的方法
    • • 1）预防死锁
      • 2）避免死锁
      • 3）检测与解除死锁
      • 4）忽略死锁
  • 死锁预防
  • • 1、预防死锁的策略
    • • (1)资源的静态分配策略
      • (2)资源的有序分配法
  • 死锁避免
  • • 1、死锁避免的基本思想
    • 2、安全状态与不安全状态
    • • 1）安全状态
      • 2）不安全状态
    • 3、银行家算法
  • 死锁的检测与解除
  • • 1、死锁检测的时机
    • 2、死锁检测的算法
    • 3、死锁的解除方法
    • • (1)剥夺资源
      • (2)撤销进程
  • 资源分配图
  • • 1、资源分配图
    • 2、死锁定理
    • • (1)如果资源分配图中没有环路,则系统没有死锁
      • (2)如果资源分配图中出现了环路,则系统中可能存在死锁
    • 3、资源分配图化简方法
    • • (1)在资源分配图中
      • (2)将P1所释放的资源分配给申请它们的进程即在资源分配图中将这些进程对资源的申请边改为分配边。
      • (3)重复(1)、(2)两步骤,直到找不到符合条件的进程结点。
  • 哲学家就餐问题
• 六、存储管理
• • 存储管理概述
  • • 1、内存空间
    • 2、内存分配有两种方式
    • • (1)静态分配
      • (2)动态分配
    • 3、存储共享
    • • 1）目的
      • • 通过代码共享节省内存空间，提高内在利用率。
        • 通过数据共享实现进程通信。
      • 2）存储保护的内容
    • 4、地址重定位
    • • 1）静态重定位
      • 2）动态重定位
  • 分区管理方案
  • • 1、固定分区
    • 2、可变分区
    • 3、紧缩技术
    • 4、内存分配表
    • • 1）已分配区表
      • 2）空闲区表
    • 5、操作系统查找和分配空闲区的三种分配算法
    • • (1)最先适应算法
      • (2)最优适应算法
      • (3)最坏适应算法
    • 6、分区管理方案的优缺点
    • • 1）优点
      • 2）缺点
  • 覆盖与交换技术
  • • 1、覆盖技术
    • 2、交换技术（对换技术）
  • 虚拟页式存储管理方案
  • • 1、虚拟存储技术的基本思想
    • 2、页式存储管理思想
    • 3、页表
    • 4、页表的分类
    • • (1)多级页表
      • (2)散列页表
      • (3)反置页表
    • 5、转换检测缓冲区(TLB)
    • 6、缺页异常处理过程
    • 7、页面调度策略
    • 8、页面置换算法
    • • (1)理想页面置换算法(OPT)
      • (2)先进先出页面置换算法(FIFO)
      • (3)第二次机会页面置换算法
      • (4)时钟页面置换算法(Clock)
      • (5)最近最少使用页面置换算法(LRU)
    • 9、影响缺页率的因素
    • • (1)分配给程序的物理页面数
      • (2)页面的大小
      • (3)程序编制方法
      • (4)页面调度算法
    • 10、虚拟页式存储管理的优缺点
    • • 1）优点
      • 2）缺点
• 七、文件系统
• • 文件系统的基本概念
  • • 1、文件
    • 2、文件名
    • 3、文件系统
    • • 功能
    • 4、外存储设备的特点
    • 5、文件常用的存取方法
    • • 1）顺序存取
      • 2）随机存取
    • 6、文件的分类
    • • (1)按文件的用途分类
      • (2)按文件的组织形式分类
      • (3)一些常见的文件分类方式
      • (4)UNIX类操作系统中文件的分类
  • 文件的逻辑结构和物理结构
  • • 1、设计文件逻辑结构的原则
    • • 1）易于操作
      • 2）查找快捷
      • 3）修改方便
      • 4）空间紧凑
    • 2、文件的逻辑结构
    • • 1）无结构的字符流式文件
      • 2）定长记录文件
      • 3）不定长记录文件构成的记录树
    • 3、文件的物理结构（逻辑）
    • • (1)顺序结构
      • (2)链接结构
      • (3)索引结构
  • 文件目录
  • • 1、文件控制块的内容
    • 2、文件目录
    • 3、目录项
    • 4、目录文件
    • 5、目录项分解法
    • 6、FAT文件系统三个版本
    • • FAT-12
      • FAT- 16
      • FAT-32
  • 文件存储空间管理
  • • 1、磁盘空间的分配回收算法
    • • (1)位示图
      • (2)空闲块表
      • (3)空闲块链表
    • 2、空闲块成组链接法
  • 实现文件系统的表目
  • • 1、表目
    • 2、在内存中所需的重要表目
    • • 1）系统打开文件表
      • 2）用户打开文件表
  • 文件及文件目录的操作
  • • 1、建立文件的具体步骤如下
    • • (1)检查参数的合法性
      • (2)检查同一目录下有无重名文件
      • (3)在目录中有无空闲位置
      • (4)填写目录项内容
      • (5)返回
    • 2、指针定位时,系统主要完成以下工作
  • 文件系统的性能
  • • 1、磁盘高速缓存的基本思想
  • 文件共享、保护和秘密
  • • 1、文件的共享
    • 2、从共享的时间段上看的有两种使用情况
    • 3、在文件共享的具体方式上，文件的共享形式
    • • (1)文件被多个用户使用
      • (2)文件被多个程序使用
      • (3)文件被多个程序使用
    • 4、常用的文件保密的措施
    • • (1)隐蔽文件目录
      • (2)设置口令
      • (3)使用密码
      • (4)病毒防范
• 八、 I/O设备管理
• • I/0设备管理的基本概念
  • • 1、输入输出设备(I/O) 【外部设备(Peripheral)】
    • 2、I/O设备管理的任务
    • • (1)I/O 设备的性能经常成为系统性能的瓶颈
      • (2)I/O 设备千变万化,对它们实现统一的管理,从而方便用户使用,是 I/0设备管理的另一项重要任务。
      • (3)用户对 I/O 设备的使用必须是安全的
    • 3、I/O设备分类
    • • (1)按设备的使用特性分类
      • (2)若以系统中信息组织方式来划分设备
      • (3)按设备使用可共享性分类
  • I/O硬件和I/O软件的组成
  • • 1、I/O硬件组成
    • 2、I/O软件组成
  • I/O设备控制方式
  • • 1、I/0设备的控制方式
    • • (1)程序控制方式。
      • (2)中断控制方式
      • (3)DMA 控制方式
      • (4)通道控制方式
  • 设备分配与回收
  • • 1、在设备分配算法的实现中,常采用的数据结构主要含四张表
    • • 1）系统设备表
      • 2）设备控制表
      • 3）控制器控制表
      • 4）通道控制表
    • 2、设备分配的总原则
    • 3、独占设备的分配方法
    • • 1）设备的绝对号与相对号
      • 2）设备的指定方式
      • 3）独占型设备的分配
      • 4）释放
    • 4、共享设备使用的具体方法
    • • (1)申请设备
      • (2)启动设备
      • (3)释放设备
  • 磁盘调度策略
  • • 1、信息传输时间
    • • (1)寻找时间
      • (2)延迟时间
      • (3)传送时间
    • 2、移臂调度算法
    • • 1）先来先服务算法
      • 2）最短寻找时间优先算法
      • 3）电梯调度算法
      • 4）单向扫描算法
  • 缓冲技术
  • • 1、缓冲技术（根据系统设置的缓冲区的个数）
    • • 单缓冲
      • 双缓冲
      • 多缓冲
      • 缓冲池
    • 2、在缓冲池中,有四种工作缓冲区
    • • (1)用于收容设备输人数据的收容输入缓冲区 hin
      • (2)用于提取设备输人数据的提取输入缓冲区 sin
      • (3)用于收容处理器输出数据的收容输出缓冲区 hout
      • (4)用于提取处理器输出数据的提取输出缓冲区 sout
  • 虚拟设备技术
  • • 1、虚拟设备技术（SPOOLing 技术）
    • 2、SPOOLing系统
    • • 1）括输人程序模块
      • 2）输出程序模块
      • 3）作业调度程序

一、操作系统概论

概念

1、操作系统

计算机系统中的一个系统软件，他是这样一些程序模块的集合；它们能有效地组织和管理计算机系统中的硬件及软件资源,合理地组织计算机工作流程,控制程序的执行,并向用户提供各种服务功能,使得用户能够灵活、方便、有效地使用计算机,并使整个计算机系统能高效地运行。

2、操作系统特征

1)并发性

并发性是指在计算机系统中同时存在若干个运行着的程序,从宏观上看,这些程序在同时向前推进。
计算机的并发性体现在两个方面：用户程序与用户程序之间并发执行;
用户程序与操作系统程序之间并发执行。

2)共享性

共享性是指操作系统程序与多个用户程序共用系统中的各种资源。这种共享性是在操作系统控制下实现的。
资源的共享性主要针对计算机系统中的如下几项重要资源：中央处理器、内存储器、外存储器、外部设备。在计算机系统中,对资源的共享一般有两种形式:互斥共享和同时共享。

3）虚拟：

是指通过某种技术把一个物理实体变成若干逻辑上的对应物。

4）异步性

即不确定性。同一程序和数据的多次运行可能得到不同的结果;程序的运行时间、运行顺序也具有不确定性;外部输入的请求、运行故障发生的时间难以预测。这些都是不确定性的表现。

3、研究操作系统的观点:

(1)软件的观点。
(2)资源管理的观点。
(3)进程的观点。
(4)虚机器的观点。
(5)服务提供者观点。

4、操作系统的功能

1)进程管理(处理器管理)

进程管理主要包括进程控制、进程同步进程间通信和调度等几方面的内容

2)存储管理

具体包据内存的分配与回收、存储保护和内在扩充三项存储管理功能。

3)文件管理

文件管理的任务是有效地支持文件的存储,检索和修改等操作,解决文件的共享、保密和保护问题,以使用户方便、安全地访问文件。

4)设备管理

设备管理主要完成用户的I/O请求，为用户分配I/O设备。为了完成这些任务，设备管理应具有以下功能：
（1）缓冲管理（2）设备分配（3）设备处理（4）设备独立性和虚拟设备。

5）提供用户接口

具备中断处理、错误处理等功能。操作系统的各功能之间并非是完全独立的,它们之间存在着相互依赖的关系。

操作系统的体系结构

1、体系结构：

(1)Windows操作系统的体系结构。

Windows 体系结构是分层的模块系统，主要层次有硬件抽象层HAL、内核、执行体和大量的子系统集合。

(2)UNIX操作系统的体系结构。

主要包括硬件、内核、系统调用接口、应用程序

(3)Linux操作系统的体系结构。

Linux 系统有四个主要部分，即内核、Shell、文件系统和用户应用程序。内核、Shell和文件系统形成了基本的操作系统结构，它们使得用户可以运行程序、管理文件并使用系统。

(4)Android 操作系统的体系结构。

Android 操作系统分为四层，从高层到低层分别是应用程序层、应用框架层、系统运行库层和 Linux 内核层。
操作系统的发展

操作系统的发展

操作系统的发展过程包括：手工操作、监控程序(早期批处理)、多道批处理、分时与实时系统UNIX通用操作系统、个人计算机操作系统、Andrid 操作系统。

操作系统分类

操作系统分类：按照用户界面的使用环境和功能特征的不同,一般可以把操作系统分为三种基本类型,即批处理系统、分时系统和实时系统。随着计算机体系结构的发展,又出现了许多类型的操作系统,它们是个人操作系统、网络操作系统、分布式操作系统和嵌入式操作系统。

操作系统设计

1、在操作系统设计的过程中主要困难

设计复杂程度高、正确性难以保证和研制周期长等问题。

2、操作系统的设计过程

(1)功能设计。

指的是根据系统的设计目标和使用要求，确定所设计的操作系统应具备哪些功能以及操作系统的类型。

(2)算法设计。

指的是根据计算机的性能和操作系统的功能,来选择和设计满足系统功能的算法和策略,并分析和估算其效能。

(3)结构设计。

指的是按照系统的功能和特性要求,选择合适的结构,使用相应结构设计方法将系统逐步地分解、抽象和综合,使操作系统结构清晰、简明、可靠、易读、易修改,而且使用方便,适应性强。

3、操作系统的设计目标

可靠性(正确性和健壮性)、高效性、易维护性(易读性易扩充性、易剪裁性、易修改性)、可移植性、安全性、简明性

4、操作系统结构研究的目标:

(1)系统模块化。
(2)模块标准化。
(3)通信规范化。

5、操作系统的结构:

(1)整体式结构。

我们把这种操作系统的结构称之为模块组合结构。它的主要优点是,结构紧密,接口简单直接,系统效率较高。模块组合法(或称无序模块法、模块接口法等)的缺点有:第一,模块间转接随便,各模块互相牵连,独立性差,系统结构不清晰。第二,数据基本上作为全程量处理,系统内所有模块的任一程序均可对其进行存取和修改，从而造成了各模块间有着更为隐蔽的关系。第三,由于模块组合结构常以大型表格为中心,为保证数据完整性,往往采用全局封中断办法,从而限制了系统的并发性，系统中实际存在的并发性也未能抽象出明确的概念，缺乏规格的描述方法。所以,这种结构的可适应性比较差。

(2)层次式结构。

层次式结构就是把操作系统的所有功能模块,按功能流图的调用次序,分别将这些模块排列成若干层,各层之间的模块只能是单向依赖或单向调用(如只允许上层或外层模块调用下层或内层模块)关系。

(3)微内核(客户/服务器)结构。

采用客户/服务器结构模式的典型操作系统有卡内基·梅隆大学研制的 Mach操作系统和 Windows NT 的早期版本。这种模式的优点在于,它将系统分成若干个小的并且自包含的分支(服务进程),每个分支运行在独立的用户进程中,相互之间通过规范一致的方式接收发送信息而联系起来。这种体系结构的缺陷主要是对于效率的考虑。

二、操作系统运行环境

处理器

处理器一般由运算器、控制器、一系列的寄存器以及高速缓存构成。其中运算器实现指令中的算术和逻辑运算，是计算机计算的核心。

1 处理器内寄存器

1）用户可见寄存器
2）控制和状态寄存器
通常用户可见寄存器对所有程序都是可用的,由机器语言直接引用。它一般包括数据寄存器(Data Register)、地址寄存器(Address Register)以及条件码寄存器。

2 指令

1、指令执行的基本过程:

1）处理器每次从存储器中读取一条指令并在取指令完成后,根据指令类别自动将程序计数器的值变成下一条指令的地址,通常是自增 1。
2）取到的指令被存储在处理器的指令寄存器中,处理器于是解释并执行这条指令。

2、指令的五类

1）访问存储器指令

负责处理器和存储器之间的数据传送

2）I/O指令

负责处理器和I/O模块之间的数据传送和命令发送

3）算术逻辑指令（数据处理指令）

用以执行有关数据的算术和逻辑操作

4）控制转移指令

可以指定一个新的指令的执行起点

5）处理器控制指令

用于修改处理器状态,改变处理器工作方式等

3、特权指令和非特权指令

1）特权指令

指令系统中那些只能由操作系统使用的指令，有特殊权限的指令。这些指令是不允许一般的用户使用的。

2）非特权指令

用户态下能使用的指令。为了防止用户程序使用特权指令。

3 管态和目态

多数系统将处理器工作状态划分为管态和目态。

1）管态

操作系统管理程序运行的状态,具有较高的特权级别,又称为内核态、特权态(特态)、系统态。

2）目态

用户程序运行时的状态,具有较低的特权级别,又称为用户态、普通态(普态)。

4 处理器工作状态的转换

1）目态到管态的转换

其转换的唯一途径是通过中断。中断响应时交换中断向量，新的中断向量中的 PSW（Program Status Word 程序状态字（也叫程序状态寄存器）） 的处理器状态位标志为管态。

2）管态到目态的转换

通过设置PSW 指令(修改程序状态字),实现从操作系统向用户程序的转换。

计算机系统硬件部件

1、存储器的类型

在微型计算机中使用的半导体存储器有若干种不同的类型。

1）读写型的存储器

可以把数据存入其中任一地址单元,并且可在以后的任何时候把数据读出来,或者重新存人新的数据的一种存储器

2）只读型的存储器

只能从其中读取数据,但不能随意地用普通的方法向其中写人数据。通常要向其中写人数据只能用特殊的方法进行

2、存储器的层次结构

计算机存储系统的设计主要考虑三个问题：容量、速度和成本
从整个系统来看,在计算机系统中的层次化的存储体系由寄存器、高速缓存、内存储器、硬盘存储器、磁带机和光盘存储器等装置构成。

4、I/O结构

在每台外部设备中都配有各自的I/0设备控制器,由I/0设备控制器分别控制各台外部设备的运行。
通道是独立于中央处理器的，专门负责数据1/0传输工作的处理单元。

5、DMA技术（直接内存访问（DMA，Direct Memory Access））

通过系统总线中的一个独立控制单元一一DMA控制器,自动地控制成块数据在内存和1/O单元之间的传送。

6、缓冲技术

用在外部设备与其他硬件部件之间的一种数据暂存技术,它利用存储器件在外部设备中设置了数据的一个存储区域，称为缓冲区。

7、时钟部件的原理

在电路中的晶体振荡器,每隔一定间隔产生固定的脉冲频率，时钟电路中的时钟寄存器依据时钟电路所产生的脉冲数，对时钟寄存器进行加1的工作。
时钟的用途可以分为绝对时钟和相对时钟。

中断机制

1、中断与异常的概念

中断是指处理器对系统中或系统外发生的异步事件的响应。异步事件是指无一定时序关系的随机发生的事件。中断是由外部事件引发的,而异常则是由正在执行的指令引发的。

2、中断与异常的分类

1）典型的中断

(1)时钟中断

由处理器内部的计时器产生,允许操作系统以一定规律执行函数，如时间片到时、硬件实时钟到时等。

(2)输入输出(I/0)中断

由I/O控制器产生,用于通知一个I/O操作的正常完成或者发生的错误。

(3)控制台中断

如系统操作员通过控制台发出命令等。

(4)硬件故障中断

由掉电、存储器校验错等硬件故障引起等.

2）典型的异常（异常发生的时间以及位置具有确定性）

(1)程序性中断

在某些条件下由指令执行结果产生，例如算术溢出、被零除、目态程序试图执行非法指令、访问不被允许访问的存储位置、虚拟存储中的缺页等。

(2)访管指令异常

目的是要求操作系统提供系统服务。

3、中断的处理

I/O中断、时钟中断、硬件故障中断、程序性中断和系统服务请求(自愿性中断)等。

系统调用

1、系统调用

用户在程序中调用操作系统所提供的一些子功能

2、系统调用分类

(1)进程控制类系统调用
(2)文件操作类系统调用
(3)进程通信类系统调用
(4)设备管理类系统调用
(5)信息维护类系统调用

3、系统调用的处理过程

三、进程与线程

多道程序设计

1、程序的顺序执行的特点

(1)顺序性

(2)封闭性

(3)程序执行结果的确定性

(4)程序执行结果的可再现性

2、程序的并发执行的特点:

指一个时间段中有几个程序都处于已启动运行到运行完毕之间，且这几个程序都是在同一个处理机上运行，但任一个时刻点上只有一个程序在处理机上运行。

(1)在执行期间并发程序相互制约

(2)程序与计算不再一一对应。

(3)并发程序的执行结果不可再现。

(4)程序的并行执行与程序的并发执行。

3、多道程序设计环境特点

(1)独立性

(2)随机性

(3)资源共享性,

4、多道程序设计的缺陷:

(1)可能延长程序的执行时间

(2)系统效率的提高有一定限度

进程

1、定义

进程是具有一定独立功能的程序在某个数据集合上的一次运行活动,是系统进行资源分配和调度的一个独立单位。程序是静态的,而进程是动态的。

进程由程序、数据和进程控制块三部分组成。

2、进程的特征

(1)并发性

(2)动态性

(3)独立性

(4)交往性

(5)异步性

(6)结构性

一个进程由程序、数据和进程控制块三部分组成

3、三状态进程模型

(1)运行状态

进程已获得处理器,并且在处理器上执行的状态。显然，在一个单处理器系统中,最多只有一个进处于运行态。

(2)就绪状态

进程已经具备运行条件,但由于没有获得处理器而不能运行所处的状态。一旦把处理器分配给它,该进程就可运行。处于就绪状态的进程可以是多个

(3)等待状态

也称阻塞状态或封锁状态,是指进程因等待某种事件发生而暂时不能运行的状态。

三种基本状态之间的转换：就绪一运行、运行一就绪、运行一等待、等待一就绪

4、五状态进程模型

5、七状态进程模型

6、进程控制块

进程控制块的内容可以分成调度信息和现场信息两大部分

7、PCB组织方式：

PCB进程控制块（PCB Process Control Block）【为了描述控制进程的运行，系统中存放进程的管理和控制信息的数据结构】，它是进程实体的一部分，是操作系统中最重要的记录性数据结构。它是进程管理和控制的最重要的数据结构，每一个进程均有一个PCB，在创建进程时，建立PCB，伴随进程运行的全过程，直到进程撤消而撤消。

1）线性方式

2）索引方式

3）链接方式

8、进程的队列

1）就绪队列

2）等待队列

3）运行队列

9、进程控制原语

创建进程、撤销进程、挂起进程、激活进程、阻塞进程、唤醒进程以及改变进程优先级等。

10、 UNIX 类操作系统中,父进程通过调用 fork 函数创建子进程。典型的步骤

(1)为子进程分配一个空闲的 proe 结构(即进程描述符)

(2)赋于子进程唯一的标识 PID

(3)以一次一页的方式复制父进程用户地址空间

(4)获得子进程继承的共享资源的指针,如打开的文件和当前工作目录等

(5)子进程就绪,加人调度队列

(6)对子进程返回标识符 0；向父进程返回子进程的 PID

线程

1、线程的定义

在引入线程的操作系统中,线程是进程中的一个实体,是处理器调度和分派的基本单位。

2、线程实现机制

（1）用户级线程

（2）内核级线程

（3）混合实现方式

进程调度

1、进程调度的主要功能

记录系统中所有进程的执行状况;根据一定的调度算法，从就绪队列中选出一个进程，准备把处理器分配给它;把处理器分配给进程。

2、进程调度的时机

(1)正在执行的进程运行完毕

(2)正在执行的进程于某种错误而终止

(3)时间片用完,即有一个进程从运行状态变为就绪状态

(4)正在执行的进程调用阻塞原语将自己阻塞起来,即一个进程从运行状态进入阻塞状态。

(5)创建了新的进程,即有一个新的进程进入就绪队列。

(6)正在执行的进程调用了唤醒原语操作激活了等待资源的进程,即一个等待状态的进程变为就绪状态。

3、进程调度算法

(1)先来先服务算法

(2)最短进程优先算法

(3)最短剩余时间优先算法

(4)最高响应比优先算法

响应比 Rp=(等待时间+预计运行时间)/预计运行时间=周转时间/预计运行时间。

(5)轮转算法

轮转(Round-Robin，RR)算法最早来自分时系统

将CPU的处理时间划分成一个个时间片，就绪队列中的诸进程轮流运行一个时间片。当时间片结束时，就强迫运行进程让出CPU,该进程进人就绪队列，等待下一-次调度。同时，进程调度又去选择就绪队列中的一个进程，分配给它一一个时间片，以投人运行。如此轮流调度，使得就绪队列中的所有进程在一个有限的时间T内都可以依次轮流获得一个时间片的处理机时间，从而满足了系统对用户分时响应的要求。

(6)最高优先级算法

(7)多级反馈队列算法

该法综合了先进先出调度算法、时间片轮转算法和可抢占式最高优先级算法的一种进程调度算法。

系统内核

1、系统核心/系统内核【内核】

把操作系统中提供支持系统运行的各种基本操作和基础功能的一组程序模块集中安排,形成一个操作系统的核心

通常,内核只占整个操作系统代码中的一小部分,内核是操作系统中最接近裸机的部分。

四、进程同步与互斥

进程间相互作用

1）相关进程

在逻辑上具有某种联系的进程

2）无关进程

在逻辑上没有任何联系的进程

并发进程相互之间可能是无关的,也可能是相关的。

进程的同步与互斥

1、进程的同步

进程之间一种直接的协同工作关系，一些进程相互合作,共同完成一项任务。

2、进程的互斥

在系统中,许多进程常常需要共享资源，而这些资源往往要求排他性的使用，即一次只能为一个进程服务,因此,各进程间只能互斥使用这些资源,进程间的这种关系就是进程的互斥。

3、临界区

若在系统中某些资源一次只允许一个进程使用,则这类资源成为临界资源或共享变量,而在进程中访问临界资源的程序称为临界区。

4、相关临界区

有若干进程共享某一临界区

5、系统对相关临界区的调度使用原则

(1)当临界区为空时,若有一个进程要求进人临界区,应允许它立即进人临界区—— 有空让进。
(2)若有一个进程已在临界区时,其他要求进入临界区的进程必须等待 ——无空等待
(3)当没有进程在临界区,而同时有多个进程要求进人临界区，只能让其中之一进入临界区,其他进程必须等待一一多中择一
(4)任一进程进人临界区的要求应在有限时间满足一一有限等待
(5)处于等待状态的进程应放弃占用处理器一一让权等待,

信号量及P、V操作

1、信号量

一种特殊的变量,它的表面形式是一个整型变量附加一个队列;而且,它只能被特殊的操作(即 P操作和 V操作)使用。P 操作和 V操作都是原语
设信号量为 S,S可以取不同的整数值。对信号量 S实施的 P操作和 V 操作,可分别用P(S)和 V(S)表示。

2、P操作和 V操作定义

//P操作
P(S)
{
    S=S-1;
    // 若 S<0,将该进程状态置为等待状态,然后将该进程的 PCB 插入相应的 S信号量等待队列末尾,直到有其他进程在 S 上执行 V 操作为止;
}
// V操作
V(S)
{
    S=S+1;
    // 若 S≤0,释放在 S 信号量队列中等待的一个进程,将其状态改变为就绪态，并将其插人就绪队列;然后,执行本操作的进程继续执行;
}

3、用P、V操作实现进程之间的互斥

假设有进程A、B竞争进人临界区，用P,V操作实现进程之间的互斥的程序可以
写成:
进程A 进程B
P(S) P(S)
临界区操作 临界区操作
V(S） V(S)

S的初值为1

4、用P、V操作实现进程之间的同步

考虑一种同步关系,其中有两个信号量 S1,和 S2,赋予它们的初值均为 0,S1,表示在一个缓冲区中是否装满信息,S2表示该缓冲区中信息是否取走。程序可写成:

经典的进程同步问题

1、经典的进程同步问题:

(1)简单生产者一一消费者问题

(2)多个生产者一一消费者问题

(3)读者——写者问题

管程

1、管程的概念及组成

一个管程是一个由过程、变量及数据结构等组成的一个集合,它们组成一个特殊的模块或软件包。一个管程由四个部分组成,它们是管程名称、共享数据的说明、对数据进行操作的一组过程和对共享数据赋初始值的语句

2、管程具有三个主要的特性

1）模块化

2）抽象数据类型

3）信息隐蔽

进程通信

1、解决进程之间的大量信息通信的问题方案

1）共享内存

2）信息机制

包括消息缓冲通信、信箱通信和管道通信

3）管道通信

通过共享文件进行通信

五、死锁

死锁的产生

1、死锁

多道程序系统中的一种现象，一组进程中的每一个进程均无限期地等待被该组进程中的另一个进程所占有且永远不会释放的资源。系统发生这种现象称为系统处于死锁状态,简称死锁。处于死锁状态的进程称为死锁进程。

2、死锁产生的原因

(1)竞争资源

系统资源在分配时出现失误,进程间对资源的相互争夺而造成僵局。
死锁是若干进程因使用资源不当而造成无法推进的现象。
按照资源的使用性质，一般把系统中的资源分成两类:
永久性资源(可重用资源)：是指系统中可供进程重复使用长期存在的资源,如内存、外部设备、处理器等硬件资源,以及各种数据文件、表格、共享程序代码等软件资源;
临时性资源(消耗性资源)：是指由某个进程所产生、只为另一个进程使用一次或经过短暂时间后便不再使用的资源。以上两种资源都可能导致死锁发生

(2)多道程序运行时,进程推进顺序不合理。

3、死锁产生的必要条件

(1)互斥条件

(2)不可剥夺条件

(3)请求和保持条件

(4)循环等待条件

4、解决死锁的方法

1）预防死锁

2）避免死锁

3）检测与解除死锁

4）忽略死锁

死锁预防

指在任何系统操作前(例如分配资源、调度进程等),事先评估系统的可能情况,严格采取措施使得死锁的四个必要条件不成立。死锁预防的基本思想是防范于未然。

1、预防死锁的策略

(1)资源的静态分配策略

(2)资源的有序分配法

采用资源有序分配策略，其基本思想是将系统中所有资源顺序编号。一般原则是：较为紧缺、稀少的资源的编号较大。进程申请资源时，必须严格按照资源编号的顺序进行,否则系统不予分配。即一个进程只有得到编号小的资源,才能申请编号较大的资源;释放资源时,应按编号递减的次序进行。

死锁避免

1、死锁避免的基本思想

系统对进程发出的每一个系统能够满足的资源申请进行动态检查,并根据检查结果决定是否分配资源;如果分配后系统可能发生死锁,则不予分配，否则予以分配。这是一种保证系统不进入死锁状态的动态策略。

2、安全状态与不安全状态

1）安全状态

如果存在一个由系统中所有进程构成的安全序列(P1,… ,Pn),则系统处于安全状态。一个进程序列(P1,… ,Pn)是安全的,如果对于其中每一个进程 Pi(1 ≤ i ≤ n)，它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(j<i)当前占有资源量之和。系统处于安全状态则不会发生死锁。

2）不安全状态

不存在任何一个安全序列

不安全状态不一定导致死锁,但死锁状态一定是不安全状态。即系统若处于不安全状态则可能发生死锁。

3、银行家算法

最著名的死锁避免算法是由 Dijkstra 等人提出来的银行家算法。操作系统按照银行家的规定为进程分配资源，进程首先提出对资源的最大需求量,当进程在执行中每次申请资源时,系统测试该进程已占用的资源与本次申请的资源数之和是否超过了该进程对资源的最大需求量、若超过则拒绝分配资源。若没有超过,则系统再测试来现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。这样做,能保证在任何时刻至少有一个进程可以得到所需要的全部资额而执行结束，执行结束后归还的资源加人到系统的剩余资源中，这些资源又至少可以满足另一个进程的最大需求,于是,可以保证系统中所有进程都能在有限的时间内得到需要的全部资源。

死锁的检测与解除

1、死锁检测的时机

死锁检测可以在任何一次资源分配后，也可以在每次调度后,或者利用定时器定时运行检测,还有一种方法是当系统中某个进程长期位于阻塞态或阻塞进程过多时,启动死锁检测程序。

2、死锁检测的算法

死锁检测的算法依不同的系统而不同

3、死锁的解除方法

(1)剥夺资源

经常使用的方法有:还原算法，即恢复计算结果和状态;建立检查点主要是用来恢复分配前的状态。

(2)撤销进程

撤销死锁进程,将它们占有的资源分配给另一些死锁进程，直到死锁解除为止。

资源分配图

1、资源分配图

资源分配图是一张有向图，一个系统资源分配图 SRAG 可定义为一个二元组,即SRAG=(V,E),其中 V是顶点的集合,而 E是有向边的集合

2、死锁定理

(1)如果资源分配图中没有环路,则系统没有死锁

(2)如果资源分配图中出现了环路,则系统中可能存在死锁

A) 如果处于环路中的每个资源类中均只包含一个资源实例,则环路的存在即意味着死锁的存在。此时，环路是死锁的充分必要条件。
B) 如果处于环路中的每个资源类中资源实例的个数不全为 1，则环路的存在是产生死锁的必要条件而不是充分条件。

3、资源分配图化简方法

(1)在资源分配图中

找出一个既非等待又非孤立的进程结点 P1 ，由于P1可获得它所需要的全部资源，且运行完后释放它所占有的全部资源，故可在资源分配图中消去P1， 所有的申请边和分配边,使之成为既无申请边又无分配边的孤立结点。

(2)将P1所释放的资源分配给申请它们的进程即在资源分配图中将这些进程对资源的申请边改为分配边。

(3)重复(1)、(2)两步骤,直到找不到符合条件的进程结点。

经过化简后,若能消去资源分配图中的所有边，使所有进程都成为孤立结点,则该图是可完全化简的;否则为不可化简的。

哲学家就餐问题

操作系统中关于进程同步与互斥的经典问题,也是涉及死锁的关键问题。

六、存储管理

存储管理概述

1、内存空间

由存储单元(字节或字)组成的一维连续的地址空间,简称内存空间。内存空间一般分为两部分:一部分是系统区,用以存储操作系统常驻内存部分,用户不能占用这部分空间;另一部分是用户区,分配给用户使用,用于装人并存储用户程序和数据,这部分的信息随时都在发生变化。存储管理实质上就是管理供用户使用的那部分空间。

2、内存分配有两种方式

(1)静态分配

程序要求的内存空间是在目标模块连接装入内存时确定并分配的，并且在程序运行过程中不允许再申请或在内存中“搬家”,即分配工作是在程序运行前一次性完成。

(2)动态分配

程序要求的基本内存空间是在目标模块装入时确定并分配的,但是程序运行过程中申请附加的内存空间或在内存中“搬家”,即分配工作可以在程序运行前及运行过程中逐步完成。

3、存储共享

两个或多个进程共用内存中相同区域,这样不仅能使多道程序动态地共享内存，提高内存利用率,而且还能共享内存中某个区域的信息。共享的内容包括代码共享和数据共享,特别是代码共享要求代码必须是纯代码。

1）目的

通过代码共享节省内存空间，提高内在利用率。

通过数据共享实现进程通信。

2）存储保护的内容

保护系统程序区不被用户有意或无意的侵犯；不允许用户想读写不属于自己地址空间的数据,如系统区地址空间、其他用户程序的地址空间。

4、地址重定位

把逻辑地址转换成绝对地址的工作称“地址重定位”或“地址转换”,又称“地址映射”。重定位的方式可以有“静态重定位”和“动态重定位”。

1）静态重定位

内存在装人程序时,要把程序中的指令地址和数据地址全部转换成绝对地址。由于地址转换工作是在程序开始执行前集中完成的，所以在程序执行过程中就无须再进行地址转换工作，这种地址转换方式称“静态重定位”

2）动态重定位

内存在装入程序时,不进行地址转换，而是直接把程序装入到分配的内存区域中。在程序执行过程中,每当执行一条指令时都由硬件的地址转换机构将指令中的逻辑地址转换成绝对地址。这种方式的地址转换是在程序执行时动态完成的,故称为“动态重定位”

分区管理方案

1、固定分区

系统先把内存划分成若干个大小固定的分区，一旦划分好,在系统运行期间便不再重新划分。为了满足不同程序的存储要求,各分区的大小可以不同由于每一分区的大小是固定的,就对可容纳程序的大小有所限制。因此,程序运行时必须提供对内存资源的最大申请量。

2、可变分区

系统不预先划分固定分区,而是在装入程序时划分内存分区,使为程序分配的分区的大小正好等于该程序的需求量,且分区的个数是可变的。显然,可变分区有较大的灵活性,较之固定分区能获得较好的内在利用率。

系统初启后,在内存中除操作系统区之外,其余空间为一个完整的大空闲区。当有型程序要求装人内存运行时,系统从该空闲区中划分出一块与程序大小相同的区域进行分配，当系就运行一段时间后,随着一系列的内存分配和回收。原来的一整块大空用区形成了若干占用区和空用闲区相间的布局。若有上下相邻的两块空闲区,系统应将它们合并成为一块连续的大空闲区。

3、紧缩技术

解决碎片问题的办法是在适当时刻进行碎片整理,通过移动内存中的程序,把所有空闲碎片合并成一个连续的大空闲区且放在内存的一端,而把所有程序占用区放在内存的另一端这一技术称为“紧缩技术”或“压缩技术”

4、内存分配表

由两张表格组成。

1）已分配区表

记录已装入的程序在内存中占用分区的起始地址和长度,用标志位指出占用分区的程序名。

2）空闲区表

记录内存中可供分配的空闲区的起始地址和长度,用标志位指出该分区是未分配的空闲区

5、操作系统查找和分配空闲区的三种分配算法

(1)最先适应算法

又称顺序分配算法,当接到内存申请时,顺序查找分区说明表,找到第一个满足申请长度的空闲区,将其分割并分配。此算法简单,可以快速做出分配决定。

(2)最优适应算法

当接到内存申请时，查找分区说明表,找到第一个能满足申请长度的最小空闲区,将其分割并分配。此算法最节约空间,因为它尽量不分割大的空闲区;其缺点是可能会形成很多很小的空闲区域,称作碎片。

(3)最坏适应算法

当接到内存申请时,查找分区说明表,找到能满足申请要求的最大的空闲区。该算法的基本思想是:在大空闲区中装人信息后,分割剩下的空闲区相对也很大,还能用于装人其他程序。

6、分区管理方案的优缺点

分区管理是实现多道程序设计的一种简单易行的存储管理技术。

1）优点

通过分区管理,内存真正成为了共享资源,有效地利用了处理器和 I/O 设备，从而提高了系统的吞吐量和缩短了周转时间。分区在管理算法比较简单,所采用的表格不多,实现起来比较容易，内存额外开销较少,存储保护措施也很简单。在内存利用率方面,可变分区的内存利用率比固定分区高。

2）缺点

内存使用仍不充分,并且存在着较为严重的碎片问题。虽然可以解决碎片问题,但需要移动大量信息,浪费了处理器时间。此外,分区管理不能为户提供“虚存”,即不能实现对内存的“扩充”,每一个用户程序的存储要求仍然受到物理储器实际存储容量的限制。分区管理要求运行程序一次全部装人内存之后,才能开始运行。这样，内存中可能包含有一些实际不使用的信息。

覆盖与交换技术

1、覆盖技术

一个程序的若干程序段，或几个程序的某些部分共享某一个存储空间。覆盖技术的实现是把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构使那些不会同时执行的程序段共享同一块内存区域。未执行的程序段先保存在磁盘上,当有关程序段的前一部分执行结束后,把后续程序段调入内存,覆盖前面的程序段。

2、交换技术（对换技术）

在分时系统中,用户的进程比内存能容纳的数量要多,这就需要在磁盘上保存那些内存放不下的进程。在需要运行这些进程时,再将它们装人内存。

在实际操作系统中使用交换技术需考虑的问题：换出进程的选择、交换时机的确定交换空间的分配、换人进程换回内存时位置的确定。

虚拟页式存储管理方案

1、虚拟存储技术的基本思想

利用大容量的外存来扩充内存,产生一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间,简称虚存,以便能够有效地支持多道程序系统的实现和大型程序运行的需要,从而增强系统的处理能力。

2、页式存储管理思想

页式存储管理思想首先由英国曼彻斯特大学提出，并在该校的 Atlas 计算机上使用。该技术近年来已广泛用于计算机系统中,支持页式存储管理的硬件部件通常称为“存储管理部件”

3、页表

页表指出该程序虚拟施址中的页号与所占用的物理页面号之间的对应关系。页表的长度由程序拥有的页面数而定,故每个程序的页表长度可能是不同的。
页表又是硬件进行地址转换的依据，每执行一条指令时按虚拟地址中的页号查页表，若页表中无此页号,则产生一个“地址销”的程序性中断事件。若页表中有此页号,则可得到对应的物理页面号,按计算公式可转换成访问的内存的物理地址。

4、页表的分类

(1)多级页表

大多数操作系统中采用二级页表,即由页表页和页目录一起构成进程页表。第一级表示页目录,保存页表页的地址;第二级表示页表页,保存物理页面号。

(2)散列页表

当地址空间大于 32 位时，一种常见的方法是使用以页号为散列值的散列页表。其中每个表项都包含一个链表,该链表中元素的散列值都指向同一个位置。这样,散列页表中的每个表项都包含三个字段:(a)虚拟页号;(b)所映射的页框号;©指向链表中下一个元素的指针。

(3)反置页表

在反置页表中,每个物理页框对应一个表项。每个表项包含与该页框相对应的虚拟页面地址,以及拥有该页面进程的信息。因此，整个系统中只存在一个页表,并且每个页框对应其中一个表项。由于一方面系统中只有一个页表,而另一方面系统中又存在着多个映射着物理内存的地址空间,因此需要在反置页表中存放地址空间标志符。

5、转换检测缓冲区(TLB)

利用高速缓冲存储器存储当前访问最频繁的少数活动页面的页号，这个高速缓冲存储器称为“转换检测缓冲区”,也称为“快表”

6、缺页异常处理过程

(1)根据当前执行指令中的逻辑地址查页表的有效位,判断该页是否在内存。
(2)该页标志为“0”,形成缺页异常。保留现场,中断装置通过交换 PSW 让操作系统的中断处理程序占用处理器。
(3)操作系统处理缺页异常,寻找一个空闲的页面。
(4)若有空闲页，则把磁盘上读出的信息装人该页面中
(5)修改页表及内存分配表,表示该页已在内存。
(6如果内存中无空用面,则按某种算法选择一个已在内存的页面,把它暂时调出存。若在执行中该页面已被修改过,则要把该页信息重新写回到磁盘上，否则不必重新回磁盘、当一页被暂时调出内存后,让出的内存空间用来存储当前需要使用的页面。面被调出或装入之后都要对页表及内存分配表作修改。
(7)恢复现场、重新执行被中断的指令。当重新执行该指令时，由于要访问的页面被装人内存、所以可正常执行下去。

7、页面调度策略

虚拟存储器系统通常定义三种策略来规定如何(或何时)进行页面调度:调入策略(请求调页和预调页)、置页策略和置换策略(固定分配局部换、可变分配全局置换和可变分配局部置换)

8、页面置换算法

(1)理想页面置换算法(OPT)

(2)先进先出页面置换算法(FIFO)

(3)第二次机会页面置换算法

(4)时钟页面置换算法(Clock)

(5)最近最少使用页面置换算法(LRU)

9、影响缺页率的因素

(1)分配给程序的物理页面数

(2)页面的大小

(3)程序编制方法

(4)页面调度算法

10、虚拟页式存储管理的优缺点

1）优点

由于它不要求进程的程序段和数据在内存中连续存放,从而有效地解决了碎片问题。这既提高了内存的利用率,又有利于组织多道程序执行。

2）缺点

存在页面空间的浪费问题。这是由于各种程序代码的长度是各不相同的,但页面的大小是定的,所以在每个程序的最后一页内总有一部分空间得不到利用。如果页面较大,则由此引起的存储空间的损失仍然较大。

七、文件系统

文件系统的基本概念

1、文件

一组带标识的、在逻辑上有完整意义的信息项的序列。

2、文件名

用户在创建文件时确定的,并在以后访问文件时使用。文件名通常由用户给定,它是一个字母数字串,有些系统规定必须是英文字母打头且允许一些其他的符号出现在文件名的非打头部分。

3、文件系统

操作系统中统一管理信息资源的一种软件。它管理文件的存储、检索、更新,提供安全可靠的共享和保护手段,并且方便用户使用。

功能

(1)统一管理文件的存储空间,实施存储空间的分配与回收。
(2)实现文件从名字空间到外存地址空间的映射。即实现文件的按名存取,以对用户透明的方式管理名字空间。
(3)实现文件信息的共享,并提供文件的保护和保密措施。
(4)向用户提供一个方便使用的接口(提供对文件系统操作命令,以及提供对文件的操作命令:信息存取、加工等)。
(5)系统维护及向用户提供有关信息。
(6)保持文件系统的执行效率。
文件系统在操作系统接口中占的比例最大,用户使用操作系统的感觉在很大程度上取决于对文件系统的使用效果。
(7)提供与I/0的统一接口

4、外存储设备的特点

在计算机系统中,外存储设备同内存相比较,一般有容量大、断电后仍可保存信息、速度较慢、成本较低等特点。

5、文件常用的存取方法

1）顺序存取

2）随机存取

6、文件的分类

(1)按文件的用途分类

系统文件、库函数文件、用户文件

(2)按文件的组织形式分类

普通文件、目录文件,特殊文件

(3)一些常见的文件分类方式

A）按文件的保护方式可划分为;只读文件、读写文件、可执行文件、无保护文件
B ）按信息的流向分类可划分为:输人文件、输出文件和输人输出文件等
C）接文件的存放时限可划分为:临时文件、永久文件和档案文件等。

临时文件,及有临时性信息的文件;永久性文件,即其信息需要长期保存的文件;档案文件,即保存在作为“档案”用的磁带或光盘等永久性介质上,以备查证和恢复时使用的文件。

D）按文件所使用的介质类型分类可划分为:磁盘文件、磁带文件、卡片文件和打印文件等，
E）按文件的组织结构分类。

(4)UNIX类操作系统中文件的分类

A)普通文件。这是内部无结构的一串平滑的字符所组成的文件
B)目录文件。这是由文件目录项所构成的文件。
C)特殊文件。在 UNIX 类操作系统中,把 I/O设备也看成是一种文件——特殊文件

文件的逻辑结构和物理结构

1、设计文件逻辑结构的原则

1）易于操作

2）查找快捷

3）修改方便

4）空间紧凑

2、文件的逻辑结构

用户所看到的文件的组织形式。
可以按逻辑结构把文件划分成三类:

1）无结构的字符流式文件

2）定长记录文件

3）不定长记录文件构成的记录树

定长记录文件和不定长记录文件可以统称为记录式文件。

3、文件的物理结构（逻辑）

文件在外存上的存储组织形式,它与存储介质的物理特性、文件的存取方法以及所采用的存储空间的分配方式都有关。

(1)顺序结构

又称连续结构,这是一种最简单的文件物理结构,它把逻辑上连续的文件信息依次存放在连续编号的物理块中。

(2)链接结构

文件的链接结构的实质就是为每个文件构造所使用磁盘块的链表。使用这种链接结构的文件,将逻辑上连续的文件分散存储在若干不连续的物理块中。

(3)索引结构

索引结构的文件把每个物理盘块的指针字,集中存储在称为索引表的数据结构中的内存索引表中。

文件目录

1、文件控制块的内容

文件名、文件号、用户名、文件地址、文件长度、文件类型、文件属性、共享计数、文件的建立日期、保存期限,最后修改日期、最后访问日期、口令、文件逻辑结构、文件物理结构,等等。

2、文件目录

在操作系统中,为了管理大量的文件,为每个文件都设置一个描述性数据结构——文件控制块，把所有文件的文件控制块有机地组织起来,就构成了文件控制块的一个有序集合,称为文件目录。

根据实际的需要,一般把文件目录设计成一级(单级)目录结构、二级目录结构和多领目录结构。

3、目录项

当用户建立一个新文件时,与该文件有关的一些信息与属性记录在该文件的文件控制块内。为了便于管理,通常将文件控制块做成定长数据结构的一个记录,存储在目录文件中。而这样的每一个记录称为目录项。

4、目录文件

多个文件的文件控制块集中在一起组成了文件的目录。通常,文件目录以文件的形式保存起来,这个文件就被称为目录文件。目录文件是每项记录长度固定的记录式文件。

5、目录项分解法

为加快目录检索可采用目录项分解法。
即把目录项分为两部分,符号目录项(次部)和基本目录项(主部)。其中,符号目录项包含文件名以及相应的文件号;而基本目录项包含了除文件名外文件控制块的其他全部信息。

6、FAT文件系统三个版本

取决于用多少二进制位表示磁盘块地址

FAT-12

FAT- 16

FAT-32

文件存储空间管理

1、磁盘空间的分配回收算法

(1)位示图

该法的基本思想是,利用一串二进制位(bit)的值来反映磁盘空间的分配使用情况

(2)空闲块表

空闲块表是专门为空闲块建立的一张表,该表记录外存储器全部空闲的物理块:包括每个空闲块的第一个空闲物理块号和该空闲块中空闲物理块的个数

(3)空闲块链表

将外存储器中所有的空闲物理块连成一个链表,用一个空闲块首指针向第一个空闲换,随后的每个空闲块中都含有指向下一个空闲快的指针，最后一块的指针为空，表示链尾,这样就构成了一个空闲块链表。

2、空闲块成组链接法

对链接表的一个改进方案是将 n 个空闲盘块的地址存储在第一个空闲块中。其余n-1个空闲盘块是实际空闲的。假设每 100 个空闲块为一。第一组的 100 个空闲块块号放在第二组的头一块中，而第二组的其余 99 块是完全空闲的。第二组的 100 个块号又放在第三组的头一块中，依次类推,组与组之间形成链接关系。在最后一组的块号中第2个单元填“0”,表示该块中指出的块号是最后一组的块号,空闲块链到此结束。在这个空闲块链中,不足 100块的一个组的块号,通常放在内存的一个专用块中。这种方式称为成组链接。

实现文件系统的表目

1、表目

当用户申请打开一个文件时,系统要在内存中为该用户保存一些必要的信息，这些信息以表格栏目中内容的形式出现。

2、在内存中所需的重要表目

1）系统打开文件表

2）用户打开文件表

文件及文件目录的操作

1、建立文件的具体步骤如下

(1)检查参数的合法性

文件名是否符合命名规则,若是,则进行下一步(2);否则报错,返回。

(2)检查同一目录下有无重名文件

若没有,则进行下一步(3);否则报错,返回。

(3)在目录中有无空闲位置

若有,则进行下一步(4);否则,不成功返回。有的系统可能要为此文件申请数据块空间(申请一部分或一次性全部申请)。

(4)填写目录项内容

包括文件名、用户名、存取权限、长度置零,首地址等

(5)返回

2、指针定位时,系统主要完成以下工作

(1)由 fd检查用户打开文件表,找到对应的人口
(2)将用户打开文件表中文件读写指针位置设为新指针的位置,供后继读写命令存取该指针处文件内容。

文件系统的性能

1、磁盘高速缓存的基本思想

系统在内存中保存一些磁盘块，这些磁盘块在逻辑上属于磁盘，内存的这一区域被称为块高速缓存。
运行时：系统检查所有的读请求,看所需的文件块是否在块高速缓存中。如果在，则可直接在内存中进行读操作;否则,首先要启动磁盘,将所需块读到高速缓存中,再复制到其他内存区域。如果内存中的高速缓存已满,则需要按照一定的算法淘汰一些较少使用的磁盘块，让出块高速缓存空间。

文件共享、保护和秘密

1、文件的共享

一个文件可以允许多个用户共同使用。
文件共享不仅是完成共同任务所必需,而且还带来许多好处:节省文件所占用的存储空间;免除系统复制文件的工作;减少用户大量重复性劳动;减少实际输入输出文件的次数。此外,利用文件共享可以实现进程间相互通信。

2、从共享的时间段上看的有两种使用情况

文件可以同时使用、文件不允许同时使用。

3、在文件共享的具体方式上，文件的共享形式

(1)文件被多个用户使用

由存取权限控制。

(2)文件被多个程序使用

但分别用自己的读写指针

(3)文件被多个程序使用

但共享读写指针。

4、常用的文件保密的措施

规定文件的使用权限在一定程度上可起到文件保密的作用,但是文件的使用权限可由用户设定或修改，因而单靠规定文件的使用权限不能达到文件保密的目的。
常用的文件保密的措施还有以下几种:

(1)隐蔽文件目录

(2)设置口令

(3)使用密码

(4)病毒防范

八、 I/O设备管理

I/0设备管理的基本概念

1、输入输出设备(I/O) 【外部设备(Peripheral)】

有时简称为设备或外设，包括计算机系统中除 CPU 和内存储器以外的所有的设备和装置。例如各种外部存储设备。在不同的上下文中，I/O 设备一词有广义和狭义两种含义,广义的 I/O 设备即上述定义,狭义的I/O设备不包括外存设备。

2、I/O设备管理的任务

(1)I/O 设备的性能经常成为系统性能的瓶颈

CPU 性能越强， I/O 设备性能同CPU性能不匹配的反差也就越大。如何解决这一矛盾是 I/O 设备管理的一项重要任务,操作系统主要通过缓冲技术、中断技术和虚拟技术来解决这一问题。

(2)I/O 设备千变万化,对它们实现统一的管理,从而方便用户使用,是 I/0设备管理的另一项重要任务。

(3)用户对 I/O 设备的使用必须是安全的

对于设备的使用者而言,由设备传送或管理的数据应该是安全和保密的,不能破坏或泄露;对于设备的拥有者而言,多用户多任务环境中的设备使用应该通过协调避免冲突,设备不能被破坏。如何保证安全正确地使用设备，也是设备管理的重要任务。

3、I/O设备分类

(1)按设备的使用特性分类

I/O 设备可分为输入设备、输出设备、交互式设备、存储设备等。

(2)若以系统中信息组织方式来划分设备

可把 I/O设备划分为字符设备和块设备

(3)按设备使用可共享性分类

可分为独占设备、共享设备和虚拟设备等。

I/O硬件和I/O软件的组成

1、I/O硬件组成

从硬件的角度看,I/O硬件由物理设备和电子部件两部分组成。物理设备是达成I/O硬件功能的物质基础,对操作系统而言更注重的是其电子部件的控制方式。

2、I/O软件组成

一般的I/O软件结构分为四层:中断处理程序、设备驱动程序、设备独立的操作系统软件和用户级软件（指在用户空间的I/O软件），从功能上看，设备独立层是I/O软件的主要部分，从代码量上看，设备驱动层是I/O软件的主要部分。

I/O设备控制方式

1、I/0设备的控制方式

(1)程序控制方式。

也称为PIO (Proremmed I/O,程控I/O)方式，是指由用户进程直接控制理器或内存和外周设备之间进行信息传送的方式,也称为”忙一等”方式，轮询方式或循环测试方式,这种方式的控制者是用户进程。

(2)中断控制方式

中断控制方式的处理过程如下;
A)处理器通过数据总线发出命令,启动外设工作,当前进程阻塞,调度程序调度其他进程。
B)外设数据准备好，置位中断请求触发器
C)若此时接口中断屏蔽触发器状态为非屏蔽状态,则接口向处理器发中断请求(IR)
D)处理器接受中断请求，且中断为允许中断状态，则中断判优电路工作。
E)中断判优电路对优先级最高的中断请求给予响应(INTA),处理器中断正在执行的其他进程,转而执行中断服务程序

(3)DMA 控制方式

DMA 方式的数据块传送过程可分为三个阶段:传送前预处理、数据传送、传送后处理。

(4)通道控制方式

按照信息交换方式的不同，一个系统中可以设立三种类型的通道,即选择通道、数组多路通道和字节多路通道。

设备分配与回收

1、在设备分配算法的实现中,常采用的数据结构主要含四张表

1）系统设备表

2）设备控制表

3）控制器控制表

4）通道控制表

2、设备分配的总原则

要充分发挥设备的使用效率,尽可能地让设备忙碌,但又要避免由于不合理的分配方法造成进程死锁

3、独占设备的分配方法

1）设备的绝对号与相对号

2）设备的指定方式

3）独占型设备的分配

4）释放

4、共享设备使用的具体方法

(1)申请设备

如设备被占用,进人设备等待队列,否则分配设备

(2)启动设备

I/0传输。

(3)释放设备

当设备结束,发出中断信号时,系统唤醒一个等待设备的进程

磁盘调度策略

1、信息传输时间

(1)寻找时间

磁头在移动臂带动下移动到指定柱面所花的时间。

(2)延迟时间

指定扇区旋转到磁头下所需的时间。

(3)传送时间

由磁头进行读写完成信息传送的时间。

2、移臂调度算法

1）先来先服务算法

2）最短寻找时间优先算法

3）电梯调度算法

4）单向扫描算法

缓冲技术

1、缓冲技术（根据系统设置的缓冲区的个数）

单缓冲

双缓冲

多缓冲

缓冲池

2、在缓冲池中,有四种工作缓冲区

(1)用于收容设备输人数据的收容输入缓冲区 hin

(2)用于提取设备输人数据的提取输入缓冲区 sin

(3)用于收容处理器输出数据的收容输出缓冲区 hout

(4)用于提取处理器输出数据的提取输出缓冲区 sout

虚拟设备技术

1、虚拟设备技术（SPOOLing 技术）

多道程序设计系统中处理独占I/O设备的一种方法,它可以提高设备利用率并缩短单个程序的响应时间。

2、SPOOLing系统

1）括输人程序模块

2）输出程序模块

3）作业调度程序