考研复试1-南os复习1.13操作系统作用与功能

第1章：操作系统概 1o优缺点：成批处理作业，多道程序运行，资o进行人机交互，多台终端共 o特征：同时性，独立性，及时性，交互2第2章2.1.1处理 指令/ 指令 用户程序只能使用 指令，也称中断调用34、处理机CPU状态usermode用户态:只能执行非 kernelmode 态、系统态、管态何时CPU从用户态 态执行系统调用发生中断或异常如何 态到用户态系统调用或中断处理完毕后，IRET4中断的概操作系统是中断驱动的。(interrupt5开中恢复被中断程序的关开中恢复被中断程序的关中返回断点，继续执CPU向设备发确认中断信设备发中断开中执行中断开中

设置新运行保存中断现关中6多重中断的处

用户

中断

中断

用户

低级

高级7进程的定义和属一个进程映像包括正文段(程序段数据

进程控制块ProcessControl进程与程序的联系与区别进程是程序的一次执行过程程序是静态的，进程是动态的一个程序可对应一个进程，也可对应多个进（只要进程所对应的数据集不同一个进程运行时可以创建其它进程8进程的状态和:就绪ready:进程已得到除CPU以外的其它所需资源运行running:进程的指令正被执行:终止exit:进程已正常或异常结束。善后，回收资源。 时间片到,更高级进就 运被调9引入线程的动降低上下文切换时的时间和空间开销对拥有资源的基本单位(进程)，不频繁地进行切传统：单线程进程；现在：多线程进程线程的实内核级线程Kernel-LevelThreads的创建，撤用户级线程User-LevelThreads的创建，撤消完成。OS内核根本不知道用户级线程的存在。2.7.2选择调度算法的原调度准则CPU和设备利用率高：工作时间/总运行吞吐率高：单位时间内完成的作业个周转时间短：从作业提交到完响应时间快：从请求提交到首次响作业周转时间Ti=作业完成时刻–作业提交时带权周转时间Wi=作业周转时间/作业执行=(执行时间+等待时间)/执行时平均周转时间 平均带权周转时间1、先来先服务调度算法5、优先权调调度优先权最高的进程6、轮转法调RoundRobin用处理机，运行某一时间片(通常10-200ms)，2、最短作业优先算法提交执行开始结束周转带权周转1372平均周转时间T=95平均带权周转时间第3章通信与死3.1.3进程的交互 互斥和临界临界资源：一次仅允许一个进程使用的资源临界区：一个进 临界资源的那段程序代码互斥时的原则3.3.2信号量与PVtypedeftypedef{int/*，实质是可用资源个structprocess P(semaphore{if(S.value<0){addthisPtoS.L;block(thisP);}}申请分配资V(semaphore{if{removeaPfromS.L;}}释放信号量含义一个信号量可用于n个进程的同步互斥；且只能P、V操作修改（相当于临界区的通行证，实际上也是资源个数S=1时：临界区可S=0时：已有一进程进入临界S<0时：临界区已被占用，|S|个进程正等待用于同步时，S初值为 表示可用资源 表示该资源的等待队列长P(S)、V(S)操作必须成对出现用于互斥时，位于同一进程内用于同步时，交错出现于两个合作进程内多个P操作的次序不能颠倒，否则导致多个V()操作的次序可任意用P、V操作实现进程间互对每一临界资源设一信号量mutex，初值=1（此时mutex相当于此临界资源的使 证ProcessProcess{临界其它语}whileProcess{临界其它语}while用P、V操作实现进程间同对每“一类资源”设一S，初值S>=0（S为可用资源个数ProcessProcessP1: codesectionA}ProcessP2: codesection}3.3.5信号量解决生产者－消费者 设一信号量mutex，初值为1设一信号empty，初值n设一信号full，初值0dodo produceaniteminaddnextpto…}whiledo…removeanitembuffertoconsumetheitemin}while3.6.2死锁防互斥条件：涉及的是临界资源 破坏四个必要条件避免死锁

检测死锁检查系统是否死锁及哪些进程和资源涉及死解除死锁撤消死锁进程 资源以摆脱死锁

允许系死。3.6.3死锁避系统的安全状态安全状态：存在一个由所有进程构成的安全（<P1，P2，…，Pn>）。如果系统按照这个顺不安全状态：系统中不存在任何一个安全序列3.6.3死锁避例：系统中共有12台磁带机，在T0时刻 进已分最大尚可297355242此时存在一安全序列如果P1申请

P2P1>并得到一个资源并得到一个资源，系统进已分最大尚可396255 分配后仍处于“安全状态”才分配，否 3.6.4死锁检测与解 资源分配图R:请求边Pi分配边Rj有死锁环

有环无死锁

解除死锁：撤消进程 资源第4章 管地址重定位（地址映射将逻辑地址转换为物理地 的地址，一维或二维–内存单元的地址，从0顺序编静态地址重定目标程序装入内存(加载)时进行地址映射动态地址重定位 4.2.2可变分 管(最先适应法（First链表结构：空闲区按起址递增顺序排最佳适应法（Best链表结构：空闲区按分区大小递增顺序排特点：链首部碎片多，查找费时适应法（Worst链表结构：空闲区按分区大小递减顺序排特点：小碎片较少，但最大的空闲区不会很大分 管理的基本原内存划分为若干个大小相等的物理块(帧frame)进程的逻辑地址空间也划分为同样大小的逻辑(页page)帧或页大小L：512B~16MB，通常为4KB逻辑地A可表示为pp页内偏dlogicaladdressA，p=INT(A/L),d=Amod为进程离散地分配内存页面页式地址变换例：每页长1K。页表如下逻辑地址1500，3500所对应的物理地址是多帧549页 int(1500/1024)=1，所以对应页帧549 1500mod1024=476，对应的页内偏移为4761 第1页对应物理第41500对应的物理地址＝帧号×帧长＋页内偏int(3500/1024)=3，在第3页，越界分 管理的基本原010123456789页帧05页帧05122436475697快 一 页表，一 数据 若 的页号位于TLB，则从TLB中取出帧号否则从内存中的页表取出帧号，且添加进TLB快表满时淘汰旧表项，写入新表项例 内存的时间为100ns， 的时间为20ns，如果快表 间(EffectiveAccessTime)为：(20+100)×90%+(20+100+100)×10%130ns不用快表时， 两次内存，需100*2=200ns4.4.2分 管理的基本原逻辑地址：<段号，段内偏移量ssd例：load1,[X]|<Y>=load1,[1]|<200>call[X]|<Y>=call[2]|<160>段式管理的内存分配与释 段表：每个进程一个段表。段表结构如下段段的内存起始地段分段地址转换的例子

内存地地址错地址错 4.5.1虚 器的概虚拟内存的实现方请求段页在一条指令执行期间，当要 的页从磁盘调入内存6、7、页面替换①、最佳置换算法（理想置换算法 的页面最佳，但不可实现。用于衡量其它页面置换算法的性例：某 占用3个内存块，页 顺序如下串缺页

4444444222333333333112111555555 7缺页率=缺页次数 次数=7/12=串432缺页XXXXX串432缺页XXXXXXXXX淘汰驻留内存时间最久的一页例9FIFO算法中的Belady异常现通常，帧越多缺页次数越少但在FIFO算法中：有时，帧越多缺页次数越多③、最近最少使用置换算LeastRecentlyUsed淘汰在最近一段时间内最久未使用的一页串70120304230321201701帧帧7772222444000111111100000000333333000001122777缺 缺

12次缺第5章：设备管5.1.2I/O控制方四种I/O方式(1轮询方式——CPU忙等I/O(3DMA方式——常用于磁盘(4)通道方式——常用于大中型机、工作站2、中断驱动的中断CPU接到设备发来的中断信号，执行中断处理程序送给原进程，原进）、直接内存存取DMADMA工作原理和过程CPU向DMA控制器发出I/O数据块的指令发出数据传送请求的进程阻塞 I/O完一个数据块后DMA控制器向CPU中断发出数据传送请求的进程被唤醒、通道控制方式通道：带有 成I/O操作。通道由CPU的I/O指令和通道程序控制通道程序中包含多条通道命令，每条通道命令完成控制通道在完成多个数据块的I/O之后向CPU发出一次控制I/O通I/O通道控控制I/O通道I/O通道控制控控制§5.4缓冲技 引入缓冲 减少对CPU中断频率，放宽响应时间限实现缓冲 硬件缓冲、用软件管理的内存缓冲5.5.1磁盘物理结柱面单磁

磁道 扇区磁o驱动器号、柱面号、磁头号、扇区 磁盘请求的处理过磁 时间包括如下三部分1）寻道时间Ts=启动磁盘时间+移动1条磁道时间（启动磁盘时间约为3ms，m<0.1ms，Ts约2）旋转延迟时间Tr=将指定扇区移到磁头（若7200转/分钟，则每转约8.3ms，Tr平均约 读写字节数 （若每磁32768B[64扇]，则5.5.4搜查定位（磁盘调度算法 例图：磁头共移动236个柱面5.5.4搜查定位（磁盘调度算法 ，立即改变磁头移动方向例图：磁头共移动208个柱面5.5.4搜查定位（磁盘调度算法C-SCAN循环扫描算法：磁头从0号磁道开始向比SCAN的等待时间更加平均5.7.2SPOOLing的设计与实独占设备的静态分配方式不利于提高系统效率围处理机，利用磁盘进行“SPOOLing操作”第6章：文件管文件控制块、文 文文件控制块FCB：文件属性的集 文 ：一个文 可以包含多个文件文 该CB的集合。 个 ：当 .和 文件建立日期时首块盘块2416.3.2文件的逻辑结

从用户角度看文 UNIX流式文

属性(字段

36:记录名学号学号::::::

男男6.3.3文件的物理结物理结构：文件在外器上如何存放常用的文件物理结构顺序结构（连续结构结索引结构：直接索引、多重索1、顺序结构文件：连续随 ；寻道少 2 结构文件 分每个盘块（簇）上的 ；指针易损

7

文文起994、索引结构文件：索引把所有物理块地址集中到索引索引随 ，寻道多，需额 索引块4KB×（4KB/4B）=6.4.3文件空间(磁盘空闲空间)如果给文件分配连续磁盘块，则 磁盘空闲空间可由位示图、空闲区表、空闲块6.4.3文件空间(磁盘空闲空间)1bit1块的状态。0:空闲1:已占位0123456789字号10111010100000101010000000010000020001