程序员软考基础复习

大学期间考个证，复习一下基础。

第一章计算机系统基础知识

1.1 计算机系统的基本组成

计算机系统

graph LR
计算机系统-->A(硬件系统)
A-->A1(主机)
A-->A2(外部设备)
A1-->A1-1(CPU)
A1-->A1-2(内存储器_主存储器)
A1-1-->A1-1-1(运算器)
A1-1-->A1-1-2(控制器)
A1-1-->A1-1-3(寄存器组)
A2-->A2-1(输入设备)
A2-->A2-2(输出设备)
A2-->A2-3(外存储器)
计算机系统-->B(软件系统)
B-->B1(系统软件)
B-->B2(应用软件)

1.1.1 计算机硬件（基础）

基本的计算机硬件系统由运算器、控制器、存储器、输入设备、输出设备 5 大部件组成。
中央处理单元（CPU）是硬件系统的核心，用于数据的加工处理，能完成各种算数、逻辑运算及控制功能
- 运算器是对数据进行加工处理的部件，主要完成算术和逻辑运算
- 控制器主要功能则是从主存中取出指令并进行分析，控制计算机的各个部件有条不紊地完成指令的功能
- 寄存器是CPU中的记忆设备，用来临时存放指令、数据及运算结果，寄存器速度比内存快得多
存储器是计算机系统地记忆设备
- 内部存储器（内存、主存）：一般用于来临时存放计算机运行时所需要的程序、数据及中间结果
  - 速度快
  - 容量小
- 外部存储器（外存）：可用于长时间保存信息
  - 速度慢
  - 容量大
输入/输出(I/O)**设备位于主机之外，是计算机系统与外界交换信息的装置**
- 输入设备：把转换成二进制形式地信息输入到计算机的存储器中
- 输出设备：把运算处理结果按照人们所要求的形式输入到外部存储器介质上

1.1.2 计算机软件（重要组成部分）

系统软件

如操作系统、数据库等
应用软件

各种应用程序如：WPS办公软件等

1.1.3 计算机分类

个人移动设备

如：平板、手机
桌面计算机

如：台式机、笔记本
服务器

提供大规模和可靠文件及计算机服务，强调可用性、可扩展性和很高的吞吐率。
集群/仓库级计算机

将数万个服务器连接在一起形成大规模集群称为仓库及计算机
超级计算机

规格高，性能比个人电脑强许多，具有很强的计算机能力，能耗巨大

我国的超级计算机：银河、天河、曙光、神威四个系列
嵌入式计算机

专用领域，针对某个特定的应用

如：微波炉、洗衣机、数码产品，网络交换机和汽车等

1.2 数据的表示及运算

1.2.1 数制与转换

四种进位计数制
- 十进制(D)：逢十进一
- 二进制(B)：逢二进一
- 八进制(O)：逢八进一
- 十六进制(H)：逢十六进一
基数：指各种进位计数制中所使用的数码的个数，用R表示。如十进制R=10
位权：从右往左第i位位权的大小为Rⁱ
进制转换
- 非十进制 —> 十进制：位权相加法
- 十进制 —> 非十进制：取余法(除基数余整数，由下而上排列)
- 十进制小数 —> 非十进制小数：乘积取整法（乘基数取整数，由上而下排列）
- 二进制转八进制：整数从右向左三位并一位，小数部分从左向右三位并一位
- 八进制转二进制：一位拆三位
- 二进制转十六进制：整数从右向左四位并一位，小数部分从左向右四位并一位
- 十六进制转二进制：一位拆四位

1.2.2 二进制逻辑运算

与运算：“ ∧ ”或“ · ”表示。

原则：仅当两个参加运算的逻辑值都为“1”时，与的结果才为“1”，否则为“0”
或运算：“ ∨ ”或“ + ”表示。

原则：仅当两个参加运算的逻辑值都为“0”时，或的结果才为“0”，否则为“1”
非运算：“ ~ ”或在逻辑值的上方加以横线“ — ” 表示

原则：按逻辑值取反
异或运算：XOR或“ ⊕ ”表示

原则：同为0，异为1

1.2.3 机器数与码制

机器数：各种数据在计算机中表示的形式称为机器数，其特点采用二进制计数制，数的符号用0、1表示，小数点则隐含表示而不占位置。其及其对应的实际数值称为数的真值。
- 无符号位：表示正数
  - 纯整数：约定小数点位置在机器数最低位之后
  - 纯小数：约定小数点位置在机器数最高位之前
- 有符号为：机器数最高位为“0”表示正数，最高位为“1”表示负数
  - 纯整数：约定小数点位置在机器数值最低位之后
  - 纯小数：约定小数点位置在及其数值最高位之前，符号位之后
码制
- 源码
  
  源码就是符号位加上真值的绝对值，即用第一位表示符号，其余位表示值
- 反码
  
  正数的反码是其本身
  
  负数的反码是在其源码的基础上，符号位不变，其余各个位按位取反
- 补码
  
  正数的补码是其本身
  
  负数的补码是在其源码的基础上，符号位不变，其余各位取反，最后+1（即在反码的基础上+1）
- 移码
  
  补码的数值部分不变，符号取反
注意点：
1. 补码对于数字0，在补码表示中，0有唯一的编码[±0]补=0000 0000，换句话说，数值0采用补码形式下表是，机器位数全为0
2. 8位字长的表示补码（1000 0000）最小整数-128

1.2.4 定点数、浮点数

定点数：小数点的位置是固定不变的
- 定点小数：小数点隐含固定在最高数据位的左边，整数位则用于表示符号为，用于表示纯小数
- 定点整数：小数点隐含固定在最低数据位之后，最高位还是为符号位，用于表示纯整数
浮点数：小数点的位置由阶码规定的，因此是浮动的。
- 在计算机中通常把浮点数N分成阶码和尾数两部分组成
  
  N=尾数*基数^阶码（尾数是一个规格化的纯小数）
- IEEE754标准
  
  格式规范：阶符阶码尾符尾数

1.2.5 常用字符编码（了解）

BCD码（8421码）：是指每位十进制数用4位二进制数编码表示。选用0000~~1001来表示0~~9这10个数字。
- 直观
- 简单
ASCII码：计算机中常用字符编码（又称”美国标准信息交换代码“）

用7位二进制数表示一个字符；实际存储时，每个字符用一个字节存储，最高位设置成0
- 最多可以表示128个字符，编码为0~127，包括10个数字符号、52个大小写英文字母、32个标点符号和运算符以及34个控制符
- 典型ASCII码值：A为65，a为97，0为48
汉字字符编码
输入码

用于输入汉字的编码，也称为外码

将键盘的按键组合对应一个或几个汉字
- 数字编码：国标区位码将6763个汉字分成94个区，每区94个字，区码位码各占两位十进制数，每个汉字对应4位十进制数
- 拼音码：用汉字的拼音去对应汉字，有重字
- 字形码：五笔字型
国标码（GB2312-80)：是其他汉字编码的基础
机内码
- 机器内部存储和处理汉字是使用的编码，用两个字节表示一个汉字
- 将国标码的两个字节高位置为1，避免与ASCII码冲突
输出码—字形码
- 点阵方式：有笔画用1表示，无笔画用1表示，放大后效果极差
Unicode：统一的表示世界各国文字

国际标准化组织1993年公布了”通用多八位编码字符集“国际化标准ISO/IEC 10646，简称UCS
- 万国码
- 单一码
- 统一码

1.2.6 校验码（重要）

奇偶校验码（只能检查错误，不能纠正错误）

一种通过增加冗余位使得码字中”1“的个数恒为奇数或偶数的编码方法，它是一种检错码
- 奇校验
  
  整个校验码（有效信息位和校验位）中”1“的个数为奇数
- 偶校验
  
  整个校验码（有效信息位和校验位）中”1“的个数为偶数
- 垂直校验：原理和上面一样，只是方向变为垂直
- 垂直水平校验：原理同上，既有水平方向的校验，又有竖直方向的校验
海明码（既能检查错误，又能纠正错误）

在传输码列中加上冗余位，每个数据位由确定位置关系的校验位来校验。

海明码用于多位并行数据检错纠错处理
循环冗余校验码（CRC）

模2除法运算中间过程基于异或运算

利用多项式k个数据位产生r个校验码进行编码，其编码长度为k+r

循环冗余校验码由两部分组成，左边为信息吗，右边为校验码，若信息码占k位，则检验码占n-k位，所以又称位（n，k）码

1.3 计算机系统组成及工作原理

计算机系统：
- 硬件系统
- 软件系统

1.3.1 计算机系统的基本组成

1.3.2 计算机硬件系统

中央处理器CPU
- 控制器：控制器是计算机的指挥中心
- 运算器：专门负责处理数据的部件，既能进行算数运算，又能进行逻辑运算
- 寄存器：处理器内部的暂时存储单元，用来暂存指令，数据和地址
- 通常用CPU的类型+主频来表示一款CPU
  - 如PIV 2.5G，则表示Intel公司生产的PIV型号主频为2.5GHz的CPU
- 字长：通常用子长来表示CPU的另一个指标
  - 执行一条指令时可以处理的二进制位数
  - CPU有8位、16位、32位和64位
存储器 — 内部存储器
- 内存储器由ROM和RAM组成
  - 只读存储器ROM
    - 用于检查计算机系统的配置情况并提供最基本的I/O控制程序，如存储BIOS参数的CMOS芯片
    - 计算机断电后存储器中的数据仍然存在
  - 随机存储器RAM
    - RAM中的信息随着计算机的断电自然消失
    - 内存容量通常是指RAM的容量
- 高速缓冲存储器（Cache 采用双极性静态RAM,即SRAM，它的访问速度时DRAM的10倍左右，容量相对较小）
  
  为了协调二者之间的速度差异，在二者之间采用了高速缓冲存储器
存储器 — 外存储器
- 硬盘：
  - 相关参数
    - 转速：5400rpm、7200rpm
    - 平均寻道时间：越短性能越好
  - 注意
    - 硬盘工作时，避免强烈震动
- 光盘
  - CD-ROM：150Kb/s
  - CD-R：只写一次性光盘
  - CD-RW：可擦写型光盘
- 光驱
- DVD（数字多功能光碟）
  - 容量比CD提升几十倍
  - 速度比CD快得多
  - 向下兼容
移动存储设备
- U盘
  - 通过USB接口与计算机连接
  - 即插即用
- 移动硬盘
  - 流行的大容量移动存储设备
计算机中的信息存储单位及相互换算关系（重点）
- 位（bit）：表示信息的最小数据单位，是二进制的一个数位，通常用”b“表示
- 字节（Byte）：表示信息的基本数据单位，1个字节由8个二进制位组成，通常用”B“表示
  
  1个字符占1个字节，1个汉字占2个字节
  
  字节（B）、千字节（KB）和兆字节（MB）以及十亿字节（GB）换算关系
  - 1 B = 8 bit
  - 1 KB = 2¹⁰B = 1024 B
  - 1 MB = 2¹⁰ KB = 1024 KB
  - 1 GB = 2¹⁰ MB = 1024 MB
- 字（Word）：每个字中所含的位数，是由CPU的字长所决定，它总是字节的整数倍。
输入设备
- 鼠标
  - 光电式鼠标
  - 光机式鼠标
  - 无线鼠标
- 键盘
  
  104键使用最广泛
输出设备
- 显卡：将显示器介入主机的接口电路
- 显示器
  
  CRT显示器，液晶显示器LCD,触摸屏
  - 分辨率：每帧画面的像素决定
  - 刷新频率：单位时间屏幕的刷新次数
  - 点距：相邻两个像素间对角线距离
- 打印机
  - 种类
    - 针式打印机：文字和报表
    - 喷墨打印机：喷头易阻塞
    - 激光打印机：造价相当高
  - 技术指标
    - 分辨率DPI(Dots per inch)：衡量打印图像清晰度的重要指标
    - 打印速度PPM(Pages per minute)：反应打印的快慢成都
    - 最大支持打印幅面：打印幅面越大，价格越贵
系统主板 — 电脑系统各硬件模块间沟通的重要桥梁
总线（BUS）

实现微处理器、存储器和外部输入、输出接口之间相互传送信息的公共通路
- 地址总线（AB）
- 数据总线（DB）
- 控制总线（CB）

1.3.3 计算机系统的配置与性能指标

微机系统基本配置

微处理器、内存、硬盘、显示器、操作系统……
微机系统的性能指标
- 字长：指计算机处理指令或数据的二进制位数。16位、32位及64位等，目前流行的微机字长为64位
- 速度：以每秒中执行的指令条数来表示，也常用处理器的主频来表示
- 容量：指内存的容量
- 带宽：表示计算机的数据传输速率，反映了计算机的通信能力
- 版本：版本序号反应计算机硬件、软件产品不同的生产日期
- 可靠性：是指在给定的时间内，微机系统能正常运行的概率。通常用平均无故障时间（MTBF）来表示。MTBF的时间越长，表明系统的可靠性越好

1.3.4 输入/输出技术

graph LR
A(输入输出技术)-->接口的功能及分类
A-->B(主机和外设间的连接方式)
B-->总线型
B-->星型
B-->E(通道方式)
B-->I/O处理机
A-->C(I/O接口的编址方式)
C-->与内存单元统一编址
C-->I/O接口单独编址
A-->D(CPU与外设之间交换数据的方式)
D-->直接程序控制
D-->中断方式
D-->DMA方式
D-->通道方式

接口

又称界面，是指两个相对独立的子系统之间的相连部分。用于连接主机和I/O设备的转化机构就是I/O接口电路

功能
- 地址译码功能
- 在主机和I/O设备间交换数据，控制命令集状态信息等
- 支持主机采用程序查询，中断，DMA等方式
- 提供主机和I/O设备所需要的缓冲，暂存，驱动功能
- 进行数据的类型，格式等方面的转化
分类
- 按数据的传送格式分类
  - 并行接口
  - 串行接口
- 按主机访问I/O设备的控制方式
  - 查询接口
  - 中断接口
  - DMA接口
  - 通道控制器
  - I/O处理机
- 按时序控制方式
  - 同步进口
  - 异步接口
连接方式
- 总线型（基本方式）、
  
  总线协议：
  - 信号线的定义
  - 数据格式
  - 时序关系
  - 信号电平
  - 控制逻辑
- 星型
- 通道方式
- I/O处理机
输入、输出接口的编址方式
- 与内存单元统一编址
  
  将I/O接口中有关寄存器或存储器部件看作存储器单元，与主存中的存储单元统一编址
- I/O接口单独编址
  
  通过设置单独的I/O地址空间，为接口中的有关寄存器或存储部件分配单独地址码
CPU与外设之间变换数据的方式
1. 直接程序控制
  - 程序查询方式：CPU通过执行程序查询外设的状态，判断外设是否准备好进行数据传送
  - 立即程序传送方式：I/O接口总是准备好接受来自主机的数据，或随时准备向主机输入数据
2. 中断方式
  - 中断是在发生了一个外部事件时调用相应的处理程序的过程。中断服务程序与CPU正在运行的程序是相互独立，相互不传递的数据
3. DMA方式
  - 用于告诉外围设备与内存之间批量数据的传输，其实用一个专门的DMA控制器来完成内存与设备之间之境界数据传送
  不用CPU干预。当本次DMA传送的数据全部完成时，才发生终端，请求CPU进行结束处理。
4. 通道方式
  
  通道是一个用来控制外围设备工作的专用处理机。他对外围设备实现统一管理，代替CPU对I/O操作进行控制，从而使I/O操作可以与CPU并行工作

1.4 指令系统简介

指令：是控制计算机完成某种特定操作的命令，是能被计算机识别并执行的二进制代码

操作码（指明该指令要完成的操作）+ 操作数（指明操作对象的内容或所在的存储单元地址（地址码））

指令执行过程

1 2	graph TD 取指令-->分析指令-->执行指令-->为下一条指令做好准备-->取指令

寻址方式
- 立即（数）寻址
- 直接（内存）寻址
- 存储器间接寻址
- 寄存器直接寻址
- 寄存器间接寻址
- 寄存器相对寻址（操作数地址=指令地址+偏移量）
- 偏移寻址
  - 基址寻址（基址寄存器）
  - 变址寻址（变址寄存器）
  - 相对寻址

1.5 多媒体系统简介

1.5.1 数字声音

声音是由于物体振动产生的一种连续的波。声波在时间和幅度上都是连续的模拟信号，称为模拟声音信号

两个基本参数
- 幅度：指声波的振幅，通常用声压级表示，计量单位为分贝dB
- 频率：指声波每秒变化的次数，用Hz表示。人耳能听到的频率范围：20Hz-20kHz
  - < 20 Hz的称为亚音信号、次声波
  - ＞20 kHz的成为超音频信号、超声波
- 分类
  - 乐音：如果所有泛音频率都是基音的整数倍，这个复合音称为乐音
  - 噪音：如果包含非整数被基音频率的泛音，这种声音我们称之为噪音
  - 音色：音色是由基音与泛音的比例、泛音的分布、泛音随之间的衰变决定的。不同乐器一般音色不同
声音信号的数字化（重要）

声音是一种模拟信号，计算机要对它处理，必须首先将其转换为数字声音信号，即用二进制数字的编码形式来表示声音。

采样

采样频率需要大于声音信号最高频率的两倍
量化

量化是把在幅度上连续取值（模拟量）的每一个样本转化为一个离散值（数字量），量化后用二进制表示，bit位的多少反映了度量声音幅度的精度，称为量化精度/量化位数/量化分辨率
编码

便于存储数据和传输，再按照某种格式将其组织为文件，还可以进行数据压缩

波形声音信息计算
- 数据传输率 bps = 采样频率Hz * 量化位数bit * 声道数
- 声音信号数据量 Byte = 数据传输率bps * 持续时间s / 8

声音合成
- 语音合成
- 音乐合成

声音文件格式
1. Wave文件（.wav）：Windows系统中所用的标准音频文件格式，它源于对声音波形的采样，即波形文件。利用该格式记录声音文件能够和原声基本一致，质量非常高，单间数据量非常大
2. Sound文件（.snd）：NeXTComputer公司推出的数字声音文件格式，支持压缩
3. Audio文件（.au）：Sun Microsystems公司推出的广泛应用于UNIX系统中的数字声音文件格式
4. AIFF格式（.aif）：Apple公司在Mac OS的标准音频文件格式
5. Voice格式（.voc）：Creative公司波形音频文件格式，也是声卡使用的音频文件格式。每个VOC文件由文件头块和音频数据块组成
6. MPEG-1 Audio Layer 3 文件（.mp3）：现在最流行的声音文件格式，压缩率大，能够使用极低码率提供接近CD音质的声音重放效果
7. RealAudio文件（.a）：这种格式具有强大的压缩量和极小的失真，它也是为了解决网络传输带宽不足而设计的，因此主要目标是压缩比和容错性，其次才是音质
8. MIDI文件（.mid/.rmi）：MID文件格式由MIDI继承而来，它并不是一段录制好的声音，而是记录声音的信息，然后再告诉声卡如何再现音乐的一组指令。这样一个MIDI文件每存1min的音乐只用大约5~10KB

1.5.2 图形与图像

图形：矢量表示的图形
图像：像素点描述的位图，一般是用摄像头机或扫描仪等输入设备捕捉实际场景画图，离散化维空间、亮度、颜色的序列值
颜色：创建图像的基础。
- 三要素
  - 色调
  - 饱和度
  - 亮度
- 颜色模型
  - RGB颜色模型（红绿蓝）
  - CMY颜色模型（青品红黄）
  - YUV彩色模型（明亮度，色度，浓度）
分辨率和像素深度
1. 显示分辨率和图像分辨率
  - 显示分辨率：显示屏上能够显示出的像素数目
  - 图像分辨率：指组成一幅图像的像素密度，也是用水平和垂直的像素表示，即每英寸多少点（dpi）表示数字化图像的大小
2. 像素深度
  
  像素深度是指储存每个像素所用的二进制位数，它也是用来度量图像的色彩分辨率的
图像的获取
- 利用数字图像库的图像
- 绘图软件创建的图像
- 数字转换设备采集图像
  - 采样
  - 量化
  - 编码
图形图像的转换

图形和图像在一定的条件下可以转换
- 如采用栅格化（点阵化）技术可以将图形转换成图像
- 采用图形跟踪技术可以将图像转换成图形
- 一般可以通过硬件（输入/输出设备）或软件实现图形和图像之间的相互转换
图像的压缩编码以及标准
- 如果按照像素点以及深度映射的图像数据大小采样，可用下面的公式估算数据量
图像数据量 ( B ) = 图像的总箱数 * 图像深度 / 8
- 数据压缩可分为两类
  - 有损压缩
  - 无损压缩
图像文件格式
1. BMP文件（.bmp）：BMP格式是微软公司制定的图形标准，优点就是在PC上兼容度一流，几乎能被所有的图形软件“接受”，可称为通用格式，就算不装任何看图软件，用Windows的“画笔”一样可以看。其结构简单，未经过压缩，储存为bmp格式的图形不会失真，但文件比较大，而且不支持Alpha（透明背景）通道。
2. JPEG文件（.jpg）：JPG格式是目前网络上流行的图形格式，它可以把文件容量压缩到很小的格式。JPG支持不同程度的压缩比，您可以视情况调整压缩倍率，压缩比越大，品质就越低；相反地，压缩比越小，品质就越好。不过要注意的一点是，这种压缩法属于失真型压缩，文件的压缩会使得图形品质下降。
  
  JPEG（Joint Photographic Experts Group，联合图形专家组）是由CCITT（国际电报电话咨询委员会）和ISO（国际标准化组织）联合组成的一个图像专家组。
3. GIF文件（.gif）：一种位图。位图的大致原理是：图片由许多的像素组成，每一个像素都被指定了一种颜色，这些像素综合起来就构成了图片。GIF采用的是Lempel-Zev-Welch（LZW）压缩算法，最高支持256种颜色。由于这种特性，GIF比较适用于色彩较少的图片，比如卡通造型、公司标志等等。如果碰到需要用真彩色的场合，那么GIF的表现力就有限了。GIF通常会自带一个调色板，里面存放需要用到的各种颜色。在Web运用中，图像的文件量的大小将会明显地影响到下载的速度，因此我们可以根据GIF带调色板的特性来优化调色板，减少图像使用的颜色数（有些图像用不到的颜色可以舍去），而不影响到图片的质量。
4. TIFF文件（.tif）：一种灵活的位图格式，主要用来存储包括照片和艺术图在内的图像，最初由Aldus公司与微软公司一起为PostScript打印开发。TIFF与JPEG和PNG一起成为流行的高位彩色图像格式。TIFF格式在业界得到了广泛的支持，如Adobe公司的Photoshop、The GIMP Team的GIMP、Ulead PhotoImpact和Paint Shop Pro等图像处理应用、QuarkXPress和Adobe InDesign这样的桌面印刷和页面排版应用，扫描、传真、文字处理、光学字符识别和其它一些应用等都支持这种格式。从Aldus获得了PageMaker印刷应用程序的Adobe公司控制着TIFF规范。
5. PNG文件（.png）：文件格式是作为gif的替代品开发的，它能够避免使用gif文件所遇到的常见问题。它从gif那里继承了许多特征，而且支持真彩色图象。更重要的是，在压缩位图数据时它采用了一种颇受好评的lz77算法的一个变种，lz77则是lzw的前身，而且可以免费使用。PNG文件格式支持无损数据压缩。
6. WMF文件（.wmf）：WMF文件只使用在windows中，它保存的不是点阵信息，而是函数调用信息。它将图像保存为一系列GDI的函数调用。WMF文件具有设备无关性，文件结构好，但是解码复杂，其效率比较低。

1.5.3 动画和视频

动画：将静态的图像、图形等按照一定的时间顺序显示而形成的连续的动态画面。传统意义来说动画是在连续多格的胶片上拍摄的一系列画面，比将胶片以一定的速度放映，从而产生动态的视觉技术。
1. 实时动画
  
  采用各种算法来实现物体运动的机制，常用的算法有运动学算法、动力学算法、反向运动算法。
2. 矢量动画
  
  由矢量图衍生的动画形式，矢量图是利用数学公式来记录和表示图形线条、颜色、尺寸和坐标等属性。矢量动画是通过计算机的处理矢量图实现各种动画效果，如位移、变形和变色等。
3. 二维动画
  
  二维动画是对传统动画的改进，不仅具有传统动画的制作过程，而且可以发挥计算机的特有功能比如图像可以复制、粘贴、翻转、缩放、移动位置、自动计算等。
4. 三维动画中的景物有正面、反面、侧面，通过调整三维的空间点可以看到不同的内容。建立三维动画物体模型称为造型，可以在计算机内生成一个具有一定形体的几何模型。有以下三种形式记录一个物体的模型：线框模型、表面模型、实体模型。三维动画最终要生成一幅二维画面，并按一定格式记录下来称为动画的生成。
视频：活动的、连续的图像序列。一幅图像称为一帧，其中的每一幅与前一幅略有差别。
1. 模拟视频
  
  电视是当代最有影响力的多媒体信息传播工具，综合文字、图像、声音等作为信息传播媒体，传播的信号是模拟信号。
  
  传输信号：分量视频、复合视频、分离视频信号。
2. 数字视频
  
  计算机的数字视频是基于数字技术的图像显示标准，它能将模拟信号输入到计算机进行数字化视频编辑制成数字视频。模拟信号进入计算机需要要解决模拟信号数字化的问题，视频数字化的目的模拟信号经模/数转换和彩色空间变换的过程，转换成计算机可以显示和处理的数字信号。
  
  模拟视频进行数字化方法：先从复合彩色电视图像中分离彩色分量、然后数字化；先对全彩色电视信号数字化，以获得YUV、YIQ、RGB分量信号。
3. 视频压缩编码
  
  视频压缩主要目的是尽可能保证视觉效果的前提下减少视频的数据量。
  
  帧内压缩：也称为空间压缩。把单独的图像帧当做静态图像应用静态图像的压缩算法实现数据压缩。
  
  帧间压缩：视频具有时间上的连续性，可以利用帧间信息的冗余进行压缩。通常采用基于运动补偿的帧间预测编码技术。
4. 视频文件格式
  - Flic文件（.fli/.fic）：Flic文件是Autodesk公司在其出品的Autodesk Animator/Animator Pro/3D Studio等2D/3D的动画制作软件中采用的彩色动画文件格式。Flic文件采用行程编码（RLE）算法和Detla算法进行无损压缩，具有较高的数据压缩率。
  - AVI文件（.avi）：它是由Microsoft公司开发的一种数字音频与视频文件格式，AVI格式允许视频和音频交错在一起同步播放，但AVI文件没有限定压缩标准，即AVI文件格式不具有兼容性。不同压缩标准生成的AVI文件，就必须使用相应的解压缩算法才能将之播放出来。我们常常可以在多媒体光盘上发现它的踪影，一般用于保存电影、电视等各种影像信息，有时它也出没于Internet中，主要用于让用户欣赏新影片的精彩片段。它最直接的优点就是兼容好、调用方便而且图象质量好，因此也常常与DVD相并称。但它的缺点也是十分明显的,体积大。
  - Quick Time文件（.mov/.qt）：是Apple公司开发的一套完整的多媒体平台架构，可以用来进行多种媒体的创建，生产，和分发，并为这一过程提供端到端的支持：包括媒体的实时捕捉，以编程的方式合成媒体，导入和导出现有的媒体，还有编辑和制作，压缩，分发，以及用户回放等多个环节。QuickTime文件格式是QuickTime整个架构体系中的一环，非常基础和重要的一环。QuickTime的多媒体架构应用于Mac OS和Windows系统上，而QuickTime文件格式是平台无关的，可以应用于各类系统。
  - MPEG文件（.mpeg/.mpg/.dat/.mp4）：MPEG文件格式是指使用MPEG标准算法压缩的视频文件。在PC上有统一的标准格式，兼容性相当好。.mp4是采用MPEG-4中的视频编码技术进行视频编码的文件格式。
  - RealVideo文件（.rm/.rmvb）：RealVideo文件是Real Networks公司开发的一种流式视频文件格式，包含在Real Networks公司所指定的音频视频压缩规范RealMedia中，主要用来在低速率的广域网上实时传输活动视频影像，它可以根据网络数据传输速率的不同而采用不同的压缩比率，从而实现影像数据的实时传输和实时播放。RealVideo除了可以以普通的视频文件形式播放之外，还可以与RealVideo服务器相配合，实时流式媒体传输。

第二章操作系统基础知识

2.1 操作系统概述（Opertating System, OS）

2.1.1 操作系统的作用、特征与功能

作用

操作系统有效地组织和管理系统中的软、硬件资源，合理地组织计算机系统工作流程，控制程序的执行，并且向用户提供一个良好的工作环境和友好的接口。
特征：
- 并发性
  
  两个或两个以上的事件在同一时间间隔中发生
- 共享性
  
  多个并发执行的程序可以共同使用系统的资源
- 虚拟性
  
  通过虚拟技术把一个物理设备虚拟为多个逻辑设备
- 不确定性
  
  操作系统并发执行系统内各种进程，各种运行故障，输入输出，中断，发生时间不可预测
功能
1. 进程管理
  
  有效地、合理地分配CPU的时间。
2. 存储管理
  
  完成存储分配、地址转换、信息保护以及存储扩充等工作。
3. 文件管理（信息管理）
  
  对文件进行组织管理、提供方便的存取和文件的安全保证机制。
4. 设备管理
  
  对各种各样的设备进行有效地管理，为用户提供方便的操作，提高设备的利用率。
5. 作业管理
  
  包括任务、界面管理、人机交互、图形界面、语音控制和虚拟现实等。
上述五项功能是对操作系统软，硬件资源的管理。除此之外，操作系统需要提供用好的用户接口命令和图形接口，通过这两种命令请求操作系统的服务。

2.1.2 操作系统分类及特点

批处理系统（Batch Processing System）

批处理系统是一种成批处理用户作业的操作系统。
- 处理过程：
用户根据任务需求编制好程序，准备好数据以及作业操作说明书，一次提交给系统，然后不再与作业进行交互，直到作业运行完毕，按指定时间收取运行报告后，才能根据输出结果分析，确定是否需要进行修改再次上机。用户提交的作业不是立即执行，由系统操作员分批进行处理，每批中的作业由操作系统控制执行。
- 主要特征：
1. 用户脱机使用计算机
2. 作业成批处理
3. 多道程序运行
单道批处理系统：用户一次提供已安排好先后顺序的多个任务，由操作系统按照顺序自动完成任务运行的全过程。

多道批处理系统：又称多任务操作系统，用户提供多个任务同时运行，用户将要执行的任务和要求一起交代给计算机，然后由操作系统调度并协调各个作业运行，直到完成全部运行。
分时操作系统（Time Sharing System）

分时系统是一种将CPU时间划分成很小的时间片，按时间片轮转法分配给多个终端用户使用的操作系统。
- 处理过程：
多个用户或程序分时共享硬件和软件资源，每个用户或程序在属于自己的时间片内使用计算机，依次轮转。多用户分时是当今操作系统中普遍采用的一种方式UNIX就是典型的多用户分时操作系统
- 主要特征
多路性：多个用户同时工作。共享系统资源，提高了资源利用率。

独占性：各用户独立操作，互不干扰，用户感觉独占计算机。

及时性：及时对用户的操作进行响应，提高调试和修改程序的效率，缩短了周转时间。

交互性：用户根据系统响应结果进一步提出新请求（交互会话工作方式）。
实时操作系统(Real Time Operating System)

实时系统是指对于特定的输入，系统能够在极短的时间内作出响应，并完成对该输入请求处理的操作系统。
- 处理过程：Linux
实时系统采用了时间片分时技术，也具有及时性，多路性，独占性和交互性等四个特征。不过，实时操作系统与分时系统之间还是有很大的区别的。实时系统一般是专用的，其交互能力比较差，它只允许用户访问数量有限的专用程序。
- 主要特征
  - 实时性
  - 可靠性
- 主要应用：飞机售票系统，航天发射系统，生产过程自动控制、事务处理等有实时要求的领域。
分布式操作系统(Distributed Operating System）

分布式系统是指通过计算机网络将物理上分布的具有自治功能的数据处理系统或计算机系统互连起来，实现信息交换或资源共享，协作完成处理任务的操作系统。
- 处理过程：
以计算机网络为基础，所有系统任务可在系统中任何处理机上运行，自动实现全系统范围内的任务分配并自动调度各处理机的工作负载。
- 基本特征
  - 功能和任务的分布性
  - 高可靠性
网络操作系统(Network Operating System )

网络操作系统是在通常操作系统功能的基础上提供网络通信和网络服务功能的操作系统。
- 主要性能：
除具有一般操作系统的基本功能外，还应具有网络管理模块。负责管理整个网络资源，保证网络中信息传输的准确性、安全性和保密性，提高系统资源的利用率和可靠性。

网络功能与操作系统的结合程度是网络操作系统的重要性能指标。早期的做法是通常操作系统附加网络软件，过渡到网络功能成为操作系统的有机组成部分。
- 代表产品：Netware、UNIX、Linux及Windows系列。
嵌入式系统（Embedded Operating System）

嵌入式操作系统是指运行在嵌入式系统中，对整个嵌入式系统以及它控制的各种资源进行统一管理和调度的操作系统。
- 主要性能：
嵌入式操作系统能够有效管理复杂的系统资源，具有实时高效性、软件固态化以及应用专业化等特点。嵌入式操作系统在制造业、过程控制、家用电器的智能化控制等领域中都得到了很好的应用。内核可剪裁，适合各种专门用途，如手机、PDA、各种专用设备。
- 基本特征：
（1）微型化

（2）可定制

（3）实时性

（4）可靠性

（5）易移植性
微机操作系统（Microcomputer Operating System）

微机操作系统是配置在微型计算机上的操作系统。常见的微机操作系统有DOS、windows、UNIX和Linux。
- 单用户单任务操作系统MS-DOS
  
  MS-DOS是Microsoft公司开发的首先在IBM-PC机上使用的微机OS，MS-DOS操作系统现成了事实上的16位微机单用户单任务操作系统的标准。
单用户多任务操作系统MS Windows
- Windows98/2000/XP是Microsoft公司开发的一个图形用户界面的多任务、多线程、全32位的操作系统。
多用户多任务操作系统SCO UNIX

2.2. 进程管理

2.2.1 基本概念

进程管理也称为处理机管理，其核心是如何合理地分配处理机的时间，提高系统的效率。在计算机系统种有多个并发执行的程序，采用“程序”这个静态的概念已经不能描述程序执行时动态变化的过程，所有引入了“进程”。

主要任务：完成处理机资源的分配调度，处理机调度的单位可为进程或线程。
- 进程控制
- 进程同步与互斥
- 进程通信
- 进程调度
进程组成

进程是动态的概念。进程通常由程序，数据和进程块PCB组成。
- 程序：描述进程要完成的功能。
- 数据：程序在执行时所需要的数据和工作区。
- PCB：包含进程的描述信息和控制信息。它是进程存在的唯一标志。进程控制块
进程的状态以及状态间的切换

进程在执行过程中，由于操作系统中出现的不同事件导致进程执行的间歇性、不确定性，使进程的状态也随执行过程发生变化。

有三种状态：
- 就绪:进程已获除CPU外的资源,一旦得到CPU使用权就可立即运行。
- 运行:任何时刻只能有一个进程处于运行状态.在多处理机系统中,可以有多个进程运行。
- 阻塞:由于等待某个事件，如申请打印输出，而打印机被其他进程占用，进程被挂起。

2.2.2 进程控制

进程控制是指对系统中所有进程从创建到消亡的全过程实施有效的控制

进程控制是由操作系统内核中的原语实现的

原语是若干条机器指令组成的、用于完成特定功能的程序段。原语的特点是在执行时不能被分割，即原子操作要么都做，要么都不做。内核中所包含的原语主要有进程控制原语、进程通信原语、资源管理原语以及其他原语。

2.2.3 进程通信

同步和互斥概念

操作系统引入进程后，由于进程的异步性，可能会导致程序执行结果的不确定性，使程序执行时出现不可再现性。

进程互斥与同步的主要任务是使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。

同步：指多个进程中发生的事件存在着某种时序关系，它们必须按规定时序执行，以共同完成一项任务。
互斥：多个进程不能同时使用同一资源。
临界资源：某段时间内仅允许一个进程使用的资源。
临界区：每个进程中访问临界资源的那段代码。

信号量机制
- 信号量机制
  
  即利用pv操作来对信号量进行处理。
- 信号量
  
  一个特殊的变量，用于进程间传递信息的整数值，信号量的值与相应资源的使用情况有关。
- 信号量S
  
  当它的值S>=0时，表示当前可用资源的数量；
  
  当它的值S<0时，其绝对值表示阻塞队列等待使用该资源的进程个数。
注意：

信号量的值仅能由PV操作来改变以及初始化。

P操作和V操作都是不可分割的原子动作，也称为原语。

P操作表示申请一个资源

V操作表示释放一个资源
信号量机制实现进程互斥

令信号量mutex的初值为1，进入临界区时执行p操作，退出临界区时执行V操作。
信号量机制实现进程同步

同步的时序关系不能改变

进程调度算法

进程调度：解决以何种次序对各就绪进程进行处理机的分配以及按何种时间比例让进程占用处理机。

所谓可剥夺方式，是指就绪队列中一旦有优先级高于当前运行进程的优先级的进程存在时，便立即发生进程调度，转让处理机
非剥夺方式则是指即使在就绪队列中存在有优先级高于当前运行进程的进程，当前进程仍将继续占有处理机，直到该进程完成或某种事件发生（如 I/O 事件）让出处理机

先来先服务调度算法（FCFS）

这种调度算法是按照进程进入就绪队列的先后次序选择可以占用处理器的进程。当有进程就绪时，把该进程排入就绪队列的末尾，而进程调度总是把处理器分配给就绪队列中的第一个进程。一旦一个进程占有了处理器，它就一直运行下去，直到因等待某事件或进程完成了工作才让出处理器。
优先数调度算法（HPF）

对每个进程确定一个优先数，进程调度总是让具有最高优先数的进程先使用处理器。如果进程具有相同的优先数，则对这些有相同优先数的进程再按先来先服务的次序分配处理器。就绪队列中进程可按优先数从大到小排列，这样，进程调度也总是把处理器分配给就绪队列中的第一个进程。进程被创建时系统为其确定一个优先数，进程的优先数可以是固定的，也可随进程的执行过程而动态变化。优先数调度算法分为“非抢占式”的与“可抢占式”的两种。
时间片轮转调度算法（RR)

系统规定一个“时间片”的值。调度算法让就绪进程按就绪的先后次序排成队列，每次总是选择就绪队列中的第一个进程占用处理器，但规定只能使用一个“时间片”。如果一个时间片用完，进程工作尚未结束，则它也必须让出处理器而被重新排到就绪队列的末尾，等待再次运行，当再次轮到运行时，重新开始使用一个新的时间片。这样，就绪队列中的进程就依次轮流地占用处理器运行。

轮转法主要是用于分时系统的调度算法，它具有较好的响应时间，且对每个进程来说都具有较好的公平性。

”先来先服务调度算法”是“非抢占式”的；

“优先数调度算法”可以是“非抢占式”的，也可以是“抢占式”的；

“时间片轮转调度算法”是一种“抢占式”的。

死锁

若系统中存在一组进程（两个或多个进程），它们中的每一个进程都占用了某种资源而又都在等待其中另一进程所占用的资源，这种等待永远不能结束，则说系统出现了“死锁”，或说这组进程处于“死锁”状态。

特点

1）陷入死锁的进程是系统并发进程中的一部分，且至少要有两个进程，单个进程不会形成死锁。

2）陷入死锁的进程彼此都在等待对方释放资源，形成一个循环等待链。

3）死锁形成后，在没有外力干预下，陷入死锁的进程不能自己解除死锁，死锁进程无法正常结束。

4）如不及时解除死锁，死锁进程占有的资源不能被其他进程所使用，导致系统中更多进程阻塞，造成资源利用率下降。
必要条件

（1）互斥条件：进程应互斥使用资源，任一时刻一个资源仅为一个进程独占，若另一个进程请求一个已被占用的资源时，它被置成等待状态，直到占用者释放资源。

（2）占有且等待条件：一个进程请求资源得不到满足而等待时，不释放已占有的资源。

（3）不剥夺条件：任一进程不能从另一进程那里抢夺资源，即已被占用的资源，只能由占用进程自己来释放。

（4）循环等待条件：存在一个循环等待链，其中，每一个进程分别等待另一个进程所持有的资源，造成永远等待。

这四个条件仅是必要条件而不是充分条件，即只要发生死锁则这四个条件一定会同时成立，但反之则不然。
避免死锁的方法

1）预防死锁。预防死锁是在系统运行之前就采取相应措施，消除发生死锁的任何可能性。消除死锁发生的必要条件可预防死锁。破坏产生死锁的四个必要条件中一个或几个来预防产生死锁。预防死锁是处理死锁的静态策略，它虽比较保守、资源利用率低，但因简单明了较易实现，现仍被广泛使用。

2）避免死锁。避免死锁是为了克服预防死锁的不足而提出的动态策略。避免死锁与预防死锁的策略不同，它并不是事先采取各种限制措施，去破坏产生死锁的四个必要条件，而是在资源动态分配过程中，用某种方法防止系统进入不安全状态，从而可以避免发生死锁。避免死锁方法虽好，但也存在两个缺点：一是对每个进程申请资源分析计算较为复杂且系统开销较大；二是在进程执行前，很难精确掌握每个进程所需的最大资源数。银行家算法

3）检测死锁。这种方法无须事先采取任何限制性措施，允许进程在运行过程中发生死锁。但可通过检测机构及时地检测出死锁的发生，然后采取适当的措施，把进程从死锁中解脱出来。死锁检测不延长进程初始化时间，允许对死锁进行现场处理，其缺点是通过剥夺解除死锁，给系统或用户造成一定的损失。

4）解除死锁。当检测到系统中已发生死锁时，就采取相应措施，将进程从死锁状态中解脱出来。常用的方法是撤销一些进程，回收它们的资源，将它们分配给已处于阻塞状态的进程，使其能继续运行。在实际执行中，由于并发进程推进顺序的多样性，系统很难做到有效地解除死锁。

2.2.4 线程

线程的概念

进程是程序的一次执行过程和资源分配的基本单位。

线程是一个进程内的基本调度单位，是CPU分配的基本单位。
引入线程的目的

为了更好地实现并发处理和共享资源，提高CPU的利用率，提高系统的执行效率，减少处理机的空转时间和调度切换的时间，减少内存开销，便于系统管理。

引入线程后，进程成为（除CPU以外）资源分配的单位。在UNIX系统中，进程是CPU的分配单位，在Windows中，线程是CPU的分配单位。

在任务管理器的“进程”选项中，选择“查看”→“选择列”，查看一个进程所包含的线程数。

2.3 存储管理

计算机存储器的管理，存储管理的对象是内存以及作为内存的扩展和延伸的外存储器。存储管理的目标是为程序设计人员提供方便、安全和充分大的存储空间，提供一个内外存结合的满足需要的存储空间。

内存的分配与回收：为运行的进程分配内存空间,并在不需要时回收它们占据的空间。
地址变换：当程序中采用的地址和将其装入内存后的地址不一致时,要完成程序中采用的地址到内存地址的转换,即逻辑地址转换为物理地址，程序才能正确运行。通常有静态重定位、动态重定位。
存储保护：代码和数据共享，以节省内存空间和保持数据一致性。内存中程序相互干扰，要设置地址空间访问权限（读、写、执行）。
存储扩充：虚拟存储技术、覆盖技术、交换技术

虚拟存储器是指一种实际上并不存在存储器，是由内存和外存连接成的存储器。基本思想是：把当前正在使用的部分放在内存，其他暂时不用的部分放在外存，运行时根据需要进行调度。即在不改变实际内存容量情况下，借助大容量外存解决内存不足问题。

虚拟内存的最大容量与CPU的地址总线的位数有关。

程序的装入和链接

在程序环境下，要使程序运行，必须先为之创建进程。而创建进程的第一件事，

便是将程序和数据装入内存。如何将一个用户源程序变为一个可在内存中执行的程序，通常都要经过以下几个步骤：

编译：由编译程序(Compiler)将用户源代码编译成若干个目标模块(Object Module)。

链接：由链接程序(Linker)将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块(Load Module)。

装入：由装入程序(Loader)将装入模块装入内存。
存储管理基本技术
- 存储管理的目的和功能：
对主存空间进行分配和管理；提高主存的利用率；“扩充”主存容量；实现地址的变换。
- 分区法：把内存划分成若干分区，每个分区里容纳一个作业。
  - 固定分区：分区的个数、分区的大小固定不变；每个分区只能放一道作业。
    
    优点：管理方式简单。
    
    缺点：内存空间利用率低。
  - 动态分区法：分区大小和个数依作业情况而定；作业进入内存时才建分区。
    
    优点：按需分配内存。
    
    缺点：产生大量碎片。
  - 重定位分区分配：通过紧缩可解决碎片问题；作业在内存中可以移动。
    
    优点：解决了碎片的问题，提高了主存利用率。
    
    缺点：增加了开销，但须消耗大量的 CPU 时间。
- 对换技术：作业（或进程）在内存和磁盘之间交换，换出暂时不能运行的作业（或进程），换入具备运行条件的作业（或进程）。
虚拟存储器：是由操作系统提供的一个假想的特大存储器。
虚拟存储器的基本特征：
- 虚拟扩充：不是物理上，而是逻辑上扩充了内存容量。
- 部分装入：每个作业不是全部一次性地装入内存，而是只装入一部分。
- 离散分配：不必占用连续的空间，而是“见缝插针”。
- 多次对换：所需的全部程序和数据要分成多次调入内存。
虚拟存储器受到的限制：指令中表示地址的字长、外存的容量。
分页存储管理技术
- 分页的概念
  
  逻辑空间等分为页，物理空间等分为块，与页面大小相同。
  - 逻辑地址表示：（如，页面大小为 1K）。
  - 内存分配原则：以块为单位，逻辑上相邻的页可以分配在不相邻的内存块中。
  - 页表：实现从页号到物理块号的地址映射。
  - 地址映射：由硬件完成。
- 请求分页的基本思想
  
  （1）基本思想
  
  地址空间分页，内存分块，页与块大小相同；作业部分装入内存。作业所占的各块不连续。若缺页，进行缺页中断处理，换入内存。利用快表可加速地址转换。
  
  （2）缺页中断的概念
  
  缺页中断：要访问的页不在主存，需要操作系统将其调入主存后再进行访问。在这个时候，被内存映射的文件实际上成了一个分页交换文件。
  
  （3）缺页中断发生时的事件顺序如下
  - 硬件陷入内核，在内核堆栈中保存程序计数器。大多数机器将当前指令的各种状态信息保存在特殊的 CPU 寄存器中。
  - 启动一个汇编代码例程保存通用寄存器和其他易失的信息，以免被操作系统破坏。这个例程将操作系统作为一个函数来调用。
  - 当操作系统发现一个缺页中断时，尝试发现需要哪个虚拟页面。通常一个硬件寄存器包含了这一信息，如果没有的话，操作系统必须检索程序计数器，取出这条指令，用软件分析这条指令，看看它在缺页中断时正在做什么。
  - 一旦知道了发生缺页中断的虚拟地址，操作系统检查这个地址是否有效，并检查存取与保护是否一致。如果不一致，向进程发出一个信号或杀掉该进程。如果地址有效且没有保护错误发生，系统则检查是否有空闲页框。如果没有空闲页框，执行页面置换算法寻找一个页面来淘汰。
  - 如果选择的页框“脏”了，安排该页写回磁盘，并发生一次上下文切换，挂起产生缺页中断的进程，让其他进程运行直至磁盘传输结束。无论如何，该页框被标记为忙，以免因为其他原因而被其他进程占用。
  - 一旦页框“干净”后（无论是立刻还是在写回磁盘后），操作系统查找所需页面在磁盘上的地址，通过磁盘操作将其装入。该页面被装入后，产生缺页中断的进程仍然被挂起，并且如果有其他可运行的用户进程，则选择另一个用户进程运行。
  - 当磁盘中断发生时，表明该页已经被装入，页表已经更新可以反映它的位置，页框也被标记为正常状态。
  - 恢复发生缺页中断指令以前的状态，程序计数器重新指向这条指令。
  - 调度引发缺页中断的进程，操作系统返回调用它的汇编语言例程。
  - 该例程恢复寄存器和其他状态信息。
分段处理技术

逻辑空间分段：段是信息的逻辑单位，每段对应一个相应的程序模块，有完整的逻辑意义。

程序的地址结构：

逻辑地址表示：二维的地址空间。

内存分配：内存以段为单位进行分配，每个段单独占用一块连续的内存分区。

段表：实现每个逻辑段到物理内存中分区位置的映射。

地址转换：将逻辑地址转换成内存的物理地址，完成地址重定位。需要指出的是，地址转换是操作系统的地址变换机构自行完成的，无需用户干预，这样我们使用操作系统时，才方便而可靠。
- 先进先出法（FIFO）：将最先进入内存的页换出/淘汰出内存。
- 最佳置换法（OPT）：其所选择的被淘汰的页面将是以后永不使用的，或是在最长（未来）时间内不再被访问的页面。
- 最近最少使用置换法（LRU）：将最近一段时间里最久没有使用过的页面换出内存。
- 最近未使用置换法（NUR）：是 LRU 近似方法，比较容易实现，开销也比较小。
  
  实现方法：在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为 0。
  
  当某一页被访问时，由硬件将该位置 1。需要淘汰一页时，把该位为 0 的页淘汰出去，因为最近一段时间里它未被访问过。

2.4 设备管理

设备管理是操作系统中最繁杂而且与硬件紧密相关的部分，不但要管理实际I/O操作的设备（如磁盘机、扫描仪、打印机、键盘和鼠标），还要管理诸如设备控制器、DMA控制器、中断控制器和I/O处理机（通道）等支持设备。设备管理包括各种设备分配、缓冲区管理和实际物理I/O设备操作，通过管理达到提高设备利用率和方便用户的目的。

分类
- 存储设备（外存、辅助存储器）：用于存储信息的设备
- 输入/输出设备：用于输入/输出信息的设备
- 根据设备的使用性质，可将设备分成：独占设备、共享设备和虚拟设备。
- 独占设备：不能共享的设备，即：在一段时间内，该设备只允许一个进程独占。如打印机。
- 共享设备：可由若干个进程同时共享的设备。如磁盘机。
- 虚拟设备：是利用某种技术把独占设备改造成可由多个进程共享的设备。
- 针对三种设备采用三种分配技术：独占分配、共享分配和虚拟分配。
- 独占分配技术：是把独占设备固定地分配给一个进程，直至该进程完成 I/O 操作并释放它为止。
- 共享分配技术：通常适用于高速、大容量的直接存取存储设备。由多个进程共享一台设备，每个进程只用其中的一部分。
- 虚拟分配技术：利用共享设备去模拟独占设备，从而使独占设备成为可共享的、快速I/O 的设备：实现虚拟分配的最有名的技术是 SPOOLing 技术，也称作假脱机操作。
按照数据的组织方式
- 块设备和字符设备
- 块设备：以数据块为单位组织和传送数据的。比如磁盘，磁带
- 字符设备：以单个字符为单位存取的。比如打印机
按照数据传输速率
- 低速设备：每秒几个字节到数百个字节比如鼠标键盘等
- 中速设备：每秒千个字节到数万个字节比如行式打印机
- 高速设备 ：每秒十万个字节到数兆个字节比如磁盘机，光盘机

2.5 文件管理

操作系统中的文件系统专门负责管理外存储器上的信息，使用户可以“按名”高效、快速和方便地存储信息。

2.6 作业管理

作业是系统为完成一个用户的计算任务（或一次事务处理）所做的工作总和。例如，对用户编写的源程序，需要经过编译、连接、装入以及执行等步骤得到结果，这其中的每一个步骤称为一个作业步，操作系统中用来控制作业进入、执行和撤销的一组程序称为作业管理程序。操作系统可以进一步每个作业创建作业步进程，完成用户的工作。

主要任务
- 作业控制
- 作业调度
作业控制功能
- 控制作业输入
- 运行
- 计算结果的输出

为了对作业进行有效控制，操作系统为每个进入系统的作业建立一个作业控制块（JCB），里面记录着与作业调度有关的信息

作业从进入计算机系统到运行结束退出，整个过程分为4个阶段：
- 提交；
- 后备；
- 运行；
- 完成；

这4个阶段构成作业的整个生命期。作业在这四个阶段中分别处于提交状态、后备状态、执行状态和完成状态。JCB是作业存在的标志，作业退出系统时JCB随之撤销。

作业调度
1. 先来先服务算法
  
  按作业进入系统作业后备队列先后次序挑选作业。这种算法容易实现，但效率低。
2. 最短作业优先算法
  
  系统选取估计计算时间最短的作业投入运行。这种算法使平均作业周转时间短，且易于实现，但效率不高。

常见的调度算法还有优先数法、分类调度算法等。

第三章程序设计语言基础知识

3.1 程序设计语言概述

程序设计语言是为了书写计算机程序而设计的符号语言，用于对计算过程进行描述、组织和推导。程序设计语言的广泛使用始于 1957 年出现的 FORTRAN，其发展和演化已经超越了运行程序的机器。

3.1.1 基本概念

低级语言和高级语言

计算机硬件只能识别由 0、1 字符序列组成的机器指令，因此机器指令是基本的计算机语言。用机器语言编制程序效率低、可读性差，也难以理解、修改和维护。因此，人们设计了汇编语言，用容易记忆的符号代替 0、1 序列，来表示机器指令中的操作码和操作数。例如，用 ADD 表示加法、SUB 表示减法等。虽然使用汇编语言编写程序的效率和程序的可读性有所提高，但汇编语言是面向机器的语言，其书写格式在很大程度上取决于特定计算机的机器指令。机器语言和汇编语言被称为低级语言。人们开发了功能更强、抽象级别更高的语言以支持程序设计，因此就产生了面向各类应用的程序设计语言，即高级语言，常见的有 Java、C、C++、C#、Python、PHP 等。这类语言与人们使用的自然语言比较接近，大大提高了程序设计的效率。
编译程序和解释程序

目前，尽管人们可以借助高级语言与计算机进行交互，但是计算机仍然只能理解和执行由 0、1 序列构成的机器语言，因此高级程序设计语言需要翻译，担负这一任务的程序称为“语言处理程序”。由于应用的不同，程序语言的翻译也是多种多样的。它们大致可分为汇编程序、解释程序和编译程序。用某种高级语言或汇编语言编写的程序称为源程序，源程序不能直接在计算机上执行。如果源程序是用汇编语言编写的，则需要一个称为汇编程序的翻译程序将其翻译成目标程序后才能执行。如果源程序是用某种高级语言编写的，则需要对应的解释程序或编译程序对其进行翻译，然后在机器上运行。
程序设计语言的定义

一般地，程序设计语言的定义都涉及语法、语义和语用 3 个方面。

（1）语法。语法是指由程序设计语言基本符号组成程序中的各个语法成分（包括程序）的一组规则，其中由基本字符构成的符号（单词）书写规则称为词法规则，由符号（单词）构成语法成分的规则称为语法规则。程序设计语言的语法可通过形式语言进行描述。

（2）语义。语义是程序设计语言中按语法规则构成的各个语法成分的含义，可分为静态语义和动态语义。静态语义是指编译时可以确定的语法成分的含义，而运行时刻才能确定的含义是动态语义。一个程序的执行效果说明了该程序的语义，它取决于构成程序的各个组成部分的语义。

（3）语用。语用表示了构成语言的各个记号和使用者的关系，涉及符号的来源、使用和影响。

3.1.2 程序设计语言的分类和特点

程序设计语言发展概述

程序设计语言的发展是一个不断演化的过程，其根本的推动力就是对抽象机制的更高要求，以及对程序设计活动更好地支持。具体地说，就是把机器能够理解的语言提升到也能够很好地模仿人类思考问题的形式。

FORTRAN（ “FORmula TRANslator”的缩写）是第一个高级程序设计语言，在数值计算领域积累了大量高效而可靠的程序代码。
ALGOL（ALGOrithmic Language）诞生于晶体管计算机流行的年代，ALGOL60 是程序设计语言发展史上的一个里程碑，主导了 20 世纪 60 年代程序语言的发展，并为后来软件自动化及软件可靠性的发展奠定了基础。
PASCAL 语言是一种结构化程序设计语言，由瑞士苏黎世联邦工业大学的沃斯（N.Wirth）教授设计，于 1971 年正式发表。
C 语言是 20 世纪 70 年代发展起来的一种通用程序设计语言，其主要特色是兼顾了高级语言和汇编语言的特点，简洁、丰富、可移植。UNIX 操作系统及其上的许多软件都是用 C 编写的。C 提供了高效的执行语句并且允许程序员直接访问操作系统和底层硬件，适用于系统级编程和实时处理应用。
**C++**是在 C 语言的基础上于 20 世纪 80 年代发展起来的，与 C 兼容。在 C++中，主要的是增加了类机制，使其成为一种面向对象的程序设计语言。
Java 产生于 20 世纪 90 年代，其初始用途是开发网络浏览器的小应用程序，但是作为一种通用的程序设计语言，Java 得到非常广泛的应用。Java 保留了 C++的基本语法、类和继承等概念，删掉了 C++中一些不好的特征，因此与 C++相比，Java 更简单，其语法和语义更合理。
C#（C Sharp）是由 Microsoft 公司开发的一种面向对象的、运行于.NET Framework 的高级程序设计语言，相对于 C++，这个语言在许多方面进行了限制和增强。
PHP（Hypertext Preprocessor）是一种在服务器端执行的、嵌入 HTML 文档的脚本语言，其语言风格类似于 C 语言，由网站编程人员广泛运用。
Python是一种面向对象的解释型程序设计语言，可以用于编写独立程序、快速脚本和复杂应用的原型。Python 也是一种脚本语言，它支持对操作系统的底层访问，也可以将 Python 源程序翻译成字节码在 Python 虚拟机上运行。
JavaScript 是一种脚本语言，被广泛用于 Web 应用开发，常用来为网页添加动态功能，为用户提供更流畅美观的浏览效果。通常，将 JavaScript 脚本嵌入在 HTML 中来实现自身的功能。

数据成分

（1）常量和变量。

（2）全局量和局部量。

（3）数据类型
运算成分

程序设计语言的运算成分指明允许使用的运算符号及运算规则。大多数高级程序设计语言的基本运算可以分成算术运算、关系运算和逻辑运算等类型，有些语言如 C（C++）还提供位运算。运算符号的使用与数据类型密切相关。为了明确运算结果，运算符号要规定优先级和结合性，必要时还要使用圆括号。
控制成分
1. 顺序结构
2. 选择结构
3. 循环结构

C/C++提供的控制语句如下。

（1）复合语句。复合语句用于描述顺序控制结构。

（2）if 语句和 switch 语句

（3）循环语句

函数

函数是程序模块的主要成分，它是一段具有独立功能的程序。C 程序由一个或多个函数组成，每个函数都有一个名字，其中有且仅有一个名字为 main 的函数，作为程序运行时的起点。函数的使用涉及 3 个概念：函数定义、函数声明和函数调用

3.2 语言处理程序基础

语言处理程序是一类系统软件的总称，其主要作用是将高级语言或汇编语言编写的程序翻译成某种机器语言程序，使程序可在计算机上运行。语言处理程序主要有汇编程序、编译程序和解释程序 3 种基本类型。

3.2.1 汇编程序基础

汇编语言

汇编语言是为特定计算机设计的面向机器的符号化程序设计语言。用汇编语言编写的程序称为汇编语言源程序。因为计算机不能直接识别和运行符号语言程序，所以要用专门的汇编程序进行翻译。用汇编语言编写程序要遵循所用语言的规范和约定。汇编语言源程序由若干条语句组成，一个程序中可以有三类语句：指令语句、伪指令语句和宏指令语句。

（1）指令语句。指令语句又称为机器指令语句，将其汇编后能产生相应的机器代码，这些代码能被 CPU 直接识别并执行相应的操作。基本的指令如 ADD、SUB 和 AND 等，书写指令语句时必须遵循相应的格式要求。

（2）伪指令语句。伪指令语句指示汇编程序在汇编源程序时完成某些工作。

（3）宏指令语句。在汇编语言中，还允许用户将多次重复使用的程序段定义为宏。
汇编程序

汇编程序的功能是将汇编语言所编写的源程序翻译成机器指令程序。汇编程序的基本工作包括：将每一条可执行汇编语句转换成对应的机器指令；处理源程序中出现的伪指令和宏指令。由于汇编指令中形成操作数地址的部分可能在后面才能确定，所以汇编程序一般需要扫描两次源程序才能完成翻译过程。

3.2.2 编译程序基础

编译过程概述

编译程序的功能是把某高级语言书写的源程序翻译成与之等价的目标程序（汇编语言程序或机器语言程序）。编译程序的工作过程可以分为 6 个阶段。实际的编译器中可能会将其中的某些阶段结合在一起进行处理。下面简要介绍各阶段实现的主要功能。

（1）词法分析

词法分析阶段是编译过程的第一阶段，这个阶段的任务是对源程序从前到后（从左到右）逐个字符地扫描，从中识别出一个个“单词”符号。源程序可以被看成是一个多行的字符串。

（2）语法分析

语法分析的任务是在词法分析的基础上，根据语言的语法规则将单词符号序列分解成各类语法单位，如“表达式”“语句”“程序”等。语法规则就是各类语法单位的构成规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。如果源程序中没有语法错误，语法分析后就能正确地构造出其语法树；否则就指出语法错误，并给出相应的诊断信息。

词法分析和语法分析本质上都是对源程序的结构进行分析。

（3）语义分析

语义分析阶段主要分析程序中各种语法结构的语义信息，包括检查源程序是否包含静态语义错误，并收集类型信息供后面的代码生成阶段使用。只有语法和语义都正确的源程序才能被翻译成正确的目标代码。语义分析的一个主要工作是进行类型分析和检查。程序设计语言中的一个数据类型一般包含两个方面的内容：类型的载体及其上的运算。例如，整除取余运算符只能对整型数据进行运算，若其运算对象中有浮点数就认为是类型不匹配的错误。在确认源程序的语法和语义之后，就可对其进行翻译，同时改变源程序的内部表示。对于声明语句，需要记录所遇到的符号的信息，因此应进行符号表的填查工作。

（4）中间代码生成

中间代码生成阶段的工作是根据语义分析的输出生成中间代码。“中间代码”是一种简单且含义明确的记号系统，可以有若干种形式，它们的共同特征是与具体的机器无关。

（5）代码优化

由于编译器将源程序翻译成中间代码的工作是机械的、按固定模式进行的，因此，生成的中间代码往往在计算时间上和存储空间上有很大的浪费。当需要生成高效的目标代码时，就必须进行优化。优化过程可以在中间代码生成阶段进行，也可以在目标代码生成阶段进行。由于中间代码是不依赖于具体机器的，此时所作的优化一般建立在对程序的控制流和数据流分析的基础之上，与具体的机器无关

（6）目标代码生成

目标代码生成是编译器工作的后一个阶段。这一阶段的任务是把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令代码，这个阶段的工作与具体的机器密切相关。

（7）符号表管理

符号表的作用是记录源程序中各个符号的必要信息，以辅助语义的正确性检查和代码生成，在编译过程中需要对符号表进行快速有效地查找、插入、修改和删除等操作。

（8）出错处理

用户编写的源程序不可避免地会有一些错误，这些错误大致可分为静态错误和动态错误。动态错误也称动态语义错误，它们发生在程序运行时，例如变量取零时作除数、引用数组元素下标越界等错误。静态错误是指编译时所发现的程序错误，可分为语法错误和静态语义错误，如单词拼写错误、标点符号错误、表达式中缺少操作数、括号不匹配等有关语言结构上的错误称为语法错误；而语义分析时发现的运算符与运算对象类型不合法等错误属于静态语义错误。
词法分析

词法分析过程的本质是对构成源程序的字符串进行分析，是一种对象为字符串的运算。语言中具有独立含义的小语法单位是符号（单词），如标识符、无符号常数与界限符等。词法分析的任务是把构成源程序的字符串转换成单词符号序列。

1）正规表达式

运算符“ | ” “ · ” “ * ”分别称为“或”“连接”和“闭包”。在正规式的书写中，连接运算符“· ”可省略。运算符的优先级从高到低顺序排列为“ * ” “ · ” “｜”。

2）有限自动机有限自动机是一种识别装置的抽象概念，它能准确地识别正规集。有限自动机分为两类：确定的有限自动机和不确定的有限自动机。

确定的有限自动机（Deterministic Finite Automata，DFA）。

不确定的有限自动机（Nondeterministic Finite Automata，NFA）
语法分析

程序设计语言的语法常采用上下文无关文法描述。文法不仅规定了单词如何组成句子，而且刻画了句子的组成结构。形式文法是一个规则（或称产生式）系统，它规定了单词在句子中的位置和顺序，也描述了句子的层次结构。

3.2.3 解释程序基础

解释程序是另一种语言处理程序，在词法、语法和语义分析方面与编译程序的工作原理基本相同，但是在运行用户程序时，它直接执行源程序或源程序的内部形式。因此，解释程序不产生源程序的目标程序，这是它和编译程序的主要区别。

对于高级语言的编译和解释翻译方式，可从以下几个方面进行比较。

效率

编译比解释方式可能取得更高的效率。

一般情况下，在解释方式下运行程序时，解释程序可能需要反复扫描源程序。例如，每一次引用变量都要进行类型检查，甚至需要重新进行存储分配，从而降低了程序的运行速度。在空间上，以解释方式运行程序需要更多的内存，因为系统不但需要为用户程序分配运行空间，而且要为解释程序及其支撑系统分配空间。

在编译方式下，编译程序要生成源程序的目标代码并进行优化，该过程比解释方式需要更多的时间。虽然与仔细写出的机器程序相比，一般由编译程序创建的目标程序运行的时间更长，需要占用的存储空间更多，但源程序只需要被编译程序翻译一次，就可以多次运行。因此总体来讲，编译方式比解释方式可能取得更高的效率。
灵活性

由于解释程序需要反复检查源程序，这也使得解释方式能够比编译方式更灵活。当解释器直接运行源程序时，“在运行中”修改程序就成为可能，如增加语句或者修改错误等。另外，当解释器直接在源程序上工作时，它可以对错误进行更精确地定位。
可移植性

源程序是由解释器控制来运行的，可以提前将解释器安装在不同的机器上，从而使得在新环境下无须修改源程序使之运行。而编译方式下则需要针对新机器重新生成源程序的目标代码才能运行。由于编译方式和解释方式各有特点，因此现有的一些编译系统既提供编译的方式，也提供解释的方式，甚至将两种方式结合在一起。例如，在 Java 虚拟机上发展的一种 compiling-just-in- time 技术，就是当一段代码第一次运行时进行编译，其后运行时就不再进行编译了。

第一章 计算机系统基础知识