计算机操作系统

绪论

操作系统是裸机上的第一层软件，是对硬件功能的首次扩充，引入操作系统的目的
- 提供一个用户与计算机硬件系统之间的接口，使计算机更易于使用
- 有效地控制和管理计算机系统中的各种硬件和软件资源，使之得到更有效的利用
- 合理地组织计算机系统的工作流程，以改善系统性能
操作系统的概念：操作系统是一组控制和管理计算机硬件和软件资源，合理地组织计算机工作流程以及方便用户的程序的集合
- 用户观点：根据用户所使用计算机的不同而设计不同类型的操作系统
- 系统观点：资源管理观点，操作系统是计算机系统的资源管理程序
- 进程观点：由若干个可以独立运行的程序和一个对这些程序进行协调的核心所组成的
- 虚拟机观点：机器扩充的观点，计算机被扩充为功能更强大、使用更加方便的虚拟计算机
操作系统的特征：并发性和共享性是操作系统最基本的的特征
- 并发性：两个或多个事件在同一时间间隔内发生，并行性指两个或多个事件在同一时刻发生。并发性通过分时实现
- 共享性：系统中的硬件和软件资源不为某个程序所独占，而供多个用户共同使用，分互斥共享和同时访问
- 虚拟性：多道程序设计技术
- 异步性：多道程序中何时执行、执行顺序和所需时间都是不确定、不可预知的
基本功能
- 处理器管理：进程控制，进程同步，进程通信，进程调度
- 存储器管理：内存分配，内存保护，内存扩充
- 设备管理：设备分配，设备传输控制，设备独立性
- 文件管理：文件存储空间的管理，目录管理，文件操作管理，文件保护
- 用户接口：命令接口，程序接口（系统调用），图形接口
  - 联机命令接口又称交互式命令接口，用于分时或实时操作系统
  - 脱机命令接口又称批处理命令接口，用于批处理系统
形成与发展
- 无操作系统阶段：手工操作，脱机输入/输出技术
- 单道批处理系统：自动性，顺序性，单道性
- 多道批处理系统：多道，宏观上并行，微观上串行
- 操作系统：增设一组软件解决处理器、内存空间、I/O 设备的分配和程序、数据、作业的组织
分类
- 批处理操作系统：作业就是用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合，包括用户程序、所需的数据及命令等
  - 单道批处理系统：大大提高机器利用率，减少了人工操作的时间，但 I/O 速度慢时 CPU 利用率低
  - 多道批处理系统：引入多道程序设计技术。用户脱机使用计算机，成批处理，多道程序运行
- 分时操作系统：时间片轮转
  - 简单分时操作系统，具有前台和后台的分时操作系统，多道分时操作系统
  - 多路性，交互性，独占性，及时性
- 实时操作系统：以足够快的速度进行处理，并在被控制对象允许的时间范围内做出快速反应
  - 实时控制系统，实时信息处理系统
  - 提供及时响应和高可靠性
- 其他操作系统：
  - 嵌入式操作系统：运行在嵌入式系统环境中，支持嵌入式软件的运行
  - 集群系统：Clustered System，共享存储并通过 LAN 网络紧密连接，来提供高可用性
  - 网络操作系统：通过通信设施连接多个分散自治的计算机系统，实现信息交换、资源共享、可互操作和协作处理。基于计算机网络
  - 分布式操作系统：多个分散的处理单元经互联网连接，既高度自治，又相互协同
    - 统一性，共享性，透明性，自治性
    - 分布式，成本低；可靠性
运行环境
- 核心态、管态、系统态：能执行包括特权指令的一切指令，能访问所有寄存器和存储区
- 用户态、目态：只能执行规定的指令，访问制定的寄存器和存储区
- 用户态程序通过执行访问核心态的命令，引起中断，由中断系统转入操作系统内的相应程序
- 特权指令：只能由操作系统内核部分使用，不允许用户直接使用的指令，如 I/O 指令、设置中断屏蔽指令、清内存指令、存储保护指令和设置时钟指令、访问 PSW 或其他特殊寄存器
- 操作系统的内核：一些与硬件关联较紧密的模块以及运行频率较高的程序
  - 时钟管理：提供标准系统时间和实现进程的切换（时间片轮转调度）
  - 中断机制：中断的一部分，负责保护和恢复中断现场的信息，转移控制权到相关的处理程序。减少中断的处理时间，提高系统并行处理的能力
  - 原语：一些关闭中断的共用小程序。处于操作系统最底层，是最接近硬件的部分；程序运行具有原子性，操作只能一气呵成；运行时间较短，调用频繁
  - 系统控制的数据结构及处理：登记状态信息的数据结构及定义对这些数据结构的一系列操作
- 转向内核态的例子：系统调用，中断，用户程序错误，用户程序企图执行特权指令
- 中断，外中断，是系统正常功能的一部分，CPU 以外，I/O 中断、时钟中断。异常，内中断，由错误引起，CPU 内部，非法操作码、除零、地址越界、算术溢出、陷入指令，异常不能被屏蔽。通常异常会引起中断，中断未必是异常引起的
- 系统调用是应用程序同系统之间的接口，为程序接口或应用编程接口(API)。首先准备并传递系统调用的参数，通过陷入指令 trap 进入内核，此时由用户态进入内核态；执行相应的系统调用函数后将处理结果返回给用户进程，此时从内核态返回用户态
  - 设备管理，文件管理，进程控制，进程通信，内存管理

体系结构	优点	缺点
模块组合结构	结构紧密，接口简单直接，系统的效率相对较高	系统结构不清晰，可扩展性差，可适应性差
层次结构	组织和依赖关系清晰明了，可读性、可适应性和可靠性都得到了增强，便于修改和扩充	需要考虑如何有效分层
微内核结构，C/S 模式	可靠性好，灵活性好，便于维护，适合分布式处理环境	效率不高

进程管理

进程与线程

进程是资源分配的基本单位，也是独立运行的基本单位
程序的顺序执行：顺序性，封闭性，可再现性
程序的并发执行：间断性，失去封闭性，不可再现性
进程的特征：动态性，并发性，独立性，异步性，结构特征（程序段，数据段和一个 PCB）
进程和程序的关系
- 进程是动态的，程序是静止的。进程是程序的执行
- 进程是暂时的，程序是永久的
- 组成不同
- 多次执行，程序可产生多个不同进程；通过调用，一个进程可执行多个程序
- 进程可以创建其他进程，程序不能形成新的程序
- 进程具有并行特性（独立性、异步性），程序则没有
进程映像：程序段、数据段、PCB 构成的进程实体，是静态的
组织方式：链接方式，索引方式
进程和作业的区别
- 作业是用户向计算机提交任务的任务实体，经过提交、收容、执行、完成四个阶段。进程是已提交完毕作业的执行过程，是向系统申请分配资源的基本单位
- 一个作业至少由一个进程组成，一个进程不能构成多个作业
- 作业主要用于批处理系统，分时系统则没有作业的概念；进程几乎用在所有的多道程序系统中
PCB，Process Control Block，是进城存在的唯一标志：进程标识符 PID，进程当前状态，进程队列指针，程序和数据地址，进程优先级，CPU 现场保护区，通信信息，家族联系(进程家族树)，占有资源清单
- 作用：使程序能独立运行，保证程序的并发执行
- 唯一标志：创建和撤销进程实际是创建和撤销 PCB，系统总是通过 PCB 对进程进行控制的
进程的状态与转换：创建状态，就绪状态，运行状态，阻塞状态(等待状态)，结束状态
- 进程创建：用户登录，作业调度，请求系统提供服务，用户程序的应用请求(如启动程序执行)。创建原语：申请 PCB，指定 PID，分配资源，初始化 PCB，将 PCB 插入就绪队列
- 进程撤销：正常结束，异常结束，外界干预。撤销原语：停止执行，如有要求还要撤销子孙进程，回收资源归还给父进程或系统，回收 PCB
- 阻塞原语 P：block 执行状态 → 阻塞状态，主动行为。停止运行，保存现场，插入等待队列，转到进程调度
- 唤醒原语 V：wakeup 阻塞状态 → 就绪状态，被动行为。移出等待队列，插入就绪队列
- 进程切换：保存现场，更新 PCB，移入相应队列，选择另一个进程执行并更新 PCB，更新内存管理的数据结构，恢复现场
线程是进程内一个相对独立的、可调度的执行单元，只拥有一点必不可少的资源，可与同属一个进程的其他线程共享进程拥有的全部资源。线程的引入…提高了程序并发执行的速度，进一步提高了系统吞吐量
- 内核级线程：依赖于内核，由操作系统内核完成创建和撤销工作。一个内核级线程由于 I/O 操作阻塞时，不会影响其他线程的运行。时间片分配的对象是线程
- 用户级线程：不依赖于内核，由应用程序利用线程库提供创建、同步、调度和管理线程的函数来控制。可用于不支持内核级线程的多进程操作系统，甚至单用户操作系统。当一个线程阻塞时，整个进程必须等待。时间片分配对象是进程，即无论有多少用户级线程在运行，都只分配一个时间片，为所有线程所共享
线程与进程的比较
- 线程是独立调度的基本单位，进程是拥有资源的基本单位
- 进程之间可以并发执行，同一进程内的多个线程之间也可以并发执行
- 创建、撤销、切换进程的时空开销远大于对进程的操作
- 同一进程内的多个线程共享进程的地址空间，线程间的同步和通信非常容易实现，甚至无需操作系统干预
- 各个线程拥有自己的栈空间，不允许共享
多线程模型（用户级线程和内核级线程的连接方式）：多对一，一对一，多对多
进程通信
- 低级进程通信方式：互斥和同步，P、V 原语称为低级进程通信原语
- 高级进程通信方式：共享存储器系统(数据交换由用户自己安排读写指令完成)，消息传递系统(直接(消息缓冲队列)、间接(信箱，电子邮件系统))， 管道通信系统(共享文件，半双工，管道中的数据被读取后会被马上丢弃)

处理器调度

三级调度
- 高级调度：宏观调度、作业调度、长程调度
  - 选择一个或多个外存上处于后备状态的作业，分配内存、I/O 设备等必要资源并建立相应的进程
  - 运行频率较低，通常几分钟一次
- 中级调度：中程调度、内存调度、交换调度
  - 将处于外存对换区中的具备运行条件的进程调入内存，修改为就绪状态，挂在就绪队列上等待
  - 将处于内存中的暂时不能运行的进程交换到外存对换区，修改为挂起状态
- 低级调度：微观调度、进程调度、短程调度
  - 从就绪队列选取队列分配处理区，运行频率很高，几十毫秒一次，最基本的调度
性能指标
- CPU 利用率
- 系统吞吐量：单位时间 CPU 完成作业的数量
- 响应时间：用户提交请求到系统首次产生响应所用的时间
- 周转时间=完成时间-提交时间=等待时间+执行时间
- 带权周转时间=周转时间/运行时间，必定 ≥1
- 平均周转时间，平均带权周转时间
进程调度
- 功能
  - 记录系统中所有进程的有关情况以及状态特征
  - 选择获得处理器的进程
  - 处理器分配
- 引起原因：正常或异常结束，进入阻塞态，执行完系统调用等系统程序后返回用户进程，高优先级抢占，分时系统中时间片用完
- 不能进行进程调度的情况：处理中断，在操作系统内核程序临界区，其他需要完全屏蔽中断的原子操作
- 挂起态：暂时调到外存等待的状态，分为就绪挂起和阻塞挂起
- 调度方式(指有更高优先级进程就绪时)：抢占式(可剥夺方式)、非抢占式(不可剥夺方式)
调度算法
- 先来先服务 FCFS：用于作业调度和进程调度，非抢占式。公平，利长不利短
- 短作业优先 SJF：用于作业调度和进程调度(短进程优先)，不利于长作业，饥饿，非抢占式。抢占版本：剩余最短时间优先算法
- 优先级：用于作业调度和进程调度，非抢占式和抢占式，饥饿
  - 静态优先级：按执行周期长短(按进程类，按作业的资源要求，按用户类型和要求)
  - 动态优先级：根据进程占有 CPU 时间的长短，根据就绪进程等待 CPU 时间的长短
  - 优先级相同是，按 FCFS 或 SJF 的顺序执行
- 时间片轮转 RR：用于进程调度，时间片大小.. 系统的响应时间，就绪队列中的进程数目，系统的处理能力，抢占式
- 高响应比优先：用于作业调度，响应比=作业响应时间(等待时间+估计运行时间)/估计运行时间。有利于短作业，同时考虑长作业。增加了系统开销，不会饥饿，非抢占式
- 多级队列：用于进程调度，不同的队列采用不同的调度算法
- 多级反馈队列：用于进程调度，优先级和时间片轮转的结合。
  - 设置多个优先级不同的就绪队列，优先级越高，时间片越短
  - 在每个队列依次运行一个时间片后转入下一级队列，最后一个队列使用时间片轮转调度算法
  - 当优先级更高队列全空时才调度该队列中进程运行。若有更高优先级进程到达，抢占式。饥饿

同步与互斥

临界资源：同时仅允许一个进程使用的资源。进入区，临界区(进程代码，打开文件等)，退出区，剩余区
- 进程处于临界区的时候也可以进行处理器调度（到其他与该类进程无关的进程）
互斥：空闲让进，忙则等待，有限等待，让权等待
- 软件：单标志，双标志先检查，双标志后检查，皮特森算法
  - flag[]，turn，存在忙等现象
- 硬件：中断屏蔽，硬件指令。不能实现让权等待
- 硬件方法如 Swap 指令、TestAndSet 指令不能实现让权等待，可能导致饥饿。peterson 算法满足有限等待(解决饥饿)但不满足让权等待，记录型信号量由于引入阻塞机制，消除了不让权等待的情况
同步：多个相互合作的进程在一些关键点上需要互相等待或互相交换信息
- 互斥其实是同步的一种特殊情况，也是为了达到让进程之间协调推进的目的
信号量是一个确定的二元组(s,q)，s 是一个具有非负初值的整型变量，q 是一个初始状态为空的队列。s 表示系统中某类资源的数目，大于 0 时表示可用资源数目，小于 0 时表示因申请该类资源而被阻塞的进程数目
- 除信号量的初值外，信号量的值只能由 P 操作(wait)和 V 操作(signal)改变
  - P(s): s–; if(s<0) 阻塞该进程并插入等待队列;
  - V(s): s++; if(s≤0) 从等待队列中移出第一个进程，变为就绪态并插入就绪队列;
- P、V 操作均为不可分割的原子操作，一定成对出现，但可以分布在不同进程中
- 分类
  - 整型信号量：存在忙等现象，未遵循让权等待准则
  - 记录型信号量（资源信号量）：添加了链表结构用于链接所有等待该资源的进程。P 操作时若无资源可用，进程自我阻塞，放弃处理器并插入等待链表中，遵循了让权等待准则。
  - AND 型信号量，信号量集…
- 应用
  - 同步：要求 A 在 B 之前执行，A;V(N);...P(N);B;先后 V，后前 P（先 VP 后）
  - 互斥：P(N);临界区1;V(N);...P(N);临界区2;V(N);
- P、V 原语操作是低级通信机制，通过共享变量实现信息传递。高级通信机制是由系统提供发送(send)和接收(receive)两个操作，进程间通过这两个操作进行通信，无需共享任何变量

生产者-消费者问题

Semaphore full=0;    //满缓冲区数目
Semaphore empty=n;   //空缓冲区数目
Semaphore mutex=1;   //互斥信号量
Producer(){
  while(true){
    Produce();
    P(empty);
    P(mutex);
    In();
    V(mutex);
    V(full);
  }
}
Consumer(){
  while(true){
    P(full);
    P(mutex);
    Out();
    V(mutex);
    V(empty);
    Consume();
  }
}
/*P(full)/P(empty)和P(mutex)的顺序不可颠倒，否则导致死锁，V可以颠倒
mutex在单生产者单消费者的情况下可以去掉，只要有多个同类进程就一定需要互斥信号量*/

读者写者问题

读者优先

semaphore rmutex=1;//互斥访问readcount
semaphore mutex=1;
int readcount=0;
reader(){
  while(true){
    P(rmutex);
    if(readcount==0) P(mutex);
    readcount++;
    V(rmutex);
    read();
    P(rmutex);
    readcount--;
    if(readcount==0) V(mutex);
    V(rmutex);
  }
}
writer(){
  while(true){
    P(mutex);
    write;
    V(mutex);
  }
}

公平情况，顺序执行

semaphore rmutex=1;
semaphore wmutex=1;//写者存在时禁止新读者进入以及写者互斥
semaphore mutex=1;
int readcount=0;
reader(){
  while(true){
    P(wmutex);
    P(rmutex);
    if(readcount==0) P(mutex);
    readcount++;
    V(rmutex);
    V(wmutex);
    read();
    P(rmutex);
    readcount--;
    if(readcount==0) V(mutex);
    V(rmutex);
  }
}
writer(){
  while(true){
    P(wmutex);
    P(mutex);
    write;
    V(mutex);
    V(wmutex);
  }
}

写者优先

semaphore rmutex=1;
semaphore wmutex=1;
semaphore mutex=1;
semaphore readable=1;//表示当前是否有写者
int readcount=0,writecount=0;
reader(){
  while(true){
    P(readable);
    P(rmutex);
    if(readcount==0) P(mutex);
    readcount++;
    V(rmutex);
    V(readable);
    read();
    P(rmutex);
    readcount--;
    if(readcount==0) V(mutex);
    V(rmutex);
  }
}
writer(){
  while(true){
    P(wmutex);
    if(writecount==0) P(readable);
    writecount++;
    V(wmutex);
    P(mutex);
    write;
    V(mutex);
    P(wmutex);
    writecount--;
    if(writecount==0) V(readable);
    V(wmutex);
  }
}

哲学家进餐问题—并发进程处理临界资源

semaphore Fork[5]={1,1,1,1,1};
philosopher(int i){//i=1,2,3,4,5
	while(true){
    think();
    hungry();
    P(Fork[i%5]);
    P(Fork[(i+1)%5]);
    eat();
    V(Fork[i%5]);
    V(Fork[(i+1)%5]);
  }
}
/*会导致死锁，解决1.最多允许4个哲学家同时进餐2.仅当左右筷子同时可用时才可以拿起筷子
3.编号，奇数号哲学家先拿左边筷子，偶数号哲学家先拿右边筷子*/
philosopher(int i){
  while(true){
    think();
    hungry();
    if(i%2!=0){
    	P(Fork[i%5]);
    	P(Fork[(i+1)%5]);
    	eat();
    	V(Fork[i%5]);
    	V(Fork[(i+1)%5]);
    }
    else{
    	P(Fork[(i+1)%5]);
    	P(Fork[i%5]);
    	eat();
    	V(Fork[(i+1)%5]);
    	V(Fork[i%5]);
    }
  }
}

理发师问题：没有顾客则理发师睡觉；第一个顾客叫醒理发师；正在理发有空凳子则等待；没有空凳子则离开

//第一种：将理发椅和等待用的凳子看做两种不同的资源
int waiting=0;
semaphore mutex=1;
semaphore bchair=1;
semaphore wchair=n;
semaphore ready=finish=0;
barber(){
  while(true){
    P(ready);
    cut();
    V(finish);
  }
}
customer(){
    P(mutex);
    if(waiting<=n){waiting++;V(mutex);}
    else{V(mutex);leave();}
    P(wchair);
    P(bchair);
    V(wchair);
    V(ready);
    P(finish);
    V(bchair);
    P(mutex);
    waiting--;
    V(mutex);
}
//第二种：统一理发椅和凳子
int chairs=n+1;
semaphore ready=0;
semaphore finish=1;
semaphore mutex=1;
barber(){
  while(true){
    P(ready);
    cut();
    P(mutex);
    chairs++;
    V(mutex);
    V(finish);
  }
}
customer(){
  P(mutex);
  if(chairs>0){
    chairs--;
    V(mutex);
    V(ready);
    P(finish);
  }
  else{
    leave();
    V(mutex);
  }
}

管程定义了一个数据结构和能为并发进程所执行的一组操作组成的软件模块，能同步进程和改变管程中的数据
- 组成：局部于管程的共享数据结构说明，操作这些数据结构的一组过程，设置初值的语句
- 把分散在各个进程中互斥访问公共变量的临界区集中起来，提供保护
- 特征
  - 局部于管程的数据只能被局部于管程内的过程所访问
  - 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
  - 每次仅允许一个进程在管程内执行某个内部过程，即进程互斥地通过调用内部过程进入管程
- 由于管程是一个语言成分，管程的互斥访问由编译程序在编译时自动添加，且保证正确
- 管程中还应包含若干用于支持同步的设施
  - 局限于管程并仅能从管程内进行访问的若干条件变量，用于区别各种不同的等待原因
  - 在条件变量上进行操作的两个函数过程 wait 和 signal。signal 必须在 wait 之后
  - 条件变量用于实现进程同步，管程内进程执行 x.wait()操作，则进程阻塞，并挂到条件变量 x 的阻塞队列上，然后释放管程使用权，另一个进程进入管程。执行 x.signal()操作后唤醒 x 对应的阻塞队列队头进程。Pascal 语言的管程中规定只有一个进程要离开管程时才能调用 signal()操作

死锁

参与死锁的进程至少有两个，每个参与死锁的进程均等待资源，参与死锁的进程中至少有两个进程占有资源，死锁进程是系统中当前进程集合的一个子集
资源分类：可剥夺资源，不可剥夺资源。完全取决于资源本身的性质
死锁产生的原因：系统资源不足（根本原因）和进程推进顺序不当（重要原因）
预防死锁：破坏死锁的必要条件
- 互斥条件：允许多个进程同时访问资源（受到资源本身固有特性的限制，一般不太可能）
- 不剥夺条件：通常不用于剥夺资源后代价较大的场合，如打印机的分配
- 请求与保持条件：预先静态分配方法（一次性申请所需要的全部资源，未满足前不分配），资源不能充分利用，且会导致饥饿
- 环路(循环)等待条件：有序资源分配法（给资源编号，每一个进程都按照编号递增的次序请求资源，同类资源一次申请完），限制了新设备的增加、造成资源浪费、增加程序编写的复杂性
避免死锁
- 系统能按某种顺序为每个进程分配所需的资源直至最大需求，每个进程都可顺利完成，称为安全状态，该序列为安全序列。不存在安全序列的状态称为不安全状态。安全序列可能不唯一
- 安全性检测是根据进程最大资源需求而定，故安全状态一定不会发生死锁，不安全状态不一定发生死锁。死锁是不安全状态的真子集
- 银行家算法中的数据结构：假定有 n 个进程，m 类资源
  - 可利用资源向量 Available。这是一个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果 Available[j]=K，则表示系统中现有 R~j~类资源 K 个
  - 最大需求矩阵 Max。这是一个 n×m 的矩阵，它定义了系统中 n 个进程中的每一个进程对 m 类资源的最大需求。如果 Max[i,j]=K，则表示进程 i 需要 R~j~类资源的最大数目为 K
  - 分配矩阵 Allocation。这也是一个 n×m 的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 Allocation[i,j]=K，则表示进程 i 当前已分得 R~j~类资源的数目为 K
  - 需求矩阵 Need。这也是一个 n×m 的矩阵，用以表示每一个进程尚需的各类资源数。如果 Need[i,j]=K，则表示进程 i 还需要 R~j~类资源 K 个，方能完成其任务
  - 上述三个矩阵间存在下述关系：Need[i, j] = Max[i, j] - Allocation[i, j]
- 银行家算法：设 Request~i~是进程 P~i~的请求向量，如果 Request~i~[j]=K，表示进程 P~i~需要 K 个 R~j~类型的资源
  - Request~i~[j]<=Need[i, j]。否则认为出错，因为它所需要的资源数已超过它所宣布的最大值
  - 如果 Request~i~[j]<=Available[j]。否则表示尚无足够资源，P~i~须等待
  - 系统试探着把资源分配给进程 P~i~，并修改下面数据结构中的数值
    - Available[j] -= Request~i~[j]
    - Allocation[i, j] += Request~i~[j]
    - Need[i, j] -= Request~i~[j]
  - 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全才正式将资源分配给进程 P~i~，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程 P~i~等待。
- 安全性算法
  - Work 表示系统可提供给进程继续运行所需的各类资源数目，含有 m 个元素，Work=Available；Finish 表示系统是否有足够的资源分配给进程，使之运行完成，Finish[i]=false。当有足够资源分配给进程时，再令 Finish[i]=true
  - 从进程集合中找到一个能满足下述条件的进程：Finish[i]=false；Need[i, j]<=Work[j]；
    - 若找到：当进程 P~i~获得资源后，可顺利执行，直至完成，并释放出分配给它的资源：Work[j] += Allocation[i, j]；Finish[i] =true；重复查找直到没有满足条件的进程
    - 如果所有进程的 Finish[j]=true 都满足，则表示系统处于安全状态；否则，系统处于不安全状态
  - 时间复杂度 O(m*n^2^)
死锁检测
- 资源分配图(System Resource Allocation Graph)有向图。用长方形（或用圆圈）代表一个进程，用方框代表一类资源。由于一种类型的资源可能有多个，用框中的一个点代表一类资源中的一个资源。从进程到资源的有向边叫申请边，表示该进程申请一个单位的该类资源；从资源到进程的边叫分配边，表示该类资源已经有一个资源被分配给了该进程。
- 死锁定理：不同的简化顺序将得到相同的不可简化图(资源分配图消边后得到系统状态图)。系统状态 S 为死锁状态的条件是：当且仅当 S 状态的资源分配图是不可完全简化的
死锁检测算法
- Available 当前可用资源向量，Allocation 已分配资源矩阵，Request 进程请求资源矩阵，work，finish
- 依次找到请求数小于可用数的进程，分配运行并释放资源。若一组进程中有几个不属于序列，则发生死锁
- 检测死锁可以在每次分配资源后进行，由于检测时间长，系统开销大，也可以选取较长的时间间隔来执行
死锁解除：剥夺资源，撤销进程，进程回退（要求系统保留历史信息，设置还原点）
死锁，饥饿，饿死
- 饿死指饥饿到一定程度，进程赋予的任务即使完成也不再具有实际意义
- 活锁：忙等条件下发生的饥饿，如不公平的互斥算法
- 饿死与死锁都是由竞争资源引起的
  - 死锁进程都处于等待状态；忙等进程并非处于等待状态（运行或就绪），但可能被饿死
  - 死锁进程等待的资源永远不会被释放；饿死进程等待的资源会被释放但不会被分配，等待时间无上界
  - 死锁一定发生了循环等待，饿死则不然
  - 死锁一定涉及了多个进程，饥饿或饿死可能只有一个
- 饥饿与饿死与资源分配策略有关，可从公平性方面考虑防止饥饿与饿死，如多级反馈队列调度算法

内存管理

内存管理主要任务是为多道程序的运行提供良好的环境，方便用户使用存储器，提高存储器的利用率以及从逻辑上扩充存储器。应具有的功能：内存的分配和回收，地址变换，扩充内存，存储保护
应用程序从源文件到内存中执行的过程：源程序.c 经过编译程序 compiler 编译为若干个目标模块 object module 有各自的逻辑空间，与包含.h 的库模块一起由链接程序形成具有完整的逻辑地址空间的装入模块，由装入程序装入内存
- 源程序(名地址)→ 链接 → 目标程序(逻辑地址)→ 装入 → 可执行程序(物理地址)
- 形成逻辑地址的阶段是链接，完成该变换过程的阶段是装载
- 通过链接程序 linker 将目标模块和库函数链接在一起形成完整的装入模块 load module
  - 静态链接，装入时动态链接，运行时动态链接
- 通过装入程序 loader 将装入模块装入内存并执行
  - 绝对装入：编译程序产生含有物理地址的目标代码，不适合多道程序设计
  - 可重定位装入：静态重定位，容易实现，无需增加硬件地址变换机构，要求为每个程序分配一个连续的存储区，程序执行期间不能移动，不能再申请内存空间，难以做到程序和数据的共享
  - 动态运行装入：动态重定位，依靠硬件地址变换机构，可以将程序分配到不连续的存储区中，在程序运行之前装入部分代码即可投入运行，可动态申请分配内存，便于程序段的共享，可以提供比主存空间大得多的地址空间。需要附加硬件支持，软件算法比较复杂
  - 重定位寄存器，存放进程分配的内存空间，也称为基址寄存器。整个系统一个，切换程序时更新
    - 物理地址=基址寄存器内容+逻辑地址
逻辑地址：由程序产生的与段相关(与页无关，因为只有段对用户可见)的偏移地址部分，也称为相对地址
物理地址：出现在 CPU 外部地址总线上的寻址物理内存的地址信号，是逻辑地址变换后的最终结果地址，物理地址空间是内存中物理地址单元的集合，对一般用户透明
从逻辑地址到物理地址的转换过程由硬件自动完成，称为地址重定位：逻辑地址 → 界地址寄存器 → 重定位寄存器 → 物理地址
内存保护：防止一个作业有意或无意地破坏操作系统或其他作业
- 界限寄存器：上、下界寄存器，基址和限长寄存器(也叫重定位寄存器和界地址寄存器)
- 存储保护键：给每个存储块及作业分配一个单独的保护键
覆盖：用户空间分固定区和覆盖区，常用段常驻内存，即将访问的段放在覆盖区
交换：磁盘分为文件区和对换区
PCB 会常驻内存，不会被换出
内部碎片：已经分配给作业但不能被利用的内存空间
外部碎片：系统中还没有分配给作业，但由于碎片太小而无法分配给申请内存空间的新进程的存储块

连续分配管理方式

单一连续分配：静态分配，适合单道程序，分系统区(通常在低地址部分)和用户区，可采用覆盖技术，管理简单；不支持虚拟存储器的实现，无法实现多道程序共享主存。会产生内部碎片
- 硬件：界地址寄存器，越界检查机构
固定分区分配：分区大小可以不等，但事先必须确定，在运行时不能改变。采用静态重定位方式装入。可用于多道程序系统最简单的存储分配，不能实现多进程共享一个主存区，利用率较低，会产生内部碎片
- 硬件(动态分配同)：上下界寄存器，越界检查机构，及地址寄存器，畅读寄存器
动态分区分配：又称可变式分区分配，进程装入内存时动态建立分区，分区的大小和数目都是可变的
- 常用数据结构：常用空间分区表，空闲分区链
- 分区分配算法：分配分区（按需分割），并修改空闲分区表/链
  - 首次适应算法 FF：邻近适应，空闲分区按地址递增次序成链，每次都从队首开始查找
    - 优先利用低地址空闲分区，保留高地址的大空闲分区，无内部碎片
    - 低地址留下许多难以利用的外部碎片，从头开始查找的开销增加
  - 下次适应算法 NF，循环首次适应算法：将 FF 中的队列改成循环队列，从上次结果开始查找
    - 使空闲分区分布更加均匀，减少了查找开销，平均性能比首次适应算法差
    - 导致缺乏大的空闲分区，碎片多出现于高地址空间
  - 最佳适应算法 BF：按容量大小递增排序
    - 总能分配最恰当的分区，并保留大的分区
    - 导致产生很多难以利用的小外部碎片，最容易产生碎片
  - 最差适应算法 WF：(最坏，最大)按容量大小递减
    - 使分给作业后剩下的空闲分区比较大，足以装入其他作业
    - 最大的空闲分区总是因首先分配而被划分，大作业的空间申请得不到满足
- 分区的回收：上邻接，下邻接，上下邻接，无邻接
- 分区分配的动态管理(分区重定位技术)：拼接技术(拼凑、紧缩)；动态重定位分区分配技术
- 优点：实现了多道程序共用主存，管理方案相对简单、不需要更多开销，实现存储保护的手段比较简单
- 缺点：主存利用不够充分，存在外部碎片；无法实现多进程共享存储器信息；无法实现主存的扩充，进程地址空间受实际存储空间的限制

离散分配管理方式

基本分页存储管理方式
- 作业的地址空间划分为若干大小相等的区域，称为页或页面；主存的存储空间也分成与页面大小相等的区域，称为块或物理块，也称为页框。分配存储空间时以块为单位，页面大小由机器的地址结构决定
  - 进程-页，主存-页框，外存-块，都是同样的大小
  - 小页面：页内碎片较小，提高内存利用率；使页表过长，占用较多内存，降低页面换入换出效率
  - 大页面：减少页表长度，提高页面换进换出效率，但会使页内碎片增大。一般选择 512B~4KB
- 逻辑地址：页号|页内偏移
- 页表，页表项=(页号+)块号，页表通常存放在内存中
- 基本地址变化机构：硬件自动完成
  - 页表寄存器PTR：存放页表在内存中的起始地址和页表的长度
  - 根据逻辑地址得到页号和页内偏移 → 判断页号合法性 → 页表项物理地址=页号*页表项长度+页表起始地址(页表项长度即块号位数)，取出块号 → 目的物理地址=块号*块大小+页内偏移
- 具有快表的地址变换机构
  - 快表：又称联想寄存器 TLB，具有并行查找功能的高速缓冲存储器，用以存放当前访问的若干页表项
- 两级页表：外层页号|外层页内地址|页内地址…多级页表…需要多次访问内存，浪费时间
- 页的共享与保护
  - 共享：使共享用户地址空间中的页指向相同的物理块
  - 保护：地址越界保护，页表中的访问控制信息(如存取控制字段)
- 优点：内存利用率高，实现了离散分配，便于存储访问控制，无外部碎片
- 缺点：需要硬件支持(尤其是快表)，内存访问效率下降，共享困难，内部碎片
基本分段存储管理方式
- 方便编程，信息共享，信息保护
- 逻辑地址：段号|段内位移
- 段表项：(段号+)段长+内存起始地址
- 段表寄存器：存放段表始址和段表长度 TL
- 过程类似分页…
- 共享和保护
  - 不能修改的代码称为纯代码或可重入代码，这样的代码和不能修改的数据是可以共享的
  - 地址越界保护，访问控制保护。允许段动态增长的系统中，段内位移允许大于段长，因此还应设置相应增补位作为标志
- 优点：便于程序模块化处理和处理变换的数据结构，便于动态链接和共享，无内部碎片
- 缺点：需要硬件支持，为满足分段的动态增长和减少外部碎片要采用拼接技术，分段的最大尺寸受到主存可用空间的限制，有外部碎片
基本段页式存储管理方式
- 逻辑地址：段号|段内页号|页内位移，对主存的管理和分配以物理块为单位
- 一张段表，每个分段一张页表；段表寄存器：段表始址和长度
- 段表表项：段号、页表始址、页表长度；页表表项：页号、块号
- 页式平均内部碎片一个程序半页，段页式平均内部碎片比页式多
比较
- 分页通过硬件实现，页号和页内偏移透明；分段的段号和段内偏移由用户提供，可见，可由编译程序完成
- 逻辑地址：分页是一维，分段是二维
- 分页内部碎片，分段外部碎片
- 页面大小一致，段长大小不等

虚拟内存管理

前述方式都有一次性和驻留性，而虚拟内存有离散性、多次性、对换性(交换性)、虚拟性
- 部分装入，请求调入，置换功能，逻辑扩充
  - （❌）为了能让更多的作业同时运行，通常只装入 10%~30%的作业即启动运行
    - 是装入作业的一部分，而不是装入一部分作业
- 只能基于非连续分配技术
- 需要相当数量的外存，一定容量的内存，中断机构，地址变换机构，段表或页表
- 虚存的容量取决于地址空间的大小(CPU 寻址范围)，不是由实际的内存容量决定
请求分页存储管理方式
- 请求分页=基本分页+请求调页+页面置换
- 页表项：(页号)|物理块号|状态位P|访问字段A|修改位M|外存地址
- 缺页中断和地址变换
  - 硬件陷入内核，操作系统将缺页调入内存并更新页表，中断后返回产生缺页中断的指令重新执行
  - 在指令的执行期间产生和处理缺页中断
  - 一条指令可以产生多个缺页中断
  - 地址变换可能因为地址越界、缺页、访问权限错误而产生中断
- 每个进程拥有一张页表，且进程的页表驻留在内存中
- 优点：可以离散储存程序，降低了碎片数量；提供虚拟存储器，提高了主存利用率，有利于多道程序运行
- 缺点：需要硬件支持，有些情况下系统会产生抖动现象，程序最后一页仍存在未被利用的部分空间
- 基本分页调入全部页面，请求分页由请求调页机构调入部分页面，后续通过页面置换机构完成
页面置换算法/页面淘汰算法
- 最佳置换算法 OPT：(预知进程的页面号引用串)每次都淘汰以后不再使用或以后最迟再被使用的页面
  - 最优，拥有最低的缺页率。无法实现，只能作为衡量其他算法的标准
- 先进先出算法 FIFO：每次淘汰最先进入内存的页面，即驻留时间最长的页面
  - 实现简单；可能产生 Belady 异常(缺页次数随着分配的物理块数的增加而增加)
- 最近最少使用算法 LRU：用寄存器组和栈来实现，性能较好。最接近 OPT，每个页面设置一个访问字段，用来标识上次被访问到现在经历的时间
- 时钟置换算法 CLOCK/最近未使用算法 NRU：循环链表。访问置 1；循环选择，遇 1 置 0，遇 0 淘汰
- 改进型是种算法：访问位同为 0 的进程间优先淘汰没有修改过的页面，减少 I/O 次数，但增加扫描次数
  - 第一轮，不修改位，遇到的第一个(访问位=0，修改位=0)的页面用于替换
  - 第二轮，访问位置 1，寻找(0，1)。若仍然没有找到，重新执行第一轮和第二轮扫描
- 最不常用置换算法 LFU：为每页设置访问计数器。淘汰最小的页面，并将所有计数器清零
- 页面缓冲算法 PBA：FIFO 的发展，建立置换页面的缓冲(空闲页面链表/已修改页面链表)，减少 I/O 消耗
- 二次机会算法：FIFO 的基础上检查访问位，如果为 1 则给第二次机会
工作集是最近n 次内存访问的页面的集合，n 称为工作集窗口即大小（不是工作集所含元素的个数）
- 有空闲的物理块，则增加内存中进程数量以增加多道的程度；若工作集的大小总和超过了所有可用物理块的数量总和，可选择一个进程对换到磁盘中以防止抖动的发生
- 窗口选的过大，虽然进程不易缺页，但存储器也不会得到充分利用；窗口选的过小，会使进程在运行过程中频繁产生缺页中断，反而降低了系统吞吐率
驻留集：给一个进程分配的物理页框的集合
页面分配策略
- 固定分配局部置换：为每个进程分配固定数目的物理块，进程运行期间不会改变
  - 平均分配算法、按比例分配算法、考虑优先权的分配算法
- 可变分配全局置换：维护空闲物理块队列，缺页时分配，无空闲物理块则可能调出任何进程中一页
- 可变分配局部置换：根据缺页率动态调整分配给进程的物理块。较高内存空间利用率、较低缺页率
页面调入策略(时机)
- 请求调页策略：实现简单，但容易产生较多的缺页中断，时间开销大，容易产生抖动现象
- 预调页策略：基于局部性原理的预测，通常用于程序的首次调入
从何处调入页面：对换区连续分配，文件区离散分配，对换区 I/O 速度高
- 拥有足够的对换区空间：进程运行前将有关文件都复制到对换区
- 缺少足够的对换区空间：不会被修改的文件直接从文件区调入，可能被修改的部分换出时调到对换区
- UNIX 方式：UNIX 系统允许页面共享，进程请求的页面可能已被其他进程调入内存
抖动现象：刚淘汰的页面不久后又要访问，且调入不久后又调出，系统大部分时间都用在了页面的调入调出上(换页时间多于执行时间)，根本原因是在请求分页系统中的每个进程只能分配到所需全部内存空间的一部分
- 原因有对换的信息量过大、内存容量不足(主要原因)、置换算法选择不当
- 办法是降低交换页面的数量、加大内存容量、改变置换选择算法，其中可能的只有增加内存容量或降低进程数量，增加交换区容量不能解决物理内存不足的问题
Belady 异常：FIFO 算法的缺页率可能随着分配的物理块数的增加而增加
- 原因是 FIFO 算法的置换特征与进程访问内存的动态特征相矛盾，即被置换的页面并不是系统不会访问的
- LRU 算法和 OPT 算法不会出现 Belady 异常，被归类为堆栈算法的页面置换算法也不可能出现 Belady 异常
缺页率=调页次数/访问页面总次数。受置换算法、分配的页面数量、页面大小等因素影响
请求分段存数管理系统：段号|段长|内存始址|访问字段|修改位|状态位|外存地址…

内存管理方式之间的比较

	分页存储管理	分段存储管理	段页式存储管理
外部碎片	无	有	无
内部碎片	有	无	有
优点	内存利用率高，基本解决了内存零头问题	段拥有逻辑意义，便于共享、保护和动态链接	兼具
缺点	页缺乏逻辑意义，不能很好地满足用户	内存利用率不高，难以找到连续的空闲区放入整段	多访问一次内存

分页、分段、段页都需要特殊的硬件支持，分区是实现多道程序并发的简单易行且代价最小的方法
有效访问时间 EAT，Effective Access Time 指给定逻辑地址找到内存中对应物理地址单元中的数据所用总时间
- 基本分页
  - 没有快表：EAT=查找页表+访问内存单元=2t
  - 有快表：先访问快表，未命中再访存查找页表 EAT=a*b+(t+a)(1-b)+t
- 请求分页
  - 在快表中：EAT=查找快表+根据物理地址访存
  - 在主存中但不在快表中：EAT=查找快表+查找页表+修改快表+根据物理地址访存
  - 不在主存中，发生缺页：EAT=查找快表+查找页表+处理缺页+查找快表+根据物理地址访存
    - 缺页调入主存后，也要更新页表和快表

文件管理

文件的概念
- 数据项：最低级的数据组织形式。基本数据项(原子数据)，组合数据项
- 记录：一组相关的数据项的集合
- 文件：由创建者所定义的一组相关信息的集合，分为有结构文件(记录式文件)和无结构文件(流式文件)
- 记录是文件存取的基本单位，数据项是文件可使用的最小单位
文件的属性：名称，标识符(唯一，对用户透明)，文件类型，文件位置，大小、建立时间、用户标识等
文件的分类
- 按用途：系统文件(只允许调用，不允许读或修改)，库文件(允许调用和读，不允许修改)，用户文件(只能由文件所有者或所有者授权用户使用)
- 按保护级别：只读文件，读写文件，执行文件(允许核准用户调用执行，但不允许读写)，不保护文件
- 按信息流向：输入文件，输出文件，输入/输出文件
- 按数据形式：源文件，目标文件，可执行文件
文件的操作
- 创建、删除、读、写、截断、设置文件的读/写位置(重定位)
- 打开文件：使用系统调用 open，系统维护一个打开文件表 open-file table，将文件的属性从外存复制到内存，并设定一个编号或索引号(通常是一个指向打开文件表中一个条目的指针)返回
  - 避免了对文件的再次检索，既节约了检索开销，又提高了对文件的操作速度
  - 文件指针：上次读写位置，唯一，与磁盘文件属性分开保存
  - 文件打开计数：多个进程打开同一个文件时，再删除打开文件条目前要等待最后一个进程关闭文件
  - 文件磁盘位置：保存在内存中，避免每个操作都要读取磁盘
  - 访问权限：保存在进程的打开文件表中，以便允许或拒绝之后的 I/O 请求
- read 系统调用要求用户提供三个输入参数：文件描述符 fd，缓冲区首址 buf，传送的字节数 n
- open 中的参数包含文件的路径名与文件名，read 只需要使用 open 返回的文件描述符
- 关闭文件：将编号（或索引号）删除，并销毁其文件控制块，若有修改则需要将修改保存到外存
UNIX 常用系统调用
- 创建进程 fork(子进程继承父进程的环境、已打开的文件、根目录和当前目录等)，终止进程 exit(安排在子进程的末尾，完成后自我终止)，等待子进程结束 wait(用于将自身挂起，直至某一子进程终止)
- 创建文件 creat(根据文件名和许可权方式，创建新文件或重写一个已存文件)，打开文件 open(根据文件名搜索目录，将目录条目复制到打开文件表，并返回文件描述符 fd，打开后的任何操作只需使用 fd 而非路径名)，关闭文件 close(断开程序和文件之间建立的快捷通路)，读文件 read 和写文件 write(打开后才能调用)
逻辑结构又称文件组织，是用户可以直接处理的数据及其结构，物理结构是文件在外存上的存放组织形式
- 逻辑结构和存储设备的特性无关，物理结构和存储设备的特性关系很大
- 逻辑结构上，分为有结构的记录式文件和无结构的流式文件
  - 记录式文件通常有顺序、索引和索引顺序
- 物理结构上，文件的组织形式有连续分配、链接分配和索引分配

文件的逻辑结构

顺序结构，又称连续结构
- 按记录是否定长，分为定长记录顺序文件和变长记录顺序文件
- 按记录是否按关键字排序，分为串结构和顺序结构
- 优点是顺序存取时速度较快，定长记录文件可以随机访问
- 缺点是要求连续的存储空间，会产生碎片，也不利于文件的动态扩充
索引文件，为一个逻辑文件的信息建立一个索引表
- 索引表中的表目存放文件记录的长度和所在逻辑文件的起始位置，逻辑文件不再保存记录的长度信息
- 索引表本身是一个定长文件，每个逻辑块可以是变长的，索引表和逻辑文件两者构成了索引文件
- 优点是可以进行随机访问，也易于进行文件的增删
- 缺点是增加了存储空间的开销，其查找策略对文件系统的效率影响很大
索引顺序文件，为顺序文件建立索引表，为每组的第一个记录建立索引项，包含记录的关键字和指针
- 逻辑文件(主文件)是顺序文件，每个分组内部的关键字不必有序排列，但组与组之间的关键字有序排列
- 大大提高了顺序存取的速度，但仍然需要配置一个索引表，增加了存储开销
直接文件或散列文件，建立关键字和相应记录物理地址之间的对应关系
- 没有顺序的特性，有很高的存取速度，但会因散列值相同而引起冲突
适合随机存取的程度：连续分配>索引分配>链接分配

目录结构

文件目录是文件说明的集合，通常也作为一个文件来处理，称为目录文件，放在外存中
- 实现按名存取(最基本的功能)，提高检索速度，允许文件同名，允许文件共享
文件控制块 File Control Block，FCB：基本信息(如文件名，逻辑物理结构，物理位置等)，存取控制信息，管理信息(使用信息，如建立时间、修改时间)。FCB 就是文件目录项，在 create 时创建
索引结点：将文件描述信息和文件名分开，单独形成一个索引结点
- 磁盘索引结点：每个文件唯一，包括文件主标识符、文件类型、存取权限、物理地址(盘块编号)、长度(以字节为单位)、链接计数、存取时间
- 文件被打开时，磁盘索引结点复制到内存中，称为内存索引结点，增加了：索引结点编号、状态(上锁或被修改)、访问计数、逻辑设备号、链接指针
单级目录结构：整个文件系统中只建立一张目录表，文件名唯一，删除时先回收存储空间，再清除目录项
- 优点是易于实现，管理简单。缺点是不允许文件重名，文件查找速度慢
二级目录结构：分为主文件目录 Master File Directory 和用户文件目录 User File Directory
- 为每个用户建立一个单独的 UFD，表项登记用户建立的所有文件及其说明信息
- MFD 记录系统中各个用户文件目录的情况，每个用户占一个表目，包括用户名和相应 UFD 所在的存储位置
- 删除文件只需在 UFD 中删除该文件的目录项，若删除文件后用户目录表为空，则可将 MFD 中对应表项删除
- 可以解决文件重名问题，并获得较高的查找速度。但缺乏灵活性，特别在需要合作和访问其他文件时

多级目录结构，又称树形目录结构：树根为根目录，非叶子结点为目录文件(子目录)，叶子结点为文件

路径名：绝对路径，相对路径，\
当前目录，工作目录，..表示父目录
可以方便的对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护
查找文件需要按照路径名逐级访问中间结点，增加了磁盘访问次数，进而影响了查询速度

//孩子兄弟表示法
typedef struct CSNode{
  char name[MaxSize];          //名称
  int NodeType;                //0代表文件，1代表目录
  union p{                     //信息指针
    filepointer p1;            //文件信息
    catalogpointer p2;         //目录信息
  };
  struct CSNode *firstchild, *nextsibling;  //第一个孩子和右兄弟指针
}CSNode;

图形目录结构：增加指向同一结点的有向边，DAG，实现文件共享，但使系统的管理变得更复杂
为每个共享结点设置共享计数器，当计数值修改为 0 时才真正删除结点，否则只删除对应共享链
文件共享：节省大量外存空间和主存空间，减少输入/输出操作，为用户间的合作提供便利条件
- 动机：多用户操作系统用户间需要共享一些文件来共同完成任务；网络上不同的计算机之间通信需要远程文件系统的共享功能支持
- 硬链接，基于索引结点的共享方式
  - 树形结构的共享通过将各自文件的 FCB 设置为相同的物理地址实现，但新增的物理块不能被共享
  - 不同的目录项只需要指向相同的索引结点索引结点即可实现共享，一个共享文件只有一个索引结点
  - 在索引结点中增加一个计数值 count 来统计指向该索引结点的目录项的个数
  - 能够实现文件的异名共享，但当多个用户共享文件时，文件拥有着不能删除文件
- 软链接，又称符号链接，利用符号链实现文件共享
  - 创建一个称为链接的新目录项，包含被共享文件的路径名（绝对或相对）
  - 链接可以使用目录项格式加以标记，实际上是具有名称的间接指针，遍历目录树时，系统会忽略链接
  - 只有文件拥有者才拥有指向其索引结点的指针，其他用户在自己的目录下创建一个只包含被共享文件的路径名的 LINK 类型的新文件
  - 不会发生文件拥有者删除共享文件后留下悬空指针的情况
  - 能够通过网络链接任何计算机中的文件，只需提供机器的网络地址和机器中的文件路径
  - 解决了硬链接中文件拥有者不能删除共享文件的问题，但其他用户要访问共享文件时需要逐层查找目录，开销较大
文件保护：防止文件受到物理破坏和非法访问
- 访问类型：读、写、执行、添加、删除、列表清单(列出文件名和文件属性)、重命名、复制、编辑等
- 访问控制：对不同的用户访问同一个文件采取不同的访问类型
  - 拥有者，工作组用户，其他用户
  - 访问控制矩阵，访问控制表，用户权限表：使用数据结构记录操作权限
- 口令：建立 FCB 时附上相应口令，开销小，但直接存储在系统内部不够安全
- 密码：加密，使用密钥访问，保密性强，节省存储空间，但编码和译码要花费一定时间
文件系统：操作系统中与文件管理有关的软件和数据的集合
- 系统角度：对存储空间进行组织和分配，负责文件的存储并进行保护和检索(建立撤销读写修改复制)
- 用户角度：实现按名存取
- 用户接口 → 文件目录系统 → 存取控制验证 → 逻辑文件系统与文件信息缓冲区 → 物理文件系统
- 目录的实现：线性表（简单，费时），散列表（简单快速，冲突，长度固定，散列函数依赖表长）

文件的实现

物理结构的实现，包括外存分配方式和文件存储空间的管理

连续分配：不适合文件随时间动态增长和减少的情况，也不适合用户事先不知道文件大小的情况
- 优点：查找速度比其他方法快(只需要起始块号和文件大小)，目录中关于存储位置的信息比较简单
- 缺点：容易产生碎片，需要定期进行存储空间的紧缩
链接分配：用于文件长度需要动态增长以及事先不知道文件大小的情况
- 隐式链接：指针隐式地放在每个物理块中，目录项中有指向索引顺序文件的第一块盘块和最后一块盘块的指针。随机访问效率低，可靠新较差
- 显式链接：每个磁盘设置一张链接表，又称文件分配表 File Allocation Table。不能随机查找，但在内存中查找相对节省时间
- 优点：简单(只需起始位置)，文件创建和增长容易实现
- 缺点：不能随机访问盘块，链接指针占用一些存储空间，存在可靠性问题
索引分配：每个文件分配一个索引块，索引块中存放索引表，每个表项对应分配给文件的一个物理块
- 优点：支持直接访问，不会产生外部碎片，文件长度不受限制
- 缺点：索引块的分配增加了系统存储空间的开销，存取文件需要访问外存两次，降低了存取速度
- 可以在访问文件时先将索引表调入内存中，就只需要访问一次外存
- 索引表大小超过一个物理块，可以建立索引表的索引表(二级索引)
- 单级索引分配，多级索引分配，混合索引分配

空闲存储空间管理

空闲文件表法：连续空闲区看作一个空闲文件，表目内容包括第一个空闲块号、空闲块数目、物理块号
- 分配回收都类似于内存动态分区的管理
- 适用于少量空闲文件，仅适用于连续文件。若有大量的小空闲文件，则表将变得很大，效率大为降低
空闲块链表法：空闲盘块链/空闲盘区链，与动态分区分配相似，通常采用首次适应算法
位示图法：1 表示已分配，0 表示空闲，通常比较小，可以保存在主存中，使存储空间的分配与回收较快，但需要进行二进制位置与盘块号之间的转换
成组链接法(UNIX 使用)：将一个文件的所有空闲块按每组 100 块分成若干组，把每一组的盘块数目和该组的所有盘块号记入到前一组的第一个盘块中，第一组的盘块数目和第一组的所有盘块号记入到超级块中。
- 每组的第一个盘块链接成了一个链表，组内的多个盘块形成了堆栈，每组的第一块是存放下一组的块号的堆栈，系统设置了一把锁来对其互斥地访问
- 分配：先查找第一组的盘块数，超过 1 则分配栈顶盘块，超级块中的空闲盘块数减 1；等于 1(是放置下一组的盘块数和盘块号的那个块，不作为空闲块)且栈顶盘块号不是结束标记 0(最后一组的标记)，则将该块的内容读到超级块中，再分配出去(迭代)；栈顶盘块号为结束标记 0，则无空闲盘块，分配失败
- 回收：第一组不满 100 块，只需在超级块的空闲盘块的栈顶放入该空闲盘块的块号，空闲盘块数加 1；若第一组有 100 块，则先将第一组中的盘块数和盘块号写入到该空闲盘块中，然后将“盘块数=1”及“栈顶块号=该空闲盘块块号”写入到超级块中（成为新的第一组，原第一组称为第二组）
- 占用空间小，且超级块不大，可以放在内存中，提高了效率

磁盘的组织与管理

磁盘：典型的直接存取设备，包含引到控制块(通常为第一块，分区无操作系统则为空)、分区控制块(包括分区的详细信息，如分区的块数、大小、空闲块的数目、指针等)、目录结构、文件控制块
- 访问时间 = 寻道时间 T~s~ + 旋转延迟 T~r~ + 传输时间 T~t~
- 固定头，活动头，固定盘，可换盘
调度算法：使各进程对磁盘的平均访问时间（主要是寻道时间）最短
- 先来先服务算法 FCFS：合理，简单，但未对寻道进行优化，仅适合磁盘请求较少的场合
- 最短寻道时间优先算法 SSTF：选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象
  - 寻道性能比 FCFS 好，但不能保证平均寻道时间最短，并且可能导致某些进程饥饿
- 扫描算法/电梯调度算法 SCAN：在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求…
  - 具有较好的寻道性能，避免了饥饿现象，但对两端磁道请求比较不公平，局部性不好
- SCAN 到底，LOOK 到最后一个请求就返回
- 循环扫描算法 C-SCAN：规定磁头单向移动，即移到最外(内)磁道后立即返回最内(外)磁道
  - 消除了对两端磁道请求的不公平，可能出现磁臂黏着(某个磁道连续请求，导致不响应其他请求)
磁盘管理
- 磁盘初始化
  - 低级格式化，物理格式化：把空白磁盘分成扇区以便磁盘控制器能进行读和写操作，为每个扇区采用特别的数据结构，包括校验码等。每个扇区通常由头部、数据区域(通常 512B)和尾部组成
  - 磁盘分区
  - 对物理分区逻辑格式化：创建文件系统，包括空闲和已经分配的空间以及一个初始为空的目录
- 引导块：存放自举程序（初始化 CPU、寄存器、设备控制器和内存等，然后启动操作系统），自举程序应找到磁盘上的操作系统内核，装入内存，并转到初始地址，从而开始操作系统的运行
  - 只在 ROM 中保留很小的自举装入程序，将完整的自举程序保存在磁盘的启动块上，启动块位于磁盘的固定位。拥有启动分区的磁盘称为启动磁盘/系统磁盘
- 坏扇区：由于硬件有移动部件且容错能力差，容易导致扇区损坏
  - 对简单磁盘，如 IDE，坏扇区可手工处理，在FAT上标明，因此不会被程序使用
  - 对复杂磁盘，如 SCSI，控制器维护一个磁盘坏块链表，在低级格式化时初始化，并随着磁盘的使用更新。采用扇区备用方案，预留一些快作为备用，逻辑地替代坏块，对操作系统透明

设备管理

I/O 设备的分类
- 按使用特性：存储设备、人机交互设备、网络通信设备(网络接口、调制解调器)
- 按信息交换单位：字符设备、块设备
- 按传输速率：低速设备、中速设备、高速设备
- 按共享属性：独占设备、共享设备、虚拟设备
I/O 管理的任务和功能
- 设备分配：按设备类型和分配算法，还有设备控制器和通道
- 设备处理：实现 CPU 和设备控制器之间的通信，I/O 指令、中断请求
- 缓冲管理：缓和 CPU 和 I/O 设备速度不匹配的矛盾，分配、释放、管理
- 设备独立性：又称设备无关性，指应用程序独立于物理设备，可提高用户程序的适应性

I/O 控制方式

设备控制器是设备的电子部分，接收来自 CPU 的命令，并控制 I/O 设备工作。设备控制器是一个可编址设备，其设备地址数量与控制的设备数相关。应具有的功能：
- 接收和识别来自 CPU 的各种指令
- 实现 CPU 与设备控制器、设备控制器与设备之间的数据交换
- 记录设备的状态供 CPU 查询
- 识别所控制的每个设备的地址
- 对 CPU 输出的数据或设备向 CPU 输入的数据进行缓冲
- 对输入/输出数据进行差错控制
程序直接控制方式：CPU 保持不断测试 I/O 设备状态，称为轮询或忙等
- 优点：工作过程非常简单
- 缺点：CPU 的利用率相当低，只能串行工作
中断控制方式：减少程序直接控制方式中的 CPU 等待时间，提高 CPU 与设备的并行工作程度
- 优点：大大提高 CPU 的利用率
- 缺点：每台设备输入/输出一个数据都要中断 CPU，中断次数过多会耗费大量 CPU 时间
- 处理过程（仅指 I/O 完成时发出的中断）
  - 唤醒被阻塞的驱动（程序）进程：signal 操作或发送信号
  - 保护被中断进程的 CPU 环境：PSW，PC，其他寄存器..
  - 转入想要的设备处理程序：测试中断源以确定中断设备号(分析中断原因)
  - 进行中断处理
  - 恢复被中断进程的现场
DMA 控制方式：Direct Memory Access，在外设和内存之间开辟直接的数据交换通路，设备控制器具有更强的功能。设备和内存之间可以成批地进行数据交换而不用 CPU 干预。大大减轻了 CPU 的负担，也使 I/O 数据传输速度大大提高。一般用于块设备的数据传输
- 特点：
  - 数据传输的基本单位是数据块
  - 单向传输，从设备直接送入内存或者相反
  - 仅在传送一个或多个数据块的开始和结束时，才需 CPU 干预，整块数据的传送在控制器的控制下完成
- 与中断控制方式的主要区别：
  - 中断方式在每个数据传送完成后中断 CPU，DMA 方式在要求传送的一批数据全部传送结束时中断 CPU
  - 中断方式的数据传送是在中断处理时由 CPU 控制完成，DMA 方式在 DMA 控制器的控制下完成
  - DMA 中断不用中断现行程序，故不用保护现场
- 组成：主要包括四类寄存器，用于成块数据的交换
  - 命令/状态寄存器 CR，内存地址寄存器 MAR，数据寄存器 DR，数据计数器 DC
- 优点：设备和 CPU 可以并行工作，同时设备与内存的数据交换速度加快，并且不需要 CPU 干预
- 缺点：仍有部分需要 CPU 控制的局限性，且每台设备都需要一个 DMA 控制器，多 DMA 控制器不经济
通道控制方式：需要 CPU 的干预更少，可以一个通道控制多台设备，进一步减轻 CPU 负担
- 通道本质上是一个简单的处理器，独立于 CPU，有运算和控制逻辑，有自己的指令系统，也在程序控制下工作，专门负责输入、输出控制，具有执行 I/O 指令的能力，并通过执行通道 I/O 程序来控制 I/O 操作
- 通道硬件比较简单，指令类型单一，局限于与 I/O 操作有关的指令；通道程序存放在与 CPU 共享的内存中
- 字节多路通道，数组选择通道，数组多路通道
- 系统设备表，设备控制表，控制器控制表，通道控制表
- 读写单位：一组块
- 优点：解决了 I/O 操作的独立性和各部件工作的并行性(CPU 和通道，通道和通道，各通道上的外设)
- 缺点：成本较高，常应用于大型数据交互场合
- CPU 启动通道成功与否，通道都要回答 CPU，通过执行通道程序实现数据的传送
通道与 DMA 方式的区别：DMA 需要 CPU 来控制传输数据块的大小和内存，通道中由通道来控制管理；一个 DMA 控制器对应一台设备与内存传递数据，一个通道可以控制多台设备
I/O 软件层次结构：中断处理程序 → 设备驱动程序 → 设备独立性软件 → 用户层软件
- 设备驱动程序：建立设备寄存器，检查状态。设备驱动程序是操作系统中唯一知道设备控制器中设置了多少个寄存器以及有何用途的程序
  - 具体实现系统对设备发出的操作命令或通过设备状态寄存器来读取设备的状态
  - 将抽象要求转换为具体要求 → 检查 I/O 请求的合法性 → 读出和检查设备的状态 → 传送必要参数 → 设置工作方式 → 启动 I/O 设备
  - 低层部分：中断处理程序
  - 一组共享变量：协调高层和低层所需的状态信息
  - 高层部分：一些函数，在应用程序请求 I/O 操作时调用
- 设备独立性软件：命名、保护、阻塞、缓冲、分配，向用户空间软件提供一个统一的接口
  - 用于实现用户程序与设备驱动器的统一接口、设备命令、设备保护、以及设备分配与释放等
  - 使用逻辑设备名：增加设备分配的灵活性，易于实现 I/O 重定向与 DMA 方式的区别：DMA 需要 CPU 来控制传输数据块的大小和内存，通道中由通道来控制管理；一个 DMA 控制器对应一台设备与内存传递数据，一个通道可以控制多台设备
设备控制器
- 与 CPU 的接口：信号线：数据线，地址线，控制线
- 与设备的接口：每个接口存在数据、控制、状态三种类型的信号
- I/O 控制逻辑：通过一组控制线与 CPU 进行交互，对 I/O 命令进行译码
- 一个 I/O 控制器可能会对应多个设备，寄存器可能有多个且要有相应的地址，分为统一编址(内存映像 I/O)和独立编址(I/O 专用地址)
I/O 核心子系统是设备控制的各类方法，主要提供 I/O 调度、高速缓存与缓冲区、设备分配与回收、假脱机技术\设备保护和差错处理
- I/O 调度：维护请求队列。改善系统地整体性能，使进程间公平地共享设备访问，减少 I/O 完成所需要的平均等待时间
- I/O 子系统改善计算机效率的方法包括 I/O 调度和使用主存和磁盘上的存储空间技术如缓冲、高速缓存、假脱机等
- 缓冲：硬件缓冲器成本太高，一般在内存中划出一块存储区专门临时存放输入/输出数据
  - 缓和了 CPU 与设备速度不匹配的矛盾，提高了设备和 CPU 的并行操作程度，提高了系统吞吐量和设备利用率。还可以降低设备对 CPU 的中断频率，放宽对中断响应时间的限制
  - 单缓冲：设备和处理器对缓冲区的操作是串行的。输入时暂存一行，若有第二行数据要输入，则阻塞。能实现预读和滞后写。max(C, T)+M
    - C：CPU 处理，T：写入缓冲区，M：缓冲区传入用户区(CPU)
  - 双缓冲：提高处理器与设备的并行操作程度，可使块连续输入或处理器连续计算。max(C, T)
  - 循环缓冲：多个大小相等的缓冲区构成链式环，加上输入输出指针 in 和 out
  - 缓冲池：分为三种队列：空队列、满输入队列、满输出队列；具有 4 种缓冲区：收容/提取输入/输出
- 高速缓存与缓冲区
  - 两者存放的数据不同：一个是备份，一个是传递
  - 两者的目的不同：高速缓存存放低速设备上的数据的备份，这样就不需要每次都访问，但不命中还是需要访问低速设备；缓冲区是为了缓和高速设备和低速设备间速度不匹配的矛盾，每次通信都要经过缓冲区，高速设备不会直接访问低速设备

设备的分配和回收

设备管理中的数据结构：设备 → 控制器 → 通道 → 系统
- 设备控制表 DCT：每个设备一张，用于记录设备的特性及 I/O 控制器的连接情况，包含设备类型、设备标识符、设备状态(忙/闲)、设备等待队列指针、COCT 指针
- 设备控制器控制表 COCT：每个控制器一张，反映设备控制器的使用状态以及和通道的连接情况，包含控制器标识符、控制器状态、CHCT 指针、控制器等待队列指针
- 通道控制表 CHCT：每个通道一张，用于反映通道的状态，包含通道标识符、通道状态、通道等待队列指针
- 系统设备表 SDT：整个系统一张，记录了已连接到系统中的所有物理设备的情况，每个物理设备占用一个表目，包含设备类型、设备标识符、DCT 指针、驱动程序入口
设备分配策略
- 设备的使用性质：独占设备，共享设备，虚拟设备
- 设备分配算法：先请求先分配，优先级高者优先
- 设备分配的安全性：保证不发生进程的死锁
  - 静态分配：一次性分配，不会出现死锁，但设备使用效率较低
  - 动态分配：提高设备利用率，但分配算法不当可能造成死锁，分为
    - 安全分配方式：发出 I/O 请求后就进入阻塞状态，直到 I/O 完成才被唤醒，摒弃了请求和保持条件，CPU 和 I/O 串行工作
    - 不安全分配方式：允许进程发出 I/O 请求后仍然运行，有可能死锁，分配设备前进行安全性检测
  - 独占静态，共享动态
设备独立性：应用程序独立于具体使用的物理设备，可以提高设备分配的灵活性和设备的利用率，提高操作系统的可适应性和可扩展性，易于实现 I/O 重定向
- 逻辑设备表 LUT：表项有逻辑设备名、物理设备名(映射)和设备驱动程序入口地址
- 实现设备独立性的方法包括设置设备独立性软件、配置逻辑设备表以及实现逻辑设备到物理设备的映射
设备分配程序
- 单通路 I/O 系统：分配设备 → 分配设备控制器 → 分配通道，设备忙则进程插入等待队列中
- 多通路 I/O 系统：一个设备与多个设备控制器相连，设备控制器也与多个通道相连
  - 根据设备类型，检索系统设备控制表，找到第一个空闲设备，并检测分配的安全性，如安全则分配
  - 检索设备控制器控制表，找到第一个与已分配设备相连的空闲设备控制器，否则返回上一步
  - 查找与其相连的通道，找到第一个空闲通道，无则返回上一步
设备的回收：进程 I/O 完毕后，释放所占有设备、设备控制器及通道，系统回收并修改对应的数据结构
假脱机技术 SPOOLing，Simultaneous Peripheral Operating On-Line，同时外设联机操作，也称为排队转储技术：通过共享设备来虚拟独占设备，将独占设备改造成共享设备，从而提高设备利用率和系统效率
- 高速设备(一般是辅存，磁盘)上形成输入井和输出井，内存中形成输入缓冲区和输出缓冲区，输入进程和输出进程模拟脱机时的外围控制机
- 在输入设备忙时，进程不必等待 I/O 操作的完成；加快了作业完成的速度
- 提高了 I/O 速度；设备并没有分配给任何进程(而是分配一个存储区和建立一张 I/O 请求表)；实现了虚拟设备功能(逻辑)；SPOOLing 除了是一种速度匹配技术外，也是一种虚拟设备技术

补充

磁盘阵列

加密算法

对称多处理 SMP 体系结构

LINUX：允许 root 和 guest 同时登陆，允许多个客户端通过 root 账号登录

Linux 是一个多用户、多任务的操作系统;考生应该了解单用户多任务和多用户多任务的概念。 (1)Linux 的单用户、多任务。

单用户、多任务;比如以 beinan 登录系统，进入系统后，要打开 gedit 来写文档，但在写文档的过程中，感觉少点音乐，所以又打开 xmms 来点音乐;当然听点音乐还不行，MSN 还得打开，想知道几个朋友现在正在做什么。这样，在用 beinan 用户登录时，执行了 gedit、xmms 以及 msn 等，当然还有输入法 fcitx;这样说来就有点简单了，一个 beinan 用户，为了完成工作，执行了几个任务;当然 beinan 这个用户，其他的人还能以远程登录过来，也能做其他的工作。

(2)Linux 的多用户、多任务。有时可能是很多用户同时用同一个系统，但并非所有的用户都一定要做同一件事，所以这就有多用户、多任务。举个例子，比如 LinuxSir.org 服务器，上面有 FTP 用户、系统管理员、web 用户、常规普通用户等，在同一时

刻，可能有人正在访问论坛;有人可能在上传软件包管理子站，比如 luma 或 Yuking 在管理他们的主页系统和 FTP; 在与此同时，可能还会有系统管理员在维护系统;浏览主页的用的是 nobody 用户，大家都用同一个，而上传软件包用的是 FTP 用户;管理员的对系统的维护或查看，可能用的是普通账号或超级权限 root 账号;不同用户所具有的权限也不同，要完成不同的任务就需要不同的用户，也可以说不同的用户，可能完成的工作也不一样。

值得注意的是，多用户、多任务并不是大家同时挤到一起在一台机器的键盘和显示器前来操作机器，多用户可能通过远程登录来进行，比如对服务器的远程控制，只要有用户权限任何人都是可以上去操作或访问的。

计算机操作系统

Operating System

计算机操作系统

绪论

进程管理

进程与线程

处理器调度

同步与互斥

死锁

内存管理

连续分配管理方式

离散分配管理方式

虚拟内存管理

内存管理方式之间的比较

文件管理

文件的逻辑结构

目录结构

文件的实现

空闲存储空间管理

磁盘的组织与管理

设备管理

I/O 控制方式

设备的分配和回收

补充

CATALOG

FEATURED TAGS

FRIENDS