导图社区 Operating System操作系统-基础
- 25
- 举报
Operating System操作系统-基础
大学计算机相关学科的一门必修课，在我的专业，计算机图形学和操作系统是两个最大的坎。
编辑于2022-09-01 13:41:42 浙江省
- 盲文阅读效率研究
本书是在作者多年的盲文摸读实践及盲文教学经验的基础上，充分参考本领域专家、学者相关成果，经过创新性思维和反复实践论证所形成的。本书吸收借鉴中西方阅读学理论，分析影响盲文阅读效率的主客观因素，系统分析盲文阅读效率与拼读速度、理解率的关系，以及出现拼读错误的客观性，给出盲文容错率的概念。 作者为夫妻二人，男方在读博期间失明，之后一直从事视障方面的教学和研究；女方本行是计算机，现在也在做盲文的计算机算法等方面的研究。
- 盲文阅读效率研究
本书是在作者多年的盲文摸读实践及盲文教学经验的基础上，充分参考本领域专家、学者相关成果，经过创新性思维和反复实践论证所形成的。本书吸收借鉴中西方阅读学理论，分析影响盲文阅读效率的主客观因素，系统分析盲文阅读效率与拼读速度、理解率的关系，以及出现拼读错误的客观性，给出盲文容错率的概念。 作者为夫妻二人，男方在读博期间失明，之后一直从事视障方面的教学和研究；女方本行是计算机，现在也在做盲文的计算机算法等方面的研究。
- 无障碍虚拟学习环境
无障碍虚拟学习环境的思维导图，Virtual learning environments, VIEs，利用VR技术来改进学习过程和创造新的学习环境。
Operating System操作系统-基础
社区模板帮助中心，点此进入>>
- 盲文阅读效率研究
本书是在作者多年的盲文摸读实践及盲文教学经验的基础上，充分参考本领域专家、学者相关成果，经过创新性思维和反复实践论证所形成的。本书吸收借鉴中西方阅读学理论，分析影响盲文阅读效率的主客观因素，系统分析盲文阅读效率与拼读速度、理解率的关系，以及出现拼读错误的客观性，给出盲文容错率的概念。 作者为夫妻二人，男方在读博期间失明，之后一直从事视障方面的教学和研究；女方本行是计算机，现在也在做盲文的计算机算法等方面的研究。
- 盲文阅读效率研究
本书是在作者多年的盲文摸读实践及盲文教学经验的基础上，充分参考本领域专家、学者相关成果，经过创新性思维和反复实践论证所形成的。本书吸收借鉴中西方阅读学理论，分析影响盲文阅读效率的主客观因素，系统分析盲文阅读效率与拼读速度、理解率的关系，以及出现拼读错误的客观性，给出盲文容错率的概念。 作者为夫妻二人，男方在读博期间失明，之后一直从事视障方面的教学和研究；女方本行是计算机，现在也在做盲文的计算机算法等方面的研究。
- 无障碍虚拟学习环境
无障碍虚拟学习环境的思维导图，Virtual learning environments, VIEs，利用VR技术来改进学习过程和创造新的学习环境。
- 相似推荐
- 大纲
OS
一 引论
计算机系统
硬件
电子、机械和光电组件等构成的计算机部件和设备
中央处理器CPU
各种存储器
IO设备
软件
计算机系统中的各种程序、数据和有关的文档
数据：信息在计算机中的表示
程序：计算任务的处理对象和处理规则的描述
文档
分类
系统软件
编译程序，装配程序，os
应用软件
支撑软件
支撑应用软件系统编制和工作的基础
DBMS（数据库管理系统啊
甲骨文，MySQL
开发工具
vs和vs code
中间件
为应用提供通用服务和功能的软件
数据管理，应用服务，消息传递，身份验证，API管理
层次结构
操作系统
定义
操作系统是一组控制和管理计算机硬件和软件资源,合理地对各类作业进行调度,以及方便用户使用的程序的集合。
交互方式
键盘输入shell命令
鼠标点击相应的功能
编写程序调用，即系统调用接口
作用
用户与计算机硬件之间的接口
提供用户接口
功能
计算机系统资源的管理者
四种功能:处理器管理、存储器管理、I/O设备管理、文件管理
四种资源:处理器、存储器、I/O设备以及信息
构建便捷高效的虚拟机
裸机：完全无软件的计算机系统
虚拟机：覆盖了软件的机器
特征
并发 （os的基本特征你都标红出来啦
并行是同时刻同时发生 多处理器，并发是同时刻交替发生 单处理器
共享
互斥共享，同时访问
虚拟
把物理实体变为若干个逻辑上的对应物
异步（不确定性）
发生原因：竞争资源
发展和分类
手工操作方式
批处理系统
计算机自动完成一批作业的调度和执行
单道批
作业
是用户定义的、由计算机完成的一个工作单位。 作业由不同的顺序相连的作业步组成
作业=程序+数据+作业说明书
作业概念一般用于早期批处理系统和现在的大型机、巨型机系统中
作业步：在一个作业的处理过程中计算机所做的相对独立的工作
单道性、顺序性、自动性
多道批
多道程序设计技术：内存中同时驻留多个相互独立的程序，它们在操作系统的控制下共享系统资源，相互穿插地运行
允许多个用户将多个作业提交给计算机集中处理
充分发挥cpu和外设并行工作的能力
多道性、无序性、调度性
优：资源利用率高、系统吞吐量大 缺：作业平均周转时间较长、无交互能力
分时系统
分清楚响应时间和处理时间
是指一台主机上连接了多个终端，同时允许多个用户通过自己的终端，以交互的方式使用计算机,共享主机中的资源的系统。
时间片：每个终端用户的作业能连续使用CPU的最长时间。
实现中的关键问题：人机交互，及时响应用户请求
解决：配置多路卡，为每个终端配置IO缓冲区，作业提交时直接进入内存减少等待，引入时间片的概念
发展的动力是满足用户的需要
（人人有份，永不落空
实时系统
系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。、
不强求对系统资源的利用率
截止时间：开始截止时间，完成截止时间
（12306
多路性和独立性：都有 实时系统更加及时、可靠 分时系统交互性最强 分时系统不具有实时性
微机操作系统
单用户单任务
MS-DOS
单对多
windows, os
多对多
unix, linux，基于linux开发的android
网络操作系统
除了具备一般操作系统应具有的功能模块外，还要增加一个网络通信模块。该模块由通信接口中断处理程序、通信控制程序以及各级网络协议软件组成。
功能：一般操作系统的+网络通信管理，网络资源管理，网络安全管理，提供网络服务
计网
特点：多个独立计算机，无公共内存，具备消息通信机制
局限：不支持透明的资源存取，不能对网络资源进行有效统一的管理，不能支持合作计算
（百度云？
分布式系统
定义： ①包含多个分布的通用资源部件,并经过通信网络相互作用 ②有一个分布式操作系统对资源进行全局和动态的管理控制 ③系统对用户是透明的 ④任务可以分布处理;
特点：可扩展性，增加性能，高可靠性
本质的不同：系统中若干台计算机相互协作完成同一任务
嵌入式系统
是指将应用程序和OS与计算机硬件集成在一起的系统。 负责嵌入式系统的全部软、硬件资源的分配、调度工作、控制协调并发活动等
Android,windows phone,ios,黑莓, VxWorks,linux
用户接口
OS通常会为用户提高多种使用接口，如中端命令、图标菜单、系统调用和类似DOS的批命令/unix的shell文件
命令接口CLI
联机用户接口
由一组键盘操作命令及命令解释程序组成
eg，键盘打字 实时的
图形接口
菜单驱动、图符驱动
脱机用户接口
由一组作业控制语言(JCL)组成
IO命令：编译命令、操作命令、条件命令
作业说明书
作业基本情况描述，作业控制描述、作业资源要求描述
eg，塞纸带 非实时的
批处理系统
程序接口API
系统调用在这啦
程序接口是应用程序以函数调用的方式来使用系统服务的接口，在Unix/Linux系统中也称为系统调用system call
优先级： 立即抢占，非立即抢占
是否套娃：嵌套调用
系统功能调用是用户在程序一级请求操作系统服务的一种手段，它是带有一定功能号的“访管指令”。其功能是由操作系统中的程序完成的，即由软件方法实现的
系统调用处理程序：system_call()
系统调用号
Linux中每个系统调用被赋予一个唯一的系统调用号
定义在include/asm-i386/unistd.h头文件中
格式：#define __NR_restart_syscall 0
系统调用入口表
记录所有已注册的系统调用，是系统调用的跳转表
是一个函数指针数组
系统调用参数传递
寄存器传递： eax系统调用号
对参数的要求：每个参数长度不能超过寄存器长度(32位)，参数个数不能超过6个
和库函数的区别：
很多系统都会提供，如MS-DOS,windows
图形接口GUI
更加友好的交互型用户接口
交互式系统(分时、微机)
键盘命令
内核结构
内核功能：资源抽象资源分配资源共享（没有程序编辑
整体/单体结构
操作系统是一组过程的集合，每个过程有接口定义，包括入口参数和返回值，过程间可任意调用
设计重点：实现功能和高效率
缺：缺乏清晰的程序结构、错误多、难维护
eg. AT&T SystemV，BSD UNIX
模块化结构/无序模块
操作系统按功能划分模块和设计，模块需要封装，相关模块间具有良好定义的接口，模块间可任意调用
特点：有利于系统设计和扩展 高内聚低耦合
缺：模块间存在着复杂的依赖关系，使OS结构不清
eg. Choices系统
层次结构
把OS的功能模块划分为若干层，每层之间的模块只能单向调用
优：易保证系统的正确性，易扩充和易维护性（最大的特点：便于调试）
缺：自上而下的层次通信，系统效率降低
eg. Dijkstra的THE系统
最里面是处理器管理，最外面是资源分配调度
微内核结构
不用修改内核 系统更加可靠 其他功能移到外面了，所以不高效 内核的服务越少内核越稳定
特点：采用面向对象技术，基于客户/服务器模式
运行在核心态的微内核
运行在用户态的并以客户/服务器方式活动的进程层
实际操作系统的结构
UNIX
linux
windows
二 硬件基础
处理器计算
计算机最主要的两类资源是计算机资源和存储资源
处理器指令
计算机所有操作都是由指令所决定的
必须包含的信息
操作码
代表要完成的具体操作
分类：数据传递、算术运算、逻辑运算、转换、输入输出、系统控制和控制传递
源操作数
是指具体操作所需的输入，可以是一个也可以是多个
一般来源于寄存器、内存
目的操作数
指具体操作的结果
可在寄存器或者内存中
下一条指令地址
执行步骤
eg.
指令符号
ADD, SUB,LOAD……
寻址方式
寻址方式就是处理器根据指令中给出的地址信息来寻找物理地址的方式，是确定本条指令相关的数据地址以及下一条要执行的指令地址的方法
分类
指令寻址
顺序寻址
指令一般顺序地存储在内存中
必须使用程序计数器（又称指令计数器）PC来记录指令的地址。处理器根据PC给出的地址取出相应指令，同时修改PC的值，使其指向下一条指令地址
跳跃寻址
当程序执行转移或者函数调用等相关指令时，需要改变顺序执行模式，那么指令的寻址就会采取跳跃寻址方式
下条指令的地址不是由PC给出，而是由正在处理器上执行的指令给出。跳跃后PC的内容也必须相应改变
作用：可以实现程序转移，构成循环程序，从而能缩短程序长度，或将某些程序作为公共程序引用
数据寻址
形成操作数的有效地址的方法
隐含寻址、立即寻址、直接寻址、间接寻址、寄存器寻址方式和寄存器间接寻址方式、相对寻址方式、基址寻址方式、变址寻址方式、块寻址方式
前者简单些，后者复杂些，两者是交替进行的
寄存器
寄存器是中央处理器的组成部分，是有限存贮容量的高速存储部件，可用来暂存指令、数据和地址
在中央处理器的控制部件中，包含的寄存器有指令寄存器(IR)和程序计数器／指令计数器(PC) 在中央处理器的算术及逻辑部件中，寄存器有累加器(ACC)
组成
通用寄存器
专用寄存器
控制寄存器
按用途分类
数据寄存器：用来储存整数数字。在某些简单/旧的CPU中，特别地，数据寄存器是累加器，作为数学计算之用 地址寄存器：用来存放存储器地址，用来访问存储器。 通用目的寄存器（GPRs）：保存数据或地址，即结合了数据寄存器或地址寄存器的功能。 浮点寄存器（FPRs）：用来储存浮点数据。 常数寄存器：用来存放只读的数值（例如0、1、圆周率等等）。 向量寄存器：用来储存由向量处理器运行SIMD（Single Instruction, Multiple Data）指令所得到的数据。 特殊目的寄存器：储存CPU内部的数据，比如程序计数器、堆栈寄存器、程序状态寄存器等。 指令寄存器：储存当前正在被执行的指令。 索引寄存器：用于在程序运行过程中更改运算对象的地址。
是系统获得操作数的最快速途径。寄存器通常都是以他们可以保存的位数量来定义，举例来说，一个“8位寄存器”或“32位寄存器”
X86寄存器
有14个32位寄存器
通用寄存器
可用于传送和暂存数据，也可参与算术逻辑运算，并保存运算结果。它们还各自具有一些特殊功能。通用寄存器的长度取决于机器字长
32位的通用寄存器有8个：EAX,EBX,ECX,EDX,EBP,ESP,ESI,EDI，又可以分成2组，一组是数据寄存器(4个)，另一组是指针寄存器及变址寄存器(4个)
指令指针 EIP
EIP指向的是指令地址的段内地址偏移量，又称偏移地址(Offset Address)或有效地址(EA，Effective Address)
标志寄存器 EFR
有意义的主要有9位，其中6位是状态位，3位是控制位
OF溢出：运算结果超过当前运算位数所能表示的范围
IF：允许中断标志位。=1时可响应CPU外的中断请求
又称程序状态字(EPSW),用于存放条件标志、控制标志等
段寄存器
处理器特权级
管态/系统态
OS管理程序运行时处理器所处的状态。可使用系统中所有资源、访问整个存储区、使用处理器的全部指令
特权指令使用不当，将导致整个系统崩溃
清内存、关系统、设置时钟、分配系统资源、修改虚存的段表页表、修改用户的访问权限、管理IO指令，缺页处理，进程调度，时间中断，外部中断，系统调用
整数除以0，read系统调用
目态/用户态
只能访问自己的存储区域，不能执行特权指令，不能直接取用系统资源
命令解释，trap指令、跳转指令、压栈指令
访管指令可在用户态执行
sin（）函数调用
OS处理机的状态
DOS：不分态
Windows：0环管态 3环目态 12环预留
Linux, unix：00管态 11目态
存储系统
存储系统是指计算机中由存放程序和数据的各种存储设备、控制部件及管理信息调度的设备（硬件）和算法（软件）所组成的系统
制约计算机存储器设计的三个因素：容量、速度、价格
速度越快，每位价格越高，容量越小
为了权衡因素，目前主要采用存储器层次结构
从高到低
CPU内寄存器
高速内存 cache
介于主存和CPU之间的一级存储器，由静态存储芯片SRAM组成，容量小但速度被主存快很多。最重要的技术指标是它的命中率
组成
cache存储体
存放由主存调入的指令与数据
地址转换部件
建立目录表以实现主存地址到缓存地址的转换
置换部件
在缓存已满时按一定策略进行数据替换，并修改地址转换部件中的目录表
地址映像
是指某一数据在内存中的地址与在缓存中的地址两者之间的对应关系
全相联方式
直接相联方式
组相联映像方式
【计算】cache地址映射
主存储器/内存
计算机中所有程序的运行都是在内存中进行的，因此内存的性能对计算机的影响非常大
软件一般装在硬盘，需要调入内存中运行才能使用
分类
只读存储器 ROM
在制造ROM的时候，信息（数据或程序）就被存入并永久保存。这些信息只能读出，一般不能写入，即使机器停电，数据也不会丢失
ROM一般用于存放计算机的基本程序和数据，如BIOS ROM。其物理外形一般是双列直插式（DIP）的集成块
随机存储器 RAM
既可以读取，也可以写入数据
内存条（将RAM集成块集中到一起的一小块电路板）
os开机后被加载到这
区分物理存储器和存储地址空间
辅助存储器
堆栈
堆栈是C语言程序运行时必须的一个记录调用路径和参数的空间：包括函数调用框架，传递参数，保存返回地址，提供局部变量空间
基础知识
相关寄存器
堆栈操作
push：栈顶指针减少4个字节（32位 pop： 增加4个字节
执行的五个步骤
磁盘
磁盘是最常用的外部存储器，它是将圆形的磁性盘片装在一个方型的密封盒子里，这样做的目的是为了防止磁盘表面划伤，导致数据丢失
存放在磁盘上的数据信息可长期保存，且可以反复使用
读取数据时影响最大的是寻道时间
硬磁盘
有软磁盘硬磁盘之分，但软已经被淘汰了
硬磁盘的种类主要包括SCSI、IDE、以及现在流行的SATA等； 任何一种硬磁盘的生都要一定的标准； 随着相应的标准的升级，硬磁盘生产技术也在升级
结构
计算所在的磁盘号：用设备驱动程序
磁盘文件以盘块为单位读写
易失性存储
局部性原理
是指CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中
时间局部性temporal locality
空间局部性spatial locality
中断和时钟
中断
内核是由中断驱动的
唯一能让用户态到核心态的途径
中断是指计算机运行过程中，出现某些意外情况需主机干预时，机器能自动暂停正在运行的程序并转入处理新情况的程序，处理完毕后又返回原被暂停的程序继续运行。
程序性中断，输入输出中断，自愿性中断
程序中断：程序运行过程中，如果系统外部、系统内部或者当前运行程序本身出现紧急事件，处理机将立即暂停当前程序的运行，自动转入相应的处理程序(中断服务程序)，处理完再返回原来的程序运行
分类
中断
一般是异步的，由硬件随机产生，执行的任何时候都可能出现
可屏蔽中断
可由程序控制其屏蔽性的中断称为可屏蔽中断，处于屏蔽状态时，处理机将忽略该中断信号。
I/O设备发出的所有中断请求都属于可屏蔽中断
非屏蔽中断
与可屏蔽中断相对应，不能由程序控制其屏蔽性，处理机一定要立即处理的中断称为非屏蔽中断或不可屏蔽中断
通常是由一些紧急事件引发的中断，如断电、电源故障等情况，需要处理器立即处理
异常
一般是同步的，在（特殊or出错的）指令执行时，由CPU控制单元产生
内部处理完异常后不一定返回执行原来的指令，还可能是终止（除以零的指令
处理器探测异常
分类取决于处理器控制单元产生异常时保存在内核态堆栈eip寄存器中的值
故障
eip=引起故障的指令的地址
陷阱
eip=随后要执行的指令地址
异常中止abort
eip=？？？，放弃保存了
编程异常/软中断
采用中断的目的
提高计算机系统效率
维持系统可靠正常工作
满足实时处理要求
提供故障现场处理手段
中断相应
保护现场和恢复现场
时钟
时间戳
Linux两种定时测量
获得当前的时间和日期，包括time()，ftime()以及gettimeofday()等系统调用
是维持定时器，包括settimer()，alarm()等系统调用
定时测量是由基于固定频率振荡器和计数器的几个硬件电路完成的
x86的时钟
实时时钟RTC
能在IRQ8上发出周期性的中断
时间戳计数器TSC
可编程间隔定时器PIT
系统调用
见
三 进程管理
引入
程序：是为解决某一问题而设计的一系列指令的有序集合，是算法的静态描述
现代OS的重要特征是多个程序并发运行
前驱图
有向边
有向边<Vi , Vj>
执行
顺序执行：封闭环境，运行结果都可再现
并发执行：间断性，失去封闭，不可再现
进程概念
可并发执行的程序在一个数据集合上的一次运行过程，是系统进行资源分配和调度的一个独立单位
特征
动态、并发、独立、异步
进程映像：进程实体的组成
辨析
和程序的区别
最大区别是进程是动态的
一个程序可对应多个进程，一个进程可对应多个程序
和线程的区别
线程是进程的一个实体，是CPU调度和分配的基本单位。=轻量级进程
在实现了线程的操作系统中，进程是资源分配的基本单位，但线程是调度的基本单位，是系统中并发执行的单元
一个线程只能属于一个进程，一个进程可以有多线程
五种状态
释放资源：阻塞→就绪
挂起状态suspend
引入原因：终端用户需要、父进程请求、负荷调节的需要、os的需要
增加的状态
① 活动就绪->静止就绪，当进程处于未被挂起的就绪状态时，称为活动就绪状态；当挂起时，变为静止就绪状态，处于静止就绪状态的进程不接受调度。
② 活动阻塞->静止阻塞，当进程处于未被挂起的阻塞状态时，称为活动阻塞状态；当挂起时，变为静止阻塞状态，处于该状态的进程在其所期待的事件发生后，将从静止阻塞变为静止就绪。
③ 静止就绪->活动就绪，使用激活原语激活。
④ 静止阻塞->活动阻塞，使用激活原语激活
PCB进程控制块
记录了描述进程情况、控制进程运行所需的全部信息
os管理进程最重要的数据结构，PCB与进程同生死一对一
内容
进程标识信息
进程标识符PID,用户标识符，家族关系
除0号进程外，Linux所有进程都是PID为1的init进程的后代
进程调度信息
优先级，时间片
进程现场信息
处理机状态，寄存器信息，程序状态字PSW，栈指针
进程控制信息
链接指针
组织方式：链接方式、索引方式
进程控制
是对系统中所有进程实施有效的管理，是处理机管理功能的一部分。通常通过原语来实现
原语primitive：由若干个机器指令组成，用于完成某个特定功能的过程（PV操作是低级进程通信原语
在核心态运行常驻内存，一旦启动就不允许被中断
进程创建
进程图：描述进程家族关系的有向树 （比：前驱图）
父子进程
父进程撤销后子进程也会撤销
父进程子进程并发执行
典型事件
作业调度
用户登录
提供特定服务
因为包含太多写得笼统，不怎么考
应用请求
申请空白PCB→为新进程分配资源→初始化PCB→新进程插入到就绪队列
进程撤销/终止
kill(PID)
典型事件
正常结束后
异常终止后
外界干预
操作员或os干预
死锁
父进程请求
父进程被撤销
会很负责地给子进程找到新爸爸才撤销
进程阻塞、唤醒
典型事件
请求资源失败
等待某操作的完成
前驱进程尚未完成
进程无新工作可做
sleep(), wakeup()
sleep():入口→保存进程cpu现场信息到pcb/堆栈→状态变为阻塞态→pcb插入相应阻塞队列→转进程调度程序
wakeup():入口→阻塞队列中确定唤醒进程→状态变为就绪态→pcb移除阻塞队列并插入相应就绪队列
Linux进程管理
Linux进程实体
PCB(task_struct
prio进程的动态优先级
实时进程[0,99]
动态进程[100,139)
NI(nice)静态优先级
（-20，19）
正文段
进程要运行程序代码
数据段
用户数据段
目态执行的所有数据
系统数据段
管态执行的数据
进程创建
fork(), vfork() 用来创建一般进程
clone()可以有选择性地继承父进程的资源，用来创建轻量级进线程
返回：<0 出错 =0 从子进程返回，现在正执行新创建的子进程 >0从父进程返回，现在执行父进程，返回值=新子进程的PID
进程终止
exit()系统调用：do_exit()
进程同步
间接制约关系/互斥共享
进程同步：相互合作的进程需要按一定的先后顺序执行，以顺利完成任务
临界资源
一次仅允许一个进程使用的资源称为临界资源。
物理设备（输入机打印机）和软件资源（公用变量、数据、表格、队列）都属
多个进程在共享临界资源时必须以互斥方式共享
临界区
每个进程中访问临界资源的那段代码
若一个系统中共有5个并发进程，共享一个变量A，则变量A的相关临界区是由（ 5）个临界区构成的
do{ 进入区 临界区 退出区 剩余区 }while(TRUE)
进入区：置于临界区之前，用于检查临界资源使用状态
退出区：完成工作的代码
剩余区：和临界资源无关的
同步机制原则
空闲让进
忙则等待
有限等待
有限指的是时间
让权等待
进程不能进入临界区时应立即释放CPU
解决进程互斥
硬件方法
禁止中断
系统只有在时钟中断或其他中断处理才会发生进程切换。如果把中断禁止了就可以避免切换
把【临界区】前后换成【禁止中断】和【开放中断】
实现简单，但有两个缺点
将禁止中断的特权下放到普通用户可能会增加系统风险
只能用于单处理器系统，一个进程只能禁止该CPU的中断不能禁其他个
利用专用机器指令
多处理器系统提供了TSL，Swap指令（都是原子性执行）
Test and Set Lock
CPU在执行TSL指令时会封锁内存总线，以禁止其他CPU在指令执行好之前访问内存
代码
Swap
代码
可以相对简单地解决多处理系统的进程互斥，但
不遵循“让权等待”
可能存在饥饿现象：一个进程退出临界区后，如果有多个进程在等待，进入的下一个是随机的，可能有些倒霉的进程一直进不去
软件方法
不正确的软件算法
严格交替算法
能实现互斥，但违背了空闲让进
1+bool数组
甚至互斥都保证不了……
Peterson算法
针对双进程互斥，很容易推广到n个进程的互斥问题
面包店算法
按取号和名字排列顺序
缺点：算法复杂，正确性难以证明，上升到多进程时更加麻烦
锁机制
简单方便地实现多进程的互斥
开锁和关锁由系统提供的2个原语实现
信号量机制
（Dijkstra提出的……哲学家、银行家、SPF也是……
整型信号量机制
后继进程在执行相关工作前，应先执行信号量的P操作
记录型信号量机制
信号量集机制
实现互斥
经典问题
生产者-消费者
哲学家进餐
读者-写者
理发师
如果理发店中没有顾客在等待理发，则理发师执行wait(cust ready)将进入睡眠状态
管程机制
进程调度
层次
低级调度/进程调度（发生频率最高
不能都用时间片轮转
中级调度/对换调度
高级调度/作业调度
功能
排队程序
分派程序
上下文切换程序
（简而言之，CPU调度+CPU切换
方式
非抢占方式
抢占方式
抢占原则
时间片
优先权
剩余运行时间
………
实现机制
内核完全不可抢占：传统unix
内核部分可抢占：linux
内核完全可抢占：Solaris，win2000
选择时该考虑的
系统设计目标
调度的公平性
资源均衡利用
合理的系统开销
性能评价指标
CPU的利用率
40~90%
系统吞吐量
CPU利用率高+系统开销小
周转时间和带权周转时间
响应时间
交互式系统
对截止时间的保证
实时系统
可能会调度的时机
时间片用完
进程本身发生转换：终止、等待
从系统调用返回目态
从中断处理返回目态
就绪队列出现更高优先级的进程
算法
FCFS 先来先服务
对长作业有利，对短作业不利；
平均周转时间可能较长；
没有考虑任务的紧迫性
SJF 短作业优先
对长作业不利（饥饿状态）；
对紧迫作业不利
估计运行时间不准，难以真正做到短作业（进程）优先
HRRF 高响应比优先调度
响应比=1+等待时间/要求服务时间
短长作业都兼顾了
但每次调度都需要重新计算所有作业的响应比，系统开销大
不能保证紧急任务及时处理
优先级调度
静态优先级
优先级在整个生命周期中不变
nice(), setpriority()
动态优先级
初创时赋一个优先级初值，运行期间动态调整
动态优先级=（动态优先级/2）取整+静态优先级
升等级
线程I/O操作完成；
线程信号量或事件等待结束；
前台进程中的线程完成一个等待操作；
线程处于就绪状态超过一定时间，但没能进入运行状态
降等级
运行完一个时间配额后降级
时间片轮转
多级队列，多级反馈队列
进程通信
指进程之间直接以较高的效率传递较多数据的信息交互方式
分类
共享存储器系统通信
过程：申请共享存储分区→将共享存储分区映射到本进程地址空间中→进行数据读写→解除共享存储分区映射→删除共享存储分区
最大特点：没有中间环节，进程直接访问虚拟地址空间
没有进程同步机制
消息传递系统通信
进程间的数据交换是以消息（或报文）为单位。程序员直接利用系统提供的一组通讯命令（原语）来实现通信
接收方和发送方之间有明确的协议和消息格式
分类
直接通信
send(), receive()
send
发送信息后被阻塞直到消息被接收
or立即接收消息并继续执行
receive
消息没到：接收进程被阻塞直到消息到达、继续运行但放弃接收
消息到了：立即接收并继续执行
间接通信
利用一个共享的中间实体(信箱)实现信息交换
信箱头：信箱名、信箱大小、创建者、存取信件指针、信件数量等 信箱体：存放消息
管道通信
管道
概念：用于连接一个发送进程和一个接收进程，以实现它们之间通信的共享文件（又称pipe/FIFO文件
文件的写入写出严格遵循先进先出，不支持文件定位
实现机制
无名管道
int pipe(int fd[2] fd[1]写入端，fd[0]读出端，用于父子/兄弟通信
有名管道
int mkfifo(const char* pathname, mode_t mode) 用于任意进程通信（FIFO通信
注意问题
读写操作必须互斥
读写操作必须同步
双方必须同时存在
客户-服务器系统通信（C/S模式
客户端提出请求，服务器提供服务
套接字socket
是一条通信线路两头端口的抽象表示
流程
消息缓冲队列通信
进程死锁
如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程是死锁的（Deadlock）
如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃
死锁的必要条件：四个同时具备才会发生
互斥条件（这个条件无法破坏）
涉及的资源是非共享的
请求和保持条件
不能强行剥夺进程拥有的资源
不可抢占条件
进程在等待新资源时，依然占者已有资源
循环等待条件
必然存在一个循环链，链中的每一个进程已获得的资源同时被链中的下一个进程所请求
【计算】不死锁的最少资源数：资源数(进程数-1)+1
处理死锁
预防死锁
设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个
破坏请求和保持条件
静态分配资源
bug：可能会推迟运行，甚至产生饥饿现象
进程在没资源的时候才能申请资源
破坏不可剥夺条件
破坏循环等待条件
按序分配资源
避免死锁
在资源的动态分配过程中，用某种方法防止系统进入不安全状态
银行家算法
检测死锁
通过检测机构及时地检测出死锁的发生，然后采取适当的措施，把进程从死锁中解脱
资源分配图
检测算法：Coffman算法
解除死锁
常用方法是撤销一些进程，回收他们的资源，然后分配给已处于阻塞状态的进程
抢占资源
线程机制
线程是隶属于进程的一个实体，是比进程更小的一个运行单位。
线程的资源
一个线程ID
一组寄存器
堆栈
内核栈
用户栈
一个私有存储器
线程控制块TCB
线程vs进程
进程是资源分配和拥有单位，线程基本不拥有资源，同一进程中所有线程共享进程所拥有的资源
线程开销<进程开销
线程管理
就绪态，运行态，阻塞态，终止态
控制：创建，终止，阻塞，唤醒
实现机制
多线程系统
利用线程并行执行矩阵乘法运算
web服务器利用线程响应http请求
GUI调试程序用不同的线程分别处理用户输入、计算和跟踪等操作
用户级线程ULT
完全由用户应用程序实现
POSIX Pthreads；Mach C-threads
优点
线程的调度及切换开销小
调度由应用程序完成，可以选择最适当的算法
可运行在任何操作系统上
内核级线程KLT
完全由OS内核实现的线程机制
Windows 2000/xp，Solaris，Digital UNIX
优缺点
核心可以同时调度同一进程的多个线程，核心例程是多线程的
同一进程内的线程切换调用内核，系统开销大
二者相结合的
内核支持内核级线程，线程库支持用户级线程
Solaris
四 存储器管理
存储器管理
子主题
计算机开机后os最终被加载到RAM
权衡关系：容量、性能、价格
性能往高性能靠，容量价格往廉价靠
【计算】有效访问时间
功能
内存分配与回收
用到的数据结构：主存资源信息块、等待队列、空闲区队列、主存分配程序
制定策略
分配
放置
调入
淘汰
方式
静态
动态
地址映射
将程序地址空间中使用的逻辑地址变换成主存中的物理地址的过程，称为地址映射
物理地址
逻辑地址
可能是一维线性的连续空间，也可能是二维非线性空间
内存的共享和保护
共享：多个进程共享share访问某一段内存的程序或数据
保护
避免各进程互相干扰，对进程的程序和数据进行保护
实施方法：界地址保护
上下界保护
基地址、限长防护
内存扩充
必要性：主存容量不满足应用需求
可行性：局部性
时间局部性（不久的将来再次访问该指令/数据）
空间局部性（马上将访问其附近的指令/数据）
实现方法
程序的全部代码和数据存放在辅存中；
程序当前执行所涉及的那部分程序代码放入主存中；
程序执行时，当所需信息不在主存，
由操作系统和硬件配合来从辅存中调入信息，程序继续执行。
链接与装入
链接Link
静态链接
在执行前
装入时动态链接
运行时动态链接
装入Load
绝对装入
静态重定位装入
动态重定位装入
这两个的分类都是依据进行的时机
连续存储分配
单一连续分配
最简单的一种存储管理方式，但只能用于单用户、单任务的OS中。
将内存分为系统区（os，在内存低端）和用户区（在内存高端）
作业一旦进入内存，就要到它运行结束才能释放内存
固定分区分配
最早使用的一种可运行多道程序的存储管理方法
使用分区分配表和相应的分配回收算法实现，每个分区只能装入一个程序
内存碎片：在已分配区之间存在着的一些太小而难以利用的空闲区，称为碎片。碎片影响主存的利用率
动态分区分配
分区大小和数量都可以变化
回收的时候相邻分区可以合并成较大的分区
拼接：移动主存中已分配区，使本来分散的小空闲区连成一个大的空闲区
基于顺序搜索的
首次适应算法
是将程序装入到主存中足够装入且地址最低的空闲区中
空闲区按地址由低到高排序
尽量利用主存低地址空闲区，尽量在高地址保留大空闲区
循环首次适应算法
or下次适应算法
在为作业分配内存空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能满足其大小要求的空闲分区为止
最佳适应算法
将程序装入到主存中与其大小最接近的空闲区中
空闲区按大小由小到大排序
尽量利用存储器中小的空闲区，而尽量保存大的空闲区
最坏适应算法
是将程序装入到主存中与其大小差距最大的空闲区中。
空闲区按大小由大到小排序
尽量利用存储器中的大空闲区，使剩余空闲区较大。
基于索引搜索的
快速适应算法quick fit
将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样系统中存在多个空闲分区链表
伙伴系统Buddy
无论已分配分区或空闲分区，其大小均为2的K次幂，K为整数，l≦k≦m,其中：2l表示分配的最小分区的大小，2m表示分配的最大分区的大小。
若存在2i+1的空闲分区，则把该空闲分区分为相等的两个分区，这两个分区为一对伙伴
ps注意是0开头还是1
哈希算法
利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律
动态重定位分区分配
与动态分区分配算法基本上相同，差别仅在于：在这种分配算法中，增加了紧凑的功能
真正访问地址=相对地址+重定位寄存器中地址
覆盖
早期os中应用，感兴趣的了解
其目标是在较小的可用内存中运行较大的程序。常用于多道程序系统,与分区存储管理配合使用。
常用功能存内存，不常用功能存外存（覆盖文件），需要用的时候再调入
不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。(即不同时用的模块可共用一个分区)
对换
将暂时不用的某个进程及数据（首先是处于阻塞状态优先级最低的，根据系统的采用算法决定）部分/全部从内存移到到外存（备份区或对换区，采用连续分配的动态存储管理方式）中去，让出内存空间，同时将某个需要的进程调入到内存中，让其运行。
回收算法
离散存储分配
页式存储管理
虚页实页
页面page
程序的地址空间被等分成大小为2^k的片段，这些片段称为页面，虚页
页框frame
物理内存也被等分成大小相等的片，称为主存块、物理块、页框，又称为实页
页面大小=页框大小
逻辑地址
页面大小决定页内地址的位数，位数决定逻辑地址页面的总数
逻辑地址=页号&位移量（&号是连接符号，是将页号作为逻辑地址的最高位）
【计算】页号和页内地址
页表page table
系统为每个进程设置了一张页号到物理块号的映射表，称为页表。页表项PTE包含页号和块号，但是实际只存储块号
【计算】PTE，存储
子主题
如果页号超过页表长度，则产生“地址越界”中断，于是停止指令的执行，操作系统进行越界中断处理
段式存储管理
段segment
逻辑空间分为若干个段，每个段定义了一组有完整逻辑意义的信息（如主程序Main（））。内存空间为每个段分配一个连续的分区
段的长度由相应的逻辑信息组的长度决定，因而各段长度不等
程序的分段是在用户编程时决定
优点
方便编程
信息共享
易于实现段的共享，对段的保护也十分简单
信息保护
缺点
主存空间分配比较麻烦。
容易在段间留下许多碎片，造成存储空间利用率降低。
由于段长不一定是2的整数次幂，因而不能简单地像分页方式那样用虚拟地址和实存地址的最低若干二进制位作为段内地址，并与段号进行直接拼接，必须用加法操作通过段起址与段内地址的求和运算得到物理地址。因此，段式存储管理比页式存储管理方式需要更多的硬件支持。
段式逻辑地址
段表
一张映射表，每段一个表项：段号，段长，段基址
【计算】地址映射
eg
注意地址可能会超出范围（地址越界）
【计算】有效访问时间
段页式
在段式存储管理中结合分页存储管理技术，在一个分段内划分页面，就形成了段页式存储管理
用户程序先分段，每个段内部再分页
逻辑结构
在页式、段式存储管理中，为获得一条指令或数据，须两次访问内存；而段页式则须三次
页面置换算法
clock算法
虚拟存储系统
指具有请求调入功能和置换功能，能够利用外存储器的空余空间从逻辑上对内存容量进行扩充的一种存储器系统
进程的局部性
时间局部性
若某个指令/数据被访问了，那么在不久的将来将会再次访问
程序的循环结构导致的
空间局部性
若某个指令/数据被访问了，那么它附近的指令/数据可能马上被访问
程序顺序执行的方式和线性数据结构（如数组）所导致的
虚拟存储器
将进程调入的一次性或者整体性改为多次性
将进程的驻留性改为置换性
容量
虚拟容量
指令的地址长度
实际容量
外存+内存
请求分页存储管理
虚拟存储器只是把一部分程序内容装入内存，而把其他的部分放置在硬盘中。执行的部分
页面调入时可能还需要考虑置换
页式系统
简单页式系统
装入一个程序的全部页面才能投入运行
请求页式系统
装入一个程序的部分页面就能投入运行
扩充页表
P: 该页是否在主存
A: 页面被访问的情况
M: 页面装入内存后是否被修改过，供页面置换时参考
缺页处理
页面置换策略
最佳置换算法OPT
淘汰那页是以后不会再用的/最长时间才会用到的
是一个理论算法，无法实现
先进先出法FIFO
淘汰最早进入主存的那一页
这货最容易缺页
Belady现象
最近最久未使用法LRU
最近最少使用法LFU
时钟算法CLOCK
抖动 thrashing
在主存和辅存之间的频繁页面置换的现象，这种情况会导致系统效率急剧下降
五 设备管理
功能
设备分配
数据结构，分配算法
缓冲管理
目的、实现机制
设备管理
设备驱动+中断处理
I/O系统
分类
按数据传输率分
高速设备：≥几百万字节/秒
中速设备：几千到几十万字节/秒
低速设备：几个到几百个字节/秒
按信息交换的单位分类
一次I/O操作的最小数据传输单位
块设备
以数据块为单位来传送数据的设备
eg：磁盘，
特点
信息交换的单位是等长数据块
可寻址
IO控制采用DMA方式
信息存储设备
字符设备
以字符为单位
eg：终端，打印机
特点
信息交换的单位为字符或字节；
不可寻址；
I/O控制采用中断驱动方式
信息输入输出设备
按设备共享属性分
独占设备
共享设备
虚拟设备
按工作特性分
存储设备
IO设备
设备管理器
I/O设备一般由机械部件和电子部件两部分组成，设备控制器就是电子部件的部分
基本功能
接收和识别命令
数据交换和缓冲
标识和报告设备的状态
地址识别：设备选中
差错控制
组成
设备控制器与CPU间的接口：系统接口
接口寄存器类型
数据寄存器
地址寄存器
控制寄存器
设备控制器与设备间的接口：设备接口
IO通道
是一种特殊的处理机，它控制设备与内存直接进行数据交换
与一般处理机的区别
通道的指令类型单一，主要局限于与I/O操作有关的指令；
通道没有自己的内存，是与CPU共享内存
分类
字节多路通道
分时控制，多台低速中速设备
数组选择通道
串行控制，多台高速
数组多路通道
分时控制，多台高速
通道程序
保存在主存中，由一系列通道指令构成
IO系统结构
总线型
用于微机IO系统
总线：是一组线和一组严格定义的可以描述在线上传输信息的协议，这一组线用来连接多个设备，这种连接称为总线
通道型
用于主机IO系统
I/O控制方式
程序IO控制
循环测试IO方式
中断驱动IO控制
常用于字符设备的IO控制
DMA 直接存储器存取
常用于块设备的IO控制
DMA传送过程
DMA预处理（CPU完成）→DMA控制器完成设备与主存之间的数据传送→CPU响应中断进行后处理（CPU完成）
不同： 对CPU的中断频率不同 数据传输控制不同
IO通道控制
是一种以内存为中心，实现设备和内存之间直接交换数据的控制方式
通道的运算控制部件
通道地址字 CAW：记录下一条通道指令的地址，其功能类似于CPU的指令计数器
通道命令字 CCW：记录正在执行的通道指令，其作用相当于CPU的指令寄存器
通道状态字 CSW：记录通道、控制器、设备的状态，包括I/O传输完成信息、出错信息、重复执行次数等
【计算】中断时间比率
缓冲管理
缓冲是在两种不同速度的设备之间传输信息时平滑传输过程的常用手段
作用
缓和CPU与IO设备之间的并行性
提高CPU和IO设备间的并行性
减少对CPU的中断频率，放宽对CPU中断响应时间的限制
实现机制
单缓冲
T=max(C,T)+M
双缓冲
T=max(C+M,T)
循环缓冲
4是空缓冲区，1是满缓冲区
缓冲池
组成
缓冲队列：由内存一组缓冲区组成，由系统统一管理。包括空缓冲队列emq、输入队列inq、输出队列outq
工作缓冲区：进程正在使用的缓冲区。包括收容输入、提取输入、收容输出、提取输出工作缓冲区
使用
getbuf(type)申请缓冲区，putbuf(type, number)释放缓冲区
void Get_buf(type){ wait(Rs(type)); wait(mutex(type)); B(number)=takebuf(type); signal(mutex(type)); } void Put_buf(type,number){ wait(mutex(type)); add_buf(type,number); signal(mutex(type)); signal(Rs(type)); }
块缓冲
UNIX系统的，预先缓存、延迟发送
IO软件
层次
1）用户层 I/O 软件。实现与用户交互的接口，用户可直接调用该层所提供的、与 I/O 操作有关的库函数对设备进行操作。
2）设备独立性软件。用于实现用户程序与设备驱动器的统一接口、设备命名、设备的保护以及设备的分配与释放等，同时为设备管理和数据传送提供必要的存储空间。
3）设备驱动程序。与硬件直接相关，用于具体实现系统对设备发出的操作指令，驱动 I/O 设备工作的驱动程序。
4）中断处理程序。CPU 先保护被中断进程的 CPU 环境，再转入相应的的中断处理程序进行处理，处理完毕后 CPU 再恢复被中断进程的现场，返回到被中断的进程。
独立于设备的软件
设备独立性
是指用户在程序中使用的设备与实际使用的设备无关，即在用户程序中仅使用逻辑设备名。也称为设备无关性
ls -l /dev
优点：提高设备分配的灵活性，容易实现IO重定向
实现：用逻辑设备表LUT
逻辑设备名、物理设备名、设备驱动程序入口地址
方式：给整个系统一张表or给每个用户一张表
~软件
功能
实现设备命名及映射
提供设备保护,存取控制检查
提供与设备无关的逻辑块
实现缓冲技术
出错处理
设备驱动程序
功能
1)接收由上层软件发来的抽象命令，将其转换为具体要求,并插入请求队列。如打印机驱动程序需要将打印数据从存储编码(内码）转换成输出编码（字库) 2)完成IO操作的初始化工作:检查用户IO请求的合法性，了解I/O设备的状态，传递有关参数，设置设备的工作方式。 3)发出IO命令，启动IO设备。 4)及时响应由控制器或通道发来的中断请求。(5)根据用户的IO请求，自动地构成通道程序。
特点
(1)驱动程序是请求I/O的进程与设备控制器之间的一个通信和转换程序。 (2)驱动程序与设备控制器和I/O设备的硬件特性紧密相关，因而对不同类型的设备应配置不同的驱动程序。 (3)驱动程序与IO设备所采用的I/O控制方式紧密相关。(4)由于驱动程序与硬件紧密相关，因而其中的一部分代码必须用汇编语言书写。 (5)驱动程序应允许可重入。
处理过程
(1）将抽象要求转换为具体要求 (2）对服务请求进行校验 (3）检查设备的状态 (4）传送必要的参数 (5)启动IO设备
设备分配
设备标识
系统以某种原则为每台设备分配唯一的号码，用以标识该设备，成为设备绝对号/物理设备名
设备分配的数据结构
设备控制表DCT
每个设备一张表
控制器控制表COCT
通道控制表CHCT
系统设备表SDT
整个系统一张表
设备分配算法
先来先服务
优先级高者优先
设备分配过程
分配设备→分配控制器→分配通道
SPOOLING系统
在联机情况下实现的同时外围操作称为SPOOLing，或称为假脱机操作
设计思想：预输入、缓输出
典型应用：共享打印机
请求打印时：①在输出井申请一个空闲磁盘分区，并将要打印的数据送入；②再为用户进程申请一张空白的用户请求打印表，打印要求填入，再将表挂到打印请求队列上
Linux中断处理机制
六 文件系统
文件和文件系统
文件
文件是具有符号名的、在逻辑上有完整意义的一组相关信息项的有序集合。
通常存在外存
unix和linux系统把设备也作为特殊文件处理
linux 把外部设备当作特殊文件，它们都放在目录（./dev）中
基本单位：可以是字符/字节，也可以是记录
分类
按用途分类
系统文件
库文件
用户文件
按保护级别分类：只读文件、读写文件、只执行文件和不保护文件
按存取方法分类：顺序存取文件和随机存取文件
实际操作系统中文件分类：Window、Unix和Linux都有普通文件和目录文件，Unix和Linux 系统还有特殊文件
目录文件由文件说明信息组成
文件系统
指被管理的文件、对文件进行管理的一组软件集合以及实现管理功能所需要的数据结构的总体。
功能
用户角度
按名存取
系统角度
文件存储空间管理
文件目录管理
文件地址映射
文件读写管理
文件共享和保护
文件操作
创建、删除、打开、读写……
结构
逻辑结构
面向用户的文件组织结构和构造方式
设计原则
操作简单易用
提高文件信息的检索速度
方便文件内容的修改
数据空间紧凑降低文件的存储费用
系统灵活性
分类
有结构文件 / 记录式文件
整个文件由若干条记录构成
用户程序与文件系统交换信息的基本单位：记录
为了能唯一标识一个记录，必须在记录的各个数据项中确定关键字key
数据组织
数据项
记录
文件
分类
顺序文件
最常见最简单的文件逻辑结构
文件较大时顺序文件的顺序存取速度最快
按长度分
定长记录文件
变长记录文件
按是否按key排序
串结构
通常按记录存入的先后排序
顺序结构
按key，可设定从大到小、从小到大
可以用折半查找、插值查找等，效率高
优缺点
顺序存储时效率高，但不利于文件的查找、动态添加、删除
索引文件
为逻辑文件的信息建立一张索引表，一条逻辑记录一个表项，表项存放key、长度、起始位置
所以逻辑文件不用再保存长度了
优缺点
可以随时访问，利于文件的增加删除
但索引表增加了存储开销，索引表的查找策略对文件系统的效率影响大
顺序索引文件
讲顺序文件的所有记录分成若干个组，为每组的第一条记录在索引表中建立一个索引项，表项存放key和指针
分组里面的key没有排序，但组间的key是排序的
太大的文件可以为它创建多级索引，索引表套娃索引表
优缺点
克服了效率，但还存在存储问题
直接文件
建立key和对应物理地址的对应关系，使用key就可以直接找到物理地址
散列文件Hash
最典型和广泛的直接文件
通过hash函数对key进行转换，转换结果直接决定记录的物理地址（的指针）
优缺点
存取速度高，但可能使不同的key得到相同的函数值，造成冲突
无结构文件 / 流式文件
由一组相关信息组成的有序字符流
基本单位：字节
访问是用读/写指针指出下一个要访问的字符
Linux·、Unix、Windows中所有文件都被看做流式文件
目前绝大多数文件系统采用的逻辑结构都是流式文件。
物理结构
文件在存储介质上的组织方式
物理块/磁盘块/簇
是磁盘上的一组连续扇区，是文件分配和传输信息的基本单位
大小一般是2^n个，和逻辑记录的大小无关
为管理方便，一般把文件逻辑信息划分为与物理块大小相等的逻辑块
分类
连续文件/顺序文件
最简单的磁盘空间分配策略，但分配前要说明文件的磁盘空间大小，然后查找系统有没有足够大的连续空间
优缺点：访问速度快、可随机存取，但会产生磁盘碎片、文件修改困难
链接文件
用链接指针将这多个离散的磁盘块链接起来
隐式链接
在每个磁盘块的最后一个单元设置一个链接指针
文件最后一个磁盘块的链接指针放的是文件结束标志
串联文件
最大缺点：只能顺序存取。文件容易丢失，可靠性差
显式链接
链接指针统一存放在一张显示的链接表(FAT，文件分配表)
FAT
以磁盘上的物理块为顺序→表项数目由磁盘块的数目而定
【计算】FAT大小
每个磁盘块号大小取半个字节的整数倍
优缺点
检索速度快、支持随机存取
但FAT占内存空间，随机存取效率降低
链接文件
优缺点
克服了连续文件的不足之处，但文件的随机访问系统开销较大。适应于顺序访问的文件
索引文件
单极索引
多级索引
将索引表离散存放在多个索引块中，再为这些索引块建立一级索引，这样就形成了两级索引文件。如果文件非常大时，还可使用三级、四级索引文件
混合索引
【计算】最大文件
子主题
优缺点
既适应于顺序访问，也适应于随机访问
存取
文件的存储结构不仅与存储介质的物理特性有关，还与文件的存取方法等因素有关
顺序存取
按文件中的记录顺序依次进行读/写操作的存取
随机存取
打开文件：把指定文件内容复制到内容指定区域，把FCB从磁盘拷贝到内存
当用户执行:“In f1 f2”命令后，系统会为f2文件建立一个目录项，并分配1块磁盘块存放f2的内容
目录管理
os对目录管理的要求
按名存取
提高目录的检索速度
允许文件重名
允许文件共享，但也应采取安全措施防止越权使用
文件
文件体
文件本身的内容
文件控制块FCB, File Control Block
用于描述和控制文件的数据结构，保存系统管理文件所需要的全部属性信息
文件存在的唯一标识
基本内容
基本信息
文件名、用户名、文件类型、文件长度、逻辑结构物理结构
不放索引表
存取控制信息
描述文件的存取控制权限
使用信息
建立时间，上次存取的时间，当前使用状态信息，共享链接计数等
索引节点/i节点
文件系统FCB中，除文件名以外的描述信息单独形成的数据结构
i节点在文件系统中的作用： what: 记录文件的权限和属性（除文件名以外 所有描述信息 一个文件占用一个inode 同时记录文件数据所在的block号码 why： 减少目录文件大小（） 减少平均磁盘启动次数 大大提高目录检索效率
分类
磁盘索引节点
内存索引节点
目录结构
单级目录
两级目录
将文件目录分为主文件目录和用户文件目录
多级目录
两级目录结构加以推广，允许用户文件目录再建立下级子目录，由此形成了多级目录结构。在树形目录中，主目录则称为根目录，目录树中的非叶节点均为目录文件（又称子目录），叶节点为数据文件
目录检索技术
线性检索
Hash
建立一个Hash索引文件目录，当用户给定文件名之后，直接把它转换为文件目录的索引值，再利用该索引值查找目录
但hash无法检索带有特殊字符的文件名，而且不同文件名可能会转换成相同的hash值
解决：hash值上再加上一个常数形成新的索引值，然后重新查找
存储空间管理
空闲表法
为外存上的所有空闲分区建立一张空闲表，每个空闲区占一个表项，再将所有空闲区按其起始盘块号递增的次序排列
因此最适合连续结构的文件存储
空闲区
序号
起始盘块号
空闲盘块数
空闲块链表法
空闲盘块链
磁盘的每一个空闲盘块中存放一个指针，指向另一个空闲盘块，这样磁盘上的所有空闲块链接在一起形成一个链表
空闲盘区链
每个空闲盘区包括若干个连续的空闲盘块
位示图
分配
顺序扫描位示图，找到一个或一组0→将二进制位转换成对应的盘块号 b=n(i-1)+j →修改位示图，使map[i,j]=1
回收
i=(b-1)DIV n+1, j=(b-1)MOD n+1 →修改位示图
成组链接法
把所有空闲磁盘块按照固定数量分成若干组
将每组（第1组外）的总块数及相应的块号记录在前一组的最末块，第1组的将这些信息记录在空闲盘块中，放在超级块里
共享
指一个文件可以被多个授权用户使用
分类
基于索引节点的共享/硬
硬链接
基于符号链接的共享/软
为共享文件创建一个link类型的新文件
区别
文件属性
保护
磁盘调度
一次磁盘读写需要的时间
寻道时间
=启动磁头臂消耗的时间+跨越磁道的总时间m*n
延迟时间
通过旋转磁盘，使磁头定位到目标扇区所需要的时间。设磁盘转速为r（单位：转/秒，或转/分），则平均所需延迟时间TR = (1/2)*(1/r) = 1/2r
传输时间
从磁盘读出或向磁盘中写入数据所经历的时间，假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节数为N，则传输时间TR = (b/N) * (1/r) = b/(rN)
算法
先来先服务算法（FCFS）
最短寻道时间优先算法（SSTF）
这种算法会产生“饥饿”现象
扫描算法，电梯算法（SCAN）
循环扫描算法（CSCAN）
【计算】扇区的物理地址
【计算】磁盘传输速率