操作系统概念总结

操作系统概念总结

非常感谢学长总结的知识点
操作系统概念第七版
部分参考:https://www.kancloud.cn/hanghanghang/os/116695

概述

什么是操作系统(Operating System)
管理计算机硬件的程序,它为应用程序提供基础,并且充当硬件和用户的中介
中断(interrupt)
中断指当出现需要时,CPU暂时停止当前程序的执行转而执行处理新情况的程序和执行过程
中断向量(interrupt vector)
各种设备的中断处理子程序的地址数组
interrupt and trap
interrupt即外中断,指来自处理机和内存外部的中断,包括 I/O 设备发出的 I/O中断、外部信号中断、各种定时器引起的时钟中断以及调试程序中设置的断点等引起的调试中断等,是硬件产生的中断
trap即内中断,指在处理机和内存内部产生的中断。它包括程序运算引起的各种错误
同步I/O与异步I/O
同步I/O(synchronous I/O),线程启动一个I/O操作然后就立即进入等待状态,直到I/O操作完成后才醒来继续执行.
异步I/O(asynchronous I/O),线程发送一个I/O请求到内核,然后继续处理其他的事情,内核完成I/O请求后,将会通知线程IO操作完成
当I/O设备需要服务时会产生中断。发生中断时,操作系统首先确定哪个I/O设备引起中断。接着它会查找I/O设备表,以确定该设备状态,并修改表条目,以反映出现了中断。对于绝大多数设备,中断表示I/O请求的完成。如果队列中还有其他请求等待该设备,那么操作系统开始处理下一个请求。
DMA(direct memory access)及其工作原理
DMA即直接内存访问模式,用于能够以接近内存速度传输信息的高速I/O设备,设备控制器直接将数据块从缓冲存储器传输到主存储器,不需要CPU的干预,每个块只生成一个中断,而不是每个字节生成一个中断
多道程序系统(multiprocessor systems)
多处理器系统也称并行系统(parallel systems)或者是多核系统(multicore systems),这类系统有多个紧密通信的CPU,他们共享计算机总线,有时还有时钟、内存和外设等
多道程序系统的优点
增加吞吐量(Increased throughput)
规模经济(Economy of scale) 多处理器系统的成本低于等效的多单处理器系统
增加可靠性(Increased reliability)
对称多道程序系统与非对称多道程序系统
非对称:asymmetric multiprocessing 每个处理器都有各自特定的任务,一个主处理器控制系统,其他处理器或者向主处理器要任务或者完成预定任务
对称:symmetric multiprocessing 每个处理器都要完成操作系统的任务,所有处理器对等,没有主从关系
多模式操作(Dual-mode operation)
为确保操作系统的正常执行,必须区分操作系统代码和用户定义代码的执行。因此存在两种模式
user mode 用户执行
monitor mode 操作系统执行
计算机硬件会设置一个 mode bit 来判断当前模式。当中断或故障发生时,硬件切换为 monitor mode
I/O保护(I/O protection)
所有的I/O指令都是特权指令(privileged instructions),用户执行系统调用,请求操作系统来执行I/O操作,操作系统在 monitor mode 下执行,检查请求是否有效,并且(如果请求有效)执行I/O请求。
内存保护(Memory protection)
为了向中断向量和中断服务程序提供保护,添加了两个寄存器来决定程序可以访问的合法地址范围
基址寄存器(base register) 保存程序的起始物理地址
界限寄存器(limit register) 保存程序的长度
界限外的程序受到保护
定时器(timer)
使用定时器来确保操作系统能维持对CPU的控制,也防止用户程序陷入死循环或不调用系统服务,并且不将控制权返回到操作系统。当定时器的值为0时发生中断,控制权自动交给操作系统。显然,Load-timer是一个特权指令
进程
进程是执行中的程序
操作系统进程管理包括

  • 进程创建(creation)和删除(deletion)
  • 进程暂停(suspension)和恢复(resumption)
  • 进程同步(synchronization)
  • 进程通信(communication)
  • 死锁处理(deadlock handling)

内存管理包括

  • 跟踪哪些内存在使用以及由谁使用
  • 确定哪些进程可以被加载进内存
  • 根据需要分配和释放内存

什么是文件
操作系统对存储设备的物理属性进行了抽象,定义了逻辑存储单元,即文件
文件是由创建者定义的一组相关信息的集合,通常包括文件内容(file contents)、文件格式(file formats)、文件结构(file structures)、文件属性(file attributes)
文件管理包括

  • 创建和删除文件
  • 创建和删除目录(directory)
  • 提供操作文件和目录的原语(primitives)
  • 将文件映射到二级存储器(辅存)上
  • 在稳定的存储媒介上备份文件

I/O管理:操作系统的目标之一是为用户隐藏特定硬件设备的特质。只有设备驱动程序才知道被指定的设备的特质。
I/O管理包括

  • 一个通用的设备驱动程序接口
  • 内存管理组件,包括缓冲(buffering)、缓存(caching)和假脱机(外部设备联机并行技术 Simultaneous Peripheral Operation On-Line)
  • 特定硬件设备的驱动程序

二级存储管理包括

  • 自由空间管理(free space management)
  • 存储分配(storage allocation)
  • 磁盘调度(disk scheduling)

网络管理包括

  • 网络协议
  • 网络设备驱动程序(物理层和数据链路层)

保护管理(protection management)
保护是指控制程序、进程或用户对系统和用户资源的访问的机制。
保护机制必须

  • 区分已授权和未授权的使用
  • 提供一定的方法以规定所有要进行的控制
  • 提供加强控制的方法

什么是命令解释器(command-interpreter)
命令解释器是用户和操作系统之间的接口。
命令解释器可用于交互式用户和批处理用户。
命令解释器可以包含代码段或调用实用程序来执行命令
绝大多数用户所看到的操作系统是由系统程序而不是实际系统调用定义的
操作系统功能

  • 程序执行(program execution):将程序加载到内存并运行它的系统功能
  • I/O操作(I/O operations):由于用户程序无法直接执行I/O操作,操作系统必须提供一些执行I/O操作的方法
  • 文件系统操作(file-system manipulation):读取,写入,创建和删除文件的程序功能
  • 通信(communications):在同一台计算机上或由网络连接在一起的不同系统上执行的进程之间的信息交换。通过共享内存或消息传递实现。
  • 错误检测(error detection):通过检测CPU和内存硬件、I/O设备或用户程序中的错误来确保正确的计算
  • 资源分配(resource allocation):将资源分配给多个用户或同时运行的多个作业
  • 统计(accounting):跟踪和记录哪些用户使用多少以及哪种计算机资源
  • 保护(protection):确保控制所有对系统资源的访问

API(Application Programming Interface)
API(应用程序编程接口)是一些预先定义的函数,目的是提供应用程序与开发人员基于某软件或硬件得以访问一组例程的能力,而又无需访问源码,或理解内部工作机制的细节
系统调用(system calls)
系统调用提供正在运行的程序同操作系统之间的接口
三种用于在程序和操作系统之间传递参数的方法

  • 传递寄存器中的参数
  • 将参数存在内存中的表中,表地址作为参数传入寄存器中
  • 通过程序将参数推送(push)到堆栈中,然后通过操作系统弹出(pop)堆栈

操作系统结构

  • 单层 monolithic
  • 分层 layered
  • 微内核 microkernel
  • 虚拟机 virtual machine

进程(process)

本章主要内容

  • process concept
  • process scheduling
  • process operations
  • process cooperating
  • inter-process communication
  • communication in client-server systems

进程基本概念

进程是一个可拥有资源的独立单元,同时又是一个可独立调度和分派的基本单元
进程包括

  • 程序代码
  • 程序计数器值和处理器寄存器内容
  • 堆栈部分(stack section)和数据部分(data section)

进程的特征

  • 动态性:进程是进程实体的运行过程
  • 并发性:多个进程实体同存于内存中,能在一段时间内同时运行
  • 独立性:进程实体是一个拥有独立的资源,能独立地接受调度并独立的运行的基本单位
  • 异步性:进程按各自独立的、不可预知的速度向前推进
  • 结构性:进程实体是由程序段、数据段及PCB三部分组成

进程状态

  • new
  • running
  • waiting
  • ready
  • terminated
    1

PCB:process control block 进程控制块,是操作系统中存放进程的管理和控制信息的数据结构,主要包括

  • 进程状态(process state)
  • 程序计数器(program counter)
  • CPU寄存器信息
  • CPU调度信息
  • 内存管理信息
  • I/O状态信息

操作系统中的队列(queues)

  • 作业队列(job queue):系统中所有进程的集合
  • 就绪队列(ready queue):准备执行的所有进程的集合
  • 设备队列(device queue):等待I/O设备的进程的集合

调度程序

  • 长程调度(作业调度):选择后备状态的作业建立进程,控制内存中进程的数量
  • 中程调度(交换调度):将进程调入或调出内存
  • 短程调度(CPU调度):选择哪个进程可以执行

上下文切换(Context switch)
当CPU切换到其他进程时,操作系统需要保留现场,存储进程的PCB,当切换回来时加载PCB,这会造成额外开销
2

进程可以创建子进程,形成进程树
三种资源共享方式

  • 父进程与子进程共享所有资源
  • 子进程共享父进程中的部分资源
  • 父进程与子进程不共享任何资源

当进程创建新进程时,有两种执行可能

  • 父进程与子进程并发执行(concurrently)
  • 父进程等待,直到某个或全部子进程执行完毕

UNIX创建进程
fork系统调用,fork创造的子进程复制了父进程的资源,新旧进程使用同一代码段,复制数据段和堆栈段,一旦子进程开始运行,则新旧进程的地址空间已经分开,两者运行独立。在子进程中返回0,在父进程中返回子进程ID,如果出错返回-1

父进程终止子进程

  • 子进程已经用完分配的资源
  • 不再需要分配给子进程任务
  • 父进程被终止

级联终止(cascading termination):如果一个进程终止,那么它的所有子进程也被终止

进程合作

为什么要进程合作

  • information sharing
  • computation speed-up
  • modularity(模块化)
  • convenience

进程合作机制(mechanisms for process cooperation):
communication(合作) and synchronization(同步)

生产者-消费者问题(Bounded-buffer problem)
shared data

1
2
3
4
5
6
#define BUFFER_SIZE 10

typedef struct{
...} item;
item buffer[BUFFER_SIZE];
int in = 0;int out = 0;

producer process

1
2
3
4
5
6
item nextProduced;
while (1){
while(((in+1)%BUFFER_SIZE) == OUT); //缓冲区满,循环等待
buffer[in] = nextProduced;
in = (in+1) % BUFFER_SIZE;
}

consumer process

1
2
3
4
5
6
item nextConsumed;
while(1){
while(in == out); //缓冲区空,循环等待
nextConsumed = buffer[out];
out = (out+1) % BUFFER_SIZE;
}

进程间通信

IPC(inter-process communication)
共享内存方法要求进程共享同一个缓冲池,并且实现缓冲的代码需要应用程序员自己明确编写。实现这种效果的另一种方法是操作系统提供机制,让协作进程能通过进程间通信(IPC)工具来进行彼此间的通信
对称寻址:发送进程和接受进程必须命名对方,以方便通信
非对称寻址:只要发送者命名接收者,而接收者不需要命名发送者
对称和非对称寻址方案的共同缺点是限制了进程定义的模块化
对于间接通信,消息通过邮箱或端口来发送和接收
不管通信是直接的或是间接的,通信进程所交换的消息都驻留在临时队列中。简单来说,队列实现有三种方法:

  • 零容量:发送者必须等待接收者出现
  • 有限容量:当链接满后发送者必须等待
  • 无限容量:发送者无需等待

线程(threads)

线程:有时称轻量级进程(lightweight process),是CPU使用的基本单元;它由线程ID、程序计数器、寄存器集合和堆栈组成。它与属于同一进程的其它线程共享其代码段、数据段和其他操作系统资源
为什么引入线程:减少程序在并发执行时所付出的时空开销,使OS具有更好的并发性
多线程优点

  • 响应度高(responsiveness):多个线程分别处理相应事件
  • 资源共享(resource sharing):线程默认共享它们所属进程的内存和资源
  • 经济(economy):进程创建所需要的内存和资源的分配比较昂贵
  • 多处理器体系结构的利用(utilization of MP architectures):充分使用多处理器体系结构,以便每个线程能并行运行在不同的处理器上

用户线程与内核线程
用户线程在内核之上支持,并在用户层通过线程库来实现。线程库提供对线程创建、调度和管理的支持而无需内核支持。优点:能快速创建和管理。
内核线程由操作系统直接支持:内核在其空间内执行线程创建、调度和管理。内核线程的创建和管理通常要慢于用户线程的创建和管理。
用户线程:如果内核是单线程的,那么任何一个用户级线程若执行阻塞系统调用就会引起整个进程阻塞,即使还有其他线程可以在应用程序内执行。
内核线程:由于内核管理线程,当一个线程执行阻塞系统调用时,内核能调度应用程序内的另一个线程以便执行

多线程模型

  • many-to-one model:将许多用户级线程映射到一个内核线程
  • one-to-one model:每个用户线程映射到一个内核线程
  • many-to-many model:多对多模型多路复用了许多用户级线程到同样数量或更小数量的内核线程上

CPU调度

调度程序从内存中就绪可执行的进程里选择一个,并为其中之一分配CPU
分派程序(process dispatcher):分派程序为短期调度程序提供CPU控制,包括切换上下文、切换到用户模式、跳转到用户程序中的正确位置以重启此程序(PC计数器)
调度延迟:调度程序停止一个进程并启动另一个进程所需的时间
吞吐量:一个时间单元内所完成进程的数量
周转时间:从进程提交到完成的时间间隔,是所有时间段之和
等待时间:进程在就绪队列中等待时间之和
响应时间:从提交请求到产生第一响应时间

调度算法

First Come First Served(FCFS) 先到先服务
3
护航效果(convoy effect):所有其他进程都等待一个大进程释放CPU,导致CPU和设备的使用率变得更低
Shortest Job First(SJF) 最短作业优先
将每个进程与其下一个CPU区间相关联,当CPU为可用时,它会赋给具有最短后续CPU区间的进程。如果两个进程具有相同长度的CPU区间,那么可以使用FCFS调度
抢占式(preemptive):如果一个新来的进程其CPU区间小于当前进程的CPU区间,则抢占之。这种调度称为最短剩余时间作业优先(SRTF)
5
非抢占式(non-preemptive):一旦进程获得CPU就一直占据CPU,直到其CPU区间完成为止
4
Priority scheduling 优先级调度
CPU被分配给具有最高优先级的进程
6
问题:Starvation(饥饿)-低优先级进程可能永远不会执行
解决方法:Aging(老化)-一个进程将随着时间的推移而增加其优先级
Round Robin 轮转法调度
每个进程获得一小部分CPU时间(time quantum),经过这段时间后,该进程被抢占并添加到就绪队列的末尾。将就绪队列保持为进程的FIFO队列,并将新进程添加到就绪队列的尾部。CPU调度程序从就绪队列中选择第一个进程,将计时器设置为在一个time quantum后中断,然后调度该进程。
调度存在两种情况:进程需要小于一个time quantum的CPU区间,此时进程本身会自动释放CPU,调度程序接着处理就绪队列的下一个进程;进程运行所需时间大于一个time quantum,定时器会发生中断,进行上下文切换,该进程被加入到就绪队列尾部,CPU调度程序会选择就绪队列中的下一个进程
7
如果时间片过小,上下文切换会使进程执行减慢
Multilevel queue algorithm 多级队列调度
就绪队列被划分为单独的队,每个队列都有自己的调度算法,必须在队列间进行调度。进程进入系统时,被永久地分配到一个队列,这种设置的优点是低调度开销,缺点是不够灵活
8
Multilevel feedback queue algorithm 多级反馈队列调度
一个进程可以在各个队列之间移动,如果进程使用过多CPU时间,会将其移至优先级较低的队列,在较低优先级队列中等待太长的进程可以移动到较高优先级的队列
定义多级反馈队列调度程序的参数:

  • 队列数量
  • 每个队列的调度算法
  • 用于确定进程需要服务时进程进入哪个队列的方法
  • 用于确定何时升级/降级进程的方法

进程同步(process synchronization)

共享数据的并发访问会导致数据不一致,维护数据的一致性需要能够保证协作进程顺序执行的机制
原子操作(atomic operation):一个不会中断的完整操作
竞争条件(race condition):多个进程并发访问和操作同一数据且执行结果与访问发生的特定顺序有关
临界资源:一次仅允许一个进程使用的资源称为临界资源
把临界资源的访问过程分成四个部分:

  • 进入区(entry section):为了进入临界区使用临界资源,在进入区要检查可否进入临界区,如果可以进入临界区,则应设置正在访问临界区的标志,以阻止其他进程同时进入临界区
  • 临界区(critical section):在每个进程中,访问临界资源的那段代码称为临界区
  • 退出区(exit section):将正在访问临界区的标志清除
  • 剩余区(remainder section):代码中的其余部分

同步机制应遵循的标准

  • 互斥(mutual exclusion):如果进程Pi在其临界区执行,那么其他进程都不能在其临界区内执行
  • 有空让进(progress):临界区空闲时,可以允许一个请求进入临界区的进程立即进入临界区
  • 有限等待(bounded waiting):对请求访问的进程,应保证能在有限时间内进入临界区

软件实现进程同步

单标志算法

核心思想:设置一个公共整形变量turn,用于指示被允许进入临界区的进程编号

1
2
3
4
5
6
7
8
9
10
//shared variables
int turn; //初始 turn = 0
turn = i; //决定哪个进程可以访问临界区
//process Pi
do {
while(turn != i);//循环等待
critical section
turn = j;
reminder section
}while(1);

问题:P0和P1只能交替使用,而且当某个进程不再进入临界区了,那么另一个进程不再进入临界区,这种情况不满足有空让进

双标志算法

核心思想:每一个进程在访问临界区之前,先查看一下临界区是否正在被访问,如果正在被访问,等待,否则进入临界区

1
2
3
4
5
6
7
8
9
10
11
//shared variables
boolean flag[2]; //初始 flag[0]=flag[1]=false
flag[i] = true;
//process Pi
do{
flag[i] = true;
while(flag[j]); //循环等待
critical section
flag[i] = flase;
remainder section
}while(1);

问题:不需要交替使用,但Pi和Pj可能同时进入临界区,将flag置为true。这时Pi和Pj在各自的while语句内循环等待,违反了有空让进

Peterson算法

核心思想:每个进程宣布自己想访问临界区,但是这一轮先不访问,把turn设置为对方的

1
2
3
4
5
6
7
8
9
//process Pi
do{
flag[i] = true; //表示Pi想访问临界区
turn = j; //表示j可以进入临界区
while(flag[j] and turn == j); //当Pj想访问且有权访问时,Pi循环等待
critical section //否则访问临界区
flag[i] = false;
remainder section
}while(1);

代码可以解释为,如果P0和P1并发,必有一个会进入while循环(flag[i]或flag[j]均为true),而另一个会完成自己的任务,完成自己的任务后将自己的flag置为false,这时对方的while条件不再满足,即可执行的程序,实现互斥

面包店算法

核心思想:每个线程在门廊区得到一个序号,然后一直等待,直到再没有序号比自己更早的线程尝试进入临界区为止,如果两个线程的排队签到号码相等,则线程id号较小的具有优先权

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//shared data
boolean choosing[n]; // choosing[i]==true 表示进程i正在获取它的排队登记号
int number[n]; //Number[i]的值,是进程i的当前排队登记号。如果值为0,表示进程i未参加排队,不想获得该资源。规定这个数组元素的取值没有上界
//process Pi
do{
choosing[i] = true;
number[i] = max(number[0],...,number[n-1]) + 1;
choosing[i] = false;
for(j=0; j<n; j++){
while(choosing[j]);
while((number[j] != 0) && ((number[j],j) < (number[i],i)));
}
critical section
number[i] = 0;
remainder section
}while(1);

硬件实现进程同步

计算机提供了特殊的硬件指令,允许对一个字中的内容进行检测和修正(TestAndSet),或者是对两个字的内容进行交换(Swap)等。这些硬件指令是原子操作
TestAndSet

1
2
3
4
5
6
7
8
9
10
//TestAndSet,读出指定标志后把该标志设置为真
boolean TestAndSet(boolean &target){ boolean rv = target; target = true; return rv;}// shared data
boolean lock = false;
// process Pi
do{
while(TestAndSet(lock));
critical section
lock = false;
remainder section
}

为每个临界资源设置一个共享布尔变量lock,表示资源的两种状态:true表示正被占用,初值为false。在进程访问临界资源之前,利用TestAndSet检查和修改标志lock;若有进程在临界区,则重复检查,直到进程退出

Swap

1
2
3
4
5
6
7
8
9
10
11
12
//swap,交换两个字节的内容
void Swap(boolean &a, boolean &b){ boolean temp = a; a = b; b = temp;}
//shared data
boolean lock = false;
//process Pi
do{
key = true;
while(key == true) Swap(lock,key);
critical section
lock = false;
remainder section
}

为每个临界资源设置了一个共享布尔变量lock,初值为false;在每个进程中再设置一个局部布尔变量key,用于与lock交换信息。在进入临界区之前先利用Swap指令交换lock 与key的内容,然后检查key的状态;有进程在临界区时,重复交换和检查过程,直到进程退出

生产者-消费者问题的TestAndSet实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//shared data
boolean waitng[i];
boolean lock;
do{
waiting[i] = true;
key = true;
while(waiting[i] && key) key = TestAndSet(lock);
waiting[i] = fales;
critical section
j = (i+1) % n;
while((j != i) && !waiting[j]) j = (j+1) %n;
if(j == i) lock = false;
else waiting[j] = false;
remainder section
}while(1);

只有waiting[i]=false或key=false时,进程Pi才进入其临界区。只有当TestAndSet执行时,key的值才变为false。执行TestAndSet的第一个进程会发现key==false;所有其他进程必须等待。只有其他进程离开其临界区时,变量waiting[i]的值才能变为false;每次只有一个waiting[i]被设置为false,以维护互斥要求

信号量机制

信号量(semaphore)
信号量机构是一种功能较强的机制,可用来解决互斥与同步的问题,它只能被两个标准的原语wait(S)和signal(S)来访问,也可以记为“P操作”和“V操作”

1
2
3
4
5
6
7
8
9
//shared data
semaphore mutex; //初始为1
//Process Pi
do{
wait(mutex);
critical section
signal(mutex);
remainder section
}while(1);

记录型信号量
记录型信号量是不存在“忙等”现象的进程同步机制。除了需要一个用于代表资源数目的整型变量value外,再增加一个进程链表L,用于链接所有等待该资源的进程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct{ 
int value;
struct process *L;
}semaphore;

//wait操作,S.value--,表示进程请求一个该类资源,当S.value<0时,表示该类资源已分配完毕,因此进程应调用block原语,进行自我阻塞,放弃处理机,并插入到该类资源的等待队列S.L中
wait(S):
S.value--;
if(S.value<0){
add this process to S.L;
block;}

//signal操作,表示进程释放一个资源,使系统中可供分配的该类资源数增1,故S.value++。若加1后仍是S.value<=0,则表示在S.L中仍有等待该资源的进程被阻塞,故还应调用wakeup 原语,将S.L中的第一个等待进程唤醒
signal(S):
S.value++;
if(S.value<=0){
remove a process P from S.L;
wakeup(P);
}

死锁(Deadlock):两个或多个进程无限地等待一个事件,而该事件只能由这些等待进程之一来产生
饥饿(Starvation):无限阻塞,一个被悬挂的进程可能永远无法从信号量队列中移出
计数信号量(counting semaphore):其整数值可跨越于一个不受限制的域内
二进制信号量(binary semaphore):只能为整数值0或1

用二进制信号量实现计数信号量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//shared variables
binary-semaphore S1=1,S2=0;
int C;

//wait操作
wait(S1);
C--;
if(C<0){
signal(S1);
wait(S2);
}
signal(S1);

//signal操作
wait(S1);
C++;
if(C<=0) signal(S2);
else signal(S1);

经典进程同步问题

有限缓存问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//shared data
semaphore mutex=1; //临界区互斥信号量
semaphore full=0; //缓冲区初始化为空
semaphore empty=n; //空闲缓冲区

//生产者进程
producer () {
while(1){
produce an item in nextp; //生产数据
wait(empty); //获取空缓冲区单元
wait(mutex); //进入临界区.
add nextp to buffer; //将数据放入缓冲区
signal(mutex); //离开临界区,释放互斥信号量
signal(full); //满缓冲区数加1
}
}

//消费者进程
consumer () {
while(1){
wait(full); //获取满缓冲区单元
wait(mutex); // 进入临界区
remove an item from buffer; //从缓冲区中取出数据
signal(mutex); //离开临界区,释放互斥信号量
signal(empty) ; //空缓冲区数加1
consume the item; //消费数据
}
}

该类问题要注意对缓冲区大小为n的处理,当缓冲区中有空时便可对empty变量执行P 操作,一旦取走一个产品便要执行V操作以释放空闲区。对empty和full变量的P操作必须放在对mutex的P操作之前

读者-写者问题

一个数据对象可以为多个并发进程所共享。其中有的进程可能只需要读共享对象的内容,而其他进程可能要更新共享对象(即读和写)
读者优先:如果共享内存正在被读,其它的读者不应该苦等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//shared data
semaphore mutex = 1; //用于确保在更新变量readcount时的互斥
semaphore wrt = 1; //为读者和写者进程所共用,供写者作为互斥信号量使用
int readcount = 0; //用来记录有多少进程正在读对象

//写者进程
writer () {
while (1){
wait(wrt); // 互斥访问共享文件
Writing; //写入
signal(wrt) ; //释放共享文件
}
}

//读者进程
reader () {
while(1){
wait(mutex) ; //互斥访问readcount变量
readcount++;
if (readcount==1) //当第一个读进程读共享文件时
wait(wrt); //阻止写进程写
signal(mutex) ; //释放互斥变量readcount
reading; //读取
wait(mutex); //互斥访问count变量
readcount--; //读者计数器减1
if(readcount==0) //当最后一个读进程读完共享文件
signal(wrt); //允许写进程写
signal(mutex); //释放互斥变量readcount
}
}

当存在读进程时,写操作将被延迟,并且只要有一个读进程活跃,随后而来的读进程都将被允许访问文件。这样的方式下,会导致写进程可能长时间等待,且存在写进程“饿死”的情况。

写者优先:如果一个作者在排队,就不应该让它等得太久,即当有读进程正在读共享文件时,有写进程请求访问,这时应禁止后续读进程的请求,等待到已在共享文件的读进程执行完毕则立即让写进程执行,只有在无写进程执行的情况下才允许读进程再次运行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//shared data
semaphore mutex = 1; //用于确保在更新变量readcount时的互斥
semaphore wrt = 1; //为读者和写者进程所共用,供写者作为互斥信号量使用
semaphore w = 1; //用于实现“写优先”
int readcount = 0; //用于记录当前的读者数量

//写者进程
writer(){
while(1){
wait(w); //在无写进程请求时进入
wait(wrt); //互斥访问共享文件
writing; //写入
signal(wrt); // 释放共享文件
signal(w) ; //恢复对共享支件的访问
}
}

//读者进程
reader () {
while (1){
wait(w) ; // 在无写进程请求时进入
wait(mutex); // 互斥访问readcount变量
readcount++;
if (readcount==1) //当第一个读进程读共享文件时
wait(wrt); //阻止写进程写
signal(mutex) ; //释放互斥变量readcount
signal(w); //恢复对共享文件的访问
reading; //读取
wait(mutex) ; //互斥访问readcount变量
readcount--;
if (count==0) //当最后一个读进程读完共享文件
signal(wrt); //允许写进程写
signal(mutex); //释放互斥变量readcount
}
}

哲学家进餐问题

一张圆桌上坐着5名哲学家,每两个哲学家之间的桌上摆一根筷子,桌子的中间是一碗米饭,当哲学家饥饿的时候,才试图拿起左、 右两根筷子(一根一根地拿起)。如果筷子已在他人手上,则需等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐,当进餐完毕后,放下筷子继续思考。
1
有问题的解决方法

1
2
3
4
5
6
7
8
9
10
11
12
//shared data
semaphore chopstick[5] = {1,1,1,1,1}; //定义信号量数组chopstick[5],并初始化

//哲学家i
do{
wait(chopstick[i]); //取左边筷子
wait(chopstick[(i+1)%5]); //取右边篌子
eat; //进餐
signal(chopstick[i]); //放回左边筷子
signal(chopstick[(i+l)%5]); //放回右边筷子
think; //思考
}while(1);

当五个哲学家都想要进餐,分别拿起他们左边筷子的时候(都恰好执行完wait(chopstick[i]);)筷子已经被拿光了,等到他们再想拿右边的筷子的时候(执行 wait(chopstick[(i+l)%5]);)就全被阻塞了,这就出现了死锁
解决办法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//shared data
semaphore chopstick[5] = {1,1,1,1,1};
semaphore coord = 4; //至多允许四个哲学家同时进餐

//哲学家i
do{
wait(coord); //整个过程中获取互斥量
wait(chopstick[i]);
wait(chopstick[(i+1)%5]);
eat;
signal(chopstick[i]);
signal(chopstick[(i+1)%5]);
signal(coord);
think;
}while(1);

死锁(Deadlock)

系统拥有一定数量的资源,分布在若干竞争进程之间。资源分成多种类型,如内存空间、CPU周期、文件、I/O设备等。每种类型有相同数量的实例
正常操作模式下,进程按如下顺序使用资源

  • 申请:如果申请不能立即被允许,那么申请进程必须等待直到它获得该资源为止
  • 使用:进程对资源进行操作
  • 释放:进程释放资源

如果同时满足以下四个条件时,就会引起死锁

  • 互斥(mutual exclusion)
  • 占有并等待(hold and wait)
  • 非抢占(no preemption)
  • 循环等待(circular wait)

对待死锁的三种方式

  • 可使用协议以预防或避免死锁,确保系统永远不会进入死锁状态
  • 可允许系统进入死锁状态,然后检测它,并加以修复
  • 可忽略这个问题,认为死锁不可能在系统内发生。绝大多数操作系统都使用这种方法

死锁预防:只要死锁出现的四个必要条件之一不满足就可以
死锁避免:在资源动态分配过程中,防止系统进入不安全状态,以避免发生死锁
系统安全状态:指系统能按某种进程推进顺序( P1, P2, …, Pn),为每个进程Pi分配其所需资源,直至满足每个进程对资源的最大需求,使每个进程都可顺序地完成。此时称 P1, P2, …, Pn 为安全序列。如果系统无法找到一个安全序列,则称系统处于不安全状态

银行家算法

数据结构

  • available:可利用资源,Available[j]=K,则表示系统中现有Rj类资源K个
  • max:定义了系统中n个进程中的每一个进程对m类资源的最大需求。Max[i, j]=K,则表示进程i需要Rj类资源的最大数目为K
  • allocation:定义了系统中每一类资源当前已分配给每一进程的资源数。All0Cati0n[i, j]= K,则表示进程i当前已分得Rj类资源的数目为K
  • need:表示每个进程尚需的各类资源数。Need[i, j]=K,则表示进程i还需要Rj类资源的数目为K

算法步骤:

  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,它表示系统是否有足够的资源分配给进程,使之运行完成,当有足够资源分配给进程时,再令Finish[i]=true
  2. 从进程集合中找到一个能满足下述条件的进程:
    Finish[i] = false;
    Need[i,j] ≤ Work[j];若找到,执行3,否则,执行4
  3. 当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:
    Work[j] = Work[j] + Allocation[i,j];
    Finish[i]:=true;
    go to 2;
  4. 如果所有进程的Finish[i]=true都满足,则表示系统处于安全状态;否则,系统处于不安全状态

死锁的检测与解除

系统死锁,可利用资源分配图来描述。用圆圈代表一个进程,用框代表一类资源。由于一种类型的资源可能有多个,用框中的一个点代表一类资源中的一个资源。从进程到资源的有向边叫请求边,表示该进程申请一个单位的该类资源;从资源到进程的边叫分配边,表示该类资源已经有一个资源被分配给了该进程
7-1
应何时调用检测算法,取决于两个因素

  • 死锁可能发生的频率是多少?
  • 当死锁发生时,有多少进程会受影响?

打破死锁状态有两个方法

  • 简单地终止一个或多个进程以打破循环等待
  • 从一个或多个死锁进程那里抢占一个或多个资源

确定终止哪个进程或哪些进程可以打破死锁需要考虑的因素

  • 进程的优先级是什么?
  • 进程已计算了多久,进程在完成其指定任务之前还需要多久?
  • 进程使用了多少什么类型的资源(是否容易抢占?)
  • 进程需要多少资源以完成?
  • 多少进程需要被终止?
  • 进程是交互的还是批处理的?

如果要求使用抢占来处理死锁,那么有三个问题需要处理

  • 选择一个牺牲品
  • 回滚:必须将被抢占进程的状态恢复到某个安全状态
  • 饥饿:如何保证资源不会总是从同一个进程被抢占。

解决方法:在代价因素中加上回滚次数。

内存管理(memory management)

逻辑地址:由CPU生成,也称为虚拟地址
物理地址:内存单元所看到的地址
在编译时(compile-time)地址绑定和加载时(load-time)地址绑定方案中,逻辑地址与物理地址是相同的。但是执行时(execution-time)地址绑定方案中,逻辑地址与物理地址不同
加载之前已经形成绝对地址,逻辑地址的值已经等于绝对地址
内存管理单元(Memory-Management Unit):运行时从虚拟地址映射到物理地址的硬件设备称为内存管理单元
用户进程所生成的地址在送交内存之前,都将加上重定位寄存器的值。用户程序处理的是逻辑地址
8-1
将指令与数据绑定到内存地址的时刻

  • 编译时:如果在编译时就知道进程将在内存中的驻留地址,那么就可以生成绝对代码。如果将来地址发生了变化,就必须重新编译代码
  • 加载时:如果在编译时不知道进程将驻留何处,那么编译器就必须生成可重定位代码
  • 运行时:如果进程在执行时可以从一个内存段移到另一个内存段,那么绑定必须延迟到执行时才进行,这种方案需要特定硬件支持

一个子程序只有在调用时才被加载,为了更好的内存空间利用率,不用的子程序不会被装入内存。
如果大多数代码需要用来处理异常情况,如错误处理,那么这种方法特别有用。
动态加载不需要操作系统提供特别的支持。利用这种方法来设计程序主要是用户的责任。
动态连接过程推迟到执行时进行
存根(stub):一小段代码,用来指出如何定位适当的内存驻留程序,或如果该程序不在内存时应如何装入库
存根会用子程序地址来替换自己,并开始执行子程序
覆盖(overlays):在任何时候只在内存中保留所需的指令和数据。当需要其他指令时,它们会装入到刚刚不再需要的指令所占用的内存空间内
交换(swapping):进程可以暂时从内存中交换出来到备份存储上,当需要再执行时再调回到内存中
滚进、滚出(roll out, roll in):是交换策略的一个变种,被用于基于优先权的调度算法中。如果一个更高优先级进程来了且需要服务,内存管理可以交换出低优先级的进程,以便可以装入和执行更高优先级的进程。当更高优先级进程执行完后,低优先级进程可以交换回内存以继续执行
内存通常分为两个区域:一个用于驻留操作系统,常与中断向量一起放在低内存;另一个用于用户进程,常放在高内存。
通过采用重定位寄存器和界限寄存器,可以实现对内存的保护。可以保证操作系统和其他用户程序及数据不受该进程的运行所影响。重定位寄存器含有最小的物理地址值;界限寄存器含有逻辑地址值的范围
9
(hole):可用内存块,通常,一组不同大小的孔分散在内存中
从一组可用孔中选择一个空闲孔的最为常用方法有

  • 首次适应(first-fit):分配第一个足够大的孔
  • 最佳适应(best-fit):分配最小的足够孔
  • 最差适应(worst-fit):分配最大的孔

模拟结果显示首次适应和最好适应在执行时间和利用空间方面都好于最差适应。首次适应和最好适应在利用空间方面难分伯仲,但是首次适应要快些
外碎片(external fragmentation):还没有被分配出去,但由于太小了无法分配给申请内存空间的新进程的内存空闲区域
内碎片(internal fragmentation):进程所分配的内存可能比所需要的要大,这部分已经被分配出去却不能被利用的内存空间就是内碎片
一种解决外部碎片问题的方法是紧缩(shuffle)。紧缩的目的是移动内存内容,以便所有空闲空间合并成一整块。紧缩是有一定条件的,要求重定位是动态的
另一种可能解决外部碎片问题的方法是允许物理地址空间为非连续,这样只要有物理内存就可为进程分配。
有两种互补的机制可以实现这种算法:分页机制(paging)和分段机制(segmentation)。这两种技术也可以组合到一起。

paging

物理内存分为固定大小的块,称为帧(frames)
逻辑内存也分为同样大小的块,称为页(pages)
备份存储也可以分为同样大小的块,称为簇(clusters)
页表:包含物理内存中每个页面基址的表
页号(p):页号作为页表中的索引,页表中包含每页所在物理内存的基地址
页偏移(d):与页的基地址组合形成物理地址
10
页的大小通常为2的幂,根据计算机结构的不同,其大小从512B到16MB字节不等。
采用分页技术不会产生外部碎片:每个帧都可以分配给需要它的进程。不过,分页有内部碎片
当系统需要执行一个进程时,它将检查该进程所需要的页数。因此,如果进程需要n页,那么内存中至少应有n个帧。如果有,那么就可分配给新进程。进程的第一页装入一个已分配的帧,帧号放入进程的页表中。下一页分配给另一帧,其帧号也放入进程的页表中
页表的硬件实现有多种方法。最为简单的一种方法是将页表作为一组专用寄存器来实现。CPU分派程序在装入其他寄存器时,也需要装入这些寄存器。页表非常大的时候,采用快速寄存器来实现页表就不可行了。因而需要将页表放在内存中,并将页表基寄存器(PTBR)指向页表。改变页表只需改变这一寄存器即可,这也大大降低了切换时间
两次内存访问问题可以用翻译后备缓冲器(translation look-aside buffers 即TLBs)来解决
11
在分页环境下,内存保护是通过与每个帧相关联的保护位(protection bit)来实现的。通常这些位保存在页表中,任何一位都能定义一个页是可读、可写或只可读
有效无效位(valid-invalid bit)与页表中的每一条目相关联:当该位有效时,该值表示相关的页在进程的逻辑地址空间内,因此是合法的页.该位无效时,该值表示相关的页不在进程的逻辑地址空间内
12
绝大多数现代计算机系统支持大逻辑地址空间。在这种情况下,页表本身可以非常大。显然,人们并不愿意在内存中连续地分配这个页表。
这个问题的一个简单解决是将页表划分成更小部分。
完成上述划分有许多方法,一种方法是使用两层分页算法,就是将页表再分页
13
处理超过32位地址空间的常用方法是使用Hash页表虚拟页号与链表中的每 一个元素的第一个域相比较。如果匹配,那么对应的帧码就用来形成位置地址。如果不匹配,那么就对链表中的下一个域进行页码比较。每个元素有三个域:虚拟页码、所映射的帧号和指向链表中下一个元素的指针
14

segmentation

逻辑地址空间是由一组段组成,每个段都有名称和长度。地址指定了段名称和段内偏移
逻辑地址由两个元素组成<段号s,偏移d>
段表:将二维的用户定义地址映射为一维物理地址。段表的每个条目都有段基地址和段界限。
基地址:包含段的起始地址
界限:指定段的长度
段表基地址寄存器(STBR):指向内存中的段表的位置
段表长度寄存器(STLR):指示程序所用的段的个数
段号S小于STLR的时候才是有效的
段号用做段表的索引。逻辑地址的偏移d应位于0和段界限之间。如果不是这样,则会陷入到操作系统中。如果偏移d合法,那么就与基地址相加而得到所需字节在物理内存的地址。因此段表是一组基址和界限寄存器对
15
分段的一个显著优点是可以将段与对其的保护相关联。因为段内所有内容可能会按同样方式使用。因此有的段是指令,而有的段是数据。内存映射硬件会检查与段条目相关联的保护位以防止对内存的非法访问。
分段的另一个优点是关于代码或数据的共享。每个进程都有一个段表,当该进程被允许使用CPU时,分派程序会定义一个硬件段表。当两个进程的某些条目指向同一个物理位置时,就可以共享段
16

虚拟内存

在许多情况下并不需要将整个程序放到内存中
能够执行只有部分在内存中的程序会有很多好处:

  • 程序不再受现有的物理内存空间限制。简化了编程任务
  • 因为每个用户程序使用了更少的物理内存,所以更多的程序可以同时执行
  • 由于装入或交换每个用户程序到内存中所需的I/O会更少,用户程序会运行的更快

虚拟内存:虚拟内存将内存抽象成一个巨大的、统一的存储数组,进而将用户看到的逻辑内存与物理内存分开
17
虚拟内存的实现:请求页式调度,请求段式调度

请求页式调度

请求页面调度类似于分页系统加上交换。进程驻留在次级存储器上。当需要执行进程时,将它调入内存。不过,不是将整个进程换入内存,而是使用lazy swapper。
lazy swapper:只有在需要页时,才将它调入内存
对这种方案,需要一定形式的硬件来区分哪些页在内存里,哪些页在磁盘上。有效-无效位可以用于这一目的。现在当该位置为“有效”时,该值表示相关的页既合法且也在内存中。当该位设置为“无效”时,该值表示相关得页为无效(也就是,不在进程的逻辑地址空间中)或者有效但在磁盘上
缺页(Page fault):当软件试图访问已映射在虚拟地址空间中,但是目前并未被加载在物理内存中的一个分页时,由中央处理器的内存管理单元所发出的中断
处理缺页

  1. 检查进程的页表,以确定该引用是合法还是非法的地址访问。
  2. 如果引用非法,那么终止进程。如果引用有效但是尚未调入页面,那么现在应调入。
  3. 找到一个空闲帧(从空闲帧链表中取一个)
  4. 调度一个磁盘操作,以便将所需要的页调入刚分配的帧
  5. 当磁盘读操作完成后,修改进程的内部表和页表,以表示该页已在内存中。
  6. 重新开始因非法地址陷阱而中断的指令。进程现在能访问所需的页,就好像它似乎总在内存中。

写时拷贝(copy-on-write):只有进程空间的各段的内容要发生变化时,才会将父进程的内容复制一份给子进程
内存映射文件(Memory-Mapped Files):将文件I/O作为普通内存访问,它允许一部分虚拟内存与文件逻辑相关联。文件的内存映射可将一磁盘块映射成内存的一页

页置换

  1. 查找所需页在磁盘上的位置
  2. 查找一空闲帧,如果有空闲帧,那么就使用它,如果没有空闲帧,那么就使用页置换算法以选择一个“牺牲”帧(victim frame)。将“牺牲”帧的内容写到磁盘上;改变页表和帧表。
    3.将所需页读入新空闲帧;改变页表和帧表
    4.重启用户进程。
    18
    降低额外开销的方法:可通过修改位(或脏位)(modify bit or dirty bit)来降低额外开销。每页或帧可以有一个修改位通过硬件与之相关联。每当页内的任何字或字节被写入时,硬件就会设置该页的修改位以表示该页以修改

FIFO

先进先出置换算法:选择在主存中停留时间最长的一页置换,即先进入内存的页,先退出内存
19
Belady异常:对有的页置换算法,页错误率可能会随着所分配的帧数的增加而增加。

OPT

最优页置换算法:置换那些以后永不使用的,或者是在最长时间内不再被访问的页面,但实际上无法实现
20

LRU

最近最久未使用算法:选择在最近一段时间里最久没有使用过的页面予以置换
21
LRU算法需要实际硬件的支持,问题是确定最后使用时间的顺序,有两种解决办法

  • 计数器:为每个页表项关联一个使用时间域,并为CPU增加一个逻辑时钟或计数器。对每次内存引用,计数器都会增加。每次内存引用时,时钟寄存器的内容会复制到相应页所对应页表项的使用时间域内。置换具有最小时间的页
  • 页码堆栈:每次引用一个页,该页就从堆栈中删除并放在顶部。这样,堆栈顶部总是最近使用的页,堆栈底部总是LRU页
  • 附加引用位算法(Additional-reference-bits algorithm):可以为位于内存中的每个表中的页保留一个8bit的字节。在规定的时间间隔(如每100ms)内,时钟定时器产生中断并将控制转交给操作系统。操作系统把每个页的引用位转移到其8bit字节的高位,而将其他位向右移,并抛弃最低位。这些8bit移位寄存器包含着该页在最近8个周期内的使用情况。如果将这8bit字节作为无符号整数,那么具有最小值的页为LRU页,且可以被置换。

二次机会算法(second-chance)

基本思想是与FIFO相同的,但是有所改进,避免把经常使用的页面置换出去。当要选择一个页时,检查其引用位,如果其值为0那么就直接置换该页;如果该引用位为1,那么就给该页第二次机会,并选择下一个FIFO页。当一个页获得第二次机会时,其引用位清零,且其到达时间设为当前时间。如果该页在此期间被访问过,则访问位置1。这样给了第二次机会的页面将不被淘汰,直至所有其他页面被淘汰过(或者也给了第二次机会)。因此,如果一个页面经常使用,它的访问位总保持为1,它就从来不会被淘汰出去
一种实现二次机会算法的方法是采用循环队列

其他算法

最不经常使用页置换算法(LFU):置换计数最小的页
最常使用页置换算法(MFU):具有最小次数的页可能刚刚调进来,且还没有使用

帧分配

平均分配:如100帧,5个进程,则给每个进程20帧
比例分配:根据进程的大小按比例分配
另一个方法是使用比例分配的策略,但不是根据进程相对大小,而是根据进程优先级或是大小和优先级的组合
如果进程 Pi 产生了一个页错误,那么从自身的帧中选择用于替换,或从比自身优先级低的进程中选取帧用于替换
全局置换:允许一个进程从所有帧集合中选择一个置换帧,而不管该帧是否已分配给其他进程;一个进程可以从另一个进程中取帧
局部置换:要求每个进程仅从其自己的分配帧中进行选择
颠簸(thrashing):如果一个进程出现了页错误,必须置换某个页。然而,其所有页都在使用,它置换一个页,但又立刻再次需要这个页。因此,它会不断地产生页错误。进程继续页错误,置换一个页而该页又立即出错且需要立即调进来。这种频繁的页调度的行为称做颠簸
CPU调度程序发现CPU利用率降低,因此会增加多道程序的程度。新进程试图从其他运行进程中拿帧,从而引起更多页错误,更长的调页设备的队列。因此,CPU利用率进一步降低,CPU调度程序试图再增加程序的程度。这样系统颠簸就出现了,系统吞吐量突降,页错误显著增加
颠簸的原因:分配的帧数少于现有局部的大小
工作集窗口(Working set window):如果一个页正在使用中,那么它就在工作集合内。工作集合是程序局部的近似
页错误率策略:如果错误率太低,则进程可能有太多的帧,因此应丢弃一些帧,如果错误率太高,则为进程分配更多帧

文件系统

操作系统对存储设备的各种属性加以抽象并且定义了逻辑存储单元(文件),再将文件映射到物理设备上
文件(file):记录在外存上相关信息的具有名称的集合。从用户角度而言,文件是逻辑外存的最小分配单元
文件的属性

  • 名称:文件符号名称是唯一的,按照人们容易读取的形式保存
  • 标识符:标识文件系统内文件的唯一标签,通常为数字
  • 类型:由OS和程序定义
  • 位置:该信息指向设备和设备上文件位置的指针
  • 大小:文件当前大小,该属性也能包括可允许大小的最大值
  • 保护:决定谁能读、写、执行等的访问控制信息
  • 时间、日期和用户标识:文件创建、上次修改和上次访问都可能有该信息。用于保护、安全和使用跟踪

Open(Fi):在磁盘上的目录结构中查找Fi,并将其内容复制到内存
Close(Fi):将内存中的Fi的内容复制到位于磁盘上的目录结构中

整个系统表包含进程无关信息如文件在磁盘上的位置、访问日期和文件大小。一旦一个进程打开一个文件,另一个进程执行open,其结果只不过简单地在其进程打开表中增加一个条目,并指向整个系统表的相应条目。通常,系统打开文件表的每个文件还有一个文件打开计数器open count,以记录多少进程打开了该文件
文件访问方式

  • 顺序访问:文件信息按顺序,一个记录接着一个记录地加以处理。顺序访问基于文件的磁带模型
  • 直接访问:文件由固定长度的逻辑记录组成,以允许程序按任意顺序进行快速读和写

其他访问方式可建立在直接访问方式之上。这些访问通常涉及创建文件索引。索引,如同书的索引,包括各块的指针。为了查找文件中的记录,首先搜索索引,再根据指针直接访问文件,以查找所需要的记录。
对于大文件,索引本身可能太大以至于不能保存在内存中。解决方法之一是为索引文件再创建索引。初级索引文件包括二级索引文件的指针,而二级索引再包括真正指向数据项的指针
计算机的文件系统可以非常大。有的系统在数千吉磁盘上保存了数以万计的文件。为了管理所有这些数据,需要组织它们。这种组织通常分为两部分:
第一,磁盘分为一个或多个分区,或称为小型磁盘或卷。通常,每个系统磁盘至少包括一个分区,这是用来保存文件和目录低层结构。
第二,每个分区都包括了存储在分区中的文件的信息。这种信息保存在设备目录或卷内容表中。设备目录记录分区上所有文件的各种信息,如名称、位置、大小和类型等
一致性语义(consistency semantics):描述了多用户同时访问共享文件的语义。特别地,这些语义规定了一个用户所修改的数据何时对另一个用户可见
UNIX语义:一个用户对已经打开的文件进行写操作,可以被同时打开同一文件的其他用户看见。有一种共享模式允许用户共享文件当前指针的位置
ASF语义(Andrew File System Semantics):一个用户对打开文件的写不能被同时打开同一文件的其他用户所看见。一旦文件关闭,对其修改只能为以后打开的会话所看见。已经打开文件的用户并不能看见这些修改
永久共享文件语义(Immutable-shared file semantics):一旦一个文件被其创建者声明为共享,它就不能被修改。永久共享文件有两个重要特性:文件名不能重用,且文件内容不可修改

文件系统实现

目录(directory):目录用来记录磁盘上某一个分区中所有文件的信息,可以看成是一个标志的表,用来将文件的名字翻译成一个记录的实体,该实体包括文件的名字、类型、地址、文件长度,所有者等信息
磁盘的特点

  • 可以原地重新写:可以从磁盘上读一块,修改该块,并将它写回到原来的位置
  • 可以直接访问磁盘上的任意一块信息

为了改善I/O效率,内存与磁盘之间的I/O转移是以块为单位而不是以字节为单位来进行的
为了提供对磁盘的高效且便捷的访问,操作系统通过文件系统来轻松地存储、定位、提取数据
文件系统的结构
25
I/O控制(I/O control):由设备驱动程序和中断处理程序组成,实现内存与磁盘之间的信息转移。其输出由底层的、硬件特定的命令组成,这些命令用于硬件控制器,通过硬件控制器可以使I/O设备与系统其他设备相连。设备驱动程序通常在I/O控制器的特定位置写入特定格式来通知控制器在什么位置采取什么动作
基本文件系统(Basic file system):向合适的设备驱动程序发送一般命令就可以对磁盘上的物理块进行读写,每个块由其磁盘地址来标识
文件组织模块(file-organization module):知道文件及其逻辑块和物理块,可以将逻辑块地址转换成基本文件系统所用的物理块地址
逻辑文件系统(logical file system):管理元数据(metadata),元数据包括文件系统的所有数据结构,而不包括实际数据。根据给定符号文件名来管理目录结构,并提供给文件组织模块所需要的信息。逻辑文件系统通过文件控制块(FCB)来维护文件结构
在磁盘上,文件系统可能包括如下信息:如何启动所存储的操作系统、总的块数、空闲块的数目和位置、目录结构以及各个具体文件等
磁盘结构包括

  • 引导控制块(boot control block):包括系统从该分区引导操作系统所需的信息,通常为分区的第一块
  • 分区控制块(partition control block):包括分区详细信息,如分区的块数、块的大小、空闲块的数量和指针、空闲FCB的数量和指针等
  • 目录结构(directory structure):用来组织文件
  • 文件控制块(FCB):包括很多文件信息,如文件许可、 拥有者、大小和数据块的位置等

内存信息用于文件系统管理和提高性能,包括

  • 内存分区表:包括所有安装分区的信息
  • 内存目录结构:保存近来访问过的目录信息
  • 系统范围的打开文件表:包括每个打开文件的FCB拷贝和其他信息
  • 单个进程的打开文件表:包括一个指向系统范围内已打开文件表中合适条目的指针和其他信息

创建文件:

  1. 引用程序调用逻辑文件系统
  2. 逻辑文件系统分配一个新的FCB
  3. 把相应目录读入内存
  4. 增加一个新的目录项
  5. 用新的文件名更新该目录和FCB
  6. 将结果写回磁盘

打开文件:

  1. 调用open将文件名传给文件系统
  2. 当文件打开时,根据给定文件名来搜索目录结构
  3. 将文件的FCB读入内存
  4. 其FCB复制到系统范围的打开文件表
  5. 在单个进程的打开文件表中会增加一个条目,并通过指针将系统范围的打开文件表的条目同其他域相连
  6. 调用open返回一个指向单个进程的打开文件表中合适条目的指针

关闭文件:

  1. 删除一个相应的单个进程打开文件表的条目
  2. 系统范围内打开文件表的打开数也会递减
  3. 当打开文件的所有用户都关闭一个文件时,更新的文件信息会复制到磁盘的目录结构中,系统范围的打开文件表的条目也将删除

VFS:虚拟文件系统,可以支持多个类型文件系统
26

磁盘空间分配方法

  • 连续分配(contiguous allocation)
  • 链接分配(linked allocation)
  • 索引分配(indexed allocation)

连续分配:每个文件占据磁盘上的一组连续的块
27
特点:简单,只需要记录文件的起始位置(块号)及长度。访问文件很容易,所需的寻道时间也最少
存在的问题:为新文件找空间比较困难(类似于内存分配中的连续内存分配方式),文件很难增长
修正的连续分配方法:开始分配一块连续空间,当空间不够时,另一块被称为扩展的连续空间会添加到原来的分配中,文件块的位置是开始地址、块数、加指向下一个扩展的指针

链接分配:每个文件是磁盘块的链表,磁盘块分布在磁盘的任何地方
28
优点:简单,只需起始位置;文件创建与增长容易
缺点:不能随机访问;块与块之间的链接指针需要占用空间;存在可靠性问题
每个分区的开始部分用于存储FAT表,每个磁盘块在该表中有一项,该表可以通过块号来索引,目录条目中含有文件首块的块号码,根据块号码索引的FAT条目包含文件下一块的号码,这种链会一直继续到最后一块,该块对应FAT条目的值为文件结束值。未使用的块用0值来表示,为文件分配一个新的块只要简单地找到第一个值为0的FAT条目,用新块的地址替换前面文件结束值,用文件结束值代替0

索引分配:将所有的数据块指针集中到索引块中,索引块中的第i个条目指向文件的第i块,目录条目包括索引块的地址,unix使用索引分配
29

为了记录空闲磁盘空间,系统需要维护一个空闲空间链表。空闲空间链表记录了所有空闲磁盘空间,即未分配给文件或目录的空间。当创建文件时,搜索空闲空间链表以得到所需要的空间,并分配给新文件。这些空间会从空闲空间链表中删除
空闲空间管理的四种方法

  • bit vector
  • linked list
  • grouping
  • counting

I/O系统

端口(port):设备通过连接点与机器通信
总线(bus):一组线和一组严格定义的可以描述在线上传输信息的协议
控制器(controller):用于操作端口、总线或设备的一组电子器件
30
控制器有一个或多个用于数据和控制信号的寄存器。处理器通过读写这些寄存器的位组合来与控制器通信
设备控制寄存器映射到处理器的地址空间。处理器执行I/O请求是通过标准数据传输指令来完成对设备控制器的读写
I/O控制器有四种寄存器

  • 状态寄存器(status register):包含一些主机可读取的位信息,这些信息指示各种状态如当前任务是否完成,数据输入寄存器中是否有数据可以读取,是否出现设备故障等
  • 控制寄存器(control register):可以被主机用来向设备发送命令或改变设备状态
  • 输入寄存器(data-in register):主机用来获取输入
  • 输出寄存器(data-out register):主机输出

轮询(polling):有两个位,忙位和就绪位

  1. 主机不断地读取忙位,直到该位被清除 (这个过程称为轮询,亦称忙等待-busy waiting)
  2. 主机设置命令寄存器中的写位并向数据输出寄存器中写入一个字节
  3. 主机设置命令就绪位
  4. 当控制器注意到命令就绪位已被设置,则设置忙位。
  5. 控制器读取命令寄存器,并看到写入命令。它从数据输出寄存器中读取一个字节,并向设备执行I/O操作。
  6. 控制器清除命令就绪位,清除状态寄存器的故障位以表示设备I/O成功,清除忙位以表示完成

CPU硬件有一条中断请求线(interrupt-request line,IRL),由I/O设备触发,设备控制器通过中断请求线发送信号而引起中断,CPU捕获中断并派遣到中断处理程序,中断处理程序通过处理设备来清除中断
两种中断请求

  • 非屏蔽中断(nonmaskable interrupt):主要用来处理不可恢复内存错误等事件
  • 可屏蔽中断(maskable interrupt):由CPU在执行关键的不可中断的指令序列前加以屏蔽

中断优先级:能够使CPU延迟处理低优先级中断而不屏蔽所有中断,这也可以让高优先级中断抢占低优先级中断处理
中断的用途

  • 用于处理各种异常
  • 系统调用的实现需要用到中断
  • 中断也可以用来管理内核的控制流

对于需要大量传输的设备,例如磁盘驱动器,如果使用昂贵的通用处理器来观察状态位并按字节来向控制器送入数据(Programming I/O,PIO),那么就浪费了。许多计算机为了避免用PIO而增加CPU的负担,将一部分任务下放给一个专用处理器,这称为DMA(direct-memory access)控制器
在开始DMA传输时,主机向内存中写入DMA命令块。该块包括传输的源地址指针、传输的目的地址指针、传输的字节数。CPU在将该命令块的地址写入到DMA控制器中后,就继续其他工作。DMA控制器则继续去直接操作内存总线,无需主CPU的帮助即可以将地址放到总线以开始传输
DMA控制器与设备控制器之间的握手通过一对称为DMA-request和DMA-acknowledge的线来进行。当有数据需要传输时,设备控制器就通过DMA-request线发送信号。该信号会导致DMA控制器抓住内存总线,并在内存总线上放上所需地址,并通过DMA-acknowledge线发送信号。当设备控制器收到DMA-acknowledge信号时,就可以向内存传输数据,并清除DMA-request请求信号
31
I/O系统调用通用类型包装了设备行为,为应用程序隐藏了硬件差异
缓冲(buffer):用来保存在两设备之间或在设备和应用程序之间所传输数据的内存区域
采用缓冲的三个理由

  • 处理设备速度的差异
  • 处理设备传输大小的差异
  • 维护应用程序的拷贝语义(copy semantics)

高速缓存(cache):可以保留数据拷贝的高速内存
cache是为了弥补高速设备和低速设备的鸿沟而引入的中间层,最终起到加快访问速度的作用。而 buffer 的主要目的进行流量整形,把突发的大数量较小规模的 I/O 整理成平稳的小数量较大规模的 I/O,以减少响应次数

假脱机(SPOOL):用来保存设备输出的缓冲,这些设备如打印机不能接收交叉的数据流
设备预留(device reservation):为某进程保留该设备的使用权,在该进程获得运行之前,其他申请该设备的进程将得不到使用权

保护

操作系统中的进程必须保护加以保护,使其免受其他进程活动的干扰。确保只有从操作系统中获得了恰当授权的进程才可以操作相应的文件、内存段、处理器和其他资源。
保护(protection):一种控制程序、进程或用户对计算机系统资源的访问的机制
need to know principle:在任何时候,进程只能访问完成现阶段的任务所需要的资源
保护域:一个访问权限的集合,每个访问权限是一个有序对<对象名,权利集合>
可以将保护模型抽象为一个矩阵,称之为访问矩阵。矩阵的行代表域,矩阵的列代表对象。访问条目(i,j)定义了在域Di中执行的进程在对象Oj上可以调用的操作的集合

0%