计算机操作系统

视频教程点这里

文章目录

• 计算机操作系统
• • 一、操作系统概述
  • • 1）操作系统的发展
    • 2）操作系统的特征
    • 3）操作系统的功能
  • 二、进程与线程
  • • 1）进程的创建、表示、组织、特征
    • 2）进程的状态转换
    • 3）进程通信
    • 4）进程同步与互斥
    • 5）进程同步、互斥综合实现的经典案例
    • 6）线程的属性、实现方式、多线程模型
  • 四、调度与死锁
  • • 1）处理机调度的层次
    • 2）进程调度的时机和方式
    • 3）调度算法的评价指标
    • 4）适用于早期批处理系统的调度算法
    • 5）适用于交互式系统的调度算法
    • 6）死锁的发生和处理
  • 五、内存
  • • 1）程序与内存、存储保护
    • 2）内存空间的管理
    • 3）内存空间的扩充
  • 六、文件管理
  • • 1）文件系统层次结构
    • 2）文件基本操作
    • 3）文件目录
    • 4）文件保护
    • 5）文件逻辑结构
    • 6）文件物理结构
    • 7）文件存储空间管理
    • 8）磁盘管理
  • 七、I/O设备
  • • 1）I/O设备
    • 2）I/O软件系统

一、操作系统概述

1）操作系统的发展

• 手工操作阶段：用户独占全机；人机速度矛盾

• 批处理阶段（解决了用户独占全机和人机速度矛盾的问题）

  • 单道批处理系统：脱机输入输出技术（外围机+磁带）；负责控制作业输入输出的监督程序（操作系统雏形）
  • 多道批处理系统：每次往内存中输入多道程序；操作系统正式诞生，并引入了中断技术，且各个程序并发执行，共享计算机资源

• 分时操作系统：（解决了人机交互问题）以时间片为单位轮流为各用户服务，各用户可通过终端与计算机进行交互，但不具由有优先处理紧急任务的能力

• 实时操作系统：（解决了紧急任务处理的问题）计算机系统在收到外部信号时及时处理并且要在严格时限内处理完事件

  • 硬实时系统：必须绝对严格规定时间内完成处理，如导弹控制系统、自动驾驶系统
  • 软实时系统：能接受偶尔违反时间规定，如12306火车订票系统

• 网络操作系统：实现网络中各资源的共享和各计算机之间的通信，如网站服务器可以使用的Windows NT系统

• 分布式操作系统：任何工作都可以分布在这些计算机上，由它们并行、协同完成

• 个人计算机操作系统：如Windows XP、MacOS，方便个人使用

2）操作系统的特征

• 并发：宏观上同时发生，微观上交替发生（并行是指宏观微观上都是同时发生）
• 共享
  • 互斥共享：同一时间段只允许一个进程访问该资源，如摄像头
  • 同时共享：允许一个时间段内由多个进程宏观上同时访问该资源，如硬盘资源，微观上同时访问该资源，如扬声器
• 虚拟
  • 虚拟存储器技术，4GB内存的电脑可以同时运行加起来超出4GB的多个程序（空分复用技术）
  • 虚拟处理器技术，一个单核CPU能同时运行多个用户程序（时分复用技术）
• 异步：多道程序环境下，由于资源有限，进程的执行不是一贯到底的，而是走走停停

3）操作系统的功能

• 原语：一种运行在核心态的特殊程序，把本身很简单的硬件的功能拓展为更丰富的、更方便用户使用的一系列功能，是最接近硬件的部分，这种程序的运行具有原子性，通过“关中断指令”和“开中断指令”实现，执行期间会忽略外部中断信号，保证程序一气呵成，如设备驱动、CPU切换、进程控制（如创建原语、切换原语、阻塞原语、唤醒原语、撤销原语）等

• 时钟管理：计时功能

• 系统资源管理

  • 文件管理：文件的读、写、创建、删除

  • 内存管理：内存的分配、回收等

  • 进程管理：进程控制（创建、撤销、阻塞、唤醒等）、进程调度、进程间通信

  • 存储器管理：存储分配、存储共享、存储保护、存储扩张等

  • 设备管理：设备分配（请求、启动、释放）、设备传输控制、设备独立性等

• 作为用户和计算机硬件之间的接口

  • 命令接口：允许用户直接使用

    • 联机命令接口：如Windows操作系统的cmd命令提示符窗口

    • 脱机命令接口（批处理命令接口）：如Windows操作系统的*.bat文件

  • 程序接口（内中断/系统调用）：为避免各个进程随意使用系统资源，操作系统提供“系统调用”功能，用户进程想要使用共享资源时，只能通过系统调用向操作系统发出请求，操作系统回怼各个请求进行协调管理

    • 如程序员在程序中调用C:\Windows\System32\user32.dll即可实现创建窗口等功能

    • 如高级语言中的某些库函数内部封装了系统调用的复杂细节，使编程更加方便

  • 图形用户接口：GUI图形用户界面

• 中断处理

  【CPU两种状态：用户态/目态（CPU只能执行非特权指令/普通指令，如加减乘除，应用程序运行在用户态）、核心态/管态（非特权指令、特权指令，如内存清零指令都能执行，特权指令只能在核心态下执行，内核程序运行在核心态）】

  【中断是CPU从用户态切换为核心态的唯一途径，使操作系统获得计算机的控制权】

  【核心态到用户态的转换要执行一个特权指令，设置程序状态字寄存器PSW的相应标志位，0为用户态，1为核心态】

  • 进程之间切换时：CPU收到计时部件发出的中断信号，把CPU使用权限交给操作系统，切换为核心态对中断进行处理，进程间切换完成后将CPU的使用权交回

  • 进程中遇到像输入输出操作这样的特权指令时（内中断/系统调用）：在将相应数据准备好后，需要在用户态下先执行一个陷入（trap/访管）指令，随后立即引发一个内中断，这时CPU会让操作系统介入，切换为核心态代替进程完成相应的工作（如让打印机开始工作，暂停当前进程等待I/O完成，换另一进程运行），之后将CPU的使用权交回

  • 外部设备向CPU发出如I/O完成的中断信号时（外中断）：CPU会让操作系统介入，切换为核心态对中断进行处理（如让暂停的进程恢复运行），处理完后将CPU的使用权交回

二、进程与线程

1）进程的创建、表示、组织、特征

• 引起进程创建的事件

  • 用户登录：分时系统中，用户登录成功，系统会建立一个新进程
  • 作业调度：多道批处理中，有新的作业放入内存，系统会建立一个新进程
  • 提供服务：用户向操作系统提出某些请求时，会新建一个进程处理该请求
  • 应用请求：由用户进程主动请求创建一个子进程

• 进程实体（进程映像）

  • PCB：系统为每个运行的程序配置一个数据结构，成为进程控制块（PCB），用来描述进程的各种信息，创建一个进程实质上是创建进程实体中的PCB，撤销进程实质上是撤销进程实体中的PCB，PCB是进程存在的唯一标志

    • 进程描述信息：进程标识符PID、用户标识符UID
    • 进程控制和管理信息：进程当前状态、进程优先级
    • 资源分配清单：程序段指针、数据段指针、键盘、鼠标
    • 处理机相关信息：各种寄存器值，当进程切换时需要把进程当前的运行情况记录下来保存在PCB中，如程序计数器的值

  • 程序段：存放要执行的代码

  • 数据段：存放程序运行过程中处理各种数据

• 多个进程之间的组织方式

  • 链接方式：按照进程状态将PCB分为多个队列，操作系统持有指向各个队列的指针

    • 执行指针：指向当前处于运行状态（执行态）的进程的进程控制块，单CPU计算机中，同一时刻只会有一个进程处于运行态
    • 就绪队列指针：指向当前处于就绪态的进程的进程控制块，通常把优先级高的进程放在队头
    • 阻塞队列指针：指向当前处于阻塞态的进程的进程控制块，很多系统还会根据阻塞原因不同，再分为多个阻塞队列

  • 索引方式：根据进程状态不同，建立几张索引表，操作系统持有指向各个索引表的指针

    • 执行指针：同链接方式
    • 就绪表指针：指向就绪索引表的第一个进程控制块
    • 阻塞表指针：指向阻塞索引表的第一个进程控制块

• 进程的特征

  • 动态性：进程是程序的一次执行过程，是动态地产生、变化和消亡的

  • 并发性：内存中有多个进程实体，各进程可并发执行

  • 独立性：进程是能够独立运行、独立获得资源、独立接受调度的基本单位（引入线程前，进程是资源分配、系统调度的基本单位，引入线程后，线程是系统调度的基本单位，但进程还是资源分配的基本单位）

  • 异步性：各进程按各自独立的、不可预知的速度向前推进（异步性会导致并发程序执行结果的不确定性，因此操作系统要提供“进程同步机制”来解决异步问题）

  • 结构性：进程由程序段、数据段、PCB组成

2）进程的状态转换

• 五状态模型

  • 创建状态：操作系统为该进程分配所需内存空间等系统资源，并为其创建、初始化PCB的过程
  • 就绪状态：已经具备运行条件，因CPU没有空闲，暂时不能运行，拥有其他运行资源
  • 运行状态：占有CPU，并在CPU上运行，拥有其他所需资源
  • 阻塞状态：因等待某一事件而暂时不能运行，不占有CPU，不拥有其他运行资源
  • 终止状态：回收分配给进程的资源，撤销进程PCB的过程

• 七状态模型

• 进程状态间的转换

  （通过原语来实现，以五状态模型为例，七状态模型中其他进程状态之间的切换见“四、调度”一章的”1）处理机调度层次“一节）

  • 创建态 -> 就绪态：需修改PCB内容和相应队列，由创建原语完成

  • 就绪态 -> 运行态：该进程被调度，需恢复进程运行环境（之前可能被切换了）、修改PCB内容和相应队列，由切换原语完成

  • 运行态 -> 就绪态：时间片到，或者处理机被抢占，需保存进程运行环境、修改PCB内容和相应队列，由切换原语完成

  • 运行态 -> 阻塞态：进程用系统调用的方式申请某种系统资源，或者请求等待某个事件发生（进程的主动行为），需保存进程运行环境、修改PCB内容和相应队列，由阻塞原语完成

  • 阻塞态 -> 就绪态：申请的资源被分配，或等待的事件发生（被动行为），需修改PCB内容和相应队列，如果等待的是资源，还需为进程分配系统资源，由唤醒原语完成

  • 运行态 -> 终止态：进程运行结束，或运行过程中遇到不可修复的错误，需回收进程拥有的资源，撤销PCB，由撤销原语完成

3）进程通信

• 共享存储

  （操作系统会给需要相互通信的进程分配共享空间）

  （但是进程对共享空间的访问是互斥的，通过系统提供的同步互斥工具实现，如P、V操作）

  • 基于数据结构的共享：如共享空间里只能放一个长度为10 的数组，由操作系统决定，进程间每次通信只能传一个长度为10的数组，是一种低级通信方式
  • 基于存储区的共享：数据的形式、存放位置由相互通信的进程决定，是一种高级通信方式

• 消息传递

  （以格式化消息为单位，通过“发送消息/接收消息”两个原语来实现）

  （消息头包括发送进程ID、接收进程ID、消息类型、消息长度等格式化消息，消息体是指要交换的数据）

  • 直接通信方式：发送进程用发送原语将消息直接挂到接收进程的消息缓冲队列上，接收进程用接收原语将消息缓冲队列中的消息依次接收
  • 间接通信方式：也称信箱通信方式，消息由发送原语发送到中间实体信箱中，由接收原语从信箱中取走消息

• 管道通信：

  （管道是在内存中开辟的一个大小固定的缓冲区，指用于连接读写进程的一个共享文件，pipe文件，每个管道只能实现半双工通信）

  （进程对管道的访问是互斥的）

  （数据以字符流的形式写入管道，当管道写满时，写进程的write()系统调用将被阻塞，等待读进程将数据取走，全部取走管道变空时读进程的read()系统调用将被阻塞）

  （如果没有写满不允许读，如果没有读空不允许写）

  （数据一旦被读出就被抛弃，所有读进程只能有一个）

4）进程同步与互斥

• 进程互斥

  （是指当一个进程正在访问临界资源(一个时间段内只允许一个进程使用的资源)时，即进入了临界区，另一进程必须等待而形成的间接制约关系，遵循空闲让进、忙则等待、有限等待、让权等待(当进程暂时不能访问临界资源时，应立即释放处理机)原则）

  • 软件实现方法

    • 单标志法：定义一个标志表示当前允许进入临界区的进程号，每个进程要首先对标志进行检查，判断当前允许进入临界区的进程号是否为自己，如果不是则无限循环等待，直到另一个进程将标志位设为自己，然后跳出循环进入临界区

      （如果一开始标志位设置为其中一个进程，这个进程不想要进入临界区，而另一个进程想要进入临界区，但此时它没办法进入，违背了空闲让进原则）

    • 双标志先检查：设置一个数组，数组中各元素用来标记各进程想要进入临界区的意愿，每个进程首先要一直检查另一个进程的意愿是否为true，如果对方意愿为true，则无限循环等待，直到对方意愿变为false，然后上锁，修改自己意愿为true，接着进入临界区

      （由于检查和上锁两个处理不是一起呵成的，因为处理机的调度，可能导致两进程同时访问临界区，违背了忙则等待的原则）

    • 双标志后检查：与双标志先检查法不同的是先上锁，把自己的意愿修改为true，再检查对方意愿是否为true，如果是则无线循环等待，直到对方意愿变为false，跳出循环进入临界区

      （由于检查和上锁两个处理不是一起呵成的，因为处理机的调度，可能导致两进程都无法进入临界区，违背了空闲让进、有限等待的原则，导致各进程长期无法访问临界资源而产生饥饿现象）

    • Peterson算法：即设置当前允许进入临界区的进程号，又设置意愿数组，首先主动争取，将意愿设为true，然后主动让步，将允许进入临界区的进程号设为另一个进程，最后检查另一个进程的意愿是否为true，并且当前允许的进程号是否是对方，如果都是，则无线循环等待，直到对方意愿变为false或当前允许的进程号被修改成自己，则退出等待，进入临界区

      （既解决了进程互斥问题，又遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待原则，在自己无限循环等待时不让出CPU，直到自己时间片结束被迫让出CPU）

  • 硬件实现方法

    • 中断屏蔽法（关中断、开中断指令）：在某进程开始访问临界区到访问结束为止不允许被中断

      （关中断指令和开中断指令是针对当前处理机有效的，不能避免多个处理机同时访问同一临界资源的情况，所以这种方法不适合多处理机，且开中断、关中断指令只能运行在内核态，所以只适用于操作系统内核进程，不适用于用户进程）

    • TestAndSet（TS）指令或TestAndSetLock（TSL）指令：系统为临界区设置一个共享变量，作为当前临界区是否被加锁的标志，TS或TSL指令会先对其加锁，然后返回加锁前的标志值，进程使用这个指令判断当前临界区是否是上锁的，如果是，则无限循环等待，如果不是，则进入临界区，执行完后解锁

      （TSL指令是用硬件方式一气呵成的原子操作，上锁和检查操作是用硬件方式一气呵成的原子操作，无需像软件实现方法那样要严格检查是否会有逻辑漏洞，适用于多处理机环境；但是依旧不满足让权等待原则，暂时无法进入临界区的进程会一直占用CPU，直到自己时间片结束）

    • Swap指令（有的地方也叫Exchange指令，简称XCHG指令）：系统为临界区设置一个共享变量，作为当前临界区是否被加锁的标志，Swap指令实现两个变量值的交换，进程使用这个指令前，先设置一个值为true的变量，然后一直检查这个变量的值，如果为true，则将这个变量的值与临界区标志值进行交换，其实相当于上锁和检查，直到这个变量的值变为false，说明临界区标志值变为了false，则跳出循环，进入临界区，其实这个逻辑与TS或TSL指令是一样的

      （Swap指令是用硬件方式一气呵成的原子操作，上锁和检查操作是用硬件方式一气呵成的原子操作，无需像软件实现方法那样要严格检查是否会有逻辑漏洞，适用于多处理机环境；但是依旧不满足让权等待原则，暂时无法进入临界区的进程会一直占用CPU，直到自己时间片结束）

  • 信号量机制

    （信号量是一种变量，可以是一个整数，也可以是更复杂的记录型变量，可以用来表示系统中某种资源的数量）

    （使用操作系统提供的wait原语，即P操作，和signal原语，即V操作这一对原语来对信号量进行操作）

    （对信号量的操作只有初始化、P操作、V操作三种）

    • 整形信号量：初始化整形信号量为资源数，整形信号量作为wait原语的传入参数，wait原语会先判断信号量是否为0或小于0 ，如果是，则无限循环等待，如果不是，则将信号量减1，然后wait原语执行结束；signal原语直接将信号量加1；进程想要进入临界区时，先使用wait原语，然后进入临界区，执行完后然后使用signal原语退出临界区

      （可以解决双标志先检查法中进入区的检查、上锁操作无法一气呵成而导致的两进程同时进入临界区的问题）

      （无法实现让权等待，暂时无法进入临界区的进程会一直占用CPU，直到自己时间片结束）

    • 记录型信号量：初始化记录型信号量，其value值为资源数，记录型信号量作为wait原语的传入参数，wait原语会先将记录型信号量的value值减1，然后判断其值是否小于0，若小于0则表示在执行wait原语时剩余资源数已经不够了，这时，就使用block原语，使当前进程从运行态进入阻塞态，并把它挂到信号量S的等待队列，即阻塞队列的队尾；当允许进入临界区且执行完毕后，将执行signal原语，记录型信号量作为传入参数，首先对信号量的value值加1，然后判断其若还是还小于等于0，则要使用wakeup原语唤醒等待队列中的进程，使它从阻塞态变为就绪态继续执行

      （可以解决双标志先检查法中进入区的检查、上锁操作无法一气呵成而导致的两进程同时进入临界区的问题）

      （可以实现让权等待，暂时无法进入临界区的进程会被阻塞，被迫让出CPU）

• 进程同步（前驱关系）

  （是指有些进程需要在某些位置上协调工作次序而产生的直接制约关系，如进程通信中的管道通信）

  • 一对前驱关系实现方法：初始化记录型信号量为0，在“前操作”之后执行V操作，在“后操作”之前执行P操作

  • 多对前驱关系实现方法：要对每一对前驱关系各设置一个记录型信号量，也称同步变量

• 管程实现同步与互斥

  • 管程的定义：一种特殊的软件模块，由与共享资源相对应的共享数据结构、对该数据结构进行操作（如insert、remove等）的一组过程（函数）、对该数据结构进行初始化的语句、管程的名字构成（类似于Java当中的类）

  • 管程的特征：管程的数据只能相对应的进程访问、一个进程只有通过调用管程内的过程（函数）才能进入管程访问共享数据、每次仅允许一个进程在管程内执行（无论执行的是哪个过程）

  • 用管程解决生产者消费者问题：为了解决并发问题，由编译器负责实现各进程互斥地进入管程中的过程，类似于一个排队器，一个进程一个进程地访问，当然如果一个进程不能访问共享资源而被阻塞，那么它应该先释放管程的使用权，让下一个排队的进程可以进入管程执行某个内部过程；为了解决同步问题，管程中还需要设置类似于信号量的条件变量，用wait和signal操作实现同步

  • 管程的好处：信号量机制编写程序困难、易出错，管程是用于实现进程的同步与互斥的一种高级同步机制，程序员可以用某种特殊的语法定义一个管程，之后其他程序员就可以使用这个管程提供的特定的“入口”很方便地使用实现进程同步、互斥了

  • Java中类似于管程的机制：如果用关键字synchronized来描述一个函数，那么这个函数同一时间段内只能被一个线程调用

5）进程同步、互斥综合实现的经典案例

（这里只列了注意点，详细操作见视频教程）

（使用的信号量均为记录型信号量）

• 生产者消费者问题（单生产者单消费者问题）
  • 如消费者生产者互相等待的情况需要设置两个同步信号量，实现两个“前V后P”
  • 还要设置互斥访问
  • 而且实现互斥的P操作一定要在实现同步之后，否则会出现死锁，由于V操作不会导致进程阻塞，因此两个V操作可以互换顺序
• 爸妈儿子女儿盘子苹果橘子问题（多类生产者多类消费者问题）
  • 同步信号量的设置：有多少种资源，就设置多少种信号量
  • 同步关系的处理：同步时应该从事件角度分析，而不是进程角度
  • 当缓冲区容量为1时，所有同步信号量中最多有一个1，这时可以不设置专门的互斥信号量
  • 当缓冲区容量大于1时，这时必须设置专门的互斥信号量
• 吸烟者问题（可生产多种产品的单生产者多消费者问题）
  • 要实现消费者轮流抽烟的话，要设置一个普通标志变量，用于生产者中进行if判断
• 多写者多读者问题（写者间互斥、读者与写者间互斥、读者间不互斥）
  • 读数据时不会清空数据，也不会改变数据，因此多个读者可同时访问共享数据，而任一写进程不能与其他读进程或写进程同时操作，为此增加一整数变量count来记录当前几个读进程在访问文件，每个读进程要对count进行检查，若此进程是第一个读进程，则开始前要进行P操作和count++操作，若此进程是最后一个读进程，则结束前要进行V操作和count–操作
  • 而且为了避免对count变量的检查和赋值无法一气呵成的问题，要在判断count值、P操作、count++操作这三个操作组合以及判断count值、V操作、count–操作这三个操作组合的前后加互斥访问，即建立新的互斥信号量，加P、V操作
  • 为了避免源源不断的读进程到来导致的写进程饿死现象，要增加一个新的信号量，把相应的P、V操作加在写进程while循环的所有操作前后，也加在读进程while循环里读文件前的所有操作前后，以对写进程设置写优先，当然不是真正的写优先，而对于后续进程的处理遵循类似于先来先服务原则的相对公平的操作（读写公平法）
• 哲学家进餐问题（每个进程需要同时持有两个临界资源才能顺利执行）
  • 定义互斥信号量数组，对进程编号，将编号与互斥信号量数组元素的角标进行映射
  • 为了避免死锁现象，解决方法一是对哲学家进程施加一些限制，比如最多允许四个哲学家同时进餐，即四个进程并发执行，设置初始值为4的信号量；解决方法二是要求奇数号的哲学家先拿左边的筷子，偶数号哲学家先拿右边的筷子，先判断自己是奇数号还是偶数号，然后执行不同顺序的操作；解决方法三是增加一个新的互斥信号量，将哲学家拿左筷子和右筷子的操作前后加上P、V操作

6）线程的属性、实现方式、多线程模型

• 线程的属性

  • 引入线程之后，线程成为CPU调度的基本单位，程序执行流的最小单位，每个线程都有一个线程ID、线程控制块TCB，线程也有就绪、阻塞、运行三种基本状态
  • 进程只作为除了CPU之外的系统资源的分配单元，如打印机、内存地址空间都是分配给进程的，线程几乎不拥有系统资源，同一进程的不同线程间共享进程的资源，共享地址空间，所以同一进程的线程间通信无需系统干预
  • 同一进程内线程的切换不需要切换进程环境，系统开销小；不同进程中的线程切换会引起进程切换，系统开销大

• 线程的实现方式

  • 用户级线程：由应用程序通过线程库实现，所有线程切换工作都由应用程序负责，在用户态下完成，系统内核并意识不到线程的存在
  • 内核级线程：线程调度、切换工作由操作系统内核完成，在核心态下完成，内核级线程才是处理机调度的单位

• 多线程模型

  （有的操作系统只支持用户级线程，有的只支持内核级线程，有的同时支持用户级线程和内核级线程）

  • 多对一模型：多个用户级线程映射到一个内核级线程，一个进程对应一个内核级线程

    • 优点：用户级线程的切换在用户空间就能完成，不需要切换到核心态，线程管理的系统开销小，效率高）

    • 缺点：进程每次只有一个线程处于运行状态，其他线程只能等待，当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高，多个线程不可在多核处理机上并行运行）

  • 一对一模型：一个用户级线程映射到一个内核级线程，一个进程对应多个内核级线程

    • 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强，多线程可在多核处理机上并行执行）

    • 缺点：线程切换由操作系统内核完成，需要切换到核心态，线程管理成本高、开销大）

  • 多对多模型：将n个用户级线程映射到m个内核级线程上，n>=m，一个进程对应多个内核级线程

    • 优点：克服了多对一模型中并发度不高的缺点，又克服了一对一模型中系统管理开销大的缺点）

四、调度与死锁

1）处理机调度的层次

• 高级调度（作业调度）：按一定的原则从外存上处于后备队列的作业中挑选一个或多个，给他们分配内存等必要资源，并建立相应的进程，也就是建立PCB，使它们处于就绪状态，每个作业只被调入一次、调出一次
• 中级调度（内存调度）：引入虚拟存储技术后，可将暂时不能运行的阻塞态进程调至外存等待，变为阻塞挂起状态；将暂时不能运行的创建态进程、就绪态进程、运行态进程调至外存等待，变为就绪挂起状态；
  • 阻塞挂起状态的进程挂起期间可能因为重新具备了运行条件但内存不足由阻塞挂起态变为就绪挂起态；如果没有重新具备运行条件但内存有空闲，进程会被重新调入内存成为阻塞态；如果它重新具备了运行条件且内存又稍有空闲，再重新调入内存进入就绪态
  • 就绪挂起状态的进程挂起期间可能因为内存有空闲，重新被调入内存变为就绪态
• 低级调度（进程调度）：按照某种算法从就绪队列中选取一个进程，将处理机分配给它（这里进程调度的概念包括了进程的调度和切换过程）

2）进程调度的时机和方式

• 需要进行进程调度的情况：

  • 当前运行的进程主动放弃处理机：进程正常终止、进程异常终止、进程主动请求阻塞（如等待I/O）

    （非剥夺调度方式/非抢占方式，适合于早期批处理系统）

  • 当前运行的进程被动放弃处理机：分给进程的时间片用完、有更紧急的事要处理（如I/O中断）、有跟高级优先级的进程进入队列

    （剥夺调度方式/抢占方式，适合于分时操作系统和实时操作系统）

• 不能进行进程调度与切换的情况

  • 处理中断的过程中

  • 原子操作过程中

  • 操作系统内核程序临界区中

    （临界资源：一个时间段内只允许一个进程使用的资源，如某种内核数据结构这种内核临界资源、打印机这种普通临近资源）

    （临界区：访问临界资源的那段代码）

    （内核临界区：一般用来访问某种内核数据结构，会上锁，如由各就绪进程的PCB组成的就绪队列）

    （访问普通临界资源时可以进行进程调度与切换）

3）调度算法的评价指标

• CPU利用率：CPU忙碌时间占总时间的比例
• 系统吞吐量：单位时间内完成作业的数量
• 周转时间：从作业被提交给系统开始，到作业完成为止的时间（平均周转时间=所有作业周转时间之和 / 作业数）
• 带权周转时间：周转时间 / 作业实际运行时间（平均带权周转时间=所有作业带权周转时间之和 / 作业数）
• 进程等待时间：作业被调入内存后建立对应的进程，这个进程被建立起之后等待被CPU、I/O设备服务的时间（在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间）
• 作业等待时间：不仅要考虑建立进程后的等待时间，还要加上作业在被调入内存之前在外存后备队列中等待调度的时间（平均作业等待时间：所有作业等待时间之和 / 作业数量）
• 响应时间：用户提交请求到首次产生响应所用的时间

4）适用于早期批处理系统的调度算法

（主要关心对用户的公平性、平均周转时间、平均等待时间等指标，不关心响应时间，不区分任务紧急程度，对用户来说交互性很糟糕）

• 先来先服务（FCFS）：

  • 用于作业调度，看哪个作业先到达后备队列；用于进程调度看哪个进程先到达就绪队列；

  • 非抢占式算法；

  • 不会导致饥饿，某进程或作业不会长期得不到服务；

  • 常结合其他算法适用，在现在也扮演着很重要的角色

• 最短作业优先（SJF）：

  • 用于作业调度；用于进程调度时称为短进程优先算法（SPF）；

  • SJF和SPF都是非抢占式算法，执行完当前进程之后再进行调度；也有抢占式版本——最短剩余时间优先算法（SRTN），当新进程到达时需要进行调度，如果新到达进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前进程重新回到就绪队列，当一个进程完成时也需要进行调度；

  • SJF算法和SPF算法追求更少的平均等待时间、平均周转时间、平均带权周转时间，如果不是所有作业几乎同时到达，则SRTN的这三个指标更少；

  • 可能产生饥饿现象，还可能饿死；

• 最高响应比优先（HRRN）：

  • 综合考虑作业或进程的等待时间和要求服务时间，在每次调度时先计算各个作业或进程的响应比，选择响应比最高的作业或进程服务，响应比=(等待时间+要求服务时间) / 要求服务时间

  • 非抢占式算法，只有当前运行的作业或进程主动放弃处理机时才需要调度

  • 不会导致饥饿现象

5）适用于交互式系统的调度算法

• 时间片轮转调度算法（RR）：
  • 按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片，如果进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队，如果时间片太大，则会退化成先来先服务调度算法
  • 用于进程调度，只有作业被放入内存建立了相应的进程后，才能被分配处理机时间片
  • 抢占式算法，由时钟装置发出时钟中断来通知CPU时间片已到
  • 不会导致饥饿
• 优先级调度算法：
  • 每个作业或进程有各自的优先级，调度时选择优先级最高的作业或进程
  • 既可以用于作业调度，也可用于进程调度
  • 非抢占式版本：在当前进程主动放弃处理机时进行调度；抢占式版本：还需在就绪队列变化时检查是否会发生抢占，就绪队列未必只有一个，可以按照不同优先级来组织，还可以把优先级高的进程排在更靠近队头的位置，方便调度
  • 根据优先级是否可以改变，分为静态优先级和动态优先级两种；通常优先级系统进程优先级高于用户进程，前台进程优先级高于后台进程，I/O型进程，或称I/O繁忙型进程，比计算型进程优先级高，因为I/O设备可以和CPU并行工作；如果某进程在就绪队列中等待了很长时间，则可适当提升 其优先级，如果某进程占用处理机运行了很长时间，则可适当降低其优先级，如果发现一个进程频繁地进行I/O操作，则可适当提升其优先级
  • 适用于实时操作系统
  • 可能会导致饥饿
• 多级反馈队列调度算法：
  • 对之前所有调度算法的折中权衡，设置多级就绪队列，优先级从高到低，时间片从小到大，新进程到达时先进入第一级队列，执行完相应时间片后，进入下一级队列的队尾，如果已经在最低级队列，则放入原队列队尾，如果运行时有新的进程到达时，由于放在第一级队列优先级高，则会出现抢占处理机的情况，此时未完成的进程就会被放在原来级别队列的队尾，只有优先级高的队列为空时才执行优先级低的队列；可以灵活地调整对各类进程的偏好程度，如CPU密集型进程、I/O密集型进程，可以将因I/O而阻塞的进程重新放回原队列，这样I/O进程就可以保持较高优先级
  • 用于进程调度
  • 抢占式算法，实际应用时可能实现为非抢占式
  • 会导致饥饿的现象，如有源源不断的短进程到来

6）死锁的发生和处理

• 死锁发生条件

  • 互斥条件
  • 不可剥夺条件
  • 请求和保持条件
  • 循环等待条件

• 死锁发生时机

  • 对系统资源的竞争
  • 进程推进顺序非法
  • 信号量的使用不当

• 预防死锁（静态策略）：破坏死锁产生的四个必要条件的一个或几个，不允许死锁发生；

  • 破坏互斥条件：如采用SPOOLing技术，把独占设备在逻辑上改造成共享设备，如建立一个打印机输出进程，接收各进程的打印任务，依次打印；

    （但不是所有设备都能改造，有些还是基于安全性不能改造的，因此适用范围不广）

  • 破坏不可剥夺条件：方案一是当某个进程请求新的资源得不到满足时必须立即释放手里的所有资源；方案二是当某个进程需要的资源被其他进程占有时，可以由操作系统协助，将想要的资源强行剥夺，一般要考虑各进程的优先级；

    （实现起来较复杂；释放已获得的资源可能造成前一段工作失效，因此一般只适用于易保存和恢复是资源，如CPU；反复申请资源会导致增加系统开销；可能导致进程饥饿）

  • 破坏请求和保持条件：采用静态分配法，进程运行前一次性申请完它所需的全部资源，在资源未满足前不让它投入运行，一旦投入运行，这些资源就会一直归它所有

    （资源利用率低，也有可能导致某些进程饥饿）

  • 破坏循环等待条件：采用顺序资源分配法，首先给系统中资源进行编号，规定每个进程必须按照编号递增的顺序请求资源，一个进程只有占有了小编号资源时才能申请更大编号资源，有大编号资源的进程不能申请小编号资源

    （不方便增加新设备，要重新进行编号；进程实际使用资源的顺序可能和编号递增顺序不一致导致资源浪费；不同系统编号不一致会导致用户多次代码修改，编程麻烦）

• 避免死锁（动态策略）：用某种方法防止系统进入不安全状态，不允许死锁发生

  • 安全序列：如果系统按照这种序列分配资源，则每个进程都能顺利完成

  • 系统的安全状态：只要能找出一个安全序列，系统就处于安全状态，当然安全序列可能有多个，如果系统处于安全状态就一定不会死锁，如果处于不安全状态就有可能发生死锁

  • 避免系统进入不安全状态

    （银行家算法核心思想：在资源分配前预判这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求）

    • 长度为m的一维数组Available表示还有多少可用资源；n*m的Max矩阵表示各进程对资源的最大需求数；n*m的Allocation矩阵表示各进程分配了多少资源；Max-Allocation=Need矩阵表示各进程最多还需要多少资源；长度为m的一维数组Request表示此进程此次申请的各资源数
    • 检查这次申请是否超过了之前声明的最大需求数
    • 检查此时系统剩余可用资源是否还能满足这次请求
    • 试探着分配，更改各数据结构
    • 用安全性算法检查此次分配是否会导致系统进入不安全状态：检查当前剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的所有资源全部回收；不断重复上述过程，看最终是否能让所有进程都加入安全序列

• 死锁的检查和解除：允许死锁发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁

  • 死锁的检测
    • 资源分配图
    • 检测算法：算法首先从资源分配图中既不阻塞又不是孤点的进程开始，与寻找安全序列原理相同去消除请求边和分配边，如果能消除所有的边，就称这个图是可安全简化的，则此时一定没有死锁发生，否则此时就是发生了死锁，最终还连着边的那些进程就是处于死锁状态的进程
  • 死锁的解除
    • 资源剥夺法：挂起某些死锁进程放到外存，并抢占它的资源，将这些资源分配给其他死锁进程，但是应防止被挂起的进程长时间得不到资源而饥饿
    • 撤销进程法：或进程终止法，强制撤销部分甚至全部死锁的进程，并剥夺这些进程的资源，但是代价很大
    • 进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步，这就要求系统记录进程的历史信息，设置还原点，也不太容易实现
    • 决定对那个进程下手：考虑进程优先级、已执行多长时间、还要多久完成、进程已经使用了多少资源（为了尽快解除死锁，可以优先牺牲拥有资源数多的进程）、进程是交互式的还是批处理式的（为了不影响用户使用感受，可以优先牺牲批处理式的进程）

五、内存

1）程序与内存、存储保护

• 从写程序到程序运行

  • 编译：由编译程序将用户源代码编译成若干个目标模块，即把高级语言翻译为机器语言，实际上在生成机器指令时并不知道该进程的数据会被放在什么位置，所以编译生产的指令中一般不使用物理地址（绝对地址），一般使用逻辑地址（相对地址）

  • 链接：由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块

    • 静态链接：程序运行前，将各目标模块及它们所需的库函数链接成一个完整的可执行文件（装入模块），之后不再拆开
    • 装入时动态链接：将各目标模块装入内存时，边装入边链接
    • 运行时动态链接：程序执行中需要该目标模块时，才对它进行链接，这种方式便于修改和更新，便于实现对目标模块的共享

  • 装入：即装载，由装入程序将装入模块装入内存运行，这一步涉及逻辑地址向物理地址的转换

    • 绝对装入：编译时如果知道程序将放在内存中哪个位置，编译程序将产生绝对地址的目标代码，装入程序按照装入模块的地址将程序和数据装入内存，只适合单道程序环境，那时还没有操作系统，内存中同一时刻只会有一道程序运行，程序中使用的绝对地址可在编译或汇编时给出，也可由程序员直接赋予，通常情况下都是编译或汇编时再转换为绝对地址

    • 可重定位装入：也叫静态重定位，编译、链接后的装入模块的地址都是从0开始的，是逻辑地址，可根据内存情况将装入模块装入到内存的适当位置，装入时重定位，将逻辑地址转换为物理地址，要对其进行修改，地址变换是在装入时一次完成的，必须分配其要求的全部内存空间，如果没有足够内存，就不能装入该作业，作业一旦装入内存后，运行期间就不能再移动，也不能再申请内存空间，用于早期的多道批处理操作系统

    • 动态运行时装入：也叫动态重定位，编译、链接后的装入模块的地址都是从0开始的，是逻辑地址，装入程序把装入模块装入内存后，不会立即把逻辑地址转换为物理地址，不会对其修改，而是把地址转换推迟到程序真正要运行时才进行，当然也不会对其修改，系统会设置一个重定位寄存器，存放装入模块存放的起始地址，允许程序在内存中发生移动，只要修改重定位寄存器的值就行了，适合现代操作系统

      （其他优点：可将程序分配到不连续的存储区；在程序运行前只需装入部分代码即可投入运行，然后在程序运行期间可根据需要动态申请分配内存；便于程序段的共享，可以向用户提供一个比内存空间大得多的地址空间）

• 存储保护

  （让各个进程只能访问自己的内存空间，不能访问操作系统的，也不能访问其他进程的）

  • 在CPU中设置一对上、下限寄存器，存放进程的上、下限地址

  • 采用重定位寄存器（基址寄存器，存放进程起始物理地址）和界地址寄存器（限长寄存器，进程最大逻辑地址）进行越界检查

2）内存空间的管理

（即内存空间的分配与回收，记录那些内存区域已经被分配出去了，哪些又还空闲，分配时应该放哪里，进程运行结束后如何将进程占用的内存空间回收）

（内部碎片：分配给某进程的内存区域中有些部分没用上；外部碎片：内存中某些空闲分区太小难以利用）

• 连续分配管理

  • 单一连续分配：内存被分为系统区和用户区，但是内存中只能有一道用户程序

    （只能用于单用户单任务的操作系统，如早期PC操作系统MS-DOS，不一定采取内存保护，重启就好了）

    （有外部碎片）

  • 固定分区分配：将内存里的用户区分为若干固定大小的分区，每个分区只能装入一道作业，分区可以采取大小相等策略，也可以采取分区大小不等的策略，需要建立一个分区说明表，标注每块分区大小，起始地址、状态

    （当用户程序太大时，需要采用覆盖技术解决，会影响系统性能）

    （没有外部碎片，有内部碎片）

  • 动态分区分配：又称可变分区分配，不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，使分区大小正适合进程的需要

    • 记录内存使用情况：空闲分区表、空闲分区链

    • 分区的分配：修改空闲分区表或空闲分区链

      （涉及到的四种动态分区分配算法：空闲分区按地址递增的次序链接以便查找的首次适应算法、空闲分区按容量递增次序链接以便查找的最佳适应算法、空闲分区容量递减的次序链接以便查找的最坏适应算法、空闲分区以地址递增顺序链接成循环链表以便从上次的位置开始查找的邻近适应算法）

    • 分区的回收：修改空闲分区表或空闲分区链，注意将连续的空闲分区合并

    （没有内部碎片，有外部碎片，为了充分利用外部碎片，采用紧凑技术，将某些进程挪位，腾出足够内存空间给新的进程使用，所以装入方式应该选用动态重定位方式，不过紧凑技术的时间代价很高）

• 非连续分配管理

  • 基本分页存储管理

    （基本思想：把内存分为一个个相等的小分区，称为页框，再按照分区大小把进程拆分成一个个小部分，称为页面，页框与页面一一对应，页面分配时不按顺序，系统会用页表记录进程中每个页面在内存中的起始地址，页表通常装在连续的内存块中，进程的每一页对应页表里的一个页表项，每个页表项由页号和块号组成，页号从0开始，各页表项会连续地存放在内存中，每个页表项的长度是相同的，知道了该页表在内存中存放的起始地址，则目标页号的页表项存放地址就能算出来了，即其实页表项中页号是隐含的）

    （逻辑地址结构：为方便计算页号、页内偏移量，计算机一般将页面大小设置为2的K次方个存储单元，如果设置一个进程最多允许2的M次方个页面，这时分页存储管理的逻辑地址结构就是M位页号+K位页内偏移量，分页式存储用户进程地址空间是一维的）

    （地址转换：算出逻辑地址对应的页号，从页表中找出该页号对应页面在内存中的起始地址，然后算出逻辑地址在页面中的偏移量，就能算出物理地址在哪了）

    • 基本地址变换机构：通常会在系统中设置一个页表寄存器PTR，存放页表在内存中的起始地址F和页表长度，进程未执行时，页表的起始地址和页表长度放在进程控制块PCB中，当进程被调度时，操作系统内核就会把它们放到页表寄存器中，CPU只需要知道逻辑地址的值，就能完成地址变换
    • 具有快表的地址变换机构：如果执行了程序中某条指令，或访问了某个数据，那么不久后该数据很可能再次被访问，称为时间局部性；一旦程序访问了某个存储单元，不久后附近的存储单元也很有可能被访问到，称为空间局部性；快表，又称联想寄存器TLB，是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换过程；引入快表之后，先查快表，再查慢表，还要将在慢表中查到的页表项复制到快表中，若快表满了要对旧的页表项进行替换
    • 两级页表：单级页表占用内存空间过大，且要连续存储，违背了分页存储的思想；所以将页表分组，称为二级页表，每个内存块刚好放入一个二级页表，每个二级页表中的起始页号改成0，再将各二级页表离散地放到各个内存块中，这时需要为离散分配的二级页表建立一张页目录表，或称外层页表，顶层页表，用来存放二级页表的页号和内存块号，逻辑地址结构就变成了(M-K)位一级页号+K位二级页号+K位页面偏移量
    • 多级页表：原理与二级页表一样，原则是各级页表的大小不能超过一个页面的大小，即一个内存块的大小，以三级页表为例，这时逻辑地址结构变成了(M-2*K)位一级页号+K位二级页号+K位三级页号+K位页面偏移量；N级页表访问一个逻辑地址需要N+1次访存

  • 基本分段存储管理：按照程序自身逻辑关系划分为若干个段，每段从0开始编址，每段在内存中占据连续空间，但各段之间可以不相邻；分段系统的逻辑地址由段号+段内地址组成，段号位数决定了每个进程最多可以分为几个段，段内地址位数决定了每个段最大长度是多少；需要为每个进程建立一张段表，记录每段的长度和在内存中的起始地址，段表项由段号、段长、基址组成，各段表项长度是相同的，因此段号是隐含的，不占存储空间；与分页存储不同的是在查询到逻辑地址对应的段表项时，要加一个检查段内地址是否超过段长的操作

    （低级语言中程序员使用段名编程，由于是按逻辑功能划分的，用户编程更方便，程序可读性更高）

    （分页用户进程地址空间是一维的，程序员只需要给出一个记忆符就可以表示一个地址，而分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址）

    （分页是系统管理上的需要，完全是系统行为，对用户是不可见的，而分段主要为了更好地满足用户需求，对用户是可见的，用户编程时要显式地给出段名）

    （分段比分页更容易实现信息的共享和保护）

    （分段系统中也可以引入快表机构）

  • 段页式存储管理：分段+分页，将分段系统中逻辑地址结构段号+段内地址中的段内地址再分为页号加页内偏移量，系统会为每个进程建立一个段表，段表中的每一个段对应一个页表，因此一个进程对应一个段表，有可能对应多个页表；段表与分段式存储管理有所不同，每个段表项是由段号（隐含的）、页表长度、页表起始地址组成的，页表与分页式存储管理相同；在查询到逻辑地址对应的段表项时，要检查页号是否超过页表长度

    （段页式存储用户进程地址空间是二维的）

    （分段对用户是可见的，分页对用户是不可见的，属于系统自动的行为）

    （也可以引入快表机构，用段号和页号作为查询快表的关键字，若快表命中则仅需一次访存）

3）内存空间的扩充

• 覆盖技术：内存为程序分配一个固定区和若干覆盖区，常驻内存的程序段放在固定区，不常用的段需要时再调入内存，放在覆盖区用不到时调出内存，不需要同时用到的程序段共享一个覆盖区

  （必须由程序员声明覆盖结构，操作系统自动完成覆盖，对用户不透明，增加了用户编程负担，只用于早期的操作系统中）

  （在同一个程序或进程中进行）

• 交换技术：又称对换技术，内存空间紧张时，如经常发生缺页，系统将内存中某些比如优先级低的或阻塞的或驻留时间长的进程暂时换出外存，内存空间充裕时，再把外存中某些已具备运行条件的进程换入内存，即内存调度，也称中级调度，注意PCB不会被换出

  （具有对换功能的系统中，通常把磁盘空间分为文件区和对换区两部分，对换区采用连续分配方式，文件区采用离散分配方式）

  （在不同进程或作业间进行）

• 虚拟存储技术

  （虚拟技术，操作系统的虚拟性，解决物理内存不够的问题）

  （针对作业必须一次性装入内存导致大作业无法运行，多道程序并发度下降的问题）

  （根据局部性原理，进程在一段时间内可能只需要访问几个特定的页面，没必要让整个页表都常驻内存，可以把暂时用不到的信息换出到外存，用到时再调入内存）

  （虚拟内存的实际容量是受计算机的地址结构，即CPU的寻址范围，与内存外存容量之和限制的，最大容量就是计算机的地址结构，即CPU的寻址范围）

  （需要建立在非连续分配的内存管理方式之上）

  • 请求分页存储管理

    • 页表机制：页表增加了四个字段，变为请求页表，分别是状态位(是否已经调入内存)，访问字段(供置换算法选择换出页面时参考)，修改位(是否被修改)，外存地址(页面在外存中存放位置)
    • 缺页中断机构：访问一个页面时检查其状态位，若页面不在内存，便产生一个缺页中断(属于内中断中故障类，一条指令可能产生两次中断)，然后由操作系统的缺页中断处理程序处理中断，将缺页的进程阻塞，放入阻塞队列，若内存中有空闲块，则为进程分配一个空闲块，并修改请求页表相关内容，若没有空闲块，则由页面置换算法选择淘汰一个页面，并修改淘汰页面对应的请求页表项，如果该页面被修改过，还要将其写会外存，并将空出的内存块分配给进程，修改请求页表中对应的页表项，调页完成后再将其唤醒，放回就绪队列
    • 地址变换机构：可以采用快表+慢表机制，在具有快表机构的请求分页系统中，访问一个逻辑地址时，先查快表，若未命中，查慢表，若发现想要的页面不在内存，则进行调页操作，并把调入的页面对应页表项直接加入快表，方便以后快速查询；页面被调出内存后对应的页表项也会从快表中删除，所以快表中的页表项对应的页面一定在内存中，因此，只要快表命中，则页表项状态位的检查也免了；当对快表中的页表项进行替换时，需要将有所修改的页表项写回内存中的慢表，而且只有替换时才需要写；当内存中的页面被调出到外存时，如果对应页表项的修改位表明有修改，这时需要把内存中的页面写回外存，若没有修改，则不用写回

  • 请求分段存储管理

  • 请求段页式存储管理

  • 页面置换算法

    • 最佳置换算法OPT：每次选择淘汰的页面将是以后永远不使用，或者在最长时间内不再被访问的页面，前提是需要已知之后要访问的页面序列，因此无法实现
    • 先进先出置换算法FIFO：每次选择淘汰的页面是最早进入内存的页面，需要把调入内存的页面根据调入顺序排成一队，需要换出时选择队头页面即可，队列的最大长度取决于系统为进程分配了多少内存块；会发生分配的内存块变多但缺页次数也变多的Belady异常，因此算法性能最差
    • 最近最久未使用置换算法LRU：每次淘汰的页面是最近最久未使用的页面，需要在每个页表项加上访问字段，记录该页面自上次访问以来经历的时间；实际实现需要专门的硬件支持，虽然算法性能好，但实现困难，开销大
    • 时钟置换算法CLOCK（或最近未用算法NRU）：为每个页面对应的页表项设置一个访问位，再将内存中的页面通过指针链接成一个循环队列，当某页被访问时，将访问位标为1，当需要淘汰页面时，若访问位标记为0，则将该页面换出，如果是1，则不换出，将其修改为0，继续检查下一个页面，因此CLOCK算法淘汰页面最多扫描两轮；算法开销小，但未考虑页面是否被修改过
    • 改进型的时钟置换算法：第一轮扫描不修改任何标志位，淘汰第一个没有被访问过并且没有被修改过的页面，若第一轮淘汰失败，第二轮扫描淘汰第一个没有被访问过但是有修改过的页面，且要将扫描过的页面访问位修改为0未访问，若第二轮淘汰失败(这时所有已经被访问过的页面标志都已经变为未访问)，则第三轮扫描淘汰第一个未访问且未修改的页面，本轮不修改任何标志位，若第三轮淘汰失败，则第四轮扫描淘汰第一个未被访问但是修改过的页面，改进型CLOCK置换算法淘汰页面最多扫描四轮；算法开销小，性能也不错

  • 页面分配、置换策略

    （驻留集：请求分页存储管理中给进程分配的物理块集合）

    （锁定页面：系统会锁定一些重要页面，这些页面不能被置换出外存）

    • 固定分配局部置换：操作系统为每个进程分配一组固定数目的物理块，进程运行期间不再改变；发生缺页时，只能选进程自己的物理块进行置换；采用这种方法在刚开始就确定应为每个进程分配多少物理块比较困难
    • 可变分配全局置换：先为每个进程分配一定数目的物理块，进程运行期间可根据情况做适当增加或减少；发生缺页时，可以将别的进程未锁定页面置换到外存，再将空出的物理块分配给缺页的进程；采用这种方法会导致被选中调出页面的进程缺页率增加
    • 可变分配局部置换：先为每个进程分配一定数目的物理块，进程运行期间可根据情况做适当增加或减少；发生缺页时，只能选进程自己的物理块进行置换，如果进程运行中频繁缺页，则系统会为进程多分配几个物理块，如果缺页率特别低，就会适当减少分配给该进程的物理块

  • 页面调入策略

    • 预调页策略：根据空间局部性原理，预测不久后可能访问到的页面，将它们预先调入内存，但预测成功率只有50％，主要用于进程首次调入，由程序员指出应先调入哪些部分（运行前调入）
    • 请求调页策略：进程运行期间发现缺页时才将所缺页面调入内存，I/O开销大（运行时调入）

  • 从何处调入页面

    • 外存对换区：采用连续分配方式，读写速度快，若干系统拥有足够的对换区空间，那么在进程运行前，需将进程相关数据从文件区复制到对换区，页面的调入调出都是在内存和对换区进行的
    • 外存文件区：采用离散分配方式，读写速度慢，凡是不会被修改的数据都直接从文件区调入，对于可能被修改的部分，换出时写回对换区，下次需要时再从对换区调入
    • UNIX方式：运行前进程所需数据全部在文件区，未使用过的页面都可以从文件区调入，被使用过的页面换出时写回对换区，下次需要时从对换区调入

  • 防抖动防颠簸：工作集是指在某段时间间隔里，进程实际访问页面的集合，系统根据进程工作集的大小决定给进程分配多少内存块，即根据工作集的大小确定进程驻留集的大小，一般来说，驻留集的大小不能小于工作集的大小，否则进程运行过程中将频繁缺页；还可以根据进程近期访问的页面集合(工作集)来设计一种页面置换算法，淘汰不在工作集中的页面

六、文件管理

1）文件系统层次结构

• 用户接口（文件的基本操作）：文件系统需要向上层用户提供一些简单易用的功能接口，这层就是用于处理用户发出的系统调用请求，如Read、Write、Open、Close等系统 调用
• 文件目录系统（文件目录）：用户通过文件路径来访问文件，这一层需要根据用户给出的文件路径找到相应的FCB或索引结点，所有和目录、目录项相关的管理工作都在本层完成，如管理活跃的文件目录表、管理打开文件表等
• 存取控制模块（文件保护）：为了保证文件数据的安全，需要验证用户是否具有访问权限，这一层主要完成文件保护相关功能
• 逻辑文件系统与文件信息缓冲区（文件逻辑结构）：如果采用索引文件这种逻辑结构的话，会为文件当中的各个记录建立一个索引表，为了查询这些记录对应的逻辑地址，就需要查询索引表，而在查询文件索引表之前，就需要将索引表调入到内存的文件信息缓冲区
• 物理文件系统（文件物理结构）：找到记录对应的逻辑地址之后，这一层把逻辑地址转换为物理地址
  • 辅助分配模块（文件存储空间管理）：如果需要向文件中添加或删除一些记录的话，就需要辅助分配模块为文件分配或回收一些物理块
  • 设备管理模块（磁盘管理）：直接与硬件交互，做所有和硬件相关的管理工作，如分配设备、分配设备缓冲区、磁盘调度、启动设备、释放设备等

2）文件基本操作

• 创建文件(Create系统调用)、删除文件(Delete系统调用)、打开文件(open系统调用：不会将文件数据写入内存)、关闭文件(Close系统调用)、读文件(read系统调用：会将文件数据写入内存)、写文件(write系统调用)
• 打开文件表：
  • 系统打开文件表：用户打开文件后会将对应的目录项复制到内存中的“系统打开文件表”中，并将对应表目的编号(也称文件描述符)返回给用户，之后用户使用打开文件表的编号来指明要操作的文件，就不用每次都重新查目录了；系统文件表中还有一个打开计数器字段，用于记录对应文件当前被几个进程打开了，方便实现某些文件管理功能
  • 进程打开文件表：记录进程打开文件有哪些，还有记录当前进程对此文件的读写操作进行到了什么位置的读写指针、访问权限、系统打开文件表索引号

3）文件目录

• 文件控制块：每个文件夹对应一个目录文件，目录文件中的一个文件目录项就是一个文件控制块FCB，FCB中包含了文件的基本信息、存取控制信息、使用信息，最重要最基本的还是文件名、文件存放的物理地址
• 目录结构
  • 单级目录结构：不允许文件重名
  • 两级目录结构：主文件目录+用户文件目录，主文件目录记录用户名及相应用户文件目录的存放位置，用户文件目录由该用户的文件FCB组成，运行不同用户的文件重名
  • 多级目录结构：又称树形目录结构，不同目录下文件可以重名，用户或用户进程想要访问某个文件时要用文件路径名标识文件，如果从根目录开始一层一层地找到下一级目录，要进行多次读磁盘的I/O操作，根据空间局部性，可以将当前打开的目录对应的目录表设置为当前目录，当用户想要访问某个文件时，使用从当前目录出发的相对路径
  • 无环图目录结构：在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图，便于实现多个用户间的文件共享，不同用户可以用不同文件名指向同一文件或目录
    • 基于索引结点的共享方式（硬链接）：将自己的目录项直接指向共享文件，并在共享文件的索引结点中设置一个链接计数变量count(一个共享计数器)，表示链接到本索引结点上的用户目录项数，记录此时有多少个用户共享该节点；为了避免一个用户删除文件导致其他用户也不可见的情况，用户删除文件时，只是删除该用户的FCB，并使共享计数器减1，而不会直接删除共享结点
    • 基于符号链的共享方式（软链接或符号链接）：并不是将自己的目录项直接指向共享文件，而是创建了一个Link类型的文件，记录了共享文件的存放路径，操作系统根据路径查找目录文件里对应的目录项找文件，类似于Windows操作系统的快捷方式，当然非共享文件也可以创建快捷方式；软链接方式访问共享文件时要查询多级目录，会有多次磁盘I/O操作，因此访问速度比硬链接慢
• 索引结点（对文件控制块的优化）：将文件控制块中除了文件名之外的文件描述信息都放到索引结点中，FCB就简化成了文件名+索引结点指针，这样目录表所占空间就减小很多，文件查找时可以减少I/O操作启动磁盘的次数，提升文件查找效率，当找到文件名对应的目录项时，才需要将索引结点调入内存，根据其中的存放位置信息找到文件，存放在外存中的索引结点称为磁盘索引结点，当索引结点调入内存后称为内存索引结点，相比之下内存索引结点中需要增加一些信息，比如文件是否被修改、此时有几个进程正在访问该文件等

4）文件保护

• 口令保护：为文件设置口令，口令一般存放在文件对应的FCB或索引结点中；保存口令空间开销不大，验证口令时间开销也很小，但是正确是口令存放在系统内部，不够安全
• 加密保护：使用某个密码对文件进行加密，如异或加密，系统中保存的是加密后的文件数据，而不是文件原始数据；保密性强，不需要在系统中存储密码，但编码译码要花费一定时间
• 访问控制：每个文件的FCB（或索引结点）中增加一个访问控制表ACL，该表中记录了各个用户可以对该文件执行哪些操作，如读、写、执行(将文件装入内存并允许)、添加、删除、列表清单(列出文件名和文件属性)；如果计算机有很多用户，那么访问控制表可能很大，可以用精简的访问列表解决这个问题，以组为单位标记各组用户可以对文件执行哪些操作，如系统管理员、文件主、文件主的伙伴、其他用户等，权限有完全控制、执行、修改、读取、写入等，系统还需要管理分组的信息，如把用户添加到相应分组、更换用户的分组等；实现灵活，可以实现复杂的文件保护功能

5）文件逻辑结构

• 无结构文件：文件内部数据就是一系列二进制流或字符流组成，又称流式文件，如.txt文件

• 有结构文件：又称记录式文件，每条记录由若干数据项组成，根据各条记录的长度是否相等，又可分为定长记录和可变长记录

  • 顺序文件：文件中的记录逻辑上一个接一个地顺序排列

    （记录可以是定长的也可以是可变长的）

    （记录之间的顺序可以是与关键字无关的串结构，如按记录存入的时间顺序，也可以是按关键字顺序排列的顺序结构）

    • 物理上顺序存储(物理上相邻)：可变长记录无法实现随机存取，每次只能从第一个记录开始依次往后查找；定长记录可实现随机存取，其中串结构无法快速找到某关键字对应的记录，顺序结构可以快速找到某关键字对应的记录，如折半查找，但顺序结构增加/删除一个记录比较困难，实际应用当中，操作系统会管理一个日志文件记录修改信息，每隔一段比较长的时间，再将这些修改统一合并到外存的文件中
    • 物理上链式存储(物理上不一定相邻)：无论是定长还是可变长记录，无论是串结构还是顺序结构，都无法时间随机存取，每次只能从第一个记录依次往后找

  • 索引文件结构：为了加快可变长记录文件的检索速度，可以为每个文件建立一张索引表，索引表在物理上连续存放，而文件中的记录在物理上可以离散存放，索引表中每个索引项由索引号+长度+指针组成，可以将关键字作为索引号内容，方便按照关键字快速查找，另外可以用不同的关键字建立多张索引表

  • 索引顺序文件结构：建立索引表时一个索引表项对应文件的一组记录，索引表中每个索引项由键和地址组成，其中地址是文件对应分组的地址，如按照学生姓名开头字母进行分组，这样可以大大减少平均查找次数，文件分组内的记录不需要按关键字排序，索引表中的索引项也不需要按关键字顺序排列，这样极大地方便新表项的插入

  • 多级索引顺序文件结构：为了进一步提高检索效率，可以为顺序文件建立多级索引表，如两级索引表：顶级索引表+低级索引表，顶级索引表中索引项的地址是对应低级索引表的地址，低级索引表中索引项的地址是文件对应分组的地址

6）文件物理结构

（外存文件的逻辑地址可以表示为(逻辑块号,块内地址)的形式）

• 连续分配：要求每个文件在磁盘上占有一组连续的块，文件目录中记录存放的起始块号和长度，物理块号=起始块号+逻辑块号；支持顺序访问和随机访问；连续分配的文件在顺序读/写时速度最快；不方便文件拓展；紧凑技术处理磁盘碎片耗费时间代价很大
• 链接分配
  • 隐式链接：文件目录中记录了文件存放的起始块号和结束块号，也可增加一个字段表示文件长度，除文件的最后一个磁盘块之外，每个磁盘块都会保存指向下一个盘块的指针，这些指针对用户是透明的；方便文件拓展，不会有碎片问题；只支持顺序访问，不支持随机访问
  • 显式链接：把用于链接文件各物理块的指针显式地存放在一张文件分配表FAT中，其中每个表项由物理块号+下一块组成，表项都是定长的，所以物理块号是隐含的；一个磁盘仅需要设置一张FAT就够了，开机时将FAT读入内存并常驻内存；支持顺序访问，也支持随机访问，且块号转换过程不需要访问磁盘，因此相对于隐式链接，访问速度快很多；且也方便文件拓展，不会有碎片问题；不过文件分配表要占据一定的存储空间
• 索引分配：允许文件离散地分配在各个磁盘中，系统会为每个文件建立一张索引表，记录文件各个逻辑块对应的物理块，类似于内存中的页表，目录文件中需记录文件的索引块(索引表)存放位置，索引表表项由逻辑块号+物理块号组成，其中逻辑块号是隐含的，可以支持随机访问，也很容易实现文件拓展；但索引表需要占用一定的存储空间
  • 链接方案：如果索引表太大，一个磁盘块放不下，可以将多个索引块链接起来存放，因为只支持顺序访问，所以此时查找效率低
  • 多层索引：类似于多级页表，各层索引表大小不能超过一个磁盘块，如果要访问的是前几个数据块，仍然需要多次读磁盘操作
  • 混合索引：一个文件的顶级索引表中，既包含直接地址索引，又包含一级间接索引，还包含两级间接索引

7）文件存储空间管理

• 存储空间的划分与初始化：将物理磁盘划分为一个个文件卷，每个文件卷(磁盘分区)分为目录区(主要存放文件目录信息FCB，磁盘存储空间管理信息空闲表、位示图、超级块等)和文件区(存放普通文件数据)；有的系统还支持超大型文件，由多个物理磁盘组成一个文件卷
• 几种管理方法
  • 空闲表法：每个表项由每个空闲区间的起始盘块号+盘块数组成，适用于文件物理结构是联系分配的场景，为文件分配磁盘块时可采用首次适应、最佳适应、最坏适应等算法
  • 空闲链表法
    • 空闲盘块链：以盘块为单位组成一条空闲链，空闲盘块中存储着下一个空闲盘块的指针，操作系统保存着链头、链尾指针；为一个文件分配多个磁盘块时可能要重复多次操作；适用于离散分配的物理结构
    • 空闲盘区链：以盘区为单位组成一条空闲链，空闲盘区中第一个盘块记录了盘区的长度、下一个盘区的指针；为文件分配磁盘块时，可以采用首次适应、最佳适应算法从链头开始检索，若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件；适用于连续分配、离散分配的物理结构
  • 位示图法：一般用连续的字来表示，字中每一位对应一个盘块，可以用(字号,位号)或(行号,列号)对应一个盘块号；适用于连续分配、离散分配的物理结构
  • 成组链接法：空闲表法、空闲链表法由于空闲表、空闲链表可能过大，不适用于大型文件系统，UNIX系统采用了成组链接法对磁盘空闲块进行管理，文件卷的目录区中专门用一个磁盘块作为超级块，系统启动时需要将超级块读入内存，并且要保证内存与外存中的超级块数据一致，超级块中第一项记录着第一组空闲盘块数，其他项每项记录第一组的一个空闲块号，第二项对应的磁盘块中还需要记录下一组空闲盘块的信息(下一组空闲盘块数+下一组各空闲块号)，以此类推，在倒数第二组盘块的第一个盘块中本应记录下一组第一个盘块号位置的地方要增加一个-1标志位，代表再下一个分组已经是最后一个分组了；成组链接法中每组盘块的数量是有一个最大值的，而且因为倒数第二组增加了标志位，所以最后一个分组的最大盘块数要比其他盘块数少1的；为文件分配磁盘块时，从第一个分组的最后一个磁盘块开始，如果一个分组的磁盘块全部被分配出去，还需要将它第一个磁盘块中存放的下一组磁盘块的信息复制到超级块中；磁盘块回收时，如果第一组磁盘块还没满的话，就插入到第一个分组的组尾，如果第一组已满，则将新回收的块作为一个新的分组，将超级块中的数据复制到新的分组的第一个磁盘块中，让之前的第一组作为新分组的下一组，超级块中的数据修改成新分组的信息，这时新分组就成了第一组

8）磁盘管理

• 磁盘的结构
  • 物理地址：一个盘片可能对应两个盘面，每个盘面有若干环形磁道，整个盘面分成若干扇区，所有盘面相同位置的磁道组成一个柱面，可用（柱面号，盘面号，扇区号）来定位任意一个磁盘块，对应外存的物理块
  • 读写数据：先找柱面，再激活磁头找到盘面，在旋转磁盘找到扇区，一次磁盘读写操作所需时间=寻道时间(启动磁臂、移动磁头所花时间)+延迟时间(将目标扇区转到磁头下面所花时间)+传输时间(读写数据花费时间)
  • 磁盘分类 ：活动头磁盘和固定头磁盘、可换盘磁盘和固定盘磁盘
• 磁盘调度算法
  • 先来先服务算法FCFS
  • 最短寻找时间优先算法SSTF：保证每次寻道时间最短，但不能保证总的寻道时间最短；可能产生饥饿现象
  • 扫描算法SCAN：或称电梯算法，只有磁头移动到最外侧磁道的时候才往内移动，移动到最内侧时才往外移动；不会产生饥饿现象
  • LOOK调度算法：SCAN算法的改进版，如果磁头移动方向上已经没有别的请求了，就可以立即改变磁头移动方向；不会产生饥饿现象
  • C-SCAN算法：解决SCAN算法对于各个位置磁道的响应频率不均的问题，规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动到起始端而不处理任何请求；不会产生饥饿现象
  • C-LOOK算法：如果磁头移动方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置；不会产生饥饿现象
• 减少磁盘延迟时间的方法：采用(柱面号,盘面号,扇区号)的物理地址结构，使读取地址连续的磁盘块时减少移动磁头的次数；由于磁头读入一个扇区数据后需要一小段时间处理，如果逻辑上相邻的扇区在物理上也相邻，那么连续读入逻辑上相邻的几个扇区，就需要转动好几圈磁盘，因此，对盘面采用交替编号的策略，让逻辑上相邻的扇区在物理上有一定间隔，而且采用相邻盘面之间错位命名的方法，可以使读取连续的扇区和连续的盘面所需延迟时间更小
• 磁盘的管理
  • 磁盘初始化
    • 低级格式化(物理格式化)，将磁盘的各个磁道划分为扇区；一个扇区通常可分为头、数据区域、尾三个部分组成，管理扇区所需的各种数据结构一般放在头、尾两个部分，包括扇区校验码，用于检验扇区中数据是否发生错误
    • 磁盘分区：每个分区由若干柱面组成
    • 逻辑格式化：创建文件系统，包括创建文件系统根目录、初始化存储空间管理所用的数据结构，如位示图、空闲分区表
  • 引导块：计算机开机时需要进行一系列初始化的工作，这些初始化工作是通过执行初始化程序(自举程序)完成的；为了保证自举程序的可修改性，ROM中只存放很小的自举装入程序，完整的自举程序放在磁盘的启动块(引导块/启动分区)上，启动块位于磁盘的固定位置；开机时计算机先运行自举装入程序，通过执行该程序就可以找到引导块，并将完整的自举程序读入内存，完成初始化；拥有启动分区的磁盘称为启动磁盘或系统磁盘，如C盘
  • 坏块的管理
    • 对于简单的磁盘，可以在逻辑格式化时，对整个磁盘进行坏块检查，标明哪些扇区是坏扇区，比如在文件分配表FAT上标明，这种方式中，坏块对操作系统不透明
    • 对于复杂的磁盘，磁盘控制器(磁盘设备内部一个硬件部件)会维护一个坏块链表，在磁盘出厂前进行低级格式化(物理格式化)时就将坏块链进行初始化，还会保留一些备用扇区用磁盘控制器替换坏块，这种处理方式中，坏块对操作系统透明

七、I/O设备

1）I/O设备

• I/O设备分类

  • 按使用特性分类

    • 人机交互类外部设备：数据传输速度慢，鼠标、键盘、打印机等
    • 存储设备：数据传输速度快，移动硬盘、光盘等
    • 网络通信设备：数据传输速度介于两者之间，调制调解器等

  • 按传输速率分类

    • 低速设备：传输速率为每秒几个到几百字节，如鼠标、键盘等
    • 中速设备：传输速率为每秒数千至上万个字节，如激光打印机等
    • 高速设备：传输速率为每秒数千字节至千兆字节，如磁盘等

  • 按信息交换的单位分类

    • 块设备：传输速率较高，可寻址，即可随机地读/写任一快
    • 字符设备：传输速率较慢，不可寻址，在输入/输出时常采用中断驱动方式

• I/O设备组成

  • 机械部件：执行具体I/O操作，如鼠标/键盘的按钮、显示器的LED屏、移动硬盘的磁臂、磁盘盘面

  • 电子设备：即I/O控制器，又称设备控制器，用于实现CPU对I/O设备的控制，通常是一块插入主板扩充槽的印刷电路板

    • CPU与控制器的接口：用于实现CPU与控制器之间的通信，包含一个或多个数据寄存器、控制寄存器、状态寄存器等，且这些寄存器都要有相应的地址，方便CPU操作，有的计算机会让这些寄存器占用内存地址的一部分，称为内存映像I/O，另一些计算机则采用I/O专用地址，即寄存器独立编址(需要设置专门的指令来实现对控制器的操作，一台计算机可以有多个I/O控制器，一个I/O控制器可以有多个寄存器，所以要在指令中指明各寄存器的地址和各控制器的编号)；CPU通过控制线发出命令，通过地址线指明要操作的设备，通过数据线来取出或输入数据

    • I/O逻辑：负责接收和识别 CPU的各种命令(如地址译码)，然后翻译成 具体的设备能够明白的命令并发送给设备

    • 控制器与设备的接口：用于实现控制器与设备之间的通信，一个I/O控制器有可能会控制多个具体的I/O设备，有多个控制器与设备的接口

• I/O控制器功能

  • 接受和识别CPU发出的命令：如CPU发来的read/write命令，I/O控制器中会有相应的控制寄存器来存放命令和参数
  • 向CPU报告设备的状态：会有相应的状态寄存器，用于记录I/O设备的当前状态，如1表示空闲，0表示忙碌
  • 数据交换：设置相应的数据寄存器，输出时用于暂存CPU发来的数据，之后由设备控制器传送给设备，输入时用于暂存设备发来的数据，之后CPU从中取走
  • 地址识别：I/O控制器通过CPU提供的地址来判断CPU要读/写的是哪个寄存器

• I/O控制方式

  • 程序直接控制方式：CPU向控制器发出读命令，设备启动，状态寄存器设为1未就绪；程序直接控制方式就是轮询检查控制器的状态，其实就是不断执行程序的循环，若状态位一直是1未就绪，说明设备还没准备好要输入的数据，于是CPU会不断地轮询；输入设备准备好数据后将数据传给控制器，并报告自身状态，控制器将输入的数据放到数据寄存器中，并将状态寄存器改为0已就绪；当CPU发现设备已就绪，即可将数据寄存器中的内容读入CPU寄存器中，再把CPU寄存器中的内容放入内存；每次读/写一个字，因此需要CPU多次发出命令
  • 中断驱动方式：CPU发出读/写命令后，将等待I/O的进程阻塞，切换到其他进程，CPU会在每个指令周期末尾检查中断；中断处理过程中需要保存、恢复进程的运行环境，导致时间开销大，降低系统性能，但是能让CPU与I/O设备并行工作，CPU利用率得到明显提升，但是由于每次读/写一个字，要发生很多次中断，频繁的中断处理会消耗较多的CPU时间
  • DMA方式：直接存储器存取方式，DMA控制器，I/O控制器的一种，主要用于块设备的I/O控制，一次传送一个块或多个连续的块，且这些块读入内存后也必须是连续存放的，DMA方式传送数据不再经过CPU，而是直接从设备放入内存，或从内存直接输出到设备，仅在传送一个或多个数据块的开始和结束时，才需要CPU干预，DMA控制器会根据CPU提出的要求完成数据的读/写工作，其实过程中还是一个字一个字地传送的，整块数据传输完成后，才会向CPU发出中断信号；CPU与I/O设备的并行性得到提升，但是CPU每发出一条I/O指令只能读写一个或多个连续的数据块
    • 主机-控制器接口：包含数据寄存器DR、内存地址寄存器MAR、数据计数器DC、命令/状态寄存器CR等
    • I/O控制逻辑
    • 块设备-控制器接口
  • 通道控制方式：一种硬件，弱鸡版CPU，可以识别并执行一系列通道指令，一台计算机可以有多个通道，一个通道可以控制多个I/O控制器，一个I/O控制器可以控制多个I/O设备；CPU向通道发出I/O指令，指明通道程序(任务清单，其中指明了要读入/读出多少数据，读/写的数据应放在内存什么位置等信息)在内存中的位置，并指明要操作的是哪个I/O设备，通道从内存中读取并执行通道程序，完成后向CPU发出中断信号，之后由CPU对中断进行处理；CPU干预频率极低，利用率极高，每次读/写一组数据块，存储地址可以是连续的，可以是不连续的；但实现复杂，需要专门通道硬件的支持

2）I/O软件系统

• 用户层软件：实现了与用户交互的接口，用户可直接使用该层提供的、与I/O操作相关的库函数对设备进行操作，用户层软件将用户请求翻译成格式化的I/O请求，并通过系统调用请求操作系统内核的服务，如print(“hello,world!”);会被翻译成等价的write系统调用，用户层软件也会在系统调用时填入相应参数。

  • 假脱机技术（SPOOLing技术）：用软件的方式模拟脱机技术，需请求磁盘设备的设备独立性软件的服务
    • 脱机输入/脱机输出技术：批处理阶段引入，用外围控制机将慢速输入设备的数据先输入到更快速的磁带上，之后再读入主机，输出时也类似（脱离主机的控制进行输入和输出）
    • SPOOLing系统：在磁盘上开辟出两个存储区域输入井和输出井，输入井模拟脱机输入时的磁带，输出井模拟脱机输出时的磁带；内存中输入进程模拟脱机输入时的外围控制机，输出进程模拟脱机输出时的外围控制机，与用户进程并发执行，因此必须要有多道程序技术的支持；内存中的输入缓冲区用于暂存从输入设备输入的数据，之后再转存到输入井中，输出缓冲区用于暂存从输出井送来的数据，之后传送到输出设备
    • SPOOLing技术的应用：（共享打印机的实现）在磁盘输出井中为用户进程申请一个空闲缓冲区，用户进程会将要打印的数据从内存送入磁盘的输出井中，然后为用户进程申请一张空白的打印请求表，并将用户的打印请求如打印数据存放位置等信息填入表中，再将该表挂到假脱机文件队列上，打印机空闲时，输出进程会从文件队列的队头取出一张打印申请表，并根据表中要求将要打印的数据从磁盘的输出井传送到内存的输出缓冲区，再输出到打印机进行打印

• I/O核心子系统：操作系统内核部分

  • 设备独立性软件：

    • 向上层提供统一的调用接口（如read/write系统调用）

    • I/O调度：用某种算法确定一个好的顺序来处理各个I/O请求，也可以用先来先服务算法、优先级算法、短作业优先算法等来确定I/O调度顺序

    • 设备保护：不同用户对各个设备的访问权限是不一样的，如只读、读写等，UNIX系统将外部设备抽象成一种特殊的文件，每个设备也会有对应的FCB，用户可以使用与文件相同的方式根据FCB中记录的信息来判断该用户是否有相应的访问权限

    • 差错处理：对一些设备的错误进行处理

    • 设备的分配与回收

      1. 设备分配时应考虑的因素：设备的固有属性(独占设备、共享设备、虚拟设备)、设备分配算法(先来先服务、优先级高者优先、短任务优先等)、设备分配中的安全性(为进程分配一个设备后就将其阻塞的安全分配方式、进程被分配设备后能继续执行并且之后还可以发出新的I/O请求直到某个I/O请求得不到满足时才将其阻塞的不安全分配方式)
      2. 分配方式：进程运行前为其分配全部所需资源的静态分配、进程运行过程中动态申请设备资源的动态分配
      3. 设备分配管理中的数据结构
         • 系统设备表SDT：记录了系统中全部设备的情况，每个设备对应一个表目，每个表目由设备类型、设备标识符(物理设备名)、设备控制表DCT、驱动程序入口构成
         • 设备控制表DCT：系统为每一个设备配置一张DCT，用于记录设备情况，设备控制表由设备类型、设备标识符(物理设备名)、设备状态、指向控制器表的指针、重复执行次数或时间(当重复执行多次I/O操作仍不成功后才认为此次I/O失败)、设备队列的队首指针(指向正在等待该设备的由进程PCB组成的阻塞进程队列)组成
         • 控制器控制表COCT：每个设备控制器对应一张COCT，操作系统根据COCT的信息对控制器进行操作和管理，控制器控制表由控制器标识符(各控制器的唯一ID)、控制器状态、指向通道表的指针、控制器队列的队首指针、控制器队列的队尾指针(指向正在等待该控制器的由进程PCB组成的阻塞进程队列)组成
         • 通道控制表CHCT：每个通道会对应一张CHCT，操作系统根据CHCT的信息对通道进行操作和管理，通道控制表由通道标识符(各通道唯一ID)、通道状态、与通道连接的控制器表首址指针(可通过该指针找到该通道管理的所有控制器相关信息)、通道队列的队首指针、通道队列的队尾指针(指向正在等待该通道的由进程PCB组成的阻塞进程队列)组成
         • 逻辑设备表LUT：建立了逻辑设备名与物理设备名之间的映射关系，每一个表项由逻辑设备名+物理设备名+驱动程序入口地址构成；某用户进程第一次使用设备时使用逻辑设备名向操作系统发出请求，操作系统根据用户指定的设备类型(逻辑设备名)查找系统设备表，找到一个空闲设备分配给进程，并在LUT中增加相应表项，如果之后用户进程再次通过相同的设备名请求使用设备，则操作系统通过LUT表就能知道用户进程实际要使用的是哪个物理设备了，并且也能知道该设备的驱动程序入口地址
      4. 设备分配的步骤
         • 根据进程请求的逻辑设备名(其实就是设备类型)查找SDT
         • 查找SDT找到用户进程指定类型的、并且空闲的设备，将其分配给该进程，操作系统在逻辑设备表LUT中新增一个表项
         • 根据DCT找到COCT，若控制器忙碌就将进程PCB挂到控制器等待队列中，不忙碌就将控制器分配给进程
         • 根据COCT找到CHCT，若通道忙碌就将该进程PCB挂到通道等待队列中，不忙碌就将通道分配给进程
         • 只有设备、控制器、通道三者都分配成功时，这次设备才算分配成功，之后便可启动I/O设备进行数据传送

    • 设备缓冲区管理（缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可以利用内存作为缓冲区，使用硬件作为缓冲区的成本较高，容量也较小，一般仅用于对速度要求非常高的场合，如联想寄存器存放页表项的副本）（缓冲区可以缓和CPU与I/O设备之间速度不匹配的矛盾、减少对CPU的中断频率以放宽对CPU中断响应时间的限制、解决数据粒度不匹配的问题、提高CPU与I/O设备之间的并行性）

      1. 单缓冲区：假设某用户进程请求某种块设备读入若干块的数据，系统会在内存中为其分配一个缓冲区，当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据取出，当缓冲区为空时，可以往缓冲区冲入数据，但必须把缓冲区充满后，才能从缓冲区把数据传出
      2. 双缓冲区：假设某用户进程请求某种块设备读入若干块的数据，系统会在内存中为其分配两个缓冲区，每个缓冲区的工作机制与单缓冲相同；两设备通信时可以配置缓冲区用于数据的发送和接收，可以用双缓冲区实现数据的双向传输；管道通信中的管道其实就是缓冲区，要实现数据的双向同时传输，必须设置两个管道
      3. 循环缓冲区：将多个大小相等的缓冲区链接成一个循环队列，其中in指针指向下一个可以冲入数据的空缓冲区，out指针指向下一个可以取出数据的满缓冲区
      4. 缓冲池：由系统中共用的缓冲区组成，这些缓冲区按使用情况分为空缓冲队列、装满输入数据的缓冲队列(输入队列)、装满输出数据的缓冲队列(输出队列)，另外根据一个缓冲区在实际运算中扮演的功能不同，又设置了四种工作缓冲区，用于收容输入数据的公众号缓冲区(hin)、用于提取输入数据的工作缓冲区(sin)、用于收容输出数据的工作缓冲区(hout)、用于提取输出数据的工作缓冲区(sout)
         • 输入进程请求输入数据时，从空缓冲队列中取出一块作为收容输入数据的工作缓冲区(hin)，冲满数据后将缓冲区挂到输入队列队尾
         • 计算进程想要取得一块输入数据时，从输入队列中取得一块冲满输入数据的缓冲区作为提取输入数据的工作缓冲区(sin)，缓冲区读空后挂到空缓冲区队列
         • 计算进程想要将准备好的数据冲入缓冲区时，从空缓冲队列中取出一块作为收容输出数据的工作缓冲区(hout)，数据冲满后将缓冲区挂到输出队列的队尾
         • 输出进程请求输出数据时，从输出队列中取得一块冲满数据的缓冲区作为提取输出数据的工作缓冲区(sout)，缓冲区读空后挂到空缓冲区队列

    • 建立逻辑设备名到物理设备名的映射关系，根据设备类型选择调用相应的驱动程序（通过逻辑设备表LUT完成映射，每条表项由逻辑设备名+物理设备名+驱动程序入口地址构成）

      （第一种方式是整个系统只设置一张LUT，意味着用户不能使用相同的逻辑设备名，只适用于单用户操作系统；第二种方式是为每个用户设置一张LUT，类似于设置了两级目录那样的结构，各个用户使用的逻辑设备名可以重复，适用于多用户操作系统，系统会在用户登录时为其建立一个用户管理进程，LUT就存放在用户管理进程的PCB中）

  • 设备驱动程序：主要负责对硬件设备的具体控制，将上层发出的一系列命令(如read/write)转化成特定设备能听得懂的一系列操作，包括设置设备寄存器，检查设备状态等（不同设备的驱动程序不同，由厂家提供，驱动程序一般会以一个独立进程的方式存在）

  • 中断处理程序：当I/O任务完成时，I/O控制器会发送一个中断信号，系统根据中断信号类型找到相应的中断处理程序并执行；中断处理程序会从控制器中读取设备状态，如果I/O正常结束，则从设备控制器的数据寄存器中读入一个字的数据并经由CPU放到内存缓冲区中，如果I/O非正常结束，那么要根据异常原因做相应处理，如硬件故障

• 硬件：执行I/O操作，由机械部件、电子部件组成