1、导论

与用户交互的程序：

基于文本的shell
基于图标的图形化用户界面（GUI）

操作系统所处的位置：

Pentium系统的启动过程：

主板上有一个基本输入输出系统（BIOS），其中有底层I/O软件。
计算机启动时，BIOS开始运行。
首先检查安装RAM数量，键盘和其他基本设备是否已安装并正常相应。
开始扫描ISA和PCI总线并找出连接在上面的所有设备，记录下来。
如果现有设备和系统上一次启动时的设备不同，则配置新的设备。
BISO通过存储在CMOS存储器中的设备清单决定启动设备。
启动设备上的第一个扇区被读入内存并执行。
启动扇面末尾的分区表检查的程序，确定哪个分区是活动的。
从活动分区读入第二个启动装载模块，装在模块被读入操作系统。
操作系统询问BIOS，以获得配置信息。
系统检查每种设备驱动程序是否存在，有就将设备驱动程序调入内核。
系统创建背景进程，在终端上启动登录程序或GUI。

操作系统概念

进程：

进程本质是正在执行的一个程序。与一个进程有关的所有信息，除了该进程自身地址空间的内容以外，均存放在操作系统的一张表中，称为进程表（数组或链表结构）。

地址空间：

现代操作系统通常使用虚拟内存技术。操作系统可以把部分地址空间装入主存，部分留在磁盘上，在需要时再交换它们。

文件：

大多数系统都有目录结构，目录项可以是文件或者目录，构成了一种层次结构（文件系统）。进程和文件层次都可以组织成树状结构，一般进程的树状结构层次不深，而且是暂时的；文件树的层次常常多达四层、五层或者更多层，存在时间可能达数年。

输入/输出：

所有计算机都有用来获取输入和产生输出的物理设备。包括键盘、显示器、打印机等。

保护：

例如UNIX系统中对文件实现保护，三个3位保护字段（rwxrwxrwx），分别表示所有者、所有者同组用户、其他用户的读、写、执行权限。

shell：

UNIX的命令解释器称为shell，不是操作系统的一部分。shell是终端用户与操作系统之间的界面，除非用户使用的是GUI界面。

系统调用

系统调用函数的过程：

参数nbytes压栈
参数&buffer压栈
参数fd压栈
对库过程read进行实际调用
把系统调用的编放在寄存器中
执行TRAP指令，切换到内核态，在内核中一个固定地址开始执行
内核代码检查系统调用编，发出系统调用处理指令
系统调用句柄执行
控制返回给用户空间库过程
以通常的过程调用返回的方式，返回到用户程序
用户程序清除堆栈空间

2、进程与线程

进程

进程模型

操作系统中最核心的概念是进程：这是对正在运行程序的一个抽象。
一个进程就是一个正在执行程序的实例、包括程序计数器、寄存器和变量的当前值。

在多道程序设计中，一个CPU能在多个进程之间来回快速切换，达到（伪）并行效果。

一个进程是某种类型的一个活动，它有程序、输入、输出以及状态。
单个处理器可以被若干进程共享，它使用某种调度算法巨顶何时停止一个进程的工作，并转而为另一个进程提供服务。

创建进程

4种主要事件导致进程的创建：

系统初始化
执行了正在运行的进程所调用的进程创建系统调用
用户请求创建一个新进程
一个批处理作业的初始化

在UNIX系统中，只有一个系统调用可以用来创建新进程：。
这个系统调用会创建一个与调用进程相同的副本。
在调用后，这两个进程（父进程和子进程）拥有相同的存储映像、同样的环境字符串和同样打开的文件。
通常子进程接着执行系统调用，以修改其存储映像并运行一个新的程序。

在Windows系统中，一个Win32函数调用即处理进程的创建，也负责把正确的程序装入新的进程。

在UNIX中，子进程的初始地址空间是父进程的一个副本，不可写的内存区是共享的，新进程有可能共享其创建者的其他资源。
在Windows中，从一开始父进程的地址空间和子进程的地址空间解释不同的。

进程的终止

进程的终止通常由以下条件引起：

正常退出（自愿的）
出错退出（自愿的）
严重错误（非自愿）
被其他进程杀死（非自愿）

进程的层次结构

在UNIX系统中，进程只有一个父进程，但可以有多个子进程。
进程和它的所有子女以及后裔共同组成一个进程组。

Windows系统中没有进程层次的概念，所有的进程都是地位相同的。

进程的状态

进程的三种状态：

运行态（该时刻进程实际占用CPU）
就绪态（可运行，但应为其他进程正在运行而暂时停止）
阻塞态（除非某种外部事件发生，否则进程不能运行）

某些进程花费了绝大多数时间在计算上，而其他进程则在等待I/O上花费了绝大多数时间。
前者称为计算密集型（computer-bound），后者称为I/O密集型（I/O-bound）。

何时调度

需要处理各种情形：

在创建一个新进程后，需要决定是运行父进程还是运行子进程。
在一个进程退出时必须做出调度决策。
当一个进程阻塞在I/O和信量上或者由于其他原因阻塞时，必须选择另一个进程运行。
在一个I/O中断发生时，必须做出调度决策。

非抢占式调度算法：挑选一个进程，然后让该进程运行直至被阻塞，或者直到进程自动释放CPU。

抢占式调度算法：选择一个进程，让该进程运行某个固定时段的最大值。
如果时段结束进程任在运行则被挂起，调度程序选择另外一个进程运行。

调度算法分类

三种环境

批处理。非抢占式，或长时间周期的抢占式算法
交互式。抢占式算法
实时。抢占有时是不需要的。

调度算法的目标

所有系统
- 公平——给每个进程公平的CPU份额
- 策略强制执行——看到锁宣布的策略执行
- 平衡——保持系统的所有部分都忙碌
批处理系统
- 吞吐量——每小时最大作业数
- 周转时间——从提交到终止间的最小时间
- CPU利用率——保持CPU时钟忙碌
交互式系统
- 响应时间——快速响应请求
- 均衡性——满足用户的期望
实时系统
- 满足截止时间——避免丢失数据
- 可预测性——在多媒体系统中避免品质降低

批处理系统中的调度

先来先服务
最短作业优先
最短剩余时间优先

交互式系统中的调度

轮转调度
优先级调度
多级队列
最短进程优先
保证调度
彩票调度
公平分享调度

实时系统中的调度

实时系统的调度算法可以是静态的或动态的。
前者在系统开始运行之前做出调度决策；后者在运行过程中进程调度决策。

3、存储管理

现代操作系统使用分层存储器体系（memory hierarchy）。操作系统中管理分层存储器体系的部分称为存储管理器（memory manager），即记录那些内存是正在使用的，那些内存是空闲的；在进程需要时为其分配内存，在进程是用完后释放内存。

无存储抽象

最简单的存储器抽象就是根本没有抽象。早期计算机没有存储器抽象，每个程序都直接访问物理内存。想要在内存中同时运行两个程序是很困难的。

一种存储器抽象：地址空间

暴露物理内存给进程的问题：

如果用户程序可以寻址内存中的每个字节，它能很容易破坏操作系统。
使用这种模型想同时运行多个城市是很困难的。

地址空间的概念

保证多个应用程序同时处于内存中并且不互相影响，需要解决两个问题：保护和重定位。

地址空间为程序创造了一种抽象的内存。每个进程都有自己的地址空间，并且这个地址空间独立于其他进程的地址空间。

基址寄存器与界限寄存器

动态重定位，简单地把每个进程的地址空间映射到物理内存的不同部分。程序装在到内存期间无须重定位，程序的起始物理地址装在到基址寄存器中，程序的长度装在到界限寄存器中。

缺点：每次访问内存都需要进行加法和比较运行。

交换技术

两种处理内存超载的方法：交换（swapping）技术，虚拟内存（virtual memory）。

查找位图中指定长度的连续0串是耗时操作，这是位图的缺点。

链表管理法适配方式：

首次适配（first fit）：存储管理器沿着链表进行搜索，直到找到一个足够大的空闲区。
下次适配（next fit）：每次找到合适的空闲区都记录，以便下次从此开始搜索。
最佳适配（best fit）：搜索整个表，找出能够容纳进程的最小空闲区。
最差适配（worst fit）：总是分配最大的可用空闲区，使新的空闲区比较大。
快速适配（quick fit）：为那些常用大小的空闲区维护单独的链表。

虚拟内存

基本思想：每个程序拥有自己的地址空间，这个空间被分割成多个块，每一块称作一页或页面（page）。每一页有连续的地址范围。这些页被映射到物理内存，但并不是多有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间使，由硬件立刻执行必要的映射。放程序引用到一部分不再物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。

分页

由程序产生的地址称为虚拟地址（virtual address），它们构成了一个虚拟地址空间（virtual address space）。在没有虚拟内存的计算机上，系统直接将虚拟地址送到内存总线上，读写操作使用具有同样地址的物理内存字；而在使用虚拟内存的情况下，虚拟地址不是被直接送到内存总线上，而是被送到内存管理单元（Memory Management Unit，MMU），MMU把虚拟地址映射为物理内存地址。

页框
“在/不在”位：对应的虚拟页面在不在内存中
保护位：三位，表示读写执行
修改位
访问位
高速缓存禁止位

加速分页过程

在任何分页式系统中，都需要考虑两个主要问题：

虚拟地址到物理地址的映射必须非常快。
如果虚拟地址空间很大，页表也会很大。

解决方式：

转换检测缓冲区（Translation Lookaside Buffer，TLB）。大多数程序总是对少量的页面进行多次访问。
软件TLB管理

针对大内存的页表

多级页表：避免把全部页表一直保存在内存中。
倒排页表：在实际内存中每一个页框有一个表项，而不是每一个虚拟页面有一个表项。

页面置换算法

当发生缺页中断时，操作系统必须在内存中选择一个页面将其换出内存。如果要换出的页面在内存驻留期间已被修改，就必须写回磁盘；如果没有修改直接被覆盖就可以了。

最优页面置换算法：置换最久将要被访问的页面。此算法无法实现。
最近未使用页面置换算法（Not Recently Used，NRU）：随机地从类编最小的非空类中挑选一个页面淘汰之。
1. 没有被访问，没有被修改
2. 没有被访问，已被修改
3. 已被访问，没有被修改
4. 已被访问，已被修改
先进先出页面置换算法（First-In，First-Out，FIFO）：每次置换链表的表头。
第二次机会页面置换算法：检查最老页面的访问位。如果是0则立刻置换，如果是1则修改为0并把该页面放到链表尾端。
时钟页面置换算法：环形链表，有一个表针指向最老页面。首先检查表针，如果R位是0就淘汰页面，插入页面后表针前移一个位置。如果R位是1就清除R并把表针前移一个位置，直到找到R为0的页面。
最近最少使用页面置换算法（Least Recently Used，LRU）：置换未使用时间最长的页面。
工作集页面置换算法：进程当前正在使用的页面的集合称为它的工作集（working set）。缺页中断时淘汰一个不再工作集中的页面。
工作集时钟页面置换算法

页面置换算法小结

算法	注释
最优算法	不可实现，但可用作基准
NRU（最近未使用）算法	LRU的很粗糙的近似
FIFO（先进先出）算法	可能抛弃重要的页面
第二次机会算法	比FIFO有大的改善
时钟算法	现实的
LRU（最近最少使用）算法	很优秀，但很难实现
NFU（最不常用）算法	LRU的相对粗略的近似
老化算法	非常近似LRU的有效算法
工作集算法	实现起来开销很大
工作集时钟算法	好的有效算法

分页系统中的设计问题

局部分配策略与全局分配策略：当发生缺页中断时，页面置换算法在寻找最近最少使用的页面时，只考虑分配给该进程的页面，称为局部页面置换算法；考虑所有在内存中的页面，称为全局页面置换算法。
负载控制
页面大小：确定最佳页面大小。
分离的指令空间和数据空间：为指令和数据设置分离的地址空间
共享页面：UNIX系统中进行系统调用后，父子进程共享程序文本和数据。这些进程拥有自己的页表，但都指向同一个页面集合。只要有一个进程要求更新数据，就会触发只读保护，引发操作系统陷进，生成该页的一个副本。这种方式称为写时复制。
共享库：如果其他程序已经装载了某个共享库，另一个程序就没必要再次装载了。编译共享库时，使用-fPIC产生位置无关代码。
内存映射文件：进程可以通过发起一个系统调用，将一个文件映射到虚拟地址空间的一部分。在访问页面时每次一页的读入。多个进程可以通过映射同一个文件来通信。
清除策略：如果发生缺页中断时系统中有大量的空闲页框，此时分页系统工作在最佳状态。一种实现清除策略的方法就是使用一个双指针时钟。
虚拟内存接口

有关实现的问题

与分页有关的工作：操纵系统要在四段时间里做与分页相关的工作。进程创建时，进程执行时，缺页中断时，进程终止时。
缺页中断处理
1. 硬件陷入内核，在堆栈中保存程序计数器。
2. 启动一个汇编代码例程保存通用寄存器和其他易失的信息，以免被操作系统破环。
3. 当操作系统发现一个缺页中断时，尝试发现需要哪个虚拟页面。
4. 一旦知道发生缺页中断的虚拟地址，操作系统检查这个地址是否有效，并检查存取与保护是否一致。
5. 如果选择的页框“脏”了，安排该页写回磁盘，并发生一次上下文切换，挂起产生缺页中断的进程，让其他进程运行直至磁盘传输结束。
6. 一旦页框“干净”后，操作系统查找所需页面在磁盘上的地址，通过磁盘操作将其装入。
7. 当磁盘中断发生时，表明该页已经被装入，页表已经更新可以反应它的位置，页框也被标记为正常状态。
8. 恢复发生缺页中断指令以前的状态，程序计数器重新指向这条指令。
9. 调度引发缺页中断的进程，操作系统返回调用它的汇编语言例程。
10. 该例程恢复寄存器和其他状态信息，返回到用户空间继续执行，就好像缺页中断没有发生过一样。
指令备份：使用一个隐藏的内部寄存器。在每条指令执行之前，把程序计数器的内容复制到该寄存器中。
锁定内存中的页面：保证正在做I/O操作的页面不会被移出内存。
后备存储
策略和机制的分离

分段

分页和分段的比较

考察点	分页	分段
需要程序员了解正在使用这种技术吗/td>	否	是
存在多少线性地址空间/td>	1	许多
整个地址空间可以超出物理存储器的大小吗/td>	是	是
过程和数据可以内区分并分别被保护吗/td>	否	是
其大小浮动的表可以很容易提供吗/td>	否	是
用户间过程的共享方便吗/td>	否	是
为什么发明这种技术/td>	为了得到大的线性地址空间而不必购买更大的物理存储器	为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护

4、文件系统

文件

文件命名：在具体系统中规则不一，UNIX文件系统区分大小写，MS-DOS文件系统不区分大小写。
文件结构：字节序列、记录序列、树。所有UNIX、MS-DO、Windows系统都把文件看成无结构字节序列。
文件类型：ASCII文件和二进制文件。
文件存取：顺序存取和随机存取。
文件属性：文件的附加信息，称为属性（attribute）或元数据（matedata）。
文件操作：常用系统调用
- ：创建不包含任何数据的文件。
- ：删除文件释放磁盘空间。
- ：打开文件，把文件属性和磁盘地址表装入内存，便于后续调用。
- ：关闭文件释放内部表空间。
- ：在文件中读取数据。
- ：向文件中写数据。
- ：在文件末尾添加数据。
- ：对于随机存取文件，指定从何处开始取数据。
- ：读取文件属性。
- ：某些属性可由用户设置。
- ：改变已有文件的名字。

一级目录系统：一个目录中包含所有文件，称为根目录。能快速定位文件。
层次目录系统：层次化的目录树结构，几乎所有现代文件系统都采用。
路径名：绝对路径与相对路径。
目录操作：常用基本系统调用。
- ：创建目录，处理目录项.和..外，目录内容为空。
- ：删除目录。
- ：打开目录以备读取。
- ：关闭目录释放内部表空间。
- ：读取目录返回目录下一个目录项。
- ：更改目录名称。
- ：连接技术允许在多个目录中出现同一个文件。
- ：删除目录项。

文件系统的实现

文件系统布局

文件系统存放在磁盘上。多数磁盘划分为一个或多个分区，每个分区中有一个独立的文件系统。磁盘的0 扇区称为主引导记录（Master Boot Record，MBR），用来引导计算机。在MBR的结尾是分区表。该表给出了每个分区的起始地址和结束地址。表中的一个分区被标记为活动分区。在计算几被引导时，BIOS读入并执行MBR。MBR做的第一件事是确定活动分区，读入它的第一个块，称为引导块（boot block），并执行之。引导块中的程序将装在该分区中的操作系统。

一种可能的文件系统布局：

共享文件

磁盘块不列入目录中，而是列入一个与问价本身关联的小型数据结构（i节点中）中。目录将指向这个小型数据结构。
建立一个类型为link的新文件，使其与另一个文件存在连接。新文件中指包含了它所连接的文件的路径名。称为符连接（symbolic linking）。

日志文件系统

基本思想是将整个磁盘结构化为一个日志。每隔一段时间，或是有特殊需要时，被缓冲在内存中的所有未决的血操作都被放到一个单独的段中，作为在日志末尾的一个邻接段写入磁盘。

保存一个用于记录系统下一步将要做什么的日志。这样当系统在完成它们即将完成的任务钱崩溃时，重新启动之后，可以通过查看日志，获取崩溃前计划完成的任务，并完成它们。这样的文件系统称为日志文件系统。

为了增加可信性，一个文件系统可以引入数据库中原子事务（atomic transaction）的概念。

虚拟文件系统

大多数UNIX操作系统都使用虚拟文件系统概念尝试将多种文件系统统一成一个有序的框架。
关键思想解释抽象出所有文件系统的共有部分，并且将这部分代码放在单独的一层，该层调用底层的实际文件系统来具体管理数据。

虚拟文件系统的位置：

中断处理程序
设备驱动程序
与设备无关的I/O软件
用户空间的I/O软件

盘

磁盘
RAID
CD-ROM
可刻录CD
可重写CD
DVD

影响磁盘块读写速度的因素

寻道时间（将磁盘臂移动到适当的柱面上所需的时间）
旋转时间（等待适当扇区旋转到磁头下所需的时间）
实际数据传输时间。

时钟

时钟硬件：晶体振荡器、计数器和存储寄存器。
时钟软件
软定时器

用户界面：键盘、鼠标和显示器

输入软件
- 键盘软件
- 鼠标软件
输出软件
- 文本窗口
- X窗口系统
- 图形用户界面
- 位图
- 字体

6、死锁

资源

所有需要排他性使用的对象都可以称作资源（resource）。资源可以分为两类：

可抢占资源。可以从拥有它的进程中抢占而不会产生任何副作用，例如存储器。
不可抢占资源。在不引起相关的计算失败的情况下，无法把它从占有它的进程处抢占过来。

死锁概述

死锁的规范定义：如果一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事件，那么，该进程集合就是死锁的。

资源死锁的4个条件：

互斥条件。
占有和等待条件。
不可抢占条件。
环路等待条件。

四种处理死锁的策略：

忽略该问题。
检测死锁并恢复。
仔细对资源进行分配，动态的避免死锁。
通过破坏引起死锁的四个必要条件之一，防止死锁的产生。

鸵鸟算法

鸵鸟算法：把头埋到沙子里，假装根本没有问题发生。

死锁检测和死锁恢复

每种类型一个资源的死锁检测。检测是否存在有向图环路。
每种类型多个资源的死锁检测。基于矩阵的算法。
从死锁中恢复
- 利用抢占恢复
- 利用回滚恢复
- 通过杀死进程恢复

死锁避免

资源轨迹图
安全状态和不安全状态
单个资源的银行家算法
多个资源的银行家算法

死锁预防

破环互斥条件
破坏占有和等待条件
破坏不可抢占条件
破坏环路等待条件

其他问题

两阶段加锁
通信死锁
活锁
饥饿

7、多媒体操作系统

多媒体简介

多媒体的两个关键特征：

多媒体使用极高的数据率。
多媒体要求实时回放。

多媒体文件

视频编码

基于人眼的特性：当一幅图像闪现在视膜上时，在它衰退之前将保持几毫秒时间。如果一个图像序列以每秒50或更多张图像闪现，眼界就不会注意到它看到的是不连续的图像。

为了将二维图像表示作为时间函数的一维电压，摄像机用一个电子束对图像进行横向扫描并缓慢地向下移动，记录下电子束经过处光的强度。在扫描的终点处，电子束折回。称为一帧（frame）。

彩色视频采用与单色视频相同的扫描模式，只不过使用了三个同时运动的电子束来显示图像。红、绿、蓝（RGB）三原色。

数字视频最简单的表示方法是帧的序列，每一帧由呈矩形栅格的图像要素即像素（pixel）组成。每个像素RGB三色中的每种颜色用8个二进制位来表示。

音频编码

音频波可以通过模数转换器（Analog Digital Converter，ADC）转换成数字形式。ADC以电压作为输入，并且生成二进制数作为输出。

由于每一样本的位数有限而引入的误差称为量化噪声（quantizatuin）。

电话系统使用的实时脉冲编码调制（pulse code modulation），脉冲编码调制以每秒7位或8位对声音采样8000次，故这一系统的数据率为56000bps或64000bps。由于每秒只有8000个样本，所以4kHz以上的频率就丢失了。

音频CD是以每秒44100个样本的采样率进行数字化的，足以捕获高达22050Hz的频率。

视频压缩

所有的压缩系统都需要两个算法：一个用于在源端进行数据压缩，另一个用于在目的端对数据进行解压缩。分别为编码算法和解码算法。

编码与解码具有某些不对称性。视频信经过编码和解码之后与原始信存在轻微差异时，系统被称为是有损的（lossy）。

JPEG标准

用于压缩连续色调静止图像的JPEG（Joint Photographic Experts Group，联合摄影专家组）。用于压缩运动图像的MPEG不过是分别对每一帧进行JPEG编码，再加上某些帧间压缩和运动补偿等额外的特征。

MPEG标准

MPEG（Motion Picture Experts Group，运行图像专家组）标准是用于压缩视频的主要算法。

MPEG的两个版本均利用了在电影中存在的两类冗余：空间冗余和时间冗余。MPEG-2输出有三种不同的帧组成：

I帧：自包含的JPEG编码静止图像
P帧：与上一帧逐块的差。
B帧：与上一帧和下一帧的差。

音频压缩

最流行的是MP3（MPEG音频层3），属于MPEG视频压缩标准里的音频部分。

音频压缩可由两种方法完成。波形编码技术和感知编码。

多媒体进程调度

调度同质进程
一般实时调度
速率单调调度
最早最终时优先调度

多媒体文件系统范型

VCR控制功能
近似视频点播
具有VCR功能的近似视频点播

文件存放

多媒体文件非常庞大、通常只写一次而读许多次，并且倾向于被顺序访问。

在单个磁盘上存放文件
两个替代的文件组织策略
近似视频点播的文件存放
在单个磁盘上存放多个文件
在多个磁盘上存放文件

高速缓存

块高速缓存
文件高速缓存

多媒体磁盘调度

静态磁盘调度
动态磁盘调度

8、多处理机系统

多处理机

共享存储器多处理机（multiprocessor）是这样一种计算机系统，其两个或更多的CPU全部共享访问一个公用的RAM。

UMA（Uniform Memory Access，统一存储器访问）
NUMA（Nonuniform Memory Access，非统一存储器访问）

多处理机硬件：

基于总线的UMA多处理机体系结构
使用交叉开关的UMA多处理机
使用多级交换的UMA多处理机
NUMA多处理机
多核芯片

声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！