操作系统引论

操作系统基础知识

定义：操作系统（Operating System，OS）是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。
设计目标：在计算机系统上配置操作系统，，其主要目标是方便性，有效性，可扩充性和开放性。
作用：可以从用户，资源管理以及资源抽象等多个不同角度来分析讨论。

OS作为用户与计算机硬件系统之间的接口
OS作为计算机系统资源的管理者
OS实现了对计算机资源的抽象

操作系统的发展过程

未配置操作系统的计算机系统——单道批处理系统——多道批处理系统——分时系统——实时系统——微机操作系统的发展

单道批处理和多道批处理系统的原理，优缺点

单道批处理系统

原理

计算机系统自动的一个作业紧接一个作业地进行处理，直至磁带上所有作业全部完成。虽然系统对作业的处理是成批的，但在内存中始终只保持一道作业。

优缺点

主要缺点是系统中的资源得不到充分利用。优点是一定程度上提高了系统资源利用率。

多道批处理系统

原理

用户所提交的作业先存放在外存上，并排成一个队列，然后作业调度程序按照一定的算法，从队列选择若干个作业调入内存，使他们共享CPU和系统中的各种资源。

优缺点

资源利用率高
系统吞吐量大
平均周转时间长
无交互能力

分时，实时系统的特征

分时系统

多路性
独立性
及时性
交互性

实时系统

多路性
独立性
及时性
交互性
可靠性

进程的描述与控制

进程的基本知识

基本概念

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。（这是传统的操作系统进程概念，在引入线程的操作系统中，进程只是拥有资源的基本单位）

特征

动态性：进程的实质是进程实体的执行过程，它由创建而产生的，因调度而执行，因撤销而消亡
并发性：多个进程实体同存于内存中，且能在一段时间内运行
独立性：进程实体是一个能独立运行，独立获得资源和接收调度的基本单位
异步性：各个进程按各自独立的，不可预知的速度向前推进

状态转换

进程有三个基本状态，就绪状态，执行状态，阻塞状态。
为了满足进程控制块（PCB）对数据及操作的完整性要求以及增强管理的灵活性，通常在系统中又为进程引入了两种常见状态：创建状态和中止状态。

线程的基本知识

线程的概念

线程是操作系统调度和分派的基本单位。

线程状态与线程控制块（TCB）

线程状态

执行状态
就绪状态
阻塞状态

线程控制块

所有用于控制和管理线程的信息纪录在线程控制块中。数据结构包含：

线程标识符
一组寄存器
线程执行状态
优先级
线程专有存储区
信号屏蔽
堆栈指针

进程和线程的区别

从以下六个方面进行讨论

调度性：在传统OS中，拥有资源的基本单位，独立调度和分派的基本单位都是进程。在引入线程的OS中，把线程作为调度和分派的基本单位，进程只是拥有资源的基本单位。
并发性：在引入进程的OS中，不仅线程间可以并发执行，而且在一个进程内的多线程间，也可以并发执行。
拥有资源：拥有资源的基本单位一直是进程，线程除了一点在运行中必不可少的资源，本身不拥有系统资源，但它可以共享其隶属进程的资源。
独立性：每个进程都能独立申请资源和独立运行，但是同一进程的多个线程则共享进程的内存地址空间和其他资源，他们之间独立性要比进程之间独立性低。
系统开销：在创建或者撤销进程时，系统都要为之分配和回收进程控制块（PCB）以及其他资源，进程切换时所要保存和设置的现场信息也要明显多于线程。由于隶属于一个进程的多个线程共享同一地址空间，线程间的同步与通讯也比进程简单。
支持多处理机系统：传统的进程只能运行在一个处理机上，多线程的进程，则可以将进程中的多个线程分配到多个处理机上，从而获得更好的并发执行效果。

前驱图

前驱图是指一个有向无循环图（DAG），用于描述进程之间执行的先后顺序。

PCB中的信息，组织形式

PCB概念

PCB作为进程实体的一部分，记录了操作系统所需的，用于描述进程的当前情况以及管理进程运行的全部信息，是操作系统中最重要的记录型数据结构。

PCB中的信息

进程标识符
- 外部标识符：方便用户（进程）对进程的访问
- 内部标识符：方便系统对进程的访问
处理机状态：处理机的上下文，主要是由处理机的各种寄存器中的内容组成的。
进程调度信息：进程状态，进程优先级，进程调度所需其他信息，事件
进程控制信息：数据与程序的地址，进程同步和通信机制，资源清单，链接指针

PCB的组织形式

线性方式：把系统所有PCB都组织在一张线性表中
链接方式：把所有相同状态进程的PCB分别通过PCB中的链接字链接成一个队列
索引方式：根据所有进程状态的不同，建立几张索引表

临界资源，临界区

临界资源是一次仅允许一个进程使用的共享资源。
每个进程中访问临界资源的那段代码称为临界区。

信号量机制

信号量是一种卓有成效的进程同步工具。可利用信号量实现进程互斥。

处理机调度与死锁

处理机的三级调度

一个作业从提交开始，往往要经历下述三级调度

高级调度

又叫作业调度或者长程调度，用于决定把外存后备队列中的哪些作业调入内存，为他们创建进程。

低级调度

又叫进程调度或短程调度，用来决定就绪队列中哪个进程先获得处理机，并将处理机分配给选中的进程，具体有两种方式

非抢占方式

一旦进程获得CPU，它将一直执行，直至该进程完成或者发生某些事件而阻塞时才会把CPU让出去。

抢占方式

系统可以根据某种原则让一正在执行的进程暂停，并将已分配给他的处理机重新分配给另一个进程

优先权原则

就绪的高优先权进程有权抢占低优先权进程的CPU

短作业优先原则

就绪的短进程有权抢占长进程的CPU

时间片原则

一个时间片用完后，系统重新进行进程调度

中级调度

又称内存调度或中程调度，它按一定算法将外存中已具备运行条件的进程换入内存，将内存中处于阻塞状态的某些进程换至外存

调度队列模型

周转时间，平均周转时间，带权周转时间，平均带权周转时间算法

周转时间 = 作业完成时间 − 作业提交时间
平均周转时间 = 所有作业周转时间之和/总作业数量
带权周转时间 = 作业周转时间/提供服务的时间之比
平均带权周转时间 = 所有作业带权周转时间之和/总作业数量

响应时间，截止时间和系统吞吐量

响应时间是提交请求和返回该请求的响应之间使用的时间
截止时间是某任务必须开始执行或者必须完成的最迟时间
吞吐量是对单位时间内完成的工作量的量度

调度算法的基本原理

总体上说，我们需要何时调度（调度的时机）、是否能够在内核执行的任意位置进行调度（调度的方式）、如何完成进程切换（上下文切换）、如何选择“合适”的进程执行（调度策略/调度算法）、如何评价选择的合理性（进程调度的指标）。

死锁基础知识

死锁定义

如果一组进程中的每个进程都在等待仅由该进程中的其他进程才能引发的事件，那么该组进程就是死锁的。

死锁的产生

需要同时具备以下四个条件，互斥条件，请求和保持条件，不可抢占条件，循环等待条件。

死锁的预防

破坏请求和保持条件：当一个进程请求资源时，它不能持有不可抢占资源。
破坏不可抢占条件：当一个已经保持了某些不可抢占资源的进程，提出新的资源请求而不能得到满足时，他必须释放已经保持的所有资源。
破坏循环等待条件：赋予每个进程序号，规定每个进程必须按序号递增的顺序请求资源。

死锁的避免

保持系统安全状态

银行家算法

最有代表性的避免死锁算法

银行家算法中的数据结构

可利用资源向量Available：表示某种资源还剩多少可用
最大需求矩阵Max：表示最多需要多少资源
分配矩阵Allocation：表示已经分配的资源
需求矩阵Need：表示还需要多少资源才能完成任务

并有以下关系
Need[i,j] = Max[i,j]-Allocation[i,j]

银行家算法

设Request是进程P的请求向量，表示请求Request个资源
有以下步骤

存储器管理

存储器的基础知识

存储器结构

主存储器

简称内存或主存，用于保存进程运行时的程序和数据，也叫执行存储器，通常处理机都是从主存储器中取得指令和数据的，并将指令放入指令寄存器中，数据放入数据寄存器中。

寄存器

寄存器具有与处理机相同的速度，对寄存器的访问速度最快，完全能与CPU协作。
寄存器主要用于存放处理机运行时数据，加速存储器访问速度。

高速缓存

它是介于寄存器和存储器之间的存储器，主要用于备份主存中比较常见的数据，减少处理机对主存储器的访问次数。

磁盘缓存

目前磁盘I/O远低于对主存的访问速度，为了缓和两者之间在速度上不匹配，设置了磁盘缓存。主要用于暂时存放频繁使用的一部分磁盘数据和信息。

程序运行的处理阶段

主要有编译，链接，装入，下面主要讲链接和装入

程序的链接

源程序经过编译后，可得到一组目标模块。链接程序的功能是将这组目标模块以及它们所需要的库函数装配成一个完整的装入模块。
链接又可分为静态链接，装入时动态链接，运行时动态链接。

程序的装入

分为绝对装入方式，可重定位装入方式，动态运行时的装入方式。

内存的分配方式

单一连续分配
固定分区分配
动态分区分配
基于顺序搜索的动态分区分配：首次适应算法，循环首次适应算法，最佳适应算法，最坏适应算法
基于索引搜索的动态分区分配：快速适应算法，伙伴系统，哈希算法
动态可重定位分区分
离散分配：分页存储管理方式，分段存储管理方式，段页式存储管理方式

分页存储管理方式基础知识

分页存储原理

将用户程序的地址空间分为若干个固定大小的区域，称为“页”或“页面”，也将内存空间分为若干物理块或页框。

分段存储原理

把用户程序地址空间分为若干个大小不同的段，每段可定义一组相对完整的信息。

逻辑地址与物理地址映射

系统为每个进程建立了一张页面映像表，称为页表，在进程地址空间内的所有页（0~n），依次在页表中有一页表项，记录了相应页在内存中对应物理块号。通过查找该表，即可找到每页在内存中的物理块号。

快表的定义

为了提高地址变换速度，可在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲寄存器，称为快表。

内存访问时间的计算

从进程发出指定逻辑地址的访问请求，进过地址变换，到在内存中找到对应的实际物理地址单元并取出数据，所花费的总时间，称为内存的有效访问时间（EAT）。
在传统的分页存储管理方式中：

$EAT\;=\;2t$

在引入快表的分页存储管理方式中：( $\lambda$ 为查找快表时间，a表示命中率，t表示访问一次内存所需要的时间)

$EAT\;=\;a\;\times\;\lambda\;+\;(t\;+\;\lambda)(1\;-\;a)\;+\;t\;=\;2t\;+\;\lambda\;-\;t\;\times\;a$

虚拟存储器

虚拟存储的实现方式

虚拟内存的实现都是建立在离散（动态）分配存储管理方式的基础上。主要有两种实现方式：

分页请求系统

在分页系统基础上增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。它允许用户程序只装入少数界面的程序（及数据）即可启动运行，以后再通过调页功能及页面置换功能陆续将即将运行的页面调入内存，同时把不用的页面再换出到外存上。
硬件支持：请求分页的页表机制，缺页中断结构，地址变换机构
实现请求分页的软件：包括用于实现请求调页的软件和实现页面置换的软件，在硬件支持下，将程序正在运行时所需的页面（尚未在内存中）调入内存，再将内存中暂时不用的页面从内存置换到磁盘上

请求分段系统

在分段系统基础上增加了请求调段功能和分段置换功能所形成的段式虚拟存储系统，具体实现原理同分页请求系统，不过载体是“段”不是“页”

页面置换算法

最佳置换算法（OPT）

其所选择被淘汰的页面将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面，但是因为未来不可预知，所以该算法不能实现。

先进先出置换算法（FIFO）

总是先淘汰最先进入内存的页面。

最近最久未使用算法（LRU）

选择最近最久未使用内存页面进行淘汰。需要较多硬件支持。

最少使用置换算法（LFU）

在内存为每个页面设置一个移位寄存器记录该页面被访问频率，选择最近时期使用最少的页面作为淘汰页。

Clock置换算法

是一种LRU算法
每页设置一个访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列；
当某个页面被访问时，其访问位置1。淘汰时，检查其访问位，如果是0，就换出；若为1，则重新将它置0；
再按FIFO算法检查下一个页面，到队列中的最后一个页面时，若其访问位仍为1，则再返回到队首再去检查第一个页面；

输入输出系统

设备控制器基本知识

I/O系统是OS的重要组成部分，用于管理诸如打印机和扫描仪等I/O设备，以及用于存储数据，如磁盘驱动器和磁带机等各种存储设备。I/O系统管理主要对象是I/O设备和相应设备控制器。主要任务是完成用户提出的I/O请求，提高I/O效率以及设备利用率。

I/O系统基本功能

隐藏物理设备的细节
与设备的无关性
提高处理机和I/O设备的利用率
对I/O设备进行控制
确保对设备的正确共享
错误处理

I/O通道的类型和瓶颈问题

I/O通道主要目的是为了建立独立的I/O操作，使数据的传送能独立于CPU，是一种特殊的处理机，具有执行I/O指令的能力，并通过执行通道程序来控制I/O操作。

通道类型

字节多路通道
数组选择通道
数组多路通道

瓶颈问题

通道价格昂贵，致使机器中所设置的通道数量势必较少，这往往又使它成了I/O瓶颈。

缓冲的基本知识

为什么需要缓冲

缓和CPU和I/O设备之间设备不匹配的矛盾：事实上，凡是数据到达速率和离去速率不同的地方都可以设置缓冲区，比如CPU速率远高于I/O设备，如果没有缓冲区，那么CPU向打印机输出数据时，打印机肯定难顶，CPU需要停下来等他。如果是打印机向CPU传送数据就会频繁中断CPU造成性能浪费。
减少对CPU的中断频率，放宽对CPU中断响应时间：在远程通信中，如果远地终端发来的数据仅用一位缓冲来接收，就意味着每收到一位数据就要中断一次CPU，而且CPU需要及时响应，不然缓冲区数据会被冲掉。类似的，在磁带控制器和磁盘控制器中都要设置缓冲寄存器，减少对CPU的中断频率。

缓冲的分类

单缓冲区，数据处理时间为： Max(C,T)+M（从磁盘把一块数据输入到缓冲区的时间为T，OS将该缓冲区中的数据传送到用户区的时间为M，CPU对这一块数据处理的时间为C）
双缓冲区，数据处理时间为：Max(C，T)
环形缓冲区，由三种类型缓冲区组成，装输入数据的空缓冲区R，已装满数据的缓冲区G，以及正在使用的现行工作缓冲区C。

独占设备，共享设备，虚拟设备的特点

独占设备：指在一段时间内只允许一个用户（进程）访问的设备，即临界资源；
共享设备：指在一段时间内允许多个进程同时访问的设备，如：磁盘；
虚拟设备：指通过虚拟技术将一台独占设备变换为若干台逻辑设备，供若干个用户同时使用；

Spooling技术的基础知识

概念

是Simultaneous Peripheral Operation On-Line (即外部设备联机并行操作)的缩写，是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常称为“假脱机技术”

组成

输入井和输出井。这是在磁盘上开辟的两个大存储空间；
输入缓冲区和输出缓冲区。在内存中要开辟两个缓冲区；
输入进程SPi和输出进程SPo。这里利用两个进程来模拟脱机I/O时的外围控制机；

特点

提高了I/O的速度。
将独占设备改造为共享设备。
实现了虚拟设备功能。

磁盘格式化，访问时间，磁盘调度算法计算平均寻道长度

低级格式化

将空白的磁盘划分出柱面和磁道，再将磁道划分为若干个扇区，每个扇区又划分出标识部分ID、间隔区GAP和数据区DATA等。
低级格式化只能针对一块硬盘而不能支持单独的某一个分区。每块硬盘在出厂时，已由硬盘生产商进行低级格式化，通常无需再进行低级格式化操作。
对于硬盘上出现逻辑坏道或者软性物理坏道，可以使用低级格式化来达到屏蔽坏道的作用；
低级格式化就是和操作系统无关的格式化。

高级格式化

就是清除硬盘上的数据、生成引导区信息、初始化FAT表、标注逻辑坏道等。
高级格式化主要是对硬盘的各个分区进行磁道的格式化，在逻辑上划分磁道。
长期以来，硬盘在储存数据时，都是以512B大小的扇区(Sector)为单位分割进行读写。随着硬盘容量的不断提升，这种分配标准已经越来越显的不合时宜。因此，将扇区容量扩大到4KB。
高级格式化可以优化硬盘，从而最大限度地利用全新操作系统的功能。
高级格式化就是和操作系统有关的格式化。

磁盘访问时间

寻道时间

磁臂(磁头)移动到指定磁道上所经历的时间。该时间是启动磁臂的时间s与磁头移动n条磁道所花费的时间之和，即Ts=m×n+s，其中，m是一常数，与磁盘驱动器的速度有关；

旋转延迟时间

指定扇区移动到磁头下面所经历的时间。

传输时间

数据从磁盘读出或向磁盘写入数据所经历的时间。 $T_t$ 的大小与每次所读/写的字节数b和旋转速度有关

$T_t\;=\;\frac b{rN}$

其中，r为磁盘每秒钟的转数；N为一条磁道上的字节数，当一次读/写的字节数相当于半条磁道上的字节数时， $T_t$ 与 $T_r$ 相同，因此，可将访问时间 $T_a$ 表示为

$T_a\;=\;T_s\;+\;\frac1{2r}\;+\;\frac b{rN}$

磁盘调度算法

先来先服务（FCFS）算法

按访问请求到达的先后次序服务
优点：简单，公平；
缺点：效率不高，相临两次请求可能会造成最内到最外的柱面寻道，使磁头反复移动，增加了服务时间，对机械也不利；

最短寻道时间优先（SSTF）算法

优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先
优点：改善了磁盘平均服务时间；
缺点：造成某些访问请求长期等待得不到服务

扫描（SCAN，电梯）算法

克服了最短寻道优先的缺点，既考虑了距离，同时又考虑了方向；
当设备无访问请求时，磁头不动；
当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；
否则改变移动方向，并为经过的访问请求服务，如此反复

循环扫描（CSCAN）算法

总是从0号柱面开始向里扫描
按照各自所要访问的柱面位置的次序去选择访问者
移动臂到达最后个一个柱面后，立即带动读写磁头快速返回到0号柱面
返回时不为任何的等待访问者服务
返回后可再次进行扫描

N-Step-SCAN

将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列。
处理一个队列时又是按SCAN算法，对一个队列处理完后，再处理其他队列。
当正在处理某子队列时，如果又出现新的磁盘I/O请求，便将新请求进程放入其他队列，这样就可避免出现粘着现象。
当N值取得很大时，会使N步扫描法的性能接近于SCAN算法的性能；当N=1时，N步SCAN算法便蜕化为FCFS算法。

FSCAN调度算法

FSCAN算法实质上是N步SCAN算法的简化，即FSCAN只将磁盘请求队列分成两个子队列。
一个是由当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理。
在扫描期间，将新出现的所有请求磁盘I/O的进程，放入另一个等待处理的请求队列。
所有的新请求都将被推迟到下一次扫描时处理。

文件管理

文件和文件系统的基本知识

文件是指由创建者所定义的、具有文件名的一组相关元素的集合。可分为有结构文件和无结构文件两种。
文件系统是指操作系统中各类文件、管理文件的软件，以及管理文件所涉及到的数据结构等信息的集合。

外存分配方式的基本原理、优缺点

连续分配

为每一个文件分配一组相邻接的盘块;
把逻辑文件中的记录顺序地存储到邻接的各物理盘块中;
这样形成的文件结构称为顺序文件结构,物理文件称为顺序文件;
优点：顺序访问容易; 顺序访问速度快;
缺点：要求有连续的存储空间; 必须事先知道文件的长度;

链接分配

文件的信息存放在若干不连续的物理块中；
各块之间通过指针连接，前一个物理块指向下一个物理块；
可分为隐式链接和显式链接；
优点：没有外部碎片，空闲空间列表的任何块可以用于满足请求。当创建文件时，并不需要说明文件的大小只，要有可用的空闲块，文件就可以继续增长。因此，无需合并磁盘空间。
缺点：存取速度慢，不适于随机存取;可靠性问题，如指针出错;更多的寻道次数和寻道时间;链接指针占用一定的空间;

索引分配

每个文件都有自己的索引块，这是一个磁盘块地址的数组。

单级索引表

一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构——索引表，并将这些块的块号存放在一个索引表中；
索引分配方式支持直接访问，当要读文件的第i个盘块时，可以方便地直接从索引块中找到第i个盘块的盘块号；
优点：即能顺序存取，又能随机存取；满足了文件动态增长、插入删除的要求；能充分利用外存空间；
缺点：较多的寻道次数和寻道时间;索引表本身带来了系统开销,如：内外存空间，存取时间;