阻塞态），主动放弃处理机，并插入该类资源的等待队列S.L 中。可见，该机制遵循了“让权等待”原则，不会出现“忙等”现象。\n\n对信号量S 的一次V 操作意味着进程释放一个单位的该类资源，因此需要执行S.value++，表示资源数加1，若加1后仍是 S.value <= 0，表示依然有进程在等待该类资源，因此应调用wakeup 原语唤醒等待队列中的第一个进程（被唤醒进程从阻塞态 ----> 就绪态）。\n\n### 信号量机制实现进程互斥\n\n理解：信号量mutex 表示“进入临界区的名额”\n\n **注意：** \n\n \n\n### 信号量机制实现进程同步\n\n **进程同步** ：要让各并发进程按要求有序地推进。\n\n比如，P1、P2 并发执行，由于存在异步性，因此二者交替推进的次序是不确定的。若P2 的“代码4”要基于 P1 的“代码1”和“代码2”的运行结果才能执行，那么我们就必须保证“代码4”一定是在“代码2”之后才会执行。\n\n这就是进程同步问题，让本来异步并发的进程互相配合，有序推进。\n\n **用信号量实现进程同步：** \n\n **技巧口诀：前V后P** \n\n \n\n### 信号量机制实现前驱关系\n\n进程P1 中有句代码S1，P2 中有句代码S2 ，P3中有句代码S3 …… P6 中有句代码S6。这些代码要求按如下前驱图所示的顺序来执行\n\n其实每一对前驱关系都是一个进程同步问题（需要保证 **一前一后** 的操作）\n\n **因此：** \n\n \n\n### 10、经典进程同步问题\n\n### 生产者消费者问题\n\n### 问题描述\n\n系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（注：这里的“产品”理解为某种数据）\n\n生产者、消费者共享一个初始为空、大小为n的缓冲区。\n\n### 问题分析\n\n **PV操作题目分析步骤：** \n\n\n\n```\nsemaphore mutex = 1; // 互斥信号量，实现对缓冲区的互斥访问\nsemaphore empty = n; // 同步信号量，表示空闲缓冲区的数量\nsemaphore full = 0; // 同步信号量，表示产品的数量，也即非空缓冲区的数量\n```\n\n### 如何实现\n\n \n\n **能否改变相邻的PV操作顺序？** \n\n① -> ② -> ③\n\n若此时缓冲区内已经放满产品，则empty=0，full=n。\n\n则生产者进程执行①使mutex变为0，再执行②，由于已没有空闲缓冲区，因此生产者被阻塞。由于生产者阻塞，因此切换回消费者进程。消费者进程执行③，由于mutex为0，即生产者还没释放对临界资源的“锁”，因此消费者也被阻塞。这就造成了生产者等待消费者释放空闲缓冲区，而消费者又等待生产者释放临界区的情况，生产者和消费者循环等待被对方唤醒，出现“死锁”。\n\n③ -> ④ -> ①\n\n同样的，若缓冲区中没有产品，即full=0，empty=n。按③④① 的顺序执行就会发生死锁。\n\n因此， **实现互斥的P操作一定要在实现同步的P操作之后。** \n\n **V操作不会导致进程阻塞，因此两个V操作顺序可以交换。** \n\n \n\n### 多生产者多消费者问题\n\n### 问题描述\n\n桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。\n\n \n\n### 问题分析\n\n互斥关系：（mutex = 1）：对缓冲区（盘子）的访问要互斥地进行\n\n同步关系（一前一后）：\n\n### 如何实现\n\n \n\n **不设置互斥信号量？** \n\n **原因在于** ：本题中的缓冲区大小为1，在任何时刻，apple、orange、plate三个同步信号量中最多只有一个是1。因此在任何时刻,最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区…\n\n如果缓冲区大小为2，则两个生产者会都进入临界区（可能造成后者将前者的数据覆盖掉），这时候就必须得设置互斥信号量了！\n\n **注意：** \n\n### 吸烟者问题\n\n### 问题描述\n\n假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。\n\n三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。\n\n供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）\n\n### 问题分析\n\n **同步关系** \n\n **互斥关系** \n\n \n\n### 如何实现\n\n \n\n### 读者写者问题\n\n### 问题描述\n\n有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。\n\n **因此要求：** \n\n \n\n### 问题分析\n\n **两类进程** ：写进程、读进程\n\n **互斥关系** ：写进程—写进程、写进程—读进程。读进程与读进程不存在互斥问题。\n\n### 如何实现\n\n此种实现是 **读进程优先** 的，读进程一直进入，则会导致写进程饿死！\n\n \n\n **写优先** ，但不是真正的写优先，相对公平的先来先服务原则，又叫做 **读写公平法** ！\n\n \n\n### 哲学家进餐问题\n\n### 问题描述\n\n一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。\n\n### 问题分析\n\n这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有“死锁”问题的隐患。\n\n### 如何实现\n\n **错误方案** \n\n \n\n **合理方案** \n\n **第三种方案的实现：** \n\n可以保证至少有一人可以吃到饭！\n\n \n\n### 11、管程\n\n **为什么要引入管程** \n\n信号量机制存在的问题：编写程序困难、易出错\n\n能不能设计一种机制，让程序员写程序时不需要再关注复杂的PV操作，让写代码更轻松呢？\n\n1973年，Brinch Hansen 首次在程序设计语言 (Pascal)中引入了“ **管程** ”成分，即一种 **高级同步机制** \n\n### 管程定义\n\n管程是一种特殊的软件模块，由这些部分组成：\n\n类似于 **类** ！\n\n### 管程基本特征\n\n前两句类似：类对象对类的访问！\n\n### 管程解决生产者消费者问题\n\n \n\n引入管程的目的无非就是要 **更方便地实现进程互斥和同步** 。\n\n **简单来说：封装思想！** \n\n**想更深入的理解操作系统，可以看看下面这个视频：**麻省理工6.s081课程****\n\n[麻省理工6.s081课程，深入掌握linux操作系统，互联网大厂C++面试题必备​www.bilibili.com/video/BV1sUrWYXEJg/](https://www.bilibili.com/video/BV1sUrWYXEJg/)\n\n### 12、死锁\n\n### 脑图\n\n \n\n### 什么是死锁\n\n哲学家进餐问题中，如果5位哲学家进程并发执行，都拿起了左手边的筷子…\n\n每位哲学家都在等待自己右边的人放下筷子，这些哲学家进程都因等待筷子资源而被阻塞。即发生“死锁”\n\n在 **并发环境** 下，各进程因 **竞争资源** 而造成的一种 **互相等待** 对方手里的资源，导致各进程 **都阻塞** ，都无法向前推进的现象，就是“死锁”。发生死锁后若无外力干涉,这些进程都将无法向前推进。\n\n### 死锁&饥饿&死循环\n\n **死锁** ：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。\n\n **饥饿** ：由于长期得不到想要的资源，某进程无法向前推进的现象。比如:在短进程优先(SPF) 算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机， 从而发生长进程“饥饿”。\n\n **死循环** ：某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug导致的，有时是程序员故意设计的。\n\n \n\n### 死锁产生必要条件\n\n产生死锁必须同时满足以下四个条件， **只要其中任一条件不成立，死锁就不会发生** 。\n\n **互斥条件** ：只有对必须互斥使用的资源的争抢才会导致死锁(如哲学家的筷子、打印机设备)。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的(因为进程不用阻塞等待这种资源)。\n\n **不剥夺条件** ：进程所获得的资源在未使用完之前， **不能由其他进程强行夺走** ，只能主动释放。\n\n **请求和保持条件** ：进程 **已经保持了至少一个资源** ，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。\n\n **循环等待条件** ：存在一种进程 **资源的循环等待链** ，链中的每一个进程已获得的资源同时被下一个进程所请求。\n\n **注意** ：发生死锁时一定有循环等待，但是发生循环等待时未必死锁( 循环等待是死锁的 **必要不充分条件** )\n\n如果同类 **资源数大于1** ，则即使有循环等待，也未必发生死锁。但如果系统中每类资源都只有一个，那循环等待就是死锁的 **充分必要条件** 了。\n\n### 什么时候发生死锁\n\n **对系统资源的竞争** 。各进程对不可剥夺的资源(如打印机)的竞争可能引起死锁，对可剥夺的资源(CPU)的竞争是不会引起死锁的。\n\n **进程推进顺序非法** 。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程P1、P2分别申请并占有了资源R1、R2，之后进程P1又紧接着申请资源R2，而进程P2又申请资源R1,两者会因为申请的资源被对方占有而阻塞，从而发生死锁。\n\n **信号量的使用不当也会造成死锁** 。如生产者~消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。(可以把互斥信号量、同步信号量也看做是一种抽象的系统资源)\n\n总之，对 **不可剥夺资源的不合理分配** ，可能导致死锁。\n\n### 死锁处理策略\n\n### 预防死锁\n\n### 脑图\n\n \n\n### 破坏互斥条件\n\n **互斥条件** ：只有对必须互斥使用的资源的争抢才会导致死锁。\n\n如果把只能 **互斥** 使用的资源改造为 **允许共享** 使用，则系统不会进入死锁状态。比如 : **SPOOLing技术** 。\n\n操作系统可以采用SPOOLing 技术把独占设备在逻辑上改造成共享设备。比如，用SPOOLing技术将打印机改造为共享设备…（打印机添加任务队列即可）\n\n **该策略的缺点** ：并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。\n\n### 破坏不剥夺条件\n\n **不剥夺条件** ：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。\n\n **方案一** ：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要 **主动释放** ，从而破坏了不可剥夺条件。\n\n **方案二** ：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源 **强行剥夺** 。这种方式一般需要考虑各进程的优先级（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）\n\n **该策略的缺点：** \n\n### 破坏请求和保持条件\n\n **请求和保持条件** ：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。\n\n可以采用 **静态分配** 方法，即进程在运行前一次申请完它所需要的全部资源，在它的 **资源未满足前，不让它投入运行** 。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。\n\n **该策略实现起来简单，但也有明显的缺点：** \n\n### 破坏循环等待条件\n\n **循环等待条件** ：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。\n\n可采用 **顺序资源分配法** 。首先给系统中的资源编号，规定每个进程必须按 **编号递增的顺序请求** 资源， **同类资源** （即编号相同的资源） **一次申请完** 。\n\n **原理分析** ：一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程 **不可能逆向** 地回来申请小编号的资源，从而就不会产生循环等待的现象。\n\n **该策略的缺点：** \n\n### 避免死锁\n\n### 安全序列&不安全状态&死锁\n\n **安全序列** ，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是 **安全状态** 。当然，安全序列可能有多个。\n\n如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了 **不安全状态** 。这就意味着之后可能所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况。\n\n如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态）\n\n因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是“银行家算法”的核心思想。\n\n### 银行家算法\n\n银行家算法是荷兰学者Dijkstra 为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中，用于 **避免死锁** 。\n\n **核心思想** ：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。\n\n \n\n \n\n **银行家算法步骤：** \n\n **数据结构：** \n\n **安全性算法步骤：** \n\n### 死锁的检测和解除\n\n### 脑图\n\n \n\n### 死锁检测\n\n为了能对系统是否已发生了死锁进行检测，必须：\n\n \n\n如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利地执行下去。如果这个进程执行结束了把资源归还系统，就可能使某些正在等待资源的进程被激活，并顺利地执行下去。相应的，这些被激活的进程执行完了之后又会归还一些资源，这样可能又会激活另外一些阻塞的进程…\n\n如果按上述过程分析，最终能 **消除所有边** ，就称这个图是 **可完全简化** 的。此时 **一定不发生死锁** （相当于能找到一个 **安全序列** ）\n\n如果最终 **不能消除所有边** ，那么此时就是 **发生了死锁** \n\n **死锁例子：** \n\n \n\n### 死锁解除\n\n一旦检测出死锁的发生，就应该 **立即解除死锁** 。\n\n **补充** ：并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后， **还连着边** 的那些进程就是 **死锁进程** \n\n **解除死锁的主要方法有：** \n\n **如何绝对对谁动手？** \n\n## 三、内存管理\n\n### 1、内存基础知识\n\n \n\n### 内存\n\n **指令** 的编指一般采用逻辑地址，即相对地址\n\n **物理地址** = 起始地址 + 逻辑地址\n\n相对地址又称逻辑地址，绝对地址又称物理地址。\n\n### 进程运行基本原理\n\n \n\n### 三种链接方式\n\n **链接** ：由连接程序将编译后形成的一组目标 **模块** 以及所需 **函数** 连接在一起, 形成一个完整的装入模块\n\n### 三种装入方式\n\n **装入** ：由装入程序将装入模块装入内存运行\n\n为了使编程更方便，程序员写程序时应该只需关注指令、数据的逻辑性。而 **逻辑地址到物理地址的转换** （这个过程称为 **地址重定位** ），应该由操作系统负责，这样就保证了程序员写程序时不需要关注物理内存的实际情况。\n\n在编译时，如果知道程序将放到内存的哪个位置，编译程序将产生绝对地址的目标代码, 装入程序按照装入模块中的地址，将程序和数据装入内存【灵活性低, 只适合单道程序环境】\n\n绝对装入只适用于 **单道程序** 环境。还未产生操作系统，由编译器完成！\n\n程序中使用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。通常情况下都是编译或汇编时再转换为绝对地址。\n\n又称为 **可重定位装入** 。 编译, 链接后的装入模块地址都是从 0 开始的，指令中使用的地址和数据存放的地址都是相对于起始地址而言的逻辑地址。可以根据内存的当前状况将装入模块装入到内存的适当位置。装入时对地址进行\" **重定位** \"，逻辑地址变换为物理地址（地址变换是在装入时一次完成的）。【 **早期多道批处理系统** 】\n\n **静态重定位的特点** 是在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业。作业一旦进入内存后， **在运行期间就不能再移动** ，也不能再申请内存空间。\n\n又称 **动态运行时装入** 。编译、链接后的装入模块的地址都是从0开始的，装入程序把装入模块装入内存后不会立即把逻辑地址转换为物理地址，而是把地址转换 **推迟到程序真正要执行时才进行** 。因此装入内存后所有的地址依然是逻辑地址。这种方式需要一个 **重定位寄存器** （存放装入模块的起始位置）的支持。【 **现代操作系统** 】\n\n### 操作系统内存管理\n\n **1、2、4 将在下方讲解！** \n\n### 2、内存保护采用的方法\n\n### 3、内存空间的扩充\n\n### 大纲\n\n \n\n### 覆盖技术\n\n **覆盖技术** ：将程序分为多个段，常用的段常驻内存，不常用的段在需要的时候调入内存\n\n内存中分为 **一个\"固定区\" 和若干个\"覆盖区\"** ，常用的段放在固定区，不常用的段放在覆盖区\n\n **缺点** ：必须由程序员声明覆盖结构， 对用户不透明， 增加了用户的编程负担，覆盖技术只用于 **早期的操作系统** 中。\n\n \n\n### 交换技术\n\n **交换技术** ：内存空间紧张时, 系统将内存中某些进程 **暂时换出外存** ，把外存中某些已具备运行条件的进程换入内存(即 **进程在内存与磁盘间动态调度** )\n\n **应该在外存（磁盘）的什么位置保存被换出的进程？** \n\n具有对换功能的操作系统中，通常把磁盘空间分为 **文件区** 和 **对换区** 两部分。文件区主要用于 **存放文件** ，主要追求存储空间的利用率，因此对 **文件区** 空间的管理 **采用离散分配方式** ；对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度，因此 **对换区** 空间的管理主要 **追求换入换出速度** ，因此通常对换区 **采用连续分配方式** 。总之，对换区的I/O速度比文件区的更快。\n\n **什么时候应该交换？** \n\n交换通常在许 **多进程运行** 且 **内存吃紧时** 进行，而系统负荷降低就暂停。例如：在发现许多进程运行时经常发生 **缺页** ，就说明内存紧张，此时可以换出一些进程;如果缺页率明显下降，就可以暂停换出。\n\n **应该换出哪些进程？** \n\n可优先换出 **阻塞进程** ；可换出 **优先级低** 的进程；为了防止优先级低的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间。\n\n **PCB仍然得常驻内存！** \n\n### 虚拟存储技术\n\n### 大纲\n\n \n\n### 传统存储方式问题\n\n **一次性** ：作业必须一次性全部装入内存后才能开始运行\n\n **驻留性** ：一旦作业被装入内存，就会一直驻留在内存中，直到作业运行结束，这样会导致内存中驻留大量的，暂时用不到的数据，浪费内存资源。\n\n### 高速缓冲技术\n\n是对局部性原理的应用！\n\n将近期会频繁访问到的数据放到更高速的存储器中，暂时用不到的数据放在更低速存储器中。\n\n \n\n### 虚拟内存的定义和特征\n\n **虚拟内存的最大容量** 是由计算机的地址结构（CPU的寻址范围）确定的\n\n **虚拟内存的实际容量** = min（内存容量+外存容量，CPU寻址范围）\n\n **特征** ：\n\n多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。\n\n对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。\n\n虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量远大于实际容量。\n\n### 虚拟内存的实现\n\n虚拟内存技术，允许一个作业分多次调入内存。如果采用连续分配方式，会不方便实现。因此，虚拟内存的实现需要建立在 **离散分配** （非连续分配）的内存管理方式基础上。\n\n对应传统的三种非连续分配存储管理，有三种虚拟存储的实现：\n\n **调入** ：在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从 **外存调入内存** ，然后继续执行程序。（操作系统要提供 **请求调页 / 调段** 功能）\n\n **调出** ：若内存空间不够，由操作系统负责将内存中暂时用不到的信息 **换出** 到外存。（操作系统要提供 **页面置换 / 段置换** 的功能）\n\n### 请求分页存储管理\n\n与基本分页管理方式的区别：\n\n **大纲** \n\n \n\n **页表机制** \n\n与基本分页管理相比，请求分页管理中，为了实现“请求调页”，操作系统需要知道每个页面是否已经调入内存;如果还没调入，那么也需要知道该页面在外存中存放的位置。\n\n当内存空间不够时，要实现“页面置换”，操作系统需要通过某些指标来决定到底换出哪个页面;有的页面没有被修改过，就不用再浪费时间写回外存。有的页面修改过，就需要将外存中的旧数据覆盖，因此，操作系统也需要记录各个页面是否被修改的信息。\n\n \n\n **缺页中断机构** \n\n在请求分页操作系统中，每当要访问的页面不在内存时，便产生一个缺页中断, 然后由操作系统的缺页中断处理程序处理中断。\n\n此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒, 放回就绪队列。\n\n **缺页中断** 是因为当前执行的指令想要访问目标页面未调入内存而产生的，因此属于 **内中断** （故障） 。\n\n **一条指令** 在执行期间，可能产生多 **次缺页中断** 。(如: copy A to B，即将逻辑地址A中的数据复制到逻辑地址B，而A、B属于不同的页面，则有可能产生两次中断）\n\n **地址变换机构** \n\n \n\n### 页面置换算法\n\n **大纲** \n\n \n\n页面的换入、换出需要磁盘I/O，会有较大的开销，因此好的页面置换算法应该追求更少的缺页率！\n\n **最佳置换算法(OPT)** \n\n优先淘汰以后永不使用或者在最长时间内不会使用的页面，保证最低的缺页率。\n\n但是操作系统无法预判页面访问序列，这种算法是 **无法实现** 的。\n\n **先进先出置换算法(FIFO)** \n\n优先淘汰最早进入内存的页面。\n\n实现 ：将调入内存的页面根据调入的先后顺序排成一个队列，需要置换页面的时候选择队首的页面。\n\n实现简单；算法性能差，不适应进程实际运行时的规律，可能出现 **Belady** 异常。\n\n **Belady异常** ――当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。\n\n只有FIFO算法会产生Belady异常。\n\n **最近最久未使用置换算法(LRU)** \n\n优先淘汰最近最久未使用的页面。\n\n性能好，但实现起来需要专门的硬件支持，算法开销大。\n\n **时钟置换算法(CLOCK)** \n\n又叫做 **最近未用算法 NRU** \n\n为每个页面设置一个 **访问位** ，再将内存中的页面都通过链接指针链接成一个 **循环队列** 。\n\n循环扫描各页面， **第一轮** 淘汰访问位 = 0 的，并将扫描过的页面访问位改为1。若第一轮没选中，则进行第二轮扫描。（ **最多会扫描两轮！** ）\n\n实现简单，算法开销小；但 **未考虑** 页面 **是否被修改过** 。\n\n简单的时钟置换算法仅考虑到了一个页面最近是否被访问过，但是事实上，如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。\n\n因此, 除了考虑一个页面最近有没有被访问过之外，操作系统还应该考虑页面有没有被修改过。\n\n在其他条件都相同时， **应该优先淘汰没有修改过的页面** , 避免I/O操作，这就是改进型的时钟置换算法的思想。\n\n **改进型的时钟置换算法** \n\n利用**(访问位，修改位)** 的形式表示各页面状态\n\n简而言之：按照00,01,10,11的优先级进行替换！\n\n算法开销小，性能也不错。\n\n **最多扫描四轮！** \n\n### 页面分配策略\n\n **大纲** \n\n \n\n **驻留集** ：请求分页存储管理器中给进程分配的物理块的集合。\n\n在采用虚拟存储技术的系统中, 驻留集的大小一般小于进程的总大小\n\n **策略** \n\n **局部置换：** 发生缺页时只能选进程自己的物理块进行置换。\n\n **全局置换：** 可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。\n\n \n\n **页面分配&置换策略？** \n\n **固定分配局部置换** ：系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。这种策略的缺点是:很难在刚开始就确定应为每个进程分配多少个物理块才算合理。(采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数)\n\n **可变分配全局置换** ：刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程;若已无空闲物理块，则可选择一个 **未锁定** 的页面换出外存，再将该物理块分配给缺页的进程。采用这种策略时， **只要某进程发生缺页，都将获得新的物理块** ，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程中的页，因此这个 **被选中的进程拥有的物理块会减少，缺页率会增加。** \n\n **可变分配局部置换** ：刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度;反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。\n\n **何时调入页面？** \n\n **预调页策略** ：根据 **局部性原理** （主要指空间局部性），一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过，则又是低效的。因此可以 **预测** 不久之后可能访问到的页面，将它们预先调入内存，但目前预测成功率只有50%左右。故这种策略主要用于进程的首次调入，由程序员指出应该先调入哪些部分。（ **运行前调入** ）\n\n **请求调页策略** ：进程在 **运行期间发现缺页时才将所缺页面调入内存** 。由这种策略调入的页面一定会被访问到，但由于每次只能调入一页，而每次调页都要磁盘I/O操作，因此I/O开销较大。（ **运行时调入** ）\n\n **何处调入页面？** \n\n \n\n **抖动现象？** \n\n刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为 **抖动，或颠簸** 。\n\n产生抖动的 **主要原因** 是进程频繁访问的页面数目高于可用的物理块数( **分配给进程的物理块不够** )。\n\n为了研究为应该为每个进程分配多少个物理块，Denning提出了进程“ **工作集** ”的概念\n\n **工作集？** \n\n \n\n **工作集大小** 可能小于窗口尺寸，实际应用中，操作系统可以统计进程的工作集大小，根据工作集大小给进程分配若干内存块。如:窗口尺寸为5，经过一段时间的监测发现某进程的工作集最大为3，那么说明该进程有很好的局部性，可以给这个进程分配3个以上的内存块即可满足进程的运行需要。\n\n一般来说， **驻留集大小不能小于工作集大小** ，否则进程运行过程中将频繁缺页。\n\n **拓展** ：基于局部性原理可知，进程在一段时间内访问的页面与不久之后会访问的页面是有相关性的。因此，可以根据进程近期访问的页面集合(工作集）来设计一种页面置换算法――选择一个不在工作集中的页面进行淘汰。\n\n### 4、内存空间的分配和回收\n\n### 大纲\n\n连续分配管理方式\n\n非连续分配管理方式\n\n### 连续分配管理方式\n\n \n\n **连续分配** ：指为用户进程分配的必须是一个连续的内存空间。\n\n### 单一连续分配\n\n在单一连续分配的方式中, 内存被分为 **系统区和用户区** ， 系统区用于存放操作系统的相关数据，用户区用于存放用户进程的相关数据。内存中 **只能有一道** 用户程序，用户程序 **独占** 整个用户区空间。\n\n **优点** : 实现简单, **无外部碎片** ; **可以采用覆盖技术扩充内存** ; **不一定需要采取内存保护** \n\n **缺点** : 只能用于 **单用户** , **单任务** 的操作系统中; **有内部碎片** ; 存储器利用率极低\n\n **内部碎片** : 分配给某进程的内存区域有一部分没有用上，即存在\" 内部碎片 \".\n\n **外部碎片** : 内存中的某些空闲分区由于太小而难以利用\n\n### 固定分区分配\n\n在产生了支持 **多道程序** 的系统后，为了能在内存中装入多道程序而互相之间不产生干扰，将整个 **用户区** 划分为若干个 **固定大小的分区** (分区大小可以相等也可以不相等)，在 **每个分区中只能装入一道作业** ， 形成了最早的可运行多道程序的内存管理方式。\n\n固定分区分配\n\n **操作系统如何记录内存中的各个分区？** \n\n操作系统建 **立分区说明表** 来实现各个分区的分配和回收。\n\n每个表对应一个分区，通常按分区大小排列。每个表项包括对应 **分区的大小，起始地址，状态（是否已分配）** 。\n\n用 **数据结构** 的数组（或链表）即可表示这个表。\n\n当某用户程序要装入内存时，由操作系统内核程序根据用户程序大小 **检索该表** ，从中找到一个能满足大小的、未分配的分区，将之分配给该程序，然后修改状态为 ” 已分配 “ 。\n\n **优点** ：实现简单， **无外部碎片** 。\n\n **缺点** ：\n\n### 动态分区分配\n\n动态分区分配又称为 **可变分区分配** ， 这种分配方式不会预先划分内存分区。而是在进程装入内存时 **根据进程大小动态地建立分区** ，并使得分区的大小正好适合进程的需要。系统分区的大小和数目是可变的！\n\n **系统要用什么样的数据结构记录内存的使用情况？** \n\n动态分配 **不会产生内部碎片, 而会产生外部碎片** , 外部碎片可以通过\" **紧凑** \"的方式解决。\n\n **当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配?** \n\n把一个新作业装入内存时，须按照一定的 **动态分区分配算法（后面详细讲解）** ，从空闲分区表（或空闲分区链）中选出一个分区分配给该作业。由于分配算法算法对系统性能有很大的影响，因此人们对它进行了广泛的研究。\n\n **如何进行分区的分配与回收操作?** \n\n### 动态分区分配算法\n\n### 首次适应算法\n\n每次都从低地址开始查找， **找到第一个** 能满足大小的空闲分区。\n\n **实现** ：把空闲分区按 **地址递增的次序排列** 。\n\n每次分配内存时顺序地查找空闲分区链，找到大小能满足要求的第一个空闲分区。\n\n **优点** ：综合看性能最好。算法开销小，回收分区后一般不需要对空闲分区队列重新排序。\n\n### 最佳适应算法\n\n **优先使用小** 的空闲分区\n\n **实现** ： 空闲分区按 **容量递增次序排序** 。\n\n每次分配内存时顺序查找空闲分区链, 找到大小能满足要求的第一个空闲分区。\n\n **优点** ：会有更多的大分区被保留下来，更能满足大进程需求。\n\n **缺点** ：每次都选择最小的分区进行分配，会留下越来越多的容量很小难以利用的内存块，即产生很多的外部碎片；算法开销大，回收分区后可能需要对空闲分区队列重新排序。\n\n### 最坏适应算法\n\n **优先使用大** 的空闲分区\n\n **实现** ： 空闲分区按 **容量递减次序排序** \n\n **优点** ：可以减少难以利用的小碎片。\n\n **缺点** ：每次都选用最大的分区进行分配，当较大的连续空闲区被小号之后，如果有大进程到来则没有内存分区可以利用；算法开销大。\n\n### 邻近适应算法\n\n在首次适应算法的基础上，每次都 **从上次查找结束的位置开始查找** 空闲分区链(表)，找到大小能满足的第一个空闲分区。\n\n **优点** ：不用每次都从低地址的小分区开始检索。算法开销小。\n\n **缺点** ：邻近适应算法导致无论低地址还是高地址的空闲分区都有相同的概率被使用，也就导致了高地址部分的大分区更可能被使用划分为小分区，最后导致没有大分区可用。\n\n### 小总结\n\n **算法开销大** ：最佳适应法, 最坏适应法 ( 需要经常排序)\n\n **算法开销小** ：首次适应算法, 邻近适应算法\n\n \n\n### 非连续分配管理方式\n\n **连续分配管理方式缺点：** \n\n基于这一思想，产生了“非连续分配方式”，或者称为“离散分配方式”。\n\n **非连续** ：为用户进程分配的可以是一些分散的内存空间！\n\n### 基本分页存储管理\n\n### 大纲\n\n \n\n### 分页存储基本概念\n\n \n\n **思想** ：把内存分为一个个相等的小分区, 再按照分区大小把进程拆分成一个个小部分.\n\n **页框** ：将内存大小分为一个个大小相等的分区，每个分区就是一个 “ 页框 ”，或称 “ 页帧 ”、“ 内存块 ”、“ 物理块 ”。每个页框有一个编号，即 “ 页框号 ”，或称 “ 内存块号 ”、“ 页帧号 ”、“ 物理块号 ” ，页框号从 0 开始。\n\n **页面** ：将用户 **进程** 的地址空间也分为与页框大小 **相等** 的一个个区域，称为 “ 页 ” 或 “ 页面 ”。每个页面也有一个编号，即 “ 页号 ”，页号也是从 0 开始。\n\n### 如何实现地址转换\n\n \n\n **例子：** \n\nCPU执行指令1，需要访问逻辑地址为80的内存单元，如何转化为物理地址?\n\n逻辑地址为80的内存单元，应该在 **1号页** ，该页在内存中的起始位置为450，逻辑地址为80的内存单元相对于该页的起始地址而言，“偏移量”应该是30。\n\n实际物理地址 = 450 + 30 = 480\n\n **如何计算:** \n\n页号 = 逻辑地址 / 页面长度（取除法的整数部分）\n\n页内偏移量 = 逻辑地址 % 页面长度（取除法的余数部分）\n\n页面在内存中的起始位置：操作系统需要用某种数据结构记录进程各个页面的起始位置。\n\n页号 = 80 / 50 = 1\n\n页内偏移量 = 80 % 50 = 30\n\n1 号页在内存中存放的起始位置 450\n\n **为了方便计算机计算页号、页内偏移量，页面大小一般设为2的整数幂！** \n\n \n\n### 逻辑地址结构\n\n \n\n逻辑地址结构包含两个部分：前一部分为页号，后一部分为页内偏移量w。在上图所示的例子中，地址长度为32位，其中0 ~ 11位为“ **页内偏移量** ”，或称“页内地址”;12~31位为“ **页号** ”。\n\n### 页表\n\n解决地址转换的第二步：计算页号对应 **页面在内存中的起始地址** \n\n为了能知道进程的每个页面在内存中存放的位置，操作系统要 **为每个进程建立一张页表** 。\n\n **例子** \n\n假设某系统物理内存大小为4GB，页面大小为4KB，则每个页表项至少应该为多少字节?\n\n4GB = 2^32B，4KB = 2^12B\n\n因此4GB的内存总共会被分为 2^32 / 2^12 = 2^20 个内存块，因此内存块号的范围应该是0 ~ 2^20 - 1 因此至少要20个二进制位才能表示这么多的内存块号，因此至少要3个字节才够 (每个字节8个二进制位，3个字节共24个二进制位)\n\n各页表项会 **按顺序连续** 地存放在内存中\n\n如果该页表在内存中存放的起始地址为X，则M号页对应的页表项一定是存放在内存地址为 X ＋ 3 * M 因此，页表中的**“页号”可以是“隐含”的**。只需要知道 **页表存放的起始地址** 和 **页表项长度** ，即可 **找到各个页号对应的页表项存放的位置** ！\n\n在本例中，一个页表项占3B，如果进程由n个页面，则该进程的页表总共会占 3 * n 个字节\n\n### 基本地址变换机构\n\n **大纲** \n\n \n\n用于 **实现** 逻辑地址到物理 **地址转换** （借助进程的页表）的一组 **硬件机构** \n\n \n\n **设页面大小为L，逻辑地址A到物理地址E的变换过程如下:** \n\n **页表长度** 指的是这个页表中总共有几个页表项，即总共有几个页； **页表项长度** 指的是每个页表项占多大的存储空间； **页面大小** 指的是一个页面占多大的存储空间\n\n在分页存储管理（页式管理）的系统中，只要确定了每个页面的大小，逻辑地址结构就确定了。\n\n因此，页式管理中地址是 **一维的** 。即， **只要给出一个逻辑地址** ，系统就可以自动地算出页号、页内偏移量两个部分，并不需要显式地告诉系统这个逻辑地址中，页内偏移量占多少位。\n\n理论上，页表项长度为3B即可表示内存块号的范围，但是，为了方便页表的查询，常常会让一个页表项占更多的字节，使得每个页面恰好可以装得下整数个页表项。\n\n**想更深入的理解操作系统，可以看看下面这个视频：**麻省理工6.s081课程****\n\n[](https://www.bilibili.com/video/BV1sUrWYXEJg/)\n\n### 具有快表的地址变换机构\n\n是基本地址变换机构的改进版本！\n\n **局部性原理？** \n\n上小节介绍的基本地址变换机构中，每次要访问一个逻辑地址，都需要查询内存中的页表。由于局部性原理，可能连续很 **多次查到的都是同一个页表项** 。既然如此，能否利用这个特性减少访问页表的次数呢?\n\n **什么是快表TLB？** \n\n快表又成为 **联想寄存器** （TLB），是一种访问速度比内存块很多的 **高速缓冲存储器** ，用来存放当前访问的若干页表项, 以加速地址变换的过程. 与此对应的，内存中的页表常称为 **慢表** 。\n\n \n\n **引入快表的地址变换过程？** \n\n由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。因为局部性原理，一般来说快表的 **命中率可以达到90%以上** 。\n\n **基本地址变换机构 VS 具有快表的地址变换机构** \n\n \n\n### 两级页表\n\n **大纲** \n\n \n\n **单级页表存在的问题？** \n\n1、假设某计算机系统按字节寻址，支持32位逻辑地址，采用分页存储管理，页面大小为4KB，页表项长度为4B。\n\n4KB = 2^12B，因此页内地址要用12位表示，剩余20位表示页号。\n\n因此，该系统中用户进程最多有2^20 页。相应的，一个进程的页表中，最多会有 2^20 个页表项，所以一个页表最大需要2^20 * 4B = 2 ^ 22B。一个页框（内存块）大小为 4B，所以需要2^22 / 2^12 （页面大小为4KB）= 2^10个页框存储该页表。而页表的存储是需要连续存储的，因为根据页号查询页表的方法：K号页对应的页表项的位置 = 页表起始地址 + K * 4B，所以这就 **要求页表的存储必须是连续的** 。当页表很大时，需要占用很 **多个连续的页框** 。\n\n回想一下，当初为什么使用页表，就是要将进程划分为一个个页面可以 **不用连续** 的存放在内存中，但是此时页表就需要1024个连续的页框，与当时的目标 **相悖** 。\n\n2、根据 **局部性原理** 可知，很多时候， **进程在一段时间内只需要访问某几个页面就可以正常运行** 了。因此 **没有必要让整个页表都常驻内存** 。\n\n **问题一** ：页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。（解决方法： **两级页表** ）\n\n **问题二** ：没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。\n\n **解决方法** \n\n可将长长的 **页表进行分组** ，使每个内存块刚好可以放入一个分组，再将各组 **离散** 地放到各个内存块中。\n\n例子，页面大小4KB，每个页表项4B，每个页面可存放1K个页表项，因此每1K个连续的页表项为一组，每组刚好占一个内存块，再讲各组离散地放到各个内存块中！\n\n另外， **为离散分配的页表再建立一张页表** ，称为 **页目录表** ，或称外层页表，或称顶层页表\n\n \n\n **实现地址转换** \n\n **例子** \n\n \n\n **细节** \n\n若采用 **多级页表机制** ，则 **各级页表的大小不能超过一个页面** 。\n\n两级页表的访存次数分析（假设没有快表机构）\n\n **例子** \n\n \n\n### 基本分段是存储管理\n\n### 大纲\n\n \n\n### 什么是分段\n\n **分段** ：进程的地址空间会按照自身的逻辑关系划分为若干个段, 每个段都有一个段名, **每段从0开始编址** 。\n\n **内存分配规则** ： **以段为单位** 进行分配，每个段在内存中占据 **连续** 空间，但各段之间可以 **不相邻** 。\n\n \n\n分段系统的逻辑地址结构由 **段号** （段名）和 **段内地址** （ **段内偏移量** 〉所组成。\n\n \n\n **段号的位数决定了每个进程最多可以分为几个段** \n\n **段内地址位数决定了每个段的最大长度是多少** \n\n### 什么是段表\n\n **段表** ：程序分多个段，各段离散地装入内存，为了保证程序能正常运行，就必须能从物理内存中找到各个逻辑段的存放位置。为此，需为每个进程建立一张 **段映射表** 。\n\n \n\n例如：某系统按字节寻址，采用分段存储管理，逻辑地址结构为（段号16位,段内地址16位），因此用 **16位即可表示最大段长** 。物理内存（即基址范围）大小为4GB（可用 **32位** 表示整个物理内存地址空间)。\n\n因此，可以让每个段表项占16+32=48位，即6B。\n\n **由于段表项长度相同，因此段号可以是隐含的，不占存储空间** 。\n\n若段表存放的起始地址为M，则K号段对应的段表项存放的地址为 M ＋ K * 6（即段号时隐含的！）\n\n### 如何实现地址转换\n\n \n\n### 分段分页管理对比\n\n **分段** 比分页 **更容易实现信息的共享和保护** 。（类似指针，二者短表项一致即可同时指向共享内存）\n\n不能被修改的代码称为 **纯代码** 或 **可重入代码** (不属于临界资源)，这样的代码是可以共享的.可修改的代码是不能共享的(比如，有一个代码段中有很多变量，各进程并发地同时访问可能造成数据不一致)\n\n **简单来说：** \n\n \n\n **访问一个逻辑地址需要几次访存?** \n\n### 段页式存储管理\n\n### 大纲\n\n \n\n### 分页分段管理方式优缺点\n\n分段管理中产生的 **外部碎片** 也可以用“ **紧凑** ”来解决，只是需要付出 **较大的时间代价** \n\n \n\n### 分页 + 分段 = 段页式管理\n\n将进程按逻辑模块 **分段** ， **再将各段分页** （如每个页面4KB)\n\n再将内存空间分为大小相同的内存块/页框/页帧/物理块\n\n进程前将各页面分别装入各内存块中\n\n \n\n### 段页式逻辑地址结构\n\n由 **段号** 、 **页号** 、页内地址（ **页内偏移量** ）组成！\n\n分段系统的端内地址拆分为：页号 + 页内偏移\n\n \n\n **\" 分段 \" 对用户是可见** 的，而将 **各段\"分页\"对用户是不可见的** ，系统会 **根据段内地址自动划分页号和段内偏移量** ，因此段页式管理的地址结构是 \" **二维** \" 的。\n\n### 段表页表\n\n每一个进程对应一个 **段表** ，每一个 **段** 又对应一个 **页表** ，因此一个进程可能对应 **多个** 页表。\n\n每个 **段** 对应一个 **段表项** ，每个段表项由 **段号** 、 **页表长度** 、 **页表存放块号** (页表起始地址）组成。\n\n **每个段表项长度相等，段号是隐含的。** \n\n每个 **页面** 对应一个 **页表项** ，每个页表项由 **页号** 、内存存放的 **内存块号** 组成。\n\n **每个页表项长度相等，页号是隐含的。** \n\n \n\n### 如何实现地址转换\n\n \n\n1、由逻辑地址得到段号、页号、页内偏移\n\n2、段号与段表寄存器的段长度比较，检查是否越界\n\n3、由段表始址, 段号找到对应段表项\n\n4、根据段表中记录的页表长度，检查页号是否越界\n\n5、由段表中的页表地址, 页号得到查询页表，找到相应页表项\n\n6、由页面存放的内存块号，页内偏移得到最终的物理地址\n\n7、访问目标单元\n\n需要三次访存，第一次查段表，第二次查页表，第三次访问目标单元。\n\n## 四、文件管理\n\n### 1、文件管理简介\n\n### 大纲\n\n \n\n### 文件的属性\n\n文件名、标识符、类型、位置、大小、创建时间、上次修改时间、文件所有者信息、保护信息\n\n### 文件的分类\n\n记录是一组相关数据项的集合\n\n### 操作系统应向上提供哪些功能\n\ncreate、delete、 **open、close** 、read、write 等系统调用功能！\n\n### 2、文件的逻辑结构\n\n **文件逻辑结构** \n\n **无结构文件（流式文件）** ：文件内部的数据是由一系列的二进制或字符流组成，如文本文件（.txt文件）\n\n **有结构文件（记录式文件）** ：由一组相似的记录文件组成，每条记录又由若干个数据项组成， **如数据库表** 。一般来说，每条记录有一个数据项作为关键字。根据各条记录的长度（占用的存储空间）是否相等，又可分为 **定长记录** 和 **可变长记录** 。\n\n **逻辑结构** ：指在用户看来，文件内部的数据应该是如何组织起来的。\n\n **物理结构** ：指的是在操作系统看来，文件的数据是如何存放在外存的。\n\n### 大纲\n\n \n\n### 顺序文件\n\n **顺序文件** ：文件中的记录一个接一个地顺序排列（逻辑上），记录可以是 **定长的或可变长** 的。各个记录在物理上可以 **顺序存储** （物理上连续）或 **链式存储** （物理上可能不连续）。\n\n \n\n **顺序文件** （顺序结构）的缺点是增加/删除一个记录比较困难（如果是串结构则相对简单）\n\n### 索引文件\n\n解决可变长记录的快速查找问题！\n\n **索引表** 本身是 **定长记录的顺序文件** 。因此可以快速找到第i个记录对应的索引项。\n\n可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字 **折半查找** 。\n\n每当要增加/删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。\n\n另外，可以用不同的数据项建立多个索引表。如:学生信息表中，可用关键字“学号”建立一张索引表。也可用“姓名”建立一张索引表。这样就可以根据“姓名”快速地检索文件了。\n\n### 顺序索引文件\n\n **索引文件的缺点** ：每个记录对应一个索引表项，因此索引表可能会很大。比如：文件的每个记录平均只占8B，而每个索引表项占32个字节，那么索引表都要比文件内容本身大4倍，这样对存储空间的利用率就太低了。\n\n **索引顺序文件** 是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是：并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。\n\n若一个顺序文件有10000个记录，则根据关键字检索文件，只能从头开始顺序查找（这里指的并不是定长贡录、顺序结构的顺序文件），平均须查找5000个记录。\n\n若采用索引顺序文件结构，可把10000个记录分为100 组，每组100个记录。则需要先顺序查找索引表找到分组（共100个分组，因此索引表长度为100，平均需要查50次），找到分组后，再在分组中顺序查找记录（每个分组100个记录，因此平均需要查50次）。可见，采用索引顺序文件结构后，平均查找次数减少为50+50= 100次。\n\n同理，若文件共有1000000个记录，则可分为1000个分组，每个分组1000个记录。根据关键字检索一个记录平均需要查找500+500 = 1000次。这个查找次数依然很多，如何解决呢?\n\n### 多级索引顺序文件\n\n为了进一步提高检索效率，可以为顺序文件建立多级索引表。\n\n **套娃即可！** 空间换时间！\n\n### 3、文件目录\n\n### 大纲\n\n \n\n### 文件控制块\n\n **FCB中包含** \n\n **对目录进行的操作** ：搜索、创建文件、删除文件、显示目录、 **修改目录** \n\n### 目录结构\n\n **单级目录结构** \n\n早期的操作系统并不支持多级目录，整个系统只建立一张目录表，每个文件占一个目录项。\n\n单级目录实现了 \" 按名存取 \"，但是不允许文件重名。\n\n单级目录不支持多用户操作系统。\n\n **两级目录结构** \n\n早期的多用户操作系统采用两级目录结构，分为 **主文件目录** （MFD，Master File Directory）和 **用户文件目录** （UFD，User File Directory）。\n\n **优点** ：两级目录允许不同用户的文件重名，也可以在目录上实现访问限制（检查此时登录的用户名是否匹配）。\n\n **缺点** ：缺乏灵活性，用户不能对自己的文件进行分类。\n\n **多级目录结构** \n\n又称 **树形目录结构** \n\n用户(或用户进程）要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串。各级目录之间用“/”隔开。从根目录出发的路径称为绝对路径。\n\n从当前目录出发的路径称为 **相对路径** 。\n\n系统根据绝对路径一层一层地找到下一级目录。刚开始从外存 **读入根目录的目录表** ；找到“照片”目录的存放位置后，从外存读入对应的目录表；再找到“2015-08”目录的存放位置，再从外存读入对应目录表；最后才找到文件“白拍.jpg”的存放位置。整个过程需要3次读磁盘I/O操作。\n\n相对路径可以减少磁盘 I/O 操作次数。\n\n **优点** ：树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。\n\n **缺点** ：树形结构不便于实现文件的共享。\n\n对此，提出了“ 无环图目录结构 ”。\n\n **无环图目录结构** \n\n在树形目录结构的基础上， **增加** 一些指向同一节点的有向边，使整个目录成为一个 **有向无环图** 。\n\n可以更方便地实现多个用户间的 **文件共享** 。\n\n可以用不同的文件名指向同一个文件，甚至可以指向同一个目录（共享同一目录下的所有内容）。\n\n需要为每个共享结点设置一个 **共享计数器** ，用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的FCB、并使共享计数器减1，并不会直接删除共享结点。减到0时，才能删除该节点！\n\n### 索引节点\n\n对FCB的改进！\n\n **由来** ：其实在查找各级目录的过程中只需要用到“文件名”这个信息，只有文件名匹配时，才需要读出文件的其他信息。因此可以考虑让目录表“瘦身”来提升效率。\n\n将除了文件名之外的文件描述信息都放到 **索引结点** 中。由于 **目录项长度减小** ，因此每个磁盘块可以存放更多各目录项，可以大大提升文件检索速度。\n\n当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“ 存放位置 ”即可找到文件。\n\n存放在外存中的索引结点称为“ **磁盘索引结点** ”，当索引结点放入内存后称为“ **内存索引结点** ”。\n\n相比之下内存索引结点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件等。\n\n### 4、文件的物理结构（非空闲块）\n\n **文件物理结构（文件）分配方式** \n\n即文件数据应该怎样存放在外存中。\n\n是对非空闲块的管理！\n\n### 文件块和磁盘块\n\n **磁盘块** \n\n类似于内存分页，磁盘中的存储单元也会被分为一个个 ” **块 / 磁盘块 / 物理块** “。\n\n很多操作系统中，磁盘块的大小与内存块、页面的大小相同。\n\n内存与磁盘之间的数据交换（即 读/写操作、磁盘I/O）都是以” **块** “ 为单位进行的。\n\n即每次读入一块，或每次写出一块\n\n **文件块** \n\n在内存管理中, 进程的逻辑地址空间被分为一个个的页面\n\n同样的, 在外存管理中, 为了方便对文件数据的管理, 文件的 **逻辑地址空间** 也被分为了一个个的 **文件块** \n\n于是文件的逻辑地址也可以表示为 **（逻辑块号, 块内地址）**的形式\n\n### 连续分配\n\n连续分配方式要求每个文件在磁盘上占有一组连续的块。\n\n用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB） …\n\n **物理块号 = 起始块号＋ 逻辑块号（就是偏移）** \n\n当然，还需要检查用户提供的逻辑块号是否合法（逻辑块号≥长度就不合法)\n\n操作系统可以直接算出逻辑块号对应的物理块号，因此连续分配支持 **顺序访问** 和直接访问( **随机访问** )\n\n **连续分配方式** 要求 **每个文件在磁盘上占有一组连续的块** 。\n\n读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长。\n\n \n\n **优点** ：连续分配的文件在顺序读/写时速度 **最快** 。\n\n **缺点** ：采用连续分配的文件 **不方便拓展** ；存储利用率低，会产生难以利用的 **磁盘碎片** 。( 类似外部碎片，可以采用 **紧凑** 的方法来处理碎片, 但是需要耗费很大的时间代价 )\n\n### 链接分配\n\n链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。\n\n### 隐式链接\n\n隐式链接：除文件的最后一个盘块之外，每个盘块中都存有 **指向** 下一个盘块的指针。文件目录包括文件 **第一块的指针** 和 **最后一块的指针** 。\n\n \n\n **实现文件的逻辑块号到物理块号的转变** \n\n用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项（FCB） …\n\n从目录项中找到起始块号（即0号块），将0号逻辑块读入内存，由此知道1号逻辑块存放的物理块号，于是读入1号逻辑块，再找到2号逻辑块的存放位置…\n\n以此类推。\n\n因此，读入i号逻辑块，总共需要i+1次磁盘I/O。\n\n **优点** ：很方便文件拓展 （挂到文件链尾即可，可通过结束块号找到尾）；所有的空闲磁盘块都可以被利用， **不会有碎片问题** ，外存利用率高。\n\n **缺点** ：只支持顺序访问， **不支持随机访问** ，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。\n\n### 显式链接\n\n显示链接：把用于链接文件各物理块的指针显式地存放在一张表中。即 **文件分配表** （FAT，File Allocation Table）。\n\n \n\n **实现文件的逻辑块号到物理块号的转变** \n\n **结论：** \n\n **优点** ：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。\n\n **缺点** ：文件分配表的需要占用一定的存储空间。\n\n### 索引分配\n\n### 简介\n\n索引分配允许文件离散地分配在各个磁盘块中，系统会为 **每个文件建立一张索引表** ，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表一―建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为 **索引块** 。文件数据存放的磁盘块称为 **数据块** 。\n\n \n\n假设某个新创建的文件“aaa”的数据依次存放在磁盘块2 -> 5 -> 13 -> 9 。7号磁盘块作为“aaa”的索引块,索引块中保存了索引表的内容。\n\n注：在显式链接的链式分配方式中，文件分配表FAT是一个磁盘对应一张。而索引分配方式中，索引表是一个文件对应一张。\n\n可以用固定的长度表示物理块号（如：假设磁盘总容量为1TB=2^40B，磁盘块大小为1KB，则共有 2^30 个磁盘块，则可用4B表示磁盘块号)，因此，索引表中的“逻辑块号”可以是隐含的。\n\n **实现文件的逻辑块号到物理块号的转变？** \n\n可见，索引分配方式可以 **支持随机访问** 。 **文件拓展也很容易实现** （只需要给文件分配一个空闲块，并增加一个索引表项即可）。\n\n### 问题解决\n\n若每个磁盘块1KB，一个索引表项4B，则一个磁盘块只能存放256个索引项。\n\n如果一个文件的大小超过了256块，那么 **一个磁盘块是装不下文件的整张索引表** 的，如何解决这个问题?\n\n### 链接方案\n\n如果索引表太大，一个索引块装不下，那么可以将 **多个索引块链接起来存放** 。\n\n \n\n### 多层索引\n\n建立多层索引（ **原理类似于多级页表** ）。使 **第一层** 索引块指向 **第二层** 的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。\n\n \n\n### 混合索引\n\n解决多层索引对于小文件仍需要多层处理的问题！\n\n多种索引分配方式的结合。\n\n例如，一个文件的顶级索引表中，既包含 **直接地址索引** (直接指向数据块），又包含一级间接索引（指向 **单层索引表** )、还包含两级间接索引（指向 **两层索引表** )。\n\n \n\n### 小总结\n\n **链接方案** ：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。\n\n **多层索引** ：建立多层索引（ **原理类似于多级页表** )。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K +1次读磁盘操作。\n\n **混合索引** ：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含 **直接地址索引** （直接指向数据块），又包含 **一级间接索引** （指向单层索引表)、还包含 **两级间接索引** （指向两层索引表)。\n\n **重点** ：\n\n \n\n### 5、文件存储空间管理（空闲块）\n\n **对空闲块的管理！** \n\n### 大纲\n\n \n\n### 存储空间划分与初始化\n\n **文件卷** ：将物理磁盘划分为一个个文件卷（逻辑卷，逻辑盘）例如：windows CDE盘\n\n### 空闲表法\n\n **适用于连续分配方式。** \n\n \n\n### 空闲链表法\n\n **空闲链表法** \n\n **空闲盘块链** \n\n适用于离散分配的物理结构。\n\n \n\n **空闲盘区链** \n\n以盘区为单位组成一条空闲链\n\n离散分配、连续分配都使用。\n\n为一个文件分配多个盘块时效率更高\n\n \n\n### 位示图法\n\n **位示图** ：每个二进制位对应一个盘块。在本例中，“O”代表盘块空闲，“1”代表盘块已分配。\n\n \n\n **如何分配** \n\n若文件需要K个块\n\n **如何回收** \n\n### 成组链表法\n\n **空闲表法、空闲链表法不适用于大型文件系统** ，因为空闲表或空闲链表可能过大。\n\n **UNIX** 系统中采用了成组链接法对磁盘空闲块进行管理。\n\n **文件卷的目录区** 中专门用一个磁盘块作为 “ **超级块** ”，当系统启动时需要将超级块读入内存。\n\n并且要保证内存与外存中的 “ **超级块** ” 数据一致。\n\n \n\n### 6、文件基本操作\n\n### 创建文件\n\n进行 \" create 系统调用 \"\n\n需要提供的参数：\n\n操作系统在处理create系统调用时，主要做了两件事：\n\n### 删除文件\n\n进行 \" delete 系统调用 \"\n\n需要提供的参数：\n\n操作系统在处理delete系统调用时，主要做了几件事：\n\n### 打开文件\n\n进行 ” open 系统调用 “\n\n需要提供的要参数：\n\n操作系统在处理delete系统调用时，主要做了几件事：\n\n **打开文件表** \n\n每个进程有自己的打开文件表，系统中也有一张总的打开文件表\n\n### 关闭文件\n\n进行 ” close 系统调用 “\n\n### 读文件\n\n进行 ” read 系统调用 “\n\n需要提供的参数\n\n操作系统在处理read系统调用时，会从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中。\n\n### 写文件\n\n进行 ” write 系统调用 “\n\n需要提供的参数\n\n### 7、文件共享&文件保护\n\n### 文件共享\n\n### 基于索引结点的共享方式（硬链接）\n\n索引结点：是一种文件目录瘦身策略。由于检索文件时只需用到文件名，因此可以将除了文件名之外的其他信息放到索引结点中。这样目录项就只需要包含文件名、索引结点指针。\n\n索引结点中设置一个链接计数变量count，用于表示链接到本索引结点上的用户目录项数。\n\n若 count =2，说明此时有两个用户目录项链接到该索引结点上，或者说是有两个用户在共享此文件。\n\n若某个用户决定“ 删除 ”该文件，则只是要把用户目录中与该文件对应的目录项删除，且索引结点的 count 值减1。\n\n若 count > 0，说明还有别的用户要使用该文件，暂时不能把文件数据删除，否则会导致指针悬空。\n\n当 count = 0 时系统负责删除文件。\n\n### 基于符号链的共享方式（软链接）\n\n当 User3 访问 “ ccc ” 时，操作系统判断文件 “ ccc ” 属于 Link 类型文件，于是会根据其中记录的层层查找目录，最终找到 User1的目录表中的 “ aaa ” 表项，于是就找到了文件1的索引结点。（类似Windows快捷方式）\n\n速度慢于硬链接！\n\n### 文件保护\n\n### 口令保护\n\n为文件设置一个 “ 口令 ” （如: abc112233），用户请求访问该文件时必须提供 “ 口令 ”。\n\n口令一般存放在文件对应的 FCB 或索引结点中。\n\n用户访问文件前需要先输入“口令”，操作系统会将用户提供的口令与FCB中存储的口令进行对比。\n\n如果正确，则允许该用户访问文件。\n\n优点：保存口令的空间开销不多，验证口令的时间开销也很小。\n\n缺点：正确的 “口令” 存放在系统内部，不够安全。\n\n### 加密保护\n\n使用某个 “ 密码 ” 对文件进行加密，在访问文件时需要提供正确的 “ 密码 ” 才能对文件进行正确的解密。\n\n优点：保密性强，不需要在系统中存储“密码”\n\n缺点：编码/译码，或者说加密/解密要花费一定时间。\n\n### 访问控制\n\n在每个文件的 FCB （或索引结点）中增加一个访问控制列表（Access-Control List, ACL)，该表中记录了各个用户可以对该文件执行哪些操作。\n\n \n\n### 8、文件系统层次结构\n\n \n\n从上到下依次是：文件基本操作，文件目录，文件保护，文件逻辑地址，文件物理地址，文件存储空间管理，磁盘设备管理！\n\n用一个例子来辅助记忆文件系统的层次结构：\n\n假设某用户请求删除文件“D:/工作目录/学生信息…xlsx”的最后100条记录。\n\n## 五、磁盘管理\n\n### 1、磁盘结构\n\n### 磁盘&磁道&扇区\n\n **磁盘** ：表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据。\n\n **磁道** : 磁盘的盘面被划分成一个个磁道， 一个圈就是一个磁道。\n\n **扇区** : 每一个磁道被划分成一个个扇区，每个扇区就是一个个 \" 数据块 \"， **各个扇区存放的数据量相同。** \n\n最内侧磁道上的扇区面积最小, 因此数据密度最大\n\n \n\n### 磁盘如何读写\n\n需要把 “ 磁头 ” 移动到想要读/写的扇区所在的磁道。\n\n磁盘会转起来，让目标扇区从磁头下面划过，才能完成对扇区的读/写操作。\n\n### 盘面&柱面\n\n \n\n### 磁盘物理地址\n\n可用（ **柱面号，盘面号，扇区号** ）来定位任意一个“磁盘块”。\"在“文件的物理结构”小节中，我们经常提到文件数据存放在外存中的几号块，这个块号就可以转换成（柱面号，盘面号，扇区号)的地址形式。\n\n可根据该地址读取一个“块”\n\n### 磁盘分类\n\n \n\n磁头可以移动的称为 **活动头磁盘** 。磁臂可以来回伸缩来带动磁头定位磁道。\n\n磁头不可移动的称为 **固定头磁盘** 。这种磁盘中每个磁道有一个磁头。\n\n盘片可以更换的称为 **可换盘磁盘** 。\n\n盘片不可以更换的称为 **固定盘磁盘** 。\n\n### 2、磁盘调度算法\n\n### 寻道时间&延迟时间&传输时间\n\n **寻找时间(寻道时间)Ts** ：在读/写数据前，将磁头移动到指定磁道所花的时间。\n\n **延退睦潮Tr** ：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。设磁盘转速为r(单位:转/秒，或转/分），则平均所需的延迟时间Tr =(1/2) * (1/r) = 1/2r\n\n **传输时间Tt** ：从磁盘读出或向磁盘写入数据所经历的时间，假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节数为N。则:传输时间Tt=(1/r) * (b/N) = b/(rN)\n\n **总的平均存取时间T** = Ts + 1/2r + b/(rN)\n\n延迟时间和传输时间都与磁盘转速相关，且为线性相关。而转速是硬件的固有属性，因此操作系统也无法优化延迟时间和传输时间！\n\n **但是操作系统的磁盘调度算法会直接影响寻道时间** \n\n### 先来先服务FCFS\n\n根据进程请求访问磁盘的先后顺序进行调度。\n\n优点：公平；如果请求访问的磁道比较集中的话，算法性能还算过得去。\n\n缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS在性能上很差，寻道时间长。\n\n \n\n### 最短寻道时间优先SSTF\n\nSSTF 算法会优先处理的磁道是与当前磁头最近的磁道。可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。(其实就是贪心算法的思想，只是选择眼前最优，但是总体未必最优）\n\n优点：性能较好，平均寻道时间短。\n\n缺点：可能产生 “ 饥饿 ” 现象。\n\n产生饥饿的原因在于：磁头在一个小区域内来回来去地移动。\n\n### 扫描算法SCAN\n\n为了防止饥饿问题，可以规定，只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动。\n\n这就是扫描算法（SCAN）的思想。由于磁头移动的方式很像电梯，因此也叫 **电梯算法** 。\n\n优点：性能较好，平均寻道时间较短，不会产生饥饿现象\n\n缺点：\n\n### LOOK 调度算法\n\n相对于扫描算法，如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向。\n\n边移动边观察，因此叫 LOOK。\n\n优点：比起SCAN算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短。\n\n### 循环扫描算法C-SCAN\n\nSCAN算法对于各个位置磁道的响应频率不平均，而C-SCAN算法就是为了解决这个问题。\n\n规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。\n\n优点：比起SCAN来，对于各个位置磁道的响应频率很平均。\n\n缺点：只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了;并且，磁头返回时其实只需要返回到18号磁道即可，不需要返回到最边缘的磁道。另外，比起SCAN算法来，平均寻道时间更长。\n\n### C-LOOK 调度算法\n\nC-SCAN 算法的主要缺点是只有到达最边上的磁道时才能改变磁头移动方向，并且磁头返回时不一定需要返回到最边缘的磁道上。\n\nC-LOOK算法就是为了解决这个问题。如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。\n\n优点：比起C-SCAN算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短。\n\n### 3、减少磁盘延迟方法\n\n磁头读入一个扇区数据后需要一小段时间处理，如果逻辑上相邻的扇区在物理上也相邻，\n\n则读入几个连续的逻辑扇区，可能需要很长的“延迟时间”（因为扇片在不停的旋转，写一次转到是才可能继续去读）\n\n### 交替编号\n\n若采用交替编号的策略，即让逻辑上相邻的扇区在物理上有一定的间隔，可以使读取连续的逻辑扇区所需要的延迟时间更小。\n\n### 磁盘地址结构的设计\n\n磁盘的物理地址是 （柱面号、盘面号、扇区号）\n\n为什么不是 （盘面号、柱面号、扇区号）？\n\n在读取地址连续的磁盘块时，可以减少磁头移动消耗的时间。\n\n### 错位命名\n\n让相邻盘面的扇区编号 “错位”。\n\n即将多个盘面的磁头指向的扇区编号并不一致即可！\n\n若指向的扇区编号一致：则0号扇面读完要读1号扇面时，1号扇面的磁头仍需要时间激活，因此就会将需要读的扇区错过，进行转动第二圈才能读到\n\n若指向的扇区编号不一致：1号扇面磁头开始读时，由于编号不一致，即此时磁头的指向并不是要读的数据，完全有时间激活磁头，激活完毕顺便将需要读的扇区读了，转一圈即可完成！减少延迟时间！\n\n \n\n### 4、磁盘的管理\n\n### 磁盘初始化\n\n### 引导块\n\n计算机开机时需要进行一系列初始化的工作，\n\n这些初始化工作是通过执行初始化程序 (自举程序) 完成的。\n\n初始化程序 ( 自举程序 ) 如果直接放在ROM（只读存储器）中。ROM中的数据在出厂时就写入了。并且以后不能再修改，会很不方便。\n\n **解决方法：** \n\n### 坏块管理\n\n坏了、无法正常使用的扇区就是“坏块”。\n\n这属于硬件故障，操作系统是无法修复的。应该将坏块标记出来，以免错误地使用到它。\n\n对于简单的磁盘，可以在逻辑格式化时（建立文件系统时）对整个磁盘进行坏块检查，\n\n标明哪些扇区是坏扇区，比如：在FAT表上标明。（在这种方式中， **坏块对操作系统不透明** )\n\n对于复杂的磁盘，磁盘控制器（磁盘设备内部的一个硬件部件）会维护一个 **坏块链表** 。\n\n在磁盘出厂前进行低级格式化（物理格式化）时就将坏块链进行初始化。\n\n会保留一些“ **备用扇区** ”，用于替换坏块。\n\n这种方案称为 **扇区备用** 。且这种处理方式中， **坏块对操作系统透明** 。\n\n## 六、设备管理\n\n### 1、IO设备概念&分类\n\n### 概念\n\n“ I/O ” 就是“ 输入/输出 ”（lnput/Output）\n\nI/O 设备就是可以将数据输入到计算机，或者可以接收计算机输出数据的外部设备，属于计算机中的硬件部件。\n\nUNIX系统 **将外部设备抽象为一种特殊的文件** ， 用户可以使用与文件操作相同的方式对外部设备进行操作。\n\nWrite：向外部设备写出数据。\n\nRead：向外部设备读入数据。\n\n### 分类\n\n **按使用特性** \n\n **按传输速率** \n\n **按信息交换的单位** \n\n### 2、IO控制器\n\n用于实现对IO设备的控制！\n\n### 机械部件 vs 电子部件\n\nIO设备有机械部件和电子部件组成！\n\nl/O 设备的 **机械部件** 主要用来执行具体 l/O 操作。\n\n如我们看得见摸得着的鼠标/键盘的按钮；显示器的LED屏；移动硬盘的磁臂、磁盘盘面。\n\nl/O 设备的 **电子部件** 通常是一块插入主板扩充槽的印刷电路板。\n\nCPU 无法直接控制 I/O 设备的机械部件，因此 I/O 设备还要有一个电子部件作为 CPU 和 I/O 设备机械部分之间的 “中介”, 用于实现CPU对设备的控制。\n\n **这个电子部件就是 I/O 控制器，又称设备控制器。** \n\nCPU可控制 I/O 控制器，又由 I/O 控制器来控制设备的机械部件。\n\n### I/O 控制器的功能\n\n### I/O 控制器的组成\n\n \n\n **值得注意的小细节：** \n\n **内存印像I/O VS 寄存器独立编址** \n\n \n\n### 3、IO控制方式\n\n即用什么样的方式来控制 I/O 设备的数据读/写\n\n### 程序直接控制方式\n\n通过 **轮询** 实现，以读操作为例。\n\n \n\n数据传送的单位：每次读/写一个字。\n\n **CPU千预的频率** \n\n很频繁，I/O操作开始之前、完成之后需要CPU介入，并且在等待l/O完成的过程中CPU需要不断地轮询检查。\n\n **数据的流向：** \n\n每个字的读/写都需要CPU的帮助。\n\n **优点** ：实现简单。在读/写指令之后，加上实现循环检查的一系列指令即可。（因此才称为“程序直接控制方式”）\n\n **缺点** ：CPU 和 I/O 设备只能I/O串行工作， **CPU 需要一直轮询检查** ，长期处于\"忙等\"状态，CPU 利用率低。\n\n### 中断驱动方式\n\n引入 **中断机制** 。\n\n由于 I/O 设备速度很慢，因此在 CPU 发出读/写命令后，可将等待 I/O 的进程 **阻塞** ，先切换到别的进程执行。当 I/O 完成后，控制器会向 CPU 发出一个 **中断信号** ，CPU检测到中断信号后，会 **保存** 当前进程的运行环境信息，转去执行中断处理程序 **处理该中断** 。\n\n处理中断的过程中，CPU从 I/O 控制器读一个字的数据传送到 CPU 寄存器，再写入主存。接着，CPU **恢复** 等待 I/O 的进程（或其他进程）的运行环境，然后继续执行。\n\n \n\n **注意：** \n\n **CPU干预的频率：** \n\n每次 I/O 操作开始之前、完成之后需要 CPU 介入。\n\n等待 I/O 完成的过程中 CPU 可以切换到别的进程执行。\n\n数据传送的单位：每次读/写一个字。\n\n **数据的流向：** \n\n **优点** ：与 “ 程序直接控制方式 ” 相比，在“中断驱动方式”中，I/O 控制器会通过中断信号主动报告I/O 已完成，CPU不再需要不停地轮询。CPU 和 I/O 设备可并行工作，CPU利用率得到明显提升。\n\n **缺点** ：每个字在 I/O 设备与内存之间的传输，都需要经过 CPU。而频繁的中断处理会消耗较多的CPU时间。\n\n### DMA方式\n\n **DMA方式** （Direct Memory Access， **直接存储器存取** ）。\n\n主要用于块设备的 I/O 控制，相对于 “中断驱动方式 ” 有这样几个改进：\n\n \n\n **DR (Data Register，数据寄存器)** ：暂存从设备到内存，或从内存到设备的数据。\n\n **MAR (Memory Address Register，内存地址寄存器)** ：在输入时，MAR表示数据应放到内存中的什么位置；输出时MAR表示要输出的数据放在内存中的什么位置。\n\n **DC(Data Counter，数据计数器)** ：表示剩余要读/写的字节数。\n\n **CR (Command Register，命令/状态寄存器)** ：用于存放 CPU 发来的 I/O 命令，或设备的状态信息。\n\n **CPU干预的频率** ：仅在传送一个或多个数据块的开始和结束时，才需要CPU干预。\n\n **数据传送的单位** ：每次读/写一个或多个块\n\n每次读写的只能是连续的多个块，且这些块读入内存后在内存中也必须是连续的\n\n **数据的流向：** \n\n **优点** ：数据传输以“块”为单位， **CPU 介入频率进一步降低** 。数据的传输不再需要先经过 CPU 再写入内存，数据传输效率进一步增加。CPU 和 I/O 设备的并行性得到提升。\n\n **缺点** ：CPU 每发出一条 I/O 指令，只能读/写一个或多个连续的数据块。\n\n如果要读/写多个离散存储的数据块，或者要将数据分别写到不同的内存区域时，CPU要分别发出多条 I/O 指令，进行 **多次中断处理** 才能完成。\n\n### 通道控制方式\n\n **通道** ：一种 **硬件** ，可以理解为是 “ 弱鸡版的 CPU ”。通常可以识别并执行一系列的 **通道指令** 。\n\n与 CPU 相比，通道可以执行的指令很单一，并且通道程序是放在主机内存中的，也就是说 **通道与CPU 共享内存** 。\n\n \n\n **CPU 干预的频率** ： **极低** ，通道会根据 CPU 的指示执行相应的通道程序，只有完成一组数据块的读/写后才需要发出中断信号，请求 CPU 干预。\n\n **数据传送的单位** ：每次读/写一组数据块。\n\n **数据的流向〈在通道的控制下进行)** \n\n **优点** ：CPU、通道、I/O 设备可并行工作，资源利用率很高。\n\n **缺点** ：实现复杂，需要专门的通道硬件支持。\n\n### 小总结\n\n \n\n### 4、IO软件层次结构\n\n \n\n **用户层软件** ：实现与用户交互的接口，向上提供方便易用的库函数。\n\n **设备独立性软件** ：\n\n **设备驱动程序** ：主要负责对硬件设备的具体控制，将上层发出的一系列命令（如read/write）转化成特定设备“能听得懂”的一系列操作。包括设置设备寄存器，检查设备状态等\n\n **中断处理程序** ：进行中断处理。当I/O任务完成时，I/O控制器会发送一个中断信号，系统会根据中断信号类型找到相应的中断处理程序并执行。中断处理程序的处理流程如下:\n\n \n\n **硬件** ：执行 I/O 操作，有机械部分、电子部分组成。不同的I/O设备有不同的硬件特性，具体细节只有设备的厂家才知道。因此厂家需要根据设备的硬件特性设计并提供相应的驱动程序。\n\n **操作系统系统可以采用两种方式管理逻辑设备表（LUT) :** \n\n### 5、IO核心子系统\n\nI/O 核心子系统要实现的功能其实就是中间三层要实现的功能。\n\n **I/O调度、设备保护、假脱机技术(SPOOLing技术）、设备分配与回收、缓冲区管理（即缓冲与高速缓存)** \n\n \n\n### I/O调度&设备保护\n\n **I/O 调度** ：用某种算法确定一个好的顺序来处理各个 I/O 请求。\n\n如：磁盘调度（先来先服务算法、最短寻道优先算法、SCAN算法、C-SCAN算法、LOOK算法、C-LOOK算法）。当多个磁盘I/O请求到来时，用某种调度算法确定满足l/O请求的顺序。\n\n同理，打印机等设备也可以用先来先服务算法、优先级算法、短作业优先等算法来确定I/O调度顺序。\n\n **设备保护：** \n\n操作系统需要实现文件保护功能，不同的用户对各个文件有不同的访问权限。\n\n在 UNIX 系统中， **设备被看做是一种特殊的文件** ， **每个设备也会有对应的FCB。** \n\n当用户请求访问某个设备时，系统根据FCB中记录的信息来判断该用户是否有相应的访问权限，以此实现“设备保护”的功能。（参考 文件保护 小结）\n\n### 假脱机技术 SPOOLing\n\n### 脱机技术\n\n手工操作阶段：主机直接从I/O设备获得数据，由于设备速度慢，主机速度很快。 **人机速度矛盾明显** ，主机要浪费很多时间来等待设备\n\n **批处理阶段** 引入了脱机输入/输出技术（用 **磁带** 完成)\n\n **引入脱机技术后** ，缓解了CPU与慢速I/O设备的速度矛盾。另一方面，即使CPU在忙碌，也可以提前将数据输入到磁带;即使慢速的输出设备正在忙碌，也可以提前将数据输出到磁带。\n\n **脱机** ：脱离主机的控制进行输入输出操作！\n\n \n\n### 假脱机技术\n\n“假脱机技术”，又称“SPOOLing 技术”，用 **软件** 的方式 **模拟脱机** 技术。SPOOLing 系统的组成如下：\n\n \n\n要实现SPOOLing 技术，必须要有 **多道程序技术的支持** 。系统会建立“输入进程”和“输出进程”。\n\n### 共享打印机器原理\n\n **独占式设备** ：只允许各个进程串行使用的设备。一段时间内只能满足一个进程的请求。\n\n **共享设备** ：允许多个进程“同时”使用的设备（宏观上同时使用，微观上可能是交替使用）。可以同时满足多个进程的使用请求。\n\n打印机是一种 \" 独占式设备 \"，但是可以用SPOOLing技术改造成 \" 共享设备 \"。\n\n独占式设备的例子：若进程1正在使用打印机，则进程2请求使用打印机时必然阻塞等待\n\n \n\n当多个用户进程提出输出打印的请求时，系统会答应它们的请求，但是并不是真正把打印机分配给他们而是由假脱机管理进程为每个进程做两件事：\n\n当打印机空闲时，输出进程会从文件队列的队头取出一张打印请求表，并根据表中的要求将要打印的数据从输出井传送到输出缓冲区，再输出到打印机进行打印。用这种方式可依次处理完全部的打印任务\n\n虽然系统中只有一个台打印机，但每个进程提出打印请求时，系统都会为在输出井中为其分配一个存储区（相当于分配了一个逻辑设备），使每个用户进程都觉得自己在独占一台打印机，从而实现对打印机的共享。\n\n### 设备的分配与回收\n\n### 大纲\n\n \n\n### 设备分配要考虑因素\n\n设备的固有属性可分为三种：独占设备、共享设备、虚拟设备。\n\n设备分配算法：\n\n从进程运行的安全性上考虑，设备分配有两种方式：\n\n **1、安全分配方式：** 为进程分配一个设备后就将进程阻塞，本次 I/O 完成后才将进程唤醒。\n\n一个时段内每个进程只能使用一个设备\n\n优点：破坏了 “ 请求和保持 ” 条件，不会死锁。\n\n缺点：对于一个进程来说，CPU 和 I/O 设备只能串行工作。\n\n **2、不安全分配方式** ：进程发出 I/O 请求后，系统为其分配 I/O 设备，进程可继续执行，之后还可以发出新的 I/O 请求。只有某个 I/O 请求得不到满足时才将进程阻塞。\n\n一个进程可以同时使用多个设备\n\n优点：进程的计算任务和 I/O 任务可以并行处理，使进程迅速推进。\n\n缺点：有可能发生死锁（死锁避免、死锁的检测和解除)。\n\n### 静态分配&动态分配\n\n静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源。破坏了“请求和保持”条件，不会发生死锁\n\n动态分配：进程运行过程中动态申请设备资源\n\n### 设备分配管理数据结构\n\n **设备、控制器、通道之间的关系** \n\n一个通道可控制多个设备控制器，每个设备控制器可控制多个设备。\n\n \n\n **设备控制表（DCT）** \n\n系统为每个设备配置一张DCT，用于记录设备情况。\n\n \n\n **控制器控制表（COCT）** \n\n每个设备控制器都会对应一张COCT。操作系统根据COCT的信息对控制器进行操作和管理。\n\n \n\n **通道控制表（CHCT）** \n\n通道控制表（CHCT):每个通道都会对应一张CHCT。操作系统根据CHCT的信息对通道进行操作和管理。\n\n \n\n **系统设备表（SDT）** \n\n记录了系统中全部设备的情况，每个设备对应一个表目。\n\n \n\n### 设备分配步骤\n\n **缺点：** \n\n### 设备分配步骤改进方法\n\n建立逻辑设备名与物理设备名的 **映射** 机制，用户编程时只需提供逻辑设备名。\n\n某用户进程第一次使用设备时使用逻辑设备名向操作系统发出请求，操作系统根据用户进程指定的设备类型（逻辑设备名)查找系统设备表，找到一个空闲设备分配给进程，并在LUT中增加相应表项。\n\n如果之后用户进程再次通过相同的逻辑设备名请求使用设备，则操作系统通过LUT表即可知道用户进程实际要使用的是哪个物理设备了，并且也能知道该设备的驱动程序入口地址。\n\n **逻辑设备表的设置问题：** \n\n整个系统只有一张LUT：各用户所用的逻辑设备名不允许重复，适用于单用户操作系统\n\n每个用户一张LUT：不同用户的逻辑设备名可重复，适用于多用户操作系统\n\n### 缓冲区管理\n\n### 大纲\n\n \n\n### 什么是缓冲区\n\n缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可以利用内存作为缓冲区。\n\n使用 **硬件作为缓冲区** 的成本较高，容量较小， 一般仅用在对速度要求非常高的场合。\n\n比如联想寄存器 ( 快表 ) 就是硬件作为缓冲区。\n\n一般情况下， 更多的是利用 **内存作为缓冲区** 。\n\n **缓冲区的作用：** \n\n### 单缓冲\n\n假设某用户进程请求某种块设备读入若干块的数据。若采用 **单缓冲** 的策略，操作系统会 **在主存中为其分配一个缓冲区** （若题目中没有特别说明，一个缓冲区的大小就是一个块）。\n\n当缓冲区数据 **非空** 时，不能往缓冲区冲入数据，只能从缓冲区把数据 **传出** ；\n\n当缓冲区为 **空** 时，可以往缓冲区冲入数据，但必须把缓冲区 **充满** 以后，才能从缓冲区把数据传出。\n\n \n\n \n\n### 双缓冲\n\n假设某用户进程请求某种块设备读入若干块的数据。若采用 **双缓冲** 的策略，操作系统会 **在主存中为其分配两个缓冲区** （若题目中没有特别说明，一个缓冲区的大小就是一个块)。\n\n \n\n \n\n结论：采用双缓冲策略，处理一个数据块的平均耗时为Max (T, C + M)\n\n注：管道通信中的“管道”其实就是缓冲区。要实现数据的双向传输，必须设置两个管道\n\n### 循环缓冲\n\n将多个 **大小相等** 的缓冲区链接成一个 **循环队列** 。\n\n注：以下图示中，橙色表示已充满数据的缓冲区，绿色表示空缓冲区。\n\n \n\n### 缓冲池\n\n缓冲池由系统中共用的缓冲区组成。\n\n这些缓冲区按使用状况可以分为：\n\n根据一个缓冲区在实际运算中扮演的功能不同，又设置了四种工作缓冲区：\n\n \n\n
\n\n[https://zhuanlan.zhihu.com/p/1893666811733578246](https://zhuanlan.zhihu.com/p/1893666811733578246)
\n -->