操作系统是一组控制和管理计算机软硬件资源、合理地对各类作业进行调度以及方便用户使用的程序集合。
操作系统是位于硬件层之上，所有其它系统软件层之下的一个系统软件，使得管理系统中的各种软件和硬件资源得以充分利用，方便用户使用计算机系统。
在内存中仅存一道作业区运行，运行结束 或出错，才自动调整另一道作业运行
优点：减少人工操作，解决了作业的自动接续
缺点：平均周转时间长，没有交互能力
在内存中存放多道作业运行，运行结束或出错，自动调度内存中的另一道作业运行
优点：提高了CPU的利用率，提高内存和I/O设备利用率，增加系统吞吐率
缺点：平均周转时间长，没有交互能力
产生原因：用户需要人机交互、共享主机，便于用户上机
实现方法：简单分时系统，前后台分时系统，多道分时系统
计算机及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时设备和实时任务协调一致的运行
主要是对处理机的分配和运行进行管理
主要是对多道程序的运行提供良好的环境
主要是完成用户的I/O请求
主要是希望用户能方便、安全地使用各种信息资源
主要是方便用户使用计算机
应用级并发是指若干应用程序的并发执行。
系统级并发是指操作系统自身软件的并发执行。
引入进程的目的是为了使程序正确地并发执行
特征：
1. 结构特征
2. 动态性（基本特征）（程序是静态的）
3. 并发性
4. 独立性
5. 异步性
定义：
进程是进程实体的运行过程，它是系统进行资源分配和调度的一个独立单位。
为使程序（含数据）能独立运行，应为之配置一个专门的数据结构即进程控制块（PCB）
由程序段、相关的数据段和PCB三部分便构成了进程实体
创建进程 ，实质上是创建进程实体中的PCB；撤消进程 ，实质上是撤消进程的PCB
就绪 - 运行：进程调度
运行 - 就绪：高优先级任务抢占，时间片用完
运行 - 阻塞：I/O请求，等待资源/事件
阻塞 - 就绪：I/O完成，得到资源/触发事件
阻塞 - 挂起：终端用户请求，父进程请求，负荷调节需要，操作系统需要
挂起 - 就绪：**原语
特殊状态:
静止就绪，静止阻塞（上述的挂起）。
活动就绪/执行挂起得到静止就绪，静止就绪通过**原语得到活动就绪。
静止阻塞通过**原语得到活动阻塞，静止阻塞通过释放得到静止就绪。
状态转换
为使程序（含数据）能独立运行，应为之配置一个专门的数据结构即进程控制块（PCB）
PCB是进程存在的唯一标志
通常包含下列信息：
1. 进程标识符：内部标识符，外部标识符
2. 处理机状态：通用寄存器、PC、PSW、SP
3. 进程调度和控制信息
PCB的常用组织形式：线性方式、链接方式和索引方式。
类型：
1. 整型信号量
2. 记录型信号量
3. AND型信号量（要么全部分配到进程，要么一个也不分配）
4. 信号量集（在每次分配时，采用信号量集来控制，可以分配多个单位的资源）
应用：
1. 用于实现前趋关系
2. 用于实现互斥
管程是由一组局部的变量对局部变量进行操作的一组过程以及对局部变量进行初始化的语句序列构成的一个软件模块，它可用来实现进程同步。
常用的高级进程通信机制：
1. 共享存储器系统
（基于共享数据结构/共享存储区）
2. 消息传递系统
直接通信方式：对称寻址方式，非对称寻址方式
间接通信方式：信箱，消息缓冲队列通信机制
3. 管道通信
4. 客户机–服务器系统
套接字，远程过程调用和远程方法调用
进程的两个特点：资源所有权，调度/执行。调度和分派的部分通常称为线程或轻便进程，而资源所有权的部分通常称为进程。
属性：
1. 轻型实体
2. 独立调度和分派的基本单位
3. 可并发执行
4. 共享进程资源
多线程OS中的进程属性：(1) 作为系统资源分配的单位。 (2) 可包括多个线程。 (3) 进程不是一个可执行的实体。
分类：
1. 用户级线程，用户级线程在用户空间实现，无需得到内核的支持，调度算法由线程库提供。
2. 内核支持线程，内核支持线程的TCB被它的保存在核心空间中，它的运行需获得内核的支持。
3. （用户级线程和核心级线程的结合，LWP）
即无论 是用户进程中的线程，还是系统进程中的线程，他们 的创建、撤消和切换等，是依靠内核实现的。
在内核空间中为每一个内核支持线程设置了一个线 程控制块TCB，内核是根据该控制块而感知某线程的 存在的，并对其加以控制
(1) 在多处理器系统中，内核能够同时调度同一进程中多 个线程并行执行；
(2) 如果进程中的一个线程被阻塞了，内核可以调度该进 程中的其它线程占有处理器运行，也可以运行其它进程 中的线程；
(4) 内核本身也可以采用多线程技术，可以提高系统的执 行速度和效率。
对于线程切换而言，其模式切换的开销较大，在同一个进程中，从一个线程切换到另一个线程时 ，需要从用户态转到内核态进行，这是因为用户进程的线程在用户态运行，而线程调度和管理是 在内核实现的，系统开销较大。
在仅设置了内核支持线程的OS中，一种可能的线程控制方法是，系统在创建一个新进程时，便为它分配 一个任务数据区PTDA（Per Task Data area),其中包括若干个线程控制块TCB空间
用户级线程仅存在于用户空间中。对于这种线程的创建、撤消、线程之间的同步与通信等功能，都无须内核来实现。
线程切换不调用内核
调度是应用程序特定的：可以选择最好的算法
可运行在任何操作系统上（只需要线程库），可以在一 个不支持线程的OS上实现
大多数系统调用会引起进程阻塞，并且是进程中所有线 程将被阻塞
内核只将处理器分配给进程，同一进程中的两个线程不 能同时运行于两个处理器上
所有用户级线程都具有相同的数据结构，它们都运行在一个中间系统上
（1）运行时系统
是用于管理和控制线程的函数的集合，又称为线程库。
（2）内核控制线程
这种线程又称为轻型进程LWP（Light Weight Process ）
1. 互斥锁
2. 条件变量
3. 信号量机制
调度的目标：
1、提高处理机的利用率
2、提高系统吞吐量
3、尽量减少进程的响应时间
4、防止进程长期得不到运行
调度方式和算法的选择，取决于操作系统的类型及其目标。
选择准则（面向系统）：
1. 系统吞吐量
2. 处理机利用率
3. 各类资源的平衡利用
选择准则（面向用户）：
1. 周转时间
2. 响应时间
3. 截止时间的保证
4. 优先权原则
又称为作业调度或长程调度，作业（JOB）是用户在一次算题过程中或一次事务处理中，要求计算机系统所做的工作的集合 。
批处理系统需要有作业调度，分时和实时系统无需此调度
多道程序度：即允许多少个作业同时在内存中运行。
周转时间：从作业被提交给系统开始，到作业完成为 止的这段时间间隔。
吞吐量：是指在单位时间内系统所完成的作业数
它按一定的算法将外存中已具备运行条件的进程换入内存，而将内存中某些处于阻塞状态的某些进程换出至外存（阻塞->挂起）。
中级调度的目的是为了解决内存紧张问题。
又称为进程调度或短程调度。是最基本的调度，在三种类型的操作系统中都必须配置它。（批处理、分时和实时）
分为：
1. 非抢占方式
2. 抢占方式，原则：1）优先权原则 2）短作业优先原则 3）时间片原则
三个基本原则：
（1）排队器
（2）分派器（调度程序）
（3）上下文切换机制
低级调度的功能：
(1)按某种算法选取进程（调度）。
(2)保存处理机的现场信息（上下文切换第一步骤）
(3) 把处理器分配给进程（上下文切换第二步骤）
按照作业/进程进入系统的先后次序，遵循先进入系统者先调度。
优点：
1. 有利于长作业/进程
2. 有利于CPU繁忙型作业/进程
缺点：
1. 不利于短作业/进程，尤其是来的较晚的短作业/进程
2. 不利于I/O繁忙型作业/进程
用于批处理系统，不适于分时系统
按照运行时间长短进行调度，运行时间越短越优先调度。不可抢占。
优点：
1. 能有效降低作业/进程的平均等待时间
2. 提高系统的吞吐量
缺点：
1. 不利于长作业/进程
2. 未考虑作业/进程紧迫程度，不能保证紧迫作业/进程被及时处理
3. 运行时间无法准确估计，不能真正保证短作业/进程优先
4. 无法实现人机交互
分类：
1. 静态优先权，简单易行，开销小，但是不够精确，还可能导致低优先权作业/进程长期得不到调度
2. 动态优先权，更好的调度性能，可防止长作业/进程长期垄断处理机
响应比/优先权=等待时间+要求服务时间要求服务时间=响应时间要求服务时间响应比/优先权=等待时间+要求服务时间要求服务时间=响应时间要求服务时间
此处的要求服务时间，准确来说是指剩余的需要服务的时间。
HRRN是介于FCFS和SJF/SPF之间的一种这种算法，相比于SJF/SPF有着更低的吞吐量和更高的系统开销。
对短作业有利，一定程度上是先来先服务，也对长作业有利，但由于计算响应比，会增加系统开销。
系统将所有就绪进程按先来先服务原则排成队列。
就绪进程直接置于队尾，若此时正处于某一进程的时间片，该进程是位于队首的
原理：
1. 设置多个就绪队列，并为各个队列赋予不同的优先级
2. 一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度
3. 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行
调度过程：
1. 按优先级由高到低设置多个队列RQ0 ，RQ1 … RQn ，高优先级队列时间片小
2. 刚进入系统的进程按FCFS放入最高的RQ0中
3. 进程一次时间片没执行完，就降至下一级队列，以此类 推，降至最低优先级队列后，一直在此队列中不再下降
4. 系统优先调度高优先级队列中的进程，仅当RQ0 空闲时才调度RQ1 队列进程，以此类推
5. 如果是抢占式，当前时间片未用完时有进程进入高优先级队列时，将当前进程置于其所在队列的末尾，而后开始执行高优先级队列的时间片
常用的调度方式：
1. 非抢占式轮转调度方式
2. 非抢占式优先权调度方式
3. 抢占式调度优先权调度方式
4. 立即抢占的优先权调度方式
由上往下，响应时间数量级逐个降低，要求更为严格，所需资源也更多。
常用的高优先权优先的实时调度算法：
1. 最早截止时间优先算法-EDF，截止时间越早越优先。
2. 最低松弛度优先算法-LLF，松弛度：截止时间-剩余所需时间-当前时间，主要用于可抢占调度方式，当松弛度为0时，必须立即抢占CPU。
m个同类资源被n个进程共享，设一个进程最多可以请求多x个资源
m > n * (x-1) 时，系统不会发生死锁。
破坏死锁必要条件的后三者之一，互斥条件因为一些资源固有特性的限制，难以破坏，对于打印机这样的设备可以通过SPOOLing技术对互斥条件予以破坏。
1. 破坏“请求与保持”条件，规定所有进程都必须一次性申请运行过程所需的全部资源，会造成资源浪费严重和更多更久的进程阻塞。
2. 破坏“不剥夺”条件，规定一个已经保持了某些资源的进程，在提出新的资源请求而不能立即得到满足时，必须释放它已经获得的所有资源，方法实现复杂且开销大。
3. 破坏“环路等待“条件，将系统资源按类型赋予不同的序号，当进程要获取多种资源时必须按序号逐个获取资源。会限制新设备类型的增加，由于有些进程使用资源的顺序与规定的顺序不同，会造成资源的浪费。
将系统状态分为安全状态和不安全状态，安全状态一定不会产生死锁，不安全状态可能会产生死锁。
允许进程动态申请资源，系统分配资源前进行安全性检查，若分配会导致系统进入不安全状态，则不予以分配。
银行家算法，根本思想：当某个进程提出资源请求，并请求资源小于等于它实际所需资源时，检查是否存在一条路径可以在资源分配后，剩余的进程仍然可以完全结束。
数据结构：
1. 可用资源向量 AvAIlable
2. 最大需求矩阵Max
3. 分配矩阵Allocation
4. 需求矩阵Need
5. 工作向量work
6. 工作向量Finish
系统定时进行死锁的检测，当判明将发生死锁或已经发生死锁时，进行死锁的解除。
死锁的检测：
1. 判断的现有的资源能否让现有的进程全部正常结束，不能则认为将发生死锁。
2. 周期性检测进程阻塞时间，当其超过某一时间后，认为该进程为死锁进程。
死锁的解除：
1. 剥夺资源
2. 撤销进程
三级存储：
1. 高速缓存cache
2. 内存RAM
3. 磁盘
五级存储：
1. 寄存器
2. 高速缓存
3. 内存
4. 磁盘缓存
5. 磁盘
存储分配的三种方式：
1. 直接指定
2. 静态分配方式
3. 动态分配方式
运行时动态链接是目前最常使用的链接方式
内存中仅驻留一道用户程序，整个用户区为一个用户独 占。 内存分为两个区域：系统区，用户区。
应用程序装入到用户区，可使用用户区全部空间。
算法复杂，回收分区时系统开销大。
1. 固定分区分配
（1）分区大小不等（2）分区大小相等
建立分区说明表，内存分配程序检索分区说明表，找出合适分区后修改分区状态。
优点：易于实现，开销小
缺点：内碎片造成浪费，分区总数固定，限制了并发执行的程序数目，存储空间的利用率太低。
2. 动态分区分配
1. 分区数目固定
2. 分区数目大小均不固定
数据结构：空闲分区表 / 空闲分区链
基于顺序搜索：
1. 最佳适应算法
2. 最坏适应算法
3. 首次适应算法
4. 循环首次（下次）适应算法
基于索引搜素：
1. 快速适应算法
2. 伙伴系统
总是寻找其大小最接近作业所要求的存储区域。即使作业放入后剩下的零头最小。
优点：
遇到大作业到来时，作业要求的存储区域就比较容易得到满足。
缺点：
产生空白区较多，且空白区较小无法使用（可干脆将整个区域划分给申请的作业。
回收分区时插入到合适的位置较为费时。
为了加快查找速度，应将存储空间中所有的空白 区按其大小递增的顺序链接起来，组成一空白区链 (Free List)。
它在为作业选择存储区域时，总是寻找最大的空白区。在划分后剩下的空白区也是最大的，因而对以后的分配很可能仍然是有用的，这是该算法的一个优点。
但是，由于最大的空白块总是首先被分配而进行划分，当有大的作业时，其存储空间的申请往往得不到满足，这是该算法的一个缺点。
为了支持这个算法的实现，空白块应以大小递减的顺序链接起来。
每个空白区按其在存储空间中地址递增的顺序链在 一起，即每个后继空白区的起始地址总是比前者的 大。在为作业分配存储区域时，从这个空白区链的 始端开始查找，选择第一个足以满足请求的空白块， 而不管它究竟有多大。
这个选择的空白区被分成两部分。 一部分与请求的大小相等，分配给作业；剩下的部分留在空白区链中。显然，这个算法倾向于优先利用存储空间中低址部分的空白区。
优点：
算法简单，查找速度快，大作业到来时也比较容易得到满足
缺点：
会留下较多无法使用的空白区，存储空间利用率不高。较小空白区集中在前端，较大空白区在尾端，导致找到合适的空白区的速度降低。
我们把存储空间中空白区构成一个循环链。每次为存储请求查找合适的分区时，总是从上次查找结束的地方开始，只要找到一个足够大的空白区，就将它划分后分配出去。
优点：存储空间的利用更加均衡。
将空闲分区根据其容量大小进行分类，对于每一 类具有相同容量的所有空闲分区，单独设立一个空闲分区链表。
在内存中设立一张管理分区类型，并记录 了该类型空闲分区链表表头的索引表，该表的每一个表项记录了对应类型空闲分区链表表头的指针。
在内存中设立一张管理分区类型，并记录了该类型空闲分区链表表头的索引表，该表的每一个表项记录了对应类型空闲分区链表表头的指针。
优点：
查找效率高。
该算法在进行空闲分区分配时，不会对任何分区产生 分割，所以能保留大的分区，满足对大空间的需求， 也不会产生内存碎片。（外碎片）
缺点：
在分区归还主存时算法复杂，系统开销较大。
该算法在分配空闲分区时是以进程为单位，一个分区 只属于一个进程，因此在为进程所分配的一个分区中 ，或多或少地存在一定的浪费。空闲分区划分越细， 浪费则越严重。（内碎片）
进程请求大小为n的存储空间时，
首先计算一个 i 值，使 2 i－1 < n ≤ 2 i ；
在空闲分区大小为 2 i 的空闲分区链表中查找。 if 找到，即把该空闲分区分配给进程。 else 在分区大小为2 i＋1 的空闲分区链表中寻找; //表明长度为2 i 的空闲分区已经耗尽 if 找到大小为2 i＋1 的空闲分区 把该空闲分区分为相等的两个分区（一对伙 伴），其中一个用于分配，另一个加入分区大 小为 2 i 的空闲分区链表中。 else 查找大小为2 i＋2 的空闲分区……
利用哈希快速查找的优点，以及空闲分区在可利 用空间表中的分布规律，建立哈希函数，构造一 张哈希表，以空闲分区大小为关键字，每一个表 项记录了一个对应的空闲分区链表表头指针。
当进行空闲分区分配时，根据所需空闲分区大小， 通过哈希函数计算，即得到在哈希表中的位置， 从中得到相应的空闲分区链表，实现最佳分配策 略。
解决零头问题的办法，将内存中的所有作业进行移动，使它们全都相邻接，这样，可把原来分散的多个小分区合成一个大分区。这种技术称为存储器的“紧凑”。
在动态运行时装入的方式中，作业装入内存后的所有地址都仍然是相对地址，将相对地址转换为物理地址的工作，被推迟到程序指令要真正执行时进行。
动态重定位分区分配法是利用分区的“拼接”(对空白区而言)或“紧凑”(作业程序而言)技术 解决“零头”。
对换指把内存中暂不能运行的进程或暂时不用和程序和数据，换到外存上，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的程序和数据，换入内存。
对换是系统行为，是提高内存的利用率的有效措施。
- 整体对换（进程对换）
- 页面对换（分段对换）
为实现对换，系统需要三方面的功能：
对换空间的管理
进程的换入
换出
外存被分为两部分， 文件区和对换区，文件区用于存放文件，它采取离散分配方式。 对换（续） 即一个文件可根据当前外存的使用情况 ， 被分成多块 ，分别存储到不邻接的多个存储区域中 ，用指针相连。 对换区存放从内存换出的进程 ，它们在外存的存放时间较短，换入 、换出频繁。对对换区的管理，采用连续分配方式 。
分配算法可以是首次适应算法、循环首次适应算 法和最佳适应算法。
1、换出（swap out）
①选择：首先选择阻塞或睡眠状态的进程，若有多个，按优先级由低到高进行选择。若没有此状态进程，则选择就绪状态的，仍然按优先级由低到高进行选择。
②为避免某进程被频繁的换入换出，还应考虑进程在内存中的驻留时间，优先选择驻留时间长的进程。
2、换入（swap in）
①从 PCB集合中查找“就绪且换出”的进程，有多个，则选择换出时间最长的。
②根据进程大小申请内存，成功则读入，否则要先执行换出，再换入。
③若还有可换入进程，则转向①。直至无“就绪且换出”进程或无法获得足够内存空间为止。
程序在内存中不一定连续存放。
1）离散的基础
• 分页(Pages)：将程序地址空间分页
• 分块(Frames)：将内存空间分块
2）离散分配的体现
• 内存一块可以装入程序一页
• 连续的多个页不一定装入连续的多个块中 •
注：系统中页块的大小是不变的。
根据离散时的基本单位不同，可分为三种：
分页存储管理
分段存储管理
段页式存储管理
优点：没有外零头，仅有小于一个页面的内零头
注意：
页面或页，是逻辑空间的概念
物理块或页框，是内存空间/物理空间的概念
页表，每个进程对应 1 个页表，描述该进程的各页面在内存中对应的物理块号。 包括页号、物理块号，存放在主存的系统专用区。（ 平时存于PCB中，要运行时才装入PTR中）
作业表，整个系统1张，记录作业的页表情况，包含进程号、页表长度、页表始址等信息。
空闲块表，整个系统1张，记录主存当前空闲块。
（1）根据逻辑地址,计算出页号和页内偏移量；
（2）从PTR中得到页表首址，然后检索页表，查找指定页面对应的页框号；
（3）用页框号乘以页面大小获得其对应的起始 地址，并将其送入物理地址的高端。
（4）将页内偏移量送入物理地址低端，形成完整的物理地址。
为了提高地址变换速度，为进程页表设置一个专用的高速缓冲存储器，称为快表 TLB(Translation Lookaside Buffer)，或联想存储器（Associative Memory）。专门保存当前进程最近访问过的一组页表项。
根据逻辑地址中的页号 ， 查找快表中是否存在对应的页表项。
若快表中存在该表项，称为命中（hit），取出其中的页框号， 加上页内偏移量 ，计算出物理地址。
若快表中不存在该页表项 ， 称为命中失败 ， 则再查找页表， 找到逻辑地址中指定页号对应的页框号。 同时， 更新快表， 将该表项插入快表中。并计算物理地址.
定义：从进程发出指定逻辑地址的访问请求，经过地址变换，再到内存中找到对应的物理单元并取出数据，所花费的总时间。
存储大页表，① 采用离散分配方式来解决难以找到一块连续的大内存空间的问题，（即引入两级页表），② 只将当前需要的部分页表项调入内存， 其余的 页表项仍驻留在磁盘上，需要时再调入。
对于要求连续的内存空间来存放页表的问题：
可将页表进行分页，并离散地将各个页面分别存放在不同的物理块中，
同样也要为离散分配的页表再建立一张页表，称为外层页表(Outer Page Table)，在每个页表项中记录了页表分页的物理块号。
（1）IPT是为主存中的每一个物理块建立一个页表项并按照块号排序；
（2）该表每个表项包含正在访问该物理块的进程标识、页号及特征位,用来完成主存物理块到访问进程的页号的转换。
逻辑地址给出进程标识和页号,用它们去比较 IPT, 若整个反 置 页表中未能找到匹配的页表项 , 说明该页不在主存, 产生请求调 页中断 , 请求操作系统调入;否则，该表项的序号便是物理块号,块号加上位移，便形成物理地址。
分页系统实现段的共享比较困难
分段易于实现段的共享和段的保护
分段的共享是通过两个作业段表的相应表目都指向 COS过程的同一物理副本来实现的
原理：分段和分页相结合。
内存划分：按页式存储管理方案。
内存分配：以页为单位进行离散分配。
由于段页式系统给作业地址空间增加了另一级结构，现在 地址空间是由段号S、段内页号P和页内相对地址(位移量 )W构成。
地址变换：
设置段表、段内页表
① 首先，从段表寄存器从获得进程段表的起始地址，根据该地址，查找进程的段表。
② 然后，根据逻辑地址指定的段号检索段表，找到对应段的页表起始地址。
③ 再根据逻辑地址中指定的页号检索该页表， 找到对应页所在的物理块号。
④ 最后，用物理块号加上逻辑地址中指定的页内偏移量，形成物理地址。
一个段就是一个页表
在段页式存储管理方式中，每访问一 次数据，需访问三次内存。
第一次访问内存中的段表
第二次访问内存中的页表
第三次访问相应数据。大大降低了访问速度。
解决方法： 可以设置快表，表项应包括段号、页号、物理 块号。
综合了分段和分页技术的优点，既能有效地利用存储空间，又能方便用户进行程序设计。
但是，实现段页式存储管理系统需要增加硬件成本，系统的复杂度和管理开销也大大增加。
因此，段页式存储管理技术适合于大、中型计算机系统，不太适合小型、微型计算机系统。
离散分配、对换机制、动态链接、虚拟存储器、存储器共享
物理上扩充内存：
增加硬件投入，收机器自身和成本的限制
从逻辑上扩充内存：
对换技术（解决了“驻留性”问题）
覆盖技术（解决了“一次性”问题）
虚拟存储器技术（依据程序执行的局部性原理）
程序的执行总是局部性的，表现在时间局部性和空间局部性
虚拟存储器：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。
如果系统花费大量的时间把程序和数据频繁地换入和换出内存而不是执行用户指令，那么，称系统出现了抖动。出现抖动现象时，系统显得非常繁忙， 但是吞吐量很低，甚至产出为零。
根本原因：选择的页面或段不恰当。
请求分页存储管理方式是在纯分页系统的基础上，增加 了部分页装入、请求调页、页面置换功能。
实现请求页式存储管理系统，需要一定的硬件支持。除了需要一定容量的内存和外存对换区之外，还需要请求页表机制、缺页中断机构和地址变换机构。
地址变换机制：
在纯分页系统的基础上，为实现虚拟存储器增加了某些功能：
某页在外存的情况（状态位＝0），需要增加产生和处理缺 页中断、请求调页和页面置换的功能。
访问某页时，还应修改其访问位；对某页如果执行写操作， 还应设置修改位为1。
外存要分为文件区和对换区。对换区为取得较快的速度，采用连续分配方式，且对换区所规定盘块较大。
把未来不再使用的或短期内较少使用的页面调出，通 常只能在局部性原理指导下依据过去的统计数据进行预测。 要避免“抖动”（Thrashing）（又称颠簸）
改进：考虑置换代价。选择换出页面时，既要是未使用过的页面， 又要是未被修改过的页面。把同时满足两条件的页面作为首选淘汰的页。
5. 最不常用算法
最少使用置换算法LFU（Least Frequently Used)选择 到当前时间为止被访问次数最少的页面被置换。
6. 页面缓冲算法
设内存读写周期为t，查找快表时间为λ，缺页中断处理时间为ɛ，引入快表命中率为α，缺页中断率为f，则有效访问内存时间为：
EAT=λ+αt+(1−α)[f(t+ɛ+λ)+(1−f)(t+λ)+t]EAT=λ+αt+(1−α)[f(t+ɛ+λ)+(1−f)(t+λ)+t]
产生原因：
进程分配的物理块太少
置换算法选择不当
全局置换使抖动传播
消除抖动的办法：
采取局部置换策略
基于工作集的物理块分配策略
L=S准则
挂起若干进程
基本功能：
• 1、隐藏物理设备的细节
• 2、与设备的无关性
• 3、提供处理机和I/O设备的利用率（并行操作）
• 4、对I/O设备进行控制（四种控制方式）
• 5、确保对设备的正确共享（设备的共享属性）
• 6、错误处理
总体设计目标是高效性和通用性。
(1)I/O设备与CPU的并发性；
(2)简单抽象、清晰而统一的接口。
I/O系统：用于实现数据输入、输出及数据存储的系统。
(1)按设备的使用特性分类
存储设备
输入/输出设备
(2)按传输速率分类
低速设备
中速设备
高速设备
(3)按设备的共享属性分类
独占设备(临界资源 )
共享设备
虚拟设备
三种信号：
（1）数据信号：双向，有缓存
（2）控制信号：控制器发给设备；要求其完成相 关操作
（3）状态信号：传送指示设备当前状态的信号；
设备控制器是一个可编址的设备，可控制多个设 备并为它们编址,以实现I/O设备和计算机之间的 数据交换，减轻CPU的负担。
设备控制器可分为控制块设备的控制器和控制字 符设备的控制器两类。
功能：接收CPU命令，控制I/O设备工作，解放CPU
组成：设备控制器与处理机的接口，设备控制器与设备的接口和I/O逻辑
是一种特殊处理机，专门负责输入/输出工作，具有 执行I/O指令的能力。主要目的是为了建立独立的 I/O操作，使有关对I/O操作的组织、管理及其结束 处理也独立于CPU。
把引起中断的事件称为“中断源”
对出现的事件进行处理的程序称为 “ 中断处理程序”
CPU在每条指令执行周期的最后时刻扫描中断寄存器， 询问是否有中断信号
中断处理过程
–唤醒被阻塞的驱动程序进程
–保护被中断进程CPU环境
–转入相应的设备处理程序
–中断处理(特性)
–恢复被中断进程的现场
设备驱动程序功能：
(1)接收由I/O进程发来的命令和参数, 并将命令中的抽象 要求转换为具体要求。
(2)检查用户I/O请求的合法性,了解I/O设备的状态,传递有 关参数,设置设备的工作方式。
(3)发出I/O命令并检查设备状态。
(4)及时响应由控制器或通道发来的中断请求并处理。
设备驱动程序的特点：
(1)驱动程序主要是指在请求I/O的进程与设备控制器之间 的一个通信和转换程序。
(2)驱动程序与设备控制器和I/O设备的硬件特性紧密相关 ,因而对不同类型的设备应配置不同的驱动程序。
(3)驱动程序与I/O设备所采用的I/O控制方式紧密相关， 常用中断驱动和DMA方式。
(4)由于驱动程序与硬件紧密相关,因而其中的一部分必须 用汇编语言书写。
(5)驱动程序允许可重入。
设备处理方式：
(1)为每一类设备设置一个进程,专门用于执行这类设 备的I/O操作 。
(2)在整个系统中设置一个I/O进程,专门用于执行系统 中所有各类设备的I/O操作。
(3)不设置专门的设备处理进程,而只为各类设备设置 相应的设备处理程序(模块),供用户进程或系统进程调用
I/O控制方式：
含义：应用程序独立于具体使用的物理设备，即是指用 户在编程序时所使用的设备与实际设备无关。
引入逻辑设备和物理设备这两个概念。
在应用程序中,使用逻辑设备名称来请求使用某类设备;而系统在实际执行时,还必须使用物理设备名称。
设备独立性的优点
(1)设备分配时的灵活性
(2)易于实现I/O重定向
设备独立性软件主要功能：
(1)执行所有设备的公有操作
(2)向用户层(或文件层)软件提供统一接口
（1）设备控制表DCT
（2）控制器控制表、通道控制表和系统设备表
虚拟设备是利用某种技术把独占设备改造成可由多个进程共享的设备。
用户程序通过调用对应的库函数使用系统调用。
SPOOLing技术将一台物理I/O设备虚拟为多台逻辑I/O 设备，同样允许多个用户共享一台物理I/O设备。
(1)脱机输入、输出技术
(2) 在主机的直接控制下，实现脱机输入、输出功能，此时的外围操作与CPU对数据的处理同时进行。
SPOOLing技术将一台物理I/O设备虚拟为多台逻辑I/O 设备，同样允许多个用户共享一台物理I/O设备。
输入井和输出井
输入缓冲区和输出缓冲区(内存中)
输入进程SPi 和输出进程SP0
井管理程序
输出：（打印） a.进程n请求——>SPo为进程n在输出井中分配空间——> 将数据由进程缓冲区转到输出井——>生成一打印请求 表挂打印请求队列。 b.打印机空——>查打印请求表中的任务——> 取输出井 中对应的数据——>输出缓冲区——>打印
(1)缓和CPU与I/O设备间速度不匹配的矛盾。
(2)减少对CPU的中断频率,放宽对CPU中断响应 时间的限制。
(3)解决数据粒度不匹配的问题。
(4)提高CPU和I/O设备之间的并行性。
提前读，延后写，操作系统中介绍的都是软件缓冲区
一个缓冲区，CPU 和外设轮流使用， 一方处理完之后接着等待对方处理
C和T可并行，M和C或M和T不能并行，因此处理一块数据时间：Max(C,T)+M
（C为工作区处理数据，M为缓冲区传送到工作区，T为I/O设备输入到缓冲区）
两个缓冲区，CPU和外设都可以连续处理而无需等待对方。要求CPU和外设的速度相近。
• 效率有所提高，且进一步平滑了传输峰值。
• 系统处理一块数据的时间约为：MAX(C,T) • 收发可双向同时传送。
增加缓冲区的数量以改善系统性能，这就是多缓冲区方式。
多个I/O缓冲区常常被组织成一个环形队列，称为循环缓冲。
上述三种缓冲区的组织形式仅适用于某种特定的 I/O进程和计算进程，属于专用缓冲。
为了提高缓冲区的利用率，可以采用公共缓冲池
其中的缓冲区可为多个设备和进程服务
两种缓冲池：分别用于块型设备和字符型设备。
公用缓冲池，含有以下三种类型的缓冲区： ①空(闲)缓冲区； ②装满输入数据的缓冲区； ③装满输出数据的缓冲区。
为了管理上的方便，可将相同类型的缓冲区链成 一个队列，于是可形成以下三个队列：
（1）空缓冲队列emq。 这是由空缓冲区所链成的队列。
（2）输入队列inq。 这是由装满输入数据的缓冲区所链成的队列。
（3）输出队列outq 这是由装满输出数据的缓冲区所链成的队列。
1、数据组织和格式：
•磁道号——磁头号——扇区——字节
2、类型
1）固定头磁盘： –每个磁道上有一个磁头，快
2）移动头磁盘： –每个盘面仅有一个磁头，慢
• 信息记录在磁道上，多个盘片，正反两面都用来记 录信息，每面一个磁头
• 所有盘面中处于同一磁道号上的所有磁道组成一个 柱面
• 每个扇区大小为600字节（数据512字节）
• 物理地址形式： –柱面号 –磁头号 –扇区号
由三个动作组成：
– 寻道 ：磁头移动定位 到指定磁道
– 旋转延迟：等待指定 扇区从磁头下旋转经过
– 数据传输：数据在磁 盘与内存之间的实际传输
磁盘访问时间：
1）寻道时间：TS=m∗n+sTS=m∗n+s m：常量，n：磁道数，s：磁臂启动时间。 对一般的磁盘， 其寻道时间将随寻道距离的增加而 增大， 大体上是5-30 ms。
2）旋转延迟时间： 指定扇区旋转到磁头下所需时间。 设每秒r转，则Tr＝1/2rTr＝1/2r（均值） 对于7200转/分，平均延迟时间为4.2ms
3）数据传输时间：Tt＝b/rNTt＝b/rN b：读写字节数 N：每道上的字节数
访问时间：Ta=Ts+1/2r+b/rNTa=Ts+1/2r+b/rN
有一个或几个进程对某一磁道有较高的访 问频率， 即这个(些)进程反复请求对某一磁道的I/O操作，从而垄断了整个磁盘设备。 我们把这一现象称为“磁臂粘着”(Armstickiness)。
实际系统相当普遍采用最短寻道时间优先算法， 因为它简单有效，性价比好。
…
文件系统的功能：
有效地管理文件的存储空间；
管理文件目录；
完成文件的读/写操作；
实现文件共享与保护；
为用户提供交互式命令接口和程序调用接口。
定义：
操 作 系 统 中 的 各 类 文件、 管 理 文 件 的 软件， 以 及 管 理 文 件 所 涉 及 到 的 数据结 构等信息的集合
分为三个层次：
1. 文件系统接口
2. 对对象操纵和管理的软件集合
3. 对象及其属性
对于任何一个文件，都存在着以下两种形式的结构：
文件的逻辑结构(File Logical Structure),又称 为文件组织，是用户可以直接处理的数据及其 结构。
文件的物理结构， 又称为文件的存储结构， 是指文件在外存上的存储组织形式。
第一种是串结构， 各记录之间的顺序与关键字无关。 通常的办法是由时间来决定，即按存入时间的先后排列。
第二种情况是顺序结构，指文件中的所有记录按关键字 (词)排列。是最常用的文件组织方式。
顺序文件的优缺点
常 用 于 批 量 数 据 处 理 ， 这 时 文 件 的 访 问 效 率最高。
是唯一、 同 时 适 合 在 磁 盘 和 磁 带 中 存 储 的 文件。
访问效率比堆文件高。当文件较小，可以将文件全部装入内存，利用某种快速的查找算法，如折半查找法、插值查找法等快 速查找指定的记录。
可为变长记录文件建立一张索引表，对主文件中的每个记录，在索引表中设有一个相应的表项， 用于记录该记录的长度L及指向该记录的指针(指 向该记录在逻辑地址空间的首址)。
由于索引表是按记录键排序的，因此，索引表本身是一个定长记录的顺序文件，从而也就可以方便地实现直接存取。
将顺序文件中的所有记录分为若干个组(例 如，50 个记录为一个组)；
为顺序文件建立一张索引表.
在索引表中为每组中的第一个记录建立一 个索引项，其中含有该记录的键值和指向该记录的指针。
直接文件
对于直接文件，则可根据给定的关键字值，直 接获得指定记录的物理地址。
关键字值本身就决定了记录的物理地址。
这种由关键字值到记录物理地址的转换被称为键值转换。
文件目录也是一种数据结构，用于标识系统中的 文件及其物理地址，供检索时使用。
文件控制块是操作系统为管理文件而设置的数据结构，存放了管理文件所需的所有信息（文件属性）
1）基本信息类
文件名：文件标识符；
物理位置：存放文件的设备名 起始盘块号 文件长度（盘块数或字节数）
逻辑结构：有结构文件、无结构文件
物理结构：顺序文件、链式文件、索引文件
2）存取控制信息类
文件主的存取权限
核准用户的存取权限
一般用户的存取权限
3）使用信息类
文件的建立日期和时间
文件上一次修改的日期和时间
当前使用信息（进程数、是否修改等）
文件目录：把所有的FCB组织在一起，就构成 了文件目录，即文件控制块的有序集合。
目录项：构成文件目录的项目（目录项就是 FCB）
目录文件：为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，这个文件就叫目录文件。
将文件的描述信息单独形成称为索引结点的数据结构，即 i 结点
查询目录有两种方法：
线性检索法
Hash 方法
实现文件共享的方式：
基于索引结点的共享方式
利用符号链实现文件共享
利用URL实现文件共享
存取控制机制
系统容错技术（第八章）
后备系统（第八章）
保护域
访问矩阵
访问矩阵的修改
访问矩阵的实现
分级安全管理
连续分配(Continuous Allocation)要求为每一 个文件分配一组相邻接的盘块。一组盘块的地址 定义了磁盘上的一段线性地址。
把逻辑文件中的数据顺序地存储到物理上邻接的各个数据块中，这样形成的物理文件可以进行顺序存取。
连续分配的主要优点：
顺序访问容易。
顺序访问速度快。
连续分配的主要缺点：
要求有连续的存储空间。
必须事先知道文件的长度。
不能灵活地插入和删除记录
不适应动态增长的文件
该 分 配 方 案 可 能 会 导 致 磁 盘 碎 片 ， 严 重 降 低外存空间的利用率。
解 决 方 法 之 一 ， 系 统 定 期 或 不 定 期 采 用 紧 凑 技术， 将 小 分 区 合 并 为 大 的 、 连 续 分 区 ， 将文件占用空间合并在一起。
如果在将一个逻辑文件存储到外存上时，并不要 求为整个文件分配一块连续的空间，而是可以将 文件装到多个离散的盘块中。
采用链接分配方式时，可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，把这样形成的物理文件称为链接文件。
问题：
(1) 不能支持高效的直接存取
(2) FAT需占用较大的内存空间
设文件系统采用两级索引分配方式，如果每个盘块的大小为1KB，每个盘块号占4B，则单个文件的最大长度是多少？ 解：1个盘块可有1KB/ 4B=256个索引项，则两级索引下单个文件最大长度： 256*256*1KB=64MB
存储空间的基本分配单位是磁盘块。
其分配方法与内存的分配有许多相似之处，即同样可采取连续分配方式或离散分配方式。
动态跟踪磁盘上的空闲块数目和块号，形成空闲块登记表。
空闲块登记表是盘块分配和回收的依据。
空闲块登记表有四种实现方案：
分时系统或个人计算机中，操作系统 向用户提供了一组联机命令，用户可以 通过终端键入命令，以取得操作系统的 服务，并控制自己作业的运行，这样的 接口称为联机命令接口 。
联机命令接口应由终端处理程序、命令解释程序及一组联机命令构成。
Shell是UNIX与用户的交互接口,是操作系统的最外层,称为外壳
Shell既是一种命令语言,也是一种程序设计语言
Shell不是UNIX的核心程序,运行在用户态
系统调用指系统为用户程序调用操作系统所提供的子程序。 它与一般的函数调用不同，系统调用是通过中断方式转向相应子程序的，它工作在核心态 （即特权方式），而一般函数调用，仍仅在用户态下的地址转移 。
系统调用与一般过程调用的区别：
京公网安备 11010802035086号