操作系统

一、操作系统引论

1.1 操作系统的目标和作用

联机命令接口：交互式命令接口

脱机命令接口：批处理命令接口

裸机：没有任何软件支持的计算机

什么是操作系统:

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

OS的目标：

• 方便性：使计算机更易于使用
• 有效性：以更有效的方式使用计算机系统资源
  • 提高系统资源利用率
  • 提高系统吞吐量
• 可拓展性：允许有效地开发，测试和引进新的系统功能。
• 开放性：实现应用程序的可移植性和互操作性**,要求具有统一的开放的环境

OS的作用：

• 作为用户与计算机硬件系统之间的接口
• 作为计算机系统资源的管理者(软件和硬件资源)
• 用作扩充机器

1.2 操作系统的发展过程

• 手工操作阶段

  • 缺点：
    • 用户独占全机
    • cpu等待人工操作
    • 人机速度矛盾导致资源利用率低

• 批处理阶段

  • 单道批处理系统

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

    缺点：资源利用率不高、平均周转时间长、没有交互能力

  • 多道批处理系统(操作系统开始出现)

    特征：调度性、无序性、多道性

    缺点：平均周转时间长、没有交互能力

• 分时操作系统

  特征：多路性、独立性、及时性、交互性

• 实时操作系统

  特征：多路性、独立性、交互性、可靠性、及时性

1.3 操作系统的基本特性

现代OS的四个基本特征

• 并发性

  • 并行：指两个或多个事件在同一时刻发生
  • 并发：指两个或多个事件在同一时间间隔内发生

• 共享性

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

  • 互斥共享：一段时间内只允许一个进程使用，这种资源称为临界资源
  • 同时访问方式：一段时间内，多个进程可以同时使用这个资源，从微观上看，是多个进程交替互斥地使用这个资源

• 虚拟性

  是指的通过某种技术把一个物理实体变为若干个逻辑上的对应物，用于实现虚拟的技术成为虚拟技术

  • 时分复用技术
    • 虚拟处理机，分时实现
    • 虚拟设备，SPOOLing
  • 时分复用技术
    • 虚拟磁盘：逻辑分区
    • 虚拟存储器：虚拟存储管理实现

• 异步性

  异步性：多道程序环境下程序以异步的方式执行，每道程序在何时执行都是不确定的

1.4 操作系统的主要功能

• 处理机管理功能
• 存储器管理
• 设备管理
• 文件管理
• 操作系统与用户之间的接口

1.5 操作系统的体系结构

• 无结构操作系统
• 模块结构OS
• 分层式结构OS
• 微内核OS结构

二、进程的描述与控制

2.1 程序执行

可执行文件运行的过程

a.out--作业调度-->装入内存--创建-->进程---->就绪队列--调度-->进程调度

程序并发执行时的特征：

• 间断性
• 不可再现性
• 失去封闭性

程序顺序执行时的特征：

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

2.2 进程的描述

2.2.1 进程的定义和特征

进程：

• 进程是程序的一次执行，进程是系统进行资源分配和调度的一个基本单位

特征：

• 结构性
• 动态性：是进程最基本的特征，也就是有生命周期。
• 并发性
• 独立性
• 异步性

PCB的内容：

• 进程标识符

• 内部标识符，方便系统使用

• 外部标识符，由创建者提供，通常是字母数字组成，由用户访问该进程时使用

• 处理机状态：主要是由处理机的各种寄存器中的内容组成，比如通用寄存器，程序计数器，程序状态字PSW，用户栈指针

• 进程的调度信息：比如进程的状态，进程的优先级，堵塞的原因

• 进程的控制信息：比如程序和数据的地址，进程同步和通信机制，资源清单，链接指针

PCB的作用：

• 是进程存在的唯一标志
• 能实现间断性运行方式
• 提供进程管理所需要的信息
• 提供进程调度所需要的信息
• 实现与其他进程的同步与通信

进程的结构：

为使程序(含数据)能独立运行，应为之配置一进程控制块，即PCB

进程实体（进程在某个时间点的快照）：

• 程序段
• 数据段
• PCB：PCB是给操作系统用的，程序段和数据段是程序自己用的

2.2.2 进程的基本状态及切换

进程的三种基本状态

• 就绪状态：万事俱备，只欠cpu
• 执行状态
• 阻塞状态

image-20230306201505467

进程挂起状态的原因

• 父进程请求
• 终端用户的请求
• 负荷调节的需要
• 操作系统的需要。希望挂起某进程，检车资源使用情况或进行记账

被挂起进程的特征

• 不能立即执行
• 可能是等待某事件发生。若是，则堵塞条件独立于挂起条件，即使堵塞事件发生，该进程也不能执行
• 使之挂起的进程为OS，自身，或其他进程
• 只有使之挂起的进程才能使之由挂起状态转换为其他状态

2.2.3 进程的组织

实际就是PCB的组织

• 线性方式：所有PCB在一张线性表中
• 链接方式：按照进程状态，将PCB分为多个队列
  • 执行指针
  • 就绪队列指针
  • 阻塞队列指针
• 索引方式：根据进程状态的不同，建立几张索引表
  • 执行指针
  • 就绪表指针
  • 阻塞表指针

2.3 进程控制

进程控制：就是实现进程状态的转换

原语：是一种特殊的程序，它的执行具有原子性，进程的控制用原语实现

处理机的执行态：

• 系统态，又称管态，也称为内核态
• 用户态，也称目态

OS内核包含两大功能：

• 支撑功能
• 资源管理功能

进程/原语创建过程：

1. 申请空白PCB
2. 为新进程分配资源
3. 初始化空白的PCB
   • 初始化标识信息
   • 初始化处理机状态信息
   • 初始化处理机控制信息
4. 将PCB插入就绪队列

引起进程终止的事件：

• 正常结束

• 异常结束

• 外界干预

撤销原语的过程：

• 从PCB集合中找到终止进程的PCB，读出进程状态
• 若进程正在进行，立即剥夺CPU，将CPU分配给其他进程
• 终止所有子进程
• 将该进程拥有的所有资源归还给父进程或操作系统
• 将被终止进程的PCB从所在队列移出

引起进程堵塞的事件：

• 请求系统服务,比如IO
• 启动某种操作，只有该操作完成后才能继续执行
• 新数据尚未到达
• 无新工作可做

进程堵塞过程：

• 把PCB中的状态改为堵塞，并且把PCB插入到堵塞队列
• 转调度程序重新调度

进程唤醒过程：

• 首先把被堵塞的进程从该事件的堵塞队列中移出，然后把PCB中的现行状态由堵塞改为就绪
• 将PCB插入到就绪队列中

进程挂起的执行过程：

• 首先检查进程状态，若是活动就绪，改为静止就绪；活动堵塞改为静止堵塞
• 为了方便用户或OS考察该进程的运行情况而把该进程的PCB复制到某个特定区域
• 若被挂起的程序正在执行，则转向调度程序重新调度

进程的激活过程：

• 先将进程从外存调入内存，检查该进程的现行状态
• 若是静止就绪，便将之改为活动就绪；若为静止阻塞，便将之改为活动阻塞

引起进程切换的事件：

• 当前进程时间片到
• 有更高优先级的进程
• 当前进程主动阻塞
• 当前进程终止

进程切换的基本步骤：

• 保存进程上下文环境，将运行环境放到PCB中，更新PCB的状态，比如将改为就绪
• 更新PCB，改变其状态
• 将PCB移到相应的队列
• 改变需投入运行的进程的PCB内容，改变其运行状态
• 恢复需投入运行的进程的上下文环境

2.4 进程同步

临界资源：一次仅允许一个进程访问的资源为临界资源

为了实现对临界资源的互斥访问(同步机制应该遵循的原则)，需要遵循以下原则：

• 空闲让进
• 忙则等待
• 有限等待：也就是保证不会饥饿
• 让权等待：当进程不能进入临界区的时候，应该立即释放处理机

什么是进程同步？

• 就是要让并发进程按照要求有序地推进

进程同步的主要任务：

• 是使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。

2.4.1 软件实现方法

单标志法：

int turn = 0;
// 进程1
while (turn!=0){ // 进入区
    critical section; // 临界区
    turn = 1; // 退出区
    remainder section; // 剩余区
}
// 进程2
while (turn!=1){
    critical section;
    turn = 0;
    remainder section;
}

缺点：违背了空闲让进原则。也就是，假如进程1明明不需要访问临界资源，但是进程2也不一定可以访问。

双标志先检查法：

先看一下对方是否有意愿，然后再进入临界区。

bool flag[2];
flag[0] = false;
flag[1] = false;
// 进程1
while (flag[1]);
flag[0] = true;
critical section;
flag[0] = false;
remainder section;
// 进程2
while (flag[0]);
flag[1] = true;
critical section;
flag[1] = false;
remainder section;

违反了忙则等待原则。

双标志后检查法：

bool flag[2];
flag[0] = false;
flag[1] = false;
// 进程1
flag[0] = true;
while (flag[1]);
critical section;
flag[0] = false;
remainder section;
// 进程2
flag[1] = true;
while (flag[0]);
critical section;
flag[1] = false;
remainder section;

虽然解决了忙则等待原则，但是违背了空闲让进和有限等待原则。

Peterson皮特森算法：

bool flag[2];
int turn = 0; // 表示哪个进程优先进入临界区
// 进程1
flag[0] = true; // 表达自己的意愿
turn = 1; // 愿意让对方先使用
while (flag[1] && turn==1){
    critical section;
    flag[0] = false;
    remainder section;
}
// 进程2
flag[1] = true; // 表达自己的意愿
turn = 0; // 愿意让对方先使用
while (flag[0] && turn==0){
    critical section;
    flag[1] = false;
    remainder section;
}

缺点：未遵循让权等待原则；

2.4.2 硬件实现方法

中断屏蔽算法：

优点：简单，高效

缺点：不适用多处理机；只适合操作系统内核，不适用用户进程(因为开关中断只能运行在内核态，如果让用户随意使用会很危险)。

Test And Set指令：

优点：简单，适用于多处理机

缺点：不满足让权等待原则。

Swap指令(XCHG指令，Exchange指令)

优点：实现简单，适用于多处理机

缺点：不满足让权等待原则。

2.4.3 信号量机制

信号量可以理解为一种变量，表示系统中某种资源的数量

wait和signal常简称为P、V操作

整型信号量

表示系统中某种资源的数量，仍然未满足让权等待原则，会出现忙等，很少使用。

int S = 1;
void wait(int S){
    while (S <= 0);
    S = S - 1;
}
void signal (int S){
    S = S + 1;
}

记录型信号量

什么是记录型信号量：就是用记录型数据结构表示的信号量

typedef struct {
    int value;// 剩余资源数
    struct process *L;// 等待队列
} semaphore;
void wait(semaphore S){
    S.value--;
    if (S.value<0){
    	block (S.L);
    }
}
void signal(semaphore S){
    S.value++;
    if (S.value<=0){
    	wakeup (S.L);
    }
}

如何利用信号量机制实现进程同步？

P1(){
    code 1;
    code 2;
    V(S);
    code 3;
}
P2(){
    P(S);
    code 4;
    code 5;
}
// 上面的代码能保证code 4之前先运行code 1 和 code 2;

2.4.4 经典进程的同步问题

生产者-消费者问题

实现互斥的P操作，一定要在实现同步的P操作之后

两个V操作的操作顺序可以交换

semaphore mutex = 1;
semaphore empty = 1;
semaphore full = 0;
void producer(){
    while(1){
        wait(empty);
        wait(mutex);
        //produce
        signal(mutex);
        signal(full);
    }
}
void consumer(){
    while(1){
        wait(full);
        wait(mutex);
        //consume
        signal(mutex);
        signal(empty);
    }
}

多生产者多消费者问题：也就是生产者或消费者各自的种类有很多，而不是数量

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果，仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果用PV操作实现上述过程.

semaphore mutex = 1;
semaphore plate = 1; //盘子中有多少空位
semaphore apple = 0;
semaphore orange = 0; 
void dad(){
    wait(plate);
    wait(mutex);
    produce an apple;
    signal(mutex);
    signal(apple);
}
void mum(){
    wait(plate);
    wait(mutex);
    produce an orange;
    signal(mutex);
    signal(orange);
}
void son(){
    wait(orange);
    wait(mutex);
    eat an orange;
    signal(mutex);
    signal(plate);
}
void daughter(){
    wait(apple);
    wait(mutex);
    eat an apple;
    signal(mutex);
    signal(plate);
}

吸烟者问题

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料: 烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复(让三个抽烟者轮流地抽烟)。

semaphore offer1 = 0;
semaphore offer2 = 0;
semaphore offer3 = 0;
semaphore finish = 0; // 抽烟是否完成
void provider(){
    while(1){
        if(i==0){
            V(offer1);
        }else if(i==1){
            V(offer2);
        }else{
            V(offer3);
        }
        P(finish);
        i = (i + 1) % 3;
    }
}
void smoker1(){
    P(offer1);
    preduce;
    V(finish);
}
void smoker2(){
    P(offer2);
    preduce;
    V(finish);
}
void smoker3(){
    P(offer3);
    preduce;
    V(finish);
}

哲学家进餐问题

一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子(一根一根地拿起)。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

思路一：最多允许有4个哲学家同时进餐

semaphore chopstick[5]={1,1,1,1,1}
semaphore room = 4;
while(1){
    think;
    wait(room);
    wait(chopstick[i]); 
    wait(chopstick[(i+1)%5]);
    eat;
    signal(chopstick[i]); 
    signal(chopstick[(i+1)%5]);
    signal(room);
}

思路二：奇数号哲学家先拿左边的筷子，再拿右边的，偶数号哲学家相反。

semaphore chop[5]={1,1,1,1,1}
while(1){
    think;
    if (i % 2) == 0{
        wait(chop[i]);
        wait(chop((i+1)%5));
        eat;
        signal(chop[i]);
        signal(chop((i+1)%5));
    }else{
        wait(chop((i+1)%5));
        wait(chop[i]);
        eat;
        signal(chop((i+1)%5));
        signal(chop[i]);
    }
}

读者-写者问题

要求：

• 读进程可以共享同一对象
• 写进程无法共享同一对象
• 任一写者在完成写操作之前不允许其他读者或写者工作
• 写者在执行写操作前保证已有的读者和写者全部退出

semaphore wmutex = 1; // 实现互斥读写
semaphore cntMutex = 1; // 实现count变量的原子操作
int count = 0; // 记录有几个进程在访问文件
semaphore wPriority = 1; // 用于实现写优先
void writer()
    whilt(1){
    	wait(wPriority);
        wait(wmutex);
        write file;
        signal(wmutex);
    	signal(wPriority);
    }
}
void reader(){
    while(1){
        wait(wPriority);
        wait(cntMutex);
        if(count==0){
            wait(rmutex)
        }
        count++;
        signal(cntMutex);
        signal(wPriority);
        //read file;
        wait(cntMutex);
        count--;
        if(count==0){
            signal(rmutex);
        }
        signal(cntMutex);
    }
}

2.4.5 管程

引入管程的目的：更方便的实现进程互斥和同步。

由编译器负责实现各进程互斥地进入管程中的过程。例如Java中的synchronized修饰符。

2.6 进程通信

为了保证安全，一个进程不能直接访问另一个进程的地址空间

进程通信分为两类：

• 低级通信：信号量机制

  缺点：

  • 效率低
  • 对用户不透明

• 高级通信：直接利用操作系统提供的一组通信命令

  特点：效率高，通信细节对用户透明

2.6.1 共享存储

两个进程对共享空间的访问必须是互斥的

• 基于数据结构的共享：数据的形式是固定的，这种共享方式速度慢，限制多，是一种低级的通信方式
• 基于存储区的共享：在内存中画出一块共享区，数据的形式、存放位置都由进程控制，而不是操作系统，这种共享方式速度更快，更加高级

2.6.2 消息传递

• 直接通信方式：消息直接挂到接收进程的消息缓冲队列上
• 间接通信方式：消息先发送到中间实体(信箱)

2.6.3 管道通信

就是用于连接读写进程的共享文件，其实就是在内存中开辟一个大小固定的缓冲区

管道只能采用半双工通信，某一个时间段只能实现单向的传输。

功能：大量的数据发收。

2.7 线程

进程的概念体现了两个基本属性：

• 资源所有权

• 调度执行

线程不进行资源管理

线程的属性：

• 线程是可以并发执行的
• 共享进程资源
• 进程中所有的线程共享同一个地址空间，挂起进程会挂起所有线程
• 线程是轻型实体，在切换时只需保存少量寄存器的内容，不涉及存储器的管理，因此系统开销小

进程和线程的比较：

1. 调度：二者都是调度的基本单位，但是进程与资源绑定，线程不绑定；A进程到B进程是需要进程切换的，A线程到B线程在进程内部无需切换
2. 并发性：进程是进程间并发，线程既可以是同一个进程内的线程并发，也可是多个进程的线程并发
3. 拥有资源：进程是拥有资源的基本单位，线程共享进程内的资源
4. 系统开销：进程创建和撤销进程的开销大，线程小
5. 独立性：进程独立性高，同一个进程的多个线程独立性很低，共享同一进程的堆栈
6. 运行基础：进程可脱离线程独立运行，线程必须在进程内部运行

TCB的内容：

• 线程表示符(进程之内唯一)
• 一组寄存器：它包括PC和堆栈指针中的内容
• 线程运行状态
• 优先级
• 专有存储区
• 用户栈：保存局部边和返回地址
• 信号屏蔽

线程的分类:

• 内核支持线程KST

  优点：

  • 内核中可以同时把同一个进程中的线程调度到多个处理器中并行执行

• 如果进程中的一个线程被阻塞。内核可以调度同一个进程中的另一个线程，也可以运行其他进程的线程

• 内核例程本身也可以多线程

• 结构简单，高效

缺点：

• 系统开销大

• 用户级线程ULT

无需内核的支持

优点：

• 线程控制块设置在用户空间，内核完全不知道用户级线程的存在，这样可以节省模式切换系统开销
• 各进程可以独立选择线程调度算法
• 与操作系统无关，甚至可以在不支持线程机制的操作系统平台实现

缺点：

• 当线程执行系统调用引起进程阻塞时，进程中所有的线程都会被阻塞

• 不能有效利用多处理机

• 混合状态，也就是多线程模型

  • 一对一模型：一个用户级线程对应一个内核级线程

    优点：

    • 一个线程堵塞后，其他线程可以继续执行，并发能力强。

    • 多个线程可以在多核处理机上并行运行

    缺点：一个进程要占用多个内核级线程，系统开销大

  • 多对一模型：多个用户级线程对应一个内核级线程，且一个进程只分配到一个内核级线程

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

    缺点：一个用户级线程堵塞后整个进程都会被堵塞，并且不可以并行运行

  • 多对多模型：n个用户级线程对应m个内核级线程，且n≥m

线程的实现：https://www.bilibili.com/video/BV1V84y1Y77s?t=415.6&p=2

• 内核支持线程的实现

系统为每个进程创建任务数据区

• 用户级线程的实现
  • 运行时系统，也就是虚拟机

三、处理机调度与死锁

3.1 处理机调度的基本概念

高级调度(作业调度)：

• 用于决定外存尚处于后备队列中的哪些作业调入内存，主要用户批处理系统，运行频率最低

低级调度(进程调度)：

• 用来决定就绪队列中的哪个进程应获得处理机，由分派程序实现，主要用户交互式系统。频率最高，是毫秒级

中级调度(内存调度)：

• 提高内存的利用率和系统吞吐量，也就是就绪状态和挂起状态的切换，主要用户具有对换功能的系统

调度的目标：

• 提高处理机的利用率
• 提高系统吞吐量
• 尽量减少进程的响应时间
• 防止进程长期得不到运行

调度的原则：

• 满足用户的需要和系统的需要

调度算法的共同目标：

• 资源利用率
• 公平性
• 平衡性
• 策略强制执行

CPU利用率 = cpu的有效工作台时间/总时间

面向用户的准则：

• 周转时间尽量短
• 响应时间快
• 截止时间的保证
• 优先权准则

面向系统的准则：

• 系统吞吐量高
• 处理机利用率好
• 各类资源的平衡利用

批处理系统的目标：

• 平均周转时间短
• 系统吞吐量高
• 处理机利用率高

分时操作系统的目标：

• 响应时间快
• 均衡性

实时操作系统的目标：

• 截止时间的保证
• 可预测性

周转时间包括哪个四部分：

• 作业在外存后备队列上等待调度的时间
• 进程在就绪队列上等待进程调度的时间
• 进程在CPU上执行的时间
• 进程等待I/O操作完成的时间

3.2 作业与作业调度

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

• 收容状态
• 运行状态
• 完成状态

调度算法

• ==先来先服务FCFS==

  缺点：对短进程不公平，如果排在队列后面，等待时间远大于执行时间。

• ==短作业优先SJF==

  缺点：

  • 对长作业不利
  • 不能保证紧迫性作业会被及时处理
  • 用户对执行时间估计的不准确，算法不一定能真正做到短作业优先调度

• 优先级调度算法PSA

• ==高响应比优先调度==

  优点：既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务

  缺点：每次调度前，都会先做相应比的计算，会增加系统开销

3.3 进程调度

RR和多级反馈队列是抢占式的，PSA可能抢占，也可能不抢占

进程调度的任务

• 保存现场
• 选取进程
• 把处理机分配给要执行的进程

进程调度方式

• 非抢占式

• 抢占方式

  抢占的主要原则是什么？

  • 优先权
  • 短进程优先
  • 时间片原则

  使用抢占式的原因：

  • 批处理：防止长进程长期占用CPU，不公平
  • 分时：人机交互
  • 实时：紧迫任务的执行

进程调度算法

• 轮转调度算法(抢占式)

  对于短的、计算型进程比较有利

• 优先级调度算法

• 多队列调度算法

• 多级反馈队列调度算法

3.4 实时调度

实现实时调度的基本条件

1. 提供必要的信息
2. 系统处理能力强
3. 采用抢占式调度机制
4. 具有快速切换机制

3.5 死锁概述

死锁：

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

为什么死锁？

• 竞争资源
  • 可重用资源的竞争
  • 可消耗资源的竞争
• 进程推进顺序非法

死锁的发生必须具备下列四个必要条件：

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

处理死锁的方法

• 预防死锁：通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件
• 避免死锁：在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁
• 检测死锁：通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源
• 解除死锁：检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。

3.6 预防死锁

预防死锁：通过设置某些限制条件，破坏产生死锁的四个必要条件中的一个或几个。

• 破坏“互斥”条件：很少，例如SPOOLing技术，也就类似加上一个任务队列，使每个进程在逻辑上以为资源是共享的。

• 破坏“请求和保持”条件：

  所有进程在开始运行前，都必须一次性地申请整个运行过程所需的全部资源。

  • 优点：简单，易于实现且很安全
  • 缺点：资源被严重浪费，使进程延迟运行

• 摒弃“不剥夺”条件：

  当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放所有正在保持的资源。

  缺点：

  • 实现起来比较复杂，且要付出很大的代价。
  • 一个资源在使用一段时间后，他的被迫释放可能会造成前段工作的失效。
  • 会使进程前后两次运行的信息不连续。
  • 因反复地申请和释放资源，致使进程被无限推迟，延长进程周转时间，增加系统开销，降低吞吐量。

• 摒弃“环路等待”条件：

  采用顺序资源分配法。首先给系统的资源进行编号，规定每个进程必须按照编号递增的顺序请求资源，同类资源一次申请完。

  存在严重问题：

  • 为系统中各类资源分配的序号必须相对稳定，限制了新设备类型的增加。
  • 会经常发生作业使用的顺序与系统规定顺序不同的情况，造成资源浪费。
  • 增加了程序设计难度。

3.7 避免死锁

避免死锁：在资源的动态分配过程中，用某种方法去阻止系统进入不安全状态，从而避免发生死锁。

银行家算法步骤:

1. 检查此次申请是否超过了之前声明的最大需求数
2. 检查此时系统剩余的可用资源是否还能满足这次请求
3. 试探着分配，更改各数据结构
4. 用安全性算法检查此次分配是否会导致系统进入不安全状态

安全性算法步骤:

• 检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列。并把该进程持有的资源全部回收。
• 不断重复上述过程，看最终是否能让所有进程都加入安全序列。

3.8 死锁的检测和解除

检测死锁的算法:

• 在资源分配图中，找出既不阻塞又不是孤点的进程Pi。消去它所有的请求边和分配边，使之称为孤立的结点。
• 进程Pi所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。若能消去途中所有的边，则称该图是可完全简化的。

当发现发生死锁的时候，如何解除死锁？

• 剥夺资源：也就是挂起一些死锁进程，将其资源分配给其他死锁进程
• 撤销进程：强制撤销部分甚至全部死锁进程，并剥夺资源，实现简单，但是付出的代价可能很大
• 进程回退：让死锁进程回退到足以避免死锁的地步。这要求系统要记录进程的历史信息，设置还原点。

最小代价原则：

• 进程优先级最小的进程
• 已经花费处理机时间最小的进程
• 未执行部分最多的进程
• 已获资源量最少的进程
• 到目前为止，产生输出量最少的进程
• 批处理进程

四、存储器管理

4.1 地址转换

将源程序变为在内存中执行的程序通常要经历三步骤

1. 编译：将源代码转换成若干个目标模块
2. 链接：将一组目标模块和他们所需要的目标库函数链接在一起，形成一个完整的装入模块
3. 装入：由装入程序将装入模块装入内存

4.1.1 装入

1. 绝对装入方式：

• 编译程序产生绝对地址的目标代码。
• 缺点:
  • 只适合单道程序环境

2. 可重定位装入方式：

• 经编译得到的目的模块中相对地址，通常从0开始。地址变换是在装入内存时一次完成的，且以后不能移动

• 优点：

  • 不需要硬件支持，可以装入有限多道程序

• 缺点：

  • 程序通常需要占用连续的空间，程序装入内存后不能移动，不易实现共享

3. 动态运行时装入方式：

• 也就是动态重定位，把地址转换推迟到程序执行时进行，可以利用硬件地址变换机构

• 优点：

  1. 主存的使用更加灵活有效。一个用户的作业不一定要分配在一个连续的存储区，因而可以使用较小的分配单位；作业开始前也不一定要把它的地址空间全部装入内存，可以在作业执行期间根据请求动态地分配

  2. 几个作业共享一个程序段的单个副本比较容易

  3. 用户可以运行比主存存储空间大得多的程序

• 缺点：

  1. 需要硬件支持

  2. 实现存储器管理的软件比较复杂

4.1.2 链接

根据链接时间的不同，可把链接分为三种：

1. 静态链接

• 在程序执行之前就把各目标模块以及他们所需的库函数链接成一个完成的可执行文件，以后不再拆开

• 需要解决若干问题：

  • 修改相对地址

  • 改变外部调用符号为相对地址

2. 装入时动态链接

• 边装入边链接

• 优点:

  • 便于软件修改和更新
  • 便于实现目标模块共享

3. 运行时动态链接

• 在程序执行中需要该模块时，才对他进行链接

• 优点:

  • 凡是在执行过程中未用到的目标模块，都不会调入内存和链接到模块上，这样不仅可以加快程序的装入过程，也可节省大量的内存空间

4.2 内存的分配与回收

4.2.1 连续分配方式

:star: 连续分配的三种方式

概念：连续分配方式是为用户程序分配一个连续的内存空间

• 单一连续分配方式

  • 概念：
    • 内存被分为两个部分：系统区和用户区
    • 系统区通常位于内存的低地址部分
    • 用户区存放用户进程相关的数据，内存中只能有一道用户程序，用户程序独占整个用户区空间
  • 优点：
    • 实现简单，易于管理
  • 缺点：
    • 对要求内存少的程序，造成内存浪费
    • 程序全部装入，很少使用的程序部分也占有内存

• 固定分区分配

  • 概念：

    • 将整个用户空间分为若干个固定大小的分区，每个分区中只装入一道作业

  • 分类：

    • 分区大小相等：适用于一台计算机控制多个相同对象的场合
    • 分区大小不等

  • 操作系统如何记录内存分类情况

    • 建立一个数据结构--分区说明表

    分区号	大小	起始地址	状态
    1	2	8	未分配

  • 优点：

    • 易于实现，开销小，无外零头

  • 缺点：

    • 有内部碎片
    • 分区总数固定，限制了并发执行的程序数目
    • 存储空间利用率太低

• 动态分区分配(可变分区分配)

  • 概念：
    • 在进程装入内存的时候根据进程的大小动态的建立分区
  • 采用什么样的数据结构记录
    • 空闲分区表：参照分区说明表
    • 空闲分区链
  • 数目固定，大小可变
  • 数目和大小均可变

动态分区分配算法

优点考虑的方面：

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

• 最佳适应算法BF

  • 算法思想：空闲分区按照容量递增的顺序连接，找到大小能够满足的第一个空闲分区

  • 优点：为大作业分配大的空间创造了条件

  • 缺点：经过一段时间后，会产生很多很小的小分区(为了改善这种情况，就是设置一个最小分区参数G);还有一个缺点，就是回收分区的时候比较费时，因为需要进行排序。

• 最坏适应算法WF

  • 算法思想：空闲分区按照容量递减的顺序连接，找到大小能够满足的第一个空闲分区
  • 优点：使剩下的空闲分区不至于太小，产生碎片几率最小，对中、小作业有利，查找效率高
  • 缺点：会缺乏比较大的空闲分区

• 首次适应算法FF

  • 算法思想：空闲分区链以地址递增的次序链接，每次都从低地址开始查找，找到第一个能满足大小的空闲分区

  • 优点：优先使用内存低地址，为大作业分配大的内存空间创造了条件

  • 缺点：低地址被不断划分，会留下很多难以利用的、很小的的空闲分区。增加查找可用空闲分区开销。

• 循环首次适应算法NF

  • 算法思想：是基于FF的改进算法，可以把空闲分区排成一个循环链表，每次分配时从上次查找结束的位置开始

  • 优点：使空闲分区分布的更加均匀，从而减少了查找空闲分区时的开销

  • 缺点：缺乏大的空闲分区

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

• 快速适应算法QF

  优点：查询效率高，不会对任何分区切割，满足对大空间的需求

  缺点：算法复杂，系统开销大

• 伙伴系统

  在伙伴系统中，可用内存块的大小为,1≤k≤m

  优点:

  • 分配和回收内存速度快，且不会产生很多小碎片

  缺点:

  • 内存利用率不高，分配的内存大小为2的幂，有内部碎片产生

• 哈希算法

  构建一张哈希表，以空闲分区大小为关键字

紧凑

概念:

• 将内存中的所有作业移动，使他们全部邻接，可把原来分散的很多小分区合并成大分区

启动紧凑的时机:

• 载入大程序，系统无可用分区
• 发现碎片比较多，系统比较空闲时

4.2.2 非连续分配方式

• 分页存储管理
• 分段存储管理
• 段页式存储管理

A 基本分页存储管理

概念：

• 将内存空间划分位一个个大小相等的分区，每个分区称为一个页框，每个页框有一个页框号(页框也称为内存块，物理页面，页帧)
• 将进程的逻辑地址空间也划分为与页框大小相等的一个一个部分，每个部分称为一个页或者说页面，每个页有一个页号，从0开始

分页：

• 将程序地址空间分页

分块：

• 将内存空间分块
• 内存一块可以装入程序一页

优点：

• 没有外零头
• 仅有小于一个页面大小的内零头

页表：

• 每个进程对应一个页表，描述该进程的各页面在内存中对应的物理编号，页表通常在PCB中，每个页表项由页号和块号组成，记录二者之间的映射关系

• 页号是可以不存的，因为程序地址是连续的

• 由计算机中内存块的数量-->页表中页框号的位数是一个重要考点

• 计算：

  • 通用
    • 页号=逻辑地址 / 页面大小
    • 页内偏移量=逻辑地址 % 页面大小
    • 物理地址 = 页面在内存中的起始地址 + 页内偏移量
  • 若每个页面大小是B
    • 则逻辑地址的可拆分为(页号，k位页内偏移量)
    • 则物理地址的可拆分为(页框号，k位页内偏移量)

• 页表示意图：

  页号(隐式)	块号
  0	5
  1	12
  2	18
  3	124

:star:基本地址变换机构：

• 作用：借助页表将逻辑地址转换位物理地址

• 实现：在系统中设置一个页表寄存器PTR，存放页表的起始地址F和页表长度M(有多少页)

  进程未执行时，F和M存放于PCB，进程执行时，F和M被加载到PTR

• 步骤：

  • 根据逻辑地址计算页号和页内偏移量
  • 判断页号是否越界(页号是否超过PTR中的页表长度)
  • 查询页表，找到对应的页表项，确定内存块号
  • 利用内存块号和页内偏移量得到物理地址
  • 访问内存单元

• 为了更方便查找页表项，页表一般是放在连续的内存块中的

• 实际应用中，通常使一个页框恰好放入整数个页表项

页面大小的选择：

• 影响页面与页框大小的因素：页内零头，地址转换速度，页面交换效率
• 页面大小常是2的幂，通常在1KB~8KB之间

:star:具有快表的地址变换机构：

• 定义：
  • 快表，又称联想寄存器，TLB(translation lookaside buffer)，是一种高速缓存，存放最近访问的页表项的副本，可以加速地址变换的速度，内存中的页表常称为慢表
• 进程切换时，TLB会被清空
• 原理：局部性原理
  • 时间局部性原理：如果执行了程序中的某条指令/数据，那么不久后这条指令有可能再次被执行/访问
  • 空间局部性原理：一旦程序访问了某个存储单元，在不久后，其附近的存储单元也很有可能被访问
• 若快表命中，只需访问一次内存，若未命中则需要访存两次
• TLB和普通Cache的区别：TLB中只有页表项的副本，而普通Cache可能会有其它各种数据的副本

:star:两级页表：

• 单级页表存在的问题：

  • 对于32位的逻辑地址，若页面大小为4kB，因此页内地址占用12位，页号占用20位，因此一个进程最多有个页表项；页表项为4B，一个页框存取个页表项，因此需要个连续的页框，本身就违背了非连续存储的设计初衷
  • 根据局部性原理，很多时候，进程只需要访问某几个页面就可以运行了，没必要让整个页表都常驻内存

• 如何实现：

  • 将逻辑地址拆分为三部分：一级页号，二级页号，页内偏移量
  • 从PCB中读出页目录表始址，再根据一级页号查页目录表，找到下一级页表在内存中的存放位置
  • 没必要让整个页面都常驻内存，可以让页目录表新增一个字段“是否在内存中”，若想访问的页面不在内存中，就发生缺页中断，调入内存

  

  image-20230508212207795

• 注意：

  • 若采用多级页表，各级页表的大小不能超过一个页面
  • 当没有快表机构时，N级页表访问一个逻辑地址需要N+1次访存

• 页目录表示意图：

  一级页号	内存块号	是否在内存中
  0	3	是
  1	无	否
  ...	...	...

B 基本分段存储管理

定义：

• 与分页最大的区别就是离散分配时所分配地址空间的基本单位不同
• 按照程序的自身逻辑关系划分为若干个段，每个段有一个段名

分段：

• 分段系统的逻辑地址可以分为两部分：段号 段内地址
• 段号的位数决定每一个进程最多可以分为几个段
• 段内地址位数决定了每个段的最大长度是多少

引入分段存储管理方式可以满足下列需要:

• 方便编程
• 信息共享
• 信息保护
• 数据增长
• 动态链接

段表：

• 为每一个进程建立一张段映射表，记录各个逻辑段在物理内存中的位置：(段号) 段长 基址
• 各个段表项的长度是相同的
• 当发生进程切换时，从PCB加载信息到段表寄存器(存放段表始址F和段表长度M)

步骤：

• 根据逻辑地址得到段号和段内地址
• 根据段表寄存器判断是否越界(若段号S≥段表长度M则越界)
• 查询段表，找到段表项
• 检查段内地址是否超过段长(这一步与分页存储管理方式不同)
• 计算得到物理地址

分页与分段的比较：

• 页是信息的物理单位，分页主要目的是实现离散分配，提高内存利用率，对用户是不可见的
• 段是信息的逻辑单位，分段的主要目的是更好的满足用户需求，分段对用户是可见的
• 分页的用户进程地址空间是一维的，分段的用户进程地址空间是二维的
• 分段比分页更容易实现信息的共享与保护
• 页表与段表：
  • 页表：(页号) 页基址
  • 段表：(段号) 段长 段基址
• 页表寄存器与段表寄存器：
  • 页表寄存器：页表地址F 页表长度M
  • 段表寄存器：段表地址F 段表长度M
• 逻辑地址划分：
  • 分页：页号 页偏移地址
  • 分段：段号 段偏移地址

分页和分段的不同:

1. 页是物理单位，段是逻辑单位
2. 页的大小固定且由系统决定，段的长度不固定
3. 分页的作业地址空间是一维的，分段则是二维

C 段页式管理方式

定义：

• 分段+分页=段页式管理

特点：

• 分段对用户来说是可见的，程序员在编程时需要显式地给出段号，段内地址
• 分页对用户来说是不可见的，系统根据段内地址自动划分页号和页内偏移量
• 段页式管理的地址结构是二维的

逻辑地址划分：

• 段号 页号 页内偏移量
• 段号决定每个进程最多可以分为多少个段，页号决定每个段最大有多少页，页内偏移量决定了页面大小和内存块大小是多少

段表和页表：

• 每个段对应一个段表项，每个段表项由(段号),页表长度，页表起始地址组成。首先根据页表起始地址找到页表，然后根据页表找到最终的数据
• 一个进程对应一个段表，但是一个进程可能对应多个页表

4.3 内存扩充

4.3.1 覆盖技术

• 覆盖技术的思想
  • 将程序分为多个段，内存中设置一个固定区和若干个覆盖区
  • 需要常驻内存的段放在固定区中，不常用的段放在覆盖区，需要时调入内存，用不到时调出内存
• 缺点
  • 必须由程序员声明覆盖结构，操作系统完成自动覆盖，对用户不透明，增加了用户编程的负担
• 其他
  • 覆盖技术只用于早期的操作系统，现在已成为历史

4.3.2 对换技术

对换技术的设计思想 * 内存空间紧张时，系统将内存中某些进程暂时换出外存(但是PCB还在内存)，把外存中某些已具备运行条件的进程换入内存

为了实现进程对换，系统必须实现的三方面的功能

• 对换空间的管理
• 进程的换入
• 进程的换出

保存在外存的哪里 * 在具有交换功能的操作系统，通常会把磁盘空间分为文件区和对换区 * 文件区:存放文件，追求存储空间的利用率，采用离散分配方式 * 对换区：只占磁盘空间的小部分，被换出的进程数据放在对换区。对换区追求换入换出速度，因此通常采用连续分配方式 * 对换区的I/O速度比文件区的更快

换出哪些进程 * 可优先换出阻塞进程，或低优先级的进程，也会考虑进程在内存的驻留时间

其他 * 覆盖和交换的区别 * 覆盖是在同一个程序或者进程中的 * 交换是在不同进程或作业之间的

4.3.3 虚拟内存

常规存储器管理方式的特征：

• 一次性：要求将一个作业全部装入内存后才能运行
  • 大作业无法运行
  • 限制作业并发执行的程度
• 驻留性：作业装入内存后一直驻留内存直到作业完成

虚拟内存的实现思想：

• 基于局部性原理，在程序装入时，可以将程序中很快就会用到的部分装入内存，暂时用不到的放在外存
• 程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存
• 若程序内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存

虚拟内存的三个主要特征：

• 多次性：一个作业可以被分为多次调入内存
• 对换性：作业在运行过程中允许换入换出
• 虚拟性：能够从逻辑上扩充内存容量，使用户看到的内存容量远大于实际的容量

如何实现虚拟内存技术：

• 建立在非连续分配方式的基础上

请求分页存储管理方式

与基本分页存储管理的主要区别：

• 程序执行过程中，当要访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存
• 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存

系统必须提供的硬件支持:

• 请求分页的页表机制
• 缺页中断机构
• 地址变换机构

缺页中断与一般中断的区别:

• 在指令执行期间产生和处理中断信号
• 一条指令在执行期间，可能发生多次缺页中断

请求分页存储管理的页表：

• (页号，页框号Q，状态位D，访问位A，修改位M，外存地址)
• 状态位：是否已经调入内存
• 访问位：可记录最近被访问过几次，或者上次访问的时间，供置换算法参考
• 修改位：页面调入内存后是否被修改过
• 外存地址：页面在外存中的存放位置

页面置换算法

目标：尽可能的减少缺页率

最佳置换算法OPT:

• 每次选择淘汰的页面将是以后永不使用，或在最长时间里不再访问的页面
• 最佳置换算法可以保证最低的缺页率，但是这个算法不可实现，因为页面访问的未来顺序是不知道的

先进先出置换算法FIFO:

• 每次选择淘汰的页面是最早进入内存的页面
• Belady异常：当为进程分配的物理块号增大的时候，缺页次数不降反增的异常现象。在所有算法中，只有先入先出算法会产生Belady异常
• 特点：算法简单，但是性能差

最近最久未使用置换算法LRU:

• 每次淘汰的页面是最近最久未使用的页面
• 做题时可以逆向检此时在内存中的几个页面号
• 特点:算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大
• 性能最接近最佳置换算法

Clock置换算法(最近未用算法NRU):

• 简单的Clock算法:

  • 为每个页面设置一个访问位，再将内存中的页面通过链接指针链接成一个循环队列。
  • 当某页被访问时，访问页面置为1
  • 当需要淘汰一个页面时，只需检查页的访问位，若为0则置出；若是1则置为0，暂不换出，检查下一个页面
  • 若第一轮扫描中所有页面都是1，则将所有页面置为0后再进行第二轮页面。因此简单的Clock算法最多会经过两轮扫描

• 改进型的Clock算法:

  • 除了考虑一个页面最近有没有被访问过外，还应该考虑是否被修改过。在其他条件都相同时，优先淘汰没有修改过的页面

  • 算法规则：

    用(访问位，修改位)的形式表示各页面的状态

    1. 第一轮：扫描到第一个(0,0)的页面进行替换，不修改任何标志位
    2. 第二轮：若第一轮扫描失败，则重新扫描。找到第一个(0,1)的页面，同时将所有扫描过的页面访问位置为0
    3. 第三轮：若第二轮扫描失败，则重新扫描。找到第一个(0,0)的页面，不修改任何标志位
    4. 第四轮：若第三轮扫描失败，则重新扫描。找到第一个(0,1)的页面用于替换

  • 改进型的Clock算法最多会进行四轮扫描

  • 优先级理解：

    1. 第一优先级：最近未访问，也未修改的页面
    2. 第二优先级：最近未访问，但修改过的页面
    3. 第三优先级：最近访问过，但未修改的页面
    4. 第四优先级：最近访问过，也修改过的页面

缺页率的影响因素:

• 页面置换算法
• 页面大小
• 进程所分配的物理块的数目
• 程序的固有属性

页面分配策略

驻留集：请求分页存储管理中给进程分配的物理块的集合，一般小于进程的总大小

• 太小：缺页频繁
• 太大：多道程序并发度下降，资源利用率降低

物理块的分配策略：

• 固定分配：进程的物理块数目在运行期间保持不变

• 可变分配：与固定分配相反

• 局部置换：发生缺页时只能选择进程自己的物理块进行置换

• 全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，或者将别的进程持有的物理块置换到外存，再分配给缺页进程

• 注意：全局置换和固定分配是互斥的

• 分配策略的组合：

  • 固定分配局部置换

    实现这种策略的困难在于：很难确定应为进程分配多少物理块

  • 可变分配全局置换

    只要进程发生缺页，都将获得新的物理块；仅当空闲物理块用完时，系统才会选择一个未锁定的页面调出，被选择调出的页面可能是系统中任何一个进程的页，因此这个被选中的进程拥有的物理块就会减少，缺页率会增加

  • 可变分配局部置换

    刚开始会为每个进程分配一定数量的物理块，当进程缺页，只允许从自己的物理块中选择一个换出外存。若进程频繁的缺页，系统会为其多分配几个物理块，直至该进程缺页率达到适当的程度；反之，若缺页率非常低，也可适当减少分配给该进程的物理块

  总结：

  • 可变分配全局置换：只要缺页就会分配新的物理块
  • 可变分配局部置换：根据缺页的频率动态的增加或者减少进程的物理块

何时调入页面:

• 预调页策略：以预测为基础，将那些预计在不久之后便会访问的页面，预先调入内存；

  这种策略主要用于进程的首次调入

• 请求调页策略：只有缺页时才会将所缺页面调入内存

  I/O开销比较大

从何处调入页面:

• 系统拥有足够的对换区空间：

  进程运行时将全部有关文件从文件区拷贝到对换区，这样可以提高调页的速度

• 系统缺少足够的对换区空间:

  凡是不会修改的文件，都直接从文件区调入

  换出未被修改的文件时，直接丢弃

  对于那些可能被修改的部分，在将他们换出时，调到对换区，以后需要时从对换区调入

• UNIX方式:

  运行前所有数据放在文件区，从文件区直接调入；若被使用的页面需要换出，则写回对换区，下次从对换区调入

抖动：

• 刚刚换出的页面又要换入内存，刚刚换入的页面又要换出内存
• 原因：进程频繁访问的页面数目高于可用的物理块数

工作集:

• 在某段时间间隔里，进程实际访问页面的集合
• 工作集窗口:可以看做时间段
• 工作集大小可能小于窗口尺寸
• 一般来说，驻留集大小不能小于工作集大小，否则进程在运行中会频繁缺页

五、设备

5.1 IO系统简介

设备管理的对象：主要是IO设备

设备管理的基本任务：

• 完成用户提出的IO请求
• 提高设备的速率
• 改善设备的利用率

设备管理的主要功能：

• 缓冲区管理
• 设备分配
• 设备处理
• 虚拟设备
• 实现设备的独立性

IO系统的基本功能：

• 设备分配
• 设备映射
• 设备驱动
• IO缓冲区管理

通用设备管理分层模型：

• 用户层软件

• 设备独立性软件

  • 功能：

    • 建立逻辑设备名到物理设备名的映射关系
    • 提供设备保护功能
    • 数据缓冲区管理
    • 设备的分配与回收

    逻辑设备表LUT:

    • 第一种方式是整个系统只设立一张LUT，适用于单用户操作系统
    • 第二种方式是为每个用户设立一张LUT

• 设备驱动程序

• 中断处理程序

• 硬件

5.2 中断处理程序

中断处理程序的处理过程分成以下几个步骤:

1. 测定是否有未响应的中断信号
2. 保护被中断进程的运行环境
   • 通常由硬件自动把PSW和程序计数器中的值保留到中断保留区中
   • 然后把被中断进程的CPU现场信息(所有的CPU寄存器)都压入中断栈中
3. 转入相应的设备处理程序
   • 由处理机对各个中断源进行测试，确定引起本次中断的IO设备，并对其发送应答信号，使之消除中断请求信号
   • 将相应的中断处理程序的入口地址装入到程序计数器中，使处理机转向中断处理程序
4. 执行中断处理
   • 首先从设备控制器中读出设备状态，判断此次中断是正常完成中断还是异常结束中断
   • 若是前者，中断程序便结束处理；若还有命令，可发向控制器发送新的命令，进行新一轮的数据传送
   • 若是异常，则根据异常的原因做响应的处理
5. 恢复被中断进程的现场

5.3 设备驱动程序

5.3.1 IO控制方式

程序直接控制方式:

• 实际就是不断轮询IO控制器的状态寄存器
• 优点:
  • 实现简单
• 缺点:
  • CPU和IO设备只能串行操作，CPU需要一直轮询检查，长期处于忙等状态

中断方式:

• CPU会在每个指令周期的末尾检查中断
• 中断处理过程需要保存和恢复进程的执行环境，这个过程也需要一定的时间开销，如果中断频率太高，也会降低系统性能
• 每次中断只能读入一个字
• 优点:
  • CPU和IO设备可并行操作，CPU利用率明显提升
• 缺点:
  • 频繁的中断处理会消耗较多的CPU时间

DMA方式(直接存储器存取):

• 数据的传送单位改为块，而不是字
• 注意:每次读写只能是连续的块，若不连续则需要多条中断指令
• 特点
  1. 数据传输的基本单位是数据块
  2. 所传送的数据从设备直接到内存
  3. 仅在传输一个或多个数据块的开始或结束时，才需要CPU干预，整块数据的传送是在设备控制器的控制完成的
• DMA控制器的组成:
  • 主机和DMA控制器的接口
  • DMA控制器和块设备的接口
  • IO控制逻辑
• 优点:
  • 数据传输以块为单位，CPU的介入频率进一步降低，数据传输效率进一步增加，CPU和IO设备的并行性得到提升
• 缺点:
  • CPU每发出一条IO指令，只能读写一个或多个连续的数据块
• 组成:
  • DR:数据寄存器
  • MAR:内存地址寄存器
  • DC:数据计数器，表示剩余要读写的字节数
  • CR:命令/状态寄存器，存放CPU发来的IO命令或设备的状态信息

通道控制方式:

• 是一种硬件，可以理解为一个简化的CPU，可以识别并执行一系列通道指令
• 优点:
  • CPU,通道,IO设备可并行操作，资源利用率很高
• 缺点:
  • 实现复杂，需要专门的通道硬件支持

5.4 磁盘

5.4.1 磁盘的结构

磁道:

• 无数同心圆

扇区:

• 一个磁道被划分为一个个扇区，每个扇区就是一个磁盘块，各个扇区存放的数据量相同，因此最内侧磁道上的面积最小，数据密度也最大

可用(柱面号，盘面号，扇区号)来定位任意一个磁盘块

5.4.2 磁盘调度算法

一次磁盘读写操作需要的时间

寻道时间：s+m*n

• 启动磁头臂时间s
• 移动磁头的时间:设跨越1个磁道耗时m，总共需要跨越n条磁道

延迟时间：

• 通过旋转磁盘，使磁头定位到目标扇区所需要的时间，设磁盘转速为r，则平均所需的延迟时间为

传输时间:

• 假设磁盘转速为r,读写字节数为b，每个磁道上的字节数为N

平均存取时间

优化寻道时间的算法

先来先服务算法FCFS:

• 优点:
  • 公平，如果请求访问的磁道比较集中的话，算法性能还说得过去
• 缺点:
  • 如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS性能很差

最短寻找时间优先SSTF:

• 类似贪心算法，但是总体不一定最优
• 优点:
  • 性能较好，平均寻道时间短
• 缺点:
  • 可能产生饥饿现象

扫描算法SCAN:

• 只有磁头移动到最外侧磁道的时候才能向内移动，只有移动到最内侧磁道的时候才能往外移动
• 优点:
  • 性能较好，平均寻道时间短，不会产生饥饿现象
• 缺点:
  • 只有到达最边上的磁道时才能改变磁头移动方向(解决:LOOK算法)
  • 对于各个位置的磁道的响应频率不平均(解决:C-SCAN算法)

循环扫描算法C-SCAN:

• 优点:
  • 各个位置磁道的响应频率很平均
• 缺点:
  • 只有到达最边上的磁道时才能改变磁头移动方向

5.4.3 磁盘管理

磁盘初始化:

1. 低级格式化(物理格式化),将磁盘的各个磁道划分为扇区。一个扇区通常分为头，数据区域，尾三个部分，管理扇区所需要的各种数据结构一般存放在头和尾，比如扇区校验码
2. 将磁盘分区，每个分区由若干个相邻的柱面组成
3. 逻辑格式化:创建文件系统。比如文件系统的根目录，初始化存储空间管理所用的数据结构

引导块:

• 计算机开机时需要进行一系列的初始化工作，这些初始化工作时通过执行初始化程序完成的
• ROM中只存放很小的自举装入程序，完整的自举程序放在磁盘的启动块上，位于磁盘的固定位置。拥有启动分区的磁盘称为启动磁盘

坏块的管理:

• 在逻辑初始化时，对整个磁盘进行坏块检查，表明哪些扇区是坏扇区，比如在FAT表中标明，坏块对操作系统不透明
• 对于复杂的磁盘，磁盘控制器(硬件)会维护一个坏块链表
• 在磁盘出厂前进行敌机格式化，将坏块链初始化。另外，磁盘控制器还会保留一些备用扇区，用于替换坏块，这种方案称为扇区备用，这种情况下坏块对操作系统透明

不考

假脱机技术SPOOLing技术

独占式设备:

• 只允许各个进程串行使用的设备

共享设备:

• 允许多个进程同时使用的设备(微观上可能是交替的)

假脱机技术(SPOOLing技术):

• 用软件的方法模拟脱机技术，系统会建立输入进程和输出进程

IO设备的概念和分类

按照设备上的数据组织形式:

• 块设备
• 字符设备

按照资源分配的角度分类:

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

IO控制器

概念:

• CPU无法直接控制IO设备的机械部件，因此IO设备还有一个电子部件作为CPU和IO机械部件之间的中介，用于实现CPU对设备的控制

IO控制器的功能:

• 接受和识别CPU发出的命令-->控制寄存器
• 向CPU报告设备的状态-->状态寄存器
• 数据交换-->数据寄存器
• 地址识别

IO控制器的组成:

• CPU与控制器之间的接口
• IO逻辑
• 控制器和设备之间的接口

两种寄存器编制方式:

• 内存映射IO
• 寄存器独立编制

设备的分配和回收

设备分配时应该考虑的因素:

• 设备的固有属性
  • 独占设备
  • 共享设备
  • 虚拟设备
• 设备分配算法
• 设备分配的安全性
  • 安全分配方式：一个时段内每个进程只能使用一个设备
    • 优点：破坏了请求和保持条件，不会死锁
    • 缺点：对于一个进程来说，CPU和IO设备只能串行操作
  • 不安全分配方式：进程发出IO请求后，系统为其分配IO设备，进程可继续执行，之后还会发出新的IO请求
    • 优点：进程的计算任务和IO任务可以并行处理，使进程迅速推进
    • 缺点：有可能发生死锁

设备控制表DCT:

• 用于记录设备情况

控制器控制表COCT:

• 每个设备控制器对应一张COCT

通道控制表CHCT:

• 每个通道对应一张CHCT

系统设备表SDT:

• 记录了系统中全部设备的情况，每个设备对应一个表目

缓冲区管理

缓冲区的作用:

1. 缓和CPU和IO设备速度不匹配的矛盾
2. 减少中断频率
3. 解决数据粒度不匹配的问题
4. 提高CPU与IO设备的并行性

单缓冲:

• 在主存中为其分配一个缓冲区

双缓冲:

循环缓冲

缓冲池

六、文件管理

6.1 文件和文件系统的概念

文件的定义：

• 由创建者所定义的，具有文件名的一组相关元素的集合

文件系统的定义：

• 操作系统中的各类文件，管理文件的软件，以及管理文件涉及到的数据结构的信息的集合

文件系统的功能：

1. 有效的管理文件的存储空间
2. 管理文件目录
3. 完成文件的读写操作
4. 完成文件的共享和保护
5. 为用户提供交互式命令接口和程序调用接口

6.2 文件的结构

6.2.1 逻辑结构

就是从用户观点出发观察到的文件组织形式

按照有无结构分类:

• 无结构文件:

  文件内部的数据就是一系列二进制或字符流组成，又称“流式文件”，比如.txt

• 有结构文件:

  由一组相似的记录组成，又称“记录式文件”。每组记录又由若干记录项组成，比如数据库

  • 顺序文件

    • 链式存储
      • 无论定长/可变长记录，都无法实现随机选取
    • 顺序存储
      • 可变长记录：无法实现随机存取
      • 定长记录
        • 可实现随机存取
        • 若采用串结构(记录之间的顺序与关键字无关)：无法快速找到某关键词对应的记录
        • 若采用顺序结构(记录之间的顺序按照关键字顺序排列)：可以快速找到某关键字对应的记录

  • 索引文件

  • 索引顺序文件:并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项

6.2.2 物理结构

解决的问题:

• 文件数据应该怎样存放在外存中

文件块和磁盘块:

• 类似进程分页，文件的逻辑地址空间也被分为了一个一个的文件块，于是文件的逻辑地址也可表示为(逻辑块号,块内地址)的形式

连续分配:

• 思想:要求每个文件在磁盘上占有一组连续的块
• 如何实现:FCB中必须包含起始块号和长度
• 优点:
  • 顺序访问容易，可快速检索文件的第一个数据块
  • 顺序访问速度快，磁头移动距离短，效率最高
• 缺点:
  • 要求有连续的存储空间，会有磁盘碎片产生
  • 必须事先知道文件长度，不利于文件大小的变化

链接分配:

• 思想:采取离散分配的方式，可以为文件分配离散的磁盘块，分为隐式链接和显式链接两种

  • 隐式链接

    FCB中需要指明起始块号和结束块号，每个磁盘块都会保存指向下一个盘块的指针，指针对于用户来说是透明的

    优点：很方便对文件进行拓展，不会有碎片问题，外存利用率高

    缺点：查找效率低，只支持顺序访问，不支持随机访问，指向下一个盘块的指针也需要耗费少量的存储空间

  • 显式链接

    把用于链接文件各物理块的指针显式地存放在一张表中，也就是文件分配表FAT：(物理块号，下一块)

    一个磁盘仅设置一张FAT，开机时将FAT读入内存，并常驻内存

    优点：很方便对文件进行拓展，不会有碎片问题，外存利用率高，并且支持随机访问，相比于隐式链接来说，地址转换不需要访问磁盘，文件的访问效率更高

    缺点：文件分配表FAT需要占用一定的存储空间

索引分配:

• 思想：参考页表，为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块
• 索引表存放的磁盘块称为索引块，文件数据存放的磁盘块称为数据块
• 需要在FCB中记录索引块
• 优点：支持随机访问，文件拓展也很容易实现
• 缺点：索引表可能会占据一定的存储空间
• 如何解决索引表过大的问题?
  • 链接方案：将多个索引块链接起来存放
  • 多层索引：类似于多级页表，若采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块需要K+1次读磁盘操作
    • 改进：混合索引：引入一个顶级索引表，前面几项是直接地址索引，后面是一级间接索引和二级间接 索引

6.3 文件存储空间管理

存储空间的划分和初始化:

• 存储空间的划分:将物理磁盘划分为一个一个的文件卷
• 存储空间的初始化:将每个文件卷划分为目录区和文件区
• 在部分操作系统中，支持将多个物理磁盘组成一个文件卷

存储空间管理

空闲表法:

• (第一个空闲盘块号，空闲盘块数)

• 如何分配磁盘块:

  与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间，同样可采用BF，WF，FF，NF算法决定要为文件分配哪一个区间

空闲链表法:

• 空闲盘块链：以盘块为单位组成一条空闲链
  • 如何分配：从链头开始依次选取若干个盘块进行分配，并修改空闲链的链头指针
  • 如何回收：回收的盘块依次挂到链尾，并修改空闲链的链尾指针
• 空闲盘区链：以盘区为单位组成一条空闲链(连续的空闲盘块组成一个空闲盘区，空闲盘区的第一个盘块记录盘区的长度和下一个盘区的指针)
  • 如何分配：可采用BF，FF等算法
  • 如何回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中；若回收区没有和任何空闲区相邻，则将回收区作为一个单独的空闲盘区挂到链尾

位示图法:

• 每个二进制位对应一个盘块，比如0代表空闲，1代表已分配
• 位示图一般用连续的字来表示，比如一个字的字长是16位，可以用(字号，列号)对应一个盘块号，也有的题目表示为(行号，列号)
• 如何分配：若文件需要k个块，顺序扫描位示图，找到k个相邻或不相邻的’0‘，算出其盘块号，分配文件，将相应位置为‘1’
• 如何回收：计算相应的字号和位号，将其置为’0‘

成组链接法(Unix的方法):

• 适合大型文件系统

6.4 文件目录

文件控制块FCB:

• FCB中包含了文件的基本信息，存储控制信息，使用信息
• FCB的有序集合称为文件目录

目录结构:

• 单级目录结构:

  早期操作系统并不支持多级目录，整个系统中只建立一张目录表

  实现了按名存取，但是不允许文件重名，不适用于多用户操作系统

• 两级目录结构:

  • 主文件目录MFD：记录用户名以及用户文件目录的存放位置
  • 用户文件目录UFD：由该用户的文件FCB组成，不能对文件进行分类

• 层次目录结构:

  不同目录下的文件是可以重名的

  • 树型目录：不便于实现文件的共享
  • 无循环图目录：设置了共享计数器

索引节点(FCB的改进):

• (文件名，索引节点指针)，目录项的长度大幅减少
• 由于目录项长度减少，每个磁盘块可以存放更多的目录项，因此检索文件时磁盘I/O的次数就减少了很多

6.5 文件共享和保护

6.5.1 共享

基于索引节点的共享方式(硬链接):

• 索引节点中设置一个链接计数变量count，用于表示链接到本索引节点上的用户目录项数
• 不同用户对同一个文件的命名可以不同
• 当链接计数变量count大于等于1时，删除文件只是让索引节点指针置空

基于符号链的共享方式(软链接):

• 类似于Windows中的快捷方式
• 即使软链接指向的共享文件已被删除，Link型文件依然存在，只不过通过其去查找共享文件会失败

6.5.2 文件保护

1. 口令保护:

   • 口令一般存在文件对应的FCB或者索引节点中，操作系统会讲用户提供的口令与FCB中存储的口令进行对比，若正确才允许用户访问文件

   • 优点:

     • 保存口令的空间开销和验证口令的时间开销小

   • 缺点:

     • 正确的口令存放在系统内部，不够安全

2. 加密保护

3. 访问控制:

   • 在每个文件的FCB或索引节点中增加一个访问控制列表ACL，记录各个用户可以对文件执行哪些操作