操作系统原理复习笔记

第一章

操作系统

  • 操作系统是一个控制程序(防止错误操作,方便用户使用)
  • 操作系统是一个资源管理器(解决资源访问冲突、高效)

并发

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

并行

  • 指两个或多个事件在同一时刻发生

单内核

  • 单内核也叫集中式操作系统。整个系统是一个大模块,可以被分为若干逻辑模块,即处理器管理、存储器管理、设备管理和文件管理,其模块间的交互是通过直接调用其他模块中的函数实现的。单内核模型以提高系统执行效率为设计理念,因为整个系统是一个统一的内核,所以其内部调用效率很高
  • 缺点:各模块之间的界限并不特别清晰,模块间的调用比较随意,所以进行系统修改或升级时,往往“牵一发而动全身”,导致工作量加大,使其难于维护

微内核

  • 微内核是指把操作系统结构中的内存管理、设备管理、文件系统等高级服务功能尽可能地从内核中分离出来,变成几个独立的非内核模块,而在内核只保留少量最基本的功能,使内核变得简洁可靠,因此叫微内核。

操作系统的作用

  • 计算机硬、软件资源的管理者 ——有效
  • 用户使用系统硬件、软件的接口——方便使用
  • 扩展机(extended machine)/虚拟机(virtual machine)——扩展能力

操作系统五大基本功能

  • 处理机管理
  • 存储管理
  • 文件管理
  • 设备管理
  • 提供方便的用户接口

操作系统基本特征

  • 并发(concurrency)
  • 共享(sharing)
  • 虚拟(virtual)
  • 异步(asynchronism)

多道批处理系统

  • 在主存中同时存放多道用户的作业,使之同时处于运行状态共享系统资源。
  • 优点:资源利用率高、资源吞吐量大
  • 缺点:平均周转时间长、无交互能力

微内核功能/优缺点

功能

  • 进程(线程)管理
  • 低级存储器管理
  • 短程调度
  • 中断处理

优点

  • 良好的扩充性
  • 可靠性好
  • 便于网络服务
  • 灵活、可移植性

缺点

  • 性能大幅度下降(消息传递比直接调用效率低)

第二章

进程(process)

  • 进程是程序的一次执行
  • 进程是一个既能用来共享资源,又能描述程序并发执行过程的系统基本单位
  • 进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位
  • 进程是指一个具有一定独立功能的程序在一个数据集合上的依次动态执行过程。

线程(thread)

  • 进程中的一个运行实体,是CPU的调度单位,又称轻量级进程。

原语(primitive)

  • 由若干条指令构成的“原子操作(atomic operation)”过程,作为一个整体而不可分割

进程同步

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

进程互斥

  • 由于各进程要求使用共享资源(内存、文件等),而这些资源需要互斥使用,因此,各进程之间竞争使用这些资源,进程的这种关系为进程互斥。

临界资源(Critical Resource)/互斥变量/共享变量

  • 系统中规定在一段时间内只允许一个进程使用的资源

临界区(Critical Section)

  • 对临界资源进行操作的程序片段

管程

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

进程的特征

  • 动态性:具有动态的地址空间(包括代码、数据、系统控制信息)
  • 独立性:各进程地址空间相互独立
  • 并发性:一段时间内同时运行多个进程
  • 结构化:代码段、数据段、核心段
  • 异步性:进程之间相互制约,进程按异步方式运行

进程与程序区别

  • 进程是动态的,程序是静态的
  • 进程是暂时的,程序是永久的
  • 进程与程序的组成不同,进程包括程序、数据和PCB

进程的状态

进程状态图.jpg

就绪 ——> 运行

  • 调度程序选择一个新的进程运行

运行 ——> 就绪

  • 运行进程用完了时间片
  • 一个高优先级进程处于就绪状态,中断正在运行的进程

运行 ——> 阻塞

  • 请求OS服务
  • 对一资源的访问尚不能进行
  • 等待I/O结果
  • 等待某一进程提供输入

阻塞 ——> 就绪

  • 当所等待的事件发生时

进程控制块

  • 进程控制块(PCB):Process Control Block
  • PCB是操作系统用于记录、管理控制进程运行所用的信息集
    合。也是操作系统掌握进程状态的唯一数据结构
  • PCB记录了进程的各种属性,描述进程的运动(状态)变化
    过程
  • 进程存在的唯一标志

PCB的组成

  • 进程标识信息:进程标识符(ID), 父进程标识ID,用户标识
  • 处理器状态信息:用户使用的寄存器、控制和状态寄存器、堆栈指针
  • 进程调度信息:进程状态、进程优先级、进程调度所需要的其他信息、事件
  • 进程控制信息:程序和数据的地址、进程间同步和通信信息、资源清单、相关数据结构链接信息进程存在的唯一标志

fork代码例子

#include<stdio.h>
#include<sys/types.h>
#include<unistd.h>
int glob=3;
int main(void) {
    pid_t pid;
    int loc=3;
    printf("before fork(),glob=%d,loc=%d.\n",glob,loc);
    if((pid=fork())<0 {
        printf("fork() error.\n");
        exit(0);
    } else if(pid==0) { //子进程
        glob++;
        loc--;
        printf("child process changes glob and loc:\n");
        printf("glob=%d,loc=%d.\n",glob,loc);
    } else { //父进程
        printf("parent process doesnot change glob and loc:\n");
        printf("glob=%d,loc=%d.\n",glob,loc);
    }
    exit(0);
}
  • 出现错误:

    fork() error.
  • 子进程先运行,父进程后运行:

    before fork():glob=3,loc=3.
    child process changes glob and loc:
    glob=4,loc=2
    parent process doesnot change glob and loc:
    glob=3,loc=3
  • 父进程先运行,子进程后运行:

    before fork():glob=3,loc=3.
    parent process doesnot change glob and loc:
    glob=3,loc=3
    chinld process changes glob and loc:
    glob=4,loc=2

进程阻塞和唤醒的事件

  • 请求系统服务:临界资源
  • 启动某种操作:启动I/O设备等待指定I/O操作任务
  • 新数据尚未到达
  • 无新工作:发送进程无数据可发送时阻塞

为什么引入线程

  • 应用的需要:应用中同时多种活动,活动会被阻塞,分解成线程后,程序设计模型简单化
  • 开销的考虑:线程的开销小,创建/撤销线程花费时间少、两个线程的切换花费时间少、相互通信无须调用内核。
  • 性能的考虑:CPU密集型的多线程和大量的计算、I/O处理重叠进行

进程/线程的区别

  • 调度:进程调度时需要进行上下文的切换,线程调度只保留少量寄存器。
  • 拥有资源:线程只拥有TCB、程序计数器和少量堆栈,可以访问其隶属进程的系统资源
  • 系统开销:线程切换时系统开销小,同一进程内的多个线程之间通信无需系统内核的干预
  • 独立性:同一进程中的不同线程之间的独立性比不同进程之间的独立性低很多
  • 支持多处理机系统:传统的进程只能运行在一个处理机上

同步机制遵循的准则

  • 空闲则入:其他进程均不处于临界区
  • 忙则等待:已有进程处于其临界区
  • 有限等待:等待进入临界区的进程不能“死等”
  • 让权等待:不能进入临界区的进程应释放CPU

信号量PV操作及3个推论

  • 信号量是一个特殊变量,用于进程间传递信号的一个整数值
  • 进程可以通过P、V操作来发送和接受信号。
  • P、V都是原子操作
  • 推论1:信号量S为正值 ——> 实际还可使用的物理资源数
  • 推论2:信号量S为负值 ——> 等待队列的进程数
  • 推论3:一定条件下,P代表挂起操作,V代表唤醒操作
  • S初值为1 ——> 互斥信号量
  • 必须成对使用P和V原语:遗漏P原语则不能保证互斥访问,遗漏V原语则不能在使用临界资源之后将其释放(给其他等待的进程)
  • P、V原语不能次序错误、重复或遗漏

生产者消费者问题

  • 待解决问题:确保当缓冲区已满时,生产者不会继续向其中添加数据;当缓冲区为空时,消费者不会从中移走数据
  • 数组表示具有n个缓冲区的缓冲池,in表示输入指针,out表示输出指针
  • in := (in+1) mod n; out := (out+1) mod n
  • 缓冲池满:(in+1) mod n = out
  • 缓冲池空:in = out
  • counter作为临界资源,生产者和消费者进程互斥地访问变量counter

记录型信号量

  • mutex:互斥信号量
  • empty:可以使用的空缓冲区数
  • full:缓冲区内可以使用的产品数

P操作不能颠倒顺序
V操作次序无关紧要

producer:begin
    repeat
        producer an item in nextp;
        wait(empty);
        wait(mutex);
        buffer (in) : = nextp;
        in : = (in + 1) mod n;
        signal(mutex);
        signal(full);
    until false;
end
consumer : begin
    repeat
        wait(full);
        wait(mutex) ;
        nextc := buffer (out);
        out := (out+1) mod n ;
        signal(mutex);
        signal(empty);
        consume the item in nextc;
    until false;
end

AND信号量集

Producer:
Swait(empty, mutex); //进入区
one unit ——> buffer
Ssignal(full, mutex);//退出区

Consumer:
Swait(full, mutex);//进入区
ont unit <—— buffer
Ssignal(empty, mutex);//退出区

哲学家就餐问题

  • 利用AND信号量集解决
var chopstick:array [0,..., 4] of semaphore := (1,1,1,1,1)
    process I
        repeat
            think ;
            swait(chopstick[(I + 1) mod 5], chopstick[I]);
            eat;
            ssignal(chopstick[(I + 1) mod 5], chopstick[I]);
        until false;

读写问题

要求满足条件

  • 允许多个读者同时执行读操作
  • 不允许多个写者同时操作
  • 不允许读者、写者同时操作

利用记录型信号量解决

  • WmutexRmutex初值为1
  • Rcount表示正在读的进程数,初值为0
Reader:
wait(Rmutex);
if(Rcount == 0) wait(wmutex);
++Rcount;
signal(Rmutex);
...
read;
...
wait(Rmutex);
--Rcount;
if (Rcount == 0) signal(wmutex)
signal(Rmutex);
Writer:
wait(Wmutex);
...
write;
...
signal(Wmutex);

利用信号量集解决

  • 最多允许RN个读者同时读,信号量L初值为RN
int RN;
semaphore L = RN, mx = 1;
void Reader(){
    do{
        Swait(L, 1, 1);
        Swait(mx, 1, 0);
        ...
        perform read operation;
        ...
        Ssignal(L, 1);
    }while(true);
}

void Writer(){
    do{
        Swait(mx, 1, 1; L, RN, 0);//既无写mx=1,又无读L=RN才可进入
        perform write operation;
        Ssignal(mx, 1);
    }while(true);
}

管程的特性

  • 模块化:一个管程是一个基本程序单位,可以单独编译
  • 抽象数据类型:管程是一种特殊的数据类型,其中不仅有数据,还有对数据进行操作的代码
  • 信息封装:管程是半透明的,如何实现功能对外部不可见

用管程实现生产者消费者问题

Monitor producerconsumer{
    item buffer[N];
    int in = 0, out = 0;
    condition notfull, notempty;
    int count = 0;
    public:
        void put(item x){
            if(count >= N) cwait(notfull);
            buffer[in] = x;
            in = (in+1)%N;
            count++;
            csignal(notempty);
        }
        void get(item x){
            if(count <= 0) cwait(notempty);
            x = buffer[out];
            out = (out+1)%N;
            count--;
            csignal(notfull);
        }
} PC

void producer(){
    item x;
    while(true){
        ...
        produce an item in nextp;
        PC.put(x);
    }
}
void consumer(){
    item x;
    while(true){
        PC.get(x);
        consume the item in nextc;
        ...
    }
}

进程与管程区别

  • 目的

    • 进程:实现多个程序并发执行
    • 管程:解决共享资源的互斥使用
  • 系统管理数据结构

    • 进程:PCB,私有
    • 管程:等待队列,公共
  • 工作方式

    • 进程:主动工作
    • 管程:被动工作,被进程调用
  • 管程是操作系统固有成分,无创建和撤销
  • 进程之间能并发执行,管程不能与其调用者并发

第三章

作业(Job)

计算机操作者(或作业调度器)交给操作系统的执行单位,包括程序、数据和作业说明书

死锁

一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件

先来先服务(first-come first-served, FCFS)调度算法

  • 按照就绪的先后顺序使用CPU
  • 没有抢占
  • 适用于作业调度和进程调度
  • 只考虑等待时间,不考虑执行时间
  • 有利于CPU繁忙的作业,不利于I/O繁忙的作业

短作业优先(short job first, SJF)调度算法

  • 最短完成时间优先
  • 只考虑执行时间,不考虑等待时间
  • 平均响应时间最优
  • 不公平,长任务可能饥饿

高响应比优先(Highest Response Ratio Next, HRRN)调度算法

  • 响应比 = (等待时间 + 要求服务时间) / 要求服务时间 = 响应时间 / 要求服务时间
  • 总是选择响应比最高的进程
  • 即考虑等待时间又考虑执行时间

轮转(Round Robin, RR)调度算法

  • 基于时钟的抢占策略
  • 目标:为短任务改善平均响应时间
  • 周期性的产生时钟中断,然后进行任务切换
  • T(响应时间) = N(进程数目)*q(时间片)
  • 应当使用户输入通常在一个时间片内能处理完

产生死锁的原因

  • 竞争不可抢占性资源引起死锁
  • 竞争可消耗性资源引起死锁
  • 进程推进顺序不当引起死锁

形成死锁4个必要条件

  • 互斥条件:进程对所分配到的资源进行排他性使用
  • 请求和保持条件:申请新资源时不释放已占有资源
  • 不可抢占条件:进程已获得的资源在未使用完之前不能被抢占,只能在程序使用完时自己释放
  • 循环等待条件:发生死锁时,必然存在一个进程——资源的循环链

处理死锁的基本方法

  • 预防死锁:破坏产生死锁的后三个条件
  • 避免死锁:资源动态分配中防止系统进入不安全状态
  • 检测死锁
  • 解除死锁

银行家算法(Ⅲ-P194)

死锁定理

  • S为死锁状态的充分条件是,当且仅当S状态的资源分配图是不可完全简化
  • 如果资源分配图中没有环路,则系统中没有死锁
  • 如果资源分配图中存在环路,则系统中可能存在死锁
  • 如果每个资源类中只包含一个资源实例,则环路是死锁存在的充分必要条件
  • 资源分配图化简步骤:

    • 找一个非孤立点进程节点且只有分配边,去掉分配边,将其变成孤立结点
    • 把相应的资源分配给一个等待该资源的进程,即将某进程的申请边变成分配边
    • 重复以上步骤

第四章

逻辑地址(相对地址、虚拟地址)

  • 用户程序经过编译、汇编后形成目标代码,目标代码通常采用相对地址的形式,其首地址为0,其余指令中的地址都相对于首地址而编制

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

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

地址重定位

  • 为了保证CPU执行指令时可正确访问内存单元,需要将用户程序中的逻辑地址转换为运行时可由机器直接寻址的物理地址

对换(Swapping)

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

页面

  • 将一个进程的逻辑地址空间分成若干个大小相等的片,称为页面或页,并为各页加以编号

页框

  • 物理地址空间分成大小相等的许多区,每个区称为一块页框(物理块),大小与页面相同

页表

系统为每个进程建立一张页面映射表,简称页表

存储器层次

存储器层次.jpg

首次适应算法

  • 空闲分区链按地址递增的次序连接
  • 分配时从链首开始顺序查找,找到第一个能满足大小要求的空闲分区,剩余空闲分区插入到空闲分区链中合适位置。
  • 优先使用低地址部分的空闲分区,保留了高地址部分的大空闲区,有利于大作业的运行
  • 缺点:低址部分产生很多碎片,增加查找可用空闲分区的开销;回收分区时需搜索空闲分区表和链表且移动相应几项

循环首次适应算法

  • 当前位置开始查找第一个满足分区
  • 查询指针:指示下一次起始查询的空闲分区
  • 循环查找方式:最后一个空闲分区不满足要求时返回到第一个空闲分区继续查找
  • 能使内存中的空闲分区分布均匀减少了查找时间,但是缺乏大的空闲分区

最佳适应算法

  • 每次分配既满足要求又最小的空闲分区
  • 空闲区按照容量递增形成空闲链,第一个找到的满足要求的空闲区必是最优
  • 产生许多难以利用的小空闲区

最坏使用算法

  • 每次分配一个最大的空闲分区
  • 容量递减形成空闲链
  • 产生碎片的可能性小,对中小作业有利
  • 查找效率高

算法比较

  • 首次适应使得高地址空间有较多较大的空闲区来容纳大作业
  • 循环首次适应算法使存储器空间得到均衡使用
  • 最佳适应算法的主存利用率最好
  • 在处理某种作业序列时,最坏适应算法的性能可能最好,分配后容易剩余较大的空间,有利于再次分配
  • 实际OS中,大多采用首次适应算法,其次是最佳适应算法和下次适应算法

分页/分段存储管理逻辑地址到物理地址的转换

地址转换机构

  • 分页

    • CPU取到逻辑地址,划分为页号和页内地址
    • 用页号查页表,得到页框号
    • 与页内偏移地址拼接为物理地址
  • 分段

    • CPU取到逻辑地址
    • 用段号查段表,得到段起始地址
    • 与段内偏移计算出物理地址

快表(TLB)

  • 页表 ——> 两次或以上的内存访问
  • 程序访问的局部性原理 ——> 引入快表
  • 联想寄存器(associative memory),又称快表
  • 特点:按内容并行查找、高速
  • 保存正在运行进程的页表的子集(部分表项)
  • 内存有效访问时间(Effective Access Time, EAT):从进程发出指定逻辑地址的访问请求,经过地址变换,到在内存中找到对应的实际物理地址单元并取出数据所需要花费的总时间

分页和分段的区别

  • 页是信息的物理单位,分页是为了实现离散分配方式,提高内存的利用率,分页是系统管理的需要;
    段是信息的逻辑单位,为了更好地满足用户的需要
  • 页的大小固定且由系统决定,在系统中只能有一种大小的页面
    段的长度不固定,取决于用户所编写的程序
  • 分页的作业地址空间的是一维
    分段的作业地址空间是二维的,既需给出段名,又需给出段内地址

第五章

虚拟存储器

  • 指具有请求调入功能和置换功能,能从逻辑上对内存容量加以扩充的一种存储器系统

抖动(Thrashing)

  • 虚存中,页面在内存与磁盘之间频繁调度,使得调度页面所需的时间比进程实际运行的时间还多,这样导致系统效率急剧下降

工作集

  • 在某段时间间隔内进程实际所要访问页面的集合

页面置换算法(算法思想、置换图/表、求置换次数、缺页中断次数)

最佳(Optimal)置换算法

  • 淘汰以后永不使用或在最长时间内不再被访问的页面
  • 保证获得最低的缺页率,但无法实现,可利用该算法评价其他算法

先进先出(FIFO)页面置换算法

  • 淘汰最先调入内存的页(在内存中驻留时间最长的页)
  • 页面调入的先后次序不能反映页面的使用情况
  • Belady现象:当分配给进程的物理页面数增加时,缺页次数反而增加

最近最少使用(Least Recently Used, LRU)页面置换算法

  • 淘汰最后一次访问时间距离当前时间最长的一页
  • 实现

    • 老化算法(Aging):每隔一段时间寄存器右移一次,缺页中断时选择具有最小数值的寄存器所对应的页面
    • 栈:访问某页面时将其页面号从栈中移出并压入栈顶,栈顶始终是最新被访问页面的页面号,栈底最近最久未使用页面的页面号
    • 页面淘汰队列:执行一次页面访问后,需要从队列中把该页调整到队列尾,发生缺页中断时总淘汰队列头所指示的页
    • 软件方案:计数器记录页面被访问频率/计时器记录最后一次访问时间

第六章

I/O系统

  • I/O设备及其接口线路、控制部件、通道和管理软件的总称

设备控制器

I/O设备的电子部件称设备控制器或适配器,它是可插入主板扩充槽的印刷电路板,机械部件则是设备本身

中断、系统调用

  • 中断是指CPU对I/O设备发来的中断信号的一种响应。
  • CPU暂停正在执行的程序,保留CPU环境后,自动地转去该I/O设备的中断处理程序,执行完后再回到断点继续执行原来的程序
  • 系统调用是应用程序获得操作系统服务的唯一途径,是OS为用户程序提供的一种服务界面

引入设备控制器的原因

  • 如果没有控制器,复杂操作必须由操作系统来解决,引入控制器后,通过传递简单参数就可进行I/O操作,大大简化系统的设计,有利于计算机系统对各类控制器和设备的兼容性

引入I/O通道(I/O Channel)的原因

  • 建立独立的I/O操作,使一些原来由CPU处理的I/O任务转由通道来承担,把CPU从繁杂的I/O任务中解脱出来

引入中断的原因

  • 多道程序得以实现的基础
  • 设备管理的基础
  • 提高处理机的利用率
  • 实现CPU与I/O设备并行执行

4种I/O设备控制方式及区别

轮询方式

  • 忙——等待方式
  • 状态寄存器
  • 查询指令:查询设备是否就绪
  • 读/写指令:设备就绪时执行数据交换
  • 转移指令:设备未就绪时执行转移指令转向查询指令继续查询

中断方式

  • CPU与I/O设备并行工作
  • 字节为单位进行I/O
  • CPU与设备控制器及设备之间有中断请求线
  • 状态寄存器有中断允许位

DMA方式

  • 数据传输的基本单位是数据块
  • 仅在传送一个或多个数据块的开始和结束时才需CPU干预
  • 减少了CPU对I/O的干预,进一步提高了CPU与I/O设备的并行操作程度
  • 命令/状态寄存器CR、内存地址寄存器MAR、数据寄存器DR、数据计数器DC

通道方式

  • 进一步减少CPU的干预,以对一组数据块的控制管理为单位
  • 实现CPU、通道和I/O设备三者的并行操作

SPOOLing(Simultaneous Peripheral Operation On-Line)技术/假脱机技术

SPOOLING.jpg

  • 将一台物理I/O设备虚拟为多台逻辑I/O设备,允许多个用户共享一台物理I/O设备
  • 将用户要求的数据从输入机,通过输入缓冲区再送到输入井,当CPU需要输入数据时,直接从输入井读入内存
  • 输出设备空闲时,再将输出井中的数据,经过输出缓冲区送到输出设备上

缓冲技术、缓冲池

  • 引入

    • 缓和CPU与I/O设备间速度不匹配的矛盾
    • 减少对CPU的中断频率,放宽对CPU中断响应时间的限制
    • 解决数据粒度不匹配的问题
    • 提高CPU和I/O设备之间的并行性
  • 实现方法

    • 硬件缓冲:专用寄存器
    • 软件缓冲:在内存中开辟若干单元作为缓冲区
  • 缓冲池(Buffer Pool)

    • 空缓冲队列emq
    • 输入队列inq:装满输入数据的缓冲区
    • 输出队列outq:装满输出数据的缓冲区

磁盘调度算法(求平均寻道长度)

先来先服务(FCFS)

  • 按访问请求到达的先后次序服务
  • 优点:简单、公平
  • 缺点:效率不高
    FCFS.jpg

最短寻道时间优先(SSTF)

  • 优先考虑距当前磁头最近的范文请求进行服务
  • 优点:改善了磁盘平均服务时间
  • 缺点:造成某些访问请求长期等待得不到服务(饥饿Starvation现象)
    SSTF.jpg

扫描算法(SCAN)

  • 不仅考虑距离,更优先考虑磁头的当前移动方向,逐步由里向外、由外向里,避免了饥饿现象的出现
    SCAN.jpg

循环扫描算法(CSCAN)

  • 规定磁头单向移动
  • 把最小磁道号紧接着最大磁道号构成循环
  • 减少了新请求的最大延迟
    CSCAN.jpg

N-Step-SCAN算法

  • 前几种算法可能出现磁臂停留在某处不动的情况 ——> 磁臂粘着(Armstickiness)
  • 将磁盘请求队列分成若干个长度为N的子队列,磁盘调度将按FCFS算法依次处理这些子队列。而每处理一个队列时又是按SCAN算法
  • 克服磁臂粘着

FSCAN算法

  • 只将磁盘请求队列分成两个子队列。一个是由当前所有请求磁盘I/O的进程形成的队列,由磁盘调度按SCAN算法进行处理。在扫描期间,将新出现的所有请求磁盘I/O的进程,放入另一个等待处理的请求队列。

第七章

文件、文件目录

  • 文件是指由创建者所定义的、具有文件名的一组相关元素的集合,可分为有结构文件和无结构文件两种。
  • 文件目录是指文件控制块的有序集合,一个文件控制块是一个文件目录项,文件目录被看作是一个文件,称为目录文件

什么是逻辑文件?什么是物理文件?

  • 文件的逻辑结构(File Logical Structure):从用户观点出发所观察到的文件组织形式,是用户可以直接处理的数据及其结构,独立于文件的物理特性,称为文件组织(File Organization)
  • 文件的物理结构:又称为文件的存储结构,指文件在外存上所形成的一种存储组织形式。与存储介质的存储性能和外存分配方式有关

什么是索引文件?为何要引入多级索引?

  • 索引文件是指当记录为可变长度时,通常为之建立一张索引表,并为每个记录设置一个表项构成的文件。通常将索引非顺序文件简称为索引文件。
  • 索引是为了是用户的访问速度更快,多级索引结构可以有效的管理索引文件,可根据用户的访问情况多级处理。

第八章

数据交付

  • 数据交付是指将磁盘高速缓存中的数据传送给请求者进程

容错技术

  • 容错技术是通过在系统中设置冗余部件来提高系统可靠性

事务

  • 事务是用于访问和修改各种数据项的一个程序单位。事务也可以被看作是一系列相关读和写操作。

位示图

  • 位示图是利用二进制的一位来表示磁盘中的一个盘块的使用情况。即用一位的两种状态来表示空闲和已经分配两种情况
  • 盘块的分配:第i行第j列,其盘块号b = n(i-1)+j
  • 盘块的回收i = (b-1)DIVn + 1, j = (b-1)MODn + 1

提高磁盘I/O速度的方法

磁盘高速缓存(Disk Cache)

  • 是一组在逻辑上属于磁盘,而物理上是驻留在内存中的盘块
  • 高速缓存的大小不再是固定
  • 数据交付(Data Delivery)方式

    • 数据交付
    • 指针交付(传送的数据量少,节省了数据从磁盘到内存的时间)
  • 置换算法

    • 访问频率
    • 可预见性
    • 数据的一致性
  • 周期性地写回磁盘

    • 周期性地调用一个系统调用SYNC,强制性地将所有在高速缓存中已修改的盘块数据写回磁盘

其他方法

  • 提前读
  • 延迟写
  • 优化物理块的分布
  • 虚拟盘