第章 操作系统概述 3
操作系统定义 3
二 区程序发程序行 3
三 操作系统硬件环境 3
第二章 进程线程作业 5
吞吐量 5
二 进程概念 5
三 进程状态状态转换 5
四 进程控制块 6
五 进程组成 6
六 进程队列 6
七 线程概念 7
八 线程控制块 7
九 线程实现 8
十 作业 8
十 作业进程线程三者间关系 9
第三章 中断处理器调度 10
概述 10
二 中断概念 10
三 中断装置 10
四 中断处理程序 11
五 处理器调度 12
六 处理器调度算法 12
七 常处理器调度算法（八） 13
八 调度级级调度 17
第四章 互斥步通信 19
进程互斥 19
二 享变量界区 19
三 界区进程互斥 19
四 进程步 19
五 进程步机制 20
六 信号灯PV操作相关定义 20
七 信号灯PV操作应 22
八 信号灯变量解决综合问题——生产者—消费者问题 23
九 信号灯变量解决综合问题——读者—写者问题 26
十 信号灯变量解决综合问题——哲学家餐问题 28
十 信号灯变量解决综合问题——三台印机理 30
十二 信号灯变量解决综合问题——吸烟者问题 30
十三 进程高级通信分类概念模式 32
十四 进程通信消息传递模式两种实现方式 32
第五章 死锁饥饿 36
死锁概念 36
二 关死锁结（4） 36
三 死锁类型 36
四 死锁条件（4） 36
五 死锁处理 37
六 银行家算法（掌握思想需写） 37
七 饥饿活锁 40
八 死锁饥饿例子——独木桥问题 41
九 死锁饥饿例子——河问题 44
十 系统举例 45
第六章 存储理 46
存资源理 46
二 存储理方式（三张图非常重） 48
三 虚拟存储系统（注意颠簸页障率反馈模型） 48
第七章 文件系统 52
文件概念 52
二 文件组织 52
三 文件控制块 55
四 文件系统实现 56
第八章 设备输入输出理 58
设备分类 58
二 数传输方式——通道方式 58
三 设备驱动 59
四 虚拟设备 59
第章 操作系统概述
操作系统定义
操作系统位硬件层系统软件层系统软件理系统中种软件硬件资源充分利方便户计算机系统
二 区程序发程序行
程序行求微观时绝时刻程序时前推进
程序发求微观时需宏观程序前推进
发：宏观时运行微观交运行
三 操作系统硬件环境
a) 定时装置
1 绝时钟
时间表示形式年月日时分秒开机时电源供电计时关机时机电池供电计时
操作系统绝时钟记录作业进入系统处理时间文件修改存取时间资源占时间日志记录时间等
2 间隔时钟
称闹钟间隔固定时间发生次时钟中断时系统获控制权便运行系统理实现程序发
中断系统发必条件间隔时钟现代操作系统基础
利间隔时钟实现逻辑时钟
b) 系统栈
1 位置
存中操作系统空间固定区域
2 途
1 中断响应时保存中断现场
2 保存操作系统子程序间相互调参数值返回值返回点子程序局部变量
c) 特权指令非特权指令
1 特权指令
态执行
指令执行仅影响运行程序身会影响程序甚整系统
eg 开关中断修改址映射寄存器置程序状态字PSW停机
2 非特权指令
态目态均执行指令称非特权指令指令执行运行程序身关影响程序操作系统
eg 数传送指令算术运算指令
d) 处理器状态状态转换
1 处理器状态
硬件通常分态目态两种状态程序状态字PSW中位进行标识
1 态
态称系统态核心态操作系统运行时处状态计算机处态时执行硬件提供全部指令包括特权指令非特权指令
利特权指令修改程序状态字机器状态程序状态字部分态改变机器状态进入目态
2 目态
目态称户态般户程序运行时处状态处理器处目态时执行硬件机器指令子集非特权指令
旦户目态执行特权指令硬件产生中断进入操作系统特权指令执行制止
置程序状态字特权指令目态程序运行状态转换态
2 状态转换
1 目态态转换
处理器状态目态转换态唯途径中断
2 态目态转换
通修改程序状态字（置PSW）实现
操作系统运行态户程序运行目态种状态转换伴着操作系统户程序转换
e) 中断装置
1 定义
发现响应中断硬件机构称中断装置
2 功
1 发现中断
中断发生时够识
中断事件时发生时优先级响应高级者
2 响应中断
目前运行进程中断量PSWPC压入系统栈然根中断原指定存单元新中断量取出送寄存器中控制转相应中断处理程序
第二章 进程线程作业
吞吐量
衡量系统效率尺度吞吐量
系统吞吐量定义单位时间系统处理作业（程序）道数（数量）：
吞吐量作业道数全部处理时间
吞吐量系统处理器等资源利率密切关系提高系统吞吐量应提高系统资源利率入手
二 进程概念
进程具定独立功程序关数集合次运行活动
三 进程状态状态转换
a) 进程生存期
进程生成执行结束段时间进程生存期
b) 进程状态
进程生存期处3中基状态
1 运行态（run）
进程占处理器资源正运行
（占CPU单处理器系统中时刻进程处种状态）
2 绪态（ready）
进程身具备运行条件处理器数量少运行进程数量暂未投入运行相等处理器资源
（未CPU）
3 等态（wait）
称挂起态封锁态睡眠态进程身具备运行条件分配处理器运行
进程正等某事件发生等某资源释放等该进程相关数传输完成信号等
c) 状态转换
绪进程获处理器时状态绪态变运行态
运行进程剥夺处理器资源时完系统分时间片者出现高优先级进程状态运行态变绪态
运行进程某事件受阻时申请资源占启动数传输未完成状态运行态变等态
等事件发生时申请资源数传输完成状态等态变绪态
图 进程间基状态转换关系
四 进程控制块
a) 定义
进程控制块（Process Control BlockPCB）标志进程存数结构中包含系统进程进行理需全部信息
b) 作
道程序系统中运行程序需断点现场保存区域区域设进程控制块中
进程控制块进程存标志组信息构成
进程标识： 通常整数称进程号进程号唯户号相应
户标识： 通常整数称户号户号进程号相应
进程状态： 绪运行等间动态变化
调度参数： 确定运行进程
现场信息： 保存进程暂停断点信息包括通寄存器PSWPC
家族联系： 记载进程父进程
程序址： 记载进程应程序存储位置占存储空间
前开文件： 记载进程正文件
消息队列指针： 指进程进程接收消息构成消息队列链头
资源情况： 记载该进程生存期间系统资源时间
进程队列指针： 构建进程控制块队列系统理进程需
五 进程组成
进程两部分组成进程控制块程序中程序包括代码数等
a) 进程控制块
进程控制块进程灵魂
进程控制块放系统空间中操作系统够进行存取
b) 程序
程序进程躯体中包括代码数两部分
c) 系统开销（system overhead）
系统开销般指运行操作系统程序系统进程理花费时间空间
六 进程队列
进程控制块进程代表进程队列实际进程控制块构成队列
该队列通常链形式实现称PCB链
a) 绪队列
般整系统中绪队列
b) 等队列
等事件等队列系统中根等事件等队列等输入设备队列等输出设备队列等
c) 运行队列
单处理器系统中运行队列处理器系统中CPU运行队列
队列中进程
图 进程队列模型
七 线程概念
a) 定义
线程(thread)称轻进程进程相独立执行流
进程包含线程线程执行程序中相代码段代码段享数区堆
般认进程资源分配单位线程CPU调度单位
b) 线程相进程优点
1 文切换速度快
进程中线程切换线程需改变寄存器栈包括程序数址空间变
2 系统开销
创建线程创建进程需完成工作少
3 通信容易
进程中线程享址空间线程写数空间信息直接该进程中线程读取便通信
八 线程控制块
a) 定义
线程控制块(thread control block TCB)标志线程存数结构中包含系统线程进行理需全部信息
b) 组成
线程标识
线程状态
调度参数
现场（通寄存器指令计数器户栈指针）
链接指针
线程控制块属操作系统空间属户进程空间（运行系统理）取决线程实现方式
九 线程实现
线程两种实现方式：目态实现户级线程态实现核心级线程
a) 户级线程
1 户级线程线程相关控制结构——线程控制块保存目态空间中运行系统进行维护
2 线程操作系统见系统调度进程单位核心栈数进程数相应
3 优点
1 线程赖操作系统采问题相关调度策略灵活性
2 进程中线程切换需进入操作系统实现效率较高
4 缺点
3 进程中线程真正行处理器环境中
4 线程操作系统见调度进程级某进程中线程通系统调进入操作系统受阻该进程线程运行
b) 核心级线程
1 核心级线程线程控制块保存操作系统空间线程状态转换操作系统完成线程CPU调度基单位
2 系统调度线程单位操作系统需线程保持核心栈
3 核心级线程进程状态具实际意义省略
4 优点：发性处理器环境中意进程线程真正行执行
5 缺点：线程控制状态转换需进入操作系统完成系统开销较
十 作业
a) 定义
户求计算机系统完成计算务集合称作业(job)
（里计算务广义计算务）
般说作业进程概念
b) 作业步(job step)
作业通常包含计算步骤作业中相独立处理步骤称作业步
作业步间具序发关系
c) 作业进程关系
作业步通常进程完成样作业存处理时通常进程相应作业进程间具关系
d) 作业控制块
作业控制块(job control block JCB)标志作业存数结构中包含系统作业进行理需全部信息
e) 关批处理作业基概念
1 作业控制语言JCL：描述批处理作业控制意图语言
类C语言
2 作业说明书：JCL语句序列（作业说明书般特殊符号起始）
类C语言写程序
3 作业控制程序：解释处理作业说明书程序
类编译器程序
4 作业控制进程：执行作业控制程序进程
f) 批处理作业——作业控制程序
作业假脱机输入程序(SPOOLing 输入程序)控制进入输入井操作系统作业调度程序选择进入存建立作业控制进程
作业控制进程解释作业说明书语句根作业步求建立进程
图 作业控制程序工作原理 （批处理作业）
g) 交互式作业——系统passwd文件
分时系统说通常分时户次登录称作业
次登录系统提出请求请求应进程样分时作业进程间关系
分时系统中通设置口令文件实现分时户理UNIX系统该文件保存etcpasswd中Passwd文件中包含注册户信息
图 系统passwd文件 （交互式作业）
十 作业进程线程三者间关系
a) 作业进程关系进程线程关系
b) 作业进程
作业进入存变进程作业进程相应
进程实现作业完成功
c) 进程线程
支持线程系统中进程视单线程进程
支持线程系统中进程包含线程少包含线程
第三章 中断处理器调度
概述
中断实现道程序设计必条件
果没中断操作系统法获系统控制权处理器资源分配进程
二 中断概念
程序运行程中出现某种紧急事件必须中止前正运行程序转处理事件然恢复原运行程序程称中断
中断实现需硬件软件合作硬件部分称中断装置软件部分称中断处理程序中断装置中断处理程序称中断系统
三 中断装置
a) 定义
中断装置发现响应中断硬件机构
b) 中断装置发现响应中断步骤
1 识中断源
引起中断事件称中断源
中断源存时中断装置选择优先级高中断源
2 保存中断现场
正运行进程程序状态字PSW指令计数器PC中容压入系统栈（存中）
3 转入中断处理程序
中断事件应中断量存指定单元取出送入PSWPC中便转入应中断处理程序
图 中断响应程
c) 中断源中断字
引起中断事件称中断源
保存中断事件相关信息寄存器称中断寄存器
中断寄存器中容称中断字
d) 中断类型
1 强迫性中断
类中断正运行程序期运行程序意位置断
1 时钟中断：时钟时
2 输入输出中断：设备出错传输结束等
3 控制台中断：系统操作员通控制台发出命令
4 硬件障中断：掉电存校验错误等
5 程序错误中断：目态程序执行特权指令址越界溢出数0虚拟存储中缺页障等
2 愿性中断
类中断事件正运行程序意识安排执行访指令引起目求系统提供某种服务
例：C程序中fpfopen(…txt r+w)语句
e) 中断量
中断处理程序入口址(PC)运行环境(PSW)存放存中固定单元处中断事件发生时中断装置利PSWPC转入应中断处理程序类似量转移
PSWPC称中断量
图 中断量中断处理程序
注意：
1 类中断事件中断量
2 中断量存放位置硬件规定
3 中断量容OS系统初始化时设置
f) 中断嵌套
系统处理中断事件程中响应新中断称发生中断嵌套
般允许优先级更高中断事件断前中断事件处理程中断嵌套实际层数般会超中断优先级数
四 中断处理程序
进入中断处理程序般需进步保存现场
中断装置响应中断通中断量转入中断处理程序
中断处理程序需根中断码进步分析中断源进行相应处理根情况决定否需切换进程
a) 中断处理程序结构
1 关中断（屏蔽中断）
进步保存现场（址寄存器通寄存器等）
2 开中断（开放高优先级中断）
3 中断处理
4 恢复现场
5 中断返回
b) 中断处理整程
（CPU中断处理完成决定资源交进程）
c) 中断续元
户编中断处理程序称中断续元
中断续元入口址称中断续元入口
五 处理器调度
a) 定义
处理器调度(CPU scheduling)指CPU资源运行实体间分配
b) 分配
支持线程系统中OSCPU分配进程
支持线程系统中系统级线程OSCPU资源分配线程
户级线程OSCPU资源分配进程
六 处理器调度算法
（考计算知道算法原理意义特点）
a) 概述
处理器调度算法确定处理器空闲时应选择绪态进程投入运行
b) 选择处理器调度算法时指标
1 CPU利率：CPU量处忙碌状态
2 吞吐量：单位时间处理计算务数量
3 周转时间：计算务绪处理完毕时间
4 响应时间：务绪开始处理时间
5 系统开销：系统调度进程程中付出时空代价
c) 衡量绪务处理效率度量标准
1 周转时间(turnaround time)：绪开始时刻处理完毕时刻时间
2 均周转时间(average …)：进程周转时间进程数值
3 等时间：周转时间处理时间差
4 均等时间：进程等时间进程数值
d) 处理器调度时刻
1 非剥夺式调度(nonpreemptive)
1 指进程正运行进程里抢占CPU
2 采非剥夺式调度方式时进程旦选中运行直运行直出现情形：(1)该进程某种事件等(2)该进程运行完毕
3 优点：系统开销较
4 缺点：保证前正运行进程永远系统前运行进程中优先数高进程
2 剥夺式调度(preemptive)
1 指进程正运行进程里抢占CPU
2 采剥夺式调度方式时发生情形导致进程切换
(1)运行进程某种事件等 (2)运行进程运行完毕
(3)出现新优先级高正运行进程绪进程
新绪进程某进程唤醒动态创建新进程
3 优点：保证正运行进程永远系统前运行进程中优先级高进程
4 缺点：CPU进程间频繁切换系统开销较
七 常处理器调度算法（八）
a) 先先服务算法（非剥夺式）
1 基思想
先先服务(first come first serve FCFS)算法进程申请CPU次序（进程进入绪态次序）进行调度
2 优点
具公性会出现饿死情况
3 缺点
短进程（线程）等时间长导致均等时间较长
4 例子
b) 短作业优先算法（非剥夺式）
1 基思想
短作业优先算法(shortest job first SJF)算法CPU阵发时间递增次序调度易证明均周转（等）时间短（证明见作业二）
SJF算法中长短指CPU阵发时间长短
2 优点
务时达时均周转时间短限度降低均等时间
3 缺点
具公性较长绪务短务停达长期运行机会发生饥饿甚饿死
4 例子
c) 短剩余时间优先算法（剥夺式）
1 基思想
短剩余时间优先算法(shortest remaining time next SRTN)算法执行操作：
1 CPU空闲时选择剩余时间短线程进程
2 新进程线程达时较新进程前运行进程估计剩余时间果新进程需运行时间时间短切换运行进程
2 实质
该算法实质剥夺形式短作业优先算法效增加系统吞吐量
d) 高响应优先算法（非剥夺式）
1 基思想
高响应优先算法(highest response ratio next HRN)算法先先服务算法短作业优先算法折中响应次序调度
2 响应计算公式
RRBT+WTBT1+WTBT
中RR响应BTCPU阵发时间WT等时间
显然时达务处理时间较短务优先调度处理时间较长务着等时间增加动态提升响应会出现饥饿现象
3 缺点
系统开销较时常计算进程响应
e) 高优先数优先算法
1 基思想
高优先数优先(highest priority first HPF)算法进程PCB块中数字表示优先数需进行处理器分配时系统运行进程中选择优先数高者投入运行
2 优先数确定方法
1 静态优先数
进程创建时赋予优先数 该优先数进程整生存期固定变
优点：较简单 开销较
缺点：公性差 造成低优先数进程长期等
静态优先数法适合批处理进程
2 动态优先数
进程创建时赋予优先数该优先数进程生存期动态变化
进程获某种资源时优先级应增高进程处绪状态时优先级应着等时间增长提高等动态优先数算法适实时系统
优点：资源利率高公性
缺点：开销较实现较复杂
3 处理机调度时刻
1 非剥夺式静态优先数
获CPU进程直运行直终止等
2 剥夺式动（静）态优先数
获CPU进程运行直终止等出现高优先级进程
f) 循环轮转算法（剥夺式）
1 基思想
循环轮转(round robin RR)算法系统进程规定时间片(time slice)进程时间片长短轮流运行
2 调度程
采循环轮转算法时绪进程排成队列
处理机空闲时便选择队列头部进程投入运行时分时间片时间片完时果进程未结束CPU阵发未某种原等剥夺进程占处理机排绪队列尾部选择绪队列中队头进程运行
3 时间片
采循环轮转法进行调度时时间片长度需认真加考虑
果时间片长会影响系统响应速度
果短会频繁发生进程切换增加系统开销
通常时间片长度十毫秒百毫秒
4 优点
循环轮转法特适分时系统具公性响应时等特点
g) 分类排队算法
1 基思想
分类排队(multi level queues MLQ)算法称级队列法绪队列特征队列系统中运行进程某种原加分类实现某种调度目标
2 例子
例通操作系统中绪进程排成三队列：
Q1 实时绪进程队列
Q2 分时绪进程队列
Q3 批处理绪进程队列
处理机空闲时首先选择Q1中进程Q1空选择Q2中进程Q1Q2均空选择Q3中进程
队列部分采调度算法
h) 反馈排队算法
1 基思想
分类排队算法中进程绪队列间移动
反馈排队算法(feed back FB)绪队列特征队列部采循环轮转算法分类排队算法进程绪队列间移动
绪队列优先级次递减时间片长度次递增
图 反馈排队算法
进程创建者等时间发生时进入第级绪队列
某队列进程获处理器完该队列应时间片果尚未结束进入级绪队列
2 特点
1 短进程优先处理
运行时间短进程前面队列便已执行完队列中进程优先调度
2 设备资源利率高
设备交道进程会面原进入等状态：
(a) 申请资源占(b)启动IO传输
进程等资源IO传输完成时进入第级绪队列快获CPU资源
3 系统开销较
运行时间长进程进入优先级低队列队列时间片较长进程调度频率较低
3 缺点
反馈排队法中果高优先级队列直空低优先级队列中进程长时间运行机会便会发生饿死现象
解决问题常根某种原允许低优先级队列中进程移高优先级队列中助动态优先数算法调整序
4 优点
反馈排队算法适应性(adaptive)调度例子
八 调度级级调度
a) 处理器调度低级调度
处理器调度称低级调度(lowlevel scheduling)短程调度(short term scheduling)处理器资源分配进程线程真正前推进
低级调度中级调度高级调度起构成级调度
b) 交换中级调度
1 交换
交换(swapping)进程存外存储器间调度
交换目标般两：
1 缓解存空间等资源紧张矛盾
2 减发度降低系统开销
提高发度提高资源利率提高系统效率发度越高越
发度高会导致激烈资源竞争进程常等进程占资源降低进程推进速度甚导致死锁发度高会导致CPU资源进程线程间频繁切换增加系统开销
2 中级调度
中级调度(middlelevel scheduling)系统控制发度调度级
系统发度高时存中某进程暂时交换外存储器系统发度较低时调回存
图 具中级调度进程状态转换关系
（外存中进程等态绪态转换外存中直接完成）
c) 作业高级调度
1 作业调度
作业调度(job scheduling)称高级调度长程调度职作业输入井调入存建立相应进程具运行资格
2 作业五状态
提交状态：输入机输入井传输作业处提交状态
备状态：已进入输入井未调入存作业处备状态
执行状态：作业调度选中进入存处理作业处执行状态
(作业分解进程)
完成状态：处理完毕结果输出井作业处完成状态
退出状态：输出井印设备传送作业处退出状态
3 作业状态间转换
提交>备：SPOOLing输入进程完成
备>执行：作业调度程序(1)完成
执行>完成：作业调度程序(2)完成
完成>退出：SPOOLing输出进程完成
图 作业状态转换关系
作业调度程序(1)：
作业调度算法备作业集合中选择作业建立作业控制进程处理该作业
作业调度程序(2)：
等终止作业控制进程进行善处理
4 作
作业调度作业进程形式进入存获运行资格
真正获CPU运行需进程调度
作业调度中级调度进程调度构成调度三级
第四章 互斥步通信
进程互斥
进程互斥进程间发生种间接相互作
种相互作进程身希运行进程感觉
进程互斥发生相关进程间发生关进程间
二 享变量界区
a) 享变量：
进程均需访问变量称公变量(shared variable)称享变量
b) 界区：
访问享变量程序段称界区(critical region)称界段
界区段代码
图 享变量界区关系
三 界区进程互斥
a) 进程互斥定义
两两进程时进入关组享变量界区否发生时间关错误种现象称进程互斥
注意进程互斥相享变量言
b) 进程互斥实现
界区框架：
do {
entry section
界区
exit section
}while(1)
实现互斥编写entry sectionexit section保证时刻进程处界区
c) 界区相独占型资源资源理应满足原：
(1)关某组享变量界区均空闲时求进入该组享变量某界区进程应立进入
(2)关某组享变量某界区域占时求进入该组享变量某界区域进程应等
(3)进程离开关某组享变量某界区时应容许某等进入关该组享变量某界区域进程进入
四 进程步
a) 进程步定义
进程步进程间直接相互作合作进程间意识行种相互作发生相关进程间
b) 进程步概念
1 进程步
组进程协调推进速度某点处需相互等相互唤醒进程间种相互制约关系称进程步
注意：
进程步仅发生逻辑关系进程间进程互斥发生意两进程间
2 进程合作
组进程单独正常进行发正常进行现象称进程合作
参合作进程称合作进程
进程步合作进程间直接相互作
五 进程步机制
实现进程间步工具称步机制称步设施
典型进程步机制信号灯PV操作
六 信号灯PV操作相关定义
（求解决互斥步问题生产者消费者问题读者写者问题哲学家餐问题）
a) 信号灯PV操作定义
1 信号灯类型
定义：
struct semaphore {
int value
pointer_to_PCB queue
}
说明：
Semaphore s
2 信号灯类型valuequeue
信号灯变量包括两部分值部分svalue指针部分squeue
意时刻squeue指空指进程控制块构成队列头部初始时指空
value表示前资源数
svalue创建时赋次值直接改变value值通PV操作改变
value0时表示资源已分配完value<0时表示前没资源需排队等
3 asleep()wakeup()函数
asleep(s>queue)
执行操作进程进程控制块进入队列s>queue尾部状态运行态转等态系统转处理器调度程序
wakeup()
队列s>queue头部进程进程控制块该队列中取出排入绪队列状态等态转绪态
4 P操作原语(down)
原语：段间断执行程序称原语
void P(semaphore *s) {
s>value
if(s>value < 0) { 前申请时已没资源
asleep(s>queue) 进入等队列
}
}
P操作应申请资源
5 V操作原语(up)
void V(semaphore *s) {
s>value++
if(s>value < 0) { 表示前进程正等队列中等
wakeup(s>queue)
释放资源时资源分配等队列中第进程
}
}
V操作应释放资源
6 注意wakeup操作等队列队头元素取出等态改绪态表示前刚刚释放资源分配队头进程
进程执行V操作表示资源释放释放value>0表示前没进程正等资源value<0表示等队列中正进程等资源资源分配value>0表示资源分配等队列中资源弄混
b) 关信号灯变量规定
1 必须置次初值置次初值初值必需非负整数
2 执行P操作操作操作均非法
c) 关信号灯变量结
1 s>value>0时s>queue空
2 s>value<0时|s>value|s>queue中等进程数
3 s>value初值1时实现进程互斥需进入界区时执行次P操作离开界区时执行次V操作
4 s>value初值非1正整数时理种组合资源（具实例类资源5台印机）申请时执行次P操作时执行次V操作
5 s>value初值0时实现进程间简单步
（需先执行动作执行V操作执行动作前执行先执行P操作执行）
七 信号灯PV操作应
a) 信号灯变量实现进程互斥（初值1）
1 说明
2 图书阅系统问题
b) 信号灯变量实现进程步（初值0）
1 说明
先动作进程执行完动作进行V操作相动作进程发出信号告诉动作进程开始执行
动作进程通P操作表示信号然开始执行动作
2 司机售票员问题
注意组先动作应信号灯
P2先关车门P1启动P1先停车P2开门
八 信号灯变量解决综合问题——生产者—消费者问题
a) 问题描述
b) 问题分析
c) 问题解决
d) 求解程序
e) 优化
f) 问题实质
（果界缓区inout操作直接in+1out+1需k）
九 信号灯变量解决综合问题——读者—写者问题
a) 问题描述
b) 问题分析解决
c) 求解程序
d) 分析改进
分析 RR互斥读者源源断写者饿死
实写者操作更新数应优先进行否读者读时数
改进：写者优先
旦写者等正读读者结束写者进入新达读者等
十 信号灯变量解决综合问题——哲学家餐问题
a) 问题描述
五哲学家围坐张圆桌周围哲学家面前盘通心粉通心粉滑需两叉子夹住相邻两盘子间放叉子餐桌图示
哲学家生活中两种交活动时段：吃饭思考（种抽象哲学家言活动关紧）
哲学家觉饿时试图分两次取左边右边叉子次分次序果成功两叉子开始吃饭吃完放叉子继续思考
关键问题：哲学家写段描述行程序决会死锁？
b) 问题分析
哲学家交谈危险
产生死锁哲学家着左手餐叉永远等右边餐叉（者相反）
没死锁发生资源耗例假设规定哲学家等餐叉超五分钟放手里餐叉等五分钟进行次尝试策略消死锁（系统总会进入状态）然发生活锁果五位哲学家完全相时刻进入餐厅时起左边餐叉哲学家会等五分钟时放手中餐叉等五分钟时起餐叉
c) 问题解决
1 引入服务生
简单解法引入餐厅服务生哲学家必须允许起餐叉服务生知道餐叉正够作出判断避免死锁
演示种解法假设哲学家次标号AE果AC吃东西四餐叉中B坐AC间两餐叉法DE间空余餐叉假设时D想吃东西果起第五餐叉发生死锁相反果征求服务生意服务生会等样保证次两餐叉空余出时定位哲学家成功餐叉避免死锁
2 限制4位哲学家时进餐
3 哲学家状态增加3思考饥饿进食哲学家仅饥饿时申请叉子时申请左右两叉子果时左右两叉子空闲等
d) 限制4位哲学家时进餐求解程序
VAR fork Array [04] of Semophore(11111)
VAR count semophore 4
philosopher(i) begin
repeat
THINK
P(count)
P(fork[i])
P(fork[i+1] mod 5)
EAT
V(fork[i+1] mod 5)
V(fork[i])
V(count)
until false
end
e) 时申请两叉子求解程序
SP 信号量集解决哲学家进餐问题
VAR fork array[04] of Semaphore (11111)
Phi begin
repeat
THINK
SP( fork[i] fork[(i+1)mod 5] )
EAT
SV( fork[i] fork[(i+1)mod 5] )
until false
end
f) 问题实质
实际计算机问题中缺乏餐叉类缺乏享资源
种常计算机技术资源加锁保证某时刻资源程序段代码访问
程序想资源已程序锁定等资源解锁
程序涉加锁资源时某情况发生死锁
例某程序需访问两文件两样程序锁文件等方解锁文件永远会发生样会导致死锁
十 信号灯变量解决综合问题——三台印机理
a) 问题描述
设3台类型相印机编号分123试编写申请函数require释放函数return
require印机空闲时返回分印机编号印机空闲时等唤醒返回分印机编号
return释放指定编号空闲印机申请者等时唤醒
b) 求解程序
enum lp[13] of (freeused) (initial value is free) 表示空闲状态
semaphore S (initial value is 3) 表示3台印机
semaphore mutex (initial value is 1) 实现互斥
13 require() void return(i 13)
{ {
P(S) P(mutex)
P(mutex) lp[i]free 释放印机
for(i1 i<3 i++) V(mutex)
if(lp[i]free) V(S)
break }
lp[i]used 占第台空闲印机
V(mutex)
return(i)
}
十二 信号灯变量解决综合问题——吸烟者问题
a) 问题描述
假设系统中三抽烟者进程抽烟者断卷烟抽烟抽烟者卷起抽掉颗烟需三种材料：烟草纸火柴抽烟者烟草纸火柴
3供应商进程：
X 提供 tobacco match
Y 提供 match wrapper
Z 提供 wrapper tobacco
tobacco烟草match火柴wrapper纸
3吸烟者进程：
A 拥 tobacco
B 拥 match
C 拥 wrapper
限制条件：
(1) 时刻XYZ供应资源
(2) 提供资源耗XYZ继续供应资源
b) 传统解法
传统信号量解法：
semaphore t m w s 0 0 0 1
t m w分表示三种烟量
s实现互斥
Process X process Y process Z
P(s) P(s) P(s)
V(t) V(m) V(w)
V(m) V(w) V(t)
Process A Process B process C
P(m) P(w) P(t)
P(w) P(t) P(m)
smoke smoke smoke
V(s) V(s) V(s)
c) 存问题
进程X提供tobaccomatch分进程A进程C获导致死锁
意改变吸烟者进程两P操作次序防止死锁发生
d) 问题原解决方式
产生种错误原吸烟者进程需外两种资源通两P操作分申请
果两种资源时申请（时执行P操作）防止种问题
e) 解决问题
需扩展P操作够信号量变量时执行P操作V操作SP(simultaneous P时执行P操作)SV(时执行V操作)
作信号量集合
f) SPSV操作
si值ti次变换步长di
SP(S1t1d1 … Sntndn)
{
if S1>t1 and … and Sn>tn then
for I1 to n
do SiSidi
endfor
else
运行进程进程控制块连第si该进程指令计数器容设置SP操作起始位置该进程重新执行时等条件重新进行评估
}
SV(s1 d1 … sn dn )
{
for i 1 to n do
Si Si + di
si队列进程控制块取出连绪队列中
}
中si信号量tidi均1时称and型信号量常种形式
g) 正确解法
semaphore t m w s 0 0 0 1
Process X Process Y Process Z
loop loop loop
P(s) P(s) P(s)
SV(t1 m1) SV(m 1w 1) SV(w 1 t 1)
endloop endloop endloop
Process A Process B Process C
loop loop loop
SP(m11 w11) SP(w11 t11) SP(t11 m11)
smoke smoke smoke
V(s) V(s) V(s)
endloop endloop endloop
十三 进程高级通信分类概念模式
a) 进程通信分类
1 低级通信
进程互斥进程步称进程间低级通信
2 高级通信
进程间宗数传递称进程间高级通信
b) 进程通信概念
进程间互斥步信息交换统称进程通信
(interprocess communication IPC)
c) 进程通信模式
1 享存模式(shared memory)
种模式适单机系统
相互通信进程间公存组进程公存中写组进程该公存中读便实现进程间信息传递
2 消息传递模式(message passing)
种模式适单机系统网络环境
采种模式时操作系统户进程间通信提供两基系统调命令（称原语）发送命令(send)接收命令(receive)
需进行消息传递时发送者仅需执行发送命令接收者仅需执行接收命令消息便发送者传送接收者
消息发送者传送接收者完全OS完成户透明
十四 进程通信消息传递模式两种实现方式
a) 概述
消息传递模式实现时分两种方式：
直接方式：进程进程
间接方式：进程信箱进程
b) 直接方式
谓直接方式指相互通信进程间通信时直呼名
说发送者发送时指定接收者名字接收者接收时指定发送者名字
系统调两种形式：
1 称形式(symmetric)
称形式特点发送者发送时指定唯接收者接收者接收时指定唯发送者
系统调命令：
send(R M) 消息M发送进程R
receive(S N) 进程S处接收消息N
2 非称形式(asymmetric)
非称形式特点发送者发送时指定唯接收者接收者接收时指定具体发送者
系统调命定：
send(R M) 消息M发送进程R
receive(pid N) 接收消息N返回时设pid发送进程标识
N接收信息存pid发送进程号
发送进程相顾客接收进程相服务员服务员顾客服务服务时知道位顾客求服务位顾客先先位顾客服务
c) 消息发送进程空间传送接收进程空间途径
1 缓途径（知道步骤）
采条途径时操作系统空间中保存着组缓区
发送进程执行send系统调命令时产生愿性中断进入操作系统操作系统发送进程分配缓区发送消息容发送进程空间复制缓区中然载消息缓区连接收进程消息链中
完成信息发送发送进程返回户态继续执行面程序
某时刻接收进程执行receive系统调命令时产生愿性中断进入操作系统操作系统载消息缓区消息链中取出消息容复制接收进程空间中然收回该空闲缓区
完成消息接收接收进程返回户态继续执行面程序
消息发送者接收者间传输程次缓提高系统发性发送者旦信息传送缓区返回继续执行面程序须等接收者真正执行接收条消息系统调命令
图 发送进程接收进程间关系
（M进程发送区起始址N进程接收区起始址）
图 缓区中消息
（发送者接收者消息链操作应互斥进行进程作接收进程条消息链消息链互斥变量m_mutex分存放进程PCB中）
图 空闲缓区链
（收发进程间关系类似生产者——消费者问题消息缓区类似箱子容量k）
现出发送原语send接收原语receive实现程Sendreceive属系统调命令位户程序中系统户态执行命令时发生愿性中断事件进入操作系统操作系统总控程序判断转相应处理程序
Sb缓区数量sm接收进程消息资源数量
注意：Sendreceive 高级通讯原语低级原语PV实现
Sendreceive真正意义原语中断
2 缓途径
果操作系统没提供消息缓区发送进程空间直接传送接收进程空间
优点节省空间
缺点发性差发送进程必须等接收进程执行receive命令消息发送进程空间复制接收进程空间返回继续前推进
d) 间接方式
谓间接方式指相互通信进程间通信时直呼方名字指明中间媒体信箱进程间通信箱实现通信
时系统提供高级通信原语信箱取代进程
第五章 死锁饥饿
死锁概念
组进程中进程均等组进程中进程占永远法资源种现象称进程死锁简称死锁(deadlock)
死锁发生参死锁进程直持续非参死锁进程外某种干预
（1 进程竞争资源引起僵持称死锁）
（2 死锁解需外干预）
二 关死锁结（4）
a) 参死锁进程数目少2
b) 参死锁进程均等资源
c) 参死锁进程少2占资源
d) 参死锁进程系统中前正运行进程集合子集
三 死锁类型
a) 竞争资源引起死锁
进程争夺系统中限资源引起死锁
面谈死锁种类型死锁
资源：进程时释放进程
b) 进程通信引起死锁
基消息系统中P1等P2消息P2等P3消息P3等P1消息种循环等消息引起死锁称进程通信引起死锁
生灭资源：次利资源消息生灭资源
c) 原引起死锁
P1P2竞争独占型资源P1P2先P2P1先两进程均法推进称After YouAfter You问题
四 死锁条件（4）
面出死锁发生4必条件称coffman条件
a) 资源独占(mutual exclusion)
资源时刻分配进程
果进程申请某资源该资源正外某进程占申请者需等
直占者释放该资源
b) 剥夺(nonpreemption)
资源申请者强行资源占者手中夺取资源资源占者完愿释放
c) 保持申请(hold and wait)
进程占部分资源申请新资源申请新资源时候释放已占资源
d) 循环等(circular wait)
存进程等序列{p1 p2 … pn}中p1等p2占某资源p2等p3占某资源……pn等p1占某资源
e) 仅述4条件时满足时死锁会发生
换言破坏4条件中意死锁会发生
五 死锁处理
死锁处理分死锁预防死锁避免
a) 预防（静态）
预防进程关资源活动加静态限制进程遵守协议发生死锁
预防策略两种：预先分配序分配
1 预先分配
进程运行前次性系统申请需全部资源果系统前满足进程全部资源请求分配资源进程暂时投入运行果系统前满足全部资源请求次性申请资源全部分配进程
进程投入运行前已申请需全部资源运行期间会发出新资源申请命令破坏保持申请必条件
2 序分配
事先资源类完全排序资源类赋予唯整数进程必须资源编号次序申请资源
进程占资源时 申请ri资源申请rj中资源充条件：f(ri)换言 进程申请某资源类ri中资源充条件已释放资源类rj中资源 里f(ri)种策略破坏循环等必条件
b) 避免（动态）
避免进程关资源申请命令加动态实时检测拒绝安全资源请求命令保证死锁会发生
六 银行家算法（掌握思想需写）
银行家算法种避免死锁算法
a) 安全状态安全状态
果存系统中进程构成安全序列P1…Pn系统处安全状态安全状态时定没死锁发生
安全序列指进程序列{P1…Pn}安全进程Pi(1≤i≤n）尚需资源量超系统前剩余资源量进程Pj (j < i )前占资源量
安全状态少存条路线：p1pn次执行路线进程执行完存死锁
安全状态定死锁状态安全状态定死锁状态
b) 说明
新进程进入系统时必须声明资源需求量资源类需少资源实例
进程发出资源申请命令系统够满足该请求时系统判断：果分配申请资源系统状态否安全
果安全分配资源申请者继续否分配资源申请者等
c) 实现银行家算法需数结构
设n系统中进程总数m资源类总数
P{p1p2…pn}
R{r1r2…rm}
1）利资源量int Available[m]
含m元素数组中元素代表类利资源数目果Available[j]K表示系统中现Rj类资源K初始时Available值系统资源总量
2）需求矩阵int Claim[n m]
n×m矩阵定义系统中n进程中进程m类资源需求果Claim [ij]K表示进程i需Rj类资源数目K
3）分配矩阵int Allocation[n m]
n×m矩阵定义系统中类资源前已分配进程资源数果Allocation[ij]K表示进程i前已分Rj类资源数目K初始时Allocation[I j]0
4）需求矩阵int Need[n m]
n×m矩阵表示进程尚需类资源数果Need[ij]K表示进程i需Rj类资源K方完成务
Need[ij] Claim [ij]Allocation[ij]
初始时NeedClaim
5) 前请求矩阵 int Request[n m]
n×m矩阵表示进程前申请资源类中资源实例数量果Request[I j]k进程i需资源rj中k资源实例
引入列记法：
设XY标1l维数组：
X£Y Û j (1£j£l) X[j]£Y[j]
XY Û j (1£j£l) X[j]Y[j]
Xc Û j (1£j£l) X[j]c
X±Y Û j (1£j£l) X[j]±Y[j]
实现安全性检查需定义数结构：
6) int Work[m]
记录资源
7) int Finish[n]
记录进程否执行完
d) 银行家算法——资源分配算法
e) 银行家算法——安全性检测算法
f) 银行家算法例子
g) 银行家算法保守性
七 饥饿活锁
a) 定义
等时间进程推进响应带明显影响时称发生进程饥饿(starvation)饥饿定程度进程赋予务完成具实际意义时称该进程饿死(starve to death)
忙式等条件发生饥饿称活锁．
（饥饿没界等般资源分配合理致等时间超极限会导致饿死）
b) 死锁饿死联系
饿死死锁定联系：二者竞争资源引起明显差表现方面：
(1) 进程状态考虑死锁进程处等状态忙式等(处运行绪状态)进程非处等状态饿死
(2) 死锁进程等永远会释放资源饿死进程等会释放会分配资源等时限没界(排队等忙式等)
(3) 死锁定发生循环等饿死然 表明通资源分配图检测死锁存否检测否进程饿死
(4) 死锁定涉进程饥饿饿死进程．
c) 饥饿饿死资源分配策略(policy)关防止饥饿饿死公性考虑确保进程忽视FCFS分配算法
八 死锁饥饿例子——独木桥问题
a) 题目描述
假设座东西车辆单行道桥图示次允许方干车辆通（桥方车辆通）桥没车辆时端车辆允许桥通车辆桥端车辆继续桥端车辆桥载重4辆汽车请PV操作实现东西两端桥问题
b) 分析思想：
题基读者－写者问题算法（写进程优先）
设置两变量：
eastn记录东端桥西端车辆数
westn记录西端桥东端车辆数
初值均0
两变量互斥访问设置两互斥访问信号量meastmwest初值均1
东端桥西端桥车辆言桥没车辆时谁先请求谁先桥设置互斥访问信号量wait初值1
增设信号量scount表示桥时桥车辆数初值4
int eastn0 记录东端桥西端车辆数
int westn0 记录西端桥东端车辆数
Semaphore meast1 保护eastn变量信号量
Semaphore mwest1 保护westn变量信号量
Semaphore scount4 表示桥车辆计数信号量
Semaphore wait1 确定东西两端桥请求桥序互斥信号量
1） 巴马运河西洋太洋两方船设置两进程Atlantic()Pacific()
2） 侧船运河果侧船河等果方船河时方船总河船数T河果方船河时方船河总数T等
3） 避免饥饿死锁必须控制次河船数T
c) 解决程序
main()
{
Cobegin
{
进程easti（i12…） 东端车辆桥进程
{
while (true)
{
P(wait) 东端车辆先请求先桥
P(meast) 拒绝访问eastn变量
if (eastn0) 东端第辆车桥禁止西端车辆桥
P(mwest)
eastneastn+1 东端桥车辆数增1
V(meast) 恢复访问eastn变量
V(wait) 恢复车辆桥
P(scount) 递减时桥车辆数
东端西端桥
V(scount) 递增时桥车辆数
P(meast) 拒绝访问eastn变量
eastn 东端桥车辆数减1
if (eastn0) 东端没车辆桥允许西端车辆桥
V(mwest)
V(meast) 恢复访问eastn变量
}
}
进程westj（j12…） 西端车辆桥进程
{
while (true)
{
P(wait) 西端车辆先请求先桥
P(mwest) 拒绝访问westn变量
if (westn0) 西端第辆车桥禁止东端车辆桥
P(meast)
westnwestn+1 西端桥车辆数增1
V(mwest) 恢复访问westn变量
V(wait) 恢复车辆桥
P(scount) 递减时桥车辆数
西端东端桥
V(scount) 递增时桥车辆数
P(mwest) 拒绝访问westn变量
westn 西端桥车辆数减1
if (westn0) 西端没车辆桥允许东端车辆桥
V(meast)
V(mwest) 恢复访问westn变量
}
}
}
Coend
}
种解法：
九 死锁饥饿例子——河问题
a) 问题描述
b) 问题分析
限定时河数5
两岸竞争1234两石块采序分配法
c) 求解程序
十 系统举例
死锁数系统中采视见鸵鸟算法Edsger Wybe Dijkstra设计实现THE系统中采避免死锁银行家算法
第六章 存储理
存资源理
a) 存分区
分区时刻
静态分区：系统初始化时分
动态分区：申请时分
分区
等长分区：2i
异长分区：程序程序单位象
通常作法
静态+等长（页式段页式）
动态+异长（段式界址）
b) 存分配
1 静态等长分区分配
l 字位映象图（bit map）
l 空闲页面表
l 空闲页面链（链表操作较耗费资源）
2 动态异常分区分配（区分三种算法）
理长度等区域需种称空闲区域表数结构
l 先适应算法
l 佳适应算法
l 坏适应算法
二 存储理方式（三张图非常重）
a) 页式存储理
P181P187
重点P184 图616
b) 段式存储理
P187P193
重点P191 图627
c) 段页式存储理（掌握思想）
P193196
三 虚拟存储系统（注意颠簸页障率反馈模型）
a) 虚拟问题
运行存程序
进程全部装入存浪费空间（进程活动具局部性)
b) 程序局部性原理
1 时间局部性
条指令执行条指令次执行数访问条数次访问时间相集中程序中存量循环操作
2 空间局部性
相邻指令相邻数执行时常集中程序序执行数组访问
c) 虚拟存储
进程部分装入存部分（全部）装入外存运行时访问外存部分动态调入存够淘汰
d) 虚拟页式存储理
1 基原理
程序运行前部分页面装入存部分页面（全部页面）装入外存进程运行程中果访问页面存虚拟情形相果访问页面存发生缺页障进入操作系统操作系统进行页面动态调度
2 缺页障中断处理程序
访问页存发生缺页中断中断处理程序：
找访问页外存址
存找空闲页面
没淘汰算法淘汰
需淘汰页面写回外存修改页表总页表
读入需页面（切换进程调度进程）
重新启动进程执行中断指令
3 存页框分配策略
1 均分配
2 进程长度例分配
3 进程优先级例分配
4 进程长度优先级例分配
4 外存块分配策略
1 静态分配
外存保持进程全部页面：
优点：速度快—未修改页面情况淘汰时必写回
缺点：外存浪费
2 动态分配
外存仅保持进程存页面：
优点：节省外存
缺点：速度慢淘汰时必须写回
5 页面调入时机
1 请调(demand paging)
upon page fault 发生缺页中断时调入
2 预调(prepaging)
before page fault 缺页障前调入(根程序序行定准）
定准然缺页预调必须辅请调
6 置换算法
：页淘汰段淘汰快表淘汰
1佳算法（理）
2先进先出算法
3少算法
4先淘汰算法
5频繁算法
e) 颠簸(thrashing)
1 颠簸定义
页面存外存间频繁换入换出致系统调度页面时间进程实际运行占时间长
颠簸页障率高产生结果
2 颠簸原
(1) 分进程物理页架少
(2) 淘汰算法合理
(3) 程序结构
程序滥转移指令会影响程序局部性
3 颠簸处理
(1) 增加分进程物理页架数
(2) 改进淘汰算法
(3) 改进程序结构
量避免goto语句
f) 工作集模型
g) 页障率反馈模型
工作集模型够成功指导页面分配防止发生颠簸实现开销较较困难
颠簸页障率高引起系统通页障率反馈信息动态调整页面分配
第七章 文件系统
文件概念
文件(file)具符号名逻辑完整意义信息项序序列
二 文件组织
a) 概述
文件组织称文件结构中涉文件逻辑组织文件物理组织
文件逻辑组织指文件外部组织形式户文件组织形式
文件物理组织指文件部组织形式文件物理存储设备组织形式
b) 文件物理组织
1 确定文件物理结构应考虑素（四种）：
(1)记录格式
文件记录格式分定长变长两种
定长格式实现较简单速度快浪费存储空间
变长格式实现较复杂速度慢节省存储空间
(2)空间开销
空间开销指保存文件容外需额外存储开销包括外存开销文件时需存开销
例文件目录信息记录存调时保存信息
(3)存取速度
存取速度包括序存取速度号机存取速度键机存取速度
(4)长度变化
长度变化指文件长度动态增加动态减少尤指文件长度动态增加
2 文件常物理组织形式：
序结构链接结构索引结构散列(Hash)结构倒排结构等
c) 文件常物理组织形式
1 序结构(sequential structure)——数组
2 链接结构(linked structure)——链表
3 索引结构(indexed structure)——结合两种结构优点
4 散列结构(hash structure)——哈希表
5 倒排结构(inverted structure)
6 种文件物理结构特征较
三 文件控制块
a) 定义
文件控制块(file control block FCB)标志文件存数结构 中包含系统文件进行理需全部信息
b) 容
文件名 享说明
文件号 文件逻辑结构
户名 文件物理结构
文件址 建立日期
文件长度 修改日期
记录 访问日期
文件类型 口令
文件属性
四 文件系统实现
a) 什文件系统
文件理信息资源程序集合称文件系统(file system)
b) 概述
实现文件系统存OS空间中需保存干表目
外需理保存文件容外存空间
c) 存需表目
1 系统开文件表(整系统)
FCB中保存着系统理文件需信息信息作目录项长驻外存
文件开时FCB中信息需常访问提高速度需读存
系统开文件表存中保存已开文件FCB表目
表容FCB部外 包含三信息
(1)文件号 该文件FCB部外存中位置
(2)享计数 记录前少进程正该文件值零时表明空表目
(3)修改标志 标识某文件FCB存期间否修改正该文件进程关闭该文件时 果该FCB存期间修改 需存中修改FCB写回外存否需刷新外存
2 户开文件表（进程）
文件享进程时开文件开方式前读写位置样
信息记录表中 该表称户开文件表 进程
表中系统开文件表入口指针 指该文件FCB系统开文件表中入口址进程文件时 进程户开文件表中会相系统开文件表入口
表中文件描述符正整数 值表中位置隐含确定实际记表中文件开返回进程进程便描述符存取该文件文件名字
户开文件表存储位置记录进程PCB中 户开文件表长度决定进程时开文件数量
3 户开文件表系统开文件表联系
户开文件表指系统开文件表进程享文件 户开文件表目指系统开文件表入口
第八章 设备输入输出理
设备分类
a) 块型设备字符型设备
1 块型设备
块型设备存储型设备类设备干长度相块构成
2 字符型设备
字符型设备输入输出型设备（包括通信设备）类设备进行数传输基单位字节
b) 独占设备非独占设备
1 独占设备
独占设备包字符型设备磁带机意段时间进程占
2 享型设备
享型设备包括磁带机外块型设备进程数传输块单位交叉
特例：磁带机然块单位存储设备物理特性原必须独占
二 数传输方式——通道方式
a) 通道定义
通道专门负责输入输出操作处理器DMA（存储器直接访问）数块传输功外通道具更加强输入输出功
b) 通道方式DMA方式区
相点：存中心支持块传输
点：通道专门处理器指令系统实施复杂输入输出控制
c) 通道程序位置
通道程序放存中
d) 通道容
通道相功单纯处理器涉容：
1 通道指令系统
基操作：空操作读写控制转移结束
指令格式：（操作码传输量特征位址）
操作码指定操作类型
2 通道控运部件
CAW：记录条指令存放址类似指令计数器
CCW：记录正执行指令类似指令寄存器
CSW：记录通道控制器设备状态
CDW：暂存存设备间输入输出传输数
3 通道存储区域
通道没独立存储空间需机享存空间
通周期窃方式实现通道CPU行工作
4 通道程序执行程
条通道指令传送组数通道程序传送组数
组数全部传输完毕处理器发次中断减轻机负担
三 设备驱动
a) 通道程序
CCW指令序列
静态编制动态生成
b) 设备启动
通道启动
c) 中断处理
通道结束操作CPU发中断
d) 通道处理器间相互作关系（图明白）
四 虚拟设备
a) 定义
利享型设备实现数量较速度较快独占型设备成虚拟设备
b) 虚拟设备实现（重点）
假脱机系统（称SPOOLing系统）例介绍虚拟设备实现
P285288
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
操作系统定义 3
二 区程序发程序行 3
三 操作系统硬件环境 3
第二章 进程线程作业 5
吞吐量 5
二 进程概念 5
三 进程状态状态转换 5
四 进程控制块 6
五 进程组成 6
六 进程队列 6
七 线程概念 7
八 线程控制块 7
九 线程实现 8
十 作业 8
十 作业进程线程三者间关系 9
第三章 中断处理器调度 10
概述 10
二 中断概念 10
三 中断装置 10
四 中断处理程序 11
五 处理器调度 12
六 处理器调度算法 12
七 常处理器调度算法（八） 13
八 调度级级调度 17
第四章 互斥步通信 19
进程互斥 19
二 享变量界区 19
三 界区进程互斥 19
四 进程步 19
五 进程步机制 20
六 信号灯PV操作相关定义 20
七 信号灯PV操作应 22
八 信号灯变量解决综合问题——生产者—消费者问题 23
九 信号灯变量解决综合问题——读者—写者问题 26
十 信号灯变量解决综合问题——哲学家餐问题 28
十 信号灯变量解决综合问题——三台印机理 30
十二 信号灯变量解决综合问题——吸烟者问题 30
十三 进程高级通信分类概念模式 32
十四 进程通信消息传递模式两种实现方式 32
第五章 死锁饥饿 36
死锁概念 36
二 关死锁结（4） 36
三 死锁类型 36
四 死锁条件（4） 36
五 死锁处理 37
六 银行家算法（掌握思想需写） 37
七 饥饿活锁 40
八 死锁饥饿例子——独木桥问题 41
九 死锁饥饿例子——河问题 44
十 系统举例 45
第六章 存储理 46
存资源理 46
二 存储理方式（三张图非常重） 48
三 虚拟存储系统（注意颠簸页障率反馈模型） 48
第七章 文件系统 52
文件概念 52
二 文件组织 52
三 文件控制块 55
四 文件系统实现 56
第八章 设备输入输出理 58
设备分类 58
二 数传输方式——通道方式 58
三 设备驱动 59
四 虚拟设备 59
第章 操作系统概述
操作系统定义
操作系统位硬件层系统软件层系统软件理系统中种软件硬件资源充分利方便户计算机系统
二 区程序发程序行
程序行求微观时绝时刻程序时前推进
程序发求微观时需宏观程序前推进
发：宏观时运行微观交运行
三 操作系统硬件环境
a) 定时装置
1 绝时钟
时间表示形式年月日时分秒开机时电源供电计时关机时机电池供电计时
操作系统绝时钟记录作业进入系统处理时间文件修改存取时间资源占时间日志记录时间等
2 间隔时钟
称闹钟间隔固定时间发生次时钟中断时系统获控制权便运行系统理实现程序发
中断系统发必条件间隔时钟现代操作系统基础
利间隔时钟实现逻辑时钟
b) 系统栈
1 位置
存中操作系统空间固定区域
2 途
1 中断响应时保存中断现场
2 保存操作系统子程序间相互调参数值返回值返回点子程序局部变量
c) 特权指令非特权指令
1 特权指令
态执行
指令执行仅影响运行程序身会影响程序甚整系统
eg 开关中断修改址映射寄存器置程序状态字PSW停机
2 非特权指令
态目态均执行指令称非特权指令指令执行运行程序身关影响程序操作系统
eg 数传送指令算术运算指令
d) 处理器状态状态转换
1 处理器状态
硬件通常分态目态两种状态程序状态字PSW中位进行标识
1 态
态称系统态核心态操作系统运行时处状态计算机处态时执行硬件提供全部指令包括特权指令非特权指令
利特权指令修改程序状态字机器状态程序状态字部分态改变机器状态进入目态
2 目态
目态称户态般户程序运行时处状态处理器处目态时执行硬件机器指令子集非特权指令
旦户目态执行特权指令硬件产生中断进入操作系统特权指令执行制止
置程序状态字特权指令目态程序运行状态转换态
2 状态转换
1 目态态转换
处理器状态目态转换态唯途径中断
2 态目态转换
通修改程序状态字（置PSW）实现
操作系统运行态户程序运行目态种状态转换伴着操作系统户程序转换
e) 中断装置
1 定义
发现响应中断硬件机构称中断装置
2 功
1 发现中断
中断发生时够识
中断事件时发生时优先级响应高级者
2 响应中断
目前运行进程中断量PSWPC压入系统栈然根中断原指定存单元新中断量取出送寄存器中控制转相应中断处理程序
第二章 进程线程作业
吞吐量
衡量系统效率尺度吞吐量
系统吞吐量定义单位时间系统处理作业（程序）道数（数量）：
吞吐量作业道数全部处理时间
吞吐量系统处理器等资源利率密切关系提高系统吞吐量应提高系统资源利率入手
二 进程概念
进程具定独立功程序关数集合次运行活动
三 进程状态状态转换
a) 进程生存期
进程生成执行结束段时间进程生存期
b) 进程状态
进程生存期处3中基状态
1 运行态（run）
进程占处理器资源正运行
（占CPU单处理器系统中时刻进程处种状态）
2 绪态（ready）
进程身具备运行条件处理器数量少运行进程数量暂未投入运行相等处理器资源
（未CPU）
3 等态（wait）
称挂起态封锁态睡眠态进程身具备运行条件分配处理器运行
进程正等某事件发生等某资源释放等该进程相关数传输完成信号等
c) 状态转换
绪进程获处理器时状态绪态变运行态
运行进程剥夺处理器资源时完系统分时间片者出现高优先级进程状态运行态变绪态
运行进程某事件受阻时申请资源占启动数传输未完成状态运行态变等态
等事件发生时申请资源数传输完成状态等态变绪态
图 进程间基状态转换关系
四 进程控制块
a) 定义
进程控制块（Process Control BlockPCB）标志进程存数结构中包含系统进程进行理需全部信息
b) 作
道程序系统中运行程序需断点现场保存区域区域设进程控制块中
进程控制块进程存标志组信息构成
进程标识： 通常整数称进程号进程号唯户号相应
户标识： 通常整数称户号户号进程号相应
进程状态： 绪运行等间动态变化
调度参数： 确定运行进程
现场信息： 保存进程暂停断点信息包括通寄存器PSWPC
家族联系： 记载进程父进程
程序址： 记载进程应程序存储位置占存储空间
前开文件： 记载进程正文件
消息队列指针： 指进程进程接收消息构成消息队列链头
资源情况： 记载该进程生存期间系统资源时间
进程队列指针： 构建进程控制块队列系统理进程需
五 进程组成
进程两部分组成进程控制块程序中程序包括代码数等
a) 进程控制块
进程控制块进程灵魂
进程控制块放系统空间中操作系统够进行存取
b) 程序
程序进程躯体中包括代码数两部分
c) 系统开销（system overhead）
系统开销般指运行操作系统程序系统进程理花费时间空间
六 进程队列
进程控制块进程代表进程队列实际进程控制块构成队列
该队列通常链形式实现称PCB链
a) 绪队列
般整系统中绪队列
b) 等队列
等事件等队列系统中根等事件等队列等输入设备队列等输出设备队列等
c) 运行队列
单处理器系统中运行队列处理器系统中CPU运行队列
队列中进程
图 进程队列模型
七 线程概念
a) 定义
线程(thread)称轻进程进程相独立执行流
进程包含线程线程执行程序中相代码段代码段享数区堆
般认进程资源分配单位线程CPU调度单位
b) 线程相进程优点
1 文切换速度快
进程中线程切换线程需改变寄存器栈包括程序数址空间变
2 系统开销
创建线程创建进程需完成工作少
3 通信容易
进程中线程享址空间线程写数空间信息直接该进程中线程读取便通信
八 线程控制块
a) 定义
线程控制块(thread control block TCB)标志线程存数结构中包含系统线程进行理需全部信息
b) 组成
线程标识
线程状态
调度参数
现场（通寄存器指令计数器户栈指针）
链接指针
线程控制块属操作系统空间属户进程空间（运行系统理）取决线程实现方式
九 线程实现
线程两种实现方式：目态实现户级线程态实现核心级线程
a) 户级线程
1 户级线程线程相关控制结构——线程控制块保存目态空间中运行系统进行维护
2 线程操作系统见系统调度进程单位核心栈数进程数相应
3 优点
1 线程赖操作系统采问题相关调度策略灵活性
2 进程中线程切换需进入操作系统实现效率较高
4 缺点
3 进程中线程真正行处理器环境中
4 线程操作系统见调度进程级某进程中线程通系统调进入操作系统受阻该进程线程运行
b) 核心级线程
1 核心级线程线程控制块保存操作系统空间线程状态转换操作系统完成线程CPU调度基单位
2 系统调度线程单位操作系统需线程保持核心栈
3 核心级线程进程状态具实际意义省略
4 优点：发性处理器环境中意进程线程真正行执行
5 缺点：线程控制状态转换需进入操作系统完成系统开销较
十 作业
a) 定义
户求计算机系统完成计算务集合称作业(job)
（里计算务广义计算务）
般说作业进程概念
b) 作业步(job step)
作业通常包含计算步骤作业中相独立处理步骤称作业步
作业步间具序发关系
c) 作业进程关系
作业步通常进程完成样作业存处理时通常进程相应作业进程间具关系
d) 作业控制块
作业控制块(job control block JCB)标志作业存数结构中包含系统作业进行理需全部信息
e) 关批处理作业基概念
1 作业控制语言JCL：描述批处理作业控制意图语言
类C语言
2 作业说明书：JCL语句序列（作业说明书般特殊符号起始）
类C语言写程序
3 作业控制程序：解释处理作业说明书程序
类编译器程序
4 作业控制进程：执行作业控制程序进程
f) 批处理作业——作业控制程序
作业假脱机输入程序(SPOOLing 输入程序)控制进入输入井操作系统作业调度程序选择进入存建立作业控制进程
作业控制进程解释作业说明书语句根作业步求建立进程
图 作业控制程序工作原理 （批处理作业）
g) 交互式作业——系统passwd文件
分时系统说通常分时户次登录称作业
次登录系统提出请求请求应进程样分时作业进程间关系
分时系统中通设置口令文件实现分时户理UNIX系统该文件保存etcpasswd中Passwd文件中包含注册户信息
图 系统passwd文件 （交互式作业）
十 作业进程线程三者间关系
a) 作业进程关系进程线程关系
b) 作业进程
作业进入存变进程作业进程相应
进程实现作业完成功
c) 进程线程
支持线程系统中进程视单线程进程
支持线程系统中进程包含线程少包含线程
第三章 中断处理器调度
概述
中断实现道程序设计必条件
果没中断操作系统法获系统控制权处理器资源分配进程
二 中断概念
程序运行程中出现某种紧急事件必须中止前正运行程序转处理事件然恢复原运行程序程称中断
中断实现需硬件软件合作硬件部分称中断装置软件部分称中断处理程序中断装置中断处理程序称中断系统
三 中断装置
a) 定义
中断装置发现响应中断硬件机构
b) 中断装置发现响应中断步骤
1 识中断源
引起中断事件称中断源
中断源存时中断装置选择优先级高中断源
2 保存中断现场
正运行进程程序状态字PSW指令计数器PC中容压入系统栈（存中）
3 转入中断处理程序
中断事件应中断量存指定单元取出送入PSWPC中便转入应中断处理程序
图 中断响应程
c) 中断源中断字
引起中断事件称中断源
保存中断事件相关信息寄存器称中断寄存器
中断寄存器中容称中断字
d) 中断类型
1 强迫性中断
类中断正运行程序期运行程序意位置断
1 时钟中断：时钟时
2 输入输出中断：设备出错传输结束等
3 控制台中断：系统操作员通控制台发出命令
4 硬件障中断：掉电存校验错误等
5 程序错误中断：目态程序执行特权指令址越界溢出数0虚拟存储中缺页障等
2 愿性中断
类中断事件正运行程序意识安排执行访指令引起目求系统提供某种服务
例：C程序中fpfopen(…txt r+w)语句
e) 中断量
中断处理程序入口址(PC)运行环境(PSW)存放存中固定单元处中断事件发生时中断装置利PSWPC转入应中断处理程序类似量转移
PSWPC称中断量
图 中断量中断处理程序
注意：
1 类中断事件中断量
2 中断量存放位置硬件规定
3 中断量容OS系统初始化时设置
f) 中断嵌套
系统处理中断事件程中响应新中断称发生中断嵌套
般允许优先级更高中断事件断前中断事件处理程中断嵌套实际层数般会超中断优先级数
四 中断处理程序
进入中断处理程序般需进步保存现场
中断装置响应中断通中断量转入中断处理程序
中断处理程序需根中断码进步分析中断源进行相应处理根情况决定否需切换进程
a) 中断处理程序结构
1 关中断（屏蔽中断）
进步保存现场（址寄存器通寄存器等）
2 开中断（开放高优先级中断）
3 中断处理
4 恢复现场
5 中断返回
b) 中断处理整程
（CPU中断处理完成决定资源交进程）
c) 中断续元
户编中断处理程序称中断续元
中断续元入口址称中断续元入口
五 处理器调度
a) 定义
处理器调度(CPU scheduling)指CPU资源运行实体间分配
b) 分配
支持线程系统中OSCPU分配进程
支持线程系统中系统级线程OSCPU资源分配线程
户级线程OSCPU资源分配进程
六 处理器调度算法
（考计算知道算法原理意义特点）
a) 概述
处理器调度算法确定处理器空闲时应选择绪态进程投入运行
b) 选择处理器调度算法时指标
1 CPU利率：CPU量处忙碌状态
2 吞吐量：单位时间处理计算务数量
3 周转时间：计算务绪处理完毕时间
4 响应时间：务绪开始处理时间
5 系统开销：系统调度进程程中付出时空代价
c) 衡量绪务处理效率度量标准
1 周转时间(turnaround time)：绪开始时刻处理完毕时刻时间
2 均周转时间(average …)：进程周转时间进程数值
3 等时间：周转时间处理时间差
4 均等时间：进程等时间进程数值
d) 处理器调度时刻
1 非剥夺式调度(nonpreemptive)
1 指进程正运行进程里抢占CPU
2 采非剥夺式调度方式时进程旦选中运行直运行直出现情形：(1)该进程某种事件等(2)该进程运行完毕
3 优点：系统开销较
4 缺点：保证前正运行进程永远系统前运行进程中优先数高进程
2 剥夺式调度(preemptive)
1 指进程正运行进程里抢占CPU
2 采剥夺式调度方式时发生情形导致进程切换
(1)运行进程某种事件等 (2)运行进程运行完毕
(3)出现新优先级高正运行进程绪进程
新绪进程某进程唤醒动态创建新进程
3 优点：保证正运行进程永远系统前运行进程中优先级高进程
4 缺点：CPU进程间频繁切换系统开销较
七 常处理器调度算法（八）
a) 先先服务算法（非剥夺式）
1 基思想
先先服务(first come first serve FCFS)算法进程申请CPU次序（进程进入绪态次序）进行调度
2 优点
具公性会出现饿死情况
3 缺点
短进程（线程）等时间长导致均等时间较长
4 例子
b) 短作业优先算法（非剥夺式）
1 基思想
短作业优先算法(shortest job first SJF)算法CPU阵发时间递增次序调度易证明均周转（等）时间短（证明见作业二）
SJF算法中长短指CPU阵发时间长短
2 优点
务时达时均周转时间短限度降低均等时间
3 缺点
具公性较长绪务短务停达长期运行机会发生饥饿甚饿死
4 例子
c) 短剩余时间优先算法（剥夺式）
1 基思想
短剩余时间优先算法(shortest remaining time next SRTN)算法执行操作：
1 CPU空闲时选择剩余时间短线程进程
2 新进程线程达时较新进程前运行进程估计剩余时间果新进程需运行时间时间短切换运行进程
2 实质
该算法实质剥夺形式短作业优先算法效增加系统吞吐量
d) 高响应优先算法（非剥夺式）
1 基思想
高响应优先算法(highest response ratio next HRN)算法先先服务算法短作业优先算法折中响应次序调度
2 响应计算公式
RRBT+WTBT1+WTBT
中RR响应BTCPU阵发时间WT等时间
显然时达务处理时间较短务优先调度处理时间较长务着等时间增加动态提升响应会出现饥饿现象
3 缺点
系统开销较时常计算进程响应
e) 高优先数优先算法
1 基思想
高优先数优先(highest priority first HPF)算法进程PCB块中数字表示优先数需进行处理器分配时系统运行进程中选择优先数高者投入运行
2 优先数确定方法
1 静态优先数
进程创建时赋予优先数 该优先数进程整生存期固定变
优点：较简单 开销较
缺点：公性差 造成低优先数进程长期等
静态优先数法适合批处理进程
2 动态优先数
进程创建时赋予优先数该优先数进程生存期动态变化
进程获某种资源时优先级应增高进程处绪状态时优先级应着等时间增长提高等动态优先数算法适实时系统
优点：资源利率高公性
缺点：开销较实现较复杂
3 处理机调度时刻
1 非剥夺式静态优先数
获CPU进程直运行直终止等
2 剥夺式动（静）态优先数
获CPU进程运行直终止等出现高优先级进程
f) 循环轮转算法（剥夺式）
1 基思想
循环轮转(round robin RR)算法系统进程规定时间片(time slice)进程时间片长短轮流运行
2 调度程
采循环轮转算法时绪进程排成队列
处理机空闲时便选择队列头部进程投入运行时分时间片时间片完时果进程未结束CPU阵发未某种原等剥夺进程占处理机排绪队列尾部选择绪队列中队头进程运行
3 时间片
采循环轮转法进行调度时时间片长度需认真加考虑
果时间片长会影响系统响应速度
果短会频繁发生进程切换增加系统开销
通常时间片长度十毫秒百毫秒
4 优点
循环轮转法特适分时系统具公性响应时等特点
g) 分类排队算法
1 基思想
分类排队(multi level queues MLQ)算法称级队列法绪队列特征队列系统中运行进程某种原加分类实现某种调度目标
2 例子
例通操作系统中绪进程排成三队列：
Q1 实时绪进程队列
Q2 分时绪进程队列
Q3 批处理绪进程队列
处理机空闲时首先选择Q1中进程Q1空选择Q2中进程Q1Q2均空选择Q3中进程
队列部分采调度算法
h) 反馈排队算法
1 基思想
分类排队算法中进程绪队列间移动
反馈排队算法(feed back FB)绪队列特征队列部采循环轮转算法分类排队算法进程绪队列间移动
绪队列优先级次递减时间片长度次递增
图 反馈排队算法
进程创建者等时间发生时进入第级绪队列
某队列进程获处理器完该队列应时间片果尚未结束进入级绪队列
2 特点
1 短进程优先处理
运行时间短进程前面队列便已执行完队列中进程优先调度
2 设备资源利率高
设备交道进程会面原进入等状态：
(a) 申请资源占(b)启动IO传输
进程等资源IO传输完成时进入第级绪队列快获CPU资源
3 系统开销较
运行时间长进程进入优先级低队列队列时间片较长进程调度频率较低
3 缺点
反馈排队法中果高优先级队列直空低优先级队列中进程长时间运行机会便会发生饿死现象
解决问题常根某种原允许低优先级队列中进程移高优先级队列中助动态优先数算法调整序
4 优点
反馈排队算法适应性(adaptive)调度例子
八 调度级级调度
a) 处理器调度低级调度
处理器调度称低级调度(lowlevel scheduling)短程调度(short term scheduling)处理器资源分配进程线程真正前推进
低级调度中级调度高级调度起构成级调度
b) 交换中级调度
1 交换
交换(swapping)进程存外存储器间调度
交换目标般两：
1 缓解存空间等资源紧张矛盾
2 减发度降低系统开销
提高发度提高资源利率提高系统效率发度越高越
发度高会导致激烈资源竞争进程常等进程占资源降低进程推进速度甚导致死锁发度高会导致CPU资源进程线程间频繁切换增加系统开销
2 中级调度
中级调度(middlelevel scheduling)系统控制发度调度级
系统发度高时存中某进程暂时交换外存储器系统发度较低时调回存
图 具中级调度进程状态转换关系
（外存中进程等态绪态转换外存中直接完成）
c) 作业高级调度
1 作业调度
作业调度(job scheduling)称高级调度长程调度职作业输入井调入存建立相应进程具运行资格
2 作业五状态
提交状态：输入机输入井传输作业处提交状态
备状态：已进入输入井未调入存作业处备状态
执行状态：作业调度选中进入存处理作业处执行状态
(作业分解进程)
完成状态：处理完毕结果输出井作业处完成状态
退出状态：输出井印设备传送作业处退出状态
3 作业状态间转换
提交>备：SPOOLing输入进程完成
备>执行：作业调度程序(1)完成
执行>完成：作业调度程序(2)完成
完成>退出：SPOOLing输出进程完成
图 作业状态转换关系
作业调度程序(1)：
作业调度算法备作业集合中选择作业建立作业控制进程处理该作业
作业调度程序(2)：
等终止作业控制进程进行善处理
4 作
作业调度作业进程形式进入存获运行资格
真正获CPU运行需进程调度
作业调度中级调度进程调度构成调度三级
第四章 互斥步通信
进程互斥
进程互斥进程间发生种间接相互作
种相互作进程身希运行进程感觉
进程互斥发生相关进程间发生关进程间
二 享变量界区
a) 享变量：
进程均需访问变量称公变量(shared variable)称享变量
b) 界区：
访问享变量程序段称界区(critical region)称界段
界区段代码
图 享变量界区关系
三 界区进程互斥
a) 进程互斥定义
两两进程时进入关组享变量界区否发生时间关错误种现象称进程互斥
注意进程互斥相享变量言
b) 进程互斥实现
界区框架：
do {
entry section
界区
exit section
}while(1)
实现互斥编写entry sectionexit section保证时刻进程处界区
c) 界区相独占型资源资源理应满足原：
(1)关某组享变量界区均空闲时求进入该组享变量某界区进程应立进入
(2)关某组享变量某界区域占时求进入该组享变量某界区域进程应等
(3)进程离开关某组享变量某界区时应容许某等进入关该组享变量某界区域进程进入
四 进程步
a) 进程步定义
进程步进程间直接相互作合作进程间意识行种相互作发生相关进程间
b) 进程步概念
1 进程步
组进程协调推进速度某点处需相互等相互唤醒进程间种相互制约关系称进程步
注意：
进程步仅发生逻辑关系进程间进程互斥发生意两进程间
2 进程合作
组进程单独正常进行发正常进行现象称进程合作
参合作进程称合作进程
进程步合作进程间直接相互作
五 进程步机制
实现进程间步工具称步机制称步设施
典型进程步机制信号灯PV操作
六 信号灯PV操作相关定义
（求解决互斥步问题生产者消费者问题读者写者问题哲学家餐问题）
a) 信号灯PV操作定义
1 信号灯类型
定义：
struct semaphore {
int value
pointer_to_PCB queue
}
说明：
Semaphore s
2 信号灯类型valuequeue
信号灯变量包括两部分值部分svalue指针部分squeue
意时刻squeue指空指进程控制块构成队列头部初始时指空
value表示前资源数
svalue创建时赋次值直接改变value值通PV操作改变
value0时表示资源已分配完value<0时表示前没资源需排队等
3 asleep()wakeup()函数
asleep(s>queue)
执行操作进程进程控制块进入队列s>queue尾部状态运行态转等态系统转处理器调度程序
wakeup()
队列s>queue头部进程进程控制块该队列中取出排入绪队列状态等态转绪态
4 P操作原语(down)
原语：段间断执行程序称原语
void P(semaphore *s) {
s>value
if(s>value < 0) { 前申请时已没资源
asleep(s>queue) 进入等队列
}
}
P操作应申请资源
5 V操作原语(up)
void V(semaphore *s) {
s>value++
if(s>value < 0) { 表示前进程正等队列中等
wakeup(s>queue)
释放资源时资源分配等队列中第进程
}
}
V操作应释放资源
6 注意wakeup操作等队列队头元素取出等态改绪态表示前刚刚释放资源分配队头进程
进程执行V操作表示资源释放释放value>0表示前没进程正等资源value<0表示等队列中正进程等资源资源分配value>0表示资源分配等队列中资源弄混
b) 关信号灯变量规定
1 必须置次初值置次初值初值必需非负整数
2 执行P操作操作操作均非法
c) 关信号灯变量结
1 s>value>0时s>queue空
2 s>value<0时|s>value|s>queue中等进程数
3 s>value初值1时实现进程互斥需进入界区时执行次P操作离开界区时执行次V操作
4 s>value初值非1正整数时理种组合资源（具实例类资源5台印机）申请时执行次P操作时执行次V操作
5 s>value初值0时实现进程间简单步
（需先执行动作执行V操作执行动作前执行先执行P操作执行）
七 信号灯PV操作应
a) 信号灯变量实现进程互斥（初值1）
1 说明
2 图书阅系统问题
b) 信号灯变量实现进程步（初值0）
1 说明
先动作进程执行完动作进行V操作相动作进程发出信号告诉动作进程开始执行
动作进程通P操作表示信号然开始执行动作
2 司机售票员问题
注意组先动作应信号灯
P2先关车门P1启动P1先停车P2开门
八 信号灯变量解决综合问题——生产者—消费者问题
a) 问题描述
b) 问题分析
c) 问题解决
d) 求解程序
e) 优化
f) 问题实质
（果界缓区inout操作直接in+1out+1需k）
九 信号灯变量解决综合问题——读者—写者问题
a) 问题描述
b) 问题分析解决
c) 求解程序
d) 分析改进
分析 RR互斥读者源源断写者饿死
实写者操作更新数应优先进行否读者读时数
改进：写者优先
旦写者等正读读者结束写者进入新达读者等
十 信号灯变量解决综合问题——哲学家餐问题
a) 问题描述
五哲学家围坐张圆桌周围哲学家面前盘通心粉通心粉滑需两叉子夹住相邻两盘子间放叉子餐桌图示
哲学家生活中两种交活动时段：吃饭思考（种抽象哲学家言活动关紧）
哲学家觉饿时试图分两次取左边右边叉子次分次序果成功两叉子开始吃饭吃完放叉子继续思考
关键问题：哲学家写段描述行程序决会死锁？
b) 问题分析
哲学家交谈危险
产生死锁哲学家着左手餐叉永远等右边餐叉（者相反）
没死锁发生资源耗例假设规定哲学家等餐叉超五分钟放手里餐叉等五分钟进行次尝试策略消死锁（系统总会进入状态）然发生活锁果五位哲学家完全相时刻进入餐厅时起左边餐叉哲学家会等五分钟时放手中餐叉等五分钟时起餐叉
c) 问题解决
1 引入服务生
简单解法引入餐厅服务生哲学家必须允许起餐叉服务生知道餐叉正够作出判断避免死锁
演示种解法假设哲学家次标号AE果AC吃东西四餐叉中B坐AC间两餐叉法DE间空余餐叉假设时D想吃东西果起第五餐叉发生死锁相反果征求服务生意服务生会等样保证次两餐叉空余出时定位哲学家成功餐叉避免死锁
2 限制4位哲学家时进餐
3 哲学家状态增加3思考饥饿进食哲学家仅饥饿时申请叉子时申请左右两叉子果时左右两叉子空闲等
d) 限制4位哲学家时进餐求解程序
VAR fork Array [04] of Semophore(11111)
VAR count semophore 4
philosopher(i) begin
repeat
THINK
P(count)
P(fork[i])
P(fork[i+1] mod 5)
EAT
V(fork[i+1] mod 5)
V(fork[i])
V(count)
until false
end
e) 时申请两叉子求解程序
SP 信号量集解决哲学家进餐问题
VAR fork array[04] of Semaphore (11111)
Phi begin
repeat
THINK
SP( fork[i] fork[(i+1)mod 5] )
EAT
SV( fork[i] fork[(i+1)mod 5] )
until false
end
f) 问题实质
实际计算机问题中缺乏餐叉类缺乏享资源
种常计算机技术资源加锁保证某时刻资源程序段代码访问
程序想资源已程序锁定等资源解锁
程序涉加锁资源时某情况发生死锁
例某程序需访问两文件两样程序锁文件等方解锁文件永远会发生样会导致死锁
十 信号灯变量解决综合问题——三台印机理
a) 问题描述
设3台类型相印机编号分123试编写申请函数require释放函数return
require印机空闲时返回分印机编号印机空闲时等唤醒返回分印机编号
return释放指定编号空闲印机申请者等时唤醒
b) 求解程序
enum lp[13] of (freeused) (initial value is free) 表示空闲状态
semaphore S (initial value is 3) 表示3台印机
semaphore mutex (initial value is 1) 实现互斥
13 require() void return(i 13)
{ {
P(S) P(mutex)
P(mutex) lp[i]free 释放印机
for(i1 i<3 i++) V(mutex)
if(lp[i]free) V(S)
break }
lp[i]used 占第台空闲印机
V(mutex)
return(i)
}
十二 信号灯变量解决综合问题——吸烟者问题
a) 问题描述
假设系统中三抽烟者进程抽烟者断卷烟抽烟抽烟者卷起抽掉颗烟需三种材料：烟草纸火柴抽烟者烟草纸火柴
3供应商进程：
X 提供 tobacco match
Y 提供 match wrapper
Z 提供 wrapper tobacco
tobacco烟草match火柴wrapper纸
3吸烟者进程：
A 拥 tobacco
B 拥 match
C 拥 wrapper
限制条件：
(1) 时刻XYZ供应资源
(2) 提供资源耗XYZ继续供应资源
b) 传统解法
传统信号量解法：
semaphore t m w s 0 0 0 1
t m w分表示三种烟量
s实现互斥
Process X process Y process Z
P(s) P(s) P(s)
V(t) V(m) V(w)
V(m) V(w) V(t)
Process A Process B process C
P(m) P(w) P(t)
P(w) P(t) P(m)
smoke smoke smoke
V(s) V(s) V(s)
c) 存问题
进程X提供tobaccomatch分进程A进程C获导致死锁
意改变吸烟者进程两P操作次序防止死锁发生
d) 问题原解决方式
产生种错误原吸烟者进程需外两种资源通两P操作分申请
果两种资源时申请（时执行P操作）防止种问题
e) 解决问题
需扩展P操作够信号量变量时执行P操作V操作SP(simultaneous P时执行P操作)SV(时执行V操作)
作信号量集合
f) SPSV操作
si值ti次变换步长di
SP(S1t1d1 … Sntndn)
{
if S1>t1 and … and Sn>tn then
for I1 to n
do SiSidi
endfor
else
运行进程进程控制块连第si
}
SV(s1 d1 … sn dn )
{
for i 1 to n do
Si Si + di
si队列进程控制块取出连绪队列中
}
中si信号量tidi均1时称and型信号量常种形式
g) 正确解法
semaphore t m w s 0 0 0 1
Process X Process Y Process Z
loop loop loop
P(s) P(s) P(s)
SV(t1 m1) SV(m 1w 1) SV(w 1 t 1)
endloop endloop endloop
Process A Process B Process C
loop loop loop
SP(m11 w11) SP(w11 t11) SP(t11 m11)
smoke smoke smoke
V(s) V(s) V(s)
endloop endloop endloop
十三 进程高级通信分类概念模式
a) 进程通信分类
1 低级通信
进程互斥进程步称进程间低级通信
2 高级通信
进程间宗数传递称进程间高级通信
b) 进程通信概念
进程间互斥步信息交换统称进程通信
(interprocess communication IPC)
c) 进程通信模式
1 享存模式(shared memory)
种模式适单机系统
相互通信进程间公存组进程公存中写组进程该公存中读便实现进程间信息传递
2 消息传递模式(message passing)
种模式适单机系统网络环境
采种模式时操作系统户进程间通信提供两基系统调命令（称原语）发送命令(send)接收命令(receive)
需进行消息传递时发送者仅需执行发送命令接收者仅需执行接收命令消息便发送者传送接收者
消息发送者传送接收者完全OS完成户透明
十四 进程通信消息传递模式两种实现方式
a) 概述
消息传递模式实现时分两种方式：
直接方式：进程进程
间接方式：进程信箱进程
b) 直接方式
谓直接方式指相互通信进程间通信时直呼名
说发送者发送时指定接收者名字接收者接收时指定发送者名字
系统调两种形式：
1 称形式(symmetric)
称形式特点发送者发送时指定唯接收者接收者接收时指定唯发送者
系统调命令：
send(R M) 消息M发送进程R
receive(S N) 进程S处接收消息N
2 非称形式(asymmetric)
非称形式特点发送者发送时指定唯接收者接收者接收时指定具体发送者
系统调命定：
send(R M) 消息M发送进程R
receive(pid N) 接收消息N返回时设pid发送进程标识
N接收信息存pid发送进程号
发送进程相顾客接收进程相服务员服务员顾客服务服务时知道位顾客求服务位顾客先先位顾客服务
c) 消息发送进程空间传送接收进程空间途径
1 缓途径（知道步骤）
采条途径时操作系统空间中保存着组缓区
发送进程执行send系统调命令时产生愿性中断进入操作系统操作系统发送进程分配缓区发送消息容发送进程空间复制缓区中然载消息缓区连接收进程消息链中
完成信息发送发送进程返回户态继续执行面程序
某时刻接收进程执行receive系统调命令时产生愿性中断进入操作系统操作系统载消息缓区消息链中取出消息容复制接收进程空间中然收回该空闲缓区
完成消息接收接收进程返回户态继续执行面程序
消息发送者接收者间传输程次缓提高系统发性发送者旦信息传送缓区返回继续执行面程序须等接收者真正执行接收条消息系统调命令
图 发送进程接收进程间关系
（M进程发送区起始址N进程接收区起始址）
图 缓区中消息
（发送者接收者消息链操作应互斥进行进程作接收进程条消息链消息链互斥变量m_mutex分存放进程PCB中）
图 空闲缓区链
（收发进程间关系类似生产者——消费者问题消息缓区类似箱子容量k）
现出发送原语send接收原语receive实现程Sendreceive属系统调命令位户程序中系统户态执行命令时发生愿性中断事件进入操作系统操作系统总控程序判断转相应处理程序
Sb缓区数量sm接收进程消息资源数量
注意：Sendreceive 高级通讯原语低级原语PV实现
Sendreceive真正意义原语中断
2 缓途径
果操作系统没提供消息缓区发送进程空间直接传送接收进程空间
优点节省空间
缺点发性差发送进程必须等接收进程执行receive命令消息发送进程空间复制接收进程空间返回继续前推进
d) 间接方式
谓间接方式指相互通信进程间通信时直呼方名字指明中间媒体信箱进程间通信箱实现通信
时系统提供高级通信原语信箱取代进程
第五章 死锁饥饿
死锁概念
组进程中进程均等组进程中进程占永远法资源种现象称进程死锁简称死锁(deadlock)
死锁发生参死锁进程直持续非参死锁进程外某种干预
（1 进程竞争资源引起僵持称死锁）
（2 死锁解需外干预）
二 关死锁结（4）
a) 参死锁进程数目少2
b) 参死锁进程均等资源
c) 参死锁进程少2占资源
d) 参死锁进程系统中前正运行进程集合子集
三 死锁类型
a) 竞争资源引起死锁
进程争夺系统中限资源引起死锁
面谈死锁种类型死锁
资源：进程时释放进程
b) 进程通信引起死锁
基消息系统中P1等P2消息P2等P3消息P3等P1消息种循环等消息引起死锁称进程通信引起死锁
生灭资源：次利资源消息生灭资源
c) 原引起死锁
P1P2竞争独占型资源P1P2先P2P1先两进程均法推进称After YouAfter You问题
四 死锁条件（4）
面出死锁发生4必条件称coffman条件
a) 资源独占(mutual exclusion)
资源时刻分配进程
果进程申请某资源该资源正外某进程占申请者需等
直占者释放该资源
b) 剥夺(nonpreemption)
资源申请者强行资源占者手中夺取资源资源占者完愿释放
c) 保持申请(hold and wait)
进程占部分资源申请新资源申请新资源时候释放已占资源
d) 循环等(circular wait)
存进程等序列{p1 p2 … pn}中p1等p2占某资源p2等p3占某资源……pn等p1占某资源
e) 仅述4条件时满足时死锁会发生
换言破坏4条件中意死锁会发生
五 死锁处理
死锁处理分死锁预防死锁避免
a) 预防（静态）
预防进程关资源活动加静态限制进程遵守协议发生死锁
预防策略两种：预先分配序分配
1 预先分配
进程运行前次性系统申请需全部资源果系统前满足进程全部资源请求分配资源进程暂时投入运行果系统前满足全部资源请求次性申请资源全部分配进程
进程投入运行前已申请需全部资源运行期间会发出新资源申请命令破坏保持申请必条件
2 序分配
事先资源类完全排序资源类赋予唯整数进程必须资源编号次序申请资源
进程占资源时 申请ri资源申请rj中资源充条件：f(ri)
b) 避免（动态）
避免进程关资源申请命令加动态实时检测拒绝安全资源请求命令保证死锁会发生
六 银行家算法（掌握思想需写）
银行家算法种避免死锁算法
a) 安全状态安全状态
果存系统中进程构成安全序列P1…Pn系统处安全状态安全状态时定没死锁发生
安全序列指进程序列{P1…Pn}安全进程Pi(1≤i≤n）尚需资源量超系统前剩余资源量进程Pj (j < i )前占资源量
安全状态少存条路线：p1pn次执行路线进程执行完存死锁
安全状态定死锁状态安全状态定死锁状态
b) 说明
新进程进入系统时必须声明资源需求量资源类需少资源实例
进程发出资源申请命令系统够满足该请求时系统判断：果分配申请资源系统状态否安全
果安全分配资源申请者继续否分配资源申请者等
c) 实现银行家算法需数结构
设n系统中进程总数m资源类总数
P{p1p2…pn}
R{r1r2…rm}
1）利资源量int Available[m]
含m元素数组中元素代表类利资源数目果Available[j]K表示系统中现Rj类资源K初始时Available值系统资源总量
2）需求矩阵int Claim[n m]
n×m矩阵定义系统中n进程中进程m类资源需求果Claim [ij]K表示进程i需Rj类资源数目K
3）分配矩阵int Allocation[n m]
n×m矩阵定义系统中类资源前已分配进程资源数果Allocation[ij]K表示进程i前已分Rj类资源数目K初始时Allocation[I j]0
4）需求矩阵int Need[n m]
n×m矩阵表示进程尚需类资源数果Need[ij]K表示进程i需Rj类资源K方完成务
Need[ij] Claim [ij]Allocation[ij]
初始时NeedClaim
5) 前请求矩阵 int Request[n m]
n×m矩阵表示进程前申请资源类中资源实例数量果Request[I j]k进程i需资源rj中k资源实例
引入列记法：
设XY标1l维数组：
X£Y Û j (1£j£l) X[j]£Y[j]
XY Û j (1£j£l) X[j]Y[j]
Xc Û j (1£j£l) X[j]c
X±Y Û j (1£j£l) X[j]±Y[j]
实现安全性检查需定义数结构：
6) int Work[m]
记录资源
7) int Finish[n]
记录进程否执行完
d) 银行家算法——资源分配算法
e) 银行家算法——安全性检测算法
f) 银行家算法例子
g) 银行家算法保守性
七 饥饿活锁
a) 定义
等时间进程推进响应带明显影响时称发生进程饥饿(starvation)饥饿定程度进程赋予务完成具实际意义时称该进程饿死(starve to death)
忙式等条件发生饥饿称活锁．
（饥饿没界等般资源分配合理致等时间超极限会导致饿死）
b) 死锁饿死联系
饿死死锁定联系：二者竞争资源引起明显差表现方面：
(1) 进程状态考虑死锁进程处等状态忙式等(处运行绪状态)进程非处等状态饿死
(2) 死锁进程等永远会释放资源饿死进程等会释放会分配资源等时限没界(排队等忙式等)
(3) 死锁定发生循环等饿死然 表明通资源分配图检测死锁存否检测否进程饿死
(4) 死锁定涉进程饥饿饿死进程．
c) 饥饿饿死资源分配策略(policy)关防止饥饿饿死公性考虑确保进程忽视FCFS分配算法
八 死锁饥饿例子——独木桥问题
a) 题目描述
假设座东西车辆单行道桥图示次允许方干车辆通（桥方车辆通）桥没车辆时端车辆允许桥通车辆桥端车辆继续桥端车辆桥载重4辆汽车请PV操作实现东西两端桥问题
b) 分析思想：
题基读者－写者问题算法（写进程优先）
设置两变量：
eastn记录东端桥西端车辆数
westn记录西端桥东端车辆数
初值均0
两变量互斥访问设置两互斥访问信号量meastmwest初值均1
东端桥西端桥车辆言桥没车辆时谁先请求谁先桥设置互斥访问信号量wait初值1
增设信号量scount表示桥时桥车辆数初值4
int eastn0 记录东端桥西端车辆数
int westn0 记录西端桥东端车辆数
Semaphore meast1 保护eastn变量信号量
Semaphore mwest1 保护westn变量信号量
Semaphore scount4 表示桥车辆计数信号量
Semaphore wait1 确定东西两端桥请求桥序互斥信号量
1） 巴马运河西洋太洋两方船设置两进程Atlantic()Pacific()
2） 侧船运河果侧船河等果方船河时方船总河船数T河果方船河时方船河总数T等
3） 避免饥饿死锁必须控制次河船数T
c) 解决程序
main()
{
Cobegin
{
进程easti（i12…） 东端车辆桥进程
{
while (true)
{
P(wait) 东端车辆先请求先桥
P(meast) 拒绝访问eastn变量
if (eastn0) 东端第辆车桥禁止西端车辆桥
P(mwest)
eastneastn+1 东端桥车辆数增1
V(meast) 恢复访问eastn变量
V(wait) 恢复车辆桥
P(scount) 递减时桥车辆数
东端西端桥
V(scount) 递增时桥车辆数
P(meast) 拒绝访问eastn变量
eastn 东端桥车辆数减1
if (eastn0) 东端没车辆桥允许西端车辆桥
V(mwest)
V(meast) 恢复访问eastn变量
}
}
进程westj（j12…） 西端车辆桥进程
{
while (true)
{
P(wait) 西端车辆先请求先桥
P(mwest) 拒绝访问westn变量
if (westn0) 西端第辆车桥禁止东端车辆桥
P(meast)
westnwestn+1 西端桥车辆数增1
V(mwest) 恢复访问westn变量
V(wait) 恢复车辆桥
P(scount) 递减时桥车辆数
西端东端桥
V(scount) 递增时桥车辆数
P(mwest) 拒绝访问westn变量
westn 西端桥车辆数减1
if (westn0) 西端没车辆桥允许东端车辆桥
V(meast)
V(mwest) 恢复访问westn变量
}
}
}
Coend
}
种解法：
九 死锁饥饿例子——河问题
a) 问题描述
b) 问题分析
限定时河数5
两岸竞争1234两石块采序分配法
c) 求解程序
十 系统举例
死锁数系统中采视见鸵鸟算法Edsger Wybe Dijkstra设计实现THE系统中采避免死锁银行家算法
第六章 存储理
存资源理
a) 存分区
分区时刻
静态分区：系统初始化时分
动态分区：申请时分
分区
等长分区：2i
异长分区：程序程序单位象
通常作法
静态+等长（页式段页式）
动态+异长（段式界址）
b) 存分配
1 静态等长分区分配
l 字位映象图（bit map）
l 空闲页面表
l 空闲页面链（链表操作较耗费资源）
2 动态异常分区分配（区分三种算法）
理长度等区域需种称空闲区域表数结构
l 先适应算法
l 佳适应算法
l 坏适应算法
二 存储理方式（三张图非常重）
a) 页式存储理
P181P187
重点P184 图616
b) 段式存储理
P187P193
重点P191 图627
c) 段页式存储理（掌握思想）
P193196
三 虚拟存储系统（注意颠簸页障率反馈模型）
a) 虚拟问题
运行存程序
进程全部装入存浪费空间（进程活动具局部性)
b) 程序局部性原理
1 时间局部性
条指令执行条指令次执行数访问条数次访问时间相集中程序中存量循环操作
2 空间局部性
相邻指令相邻数执行时常集中程序序执行数组访问
c) 虚拟存储
进程部分装入存部分（全部）装入外存运行时访问外存部分动态调入存够淘汰
d) 虚拟页式存储理
1 基原理
程序运行前部分页面装入存部分页面（全部页面）装入外存进程运行程中果访问页面存虚拟情形相果访问页面存发生缺页障进入操作系统操作系统进行页面动态调度
2 缺页障中断处理程序
访问页存发生缺页中断中断处理程序：
找访问页外存址
存找空闲页面
没淘汰算法淘汰
需淘汰页面写回外存修改页表总页表
读入需页面（切换进程调度进程）
重新启动进程执行中断指令
3 存页框分配策略
1 均分配
2 进程长度例分配
3 进程优先级例分配
4 进程长度优先级例分配
4 外存块分配策略
1 静态分配
外存保持进程全部页面：
优点：速度快—未修改页面情况淘汰时必写回
缺点：外存浪费
2 动态分配
外存仅保持进程存页面：
优点：节省外存
缺点：速度慢淘汰时必须写回
5 页面调入时机
1 请调(demand paging)
upon page fault 发生缺页中断时调入
2 预调(prepaging)
before page fault 缺页障前调入(根程序序行定准）
定准然缺页预调必须辅请调
6 置换算法
：页淘汰段淘汰快表淘汰
1佳算法（理）
2先进先出算法
3少算法
4先淘汰算法
5频繁算法
e) 颠簸(thrashing)
1 颠簸定义
页面存外存间频繁换入换出致系统调度页面时间进程实际运行占时间长
颠簸页障率高产生结果
2 颠簸原
(1) 分进程物理页架少
(2) 淘汰算法合理
(3) 程序结构
程序滥转移指令会影响程序局部性
3 颠簸处理
(1) 增加分进程物理页架数
(2) 改进淘汰算法
(3) 改进程序结构
量避免goto语句
f) 工作集模型
g) 页障率反馈模型
工作集模型够成功指导页面分配防止发生颠簸实现开销较较困难
颠簸页障率高引起系统通页障率反馈信息动态调整页面分配
第七章 文件系统
文件概念
文件(file)具符号名逻辑完整意义信息项序序列
二 文件组织
a) 概述
文件组织称文件结构中涉文件逻辑组织文件物理组织
文件逻辑组织指文件外部组织形式户文件组织形式
文件物理组织指文件部组织形式文件物理存储设备组织形式
b) 文件物理组织
1 确定文件物理结构应考虑素（四种）：
(1)记录格式
文件记录格式分定长变长两种
定长格式实现较简单速度快浪费存储空间
变长格式实现较复杂速度慢节省存储空间
(2)空间开销
空间开销指保存文件容外需额外存储开销包括外存开销文件时需存开销
例文件目录信息记录存调时保存信息
(3)存取速度
存取速度包括序存取速度号机存取速度键机存取速度
(4)长度变化
长度变化指文件长度动态增加动态减少尤指文件长度动态增加
2 文件常物理组织形式：
序结构链接结构索引结构散列(Hash)结构倒排结构等
c) 文件常物理组织形式
1 序结构(sequential structure)——数组
2 链接结构(linked structure)——链表
3 索引结构(indexed structure)——结合两种结构优点
4 散列结构(hash structure)——哈希表
5 倒排结构(inverted structure)
6 种文件物理结构特征较
三 文件控制块
a) 定义
文件控制块(file control block FCB)标志文件存数结构 中包含系统文件进行理需全部信息
b) 容
文件名 享说明
文件号 文件逻辑结构
户名 文件物理结构
文件址 建立日期
文件长度 修改日期
记录 访问日期
文件类型 口令
文件属性
四 文件系统实现
a) 什文件系统
文件理信息资源程序集合称文件系统(file system)
b) 概述
实现文件系统存OS空间中需保存干表目
外需理保存文件容外存空间
c) 存需表目
1 系统开文件表(整系统)
FCB中保存着系统理文件需信息信息作目录项长驻外存
文件开时FCB中信息需常访问提高速度需读存
系统开文件表存中保存已开文件FCB表目
表容FCB部外 包含三信息
(1)文件号 该文件FCB部外存中位置
(2)享计数 记录前少进程正该文件值零时表明空表目
(3)修改标志 标识某文件FCB存期间否修改正该文件进程关闭该文件时 果该FCB存期间修改 需存中修改FCB写回外存否需刷新外存
2 户开文件表（进程）
文件享进程时开文件开方式前读写位置样
信息记录表中 该表称户开文件表 进程
表中系统开文件表入口指针 指该文件FCB系统开文件表中入口址进程文件时 进程户开文件表中会相系统开文件表入口
表中文件描述符正整数 值表中位置隐含确定实际记表中文件开返回进程进程便描述符存取该文件文件名字
户开文件表存储位置记录进程PCB中 户开文件表长度决定进程时开文件数量
3 户开文件表系统开文件表联系
户开文件表指系统开文件表进程享文件 户开文件表目指系统开文件表入口
第八章 设备输入输出理
设备分类
a) 块型设备字符型设备
1 块型设备
块型设备存储型设备类设备干长度相块构成
2 字符型设备
字符型设备输入输出型设备（包括通信设备）类设备进行数传输基单位字节
b) 独占设备非独占设备
1 独占设备
独占设备包字符型设备磁带机意段时间进程占
2 享型设备
享型设备包括磁带机外块型设备进程数传输块单位交叉
特例：磁带机然块单位存储设备物理特性原必须独占
二 数传输方式——通道方式
a) 通道定义
通道专门负责输入输出操作处理器DMA（存储器直接访问）数块传输功外通道具更加强输入输出功
b) 通道方式DMA方式区
相点：存中心支持块传输
点：通道专门处理器指令系统实施复杂输入输出控制
c) 通道程序位置
通道程序放存中
d) 通道容
通道相功单纯处理器涉容：
1 通道指令系统
基操作：空操作读写控制转移结束
指令格式：（操作码传输量特征位址）
操作码指定操作类型
2 通道控运部件
CAW：记录条指令存放址类似指令计数器
CCW：记录正执行指令类似指令寄存器
CSW：记录通道控制器设备状态
CDW：暂存存设备间输入输出传输数
3 通道存储区域
通道没独立存储空间需机享存空间
通周期窃方式实现通道CPU行工作
4 通道程序执行程
条通道指令传送组数通道程序传送组数
组数全部传输完毕处理器发次中断减轻机负担
三 设备驱动
a) 通道程序
CCW指令序列
静态编制动态生成
b) 设备启动
通道启动
c) 中断处理
通道结束操作CPU发中断
d) 通道处理器间相互作关系（图明白）
四 虚拟设备
a) 定义
利享型设备实现数量较速度较快独占型设备成虚拟设备
b) 虚拟设备实现（重点）
假脱机系统（称SPOOLing系统）例介绍虚拟设备实现
P285288
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
