第一章 操作系统引论

操作系统的定义

操作系统是一组能有效地组织和管理计算机硬件和软件资源，
合理地对各类作业进行调度，以及方便用户使用的程序的集合

操作系统的目标

==方便性==、==有效性==、可扩充性、开放性

有效性: 提高系统资源的利用率、提高系统的吞吐量

引入OS的目的

为多道程序的运行提供良好的运行环境，以保证多道程序能有条不紊地、高效地运行，
并能最大程度地提高系统中各种资源的利用率。方便用户的使用

操作系统的作用

1. OS作为用户和计算机硬件系统之间的接口

• 用户有三种方式使用计算机: 命令方式、系统调用方式、图标-窗口方式

2. OS作为计算机系统资源的管理者

• 处理机管理: 用于分配和控制处理机
• 存储器管理: 负责内存的分配与回收
• I/O设备管理: 负责I/O设备的分配(回收)与操纵
• 文件管理: 用于实现对文件的存取、共享和保护

3. OS实现了对计算机资源的抽象

推动操作系统发展的主要动力

• 不断提高计算机资源利用率
• 方便用户
• 器件的不断更新换代
• 计算机体系结构的不断发展
• 不断提出新的应用需求

操作系统的发展过程

人工方式

缺点: 用户独占全机、CPU等待人工操作

脱机输入/输出方式

事先将装有用户程序和数据的纸带装入纸带输入机，在一台外围机的控制下，把纸带上的数据输入到磁带上。
CPU在需要时，从磁带上高速地调入内存。

优点: 减少了CPU的空闲时间、提高了I/O速度

单道批处理系统

• 在系统运行过程中，内存中只有一个用户作业存在；
• 把一批作业脱机输入到磁带上；
• 系统配上监督程序；
• 在监督程序的控制下使这批作业能一个接一个的连续得到处理；
• 处理机使用权在监督程序和用户程序间转换。

特征: 自动性、顺序性、单道性

缺点: 系统中的资源得不到充分的利用。因为在内存中仅有一道程序，每逢该程序在运行中发出I/O请求后，
CPU便处于等待状态，必须在其I/O完成后才继续运行

多道批处理系统

过程: 作业先存放在外存上并排成一个队列，称为“后备队列”；然后，由作业调度程序按一定的算法
从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。

优缺点:

• 资源利用率高
• 系统吞吐量大
• 可提高内存和I/O设备利用率
• 平均周转时间长
• 无交互能力

多道批处理系统需要解决的问题:

• 处理机争用问题
• 内存分配和保护问题
• I/O设备分配问题
• 文件的组织和管理问题
• 作业管理问题
• 用户与系统的接口问题

image

分时系统

分时系统是指，在一台主机上连接了多个配有显示器和键盘的终端并由此所组成的系统，\

该系统允许多个用户同时通过自己的终端，以交互方式使用计算机，共享主机中的资源

分时系统实现中的关键问题:

1. 及时接收
2. 及时处理

为实现人——机交互，采用下面的运行方式:

• 作业直接进入内存
• 采用==时间片==轮转的运行方式。

image

影响响应时间的因素:

• 终端数目多少
• 调度算法（时间片的选取）
• 信息交换量和信息交换速度
• 机器处理能力
• 请求服务的时间长短及服务请求的分布

实时系统

实时系统是指系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行

实时系统的类型:

• 工业(武器)控制系统
• 信息查询系统
• 多媒体系统
• 嵌入式系统

实时任务的类型:

• 周期性实时任务和非周期性实时任务
• 硬实时任务和软实时任务

实时系统与分时系统特征的比较

image

微机操作系统

单用户单任务操作系统

只允许一个用户上机，且只允许用户程序作为一个任务运行

单用户多任务操作系统

只允许一个用户上机，但允许用户把程序分为若干个任务，使它们并发执行

多用户多任务操作系统

允许多个用户通过各自的终端，使用同一台机器共享主机系统中的各种资源，
而每个用户程序又可进一步分为几个任务，使它们能并发执行，
从而可进一步提高资源利用率和系统吞吐量

操作系统的基本特性

并发

==并行性==: 两个或多个事件在同一时刻发生

==并发性==: 两个或多个事件在同一时间间隔内发生

程序的并发执行，有效地改善了系统资源的利用率和提高了系统的吞吐量，
但它使系统复杂化，操作系统必须具有控制和管理各种并发活动的能力。

==进程==: 在系统中能独立运行并作为资源分配的基本单位，它是由一组机器指令、数据和堆栈等组成的，是一个能独立运行的活动实体。多个进程之间可以并发执行和交换信息。

共享

资源共享指系统中的资源可供内存中多个并发执行的进程共同使用

==互斥共享方式==

临界资源: 在一段时间内只允许一个进程访问的资源

==同时访问方式==

==并发==和==共享==是多用户(多任务)OS的两个最基本的特征

虚拟

通过某种技术将一个物理实体变为若干个逻辑上的对应物

==时分复用技术==: 利用某设备为一用户服务的==空闲时间==，又转去为其他用户服务

虚拟处理机技术、虚拟设备技术

==空分复用技术==: 利用存储器的==空闲空间==分区域存放和运行其它的多道程序

虚拟存储技术

异步

进程以不可预知的速度向前推进

操作系统的主要功能

处理机管理功能

处理机的分配和运行都是以==进程==为基本单位的

处理机管理的主要功能有:
创建和撤销进程，对诸进程的运行进行协调，
实现进程之间的信息交换，以及按照一定算法把处理机分配给进程

==进程控制==: 为作业创建进程、撤销(终止)已结束的进程，
以及控制进程在运行过程中的状态转换

==进程同步(信号量机制)==: 为多个进程(含线程)的运行进行协调

协调方式: 进程互斥方式、进程同步方式

进程同步方式: 在相互合作去完成共同任务的诸进程间，由同步机构对它们的执行次序加以协调

==进程通信==: 实现相互合作进程之间的信息交换

==调度==: 作业调度、进程调度

存储器管理功能

主要任务: 为多道程序的运行提供良好的环境，提高存储器的利用率，
方便用户使用，并能从逻辑上扩充内存

主要功能: 内存分配和回收、内存保护、地址映射和内存扩充

1. ==内存分配==:

主要任务:

• 为每道程序分配内存空间
• 提高存储器的利用率
• 允许正在运行的程序申请附加的内存空间

==静态分配方式==: 运行期间不允许该作业再申请新的内存空间

==动态分配方式==: 可以在运行过程中申请新的附加内存空间

2. ==内存保护==

内存保护机制: 设置两个界限寄存器，分别用于存放正在执行程序的上界和下界

主要任务:

• 确保每道用户程序都仅在自己的内存空间内运行，彼此互不干扰
• 绝不允许用户程序访问操作系统的程序和数据，也不允许用户程序转移到非共享的其它用户程序中执行

3. ==地址映射==

能够将地址空间中的逻辑地址转换=为内存空间中与之对应的物理地址

4. ==内存扩充==

请求调入功能

置换功能

设备管理功能

主要任务:

• 完成用户进程提出的I/O请求，为用户进程分配所需的I/O设备，并完成指定的I/O操作
• 提高CPU和I/O设备的利用率，提高I/O速度，方便用户使用I/O设备

文件管理功能

主要任务:

对用户文件和系统文件进行管理以方便用户使用，并保证文件的安全性。

功能:

• 对文件存储空间的管理
• 目录管理
• 文件的读/写管理
• 文件的共享与保护

操作系统与用户之间的接口

用户接口: 用户通过该接口向作业发出命令以控制作业的运行

程序接口: 为用户程序在执行中访问系统资源而设置的

第二章 进程的描述与控制

程序顺序执行时的特征

顺序性、封闭性、可再现性

程序并发执行

只有不存在前趋关系的程序之间才有可能并发执行，否则无法并发执行

程序并发执行时的特征: ==间断性、失去封闭性、不可再现性==

image

进程的定义

==进程是程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立的基本单位==

==进程控制块==(PCB): 描述进程的基本情况和活动过程，进而控制和管理进程

==进程实体==: 程序段、相关的数据段、PCB

==创建进程==: 创建进程实体中的PCB；==撤销进程==: 撤销进程的PCB

进程的特征

• ==结构特征==: 程序段、数据段、PCB
• ==动态性==: 进程的实质是进程实体的执行过程。进程实体有一定的生命期
• ==并发性==: 多个进程实体同存于内存中，且能在一段时间内同时运行。
  ==引入进程的目的==正是为了使其进程实体能和其它进程实体并发执行
• ==独立性==: 进程实体是一个能独立运行、独立获得资源和独立接收调度的基本单位
• ==异步性==: 进程是按异步方式运行的，按各自独立的、不可预知的速度向前推进

进程的基本状态及转换

• 就绪状态: 得到了除CPU以外的所有必要资源
• 执行状态: 已获得处理机，程序正在被执行
• 阻塞状态: 因等待某事件而暂时无法继续执行，从而放弃处理机，
  使程序执行处于暂停状态

进程和程序的关系

image

基本状态的转换

image

==创建状态==: 进程已拥有了自己的PCB，但进程自身还未进入主存，
即创建工作尚未完成，进程还不能被调度运行，其所处的状态。

==终止状态==：当一个进程到达了自然结束点，或是出现了无法克服的错误，
或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入终止状态。

==挂起操作==

把一个进程挂起使之处于静止状态，以便研究它的执行情况或对它进行修改

原因：

• 终端用户请求
• 父进程请求
• 负荷调节的需要
• 操作系统的需要

状态转换：

• 活动就绪→静止就绪
• 静止就绪→活动就绪
• 活动阻塞→静止阻塞
• 静止阻塞→活动阻塞
• 静止阻塞→静止就绪

进程控制块

==概念==: 进程控制块是进程实体的重要组成部分，是操作系统中最重要的记录型数据，在进程控制块PCB（Program Contral Block）中记录了操作系统所需要的、用于描述进程情况及控制进程运行所需要的全部信息

==作用==:

通过PCB，使得原来不能独立运行的程序（数据），成为一个可以独立运行的基本单位，一个能够并发执行的进程。进程控制块是进程存在的唯一标志。

==PCB中的信息==:

进程标识符: 用于唯一地标识一个进程

处理机状态: 保留进程存放在处理器中的各种信息，主要由处理器内的各个寄存器的内容组成。

进程调度信息:进程状态、进程优秀级、阻塞原因等等。

进程控制信息:程序和数据的地址、进程同步和通信机制、资源清单、链接指针

==PCB的组织方式==

线性方式

链接方式: 将具有相同状态的PCB，用其中的链接字，链接成一个队列

索引方式: 根据进程的状态，建立索引表

进程控制

进程控制是对系统中所有进程从产生、存在到消亡的全过程实行有效的管理和控制。
进程控制一般是由操作系统的内核来实现，内核在执行操作时，
往往是通过执行各种原语操作来实现的

操作系统内核

==内核==: 加在硬件上的第一层软件，通过执行各种原语操作来实现各种控制和管理功能，具有创建、撤消、进程通信、资源管理的功能

==内核的基本功能==

支撑功能：中断处理、时钟管理、原语操作

资源管理功能：进程管理、存贮管理、设备管理

==原语==：是由若干条机器指令所构成，用以完成特定功能的一段程序 。原语在执行期间是不可分割的或不可中断的。

创建原语、撤消原语、阻塞原语、唤醒原语

进程的创建

==进程之间的关系==

• 父、子进程与祖先进程: PCB中标识
• 继承/归还资源: “父”创建“子”、父撤子消

==引起创建进程的事件==

• 用户登录 :在分时系统中，用户在终端键入登录命令
• 作业调度:在批处理系统中，当作业调度程序按一定的算法调度到某作业
• 提供服务:用户程序提出某种请求后，系统将专门创建一个进程来提供用户所需要的服务
• 应用请求:它自己创建一个新进程，以便使新进程以并发运行方式完成特定任务

==进程创建的过程==
（进程创建原语Create()）

• 申请一个空白PCB,为新进程申请获得唯一的数字标识符(PID)
• 为新进程分配资源
• 初始化PCB
• 新进程加入到就绪队列

进程的终止

==引起进程终止的事件==

• 进程正常结束
• 在进程运行期间，由于出现某些错误和故障而使得进程被迫中止
• 进程应外界的请求而中止运行

==进程终止的过程==
（进程终止原语Destroy()）

• 根据被终止进程的标识符，从PCB集合中检索该进程的PCB，读出进程状态。
• 若该进程处于执行状态，则立即终止该进程的执行。
• 若该进程有子孙进程，还要将其子孙进程终止。
• 将该进程所占用的资源回收，归还给其父进程或操作系统。
• 将被终止进程的PCB从所在队列中移出，并撤消该进程的PCB。

进程的阻塞与唤醒

==引起进程阻塞的事件==

• 请求系统服务，要求不能立即满足
• 启动某种操作，必须在操作完成后才能继续
• 合作进程提供的新数据尚未到达
• 无新工作可做

==进程阻塞的过程==
（进程阻塞原语Block()）

• 立即停止执行
• 修改进程控制块中的相关信息
• 把进程控制块插入到阻塞队列
• 转调度程序重新调度

==引起进程唤醒的事件==

• 请求系统服务得到满足
• 启动某种操作完成
• 新数据已经到达
• 有新工作可做

==进程唤醒的过程==
（进程唤醒原语Wakeup()）

• 从阻塞队列中找到该进程
• 修改该进程控制块的相关内容
• 把进程控制块插入到就绪队列

进程的挂起与激活

==进程挂起的方式==

• 把发出本原语的进程自身挂起
• 挂起指定进程名的进程
• 把某进程及其全部或部分子孙一起挂起

==进程挂起的过程==
（进程挂起原语Suspend()）

• 检查被挂进程的状态，改为相应的挂起状态
• 把进程的PCB复制到指定的区域
• 转向调度程序重新调度

==进程激活的过程==
（进程激活原语Active()）

先将进程从外存调入内存，检查该进程的现行状态，
改为相应的活动状态。根据优先级可能引起调度。

进程同步

主要任务

对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则(或时序)共享系统资源，并能很好地相互合作，从而使程序的执行具有可再现性

两种形式的制约关系

间接相互制约关系——共享某种系统资源

直接相互制约关系——相互合作

临界资源

一次仅允许一个进程使用的资源，如打印机、变量

临界区

临界区是每个进程中访问临界资源的那段代码

若能保证诸进程互斥地进入自己的临界区，
便可实现诸进程对临界资源的互斥访问

同步机制应遵循的规则

image

信号量机制

==信号量==

用于表示==资源数目==或请求使用某一资源的==进程个数==的整型量

S是与临界区内所使用的公用资源有关的信号量

S ≥0 可供并发进程使用的资源数

S < 0 正在等待使用临界区的进程数

整型信号量

Wait和Signal是两个原子操作，在执行时是不可中断的。

整型信号量解决临界区调度的==缺点==:
对不能进入临界区的进程，采用忙式等待测试法，浪费CPU时间。因此未遵循“让权等待”的准则，使进程处于“忙等”状态。
在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。

记录型信号量

struct semaphore{
    int value;
    struct process_control_block *L;
}

wait(semaphore S)
{
    S.value--;
    if(S.value＜0)  block(S.L)
}
signal(semaphore S)
{
    S.value++;
    if(S.value≤0)   wakeup(S.L);
}

image

AND型信号量

AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。

信号量集

在有些情况下，当资源数量低于某一下限值，不予以分配

Swait(S, t, d), S为信号量，t为下限值，d为需求值

image

利用信号量实现前趋关系

image

管程机制

管程: 代表共享资源的数据结构以及由对该共享数据结构实施操作的
一组过程所组成的资源管理程序共同构成了一个操作系统的资源管理模块

由四部分组成

• 管程的名称
• 局部于管程的共享数据结构说明
• 对该数据结构进行操作的一组过程
• 对内部的共享数据初始化语句

image

注意:

局部变量只能被管程的过程访问；

进程通过调用管程的过程进入管程；

只能有一个进程在管程中执行

利用记录型信号量解决生-消问题

int in = 0, out = 0;
item buffer[n];
semaphore mutex = 1, empty = n, full = 0;
void procuder() {
  do {
      procuder an item nextp;
      ...
      wait(empty);//判断是否有空缓冲区，表示空缓冲区-１；
      wait(mutex);//数据缓冲区互斥访问，关闭访问；
      buffer[in] = nextp;
      in = (in+1) % n;
      signal(mutex);//打开访问
      signal(full);//满缓冲区加+1
  } while (true);
}

void consumer() {
   do {
       wait(full);//判断是否有满缓冲区，满缓冲区-1
       wait(mutex);//数据缓冲区互斥访问，关闭访问；
       nextc = buffer[out];
       out = (out+1) % n;
       signal(mutex);//打开访问
       siganl(empty);//空缓冲区+1
       consumer the item in nextc;
       ....
   } while (true);
}

void main() {
  cobegin
    producer(); consumer();
  coend
}

每次只允许一个进程进入缓冲池进行操作

mutex为互斥信号量，实现诸进程对缓冲池的互斥访问，初值为1，取值为0、1

empty,full为资源信号量，为正时分别表示==空缓冲区==和==满缓冲区==的数量；
为负时，其绝对值为相应阻塞进程的数目。
初值为n，0。可为负

应先执行对资源信号量的wait操作，然后再执行对互斥信号量的wait操作，否则会造成死锁

由buffer组成的缓冲池是被组织成循环缓冲的

wait两个操作不能互换。例如：当 mutex=1, E=0, F=n时，则对生产者进程：wait(mutex)成功，wait(E)失败；对消费者进程：wait(F)成功，wait(mutex)失败，形成死锁

signal操作的次序无关紧要

互斥和资源信号量的原语必须成对出现

wait(empty) 
    empty >= 0  则数据送入缓冲区
    empty < 0   被阻塞  （满）
signal(empty)   
    empty > 0       
    empty <= 0  释放一个空缓冲区，唤醒一个阻塞的生产者进程
    
    
wait(full)  
    full >= 0   则从缓冲区取走数据
    full < 0    被阻塞  （空）
signal(full)    
    full > 0        
    full <= 0   数据装入缓冲区，唤醒一个
                阻塞的消费者进程

image

读者-写者问题

算法描述：

设置两个互斥信号量：

（1）wmutex，实现Reader与Writer进程间在读或写时的互斥。

（2）rmutex,用于使读者互斥地访问共享变量readcount。

readcount表示正在读的进程数目，只要有一个Reader进程在读，便不允许Writer进程去写。因此，仅当readcount=0, 表示尚无Reader进程在读时，Reader进程才需要执行Wait(wmutex)操作。若wait(wmutex)操作成功，Reader进程便可去读，相应地，做readcount+1操作。同理，仅当Reader进程在执行了readcount减1操作后其值为0时，才须执行signal(wmutex)操作，以便让Writer进程写

读者进来: 读者函数首先申请将rmutex，锁住读信号量，判断readcount是否为0，为0则申请wmutex，不让写者进来，再释放掉rmutex，到此，可以让其他读者进来，但是写者都进不来

读者离开: 先申请rmutex，锁住，不让新的读者进来，执行readcount--，移出已进来的读者，判断readcount是否为0，为0，也就是所有读者出去了，释放wmutex，这个时候，写者和读者都可以进来了

使用信号量机制时易犯的错误

==错误1==：在利用互斥信号量mutex实现进程互斥时，如果将wait(s)与signai(s)颠倒，即

signal(mutex);
critical section
wait(mutex);  

在这种情况下，可能会有几个进程同时进入临界区，因而同时去访问临界资源。对于这样的错误仅在几个进程同时活跃在临界区内时，才可能发现，而这种情况又并非总是可在发现的。

==错误2==: 在实现进程互斥时，如果程序中的signal(mutex)被误写为wait(mutex),即

wait(mutex);
critical section
wait(mutex);

此时的mutex将被出错的进程连续两次地执行wait操作，因而变成-1，这样将会使任何其它进程都不能进入临界区；从而也不会再有进程执行signal(mutex)操作，去唤醒出错的进程。在这种情况下，将发生死锁。

==错误3==:
在实现进程互斥时，如果在程序中遗漏了wait(mutex)操作，将会使多个进程同时活跃在临界区；而如果遗漏了signal(mutex)操作，则将会使其它进程无法再进入临界区；而如果已有进程因不能进入临界区而阻塞，则该进程将永远不会被唤醒。

线程

==定义==: 作为调度和分派的基本单位

==线程与进程的比较==

• 调度：进程不再是调度的基本单位。
• 并 发 性：进程之间可以并发，线程之间也可以并发执行。
• 拥有资源：线程几乎不占资源，同一进程的线程共享进程的资源。
• 独立性：同一进程中的不同线程之间的独立性要低很多。
• 系统开销：线程的创建、撤消与切换的系统开销小的多。
• 支持多处理机系统

==线程的运行状态==

• 执行状态: 表示线程已获得处理机而正在运行
• 就绪状态: 指线程已具备了各种执行条件，只须获得CPU便可立即执行
• 阻塞状态: 指线程在执行中因某事件受阻而处于暂停状态

==线程控制块TCB==

线程标志符和一组状态参数：寄存器状态，堆栈，线程运行状态，优先级，线程专有存储器，信号屏蔽

==多线程OS中的进程属性==

• 进程是一个可拥有资源的基本单位；
• 多线程可以并发执行；
• 进程已不是可执行实体

==线程的实现方式==

1. 内核支持线程

• 线程的创建、撤消、线程之间的切换，都需要在内核的支持下来实现；
• 线程控制块（TCB）
• 调度以线程为单位

2. 用户级线程

• 仅存在于用户进程空间中，线程的创建、撤消、线程之间的同步与通信都无须利用系统调用（内核）来实现；
• 系统内的线程可以“成百上千”
• 调度以进程为单位

==线程的实现==

1. 内核支持线程的实现

• 进程的任务数据区（Per Task Data Area）
• 线程控制块（TCB）
• 与进程管理类似

2. 用户级线程的实现——利用中间系统

• 运行时系统（Runtime System）是用于管理和控制线程的函数（过程）的集合。他们使用户级线程与内核无关。
• 内核控制线程（又称轻型进程LWP），用户级线程通过LWP获得内何服务。

==线程的创建和终止==

• 应用程序启动时，仅有一个线程——初始化线程
• 初始化线程调用线程创建函数去创建若干个线程
• 终止线程的方式：线程完成工作后自愿退出；线程在运行中出现错误或由于某种原因而被其它线程强行终止
• 被终止未释放资源的线程可以被需要的线程调用，使它重新恢复运行

第三章 处理机调度与死锁

调度的实质是一种资源分配，处理机调度是对处理机资源进行分配

处理机调度的层次

高级调度

又称长程调度或==作业==调度。调度对象是==作业==。运行频率最低

==主要功能==是根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，
为它们创建进程、分配必要的资源，并将它们放入就绪队列

主要用于多道批处理系统中，而在分时和实时系统中不设置高级调度

低级调度

又称为==进程==调度或短程调度。调度对象是==进程==(或内核级线程)。运行频率最高

==主要功能==是根据某种算法，决定就绪队列中的哪个进程应获得处理机，
然后再由分派程序把处理机分配给该进程

多道批处理、分时、实时系统

中级调度

又称为==内存==调度

主要==目的==是为了提高内存利用率和系统吞吐量

==功能==: 将处于外存交换区中的就绪状态或等待状态的进程调入内存，
或把处于内存就绪状态或内存等待状态的进程交换到外存交换区中。

实际上就是存储器管理中的对换功能

处理机调度算法的目标

共同目标

• 资源利用率

  CPU的利用率=
  CPU有效工作时间/（ CPU有效工作时间+CPU空闲等待时间）

• 公平性

• 平衡性

• 策略强制执行

批处理系统的目标

• 平均周转时间短

• 系统吞吐量高

  吞吐量：单位时间内完成的作业数，与作业的平均长度具有密切关系。

• 处理机利用率高

image

分时系统的目标

• 响应时间快

  响应时间：从用户通过键盘提交一个请求开始至系统首次产生响应为止。

• 均衡性

实时系统的目标

• 截止时间的保证

  截止时间：某任务开始执行的最迟时间，或必须完成的最迟时间。

• 可预测性

作业与作业调度

批处理系统中的作业

==作业==: 包含了通常的程序和数据，还配有一份作业说明书

在批处理系统中，是以作业为基本单位从外存调入内存的

==作业步==: 对作业的加工步骤

==作业控制块==(JCB): 作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息

在作业运行期间，系统按照JCB中的信息和作业说明书对作业进行控制

作业运行的三个阶段和三种状态

• 收容阶段：后备状态
• 运行阶段：运行状态
• 完成阶段：完成状态

image

作业调度的主要任务

根据JCB中的信息，检查系统中的资源能否满足作业对资源的需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程排在就绪队列上等待调度

执行作业调度时，需要解决

1.==一次接纳多少作业==，即允许多少个作业同时在内存中运行

2.==接纳哪些作业==，即哪些作业调入内存，取决于所采用的算法。比如先来先服务调度算法；或者是短作业优先调度算法；还有基于作业优先权的调度算法，响应比高者优先调度算法等

作业调度算法

先来先服务算法(FCFS)

• 可用于作业调度和进程调度。
• 按照作业（进程）进入后备队列（就绪队列）的先后次序来挑选作业（进程），先进入先被挑选。
• 算法容易实现，效率不高，只顾及作业（进程）等候时间，没考虑作业（进程）要求服务时间的长短。
• 有利于长作业（进程），不利于短作业（进程）。有利于CPU繁忙型作业，不利于I/O繁忙型作业

image

短作业优先调度算法(SJF)

image

image

优点：

• 降低作业的平均等待时间，提高系统吞吐量。

优先级调度算法(PSA)

基于作业的==紧迫程度==，由外部赋予作业相应的优先级，调度算法是根据优先级进行调度的

高响应比优先调度算法

image

image

重要例题

image

image

进程调度

进程调度的任务

• 保存处理机的现场信息
• 按某种算法选取进程
• 把处理器分配给进程

进程调度机制

• 排队器：将就绪进程插入到相应的就绪队列中。
• 分派器：依据进程调度程序所选定的进程，将其从就绪队列中取出。
• 上下文切换器：保存当前进程的上下文；新选进出的CPU现场信息恢复。

进程调度方式

非抢占方式

一旦把处理机分配给某个进程后，让该进程一直执行，
直到该进程完成或者发生某事件而阻塞

引起进程调度的因素：

• 正在执行的进程执行完毕
• 执行中的进程因为提出I/O请求而暂停执行
• 进程通信或同步过程中执行了原语操作

==优点==：实现简单、系统开销小，适用于大多数的批处理系统环境。

==缺点==：难以满足紧急任务的要求，不适宜要求比较严格的实时系统

抢占方式

允许调度程序根据某种原则，暂停正在执行的进程，将处理机重新分配给其他进程

image

轮转调度算法

image

时间片 Q=R / Nmax

R：响应时间 Nmax： 最大进程数

image

好题

优先级调度算法

==优先级调度算法的类型==

• 非抢占式优先级调度算法
• 抢占式优先级调度算法

==优先级的类型==

• ==静态优先级==

静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。

确定进程优先权的依据有如下三个方面：

（1）进程类型
（2）进程对资源的需求
（3）用户要求

• ==动态优先级==

动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。

进程优先权改变原因：

（1）进程等待时间
（2）进程占用CPU时间

多级反馈队列调度算法

• 设置多个就绪队列，并为各个队列赋予不同的优先级，优先级越高的队列中，为每个进程所规定的执行时间片就越小
• 新进程进入内存后，放入第一队列末尾，按FCFS原则等待调度，如果在一个时间片结束时没完成，将该进程转入第二队列末尾重新等待调度执行……
• 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行
• 如果处理机正在为某队列的进程服务，又有新进程插入到较高优先级的队列中，则新进程将抢占正在运行进程的处理机

算法性能：

• 较好的性能，能够照顾到用户的利益
• 短作业、长作业都能得到比较满意的处理

实时调度

实现实时调度的基本条件

1. 提供必要的信息

• 就绪时间
• 开始截止时间和完成截止时间
• 处理时间
• 资源要求
• 优先级

2. 系统处理能力强
3. 采用抢占式调度机制
4. 具有快速切换机制

实时调度算法的分类

1. 非抢占式调度算法
2. 抢占式调度算法

• 基于时钟中断的抢占式优先级调度算法
• 立即抢占的优先级调度算法

最早截止时间优先算法(EDF)

见书P100~101

• 根据开始截止时间来确定任务的优先级
• 截止时间早的排在就绪队列前面
• 总是选择就绪队列中的第一个任务
• 可用于抢占式调度和非抢占式调度

最低松弛度优先算法(LLF)

见书P101~102

• 根据任务紧急（或松弛）的程度来确定优先级
• 紧急程度愈高（松弛程度愈低）优先级愈高，愈先执行
• 主要用于抢占式调度
• ==松弛度=必须完成时间-其本身的运行时间-当前时间==

一任务在400 ms时必须完成，它本身需要运行 150 ms，则其松弛程度为 250 ms。

优先级倒置

原因: 进程之间有无资源争抢

解决方法:

• 处理机不允许被抢占
• 动态优先级继承

死锁

资源问题

• 可重用性资源：IO设备、打印机等
• 可消耗性资源（临时资源）：进程间通信的消息等
• 可抢占性资源（可剥夺资源）：CPU、内存
• 不可抢占性资源（非可剥夺资源）：磁带机、打印机

定义

如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程是死锁的

原因

• ==竞争不可抢占性资源引起进程死锁==
• ==竞争可消耗资源引起进程死锁==
• 进程推进顺序不当
• PV操作使用不当

产生死锁的必要条件

• 互斥条件：进程互斥使用资源
• 请求和保持条件：申请新资源时不释放已占有资源
• 不剥夺条件：一个进程不能抢夺其他进程占有的资源
• 环路等待条件：存在一组进程循环等待资源的环形链

处理死锁的基本方法

• 预防死锁：通过设置某些限制条件来破坏产生死锁的四个必要条件中的一个或几个，来预防发生死锁
• 避免死锁：在动态分配资源的过程中，用某种方法防止系统进入不安全状态，从而避免发生死锁
• 检测死锁：通过设置检测机制，及时检测出死锁的发生，确定有关的进程和资源
• 解除死锁：与检测死锁配套使用，常用的方法是撤销或挂起一些进程，收回资源，分配给处于阻塞状态的进程，使之转为就绪状态，可以继续运行

预防死锁

破坏“请求和保持”条件

1. 第一种协议：资源静态分配法

   一个进程必须在执行前就申请它所要的全部资源，并且直到它所要的资源都得到满足后才开始执行

2. 第二种协议：资源静态分配法

   允许进程只获得运行初期所需的资源，便开始运行。这些资源使用完毕并全部释放，再申请新的所需资源。

破坏“不可抢占”条件

采用剥夺控制

当进程在申请资源未获准许时,先主动释放已占有的资源,然后才去等待，以后再一起向系统提出申请

一般只适用于可剥夺性资源，如CPU、存储区

破坏“循环等待”条件

资源顺序分配法

对系统的全部资源编号，并规定进程申请资源时只能按升序进行

避免死锁

系统安全状态

• 安全状态是指系统能按某种顺序为每个进程分配其所需的资源，使每个进程执行完毕
• 安全序列：进程安全执行完的顺序。
• 如果系统无法找到这样一个安全序列，则称系统处于不安全状态。
• 避免死锁的本质在于：当进行资源分配时，如何避免进入不安全状态

银行家算法

• （1）如果Requesti[j]≤Need[i,j]，便转向步骤2；否则认为出错。

• （2）如果Requesti[j]≤Available[j]，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。

• （3）系统试探着把资源分配给进程Pi，并执行：

   Available[j]=Available[j]-Requesti[j];
   
   Allocation[i,j]=Allocation[i,j]+Requesti[j];
   
  Need[i,j]=Need[i,j]-Requesti[j];
  

-（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

优点：
资源利用率比静态资源分配法高，又避免死锁。

缺点：
对资源分配过于保守；计算太多，并且需知道对资源的最大需求量，不太实际

安全性算法

(1) 设置工作向量Work和布尔型向量Finish ，并初始化: Work=Available; Finish[i]=false;

(2)寻找能满足下述条件的进程：①Finish[i]=false;② Need[i,j]≤Work[j];若找到，执行 (3)，否则，执行 (4)。

(3) 执行：
Work[j]=Work[i]+Allocation[i,j];
Finish[i]=true;
go to step 2;

(4) 如果所有进程的Finish［i］=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。

死锁定理

系统为死锁状态的充分条件是：当且仅当该状态的资源分配图是不可完全简化的。该充分条件称为死锁定理。

死锁的解除

• 剥夺资源
• 终止(或撤销)进程

第四章 存储器管理

管理对象: ==内存==

存储器的多层结构

寄存器、高速缓存、主存储器、磁盘缓存 属于操作系统存储管理的管辖范畴

以上，掉电后存储信息丢失

固定磁盘、可移动存储介质 属于设备管理的管辖范畴

存储信息长期保存

可执行存储器: 寄存器、主存储器

寄存器: 存放处理机运行时的数据，以加速存储器的访问速度

高速缓存: 用于备份主存中较常用的数据，以减少处理机对主存储器的访问次数

主存储器(内存,主存): 用于保存进程运行时的程序和数据

磁盘缓存: 用于暂时存放频繁使用的一部分磁盘数据和信息

一些基本概念

逻辑地址(相对地址，虚地址)

用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都相对于首地址而编址。不能用逻辑地址在内存中读取信息。

物理地址(绝对地址，实地址)

内存中存储单元的地址，可直接寻址

地址空间

• 程序用来访问信息所用地址单元的集合
• 逻辑（相对）地址的集合
• 由编译程序生成

存储空间

• 主存中物理单元的集合
• 物理（绝对）地址的集合
• 由装配程序等生成

定位(存储分配)

为具体的程序和数据等分配存储单元或存储区工作。

映射

把逻辑地址转换为相应的物理地址的过程。

程序的装入

对用户程序的处理步骤

image

1. 编译，由编译程序对用户源程序进行编译，形成若干个目标模块
2. 链接，由链接程序将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块
3. 装入，由装入程序将装入模块装入内存

绝对装入方式

• 编译程序产生绝对地址的目标代码，即代码的逻辑地址和物理地址相同
• 装入程序按照装入模块中的地址，将程序和数据装入内存，不进行地址的修改
• 只适用于单道程序环境

可重定位装入方式

目标模块的起始地址从0开始，程序中其他地址相对于起始地址计算，装入程序根据内存的当前情况，将装入模块装入内存的适当位置

==重定位==：在装入时对目标程序中指令和数据地址的修改过程。或者说：把作业地址空间中使用的逻辑地址变换成内存空间中的物理地址的过程。又称地址映射。

地址变换在装入时一次完成，以后不再改变，==故称为静态重定位==

==优点==：无需增加硬件地址变换机构；实现简单；适用于多道程序环境

==缺点==：不允许程序运行时在内存中移动位置；程序在存储空间中只能连续分配；多个用户难以共享存于内存中的同一程序。

动态运行时的装入方式

• 装入程序把装入模块装入内存后，不立即把装入模块中的相对地址转换为绝对地址，
  而是把这种地址转换推迟到程序真正要执行时才进行。
• 装入内存后的所有地址都仍是相对地址。
• 允许程序在内存中移动；
• 需要重定位寄存器的支持
• 优点：可对内存进行非连续分配；提供了实现虚存的基础；有利于程序段的共享

程序的链接

静态链接方式

在程序运行之前，先将各目标模块以及所需的库函数，链接成一个完整的装配模块，==以后不拆开==。

在将这几个目标模块装配成一个装入模块时，须解决以下两个问题：

(1) 对相对地址进行修改。 (2) 变换外部调用符号

装入时动态链接

将用户源程序编译后所得到的一组目标模块，在装入内存时，采用==边装入边链接==的链接方式

==优点==：便于修改和更新；便于实现对目标模块的共享。

==缺点==：程序每次要运行的模块可能不相同，但无法知道本次要运行哪些模块，故只能将所有可能要运行的模块都全部装入内存并链接。

运行时动态链接

对某些目标模块的链接，在程序执行中需要该模块时，才对它进行的链接。

==优点==：凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。

连续分配存储管理方式

该方式为一个用户程序分配一个连续的内存空间，即程序中代码或数据的逻辑地址相邻，体现在内存空间分配时物理地址的相邻

单一连续分配

• 最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。
• 内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常是放在内存的低址部分；
  用户区是指除系统区以外的全部内存空间， 提供给用户使用。
• 优点：管理简单，不要求专用的硬件支持；为防止破坏OS ，设置界限寄存器；易于实现。
• 缺点：存储器利用率低；信息不共享；CPU 利用率低，周转时间长

固定分区分配

• 运行多道程序的存储管理方式。
• 内存用户被划分为若干个固定大小的区域，每个分区中只装入一道作业。
• 内存利用率低。
• 允许几道作业并发。
• ==划分分区的方法==：
  分区大小相等；分区大小不等。

内存分配:

==分区使用表==：各表项包括每个分区的起始地址，大小和状态。

用户程序需要装入时，内存分配程序检索该表，找出一个能满足要求尚未分配的分区，分配给该程序，并将其表项中的状态置为“已分配”。

若未找到大小足够的分区，则拒绝为用户程序分配内存。

动态分区分配

按作业的实际大小来划分分区，且分区个数也是随机的,实现多个作业对内存的共享，进一步提高内存资源利用率

动态分区分配中的数据结构

• 空闲分区表，一个空闲分区占一个表目，表目包括：分区序号、分区始址、分区大小
• 空闲分区链。

动态分区分配操作

分配内存

image

回收内存

image

基于顺序搜索的动态分区分配算法

顺序搜索是指依次搜索空闲分区链上的空闲分区，去寻找一个其大小能满足要求的分区

首次适应算法

把主存中所有空闲区按其==物理地址递增==的次序排列。

在为作业分配存储空间时，从低址空闲区开始查找,直到找到第一个能满足要求的空闲区后，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲链中；

优先利用内存中低址部分的空闲分区，保留了高址部分的大空闲区；==低址部分不断被分割，形成很多难以利用的碎片。==

循环首次适应算法

该算法是首次适应算法的变形，在为作业分配存储空间时，是==从上次所分配的空闲区的下一个空闲区开始查找，直到找到第一个能满足要求的空闲区==，从中划出一块与请求的大小相等的一块存储区分配给作业。若到最后一个空闲区的大小仍不能满足要求时，应再从第一个空闲区开始查找；

需设置查询指针；

使空闲分区分布均匀，但是缺乏大的空闲区；

最佳适应算法

“最佳”的含义是指每次为作业分配主存时，总是把既能满足要求，又是最小的空闲区分配给作业，以免由于“大材小用”而浪费主存。为了加速查找，==该算法要求将所有的空闲区按其大小递增次序排列==；

第一个找到能满足要求的空闲区一定使最佳的；每次分割的剩余部分都是最小的，因此在存储器中会留下很多难以利用的小碎片

最坏适应算法

在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲区，从中分割一部分存储空间给作业使用，以至于存储器缺乏大的空闲分区

优点: 使剩下的空闲区不至于太小，产生碎片的可能性最小，对中、小作业有利；查找效率最高

基于索引搜索的动态分区分配算法

==快速适应算法、伙伴系统、哈希算法==

image

动态可重定位分区分配

==紧凑==

==通过移动内存中作业的位置，把原来多个分散的小分区拼接成一个大分区==

动态重定位的实现

• 每次“紧凑”后必须对移动了的程序或数据进行重定位
• 地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行的，称为动态重定位。
• 硬件地址变换机构的支持——重定位寄存器
• 内存地址＝相对地址＋重定位寄存器中的地址
• 移动程序时只需修改重定位寄存器中的地址

对换

定义

把内存中暂时不能运行的进程或者暂时不用的程序和数据换出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据换入内存

对换是改善内存利用率的有效措施，它可以直接提高处理机的利用率和系统的吞吐量

对换分类

整体对换: 进程对换
部分对换: 页面对换、分段对换

进程对换,OS必须实现三方面的功能

对换空间的管理

1. 对换空间管理的主要目标

   在具有对换功能的OS中，通常把磁盘空间分为文件区和对换区

   1. 对文件区管理的主要目标

      提高文件存储空间的利用率，提高对文件的访问速度

      采取==离散分配==方式

   2. 对对换空间管理的主要目标

      提高进程换入和换出的速度，然后才是提高文件存储空间的利用率

      采取==连续分配==方式

进程的换出与换入

1. 换出过程

   选择处于阻塞状态且优先级最低的进程作为换出进程，
   换出后收回内存空间，修改进程的PCB相关信息

2. 换入过程

   找出“就绪”状态并已经换出的进程，将其中换出时间最久的进程作为换入进程，将其换入

直到已无可换入的进程和无可换出的进程

离散分配

连续分配方式的缺点

形成许多“碎片”；“紧凑”开销大。

离散分配的种类

根据在离散分配时所分配地址空间的基本单位的不同

1. 分页存储管理方式

在该方式中，将用户程序的地址空间分为若干个固定大小的区域，称为“==页==”或者“==页面==”。大小为1KB。相应地，也将内存空间分为若干个物理块或页框，==页和块的大小相同==。这样可将用户程序的任一页放入任一物理块中，实现了==离散分配==

2. 分段存储管理方式

该方式把用户程序的地址空间分为若干个大小不同的段，每段可定义一组相对完整的信息。

3. 段页式存储管理方式

分页存储管理方式

页(页面)

把每个作业(进程)==逻辑地址空间==划分成若干大小相等的片.第0页、第1页

(物理)块或页框(frame)

把==内存空间==分成与页面相同大小的若干个存储块。 0＃块、1＃块

页内碎片

由于进程的最后一页经常装不满一块而形成了不可利用的碎片。

页面大小

• 太小，可使内存碎片减小，有利于提高内存利用率；会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存； 此外，还会降低页面换进换出的效率。
• 较大，可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。
• 页面的大小应选择得适中，且页面大小应是2的幂，通常为1 KB~8 KB。

地址结构(页号、页内地址)

image

页表(页面映象表)

==页表的作用是实现从页号到物理块号的地址映射==

由页号和块号组成，指出逻辑地址中页号与主存中物理块号的对应关系

==页号==---作业地址空间的页序号

==块号==---内存空间的页面序号

地址转换机构

基本任务

借助于页表,实现从逻辑地址到物理地址的转换,实际上就是将逻辑地址中的页号转换为内存中的物理块号

image

image

image

image

image

image

分页和分段的主要区别

(1) 页是信息的物理单位，由于系统管理的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。

(2) 页的大小固定且由系统决定，而段的长度却不固定，它由其完成的功能决定。

(3) 分页的作业地址空间是一维的而分段的作业地址空间则是二维的，程序员在标识一个地址时，需给出段名和段内地址。

(4)由于段是信息的逻辑单位，因此便于存贮保护和信息的共享，页的保护和共享受到限制。

分段存储管理方式

==可重入代码==：又称为“纯代码”，是一种允许多个进程同时访问的代码。可重入代码是一种不允许任何进程对它进行修改的代码。

分段系统中，实现代码的共享比在分页系统中容易。

例如：不同进程共享代码长为160KB的文本编辑器。

段页式存储管理方式

引入

分页和分段管理方式各有其优缺点，分页系统能有效提高内存的利用率，而分段则能更好地满足用户的需要，因此可以将两者结合成一种新的存储管理方式系统称为“段页式系统”。

原理

先将程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。

第五章 虚拟存储器

第六章 输入输出系统

I/O系统管理的主要对象是I/O设备和相应的设备控制器

主要任务: 完成用户提出的I/O请求，提高I/O速率，以及提高设备的利用率，并能为更高层的进程方便地使用这些设备提供手段

I/O系统的基本功能

• 隐藏物理设备的细节

  仅向上层进程提供少量的、抽象的读/写命令

• 与设备的无关性

• 提高处理机和I/O设备的利用率

• 对I/O设备进行控制

• 确保对设备的正确共享

• 错误处理

I/O设备的四种控制方式:

• 采用轮询的可编程I/O方式

• 采用中断的可编程I/O方式

• 直接存储器的访问方式

  (传输数据的基本单位:数据块，提高系统的利用率)

• I/O通道方式

I/O系统的层次结构和模型

层次结构

image

I/O系统中各种模块之间的层次视图

image

image

I/O系统接口

• 块设备接口: 以块为单位传输
• 流设备接口：字符设备接口
• 网络通信接口

I/O设备的类型

• 按传输速率分类：
  低速设备、中速设备、高速设备
• 按信息交换的单位分类：
  块设备、字符设备
• 按设备的共享属性分类：
  独占设备、共享设备、虚拟设备

设备控制器

I/O设备与CPU之间的接口

image

定义和概念

==设备控制器是CPU和设备之间的一个接口,它接收从CPU发来的命令,控制I/O设备操作,实现主存和设备之间的数据传输。==

控制器接受一条命令后，CPU可以转向其它工作，而设备控制器自行完成具体的I/O操作；当命令执行完毕后，控制器发出一个中断信号，以便OS重新获得CPU的控制权并检查执行结果

设备控制器是一个可编址设备,当它连接多台设备时,则应具有多个设备地址

设备控制器的基本功能

• 接收和识别命令
• 数据交换
• 标识和报告设备的状态
• 地址识别
• 数据缓冲
• 差错控制

设备控制器的组成

image

I/O通道

==定义==：通道是独立于CPU的专门负责数据输入/输出传输工作的处理机，对外部设备实现统一管理，代替CPU对输入/输出操作进行控制，从而使输入，输出操作可与CPU并行操作。

==引入通道的目的==：为了使CPU从I/O事务中解脱出来，同时为了提高CPU与设备，设备与设备之间的并行工作能力

==通过执行通道程序来控制I/O操作==

==指令类型单一，与CPU共享内存==

通道类型

字节多路通道

• 字节多路通道以字节为单位传输信息，它可以分时地执行多个通道程序。当一个通道程序控制某台设备传送一个字节后，通道硬件就控制转去执行另一个通道程序，控制另一台设备传送信息，使所有的通道轮转一周
• 主要连接以字节为单位的低速I/O设备。如打印机，终端。
• 以字节为单位交叉传输，当一台传送一个字节后，立即转去为另一台传送字节

数组选择通道（Block Selector Channel）

• 选择通道是以成组方式工作的，即每次传送一批数据，故传送速度很高。选择通道在一段时间内只能执行一个通道程序，只允许一台设备进行数据传输
• 当这台设备数据传输完成后，再选择与通道连接的另一台设备，执行它的相应的通道程序
• 主要连接磁盘，磁带等高速I/O设备

数组多路通道（Block Multiplexor Channel）

• 它结合了选择通道传送速度高和字节多路通道能进行分时并行操作的优点。它先为一台设备执行一条通道指令，然后自动转接，为另一台设备执行一条通道指令；主要连接高速设备
• 这样，对于连接多台磁盘机的数组多路通道，它可以启动它们同时执行移臂定位操作，然后，按序交叉地传输一批批数据。数据多路通道实际上是对通道程序采用多道程序设计的硬件实现

“瓶颈”问题

解决问题的方法是增加设备到主机的通路而不增加通道：即把一个设备连接到多个控制器上，一个控制器连接到多个通道上

中断机构和中断处理程序

中断和陷入

image

中断向量表和中断优先级

image

对多中断源的处理方式

屏蔽（禁止）中断、嵌套中断

中断处理程序

当一个进程请求I/O操作时，该进程将被挂起，直到I/O设备完成I/O操作后，设备控制器便向CPU发送一个中断请求，CPU响应后便转向中断处理程序，中断处理程序执行相应的处理，处理完后解除相应进程的阻塞状态

处理过程

• 测定是否有未响应的中断信号
• 保护被中断进程的CPU环境
• 转入相应的设备处理程序
• 中断处理
• 恢复CPU的现场并退出中断

设备驱动程序

定义、主要任务

• 设备驱动程序:是I/O进程与设备控制器之间的通信程序
• 主要任务: 接收上层软件发来的抽象I/O要求，再把它转换为具体要求后，发送给设备控制器，启动设备区执行；反之，它也将由设备控制器发来的信号传送给上层软件
• 设备驱动程序包括与设备相关的代码，它的工作是：把用户提交的逻辑I/O请求转化为物理I/O操作的启动和执行，如设备名转化为端口地址、逻辑记录转化为物理记录、逻辑操作转化为物理操作等

设备驱动程序的功能

• 将接收到的抽象要求转换为具体要求；
• 检查用户I/O请求的合法性，了解I/O设备的状态，传递有关参数，设置设备的工作方式；
• 发出I/O命令，启动分配到的I／O设备，完成指定的I／O操作；
• 及时响应由控制器或通道发来的中断请求，并根据其中断类型调用相应的中断处理程序进行处理；
• 对于设置有通道的计算机系统，驱动程序还应能够根据用户的I/O请求，自动地构成通道程序

设备驱动程序的特点

• 驱动程序主要是指在请求I/O的进程与设备控制器之间的一个通信和转换程序。
• 驱动程序与设备控制器和I/O设备的硬件特性紧密相关， 因而对不同类型的设备应配置不同的驱动程序。
• 驱动程序与I/O设备所采用的I/O控制方式紧密相关。
• 由于驱动程序与硬件紧密相关， 因而其中的一部分必须用汇编语言书写。

设备处理方式

• 为每一类设备设置一个进程，专门用于执行这类设备的I/O操作 .
• 在整个系统中设置一个I/O进程，专门用于执行系统中所有各类设备的I/O操作。
• 不设置专门的设备处理进程，而只为各类设备设置相应的设备处理程序(模块)， 供用户进程或系统进程调用。

设备驱动程序的处理过程

• 将抽象要求转换为具体要求
• 检查I/O请求的合法性
• 读出和检查设备的状态
• 传送必要的参数
• 工作方式的设置
• 启动I/O设备

==I/O设备的控制方式==

宗旨

尽量减少主机对I/O控制的干预，把主机从繁杂的I/O控制事务中解脱出来，以便更多地去完成数据处理任务

使用轮询的可编程I/O方式

• 在这种方式下，输入输出指令或询问指令测试一台设备的忙闲标志位，决定主存储器和外围设备是否交换一个字符或一个字
• 一旦CPU启动I/O设备，便不断查询I/O设备的准备情况，终止原程序的执行，浪费CPU时间；
• I/O准备就绪后，CPU参与数据传送工作，而不能执行原程序，
• CPU和I/O设备串行工作，使主机不能充分发挥效率，外围设备也不能得到合理使用，整个系统效率很低。

使用中断的可编程I/O方式

• CPU启动I/O设备后，不必查询I/O设备是否就绪，继续执行现行程序。
• 设备控制器按照命令要求去控制指定的I/O设备，当数据准备好后，即进入数据寄存器后，控制器通过控制线向CPU发送中断信号
• I/O操作直接由CPU控制，每传送一个字符或字，要发生一次中断，仍然消耗大量CPU时间
• 不必忙式查询I/O准备情况，CPU和I/O设备可实现部分并行，与程序查询的串行工作方式相比，使CPU资源得到较充分利用

==直接存储器(DMA)访问方式==

如果I/O设备能直接与主存交换数据而不占用CPU，CPU的利用率还可提高，这就出现了直接存储器存取DMA方式

==特点==:

• 数据传输的基本单位是数据块，在主机与I/O设备之间每次至少传递一个数据块；
• 所传送的数据块是从设备直接送入内存；
• 在传送一个或多个数据块的开始和结束才需CPU干预，传送过程是在控制器的控制下完成

image

==DMA控制器的组成==

• 主机与DMA控制器的接口
• DMA控制器与块设备的接口
• I/O控制逻辑

==DMA工作流程==

image

I/O通道控制方式

I/O通道控制方式的引入

• 为获得CPU和外围设备间更高的并行工作能力，也为了让种类繁多，物理特性各异的外围设备能以标准的接口连接到系统中，计算机系统引入了自成独立体系的通道结构
• 由通道管理和控制I/O操作，减少了外围设备和CPU的逻辑联系。把CPU从琐碎的I/O操作中解放出来

==与DMA方式的区别==

• 通道控制方式与DMA方式相类似，也是一种内存和设备直接进行数据交换的方式。与DMA方式不同的是，在通道控制方式中，数据传送方向、存放数据的内存始址及传送的数据块长度均由一个专门负责输入/输出的硬件——通道来控制。
• 另外，DMA方式每台设备至少需要一个DMA控制器，而通道控制方式中，一个通道可控制多台设备与内存进行数据交换

==通道程序==

• 操作码。
• 内存地址。
• 计数。
• 通道程序结束位P。
• 记录结束标志R。

与设备无关的I/O软件

设备独立性的概念

• 也称为设备无关性。 其基本含义是： 应用程序独立于具体使用的物理设备。
• 引入了逻辑设备和物理设备这两个概念
• 在应用程序中， 使用逻辑设备名称来请求使用某类设备；而系统在实际执行时， 还必须使用物理设备名称。
• 系统须具有将逻辑设备名称转换为某物理设备名称的功能

设备独立性的好处

• 设备分配时的灵活性
• 易于实现I/O重定向

与设备无关的软件

• 设备驱动程序的统一接口
• 缓冲管理
• 差错控制
• 对独立设备的分配与回收
• 独立于设备的逻辑数据块

为什么要引入设备独立性？如何实现设备独立性？

引入设备独立性，可使应用程序独立于具体的物理设备，是设备分配具有灵活性。另外容易实现I/O重定向。
为了实现设备独立性，必须在设备驱动程序之上设置一层设备独立性软件，用来执行所有I/O设备的公用操作，并向用户层软件提供统一接口。关键是系统中必须设置一张逻辑设备表LUT用来进行逻辑设备到物理设备的映射，其中每个表目中包含了逻辑设备名、物理设备名和设备驱动程序入口地址三项；当应用程序用逻辑设备名请求分配I/O设备时，系统必须为它分配相应的物理设备，并在LUT中建立一个表目，以后进程利用该逻辑设备名请求I/O操作时，便可从LUT中得到物理设备名和驱动程序入口地址。

设备分配

设备分配程序

物理设备名->SDT(系统设备表)->DCT(设备控制表)->
COCT(控制器控制表)->CHCT(通道控制表)->LUT(逻辑设备表)

设备分配时应考虑的因素

1. 设备的固有属性

• 独享设备。
• 共享设备。
• 虚拟设备。

2. 设备分配算法

• 先来先服务。
• 优先级高者优先。

3. 设备分配中的安全性

• 安全分配方式
• 不安全分配方式

独占设备的分配程序

基本的设备分配程序

• 分配设备
• 分配控制器
• 分配通道

设备分配程序的改进

• 增加设备的独立性
• 考虑多通路情况

逻辑设备名到物理设备名映射的实现

为了实现设备的独立性，系统必须设置一张逻辑设备表(LUT)，
用于将应用程序中所使用的逻辑设备名映射为物理设备名。

LUT的设置问题:

• 第一种方式是在整个系统中只设置一张LUT。
• 第二种方式是为每个用户设置一张LUT。

SPOOLing技术——假脱机系统

SPOOLing：即同时联机外围操作，又称脱机操作。在多道程序环境下，可利用多道程序中的一道程序，来模拟脱机的输入输出功能。即在联机条件下，将数据从输入设备传送到磁盘，或从磁盘传送到输出设备。

组成: 输入井和输出井、输入缓冲区和输出缓冲区、输入进程和输出进程、井管理程序

SPOOLing系统特点：提高了I/O的速度、将独占设备改造成共享设备、实现了虚拟设备功能。

共享打印机——SPOOLing技术的典型实例

打印机属于独享设备。 用SPOOLing技术转换为共享设备，提高设备的利用效率。
用户请求打印后：
1.输出进程在输出井中申请一个空闲磁盘块区， 并将要打印的数据送入其中。
2.输出进程申请并填写一张空白的用户请求打印表，再将该表挂到请求打印队列上
3. 打印机空闲时，首取第一张请求表，将数据从输出井传送到内存缓冲区，进行打印

磁盘存储器的性能和调度

磁盘的类型

• 固定头磁盘:
  每条磁道上都有一读/写磁头，所有的磁头都被装在一刚性磁臂中。可以并行读/写。
• 移动头磁盘:
  每一个盘面仅配有一个磁头，也被装入磁臂中。仅能以串行方式读/写

磁盘访问时间

image

磁盘调度

目标: 使磁盘的平均寻道时间最短

先来先服务算法

原理: 根据进程请求访问磁盘的先后次序进行调度

优点: 公平，简单，每个进程的请求都能依次地得到处理，不会出现某一进程的请求长期得不到满足的情况

缺点: 平均寻道时间较长

最短寻道时间优先算法

原理：选择有距当前磁头所在磁道最近的访问磁道的进程。

优点: 比FCFS有更好的寻道性能

缺点: 可能导致某个进程发生饥饿现象

image

SCAN算法——电梯调度算法

原理：选择与当前磁头移动方向一致且距离最近的进程。

优点：寻道性能较好避免出现“饥饿”现象

循环扫描(CSCAN)算法

规定磁头单向移动。

image

image