《操作系统原理》PPT课件.pptVIP

1 OperatingSystemPrinciples 操作系统概述进程管理存储管理文件系统与I O 2 第一部分操作系统概述 一 操作系统的功能 实现对计算机资源的管理 CPU 存储器 I O设备 控制应用程序的执行提供应用程序访问计算机资源的接口 系统调用 实现对操作系统内核及应用程序的保护 操作系统给计算机一个灵活的大脑 一个强健的心脏和突出的个性 3 二 OS的分类 批系统 batchsystem 成批提交作业 作业完成或无法继续执行时发生切换交互 分时 系统 interactive Time sharingsystem 多个用户 应用程序 分享计算机资源Windows Linux 实时系统 Real timesystem 满足应用的时间约束要求VxWorks QNX 4 三 操作系统的体系结构 单内核结构 Monolithic macro kernel 与微内核结构 micro kernel 孰优 5 Monolithicvs micro kernel quotingLinusTorvalds messagepassingasthefundamentaloperationoftheOSisjustanexerciseincomputersciencemasturbation Itmayfeelgood butyoudon tactuallygetanythingDONE Monolithic 内核中所有的子系统运行在相同的特权级 privilegedmode 拥有相同的地址空间 通信采用常规C函数调用的形式 6 四 操作系统的硬件支持 特权级 区分OS与应用程序的权限 MMUCache中断 7 五 系统调用 操作系统提供给应用程序的一个接口 使得应用程序能够获得操作系统的服务进程管理 文件管理 存储管理 系统管理等 系统调用是一个复杂的过程系统调用往往通过软中断的方式实现系统调用在为应用程序提供操作系统服务的同时 也实现了对计算机资源和应用程序的保护 8 第二部分进程管理 一 进程 Process aprograminexecutiontextsection datasection stack currentactivity进程是资源拥有的基本单位 unitofresourceownership CPU 存储空间 及其他资源 I O设备 文件等 进程控制块 PCB 及其管理进程的状态 running ready blocked stopped zombie 9 二 线程 thread Thread anexecutionpathinaprocessThread theunitofdispatching进程中的线程共享进程资源 但拥有私有堆栈及线程控制块 TCB 存储寄存器值 优先级及其他线程状态信息 核心级线程 KLT kernel levelthread 应用程序通过API调用核心线程管理例程 kernelthreadfacility 来管理 需要进行模式切换是OS调度的基本单位线程阻塞不会导致整个进程的阻塞在多处理器环境下 内核可使线程在不同的处理器上运行E g windowsthread 10 用户级线程 ULT user levelthread 由应用程序自己通过线程库 threadlibrary 来管理 线程创建 终止 线程间通信 线程调度与切换OS感知不到ULT的存在线程阻塞会导致整个进程的阻塞理论上讲 在任何OS下都可以实现无法利用多处理器 11 12 include includeintsum void runner void param main intargc char argv pthread ttid pthread attr tattr pthread attr init 13 三 并发控制 互斥与同步并发 Concurrent 与并行 Parallel 临界资源 criticalresource 一次只能由一个进程访问的资源临界区 criticalsection 访问临界资源的代码段称为临界区 CS 14 互斥 mutualexclusion 在一个时刻最多只有一个进程在临界区同步 synchronization 协调需要访问临界资源的进程 否则会导致racecondition 竞争条件 如 两进程p0 p1 都通过下面的代码访问一个共享的存储单元 Sharedvariable inttotal 0 p0 p1 intcount for count 1 count 50 count total total 1 total可能的结果 最大值 最小值 注意total是两个进程都可以访问的共享存储单元 不同于一般程序中的全局变量 15 临界区问题解决方法正确性的准则 两个前提 对处理器数及各进程的相对运行速度 不会是零速度 不应该有任何假设进程在临界区停留的时间是有限的三个必须 互斥 mutualexclusion 有空让进 progress 若没有进程在临界区 则应该让申请进入临界区的进程中的一个立即进入有限等待 boundedwaiting 申请进入临界区的进程不会无止境的等待 即不会有饥饿现象 16 临界区问题的解决方法 1 软件方法 忙等待 Sharedvariablesbooleanflag 2 initiallyflag 0 flag 1 false intturn initiallyturn i ProcessPido flag i true while turni while flag j turn i flag i false while 1 此算法正确吗 17 Peterson算法 算法直观 只能解决二个进程同步P0 do flag 0 true 希望进入turn 1 给对方一次机会whileflag 1 andturn 1do nothing 如果对方先申请则等待flag 0 false while 1 18 2 利用硬件支持中断屏蔽 interruptdisable 代价大 无法做到程序的交叉执行 interleave 多处理环境下无法实现特殊机器指令TestandSetInstructionExchangeInstruction优点 适合多处理器环境 简单缺点 必须忙等待 busywaiting 可能导致饥饿 19 3 信号量 semaphore 无忙等待 OS提供的装置 用于进行进程 线程的同步与互斥数据结构 s count integer 0表示可用资源数 0 其绝对值表示挂起进程数 初始化非负queue listofprocess 正在等待该类资源的进程进程只能通过OS提供的wait和signal两个操作原语访问信号量Wait s 等待资源s count s count 1 ifs count 0thenbeginplacethisprocessins queue blockthisprocess end Signal s 释放资源s count s count 1 ifs count 0thenbeginremoveaprocessPfroms queue placeprocessPonreadylist end 20 信号量full 初始化为0 表示缓冲区中可消费的资源数mutex 初始化为1 用于对缓冲区的互斥操作empty 初始化为缓冲区的长度N 表示缓冲区中空闲单元数Producer repeatproduce wait empty wait mutex append signal mutex signal full foreverConsumer repeatwait full wait mutex take signal mutex signal empty consumeforever 利用信号量解决CS问题实例 生产者 消费者问题 21 例 有n个进程 P1 P2 Pn 向容量为M的缓冲区写数据 每个进程一次写1个数据 当缓冲区写满时 另一个读进程Pr一次将M个数据全部读完 如此反复 请用信号量解决这些进程的同步互斥问题 答 本题中需要定义下述变量和信号量 data typebuffer M data type对应于所需要的数据类型 如int float等 intin 0 用来指示下一个可存放数据的缓冲区 semaphoreempty M 对应空闲的缓冲区 semaphorefull 0 对应缓冲区中的数据 semaphoremutex 1 用来实现Pi进程对变量in的互斥访问 进程Pi可描述为 Pi while 1 wait empty wait mutex 向缓冲区buffer in 中写数据 in in 1 M signal mutex signal full 进程Pr可描述为 Pr inti while 1 for i 0 i M i wait full wait mutex 取出缓冲buffer 0 到buffer M 1 中的数据 signal mutex for i 0 i M i signal empty 22 例 有一个仓库 可以存放A和B两种产品 但要求 1 每次只能存入一种产品 A或B 2 N A产品数量 B产品数量 M 其中 N和M是正整数 试用信号量来同步产品A与产品B的入库过程 答 本题中 首先需要设置一个初值为1的互斥信号量mutex 以保证每次只存入一种产品 另外 为了保证 N A产品数量 B产品数量 M 还需设置信号量SA 表示仓库中目前可再存放的A产品的数量 其初值为M 1 SB 表示目前还可再存放的B产品的数量 其初值为N 1 A产品入库的过程可描述为 B产品入库的过程可描述为 while 1 while 1 wait SA 还可放A产品 wait SB 还可放B产品 wait mutex wait mutex 将A产品放入仓库 将B产品放入仓库 signal mutex signal mutex signal SB 可放B产品数增1 signal SA 可放A产品数增1 23 四 并发控制 死锁问题 1 死锁 deadlock 系统中存在一个进程集合 该集合中的每个进程都占用了一定数量的资源 并且在等待被集合中的其他进程占用的资源例 某系统由相同类型的8个资源组成 若资源可被3个进程共享 每个进程最多可申请3个资源 问该系统是否会发生死锁 24 2 死锁发生的4个必要条件 Mutualexclusion 互斥Holdandwait 保持等待 申请资源时拥有其他资源Nopreemption 非剥夺 进程占有的资源只能由进程自己释放 不会被别的进程剥夺Circularwait 循环等待 若各类资源的资源数为1 则一定死锁 25 3 deadlockprevention死锁预防 间接预防 阻止Mutualexclusion Holdandwait及Nopreemption都满足直接预防 阻止circularwait的发生 一种可行的方法 有序申请法 对所有资源类别编号 进程申请资源按序进行 例 哲学家就餐问题 筷子编号 先拿编号小的 再拿大的 26 4 deadlockavoidance死锁避免 进程申请资源时 决定是否应该满足必须预先知道每个进程需要的各类资源数Banker salgorithm 银行家算法基本思想 若新的状态是安全的 safe 则满足它Safestate 从此状态出发 存在某种执行顺序 安全序列 safesequence 可以使所有进程执行完毕 安全状态只是暂时安全 如果以后资源分配不当 也会导致死锁 不安全状态不一定就死锁 27 状态 a 是安全的 a b c d e a b c d 状态 b 是不安全的 28 5 死锁检测是否必要 P4没有获得资源 打上标记置W 0 0 0 0 1 P3请求的资源 W 给P3打标记 并置W W 0 0 0 1 0 0 0 0 1 1 算法无法找到满足条件的进程 终止 所以系统发生死锁 P1和P2是死锁进程 R1R2R3R4R5 P1P2P3P4 RequestAllocatedAvailable R1R2R3R4R5 R1R2R3R4R5 01001001010000110101 10110110000001000000 00001 29 6 死锁恢复 当发生死锁时 如何恢复死锁Abortalldeadlockedprocesses Abortoneprocessatatimeuntilthedeadlockcycleiseliminated Inwhichordershouldwechoosetoabort Priorityoftheprocess Howlongprocesshascomputed andhowmuchlongertocompletion Resourcestheprocesshasused Resourcesprocessneedstocomplete Howmanyprocesseswillneedtobeterminated Isprocessinteractiveorbatch Selectingavictim minimizecostRollback returntosomesafestate restartprocessforthatstate Starvation sameprocessmayalwaysbepickedasvictim includenumberofrollbackincostfactor 30 五 CPU调度 CPUscheduling 1 CPU约束进程与I O约束进程进程的执行是CPUburst与I Oburst交替的过程CPU约束进程 大量时间作计算 少量I OI O约束进程 大量的I O 少量时间作计算 31 2 调度准则 criteria 32 3 调度模式 decisionmode Non preemptive 非抢占式 进程一旦被调度 则执行至结束或不能继续执行 如因为发起I O操作而等待 Preemptive 抢占式 当一个新的进程到达时当有进程从阻塞变为就绪时进程从核心态返回到用户态时 如中断 系统调用返回时 注 此抢占非指内核抢占 33 4 常用调度算法FCFS firstcomefirstserved 先来先服务 直至结束 nonpreemptive RR Roundrobin时间片轮转 timeslice preemptive 时间片到时 将进程放入就绪队列的末尾 然后从队列头部取出一个进程运行公平的调度策略 不会导致进程饥饿Priorityscheduling 基于优先级的调度存在问题 饥饿 低优先级进程可能永远得不到执行解决办法 老化 Aging 随着时间的推移 进程的优先级可以提升 即进程的优先级可以是动态的 34 第三部分存储管理 一 基本概念Relocation 重定位 程序只有在执行时才能确定其在内存中的位置Protection 保护 进程在未被允许时不能访问其他进程的地址空间Sharing 共享 应该提供机制允许进程访问共享地址空间中的信息Logicaladdress 逻辑地址 用户进程访问的地址 即虚地址Physicaladdress 物理地址 物理存储器的地址 35 36 二 物理内存管理 分区 将内存划分为若干个分区 每个分区存放一个进程 以支持多道程序 multi programming Fixedpartitioning 固定大小的分区 分区内部会出现碎块 internalfragment Dynamicpartitioning 动态分区 按照进程大小决定分区大小 不存在内部碎块 但有外部碎块 externalfragment 涉及放置算法 placementalgorithm firstfit bestfit nextfit OS process5 process8 process2 OS process5 process2 OS process5 process2 OS process5 process9 process2 process9 process10 37 Buddysystem 常用于空闲内存管理 38 三 分页 分段及段页式存储管理 若一次TLB访问时间为 一次存储器访问时间为1TLB命中率为 则平均存取时间EAT为 EAT 1 2 1 2 页表的实现方式 页表分级Hash页表倒置页表 39 分段 segmentation 40 段页式存储管理 e g Pentium 41 四 虚拟存储 进程的虚地址空间 virtualaddressspace 由进程的逻辑地址组成的地址空间 虚地址空间可以远大于系统的物理内存 虚拟存储器 virtualmemory 逻辑地址访问的存储器 42 43 五 页装入策略 pagefetchpolicy 决定何时将进程的逻辑页面装入内存Demandpaging 按需调页 发生缺页时 才将页面装入 Prepaging 预取 预先将某些页面装入内存 44 六 页替换策略 pagereplacementpolicy OS分配给进程的物理内存不够用时 需要页替换Optimal 最优化方法 选择将来最久不会被访问的页换出需要预先知道页访问序列不可能实现 只是作为一个评判标准FIFO 最先装入的被换出LRU 最久未使用的页被换出 基于locality现象 很有效 Clockpolicy 时钟算法 LRU算法不易实现 用时钟算法近似模拟每页设置一个referencebit 为1表示在时钟指针循环一周内被访问过 查找替换页 指针扫描 若referencebit 1 置为0 否则该页就是替换对象 Belady sAnomaly belady异态 内存大 反而缺页率高 45 46 进程执行时缺页率过高 使得系统忙于页面换进换出 因此执行效率低 提高效率的可行方法 优化页调入与替换算法 增加物理内存 减少进程数 提供更快速的交换设备 工作集 workingset 进程近期访问的页面的集合 为防止抖动 应该使得进程获得足够的内存以使进程的工作集在内存中计算工作集的算法 七 抖动 thrashing 47 八 交换区管理 实现虚拟存储的重要手段扩大内存 使系统可以运行比物理内存大的程序 交换空间 swapspace 交换文件 文件系统下的一个文件 如windows下的页面文件 交换设备 如linux的swap分区 后者比前者的读写效率高交换设备的管理数据结构交换设备上的空间信息 页表项上标识页面在交换区中的信息 Linux中的Swapcache 提高交换设备的存取效率 48 第四部分文件系统与I O管理 1 文件系统文件控制块 FCB 目录空闲磁盘空间管理文件系统性能 49 文件控制块 FCB permissions dates ownershipsize Datablocksindexes 50 UNIX Linux文件控制块i node indexnode 索引节点 51 目录 存储目录下文件名字及属性 如FCB信息 Twowaysofhandlinglongfilenamesindirectory a In line b Inaheap 52 TheWindows98FileSystemDirectory AnexampleofhowalongnameisstoredinWindows98 53 通过目录搜索文件 Thestepsinlookingup usr ast mbox 54 文件系统空闲磁盘空间管理 a Storingthefreelistonalinkedlist b Abitmap 55 典型文件系统磁盘结构 56 文件系统性能 Blockcache 57 文件系统性能 inode布局 I nodesplacedatthestartofthediskDiskdividedintocylindergroupseachwithits