OS.txt

操作系统是指控制和管理整个计算机系统的硬件与软件资源，合理地组织、调度计算机的工作与资源的分配，进而为用户和其它软件提供方便接口与环境的程序集合。

操作系统的特征：并发，共享，虚拟，异步

并发和共享互为条件

共享：互斥共享方式，同时访问方式

虚拟处理器，虚拟内存，虚拟外设

作为计算机系统资源的管理者：处理机管理，存储器管理，设备管理，文件管理
进程管理：进程控制，进程同步，进程通信，死锁处理，处理机调度
存储器管理：内存分配与回收，地址映射，内存保护与共享，内存扩充
文件管理：文件存储空间管理，目录管理，文件读写管理和保护
设备管理：缓冲管理，设备分配，设备处理，虚拟设备

作为用户与计算机硬件系统之间的接口：命令接口，程序接口
命令接口：联机接口即交互式命令接口，脱机接口
程序接口：一组系统调用（广义指令）组成

扩充机器，即虚拟机

广义指令==系统调用
命令解释器、shell都属于命令接口

多道程序系统相比单道程序系统的优点有：I/O设备利用率高，真题，死背



库函数和系统调用的区别和联系
库函数有的运行在用户空间，系统调用运行在内核空间
许多库函数使用系统调用来实现

操作系统内核包括：时钟管理，中断机制，原语
中断机制只有一小部分属于内核

关中断，保存断点，引出中断服务程序，保存现场和屏蔽字，开中断，执行中断服务程序，关中断，恢复现场和屏蔽字，开中断，中断返回

程序段，数据段和PCB构成进程映像

动态性，并发性，独立性，异步性，结构性

运行态，就绪态，阻塞态，创建态，结束态

共享存储，消息传递，管道通信

空闲让进，忙则等待，有限等待，让权等待

处理机调度是操作系统设计的核心

三级调度：作业调度，内存调度，进程调度

不能立即进行调度与切换的情况：处理中断，进程在内核程序的临界区（不是普通的临界区，如打印机），其它完全屏蔽中断的原子操作

中断处理结束后返回前，若置请求调度标志，可以马上进行进程调度与切换

FCFS有利于CPU繁忙作业，不利于IO繁忙作业

短作业优先的平均等待时间和平均周转时间最少

IO型进程优先级高于计算型进程

响应比 = 周转时间/服务时间

多级反馈队列调度

中断由硬件完成的主要目的是保证可靠性

单标志法，违背空闲让进，且P1如果不进入临界区，P0无法再次进入

双标志先检查，违背忙则等待

双标志后检查，会让两个进程都进不了临界区

peterson算法，先设置自己的标志，再设置turn标志为对方，同时检测对方的标志和turn的标志

硬件方法，TestAndSet和Swap方法，不能实现让权等待

整型信号量未实现让权等待

管程由四部分组成，名称，共享结构数据说明，过程，初始化共享数据

死锁产生的原因
系统资源的竞争：不可剥夺资源的数量不足
进程推进顺序非法

死锁的四个条件
互斥，不可剥夺，请求并保持，循环等待
循环等待允许等待序列以外的进程释放某资源，死锁不允许

资源分配图含环，但不一定死锁的情况：同类资源数大于1

死锁的处理策略
死锁预防，避免死锁，死锁的检测及解除

避免死锁
不安全状态可能由于进程在结束前就释放资源从而转为安全状态，所以不安全状态不一定会死锁
银行家算法
进程必须事先声明资源的最大需求量

饥饿的进程可以只有一个，死锁至少有两个
饥饿的进程可以是就绪的，死锁的进程必定是阻塞的

死锁解除的方法
资源剥夺，撤销进程，进程回退

两次上下文切换，一次切换给分派程序，一次切换给新的进程

内存管理
内存空间的分配与回收，地址转换，内存空间的扩充，存储保护

编译，链接，装入
静态链接，装入时动态链接，运行时动态链接
绝对装入，可重定位装入，动态运行时装入（动态重定位）

动态重定位允许程序在内存中移动，需要一个重定位寄存器，允许把程序分配到不连续的存储区，只装入部分代码即可运行，动态申请分配内存

地址重定位
装入内存时，将逻辑地址转换为物理地址

内存保护
上下限寄存器，重定位（基址）寄存器和界地址（限长）寄存器

覆盖，交换

连续分配
单一连续分配，固定分区分配，动态分区分配

固定分区分配
内部碎片，太大放不进

首次适应，最佳适应，最坏(大)适应，邻近适应
外部碎片

非连续分配
分页存储管理，分段存储管理

基本分页存储管理

页面大小为L，逻辑地址A，物理地址E
页号P=A/L，页内偏移W=A%L
页表寄存器PTR，存放页表在内存的起始地址F和页表长度M
页号大于等于页表长度，越界中断
页表项地址=F+P*页表项长度，页表项内容b是物理块号
E=b*L+W

页表不能太大，地址转换必须够快
TLB相联存储器

虚存特征
多次性，对换性，虚拟性

请求分页存储管理

页表结构
状态位P，访问字段A，修改位M，外存地址

缺页中断是内部中断，一条指令可能产生多次缺页中断

最佳置换OPT，选择最长时间内不再访问的页面

先进先出置换，Belady异常，物理块数越大页故障不减反增

最近最久未使用LRU，每页一个访问字段，自上次被访问以来所经历的时间

FIFO是队列算法，LRU是堆栈类算法，堆栈类算法不会出现Belady异常

时钟CLOCK置换，又称最近未使用NRU算法，每帧一个附加的使用位u，当首次装入主存或被访问时置为1
当某一页被替换时，指针指向循环缓冲区中该页的下一帧
当需要替换时，循环扫描缓冲区，当遇到一个使用位为1的帧时置为0，当遇到使用位为0的帧时替换

改进型CLOCK置换，增加一个修改位m，替换时首次循环扫描不修改使用位，寻找u=0且m=0的帧，若失败，重新扫描u=0且m=1的帧，对每个被跳过的帧，设置u=1，若失败，重复第一步，若有必要，重复第二步

驻留集，给进程分配的物理页的集合

页面分配策略
固定分配局部置换，可变分配全局置换，可变分配局部置换

调入页面的时机
预调页策略，一次调入一批相邻的页，但准确率不高，目前主要用于进程的首次调入，由程序员指定
请求调页策略

从何处调入页面
外存分为文件区和对换区
系统拥有足够的对换区空间时，全部从对换区调入，因此在进程运行前，该进程有关的文件需要从文件区复制到对换区
系统缺少足够的对换区空间时，不会被修改的文件从文件区调入，换出页面时不需要将它们换出，可能被修改的部分在换出时需要调到对换区，需要时再从对换区调入
UNIX方式，与进程有关的文件都放在文件区，未运行过的页面都从文件区调入，被换出的页面放在对换区，共享页面若被其它进程调入，则无需再调入

工作集，某段时间内进程要访问的页面集合，由时刻t和工作集窗口大小确定

文件结构
数据项，包括基本数据项和组合数据项
记录，一组相关的数据项的集合
文件，一组相关信息的集合，逻辑上分为有结构文件和无结构文件

有结构文件：记录式文件，文件由一组相似的记录组成
无结构文件：流式文件，二进制文件或字符文件

文件属性
名称，标识符，类型，位置，大小，保护，时间日期，用户标识

文件系统的系统调用：创建，写，读，重定位，删除，截断

创建文件
在文件系统中为文件找到空间，在目录中为文件创建条目

写文件，系统为文件维护一个写位置的指针

读文件，指明文件名称和要读入文件块的内存位置，系统维护一个读位置的指针

文件重定位，文件寻址，按某条件搜索目录，将当前文件位置设为给定值，不会读写文件

删除文件，删除目录项，回收该文件的空间

截断文件，允许文件所有属性不变，将文件长度设为0并释放空间

以上基本操作可以组合起来执行其它操作，如复制，创建新文件，从旧文件读出并写入新文件

系统调用open，首次使用文件时调用
系统在内存中维护一个包含所有打开文件信息的表，打开文件表，该表中包含文件的属性，并将该表目的索引返回给用户
open根据文件名搜索目录，将目录条目复制到打开文件表，open返回一个指向打开文件表条目的指针，使用该指针而非文件名进行IO操作节省资源

另一个进程执行open时，在其进程打开表中增加一个条目，指向系统表的相应条目
通常系统打开文件表中的每个文件还有一个文件打开计数器，记录多少个进程打开了该文件

当打开计数器为0时，系统回收内存，将文件写回外存，删除系统打开文件表的该条目，释放文件控制块FCB

打开文件包括以下信息
文件指针，文件打开计数，文件磁盘位置，访问权限
文件指针对每个打开文件的进程来说都是唯一的，它和访问权限都位于进程的打开文件表

逻辑结构
无结构文件将数据按顺序组织成记录，是有序相关信息项的集合，以字节为单位
有结构文件分为顺序文件，索引文件，索引顺序文件，直接文件(Hash File)

顺序文件，一般是定长的，顺序或链表存储
串结构，按时间排列
顺序结构，按关键字排列

索引文件，可以定长也可以不定长，不定长记录的文件必须顺序查找前i-1条记录
可以建立索引表

索引顺序文件，将顺序文件的记录分为若干组，为顺序文件建立一张索引表，索引表中为每组的第一条记录的关键字值
索引表只包含关键字和指针两个项，所以关键字递增排列
同组的关键字无序，组间的关键字有序

散列文件，给定记录的键值直接决定记录的物理地址，没有顺序的特性

文件目录结构
文件控制块
FCB的有序集合称为文件目录，一个FCB是一个文件目录项
FCB包含文件基本信息、存取控制信息和使用信息

索引结点
UNIX采用了文件名和其它描述信息分开的方法，文件描述信息单独形成一个称为索引结点的数据结构，简称i结点，文件目录仅有文件名和i结点指针构成

FCB必须连续存放

磁盘索引结点
UNIX的每个文件都有唯一的磁盘索引结点，包括文件主标识符，文件类型，文件存取权限，文件物理地址，文件长度，文件链接计数，文件存取时间

文件被打开时，磁盘索引结点被复制到内存索引结点，又新增索引结点编号、状态、访问计数、逻辑设备号和链接指针

目录结构
搜索，创建文件，删除文件，显示目录，修改目录

单级目录结构
整个文件系统只建立一张目录表，每个文件占一个目录项

两级目录结构
主文件目录MFD和用户文件目录UFD
MFD记录用户名及UFD位置，UFD记录用户文件的FCB

多级目录结构
根目录和当前目录
/dev/hda
.表示当前目录，若当前目录为/bin
则/bin/ls等价于./ls

无环图目录结构
树形目录结构不便于实现文件共享
共享计数器，仅当计数器为0时删除文件，否则删除请求用户的共享链

文件共享

基于索引结点的共享方式，硬链接
文件物理地址及其它的文件属性不再放在目录项中，放在索引结点中
索引结点中还有链接计数器，表示链接到该文件上的用户目录项的数目

用户创建文件时，是该文件的所有者，其它用户要共享此文件时，在各用户的目录中增加一个目录项，设置一个指针指向该文件的索引结点

所有者不能直接删除文件，只是将文件的计数器减1，然后删除自己目录中的相应目录项

符号链接，软链接
当用户B要共享用户A的文件F时，系统创建一个LINK类型的文件，取名为F，将F写入B的目录中，LINK文件只包含被链接文件F的路径名
只有文件所有者才拥有指向索引结点的指针，其他用户只有该文件的路径名，当文件所有者删除文件后，其他用户通过LINK访问时会失败，于是将符号链接删除
若所有者删除文件，其他用户在同一路径下创建了同名文件，则会导致LINK访问到错误的文件

硬链接和软链接都是静态共享，遍历文件系统时会多次遍历共享文件

动态共享，允许多个进程同时对一个文件进行操作

文件保护
口令保护，加密保护，访问控制

访问类型
读，写，执行，添加，删除，列表清单

列表清单，列出文件名和文件属性

重命名、复制、编辑等高层功能通过系统程序调用低层系统调用实现

保护可以只在低层提供，则具有读权限也就有了复制和打印权限

访问控制AC

为每个文件和目录增加一个访问控制列表ACL，优点是可以使用复杂的访问方法，缺点是长度无法估计，可能导致复杂的空间管理

精简的访问列表采用所有者、组和其它三种用户类型

创建文件时，说明创建者及所在的组名，系统将这些信息列在该文件的FCB中，用户和所有者在同一个组时按照同组权限访问

口令
用户在建立文件时提供一个口令，系统为器FCB附上口令，用户访问时必须提供口令
口令直接存在系统内部，不够安全

密码
用户对文件进行加密，访问时需要使用密钥，保密性强，但编码和译码要花费时间

目录操作和文件操作不同，因此目录需要不同的保护机制

文件系统层次结构
0级用户调用接口，1级文件目录系统，2级存取控制验证模块，3级逻辑文件系统与文件信息缓冲区，4级物理文件系统。辅助分配模块，设备管理程序模块

文件目录系统
管理文件目录，管理活跃文件目录表，管理读写状态信息表，管理用户进程的打开文件表，管理与组织存储设备上的文件目录结构，调用下一级存取控制模块

逻辑文件系统与文件信息缓冲区
根据文件的逻辑结构将用户要读写的逻辑记录转换成文件逻辑结构内的相应块号

物理文件系统
把逻辑记录所在的块号转换成物理地址

辅助分配模块
管理外存空间，负责分配和回收

设备管理程序模块
分配设备，分配设备读写用缓冲区，磁盘调度，启动设备，处理设备中断，释放缓冲区，释放设备等

目录实现
线性列表，哈希表

文件实现
文件分配方式，文件存储空间管理

文件分配方式
连续分配，链接分配，索引分配

连续分配不便修改文件，会产生外部碎片

链接分配
隐式链接

显式链接，将链接文件各物理块的指针显式地放在文件分配表FAT中，该表在整个磁盘中只有一张，表项中值为-1表示是该文件的最后一块，-2表示空闲，文件目录中存放各文件的起始块号
FAT表在系统启动时就读入内存

索引分配
把每个文件的所有盘块号都放在一起构成索引表，文件目录项包括索引块的地址，索引块的第i项指向文件的第i块

索引块如何支持大文件
链接方案，将多个索引块链接起来表示一个大文件
多层索引
混合索引

通常将文件的索引块读入内存，以避免两次访问外存

文件存储空间管理
文件存储器空间的划分和初始化
文件卷，包括分离的文件区和目录区

空闲表法
属于连续分配方式，为每个文件分配一块连续空间，对外存所有的空闲区建立一张空闲盘块表，包括该区第一个盘块号，空闲盘块数等
空闲盘区的分配采用首次适应算法、循环首次适应算法等

空闲链表法
空闲盘块链将所有空闲空间以盘块为单位拉成链表，释放的空间插入链表末尾
空闲盘区链将所有空闲盘区拉成链表，结点上除了指向下一个盘区的指针，还指明了本盘区的盘块数，通常采用首次适应算法，回收时需要合并相邻的空闲盘区

位示图法
将所有盘块的使用情况表示到位示图
分配时顺序扫描位示图，从中找到一组为0的二进制位，并转换成盘块号，然后修改位示图
回收时将盘块号转换为位示图中的行列号，修改位示图

成组链接法
UNIX采用，克服表太大的缺点
将顺序的n个空闲扇区地址保存在第一个空闲扇区内，第n+1个空闲扇区则保存另一顺序空闲扇区的地址，直至所有空闲扇区都链接上，系统只需保存第一个空闲扇区的指针
第一个成组链块以及卷的目录区、文件区划分信息都放在卷头，在UNIX中称为超级块

读写时磁头固定，磁盘旋转
盘面分为磁道，磁道分为扇区，扇区称为盘块
密度从外向里增加，磁盘存储能力受限于最内道的最大记录密度

每个盘面对应一个磁头，所有磁头固定在一起，所有盘片上相对位置相同的磁道组成柱面

磁头相对盘片的径向方向固定的称为固定头磁盘，每个磁道一个磁头，磁头可移动的称为活动头磁盘
磁盘可移动和替换的称为可换盘磁盘，永久固定的称为固定盘磁盘

磁盘读写时间
寻找时间Ts = mn+s，n是跨越的磁道数，s是启动磁臂的时间，m是与磁盘驱动器速度有关的常数
延迟时间Tr = 1/2r，r是磁盘旋转速度
传输时间Tt = b/rN，b是字节数，r是磁盘旋转速度，N为一个磁道上的字节数
总平均存取时间Ta = Ts+Tr+Tt
一般寻道时间最长，因此文件存在一个柱面的不同盘面比存在一个盘面的不同磁道好

磁盘调度算法
先来先服务FCFS
最短寻找时间优先SSTF，会产生饥饿现象
扫描/电梯调度SCAN，在当前移动方向上选择与当前磁道最近的请求，偏向于处理最内或最外磁道的请求
循环扫描CSCAN，磁头单向移动提供服务，回返时直接移动至起始段不服务任何请求
LOOK/CLOOK调度，可以默认扫描算法采用，只移动到最远端的一个请求即返回，不移动到磁盘端点

减少延迟时间
盘面扇区交替编号，磁盘盘面错位命名
因为磁盘是连续自转设备，磁头在读写一个块厚需要短暂的处理时间才能开始读写下一块

磁盘管理
磁盘初始化，引导块，坏块

磁盘初始化
低级格式化，将磁盘分成扇区，扇区由头、数据区、尾组成
操作系统将自己的数据结构记录在磁盘上，将磁盘分为由一个或多个柱面组成的分区
逻辑格式化，创建文件系统，将文件系统数据结构存储到磁盘，包括空闲、已分配空间和初始为空的目录

引导块
自举程序，初始化CPU和寄存器、内存等
通常在ROM保存自举装入程序，将自举程序保存在磁盘的启动块，启动块位于磁盘的固定位置，拥有启动分区的磁盘称为系统磁盘或启动磁盘

坏块
简单磁盘，坏扇区在FAT表上标明
复杂磁盘，控制器维护一个在低级格式化时初始化的磁盘坏块链表，链表将一些块留作备用，用备用块逻辑地替代坏块，称为扇区备用
坏块是硬件故障，操作系统不能修复

引导控制块BCB，通常为分区的第一块，若磁盘没有操作系统则该块为空，UFS称为引导块，NTFS称为分区引导扇区
分区控制块PCB，包括分区详细信息如分区块数，块大小，空闲块数和指针，空闲FCB数和指针等，UFS称为超级块，NTFS称为主控文件表

内存分区表包含所有安装分区的信息
内存目录结构保存进来访问过的目录信息，对安装分区的目录还可以包括一个指向分区表的指针

打开文件表的索引，UNIX称为文件描述符，Windows称为文件句柄
系统调用open会首先搜索系统范围的打开文件表，以确定是否已被其它进程使用

混合索引分配
UNIX采用，分为直接地址和间接地址

DMA控制器中的寄存器
命令/状态寄存器CR，接收I/O命令或控制信息或设备状态
内存地址寄存器MAR
数据寄存器DR
数据计数器DC

I/O通道
通道指令类型单一，没有自己的内存，与CPU共享内存
每个DMA控制器对应一台设备，通道可以控制多台设备

I/O系统层次
用户层I/O软件，设备独立性软件，设备驱动程序，中断处理程序，硬件

设备独立性软件将逻辑设备名映射成物理设备名，好处是增加设备分配的灵活性，易于实现I/O重定向，即用于I/O操作的设备可以更换
执行所有设备的共有操作，如设备分配回收、设备保护、缓冲管理等
对应用程序提供统一接口

每类设备配置一个设备驱动程序，实现系统对设备的操作指令

中断处理程序，用于保存被中断进程的CPU环境，放在操作系统的底层

硬件设备，包括机械部件和电子部件

设备控制器通过寄存器与CPU通信，内存映像I/O或寄存器独立编址
接受和识别CPU或通道的命令，实现数据交换，发现和记录设备及自身的状态信息，设备地址识别

设备控制器
与CPU的接口，包括数据线，地址线，控制线，数据线连接数据寄存器和控制/状态寄存器
与设备的接口
I/O控制逻辑

I/O子系统
I/O调度，缓冲与高速缓存，设备分配与回收，假脱机，设备保护和差错处理

磁盘高速缓存逻辑上属于磁盘，物理上是驻留在内存中的盘块

缓冲区必须满了才能传出

单缓冲t = max(处理,输入)+传送
双缓冲t = max(处理+传送,输入)
循环缓冲，in指针，out指针
缓冲池

设备分配与回收
独占式使用设备，分时式共享使用设备，SPOOLing使用设备即假脱机I/O技术

设备分配的数据结构
设备控制表DCT，控制器控制表COCT，通道控制表CHCT，系统设备表SDT

一个DCT表示一个设备，DCT需要一个表项表示控制器，即需要一个COCT指针，DCT与COCT一一对应

COCT有一个表项，指向通道控制器CHCT
CHCT有一个表项，指向当前CHCT提供服务的设备控制器列表，即CHCT与COCT一对多

整个系统只有一张SDT，记录所有连接到系统的物理设备的情况

设备分配策略
原则，既要发挥设备的使用率，又要避免造成死锁，还要将用户程序和具体设备隔离
分配方式，静态分配和动态分配，动态分配可能造成死锁，独占设备可以采用静态分配
分配算法

设备分配的安全性
安全分配方式，进程发出请求后进入阻塞态，直到I/O操作完成
不安全分配方式，进程发出I/O请求后继续运行，可能发出多个I/O请求，可能产生死锁

逻辑设备表LUT
包括逻辑设备名，物理设备名，设备驱动程序入口
为每个用户建立一个进程，建立一张LUT并放入该进程的PCB

SPOOLing