理解操作系统原理

操作系统是为用户提供计算机的某种模型的软件。硬件涉及很多实现相关的细节，操作系统管理硬件资源，从而向应用程序呈现一个清晰和统一的接口。

也就是说，操作系统在硬件与应用程序间建立了一层抽象，是为了控制复杂性而设立的。最重要的是，操作系统提供了进程、地址空间和文件系统三大抽象。

历史

在早期的真空管时代（约1945-1955），连汇编语言都没有，编程是通过接驳缆线完成的，更没有操作系统。

到晶体管时期（约1955-1965），已经可以用穿孔卡片作输入媒介，人们使用计算机的方法为先把程序（通常为Fortran或汇编）打在卡片上，然后交给操作员，过段时间再来领取打印的结果。由于读卡片和打印结果是较慢的机械操作，不能善用处理器资源，所以人们开始使用批处理系统：用一台便宜的机器把一批卡片的内容写到磁带，用一台较强大的机器进行磁带指定的计算再把结果写到另一磁带，又一台便宜的机器打印输出磁带指定的内容。这样，三台机器可以流水线式地同时运作，它们的固定程序可视为操作系统的雏形，让I/O与计算可同时进行正是后来的操作系统的出发点。

到集成电路时期，随着存储空间和计算速度的增长，在内存同时驻留多个程序成为可能，把卡片机视为联机的外部设备后也不再需要用三台机，于是产生了多道程序设计，I/O密集程序在I/O时CPU密集程序可以用CPU以充分利用I/O和计算能力，分时更可降低响应时间让多个可用户交互式地使用。相应地，操作系统也变得复杂多了，OS/360和MULTICS就因为过于雄心勃勃而在商业上失败，由于为各种机器编写的操作系统要解决很多共同的问题，许多操作系统如各种类Unix在不同的机器间共享大部分代码。

到超大规模集成电路时期，个人计算机兴起，但软件还未被视为有利可图的，Digital Research从Intel获得了CP/M的版权后让它成为各种微型计算机的主流操作系统，但IBM为其新机器物色操作系统时前者不够重视，导致微软公司仅用$75000从Seattle Computer Product买回的DOS胜出，随着IBM机的流行DOS成为PC的新霸主，后续的Windows系列（95前基于DOS）继承了其流行度。

编写一个操作系统本身也不是特别难，但因为有很多程序依赖于它，不能随便变更，而且需要支持大量硬件，所以往往长时间地演化。

硬件知识复习

计算机可视为由CPU、内存、I/O设备（如磁盘、显示器、键盘、USB设备）的控制器通过总线连接而成（实际上现代的机器有多条总线以匹配不同速度的设备，如高速缓存、局部、内存、PCI、USB、SCSI、IDE）。

CPU

基本的操作模式可视为重复取指令、解码并确定类型与操作数、执行（但实际上可能会用流水线、超标量之类的方式以提高效率）。不同CPU有不同的指令集。现代的计算机有两种运行模式：内核态和用户态，由某个寄存器（程序状态字决定）。在内核态可以执行任何机器指令，在用户态只可以执行部分“较安全”的机器指令。

由于内存（DRAM）与CPU相比较慢，CPU设有一些寄存器（SRAM），其中一些有专门用途：

程序计数器（PC）保存下一条要取的指令的内存地址
堆栈指针（SP）指向当前栈顶，栈通常用于保存过程调用相关的数据
程序状态字（PSW）包含条件码（由比较指令设置）、模式等控制位
通用寄存器给程序用于保存中间结果

由于再提高单个CPU速度会导致发热快速增长，因此现在一些机器通过处多个CPU并行工作以提高性能。多处理器会导致很多新的问题：

处理器与内存的对应（每个CPU有私有内存、全部CPU共享内存、还是有的内存分配给特定CPU而其余共享）
大量CPU会使单一总线冲突过多，需要其它总线结构（如交叉开关或交换网络）
各CPU地位是否对等
- 主从式的问题是主CPU可能成为瓶颈
- 对称多处理的问题是操作系统维护数据结构的一致性较困难（过多的保护则可能浪费时间甚至导致死锁）一些CPU有多于一套控制单元，它们称为多核的，各个核可能有自己的高速缓存和运算器也可能是共用的。

存储器

典型情况下，在存储设备中，寄存器、高速缓存、内存、磁盘到磁带，容量递增、平均价格递减、访问速度递减，其中后两者是非易失的。这构成了一个缓存阶梯，尽可能在前面的设备存放常用的数据，只有在访问不常用的数据时才用慢设备，从而获得合理的性价比。高速缓存与内存之间的缓存通常由硬件控制。

内存又分为：

随机访问存储器（RAM）是易失的，须要不断用电刷新
只读存储器（ROM）是非易失的，可用于存放自检和引导程序，内容在出厂时已经固定或者可以擦写但擦写较慢（如EEPROM）
CMOS保存时间和少量配置信息（如启动装置），易失（但通常有电池供电）

另外一些设备也用于保存数据，它们通常视为I/O设备

磁盘是机械装置，一个磁盘有若干个盘片，沿同一条轴旋转（速度常见5400RPM、7200RPM或10800RPM），一个盘片可以有至多两个盘面。磁盘还有一排机械臂可沿半径方向移动，它在每个盘面外有读写头。每个读写头可读写的环状区域称为磁道，每个磁道又等分为若干扇区，作为选取的基本单位。可见，要随机读取一个扇区，需要先移动机械臂（寻道，通常是最花时间的）、然后等所需扇区转到读写头下（旋转延迟）、最后才读取扇区内容（传输延迟，通常最快）。每个磁道上第0个扇区与上一磁道上第0个扇区有偏移（柱面斜进）以便连续读多个磁道；扇区的编号也不一定连续，在和控制器缓冲区较小且到内存的复制过程较慢时，交错编号可能有助优化读连续编号扇区的速度。

磁盘用可磁化金属氧化物记录位。每个扇区包括前导码、数据和校验和。老式磁盘每个柱面的扇区数相同，新式的外围柱面会有更多的扇区数从而可提高总体的密度，但磁盘控制器会进行重映射以对操作系统屏蔽这差异，磁盘控制器一般还会作一些缓冲、坏块重映射等工作，一个磁盘控制器可能可同时控制多个磁盘。

当有多个磁盘时，可以一起使用以提高可靠性或性能，从而虚拟出可靠、快速、大容量的单一磁盘，标准用法称为独立磁盘冗余阵列（RAID）：

RAID0把以扇区条带为单位的数据分布到各个磁盘，由于可以并行地在多个磁盘同时读写，RAID0可以明显提高读写速度并尽用空间，但可靠性比单个磁盘更低
RAID1把以扇区条带为单位的数据重复存放于若干组磁盘，它可以提高读速度但不能提高写速度，但提高了容错性，任何一个磁盘故障后可从备份磁盘轻易地恢复
RAID2把以字甚至半字节为单位的数据连同海明码分布到各磁盘，这海明码的纠错能力可给出较高的容错性，但在磁盘数多且旋转同步时才能提高写速度
RAID3与RAID2类似但用奇偶校验和代替海明码，这可省点空间和时间但纠错能力也弱一点
RAID4把以扇区条带为单位的数据分布到各个磁盘，再把奇偶校验和放在另一磁盘，但存放奇偶校验和的磁盘会成为瓶颈
RAID5把以扇区条带为单位的数据及其奇偶校验和分布到各个磁盘其实在有多条内存的系统中也可用类似技术负载平衡和提高效率。

近年一些移动终端或高端机器用闪存取代磁盘的传统用途，闪存的速度介于内存与磁盘间，不易失，但容许的擦写次数较少。

光盘有较高的记录密度，常用于备份或交换数据。它利用反射率的差异来读取。光盘上的数据螺旋式地存放，概念上简单但实际建立寻道时往往要先计算近似位置再在哪里附近找16字节的前导码（00FFFFFFFFFFFFFFFFFFFF00后接3字节扇区号和一字节ECC），故寻道比磁盘慢，而且播放时旋转的角速度要逐渐降低。光盘一般都有纠错能力，如把8位的字节编码为14位的海明码。

CD-ROM用物理的痕和脊的过渡来记录数据，要先用高功率激光在母盘烧出许多与CD-ROM上相反的小孔，然后通过把树脂注入母来制作CD-ROM，由于母盘制作昂贵，这种做法只适合批量的副本生产。
CD-R在反射金层与聚碳酸酯底间加一层染料层，开始时它是透明的，但用高功率激光照射时会烧出暗斑，CD-R可以逐渐附加但不能修改。相应地，要求特殊的文件系统（如每次附加时写入新的目录信息和上个目录信息的位置）。
CD-RW与CD尺寸一样但用合金代替染料，合金有结晶和非结晶两种反射率不同（后者低）的稳定状态，高功率激光可把把合金融化为非结晶（视为痕）、中功率激光可把把合金融化为结晶（视为脊）、低功率激光不会导致变化可用于读取，CD-RW可写但较CD-R昂贵，用于备份时不可写是好处
DVD（数字通用光盘）与CD同样用120mm盘片，但使用更小的痕、更密的螺旋和波长更短的红色激光来提高存储密度，单面单层可保存4.7GB的数据，1倍速的数据率达1.4MB/s。双层盘的底部有反射层，两层间有半反射层，容量可达8.4GB（下层需要大点的痕和脊才能可靠读出故密度稍低）。如果把两0.6mm厚的单面盘背对背地粘贴起来，还可以再翻倍。
Blue-ray和HD-DVD用蓝色激光进一步增加容量（单层25GB或15GB），但竞争妨碍了推广，后者已经退出竞争。为了妨碍非法复制，发行商可能故意填入错误的校验和或文件大小，需要用其软件才能观赏。

磁带则主要用于备份（特别是离线的），只能顺序访问。

I/O设备

一般通过驱动程序使用I/O设备，驱动程序与I/O设备的控制器（如PC中主板上的芯片或卡）对话，即读写控制器中各寄存器，一些机器把它们映射到地址空间（好处是不需要专门I/O指令简化了驱动程序编写，但页表需要高速缓存禁止位和需要区分设备地址的硬件（失败重试或过滤地址）），另一些则映射到端口号。驱动程序一般需要在内核态运行（用I/O指令访问端口一般是特权指令，但操作系统可以用系统调用包装它），并且应当可重入，故操作系统要用某种方式链接到它（现在一般可动态加载不用重新编译内核），不同的设备-操作系统组合需要不同的驱动程序。另外还需要一些设备无关的I/O软件提供统一的用户I/O接口、缓冲（可能包括双层缓冲、循环缓冲区）、错误报告或重试、设备无关的块大小。

I/O设备的工作方式分为：

轮询。驱动程序不断检查设备的状态直到完成I/O，然后必要时把数据送到指定位置。它简单但在I/O完成前CPU做不了其它工作，只适合用于嵌入式系统之类没有其它工作可做的情况。
中断。驱动程序向控制器发出指令后返回，待完成I/O时由控制器发出中断，中断控制器在检测到中断后决定处理的话（如果没有更高优先级的中断未处理），先应答设备控制器让它可再发出中断，调用中断处理程序再继续原来的计算。（实际上，一些机器用了不精确的中断，这时程序计数器前的指令可能没有执行完，后面的指令也可能执行了部分，要由操作系统判断情况并回退，不然就是CPU内部有复杂的回退逻辑，都是要开销的）
直接存储器访问（DMA）。使用专用的DMA芯片而非CPU直接控制与控制器的对话，CPU先对DMA芯片进行设置，待操作完成由DMA芯片发出中断。这方法可大幅减少中断和节省CPU周期，但DMA通常比CPU慢而且会与CPU争用总线。

I/O设备按速度大致分为：

块设备，传输以块为单位，通常每个块可独立于其它块而读写
- 块可寻址设备可以高效地定位任意块，如磁盘
- 块不可寻址设备，如磁带
字符设备，传输以字节为单位，不可寻址，如网络接口、鼠标、键盘和打印机
其它，如时钟、内存映射显示器

时钟

早期的时钟每个电压周期产生一个中断，但现在的时钟是可编程的，由晶体震荡器（频率比交流电高多了）、计数器和寄存器组成，可以用软件控制什么时候发生中断。常见的使用模式有：

完成模式，即开始时先把寄存器的值复制到计数器，每个来自晶体的脉冲使计数器减1，当计数器到达0时引发中断并停止工作
方波模式，当计数器到达0时引发中断并把寄存器的值复制到计数器上继续工作，从而产生周期性中断现代的机器往往有多个时钟（没有也可软件地用一个模拟多个，只用记录到期时间链表和下一到期时间），有的是正计时的，其中有一个由电池供电的时钟在关机时仍运作以保存绝对时间。

另外一种设计是软定时器，不是由它引发中断，而是操作系统在每次离开内核态前检查时间以看看有没有计时器到期，这样可消除上下文切换或轮询开销但准确度稍低一点。

时钟的用途包括：

维护日期时间，通过维护以秒为单位的时间（可加上秒内时钟滴答数）或长的时钟滴答数
限制进程的运行时间
记帐
监视定时器，如开始旋转软盘后一段时间后速度稳定才能读写
对程序进行性能剖析，即找出时间花到哪去了

键盘

I/O端口的值是由键盘控制器给出的扫描码，其中7位用于标识各键，余下一位标识是按下还是释放。驱动程序可能处于以下模式之一：

面向字符的，这时应用程序能探测每次按键对应的代码（如ASCII）
面向行的，这时应用程序能探测规范化后的行（其中不会有退格字符之类）以下会导致一些复杂性：
回显（包括折行）
制表符和行结束符处理
特殊按键（如Unix中Ctrl-J换行、Ctrl-D文件结束符）
提前输入
支持编辑点

鼠标

鼠标是一种点设备，通常配有一个到三个按钮，以下设备均视为鼠标：

机械鼠标，用橡皮球牵引两个方向的滾轮来决定位置变化
跟踪球，基本上时反过来的机械鼠标
光学鼠标，它通过获取下方的照片并分析其变化来决定位置变化
触摸板，它通过受压力点位置的变化来决定位置变化

在按下或释放按钮，或者移动超过某个阀值（通常是可设置的）时会发送它在两个方向的位置变化和按钮的状态。操作系统可能会重组绝对坐标和两个事件合并为双击。

显示器

早期的屏幕上可显示一个字符矩阵（如25行80列）。当输出连续且有单一字体、大小和颜色时，情况比较简单，操作系统只用提供一个用于输出一个字符或字符串的调用。但随着面向屏幕的程序（如emacs、vi等编辑器）兴起，驱动程序常用转义字符的方式提供移动光标、插入字符、删除字符等命令以方便修改屏幕，由于不同终端支持不同的转义序列，一些操作系统抽象出若干标准操作。

现在很多显示器可以显示彩色位图（常见1024×768、1600×1200、1920×1200），并且在每秒刷新多次。一方面，显示对时效性有要求且这涉及数据量很大，必须重视性能。另一方面，让每个应用程序与位图这样低层次的东西打交道并不理想，应该提供高级别的操作。现代的图形用户界面（GUI)以为窗口、图标、菜单和定点设备为要素（统称WIMP），自然地一般用面向对象的方式组织，并且用事件驱动的方式使用。Windows中用操作系统代码实现图形用户界面。Unix则主要在用户代码实现，其中常用的X窗口系统则采用客户端-服务端模型，客户端作出绘制请求，服务器端则实际进行绘制，两者甚至可能只通过网络连接，它们间用X协议进行低级别的通信（到服务器的绘图命令、到客户端的事件通知（键盘、鼠标和错误等等），Mac OS X用二进制格式故效率高于X.org的文件格式）。在客户端上，由低层到高层提供了高度的灵活性：

Xlib提供了访问X功能的接口
图形工具包（如GTK+和QT）提供了一些标准的窗口内组件
窗口处理器（如GNOME和KDE）控制窗口的创建、删除和变更

由于更多工作落入软件的职责，需要考虑一些问题

决定重绘
向量字体比位图字体的好处在于在缩放下质量较好但在使用前转换为位图需要时间开销
常见的GUI工具包都是单线程的即大部分绘制和事件处理代码在同一线程上执行

电源管理

在实现相同功能而减少用电方面的主要功劳归于硬件厂商，从真空管到晶体管再到集成电路，计算机在性能大幅提升的同时用电却大幅下降，现在硬件厂商仍然通过减少制程、动态电压调节等方法省电。而作为操作系统，也可以做一点事情：

关闭或降级不必要的设备，但恢复时往往有较大延迟
- 显示器往往是PC的最主要耗电设备，可以在用户一段时间没有作出交互时关闭或调暗它直到用户击键或移动鼠标才恢复，在用电池供电或电量不足时也可能要调低亮度
- 磁盘的旋转往往是第二耗电设备，可以在一段时间不用时关闭或调低转速，利用缓冲区可使这情况更常见
- CPU在没有工作时可进入睡眠状态直到中断发生（稍长时间也可关闭高速缓存），在低负载时可以调低电压（$P=\frac{V^2}{R}$）和时钟周期
- 内存在没有工作时可以把内容写到磁盘后关闭，需要时再从磁盘恢复，但延迟大，通常在较长时间不用或用户要求时才这样做
- 射频对于无线装置也是重要耗电原因，可以在一定条件下关闭（但决定何时关闭和重开涉及消息的时效性，可能应让用户参与），在关闭时需要在本机缓冲外发的信息和通知外部消息源缓存消息以防丢失信息，到重新打开时再发出已缓存作息和向知会消息源可接收。
- 风扇的转速可按CPU的温度调整（过高时可能还要降级CPU），风扇也影响噪音
- 一些其它设备也可用ACPI统一地管理

另外，现在的电池可向操作系统报告状态（如最大电压、当前电压、剩余电量、当前消耗速度等等），从而 - 在一块电池快用完时可切换到另一电池 - 在所有电池快用完时可向用户警告或关机

要求应用程序降级以减小用电，例如视频播放器可以降低分辨率或舍弃部分帧，对应用程序进行能源审计并按此收费来可鼓励应用程序省电（如把复杂计算交给服务器以节省终端用电或相反）

概念

进程

进程就是程序的一次执行，可视为抽象的CPU。这抽象的作用在于:

容许多个程序同时运行
容许比物理CPU更多的程序看似同时运行
容许多个程序协同完成任务
尽可能利用I/O与计算能力

对于每个进程，操作系统用一个进程控制块记录有关的管理信息和状态，如：

地址空间信息（如页表、正文段指针、数据段指针、堆栈段指针）
用户ID与组ID
根目录与工作目录
打开文件的描述符列表（包括它们的指针位置）
寄存器的值（包括PC、PSW、SP）
进程状态
优先级
父进程与进程组
审计信息（如使用的CPU时间）

生存周期

在系统初始化时首个进程（称为init）被创建，正在运行的进程可通过系统调用创建其它进程（被创建的叫子进程、创建者叫父进程），于是进程间有树状关系（Unix一进程与所有后代进程构成进程组）。

大致来说，进程可处于以下状态之一：

就绪，这时可随时被调度程序换上而进入运行状态。
运行，这时实际占用CPU。运行中的程序可能被调度程序换下而回到就绪状态，或者由于等待输入而阻塞。
阻塞，这时要等待外部条件满足后才能继续，那时（如I/O设备控制器发出中断表示I/O操作完成）就回到就绪状态。

其中，把进程换下和换上的过程叫上下文切换，它制造程序的运行好像没有断过的假象，除了进程主动请求让出CPU外，操作系统的调度程序也可通过时钟中断取得CPU的控制权：

硬件压入程序计数器的值
硬件从中断向量装入新的程序计数器
汇编程序过程保存各寄存器的值
汇编程序过程设置新的堆栈
运行C的中断服务例程
调度程序决定下一个运行的进程
汇编语言过程装入下一进程上次换出时保存的各寄存器的值（包括程序计数器）

进程的终止有几种情况：

正常结束，即程序完成工作后通知操作系统它已经完成（如通过Unix下exit系统调用）
异常结束，即程序发现未能完成工作后通知操作系统它出错（如通过Unix下abort系统调用）
严重错误，即因企图执行非法指令、引用不可用的内存或除零等原因导致中断而被操作系统逮住（Unix下会发信号以给程序一个机会）
他杀，即被其它进程向操作系统要求结束（如通过Unix下kill系统调用）

调度

当有就绪进程比CPU多时，需要决定让哪个进程在哪个CPU运行，这就是调度的问题。

在以下情况需要调度：

创建新进程后要决定继续运行父进程还是运行子进程
在一进程终止后要决定运行哪个就绪进程
在一进程阻塞后要决定运行哪个就绪进程（虽然最好是可解除阻塞的，但操作系统难以做这样的决定）
在中断（非时钟）发生时决定是否以为运行刚解除阻塞的程序
在时钟中断时选择运行哪个就绪进程（间隔太长不利响应时间，太短不利吞吐量，因为上下文切换需时且引致缓存失效）

在有多个CPU（或CPU核）时，有多个策略：

局部调度在创建线程时为它指定一个CPU，然后每个CPU独立地调度，让线程在同一CPU运行的好处在于高速缓存开始时更可能命中，但CPU间负载可能不平衡
全局调度在每次调度时从所有线程作出选择
二级调度在局部调度的基础上，当有CPU没有可运行线程则尝试从其它CPU拉取一个，或者在负荷过高时推走一个有时对多个CPU同时调度是有益的，如让同一进程的多个协作线程同时运行。如果知道线程间的通信量，把通信频繁的线程放到同一CPU也可能是合适的。

批处理系统的调度

目标为提高吞吐量、降低周转时间和高CPU利用率。方法有：

先来先服务，也就是让作业们排队，它简单（只用一个队列）且易理解
最短作业优先，假定成批已知需时的作业同时进入系统，则按需时递增顺序运行它们，不抢占，它可以最小化平均周转时间
最短剩余时间优先，假定所有作业需时已知，则每次有作业进入系统时总是选中让剩余时间最短的作业，同样让平均周转时间较低，但对长作业不公平（可能永远完成不了）一个问题是难以预知各作业的需时。

交互式系统的调度

目标为降低响应时间。方法有：

轮转调度，也就是轮流为各作业分配相同长度的时间片（如50ms），它实现简单（一个队列）、公平
优先级调度，也就是总是选取优先级最高的进程，相同优先级间则轮转，其中优先级可以静态给定（如按用户职级、费用之类反映重要性的指标）或动态确定（如用不完时间片的为I/O密集从而给高优先级），它可以比较合理但低优先级的可能总没有机会执行（为防这情况，可以定时调低优先级）
多级队列，给予低优先级进程更长的时间片，为常用不完时间片或有交互式操作的进程调高优先级
最短进程优先，选取预期最短的作业，其中预期时间用它过去的运行时间估计（如用旧估计与上次运行时间的加权平均）
保证调度，统计各进程占用CPU时间比例，选取低于应得的，它强调公平性
彩票调度，为每个进程分配若干彩票，用于决定它被选中的概率
公平分享调度，企图保证各用户而非进程获得均等机会，它强调公平性

实时系统的调度

实时系统对任务的完成时间有明确要求（硬实时是硬性要求，到下周才算出明天的天气预报已经完全失去价值；软实时可以容忍一些错失，如视频渲染不及时让用户体验下降）目标为满足截止时间和可预测性。方法有：

最早截止时限优先，它可以用于作业动态进入系统的情况，原则上能满足的用这方法都能满足（不考虑上下文切换时间）
若所有任务是周期性且每次需时已知，可以静态地判断是否可调度（需时与周期之比的和不超过1）并作出调度决策规则
- 速率单调调度，假定每个进程每次运行用时相同则把优先级设为其频率，但只有在需时与周期之比的和不超过$m(2^{1/m}-1)\sim \ln 2$时才保证成功工作

进程间通信

进程间通信的基本方法为：

消息传递，在这模型中程序可用发送与接收两种原语，接收原语向指定的目标发送指定的信息，接收原语则用于获取指定的源发送的信息（没有则可以阻塞等待或返回特殊值）。在实现消息传递机制时，可能涉及进程命名、丢失重发、重复发送、身分认证等问题。由于消息传递通常涉及陷入到内核态在地址空间间复制数据，性能往往较低，但比较安全。可归入这类的方式有：
- 管道，一种特殊的文件，同时被两个进程打开，一方向它写入数据，另一方则从它读取数据，是Unix中的一个关键构造
- 信箱
- 套接字，可以让网络上两台机器上的进程通信（有时也用于本机上前后台进程），MPI接口就常用于分布式计算
共享存储区，在这模型中进程向操作系统申请让多个进程都可以访问一块内存（使有关进程的地址空间都可映射到它）。共享存储区的话，往往需要很多进程间通信来防止出现一些诡异的状况如：
- 两个进程都在输出时它们输出的内容可能夹杂在一起
- 你看到的变量可能随时被别人意外改掉

由于共享资源导致结果依赖于进程运行精确时序的情况称为竞争条件，这通常不是预期的。我们把访问共享内存的程序部分称为临界区，防止两个进程同时处于临界区中可避免常见的竞争条件，一个好的方案还要保证临界区外的进程不能阻塞其它进程、不能让进程无限期等待进入临界区。以下是一些方法：

屏蔽中断，在单处理器系统中可以在进入临界区前屏蔽中断到离开才重开（多处理器还要锁定总线），从而期间不会发生上下文切换。然而，把屏蔽中断的权限给予用户是危险的，只在实现操作系统时有用。
忙等待，可以在用户态软件地实现，但浪费CPU资源，以下代码可保证p0与p1不会同时在临界区：

int turn;
void p0(){
     while(turn!=0);
     /* 临界区 */
     turn=1;
     /* 非临界区 */
}
void p1(){
     while(turn!=1);
     /* 临界区 */
     turn=0;
     /* 非临界区 */
}

上述代码的缺点在于严格地轮转使临界区外的进程能阻塞其它进程，考虑到进程不总想进入临界区，作以下改进（进程在想进入或退出临界区时只用调用相应过程）：

int turn;
int interested[2];

void enter(int process){
     int other=1-process;
     interested[process]=1;
     turn=process;
     while(turn==process&&interested[other]);
}
void leave(){
     interested[process]=0;
}
void p0(){
     enter(0);
     /* 临界区 */
     leave(0);
     /* 非临界区 */
}
void p1(){
     enter(1);
     /* 临界区 */
     leave(1);
     /* 非临界区 */
}

专门指令
- Test and set lock，它把右操作数指定的位置处的值写到左操作数指定的位置，然后把原来位置的值设为非零

enter:
    TSL REGISTER,LOCK
    CMP REGISTER,#0
    JNE enter
    RET

leave:
    MOVE LOCK,#0
    RET

- Exchange，它原子地交换两个位置的内容

enter:
    MOVE REGISTER,#1
    XCHG REGISTER,LOCK
    CMP REGISTER,#0
    JNE enter
    RET

leave:
    MOVE LOCK,#0
    RET

互斥量，可以类似上面实现，但在测试失败时通知操作系统主动让出CPU而不是马上重复测试
信号量，一个整数变量，原语P让它减一且在结果为负时挂起当前进程，原语V让它加一且在结果非负时唤醒其中一个挂起的进程，互斥量可视为初始为1的信号量
管程，通常由程序设计语言的语法构造（如java的synchronized），用于标记临界区，相对容易写出正确的代码
屏障，屏障要求一组进程全部到达特定位置后，它们才能继续运行

以下是一些经典的进程间通信问题：

哲学家就餐问题：有五个哲学家围坐在圆桌周围，每两个哲学家之间有一只筷子，每个哲学家只有在饿且分别拿到他两边的两只筷子才能开始吃饭
读者-写者问题：有一个数据库，可以有多个进程同时在读，但有一个在写时不能有其它同时在读或写
生产者-消费者问题：有固定个货架，生产者在发现有空货架时把货物放进去，消费者在发现有非空货架时把货物拿走

并发编程的难点

正确地编写涉及同步的程序是困难的，问题难以可靠地重现使调试成为噩梦。所以，编写需要高并发的程序时应尽可能减少同步的需要，为此不惜放弃一些在不用同步时有效的优化措施，如缓存（难保一致性）、共享（难保可重入性），纯函数式或事件驱动的编程风格可能是有益的。软事务内存是近年兴起的另一模型。以下是不小心地使用进程间通信导致的问题：

死锁

若一个进程集合中每个进程都在等待只能由进程集合中其它进程引发的事件，则称这进程集合为死锁的。这时其中所有进程只能无限期地等待下去。例如在网络通信中，A向B发出的包丢失就可能使B在等待该包而A则在等待B的响应，本例子中可用超时重发的方法解决（但还要与重复发送的问题打交道）。发生死锁的必要条件为：

对共享资源（硬件或文件和锁等信息）的互斥访问
占有并等待
不可抢占
循环等待相应地有四种预防死锁的方法：
消除必须互斥访问的共享资源，如用假脱机让各进程以为自己占有打印机，但实际上只有一个守护进程占有打印机，它代为打印完整的输出文件。即使不能全部消除，尽量减少也是有益的。
禁止已经持有资源的进程再申请资源，或者必须放弃已经占有的资源再一次性获取所有所需资源，但进程事先往往不知道确切需要什么资源，这会鼓励它们保守地过度申请资源而降低资源的使用率
抢占资源，把资源做成无状态的
把资源编号，禁止请求比当前占有资源编号更低的进程，但使用不便和编号方案的麻烦使它没有广泛采用另一种策略是检测死锁并在死锁发生时打破死锁：
检测方法
- 在每种类型的资源都只有一个时，这可归结为有向图的环路检测问题
- 在每种类型的资源可多于一个时，利用资源数向量、当前分配矩阵和请求矩阵等数据结构，寻找是否有进程的请求现在可完全满足，有则清空它的请求行和分配行，如此重复，最终若有进程的请求行仍非空，则它涉及死锁。在每次请求资源时检测无疑可尽早地发现死锁但开销太大，其它选择包括周期性地检测或在CPU使用率过低时检测
从死锁中恢复的方法
- 抢占资源，但只适用于部分资源，对其它可能需要人工干预
- 把系统恢复到上一个没有死锁的检查点，由于通常开销较大，只适用于预知死锁但不容忍死锁的系统，并用专门的检查点表示
- 杀死部分进程（可能在或不在死锁环）直至不再有死锁，最好是幂等的，即在断开并重新运行时造成的最终结果没有变化的进程。还有一个策略是死锁避免，即在动态地分配资源以防止进入可能死锁的情况。
银行家算法，检测分配的话是否可能导致死锁（与死锁检测类似，但用最大剩余需求代替当前请求），是则拒绝分配，否则进行分配。由于进程在运行前往往不知道它所需资源的最大值，这方法并不实用。

考虑到死锁的频率和严重性，现代的通用操作系统一般忽略死锁，把责任推给用户，但数据库管理系统之类必须处理。

活锁

当使用轮询而还是中断时，可能出现没有阻塞而两个进程都不断查询对方持有资源是否可用的情况，这就是活锁。在进程表、打开文件列表等系统表甚至交换空间大小有限时，都可能产生活锁，例如有两个进程分别要产生四个子进程，但进程表只能容纳8个进程，则若两个进程分别创建了3个子进程则进程表已满，于是它们都在无希望地不断尝试创建进程。

饿死

在分配资源时，部分进程的请求总是得不到满足的情况叫饿死。例如随着短作业不断进入系统，最短剩余时间优先策略（而不是先来先服务）可能使长作业永远得不到服务。一些防止死锁的策略会增加出现饿死的机会。

线程

上述的进程同时是调度单位和分配其它资源的单位，线程则只作为调度单位（只用记录寄存器、堆栈和状态等）。线程的特点有：

创建和上下文切换开销较低，于是方便大量创建线程，更好地利用多CPU的能力（如服务器可能把每个请求分派到不同线程处理，收到请求时弹出式地创建或预先缓冲一些）或缩短响应时间（图形界面程序一般用多线程以免界面无响应）
同一进程可以有多个线程共享其它资源，这往往有助提高时空效率，但带来便利的同时可能鼓励结构不清晰的程序（甚至因此降低并发性）

在不感知线程的操作系统，可以在用户态实现线程，但会有些问题，例如难以强迫一线程把CPU交给其它线程（可能只能指望它们自律地主动让出）、一个线程阻塞会导致整个进程阻塞从而其它线程也不能运行（改用非阻塞操作或是阻塞操作的包装是一个方案）、各线程不能在不同CPU上并行、进程的调度异常等等，好处则是因不用陷入而可能更快、可能用定制的调度方式。用多个进程模拟多个线程可以改善一些。无论如何，主流的操作系统已经提供了线程机制，由内核管理线程表，但难以决定标准输入或信号给谁等问题是线程固有的。还有人希望操作系统暴露一种机制让阻塞时通知用户态的调度器以结合两种方式。

在Linux中线程与进程的界线是模糊的。

地址空间

地址空间就是程序看到的存储空间，每个进程有自己的地址空间。这抽象的作用在于:

容许多个进程同时驻留物理内存
容许进程占用比物理内存更大的空间
避免不同进程随便干涉对方的存储空间
可以内存映射文件以统一使用内存或作进程间通信

早期实现地址空间的方法有：

静态重定位，在链接阶段把地址空间开始位置的物理地址加到各指令的地址操作数上，缺点是使加载过程变慢和需要额外信息以便区分需重定位的数
动态重定位，在运行进程前设置基址寄存器和界限寄存器，然后在每次访问内存时硬件地把基址寄存器的值加到地址上，再验证小于界限寄存器的值才继续操作（不然陷入到操作系统），缺点时有运行期开销和仍然要求地址空间占用的物理内存连续

容许多个进程同时驻留物理内存就可能导致内存不足以同时容纳所有进程，于是想法就是把暂时用不到的内容从内存写到磁盘（通常是一个生分区或文件系统中的一个大文件）：

交换，必要时把不在运行中的进程占用内存的内容写到磁盘中然后释放有关内存位置，当它再次运行时再重新读入内存。
覆盖，由程序员建立一个管理模块在适当时候把程序的各部分换入或换出，但让程序员介入是枯燥和容易出错的。
虚拟内存，容许进程地址空间只是部分在物理内存中，从而可能运行占用比物理内存更大空间的进程
- 分页，把地址空间分为一些固定大小的页（如4KB），相应地物理内存也分成同样大小的页框，访问内存时硬件（存储管理单元，MMU）按页表把逻辑地址（由页号和页内偏移组成）映射到物理地址
- 分段，把地址空间分为一些程序员划分的逻辑实体，每个段的长度不同（甚至可能动态变化，但通常远比页大）且可以设置不同的保护（如不可写或执行），段较页更适合作为在进程间共享数据的单位，但纯分段容易产生外部碎片
- 分段后分页

分页

当访问内存时MMU会检查请求地址对应的页是否在内存，不在则陷入（称为缺页中断）让操作系统把该页调入物理内存，然后把对应的页框号和页内偏移放到地址总线。

页表中每页有一个条目，包括是否在物理内存和对应页框号，也可能有权限位（如能否读、写、执行）、高速缓存禁止位（对于映射到设备寄存器的页面，可能在CPU不知情的情况下被改掉）、访问位（在过去一段时间是否被访问过，在选择换出页面时有用）、修改位（调入后是否修改过，没修改过的话换出时不用写回磁盘）等等。

分页的难点在于：

因为访问内存极为常见（一条指令可能已经涉及多页），虚拟地址到物理地址的转换必须很快
- 常见的技巧是利用局部性，在MMU中设立硬件的转换检测缓冲区（TLB）缓存部分虚拟页号和对应的表项，MMU把请求地址中的页号同时与所有TLB中的虚拟页号比较，找到（命中）则使用缓存的表项映射，不命中才使用内存中的页表，并把有关表项缓存下来（缓存已满则淘汰一项，并把修改位和访问位之类写回页表）。在一些RISC机器中，用软件管理TLB，于是操作系统可利用更多知识作预先加载或多层缓存之类以增加命中率。
因为页表需要占用空间，每个进程有自己的页表，它不应太大（反之，页面大则会增加内部碎片，进程用不完页是对剩余空间的浪费）
- 多级页表，把页号的位模式分割，在顶级页表按首部分查二级页表位置，然后到二级页表继续找，这样可以让部分页表换出，不一定全留在物理内存（甚至必要时才创建），但增加时间开销
- 反向页表，改为用页框号索引页号以节省空间，但从虚拟地址到物理地址的转换费时（如果TLB不命中），配合散列表用可能是合理的，常用于64位机器的大地址空间

在没有足够内存时，发生缺页中断时需要把一页换出以便腾出位置给等换入的页（在高速缓存和TLB也遇到同样问题），选择换出页时，我们希望它短时间内不用再换入以减少缺页中断次数：

最优页面转换算法，即换出距离下次访问最远的页面，但一般不知道页面未来什么时间会被访问，所以它不实际，只用作性能基准
最近未使用页面转换算法，即利用局部性用过去估计未来，每过一段时间把访问位清零，优先置换访问位0的
最近最少使用页面转换算法，同样利用局部性用过去估计未来，但用多个访问位，访问时设最高位，每过一段时间右移，换出各访问位最小的页面
最不常用页面转换算法，同样利用局部性用过去估计未来，但用计数器，每次访问（软件实现时在周期后访问位为1时）时加1（溢出如何？），置换计数器最少的页面（也可作老化处理）
先进先出页面转换算法，即置换最先被换入的页面，可用链表实现，但一些常用页会被反复换出
第二次机会页面转换算法，即置换最近一周期没有被访问的页面中最先被换入的页面（都访问则同上），可通过在最老页面访问位1时清零访问位并移到列表末（或变化循环列表的指针）实现
工作集页面转换算法，即尽可能换出在过去若干时间（或内存访问次数或时钟中断数）没有用过的页面，可通过记录近似的上次使用时间实现，它倾向留下有用的页面（称为工作集）
工作集时钟页面转换算法，用一个以页框号、上次使用时间和修改位为元素的循环列表实现，对于与上次使用时间距离较长的页面，若修改位为0则换出，否则申请写回再继续，要是回到原点也没有申请过写则随意置换另外，宜优先换出修改位为0的页面，映射I/O设备寄存器的页面则不能换出（被钉住）。又一个选择是：
全局置换策略从所有进程的页框中选取换出的页面，对于工作集大小变化的情况效果较好，但对小进程不太公平，也可能用缺页中断率或页框数下限调整
局部置换策略只从请求进程的页框中选取换出的页面，基于工作集的算法一般配合局部置换策略

操作系统也可用守护进程提前保证有充足的可用页框，但在实际覆盖前仍然可用。

如果所有进程的工作集大小之和大于物理内存大小，则难免出现颠簸（缺页中断频繁到各进程几乎没有进展，通常说的死机很多属这情况），这时可能应把一些进程整个换出，并在结束颠簸前不再让它运行。这不纯是存储管理的问题，也是调度的问题，中期调度器把进程换入和换出也考虑CPU利用率等因素。

共享页面

操作系统可能容许多个进程共享部分存储区（如同一程序的多个进程可共享代码节省物理内存（共享库同理）或者多个进程间可通信（甚至免复制消息传递）），这只用让各进程的页指向相同的页框，但存在一些问题：

当其中一个进程退出时只能释放它没有被其它进程共享的页框，这可能需要引用计数器以高效地实现
当其中一个进程修改共享的内存页时，语义上是可疑的，实现上要小心与缓存的交互一种小技巧是写时复制，如重复启动一个程序时先让它们的页表项都指向同样的页框，当页面被修改时才创建新页框并更新页表

由于共享库被不同进程定位到不同地址，不能仅仅在加载时重定位，共享库要编译成位置无关代码，避免用绝对地址。

连续内存分配

与分页相对，连续内存分配会产生外部碎片。

首先需要设法跟踪内存使用情况，基本方法为：

位图，把内存划分为若干个等长单元（太大则导致一些小空隙用不了，太小则导致位图太大），然后建立一个位图每位表示一个单元是否被占用，其缺点时为了找出一个空闲单元可能要遍历位图
链表，把空闲区和非空闲区分别链起成链表或双向链表（也可只做一个链表），每个结点记录是否在用、起始位置和长度，在释放内存时应合并相邻的空闲区，通常用空闲区保存这些数据结构

分配内存时，选取一个大于等于请求大小的空闲区分出要求的大小，选取的方法有：

首次适配，即选取链表中找到的首个可用空闲区，好处是快
下次适配，即选取链表中从上次停止位置起找到的首个可用空闲区
最佳适配，即选取链表中最小的可用空闲区，好处是可尝试保留大空闲区，缺点则是慢且造成大量难用的很小的空闲区
最差适配，即选取链表中最大的可用空闲区

一种做法是维护若干个常用大小空闲区的链表或让空闲链表按大小排序，但会为合并带来困难。

文件系统

文件系统是对I/O设备特别是磁盘的抽象，通常是现代操作系统中代码量最大的部分。这抽象的作用在于:

方便地定位各种数据
以统一的方式使用多种设备
可控制使用各种设备和权限

文件

文件是进程创建的信息的逻辑载体，主流通用操作系统把每个文件的内容看作一个字节序列，也有专用的系统把文件的内容视为记录序列或树等等。文件常附带一些称为属性的元数据，可能有：

当前大小和最大长度
创建、最后修改和最后访问时间
创建者和所有者
权限
隐藏标志
锁定或系统文件标志
临时文件标志
随机访问标志
内容类型

文件的常见系统调用有：

创建，即建立一个内容为空的文件并设置一些属性
删除，即删除文件并释放它占用的空间（但在磁盘块被覆写前仍然可能恢复）
打开，进程在需要使用文件前需要先把它打开以分配访问它所需的数据结构
关闭，进程在不再需要使用文件前应关闭它以便释放内存资源和清洗缓冲区（进程退出时一般自动关闭所有未关闭文件）
读，从文件的当前位置开始读取指定量的数据到指定的缓冲区
写，把指定的数据写到文件的当前位置开始的位置（若为文件末尾则文件长度增长，否则会覆盖原有数据）
附加，把指定数据写到文件末尾
定位，改变文件的当前位置（只适用于随机存取文件）
获取属性
设置属性
移动（包括重命名），效果相当于创建一个新文件并把按原来的内容和属性设置内容和属性再删掉原来的文件，但比较高效

Unix中文件分为：

普通文件
目录
块特殊文件
字符特殊文件
符号链接

文件系统的一个重要作用是给文件命名。现在主流的操作系统都把文件组织为树（早期或嵌入式的文件系统可能只容许一层），每个结点有一个名字，其中非叶结点也叫目录（在Unix中也视为一种特殊文件）。用于指定文件的方法有：

绝对路径，它由根结点（名字为空字符串）到文件的各结点名字组成
相对路径，它由工作目录（不含）到文件的各结点名字组成，使用相对路径的好处在于在移动整个工作目录后保持不变，但必须小心处于的工作目录各结点名字间用路径分隔符（在Unix是/、在Windows是\）分隔。另外常常假定每个目录有结点.和..分别指向这目录本身和其父目录，以便用相对路径遍历整个文件系统，但这使一个文件的路径不惟一，并可能导致安全隐患。

目录作为特殊的文件，同样有创建、删除、打开、关闭、读（读取下一孩子结点）等操作，操作系统也可能提供专门用于目录的系统调用。

有时我们想两个文件总保持相同的内容，用于交流或节省空间，有两种方法实现这点：

硬链接，也就是让两个目录项指向相同的内容位置，同时用引用计数以保证在没有任何引用时空间才被释放
符号链接，也就是在指定位置创建一个特殊文件，它含有指向的路径信息，当操作系统被要求访问这文件时操作系统实际上访问该路径指定的文件，符号链接可以跨越文件系统（甚至远程），但效率较低（多一层间接）且各文件地位不平等（如删除指向的文件后链接就失效）但在记帐或复制时可能有问题

文件系统的实现

为了理解文件系统的实现，把存储介质看作线性的扇区列表，0号扇区是主引导记录（MBR），然后是分区表（记录各分区的开始位置、大小、文件系统类型等等），余下就是若干个分区。每个分区包括引导块（分区用来启动时会被执行的代码，可用于启动操作系统）、超级块（记录重要的文件系统参数）、空闲块信息、i节点、根目录和各文件内容。

由于磁盘以扇区为读写单位（访问一个字节需时和访问一个扇区需时相若），故块的大小一般是扇区的若干倍。同样地，大块浪费空间，小块浪费时间。给文件分配磁盘空间和给进程分配内存空间面临类似的问题，于是有：

连续分配，即给每个文件分配连续的块，好处是实现简单和读写效率高（很少寻道和旋转延时），但随着时间推移会出现碎片化，结果有空闲空间却因不连续而不能用，需要磁盘重组。另外在创建大小时难以估计它最终的大小。所以现在只用于光盘之类文件大小已知且不常改动的情况。
链表分配，即构造块链表
- 用每个磁盘块的第一个字记录文件下一块的位置，它可中分利用空间但读写效率低（还不利随机访问）且导致块的可用大小怪异（用大块可缓解这些问题但代价时内部碎片）
- 建立一个下一块列表（称为文件分配表，FAT）且在运行期保存在内存中，这样可在内存中找出文件的所有块从而读写效率优于上法且可随机访问，但磁盘太大时可能占用过多内存
i节点，每个文件有一个i节点，它有固定大小（如一个块），记录文件属性、前面若干块的位置和从何可知余下块位置的信息，它在文件打开时才调入内存其中空闲块的记录有以下方法：
链表，即在块中保存尽可能多的空闲块指针，再加一个指向下一个空闲链表块的指针，而内存中维护一个接近半满的空闲链表块
位图，内存中只用保存部分位图，満或空时才调入其它，好处是磁盘块会较密集地聚集起来且往往节省空间，适用于空闲块较多时

至于目录的实现，对于每个目录项，需记录名称和i节点号或首个块号，有的文件系统也把属性记在目录中。支持长文件名需要用长度字段（导致每个记录不等长，删除文件会导致碎片）或指向堆的指针。当文件很多时可能应该用散列表以避免线性搜索的时间开销。

如果操作系统要支持多种文件系统，模块化的方法是加入虚拟文件系统层抽象，其中指定公共操作的接口，于是对各类文件系统，只用分别实现这套接口并在使用文件系统前注册该模块，即可使用这种文件系统。

一些操作系统给各用户容许的文件数或块数设置配额，软性的配额给予用户若干次警告机会（有的设计不良系统在空间不足连删除文件都不能）。

性能考虑

为了提高访问磁盘的速度，有一些标准方法：

高速缓存，即把文件部分文件块缓存在内存中（可用LRU之类的置换算法）并用散列表索引，但在系统崩溃时可能导致更多不一致性（Unix每30秒同步一次，Windows则即时）。对于缺乏局部性的应用，如对视频点播服务器中不受欢迎的视频，高速缓存可能反而拖后腿；对于有特定使用模式的应用，则专用置换算法可能大幅提高性能，如在多人同时但不同步地观看视频时（进一步可企图把差距拉近）。内存映射文件可把这机制与页调度统一。
预先读，对于顺序存取文件（对随机存取文件是帮倒忙），在用户请求一个块时把保证后面的若干块已读入高速缓存
磁盘调度，即重新排序请求以减少总寻道距离，以下是一些方法：
- 先来先服务，即按请求顺序进行访问，它实现简单但往往有不必要的寻道距离
- 最短寻道优先，即总是选取请求中与当前磁道最近的，但它偏好磁盘中部的磁道，对其它磁道的访问请求会长时间得不到满足
- 双向电梯算法，先不断选取外面最近磁道的请求，到没有时不断选取里面最近磁道的请求到没有，如此循环，这可保证满足请求前磁盘臂移动距离的上界
- 单向电梯算法，先不断选取外面最近磁道的请求，到没有时选取最里面磁道的请求，如此循环如果可以获取当前扇区号，还能调度以降低旋转延迟。如果对磁盘使用模式有更多了解可能作出更符合需要的调度，如对于视频服务器要求可预测性（为此在不能满足服务质量要求时拒绝新请求），在分辨率和帧率等参数相同的条件下可以用轮流替各视频流提供一组帧，一般地可以按截止期限分批处理，同一批内按柱面排序。

日志文件系统（LFS）的思想是把总是连续地写而不是覆盖以提高性能（假定要读的大多已经缓存，而剩下瓶颈是零碎的写），增加的复杂性在于查找i节点更困难（可能一个需要i节点索引）和经常要更新i节点，还需要用清理线程清除无效i节点和块压紧空间。

灾难恢复

在系统崩溃时，一些操作未完成，因而可能处于不一致的状态，

日志：对于一些应当一起完成的工作（它应当时幂等的，即重复执行结果相同），在进行前先把日志项写到时磁盘（写一个块可视为原子操作），完成后才把日志项去除，这样如果系统在中间崩溃，则重复日志中指定的工作，这样就可保证工作的原子性
块的一致性检查：分别跟踪各块的空闲计数和使用计数，正常情况下它们一个为0另一个为1
- 若它们都为0，即发生了块丢失浪费空间，只用把块加到空闲表
- 若空闲计数大于1，则修正空闲表
- 若使用计数大于1，则复制块并让各i节点指向这不同的块
文件的一致性检查：分别跟踪各目录被包含的次数和i节点的连接计数，它们应该相等，不然应重新设置i节点的连接计数

备份到物理上隔离的介质（如磁带、光盘）更为安全，在磁盘在物理上损坏（如水灾、火灾）时仍然可恢复数据，但备份和恢复比较慢。通常备份周期性地进行（在系统低用量时），或者在进行危险操作前进行。备份分两类：

物理备份是把各磁盘块顺序写到介质上，简单可靠快速，只是当坏块对操作系统可见时（但通常磁盘控制器已经通过重映射对操作系统隐藏）要特殊处理，若干优化可避免复制太多未用的块
逻辑备份则感知文件系统，以文件为单位复制，从而有较大的灵活性备份还有一些考虑：
为了节省空间，可以只备份部分文件（如不备份设备文件和临时文件）
可以用增量备份方式避免重复保存相同的内容以节省空间和备份时间，但增加恢复时间
备份可以进行压缩以节省空间，但代价时备份更脆弱（一位错误可能使整个备份无意义）
链接的处理
在备份期间文件系统的变化处理
存放备份地点的保安

例子

ISO 9600

目录表项长度可变，包括目录项长度、扩展属性记录长度、文件位置、文件长度、日期和时间、标志（如隐藏、目录、扩展属性）、分隔、CD号、文件名（基本名.扩展名;版本号）。其中每个二进制域都用低地址结尾和高地址结尾重复编码。

存在一些扩展以支持多于8层的嵌套目录、长且非ASCII文件名、权限。

FAT

FAT系列常用于软盘、MS-DOS和早期的Windows，对介质大小已经构成实质性限制。FAT用文件分配表跟踪磁盘块，不用位图或空闲表来跟踪空闲块。每个目录项由文件名、属性、时间、日期、第一块号和大小组成，其中文件名有8.3限制，即基本名最多8个字符，扩展名最多3个字符。

V7

Unix常见的文件系统中i节点最后有一、二、三次间接块。

接口

系统调用

一些工作需要使用在内核态才能用的指令，为了进行这些工作，需要操作系统代劳，程序调用操作系统提供的库过程。这此特殊的系统调用的特点在于，其中会把编号和参数写入若干寄存器再陷入到内核态，并跳到预先确定的系统调用处理器，按编号执行相应代码。由于现代的操作系统提供很多功能，所以操作系统提供的API不都是系统调用。

操作系统的设计

操作系统的设计涉及以下方面：

定义抽象概念
提供基本操作
确保隔离
管理硬件

在进行前必须先确定需求，如：

用于多核芯片或分布式运算的系统需要设法提高并发性
需要大型地址空间的系统需要反向页表之类的方法，这甚至可用于持久性地址空间
基于互联网的系统可能以web页面作为基本数据结构和用户界面
电池供电的系统要设法节能，这意味着要避免多余的显示、射频和计算
嵌入式系统不太需要可扩展性，操作系统剪裁到足以维持已知程序工作已经足够，重点保证可靠性

通用操作系统设计的困难在于希望保持兼容性（支持过去和未来的硬件和软件），这是复杂性和ad-hoc方案的主要来源。接口设计原则上应当：

简单，易于理解和实现
完备，能够让用户做所有它需要做的事情
正交性，不同的接口方便独立地组合
能高效地实现

其中一个特别重要的原理是清晰地分离策略与机制，机制由操作系统决定而策略由用户决定。例如线程调度中，操作系统选用优先级调度是机制，而用户指定的优先级是策略。

以下是一些常见的决策：

同步还是异步：用于批处理可能适合用算法驱动，而交互式应用可能适合用事件驱动
通用还是特殊：暴露更多选项可能有助提高性能，但会增加复杂性
绑定的时机：早绑定用灵活性换取简单性，如页表容许变化页换出再换入到其它位置、动态链接内核模块容许热拔插驱动程序、用不固定长度的数据结构避免施加生硬的限制
设几个名字空间和命名方式

实现操作系统的架构可以为：

分层，即用较低层功能（接近硬件）实现较高层功能（接近用户）
模块化，即把内核分成若干个分别提供不同功能的部分
微内核，微内核的思想是让运行在内核态的部分尽可能小，绝大部分功能（甚至驱动程序）在用户态实现，从而提高可靠性，缺点则是性能往往较低。常实现成客户端-服务端模式，它们间用消息传递方式通信。

具体的手段有：

尽早隐藏硬件差异以提高可移植性
使用间接提高灵活性
编写可重用的代码以提高可维护性
避免共享数据结构或进行保护以保证可重入性
拿不准用穷举以保证正确性
编写足够的错误检查代码

在必要时在性能关键处常用的标准优化技巧有：

用空间换取时间，如记住计算结果或把i节点驻留在内存，但要考虑缓存过时的情况
用时间换取空间，如压缩数据
利用局部性，如把经常一起用的代码或数据放在一起和倾向把线程调度到它上次运行于的CPU
对常见情况特殊处理不过，最好先去掉不必要的功能。

由于开发工作通常涉及庞大的团队，操作系统的设计不仅是技术问题，更是人力资源管理的问题，软件工程经典著作《人月神话》就是IBM的OS/360项目经理Fred Brooks的惨痛教训。

虚拟机

虚拟机从软件看几乎就是一台机器，但实际上一台物理的机器可支持多台虚拟机，它的典型用途包括：

在一台机器上同时运行基于不同操作系统的程序
避免程序间的干扰（Paas云服务）
测试软件现在的主流硬件提供了对虚拟化的专门支持，不用依赖软件模拟，以致性能相当接近裸机。虚拟机的实现方式有：
执行敏感指令时陷入到虚拟机管理程序，由后者模拟
解释执行（一种变种是运行前修改代码把敏感指令换成对管理程序的调用，或者由操作系统进行转换），这是一个通用的方法（不用特殊硬件支持、可运行不同与物理机不同架构的软件）但性能可能差一些（也可能相反，因为避免了一些开销高昂的陷入）

关键词操作系统