1 概述定义负责管理协调硬件、软件等计算机资源的工作为上层用户、应用程序提供简单易用的服务是一种系统软件功能和目标资源的管理者处理机管理存储器管理文件管理设备管理向上层提供服务对于普通用户GUI图形界面命令接口联机命令接口(说一句做一句)脱机命令接口(批处理)对于软件和程序员程序接口(系统调用)对硬件机器的扩展扩充机器(虚拟机)特征并发并发指两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的，但微观上是交替发生的。并行指两个或多个事件在同一时刻同时发生。操作系统的并发性指计算机系统中"同时"运行着多个程序，这些程序宏观上看是同时运行着的，而微观上看是交替运行的。操作系统就是伴随着"多道程序技术"而出现的。因此，操作系统和程序并发是一起诞生的。共享共享即资源共享，是指系统中的资源可供内存中多个并发执行的进程共同使用。并发和共享互为存在条件资源共享方式互斥共享方式系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源。同时共享方式系统中的某些资源，允许一个时间段内由多个进程"同时"对它们进行访问。虚拟虚拟是指把一个物理上的实体变为若干个逻辑上的对应物。物理实体(前者)是实际存在的，而逻辑上对应物(后者)是用户感受到的。时分复用技术如虚拟存储器技术空分复用技术如虚拟处理器、虚拟设备技术异步异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。由于并发运行的程序会争抢着使用系统资源，而系统中的资源有限，因此进程的执行不是一贯到底的，而是走走停停的，以不可预知的速度向前推进。如果失去了并发性，即系统只能串行地运行各个程序，那么每个程序的执行会一贯到底。只有系统拥有并发性，才有可能导致异步性。发展与分类手工操作阶段缺点：人机速度矛盾批处理阶段单道批处理系统优点：缓解人机速度矛盾缺点：资源利用率低多道批处理系统优点：多道程序并发执行，资源利用率高缺点：不提供人机交互功能分时操作系统优点：提供人机交互功能缺点：不能优先处理紧急任务实时操作系统硬实时操作系统必须在绝对严格的规定时间内完成处理软实时操作系统能接受偶尔违反时间规定网络操作系统分布式操作系统个人计算机操作系统运行机制程序运行原理高级语言代码 -> 机器指令程序运行的过程就是CPU执行指令的过程两类程序内核程序应用程序两类指令特权指令非特权指令两种处理器状态内核态/核心态/管态用户态/目态CPU 中有一个寄存器叫 程序状态字寄存器(PSW)，其中有个二进制位，1表示"内核态"，0表示"用户态"内核内核(Kernel)是操作系统最核心最重要的部分由很多内核程序组成操作系统的内核如何变态内核态 -> 用户态一条修改PSW的特权指令用户态 -> 内核态由中断引起，硬件自动完成中断和异常中断的作用让操作系统内核强行夺回CPU的控制权使CPU从用户态变为内核态中断的分类内中断(异常)与当前执行的指令有关中断信号来自CPU内部陷阱、陷入(trap)由陷入指令引发，是应用程序故意引发的故障(fault)由错误条件引起的，可能被内核程序修复。内核程序修复故障后会把 CPU使用权还给应用程序，让它继续执行下去。如：缺页故障。终止(abort)由致命错误引起，内核程序无法修复该错误，因此一般不再将CPU使用权还给引发终止的应用程序，而是直接终止该应用程序。如：整数除0、非法使用特权指令外中断与当前执行的指令无关中断信号来自CPU外部时钟中断I/O中断中断机制的基本实现原理检查中断信号内中断：CPU在执行指令时会检查是否有异常发生外中断：每个指令周期末尾，CPU都会检查是否有外中断信号需要处理找到相应的中断处理程序通过"中断向量表"实现系统调用定义操作系统对应用程序/程序员提供的接口系统调用和库函数的区别有的库函数是对系统调用的进一步封装有的库函数没有使用系统调用按功能分类设备管理完成设备的请求/释放/启动等功能文件管理完成文件的读/写/创建/删除等功能进程控制完成进程的创建/撤销/阻塞/唤醒等功能进程通信完成进程之间的消息传递/信号传递等功能内存管理完成内存的分配/回收等功能系统调用的过程传参陷入指令/Trap/访管由操作系统内核程序处理系统调用请求返回应用程序其他传递系统调用参数 -> 执行陷入指令(用户态) -> 执行相应的内请求核程序处理系统调用(核心态) -> 返回陷入指令是在用户态执行的，执行陷入指令之后立即引发一个内中断，使CPU进入核心态发出系统调用请求是在用户态，而对系统调用的相应处理在核心态下进行操作系统的体系结构大内核将操作系统的主要功能模块都作为系统内核，运行在核心态优点：高性能缺点：内核代码庞大，结构混乱，难以维护微内核只把最基本的功能保留在内核优点：内核功能少，结构清晰，方便维护缺点：需要频繁地在核心态和用户态之间切换，性能低操作系统内核时钟管理实现计时功能中断处理负责实现中断机制原语是一种特殊的程序处于操作系统最底层，是最接近硬件的部分这种程序的运行具有原子性，其运行只能一气呵成，不可中断运行时间较短、调用频繁对系统资源进行管理的功能进程管理存储器管理设备管理程序运行时内存映像与地址空间虚拟机使用虚拟化技术，将一台物理机器虚拟化为多台虚拟机器（VirtualMachine,VM），每个虚拟机器都可以独立运行一个操作系统。2 进程管理基础概念进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位进程控制块(PCB)进程描述信息进程标识符PID用户标识符UID进程控制和管理信息CPU、磁盘、网络流量使用情况统计...进程当前状态：就绪态/阻塞态/运行态...资源分配清单正在使用哪些文件正在使用哪些内存区域正在使用哪些I/O设备处理机相关信息如PSW、PC等等各种寄存器的值(用于实现进程切换)进程的组成PCB进程描述信息进程控制和管理信息资源分配清单处理机相关信息程序段程序的代码(指令序列)数据段运行过程中产生的各种数据(如程序中定义的变量)进程的特征动态性进程是程序的一次执行过程，是动态地产生、变化消亡的并发性内存中有多个进程实体，各进程可并发执行独立性进程是能独立运行、独立获得资源、独立接受调度的基本单位异步性各进程按各自独立的、不可预知的速度向前推进，操作系统要提供"进程同步机制"来解决异步问题结构性每个进程都会配置一个PCB。结构上看，进程由程序段、数据段、PCB组成进程的状态与转换状态运行态(Running)CPU√ 其他所需资源√占有CPU，并在CPU运行单CPU情况下，同一时刻只会有一个进程处于运行态，多核CPU情况下，可能有多个进程处于运行态就绪态(Ready)CPU× 其他所需资源√已经具备运行条件，但由于没有空闲CPU而暂时不能运行阻塞态(Waiting/Blocked，又称：等待态)CPU× 其他所需资源×因等待某一事件而暂时不能运行创建态(New，又称：新建态)进程正在被创建，操作系统为进程分配资源、初始化PCB终止态(Terminated，又称：结束态)进程正在从系统中撤销，操作系统会回收进程拥有的资源、撤销PCB进程的组织方式链接方式按照进程状态将PCB分为多个队列操作系统持有指向各个队列的指针索引方式根据进程状态的不同，建立几张索引表操作系统持有指向各个索引表的指针进程控制概念进程控制就是要实现进程状态的转换进程控制用原语实现原语用关/开中断实现原语是一种特殊的程序原语的执行具有原子性，执行过程必须一气呵成，不可中断相关原语进程的创建操作系统创建一个进程时使用的原语创建原语申请空白PCB为新进程分配所需资源初始化PCB将PCB插入就绪队列(创建态 -> 就绪态)引起进程创建的事件用户登录分时系统中，用户登录成功，系统会为其建立一个新的进程作业调度多道批处理系统中，有新的作业放入内存时，会为其建立一个新的进程提供服务用户向操作系统提出某些请求时，会新建一个进程处理该请求应用请求由用户进程主动请求创建一个子进程进程的终止就绪态/阻塞态/运行态 -> 终止态 -> 无撤销原语从PCB集合中找到终止进程的PCB若进程正在运行，立即剥夺CPU，将CPU分配给其他进程终止其所有子进程(进程间的关系是树形结构)将该进程拥有的所有资源归还给父进程或操作系统删除PCB引起进程终止的事件正常结束进程自己请求终止(exit系统调用)异常结束整数除以0、非法使用特权指令，然后被操作系统强行杀掉外界干预任务管理器用户选择杀掉进程进程的阻塞和唤醒阻塞原语、唤醒原语必须成对使用进程的阻塞运行态 -> 阻塞态阻塞原语找到要阻塞的进程对应的PCB保护进程运行现场，将PCB状态信息设置为阻塞态，暂时停止进程运行将PCB插入相应事件的等待队列引起进程阻塞的事件需要等待系统分配某种资源需要等待相互合作的其他进程完成工作进程的唤醒阻塞态 -> 就绪态唤醒原语在事件等待队列中找到PCB将PCB从等待队列移除，设置进程为就绪态将PCB插入就绪队列，等待被调度引起进程唤醒的事件等待的事件发生因何事阻塞，就应由何事唤醒进程的切换运行态 -> 阻塞态/就绪态就绪态 -> 运行态切换原语将运行环境信息存入PCBPCB移入相应队列选择另一个进程执行，并更新其PCB根据PCB恢复新进程所需的运行环境引起进程切换的事件当前进程时间片到有更高优先级的进程到达当前进程主动阻塞当前进程终止进程控制原语总结更新PCB中的信息所有的进程控制原语一定都会修改进程状态标志剥夺当前运行进程的CPU使用权必然需要保存其运行环境某进程开始运行前必然要恢复期运行环境将PCB插入合适的队列分配/回收资源进程通信进程是分配系统资源的单位(包括内存地址空间)，因此各进程拥有的内存地址空间相互独立。为了保证安全，一个进程不能直接访问另一个进程的地址空间。但是进程之间的信息交换又是必须实现的。为了保证进程间的安全通信，操作系统提供了一些方法。共享存储设置一个共享空间要互斥的访问共享空间两种方式基于数据结构的共享(低级)基于存储区的共享(高级)管道通信管道是指用于连接读写进程的一个共享文件，又名pipe文件。其实就是在内存中开辟一个大小固定的缓冲区管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。各进程要互斥地访问管道。数据以字符流的形式写入管道，当管道写满时，写进程的write()系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取走后，管道变空，此时读进程的read()系统调用将被阻塞。如果没写满，就不允许读。如果没读空，就不允许写。数据一旦被读出，就从管道中被抛弃，这就意味着读进程最多只能有一个，否则可能会有读错数据的情况。消息传递进程间的数据交换以格式化的消息(Message)为单位。进程通过操作系统提供的"发送消息/接收消息"两个原语进行数据交换。消息头包括：发送进程ID、接受进程ID、消息类型、消息长度等格式化的信息两种方式直接通信方式消息直接挂到接收方的消息队列里间接(信箱)通信方式消息先发到中间体(信箱)线程/多线程模型线程的实现变化资源分配、调度传统进程机制中，进程是资源分配、调度的基本单位引入线程后，进程是资源分配的基本单位，线程是调度的基本单位并发性传统进程机制中，只能进程间并发引入线程后，各线程间也能并发，提升了并发度系统开销传统的进程间并发，需要切换进程的运行环境，系统开销很大线程间并发，如果是同一进程内的线程切换，则不需要切换进程环境，系统开销小引入线程后，并发所带来的系统开销减小线程的属性线程是处理机调度的单位多CPU计算机中，各个线程可占用不同的CPU每个线程都有一个线程ID、线程控制块(TCB)线程也有就绪、阻塞、运行三种基本状态线程几乎不拥有系统资源同一进程的不同线程间共享进程的资源由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预同一进程中的线程切换，不会引起进程切换不同进程中的线程切换，会引起进程切换切换同进程内的线程，系统开销很小切换进程，系统开销较大线程的实现方式用户级线程从用户视角能看到的线程，由线程库实现内核级线程从操作系统视角看到的线程由操作系统实现内核级线程才是处理机分配的单位组合方式上述两种方式的结合多线程模型一对一模型一个用户级线程映射到一个内核级线程优点：各个线程可分配到多核处理机并行执行，并发度高缺点：线程管理都需要操作系统支持，开销大多对一模型多个用户级线程映射到一个内核级线程优点：线程管理开销小效率高缺点：一个线程阻塞会导致整个进程都被阻塞(并发度低)多对多模型n个用户级线程映射到m个内核级线程(n≥m)集二者之所长线程的状态与转换线程的组织与控制处理机调度概念按某种算法选择一个进程将CPU分配给它三个层次高级调度(作业调度)按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程中级调度(内存调度)按照某种规则，从挂起队列中选择合适的进程将其数据调回内存低级调度(进程调度)按照某种规则，从就绪队列中选择一个进程为其分配处理机三层调度的联系、对比高级调度外存 -> 内存(面向作业)发生频率：最低中级调度外存 -> 内存(面向进程)发生频率：中等低级调度内存 -> CPU发生频率：最高补充暂时调到外存等待的进程状态为挂起状态(挂起态，suspend)挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态七状态模型：在五状态模型的基础上加入了"就绪挂起"和"阻塞挂起"两种状态进程调度时机什么时候可以进行进程调度主动放弃进程正常终止运行过程中发生异常而终止主动阻塞(如等待I/O)被动放弃分给进程的时间片用完有更紧急的事情需要处理(如I/O中断)有更高优先级的进程进入就绪队列什么时候不能进行进程调度在处理中断的过程中进程在操作系统内核程序临界区中原子操作过程中(原语)切换过程狭义的进程调度指的是从就绪队列中选中一个要运行的进程。(这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换)进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。广义的进程调度包含了选择一个进程和进程切换两个步骤。切换过程对原来运行进程各种数据的保存对新的进程各种数据的恢复进程调度、切换是有代价的，并不是调度越频繁，并发度就越高方式非剥夺调度方式(非抢占式)只能由当前运行的进程主动放弃CPU（阻塞或者退出时才会触发调度程序）剥夺调度方式(抢占式)可由操作系统剥夺当前进程的CPU使用权（每个时钟中断或k个时钟中断会触发调度程序）调度器/调度程序就绪与运行的状态转换通过调度程序决定。不支持内核级线程的操作系统，调度程序的处理对象是进程。支持内核级线程的操作系统，调度程序的处理对象是内核线程。闲逛进程没有其他就绪进程时，运行闲逛进程。闲逛进程的特性：优先级最低可以是0地址指令，占一个完整的指令周期（指令周期末尾例行检查中断）能耗低内核级线程与用户级线程调度用户级线程线程切换代价：低，不需要切换完整的上下文。并发/并行度：低，一个阻塞整个进程阻塞。内核级线程线程切换代价：高，需转为内核态，切换完整的上下文。并发/并行度：高，一个阻塞其他线程仍可运行。上下文及切换机制调度算法的评价指标CPU利用率或者计算某设备的利用率$利用率 = \frac{忙碌的时间}{总时间}$系统吞吐量单位时间内完成作业的数量$系统吞吐量 = \frac{总共完成了多少道作业}{总共花了多少时间}$周转时间周转时间 = 作业完成时间 - 作业提交时间$平均周转时间 = \frac{各作业周转时间之和}{作业数}$$带权周转时间 = \frac{作业周转时间}{作业实际周转时间}$$平均带权周转时间 = \frac{各作业带权周转时间之和}{作业数}$等待时间对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间。对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。进程/作业等待被服务的时间之和平均等待时间即各个进程/作业等待时间的平均值响应时间从用户提交请求到首次产生响应所用的时间调度算法先来先服务(FCFS)先来先服务调度算法：按照到达的先后顺序调度，事实上就是等待时间越久的越优先得到服务。短作业优先(SJF)短作业/进程优先调度算法：每次调度时选择当前已到达且运行时间最短的作业/进程。最短剩余时间优先算法：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度抢占式的短作业优先算法又称"最短剩余时间优先算法(SRTN)"最短剩余时间优先算法：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度注意细节高响应比优先(HRRN)高响应比优先算法：非抢占式的调度算法，只有当前运行的进程主动放弃CPU时(正常/异常完成，或主动阻塞)，才需要进行调度，调度时计算所有就绪进程的响应比，选响应比最高的进程上处理机。时间片轮转(RR)时间片轮转调度算法：轮流让就绪队列中的进程依次执行一个时间片(每次选择的都是排在就绪队列队头的进程)如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。另一方面，进程调度、切换是有时间代价的(保存、恢复运行环境)，因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。优先级调度非抢占式的优先级调度算法：每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。抢占式的优先级调度算法：每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。另外，当就绪队列发生改变时也需要检查是会发生抢占。就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种。静态优先级：创建进程时确定，之后一直不变。动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级。系统进程优先级 高于 用户进程前台进程优先级 高于 后台进程操作系统更偏好 I/O型进程(或称I/O繁忙型进程)注：与I/O型进程相对的是计算型进程(或称CPU繁忙型进程)I/O设备和CPU可以并行工作。如果优先让I/O繁忙型进程优先运行的话，则越有可能让I/O设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升多级反馈队列设置多级就绪队列，各级队列优先级从高到低，时间片从小到大新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片。若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经在最下级的队列，则重新放回最下级队列队尾只有第 k 级队列为空时，才会为 k+1 级队头的进程分配时间片被抢占处理机的进程重新放回原队列队尾多级队列调度算法进程同步/进程互斥进程同步同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。并发性带来了异步性，有时需要通过进程同步解决这种异步问题。进程互斥我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备(比如摄像头、打印机)都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源四个部分进入区检查是否可以进入临界区，若可进入，需要"上锁"临界区访问临界资源的代码退出区负责"解锁"剩余区其余代码部分需要遵循的原则空闲让进临界区空闲时，应允许一个进程访问忙则等待临界区正在被访问时，其他试图访问的进程需要等待有限等待要在有限时间内进入临界区，保证不会饥饿让权等待进不了临界区的进程，要释放处理机，防止忙等进程互斥的软件实现方法单标志法在进入区只做"检查"，不"上锁"在退出区把临界区的使用权转交给另一个进程(相当于在退出区既给另一进程"解锁"，又给自己"上锁")主要问题：不遵循"空闲让进"原则双标志先检查在进入区先"检查"后"上锁"，退出区"解锁"主要问题：不遵循"忙则等待"原则双标志后检查在进入区先"加锁"后"检查"，退出区"解锁"主要问题：不遵循"空闲让进、有限等待"原则，可能导致"饥饿"Peterson算法在进入区"主动争取，主动谦让，检查对方是否想进、己方是否谦让"主要问题：不遵循"让权等待"原则，会发生"忙等"进程互斥的硬件实现方法中断屏蔽方法使用"开/关中断"指令实现优点：简单高效缺点：只适用于单处理机，只适用于操作系统内核进程TestAndSet(TS指令/TSL指令)简称TS指令，也有地方称为TestAndSetLock指令，或TSL指令old记录是否已被上锁再将lock设为true检查临界区是否已被上锁(若已上锁，则循环重复前几步)优点：实现简单，适用于多处理机环境缺点：不满足"让权等待"Swap指令(XCHG指令)逻辑同TSL锁进程同步：条件变量信号量机制整型信号量用一个整数型变量作为信号量，数值表示某种资源数整型信号量与普通整型变量的区别：对信号量只能执行初始化、P、V三种操作整型信号量存在的问题：不满足让权等待原则记录型信号量S.value表示某种资源数，S.L指向等待该资源的队列P操作中，一定是先S.value--，之后可能需要执行block原语V操作中，一定是先S.value++，之后可能需要执行wakeup原语注意：要能够自己推断在什么条件下需要执行block或wakeup可以用记录型信号量实现系统资源的"申请"和"释放"可以用记录型信号量实现进程互斥、进程同步用信号量机制实现进程互斥分析问题，确定临界区设置互斥信号量，初值为1临界区之前对信号量执行P操作临界区之后对信号量执行V操作进程同步分析问题，找出哪里需要实现"一前一后"的同步关系设置同步信号量，初始值为0在"前操作"之后执行V操作在"后操作"之前执行P操作进程的前驱关系分析问题，画出前驱图，把每一对前驱关系都看成一个同步问题为每一对前驱关系设置同步信号量，初值为0在每个"前操作"之后执行V操作在每个"后操作"之前执行P操作生产者消费者问题多生产者多消费者吸烟者问题读者写者问题哲学家进餐问题管程引入目的解决信号量机制编程繁琐的问题组成共享数据结构对数据结构初始化的语句一组用来访问数据结构的过程(函数)基本特征各外部进程/线程只能通过管程提供的特定"入口"才能访问共享数据每次仅允许一 个进程在管程内执行某个内部过程补充各进程必须互斥访问管程的特性是由编译器实现的可在管程中设置条件变量及等待/唤醒操作以解决同步问题死锁定义各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进死锁/饥饿/死循环的区别死锁：至少是两个进程一起死锁，死锁进程处于阻塞态饥饿：可以只有一个进程饥饿，饥饿进程可能阻塞也可能就绪死循环：可能只有一个进程发生死循环，死循环的进程可上处理机死锁和饥饿是操作系统要解决的问题，死循环是应用程序员要解决的死锁产生的必要条件互斥条件对必须互斥使用的资源的争抢才会导致死锁不剥夺条件进程保持的资源只能主动释放，不可强行剥夺请求和保持条件保持着某些资源不放的同时，请求别的资源循环等待条件存在一种进程资源的循环等待链循环等待未必死锁，死锁一定有循环等待什么时候发生死锁对不可剥夺资源的不合理分配，可能导致死锁死锁的处理策略预防死锁破坏死锁产生的四个必要条件避免死锁避免系统进入不安全状态(银行家算法)死锁的检测和解除允许死锁发生，系统负责检测出死锁并解除预防死锁破坏互斥条件将临界资源改造为可共享使用的资源(如SPOOLing技术)缺点：可行性不高，很多时候无法破坏互斥条件破坏不剥夺条件方案一：申请的资源得不到满足时，立即释放拥有的所有资源方案二：申请的资源被其他进程占用时，由操作系统协助剥夺(考虑优先级)缺点：实现复杂；剥夺资源可能导致部分工作失效；反复申请和释放导致系统开销大；可能导致饥饿破坏请求和保持条件运行前分配好所有需要的资源，之后一直保持缺点：资源利用率低;可能导致饥饿破坏循环等待条件给资源编号，必须按编号从小到大的顺序申请资源缺点：不方便增加新设备；会导致资源浪费；用户编程麻烦避免死锁安全序列所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。不安全序列无法找到任何一个安全序列，说明此时系统处于不安全状态，有可能发生死锁如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然，如果有进程前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况。如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁(处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态)因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是"银行家算法"的核心思想。银行家算法检查此次申请是否超过了之前声明的最大需求数检查此时系统剩余的可用资源是否还能满足这次请求试探着分配，更改各数据结构用安全性算法检查此次分配是否会导致系统进入不安全状态死锁的避免和解除检测数据结构：资源分配图两种结点进程结点资源结点两种边进程结点 -> 资源结点(请求边)资源结点 -> 进程结点(分配边)死锁检测算法依次消除与不阻塞进程相连的边，直到无边可消注：所谓不阻塞进程是指其申请的资源数还足够的进程死锁定理：若资源分配图是不可完全简化的，说明发生了死锁解除资源剥夺法撤销进程法(终止进程法)进程回退法3 内存管理内存的基础知识定义存储单元、内存地址按字节编制、按字编址进程运行的基本原理指令的工作原理操作码 + 若干参数(可能包含地址参数)逻辑地址(相对地址)和物理地址(绝对地址)写程序到程序运行编辑源代码文件编译由源代码文件生成目标模块(高级语言"翻译"为机器语言)链接由目标模块生成装入模块，链接后形成完整的逻辑地址装入将装入模块装入内存，装入后形成物理地址链接方式静态链接装入前链接成一个完整装入模块装入时动态链接运行前边装入边链接运行时动态链接运行时需要目标模块才装入并链接装入方式绝对装入编译时产生绝对地址可重定位装入装入时将逻辑地址转换为物理地址动态运行时装入运行时将逻辑地址转换为物理地址，需设置重定位寄存器内存管理内存空间的分配与回收连续分配管理方式单一连续分配固定分区分配动态分区分配非连续分配管理方式基本分页存储管理基本分段存储管理段页式存储管理内存空间的扩充(实现虚拟性)覆盖技术交换技术虚拟存储技术地址转换操作系统负责实现逻辑地址到物理地址的转换三种方式绝对装入：编译器负责地址转换(单道程序阶段，无操作系统)可重定位装入：装入程序负责地址转换(早期多道批处理阶段)动态运行时装入：运行时才进行地址转换(现代操作系统)存储保护保证各进程在自己的内存空间内运行，不会越界访问两种方式设置上下限寄存器利用重定位寄存器、界地址寄存器进行判断内存共享内存共享通常是通过“内存映射”实现的，将多个进程的虚拟地址空间映射到同一片物理内存。可以是“页”映射，也可以是“段”映射。内存映射文件覆盖与交换覆盖技术一个固定区存放最活跃的程序段固定区中的程序段在运行过程中不会调入调出若干覆盖区不可能同时被访问程序段可共享一个覆盖区覆盖区中的程序段在运行过程中会根据需要调入调出必须由程序员声明覆盖结构，操作系统完成自动覆盖缺点：对用户不透明，增加了用户编程负担交换技术内存紧张时，换出某些进程以腾出内存空间，再换入某些进程磁盘分为文件区和对换区，换出的进程放在对换区覆盖与交换的区别覆盖是在同一个程序或进程中的交换是在不同进程(或作业)之间的连续分配管理内部碎片：分配给某进程的内存区域中，如果有些部分没有用上。外部碎片：是指内存中的某些空闲分区由于太小而难以利用。空闲分区表、空闲分区链单一连续分配只支持单道程序，内存分为系统区和用户区，用户程序放在用户区无外部碎片，有内部碎片固定分区分配支持多道程序，内存用户空间分为若干个固定大小的分区，每个分区只能装一道作业无外部碎片，有内部碎片两种分区方式分区大小相等分区大小不等动态分区分配支持多道程序，在进程装入内存时，根据进程的大小动态地建立分区无内部碎片，有外部碎片外部碎片可用"紧凑"技术来解决回收内存分区时，可能遇到四种情况回收区之后有相邻的空闲分区回收区之前有相邻的空闲分区回收区前、后都有相邻的空闲分区回收区前、后都没有相邻的空闲分区动态分区分配算法首次适应算法(First Fit)最佳适应算法(Best Fit)最坏适应算法(Worst Fit)邻近适应算法(Next Fit)基本分页存储管理基本分页存储管理的思想：把进程分页，各个页面可离散地放到各个的内存块中易混概念"页框、页帧、内存块、物理块、物理页" 与 "页、页面""页框号、页帧号、内存块号、物理块号、物理页号" 与 "页号、页面号"页表页表记录了页面和实际存放的内存块之间的映射关系一个进程对应一张页表，进程的每一页对应一个页表项，每个页表项由"页号"和"块号"组成每个页表项的大小是相同的，页号是"隐含"的i号页表项存放地址 = 页表始址 + i * 页表项大小逻辑地址结构页号P = 逻辑地址 / 页面大小页内偏移量W = 逻辑地址 % 页面大小如何实现地址转换计算出逻辑地址对应的页号与页内偏移量找到对应页面在内存中的存放位置(查页表)物理地址 = 页面始址 + 页内偏移量基本地址变换机构用于实现逻辑地址到物理地址转换的一组硬件机构页表寄存器的作用存放页表起始地址存放页表长度地址变换过程根据逻辑地址算出页号、页内偏移量页号的合法性检查(与页表长度对比)若页号合法，再根据页表起始地址、页号找到对应页表项根据页表项中记录的内存块号、页内偏移量得到最终的物理地址访问物理内存对应的内存单元其他页内偏移量位数与页面大小之间的关系(要能用其中一个条件推出另一个条件)页式管理中地址是一维的实际应用中，通常使一个页框恰好能放入整数个页表项为了方便找到页表项，页表一般是放在连续的内存块中的具有快表的地址变换机构定义快表，又称联想寄存器(TLB， translation lookaside buffer)，是一种访问速度比内存快很多的高速缓存(TLB不是内存)，用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表常称为慢表。地址变换TLB和普通Cache的区别：TLB中只有页表项的副本，而普通Cache中可能会有其他各种数据的副本。两级页表单级页表存在的问题所有页表项必须连续存放，页表过大时需要很大的连续空间在一段时间内并非所有页面都用得到，因此没必要让整个页表常驻内存两级页表将长长的页表再分页逻辑地址结构：(一级页号，二级页号，页内偏移量)注意几个术语：页目录表/外层页表/顶级页表如何实现地址变换按照地址结构将逻辑地址拆分成三部分从PCB中读出页目录表始址，根据一级页号查页目录表，找到下一级页表在内存中的存放位置根据级页号查表，找到最终想访问的内存块号结合页内偏移量得到物理地址其他多级页表中，各级页表的大小不能超过一个页面。若两级页表不够，可以分更多级多级页表的访存次数(假设没有快表机构)N级页表访问一个逻辑地址需要N + 1次访存基本分段存储管理分段将地址空间按照程序自身的逻辑关系划分为若干个段，每段从0开始编址每个段在内存中占据连续空间，但各段之间可以不相邻逻辑地址结构：(段号，段内地址)段表记录逻辑段到实际存储地址的映射关系每个段对应一个段表项。各段表项长度相同，由段号(隐含)、段长、基址组成地址变换由逻辑地址得到段号、段内地址段号与段表寄存器中的段长度比较，检查是否越界由段表始址、段号找到对应段表项根据段表中记录的段长，检查段内地址是否越界由段表中的"基址 + 段内地址"得到最终的物理地址访问目标单元分页与分段对比段页式管理方式分段 + 分页将地址空间按照程序自身的逻辑关系划分为若干个段，在将各段分为大小相等的页面将内存空间分为与页面大小相等的一个个内存块，系统以块为单位为进程分配内存逻辑地址结构：(段号，页号，页内偏移量)段表、页表每个段对应一个段表项。各段表项长度相同，由段号(隐含)、页表长度、页表存放地址组成每个页对应一个页表项。各页表项长度相同，由页号(隐含)、页面存放的内存块号组成地址变换由逻辑地址得到段号、页号、页内偏移量段号与段表寄存器中的段长度比较，检查是否越界由段表始址、段号找到对应段表项根据段表中记录的页表长度，检查页号是否越界由段表中的页表地址、页号得到查询页表，找到相应页表项由页面存放的内存块号、页内偏移量得到最终的物理地址访问一个逻辑地址所需的访存次数第一次：查段表、第二次：查页表、第三次：访问目标单元可引入快表机构，以段号和页号为关键字查询快表，即可直接找到最终的目标页面存放位置。引入快表后仅需一次访存虚拟内存传统存储管理方式的特征缺点一次性：作业数据必须一次全部调入内存驻留性：作业数据在整个运行期间都会常驻内存局部性原理时间局部性：现在访问的指令、数据在不久后很可能会被再次访问空间局部性：现在访问的内存单元周围的内存空间，很可能在不久后会被访问高速缓存技术：使用频繁的数据放到更高速的存储器中虚拟内存的定义和特征程序不需全部装入即可运行，运行时根据需要动态调入数据，若内存不够，还需换出一些数据特征多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。对换性：无需在作业运行时一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。如何实现虚拟内存技术访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存(请求调页功能)内存空间不够时，将内存中暂时用不到的信息换出到外存(页面置换功能)虚拟内存的实现请求分页存储管理请求分段存储管理请求段页式存储管理请求分页管理方式页表机制在基本分页的基础上增加了几个表项状态位：表示页面是否已在内存中访问字段：记录最近被访问过几次，或记录上次访问的时间，供置换算法选择换出页面时参考修改位：表示页面调入内存后是否被修改过，只有修改过的页面才需在置换时写回外存外存地址：页面在外存中存放的位置缺页中断机构找到页表项后检查页面是否已在内存，若没在内存，产生缺页中断缺页中断处理中，需要将目标页面调入内存，有必要时还要换出页面缺页中断属于内中断，属于内中断中的"故障"，即可能被系统修复的异常一条指令在执行过程中可能产生多次缺页中断地址变换机构找到页表项是需要检查页面是否在内存中若页面不再内存中，需要请求调页若内存空间不够，还需换出页面页面调入内存后，需要修改相应页表项页面置换算法最佳置换算法(OPT)先进先出置换算法(FIFO)最近最久未使用置换算法(LRU)时钟置换算法(CLOCK)改进型的时钟置换算法页面分配策略驻留集指请求分页存储管理中给进程分配的内存块的集合页面分配、置换策略固定分配与可变分配：区别在于进程运行期间驻留集大小是否可变局部置换与全局置换：区别在于发生缺页时是否只能从进程自己的页面中选择一个换出固定分配局部置换：进程运行前就分配一定数量物理块，缺页时只能换出进程自己的某一页可变分配全局置换：只要缺页就分配新物理块，可能来自空闲物理块，也可能需换出别的进程页面可变分配局部置换：频繁缺页的进程，多分配一些物理块；缺页率很低的进程，回收一些物理块。直到缺页率合适何时调入页面预调页策略：一般用于进程运行前请求调页策略：进程运行时，发现缺页再调页从何处调页对换区：采用连续存储方式，速度更快；文件区：采用离散存储方式，速度更慢对换区足够大：运行将数据从文件区复制到对换区，之后所有的页面调入、调出都是在内存与对换区之间进行对换区不够大：不会修改的数据每次都从文件区调入；会修改的数据调出到对换区，需要时再从对换区调入UNIX方式：第一次使用的页面都从文件区调入；调出的页面都写回对换区，再次使用时从对换区调入抖动(颠簸)现象页面频繁换入换出的现象。主要原因是分配给进程的物理块不够工作集在某段时间间隔里，进程实际访问页面的集合。驻留集大小一般不能小于工作集大小4 文件管理初识文件的定义：一组有意义的信息的集合文件的属性：文件名、标识符、类型、位置、大小、保护信息...文件内部应该如何被组织起来(文件的逻辑结构)文件之间应该如何被组织起来(目录结构)操作系统应向上提供哪些功能创建文件(create系统调用)删除文件(delete系统调用)读文件(read系统调用)写文件(write系统调用)打开文件(open系统调用)关闭文件(close系统调用)文件应如何存放在外存中(文件的物理结构)操作系统如何管理外存中的空闲块(存储空间的管理)操作系统需要提供的其他文件管理功能文件共享文件保护文件系统的全局结构物理格式化（低级格式化）：划分扇区，检测坏扇区，并用备用扇区替换坏扇区。逻辑格式化：磁盘分区（分卷Volume），完成个分区的文件系统初始化。每个分区可以是不同的文件系统，且每个分区都会有引导块，但未必都安装了操作系统。如果没安装操作系统，则该分区的引导块为空。超级块：找到空闲块。i结点区：索引结点。操作系统引导文件系统在外存中的结构每个分区就是一个独立的文件系统，可以采用不同的方案实现空闲分区管理、文件物理结构、目录实现方式。文件系统在内存中的结构近期访问过的目录文件会缓存在内存中，不用每次都从磁盘读入，这样可以加快目录检索速度。文件元数据文件元数据（metadata）：即文件属性，记录在文件FCB中。如： 文件创建者，创建时间，上一次修改时间，文件格式，隐藏标志，表示是否隐藏不显示？表示是否是系统文件？表示是否只读？文件大小等。虚拟文件系统虚拟文件系统的特点：向上层用户进程提供统一标准的系统调用接口，屏蔽底层具体文件系统的实现差异。VFS要求下层的文件系统必须实现某些规定的函数功能，如：open/read/write。一个新的文件系统想要在某操作系统上被使用，就必须满足该操作系统VFS的要求。每打开一个文件，VFS就在主存中新建一个vnode，用统一的数据结构表示文件，无论该文件存储在哪个文件系统。文件系统的挂载目录目录的操作新建一个目录，会默认有两个FCB：'.'和'..'文件的逻辑结构无结构文件由二进制流或字符流组成，无明显的逻辑结构有结构文件由记录组成，分为定长记录、可变长记录逻辑结构顺序文件索引文件索引顺序文件顺序文件链式存储无论是定长/可变长记录，都无法实现随机存取，每次只能从第一个记录开始依次往后查找顺序存储可变长记录无法实现随机存取。每次只能从第一个记录开始依次往后查找定长记录可实现随机存取。记录长度为L，则第i个记录存放的相对位置是i*L若采用串结构，无法快速找到某关键字对应的记录若采用顺序结构，可以快速找到某关键字对应的记录(如折半查找)有结构文件顺序文件串结构：记录顺序与关键字无关顺序结构：记录按关键字顺序排列可变长记录的顺序文件无法实现随机存取，定长记录可以定长记录、顺序结构的顺序文件可以快速检索(根据关键字快速找到记录)最大缺点：不方便增加/删除记录索引文件建立一张索引表，每个记录对应一个表项。各记录不用保持顺序，方便增加/删除记录索引表本身就是定长记录的顺序文件，一个索引表项就是一条定长记录，因此索引文件可支持随机存取若索引表按关键字顺序排列，则可支持快速检索解决了顺序文件不方便增/删记录的问题，同时让不定长记录的文件实现了随机存取。但索引表可能占用很多空间索引顺序文件将记录分组，每组对应一个索引表项检索记录时先顺序查索引表，找到分组，再顺序查找分组当记录过多时，可建立多级索引表文件目录文件目录的实现一个文件对应一个FCB，一个FCB就是一个目录项，多个FCB组成文件目录对目录的操作：搜索、创建文件、删除文件、显示文件、修改文件目录结构单级目录结构一个系统只有一张目录表，不允许文件重名两级目录结构不同用户的文件可以重名，但不能对文件进行分类多级(树形)目录结构不同目录下的文件可以重名，可以对文件进行分类，不方便文件共享系统根据"文件路径"找到目标文件从根目录出发的路径是"绝对路径"从"当前目录"出发的路径是"相对路径"无环图目录结构在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图为共享结点设置一个共享计数器，计数器为0时才真正删除该结点索引结点除了文件名之外的所有信息都放到索引结点中，每个文件对应一个索引结点目录项中只包含文件名、索引结点指针，因此每个目录项的长度大幅减小由于目录项长度减小，因此每个磁盘块可以存放更多个目录项，因此检索文件时磁盘I/O的次数就少了很多文件的物理结构(文件分配方式)顺序分配为文件分配的必须是连续的磁盘块链接分配链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。隐式链接除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。优点：很方便文件拓展，不会有碎片问题，外存利用率高。缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。显式链接把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表(FAT，FileAllocation Table)。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内存。优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。缺点：文件分配表的需要占用一定的存储空间。索引分配链接方案多层索引混合索引逻辑结构和物理结构逻辑结构用户(文件创建者)的视角看到的样子在用户看来，整个文件占用连续的逻辑地址空间文件内部的信息组织完全由用户自己决定，操作系统并不关心物理结构由操作系统决定文件采用什么物理结构存储操作系统负责将逻辑地址转变为(逻辑块号，块内偏移量)的形式，并负责实现逻辑块号到物理块号的映射文件存储空间管理存储空间的划分与初始化文件卷(逻辑卷)，目录区，文件区的概念目录区包含文件目录、空闲表、位示图、超级块等用于文件管理的数据空闲表法空闲表中记录每个连续空闲区的起始盘块号、盘块数分配时可采用首次适应、最佳适应等策略；回收时注意表项的合并问题空闲链表法空闲盘块链以盘块为单位组成一条空闲链分配时从链头依次取出空闲块，回收时将空闲块插到链尾空闲盘区链以盘区为单位组成一条空闲链分配时可采用首次适应、最佳适应等策略；回收时注意相邻空闲盘区合并的问题位示图法一个二进制位对应一个盘块。(字号，位号)或(行号，列号)与盘块号一一对应重要考点：要能够自己推出盘块号 -> (字号，位号)之间的相互转换公式需要注意的题目条件二进制位0/1到底哪个代表空闲，哪个代表不空闲字号、位号、盘块号到底是从0开始还是从1开始成组链接法UNIX采用的策略，适合大型文件系统。理解即可，不方便用文字描述的知识点也很难作为考题文件的基本操作创建文件分配外存空间，创建目录项删除文件回收外存空间，删除目录项打开文件将目录项中的信息复制到内存中的打开文件表中，并将打开文件表的索引号返回给用户(打开文件时并不会把文件数据直接读入内存。"索引号"也称"文件描述符")打开文件之后，对文件的操作不再需要每次都查询目录，可以根据内存中的打开文件表进行操作每个进程有自己的打开文件表，系统中也有一张总的打开文件表进程打开文件表中特有的属性：读写指针、访问权限(只读、读写)系统打开文件表中特有的属性：打开计数器(有多少个进程打开了该文件)关闭文件将进程打开文件表中的相应表项删除系统打开文件表的打开计数器减1，若打开计数器为0，则删除系统表的表项读文件根据读指针、读入数据量、内存位置，将文件数据从外存读入内存写文件根据写指针、写出数据量、内存位置，将文件数据从内存写出外存文件共享硬链接各个用户的目录项指向同一个索引结点索引结点中需要有链接计数count某用户想删除文件时，只是删除该用户的目录项，且count--只有count == 0时才能真正删除文件数据和索引结点，否则会导致指针悬空软链接(符号链接)在一个Link型的文件中记录共享文件的存放路径(Windows快捷方式)操作系统根据路径一层层查找目录，最终找到共享文件即使软链接指向的共享文件已被删除，Link型文件依然存在，只是通过Link型文件中的路径去查找共享文件会失败由于用软链接的方式访问共享文件时要查询多级目录，会有多次磁盘I/O，因此用软链接访问共享文件的速度要比硬链接更慢文件保护口令保护为文件设置一个"口令"，用户想要访问文件时需要提供口令，由系统验证口令是否正确实现开销小，但"口令"一般存放在FCB或索引结点中(也就是存放在系统中)因此不太安全加密保护用一个"密码"对文件加密，用户想要访问文件时，需要提供相同的"密码"才能正确的解密安全性高，但加密/解密需要耗费一定的时间访问控制用一个访问控制表(ACL)记录各个用户(或各组用户)对文件的访问权限对文件的访问类型可以分为：读/写/执行/删除等实现灵活，可以实现复杂的文件保护功能文件系统的层次结构用户接口文件系统需要向上层的用户提供一些简单易用的功能接口。这层就是用于处理用户发出的系统调用请求(Read、Write、Open、Close等系统调用)文件目录系统用户是通过文件路径来访问文件的，因此这一层需要根据用户给出的文件路径找到相应的FCB或索引结点。所有和目录、目录项相关的管理工作都在本层完成，如：管理活跃的文件目录表、管理打开文件表等。存取控制模块为了保证文件数据的安全，还需要验证用户是否有访问权限。这一层主要完成了文件保护相关功能。逻辑文件系统与文件信息缓冲区用户指明想要访问文件记录号，这一层需要将记录号转换为对应的逻辑地址物理文件系统这一层需要把上一层提供的文件逻辑地址转换为实际的物理地址辅助分配模块负责文件存储空间的管理，即负责分配和回收存储空间设备管理模块直接与硬件交互，负责和硬件直接相关的一些管理工作。如：分配设备、分配设备缓冲区、磁盘调度、启动设备、释放设备磁盘的结构磁盘、磁道、扇区磁盘由表面涂有磁性物质的圆形盘片组成每个盘片被划分为一个个磁道，每个磁道又划分为一个个扇区如何在磁盘中读/写数据磁头移动到目标位置，盘片旋转，对应扇区划过磁道才能完成读/写盘面、柱面磁盘有多个盘片"摞"起来，每个盘片有两个盘面所有盘面中相对位置相同的磁道组成柱面磁盘的物理地址(柱面号，盘面号，扇区号)磁盘的分类根据磁头是否可移动固定头磁盘(每个磁道有一个磁头)移动头磁盘(每个盘面只有一个磁头)根据盘片是否可更换固定盘磁盘可换盘磁盘磁盘调度算法一次磁盘读/写操作需要的时间寻找时间(寻道时间)：启动磁臂、移动磁头所花的时间延迟时间：将目标扇区转到磁头下面所花的时间传输时间：读/写数据花费的时间磁盘调度算法先来先服务算法(FCFS)按访问请求到达的先后顺序进行处理最短寻找时间优先(SSTF)每次都优先响应距离磁头最近的磁道访问请求贪心算法的思想，能保证眼前最优，但无法保证总的寻道时间最短缺点：可能导致饥饿扫描算法(电梯算法、SCAN)只有磁头移动到最边缘的磁道时才可以改变磁头移动方向缺点：对各个位置磁道的响应频率不平均循环扫描算法(C-SCAN)只有磁头朝某个方向移动时才会响应请求，移动到边缘后立即让磁头返回起点，返回途中不响应任何请求低频考点若题目中无特别说明，则SCAN就是LOOK，C-SCAN就是C-LOOKLOOK算法SCAN算法的改进，只要在磁头移动方向上不再有请求，就立即改变磁头方向C-LOOK算法C-SCAN算法的改进，只要在磁头移动方向上不再有请求，就立即让磁头返回减少延迟时间的方法交替编号具体做法：让编号相邻的扇区在物理上不相邻原理：读取完一个扇区后需要一段时间处理才可以继续读入下一个扇区错位命名具体做法：让相邻盘面的扇区编号"错位"原理：与"交替编号"的原理相同。"错位命名法"可降低延迟时间磁盘地址结构的设计理解为什么要用(柱面号，盘面号，扇区号)的结构理解为什么不用(盘面号，柱面号，扇区号)的结构原因：在读取地址连续的磁盘块时，前者更不需要移动磁头磁盘的管理磁盘初始化低级格式化/物理格式化：划分扇区磁盘分区(C盘、D盘、E盘)逻辑格式化：建立文件系统(建立根目录文件、建立用于存储空间管理的数据结构)引导块计算机启动时需要运行初始化程序(自举程序)来完成初始化ROM中存放很小的自举装入程序完整的自举程序存放在初始块(引导块)中坏块的管理简单的磁盘：逻辑格式化时将坏块标记出来复杂的磁盘：磁盘控制器维护一个坏块链，并管理备用扇区5 输入输出管理概念和分类I/O设备将数据Input/Output(输入/输出)计算机的外部设备按使用特性分类人机交互类外部设备存储设备网络通信设备按传输速率分类低速设备中速设备高速设备按信息交换的单位分类块设备(传输快，可寻址)字符设备(传输慢，不可寻址，常采用中断驱动方式)I/O控制器主要功能接受和识别CPU发出的命令(要有 控制寄存器)向CPU报告设备的状态(要有状态寄存器)数据交换(要有数据寄存器，暂存输入输出的数据)地址识别(由I/O逻辑实现)组成CPU与控制器之间的接口(实现控制器与CPU之间的通信)I/O逻辑(负责识别CPU发出的命令，并向设备发出命令)控制器与设备之间的接口(实现控制器与设备之间的通信)两种寄存器编址方式内存映射I/O控制器中的寄存器与内存统一编制可以采用对内存进行操作的指令来对控制器进行操作寄存器独立编址控制器中的寄存器独立编制需要设置专门的指令来操作控制器I/O控制方式程序直接控制方式中断驱动方式DMA方式通道控制方式I/O软件层次结构用户层软件设备独立性软件设备驱动程序中断处理程序硬件输入/输出应用程序接口设备接口阻塞/非阻塞IO阻塞I/O：应用程序发出I/O系统调用，进程需转为阻塞态等待。例如：字符设备接口：从键盘读一个字符。非阻塞I/O：应用程序发出I/O系统调用，系统调用可迅速返回，进程无需阻塞等待。例如：块设备接口：往磁盘写数据write。I/O核心子系统I/O调度用某种算法确定一个好的顺序来处理各个I/O请求设备保护操作系统需要实现文件保护功能，不同的用户对各个文件有不同的访问权限(如：只读、读和写等)。假脱机技术SPOOLing脱机技术外围控制机 + 更高速的设备：磁带作用：缓解设备与CPU的速度矛盾，实现预输入、缓输出假脱机技术又叫SPOOLing技术，用软件的方式模拟脱机技术输入井和输出井：模拟脱机输入/输出时的磁带输入进程和输出进程：模拟脱机输入/输出时的外围控制机输入缓冲区和输出缓冲区：内存中的缓冲区， 输入、输出时的"中转站"共享打印机用SPOOLing技术将独占式的打印机"虚拟"成共享打印机设备驱动程序接口设备的分配与回收考虑因素固有属性独占设备共享设备虚拟设备(SPOOLing)分配算法先来先服务、优先级高者优先、短任务优先等安全性安全分配方式为进程分配一个设备后就将进程阻塞，本次I/O完成后才将进程唤醒。不安全分配方式进程发出I/O请求后，系统为其分配I/O设备，进程可继续执行，之后还可以发出新的I/O请求。只有某个I/O请求得不到满足时才将进程阻塞。静态分配与动态分配静态分配进程运行前为其分配全部所需资源，运行结束后归还资源动态分配进程运行过程中动态申请设备资源设备分配管理中的数据结构设备控制表(DCT)每个设备对应一张DCT，关键字段：类型/标识符/状态/指向COCT的指针/等待队列指针控制器控制表(COCT)每个控制器对应一张COCT，关键字段：状态/指向CHCT的指针/等待队列指针通道控制表(CHCT)每个控制器对应一张CHCT，关键字段：状态/等待队列指针系统设备表(SDT)记录整个系统中所有设备的情况，每个设备对应一个表目，关键字段：设备类型/标识符/DCT/驱动程序入口设备分配的步骤①根据进程请求的物理设备名查找SDT②根据SDT找到DCT并分配设备③根据DCT找到COCT并分配控制器④根据COCT找到CHCT并分配通道注：只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功，之后便可启动I/O设备进行数据传送缺点：用户编程时必须使用"物理设备名"，若换了一个物理设备，则程序无法运行。若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待设备分配的步骤的改进用户编程时使用逻辑设备名申请设备，操作系统负责实现从逻辑设备名到物理设备名的映射(通过LUT)逻辑设备表的设置问题整个系统只有一张LUT：各用户所用的逻辑设备名不允许重复每个用户一张LUT：各个用户的逻辑设备名可重复缓冲区管理缓冲区的概念缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区。作用缓和CPU与I/O设备之间速度不匹配的矛盾减少对CPU的中断频率，放宽对CPU中断响应时间的限制解决数据粒度不匹配的问题提高CPU与I/O设备之间的并行性单缓冲设备-(输入T)-缓冲区-(传送M)-工作区-(处理C)处理一块数据平均耗时Max(C, T) + M分析问题的初始状态：工作区满，缓冲区空双缓冲处理一块数据的平均耗时Max(T, C + M)分析问题的初始状态：工作区空，一个缓冲区满，另一个缓冲区空循环缓冲多个缓冲区链接成循环队列，in指针指向第一个空缓冲区， out指针指向第一个满缓冲区缓冲池三个队列：空缓冲队列、输入队列、输出队列四种工作缓冲区用于收容输入数据的工作缓冲区、用于提取输入数据的工作缓冲区用于收容输出数据的工作缓冲区、用于提取输出数据的工作缓冲区固态硬盘
前言上学期（大二上）提前水过了操作系统课程，期末考试前总结了下。之后还会深入学习。以下内容仅为应对期末考试概念题：操作系统功能：处理机管理，存储器管理，设备管理，文件管理，用户接口用户接口：用户使用计算机系统的手段称为用户接口。编程接口：编程接口是为用户程序在执行中访问系统资源而设置的，是用户程序获得操作系统服务的唯一途径。它由一组系统调用组成，每一个系统调用都对应一个能完成特定功能的子程序。进程状态： 进程：一般来说，进程是程序的一次执行过程，它可以和其他进程并发执行。也可以说进程是程序在一个数据集合上的一次执行过程，是系统进行资源分配和调度的独立单位。总的来说，进程是具有一定独立功能的程序关于一个数据集合的一次运行过程。进程通常分成两类：用户进程和系统进程。进程的组成：进程控制块，有关程序段，相应的数据结构集。进程控制块（PCB）：进程标识信息，处理机状态，进程调度信息，进程控制信息缓冲：引入缓冲的原因：为了匹配外设与CPU之间的处理速度。为了减少中断次数和中断处理时间。为了解决DMA或通道方式时的瓶颈问题。缓冲的种类单缓冲多缓冲缓冲池缓冲池由多个缓冲区组成。一个缓冲区由两部分组成：一部分是用来标识该缓冲区和用于管理的缓冲首部，另一部分是用于存放数据的缓冲体。这两部分一一对应。SPOOLing系统：操作系统中实现虚拟设备的功能模块是在计算机控制下通过联机的外部设备同时操作来实现其功能的。组成：预输入程序。井管理程序。缓输出程序。SPOOLing系统必须建立在具有多道程序功能的操作系统上，而且还应有高速随机外存的支持，这通常是采用磁盘存储技术。特点：提高了I/O的速度。将独占设备改造为共享设备。实现了虚拟设备功能。文件：文件被解释为一组赋名的相关联字符或者是相关联记录（一个有意义的信息单位）的集合。文件共享：文件共享是指一个文件可以让指定的多个用户同时使用。文件共享的方式：①绕道法。②链接法。③基本文件目录法。中断：中断是指计算机在执行期间，系统内发生非寻常的急需处理事件，使得CPU暂时停止当前正在执行的程序而转去执行相应的事件处理程序，待处理完毕后又返回原来被停止处继续执行或执行优先级高的新进程的过程。 （中断源，中断请求，中断响应）通道：通道是一种硬件设施，本质上是一台专门用来管理I/O的处理器，它根据来自CPU的I/O操作指令，以独立于CPU的方式执行有关的通道程序，承担起I/O操作的组织，管理，数据传送以及结束等工作。只有在结束了CPU委托的I/O任务之后才向CPU发出中断请求信号。通道的连接方式： 四级连接，三级控制通道的类型：字节多路通道选择通道数组多路通道通道适配器问答题（6道大题）：一. 作业调度算法：1. △先来先服务调度算法（FCFS） 2. 优先级调度算法（静态/动态优先级） 2. 轮转调度算法 根据时间片是否可变，分为 固定周期轮转法，可变周期轮转法 4. △分级轮转调度算法： 多个就绪队列 高优先级队列为空才能调度低优先级队列的进程 5. 分级反馈轮转调度算法 允许进程在不同的队列间移动 6. △最短作业优先调度算法 作业周转快，系统的吞吐量大 7. △响应比高者优先级调度算法 Rp = (等待时间 + 要求执行时间) / 要求执行时间 = 1 + 等待时间/要求执行时间 分析调度情况，计算 平均周转时间，平均带权周转时间 例题： 地址转换：静态地址重定位，动态地址重定位（需要硬件支持，能够实现虚拟内存）分区存储管理：单分区存储管理多分区存储管理（固定分区存储管理，可变分区存储管理）；分配算法：最先适应分配算法，最优适应分配算法，最坏适应分配算法虚拟存储管理方法：动态页式，动态段式，动态段页式页式存储管理：静态页式（作业/进程执行前，按页全部装入内存），动态页式把主存分成大小相等的区，称为块。把程序的逻辑空间进行分页，页的大小和块相等。按页存放到块中。二. 页面置换算法：1. 随机置换算法 2. 轮转置换算法（RR） 3. △先进先出置换算法（FIFO） 4. △最近最少用置换算法（LRU） 5. 最近最不常用置换算法（LFU） 6. Clcok置换算法 简单Clock置换算法（访问位），改进型Clock置换算法（访问位，修改位） 7. 页面缓冲算法（PBA） 8. 最佳置换算法（OPT） 例题：缺页次数 = 总列数 - 空白列数缺页率 = 缺页次数 / 总列数FIFO算法： 可参考进行应试学习LRU算法 三. 磁盘的驱动调度块是信息读/写的最小单位。 确定一个块所在的位置，必须给出3个参数：柱面号，磁头号，扇区号 驱动调度：移臂调度，旋转调度 移臂调度： 1. 先来先服务调度算法（FCFS） 2. 最短寻找时间优先调度算法（SSTF）距离磁头最近的 3. 扫描调度算法（SCAN 电梯算法）看磁头方向，找到最大的后，找离磁头最近的 4. 循环扫描调度算法（CSCAN）磁头单向移动，到上限后从0开始 列表： 被访问的下一个磁道号 移动距离（磁道数） 计算时间： 总的访问时间 = 寻道时间 + 延迟时间 + 传输时间 计算寻道时间：移动磁道需要的时间。 计算延迟时间：6000r/min = 100r/s 平均旋转延迟时间 = 1/100 / 2 = 5ms 总的旋转延迟时间 = 5 * 4 = 20 ms 计算传输时间：100r/s = 0.01s/r 读取一个扇区的时间 = 10ms/100（扇区数） = 0.1ms 传输时间 = 0.1ms * 4 = 0.4ms 求和即可。4为寻道次数四. PV原语当时差不多放弃这道题了，题型不固定，比较难。没有复习套路。五. 避免死锁（银行家算法）求出 尚需量 = 最大需求量 - 已占资源 列表： 给出：进程已占资源最大需求量尚需量（最大需求量 - 已占资源）----进程可提供Work需要Need已分配Allocation释放Work+Allocation完成FinishP1根据题目尚需量已占资源可提供+已分配true给出结论： 存在安全序列P1,P2,目前系统处于安全状态。六. 文件系统：出题比较简单，小学生运算。 例题：