操作系统原理概述
1、操作系统概述
（1）、操作系统定义：是计算机系统中的一个系统软件，管理和控制计算机系统中的硬件和软件资源，合理的组织计算机的工作流程，以便有效的利用这些资源为用户提供一个功能强、使用方便的工作环境，从而在计算机与用户之间起到接口的作用。
（2）、 操作系统的发展：
。50年代中期，第一个简单批处理操作系统
。60年代中期，多道程序批处理系统
。不久，分时系统、实时系统
。80年代，微机及网络操作系统
2、进程管理
（1）、进程的引入
程序并发执行：
。多道程序设计技术：多个程序并发执行
。程序并发执行时的特征：间断性、非封闭性、不可再现性
程序并发执行引发的问题：
。协调各程序执行的顺序
。多个程序执行共享系统资源，程序之间可能会相互影响，甚至影响输出结果
。选择哪些、多少个程序进入内存执行？
。内存中的执行顺序谁先执行，谁后执行？
。内存如何有效分配？
（2）、进程的概念
定义：可并发执行的程序，在一个数据集合上的运行过程。
申请/拥有资源的基本单位，多进程中调度的基本单位
进程与程序对应的关系：
-一个程序可以对应一个进程或多个进程
-一个进程可以对应一个程序或一段程序
（3）、进程的特征
动态性
并发性
独立性
异步性
（4）、引入进程带来的问题
增加了空间开销
额外的时间开销
更难控制：
。协调多个进程竞争和共享资源如何预防
。解决多个进程因为竞争资源而出现故障
处理机的竞争尤为突出
（5）、进程的结构
组成：程序、数据集合、进程控制块PCB
PCB是进程存在的唯一标志，创建进程时，创建PCB,进程结束时，系统将撤销PCB。
（6）、PCB
进程标识信息：进程的内部和外部标识符
处理机状态信息：通用寄存器值、指令计数器值、。。。
进程调度信息：进程状态、进程优先权、进程调度的其他信息
其他信息：
（7）、PCB的组织方式之一-----单一队列
所有进程的PCB通过链表组织成为一个单一队列，适用于进程数量不多的系统。如Windows操作系统。
（8）、PCB的组织方式之一-----表格结构
PCB按进程状态的不同，组织成不同的表格：就绪进程表、执行进程表、阻塞进程表。
系统分别记载个PCB表的起始地址。
（9）、进程的状态
进程执行轨迹：进程执行的指令序列，用于观察处理机的执行过程。
两状态进程模型：执行、未执行
。进程获得处理机，进入进程；当时间片结束或其他原某种因，进程释放处理机，暂停执行，处于未执行（可分为阻塞、就绪）状态。
分派
进入---->未执行 执行---->退出
暂停
（10）、进程的五状态
。新状态：进程已经创建，但未被OS接纳为可执行状态；
。就绪状态：准备执行；
。执行状态：占用处理机（单处里机环境下，某一时刻紧一个进程占用处理机）
。阻塞状态：等待某事件发生才能执行，如等待I/O完成等；
。终止状态：因停止或取消，被OS从执行状态释放。
（11）、多个进程竞争内存资源
。内存资源紧张
。无就绪状态，处理机空闲：I/O的速度比处理机的速度慢的多，可能出现全部进程阻塞等待I/O
（12）、解决方法：
采用交换技术：换出一部分进程到外存，以腾出内存空间
采用虚拟存储技术：每个进程只能装入一部分程序和数据（存储管理部分）
（13）、对换技术，交换技术
将内存中暂时不能运行的进程，或暂时不用的数据和程序，换出到外存，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的数据和程序，换入内存。
（14）、进程的挂起状态
。进程被交换到外存，状态变为挂起状态
。进程全部阻塞，处理机空闲
。系统负荷过重，内存空间紧张
。OS的需要，OS可能需要挂起后台进程或一些服务进程，或者某些可能导致系统故障的进程
。终端用户的请求
。父进程的需求
（15）、被挂起进程的特征
。不能立即执行
。可能是等待某事件发生，若是，则阻塞条件独立于挂起条件，即使阻塞事件发生，该进程也不能执行
。使之挂起的进程为：自身、其父进程、OS
。只有挂起它的进程才能使之由挂起状态转换为其他状态
（16）、挂起与阻塞
。进程是否等待事件，是阻塞与否
。进程是否被换出内存，是挂起与否
4种状态组合：
就绪：进程在内存，准备执行；
阻塞：进程在内存，等待事件；
就绪/挂起：进程在外存，只要调入内存即可执行；
阻塞/挂起：进程在外存，等待事件
注：处理机可调度执行的进程有两种：新创建的进程；或换入一个以前挂起的进程，通常系统为避免增加系统负载，系统会换入以一个以前挂起的进程执行
（17）、具有挂起状态的进程状态转换
（18）、进程的控制
两种执行模式：
。系统模式（又称系统态）、控制模式或内核模式：
-具有较高的特权
-运行系统特定的指令，包括读/写控制寄存器的指令、基本I/O指令以及与存储器管理有关的指令
-内核模式下的处理机及其指令、寄存器和内存都受到完全控制和保护
。用户模式（或用户态）
-具有较低的特权
-用户程序一般运行在用户模式
模式切换：
用户模式--->系统模式：用户程序执行到一条系统调用，进入系统内核执行
系统模式--->用户模式：执行完系统调用的功能，返回单用户程序
操作系统内核（Kernel）：是基于硬件的第一层软件扩充，提供操作系统最基本的功能，是操作系统工作的基础（如时钟管理、进程调度等），
一般的，操作系统内核的功能可以概括划分为资源管理功能（进程管理、存储管理、I/O设备管理）和支撑功能（中断处理、统计、监测、时钟管理等）
（19）、进程创建：步骤
。为进程分配一个唯一标识号ID：主进程表中增加一个新的表项
。为进程分配空间：用户地址空间、用户栈空间、PCB空间
。初始化PCB：进程标使、处理机状态信息、进程状态
。建立链接：若调度队列使链表，则将新进程插入到就绪或就绪/挂起链表
。建立或扩展其他数据结构
（20）、进程终止：步骤
（21）、进程阻塞与唤醒
（22）、进程挂起与**
（23）、进程切换：进程A切换到进程B的步骤：
首先，保护进程A的现场，然后恢复进程B的现场
（24）、进程切换一定会引发模式切换，反之则不然
（25）、进程调度：调度的关键是需要某种方法或算法
（26）、调度目标：
。公平性，防止进程长期不能获得调度而饥饿
。处理机利用率，尽量提高处理机的利用率；
。提高系统吞吐量；
。尽量减少进程的响应时间
（27）、调度原则：
。满足用户的要求：响应时间、周转时间、截止时间
。满足系统的要求：系统吞吐量、处理机利用率、各类资源的平衡使用、公平性及优先级
（28）、进程调度方式：非剥夺方式（批处理系统）、剥夺方式（分时和实时系统）
（29）、调度的类型：
。批处理调度、分时调度、实时调度、多处理机调度
。长程调度（高级调度、作业调度）、中程调度（它是对换功能的一部分）、短程调度（进程调度、低级调度）
。I/O调度
（30）、调度算法：
。先来先服务（FCFS）算法：按进程到达的先后顺序排队，每次调度队首的进程，属于非剥夺调度方式，实现简单，看似公平，但对于那些后进入队列而运行时间较短的进程，或I/O型的进程而言，可能需要长时间等待。
-对短进程不公平，增加了平均周转时间，不利于I/O型进程，未有效利用系统资源
。短进程优先算法：属于非剥夺调度方式
。时间片轮转调度法：首先按照进程到达的先后顺序组织就绪队列，即P1，P2，P3，P4。从队首开始调度，首先调度P1，执行一个时间片，强行中断P1，P1回到就绪队列队尾排队，切换到P2，执行一个时间片，强行中断P2，P2回到就绪队列队尾排队，。。。直到P4执行完一个时间片，强行中断P4，又开始执行P1一个时间片。
。基于优先级的调度算法：如何为进程设定优先级？静态优先级，动态优先级（采用动态优先级的两种调度算法：剩余时间最短者优先和响应比高者优先）
。反馈调度法：结合了优先级和时间片轮转调度
（31）、实时系统
。实时控制系统：如飞机的自动驾驶系统，导弹的制导系统、火炮的自动控制系统
。实时信息处理系统：如飞机的订票系统等
实时任务（具有及时性要求的，常常被重复执行的特定进程）：周期性实时任务和非周期性实时任务；开始截止时间和完成截止时间；硬实时任务和软实时任务
（32）、线程
。操作系统引入进程的目的是，为了描述和实现多个程序的并发执行，以改善资源利用率和提供系统的吞吐量；
。为什么需要引入线程呢？这是为了减少程序并发执行时系统所付出的额外开销，使操作系统具有更好的并发性；
。进程的两个基本属性：
-进程是一个拥有资源的独立单位；
-进程同时又是一个可以独立调度的基本单位；
。系统为进程进行的操作
-创建进程、撤销进程、进程切换
-进程作为资源的拥有者和系统的调度对象，需要花费系统较大的额外开销，故系统中同时存在的进程数目不宜过多，进程切换的频率也不宜过高，而这也就限制了并发度的进一步提高。
。由进程到线程
-目标：既能提高进程并发度，又能降低系统的额外开销
-实现：将进程的资源申请和调度属性分开。即进程作为资源的申请和拥有者，但不作为调度的基本单位。这样就产生了线程的概念。
-线程是进程中的一个实体，是独立调度和分派的基本单位；
-线程自身基本上不拥有系统资源，只拥有少许运行中必不可少的私有资源，线程可与同属于一个进程的其他线程共享进程的全部资源。
。线程的状态：
-进程中的所有线程共享该进程的状态。
-线程具有三种基本状态：就绪、执行、阻塞
-一般不具有挂起状态，因为线程共享进程的全部资源，如果挂起一个进程，其所属的全部进程必将被挂起，而单独挂起某进程中的一个线程，必然会影响同一进程中的其他线程的执行
。对线程的操作
-一个进程可以创建和撤销一个或多个线程，同一进程中的多个线程可以并发执行
-对线程的操作包括：
，派生，当系统创建一个进程时，同时也为该进程派生一个线程，同一进程中的线程可以再派生其他线程。
，阻塞，当线程需要等待某事件时，他将被阻塞，释放处理机执行其他线程。
，解除阻塞，
，结束，当线程执行完毕，释放其私有资源
注意：线程阻塞不一定会引起整个进程的阻塞，否则，引入线程带来的并发性就不会提高。
（33）、进程与线程
。传统操作系统中，一个进程可以创建一个线程，如MS DOS就是一个单用户、单进程、单线程的操作系统，UNIX是一个多用户、多进程、单线程的操作系统；
。现代操作系统和软件设计大多支持多线程运行，例如，Java虚拟机是一个单进程、多线程的运行环境，windows操作系统和Linux操作系统都采用了多进程、多线程技术；
。同一进程中的线程间切换不会引起进程切换，但当一个进程中的线程切换到另一个进程中的线程时，将会引起进程切换。
。进程之间可以并发执行，同属于一个进程的多个线程之间，也可并发执行。
。操作系统管理进程的开销显著的大于管理线程所需的开销
。进程切换的开销也远大于线程切换的开销
。由于同一进程中的多个线程具有相同的地址空间，使他们之间的同步和通信也比较容易。
。有些类型的线程切换、同步和通信都无需操作系统内核的干预。
（34）、线程的类型
。用户级线程：能节省大量的系统额外开销，并提高程序并发性
。内核级线程：系统内核负责内核级线程的创建、撤销、切换等操作。线程切换时需要进行模式切换。
。混合模式：
（35）、进程互斥与同步
。并发控制
-竞争资源
，当并发进程竞争使用同一资源时，他们之间会发生冲突
，如果操作系统将资源分配给其中的某一个进程使用，另一个进程就必须等待，直到申请的资源可用时，有操作系统分配给他；
，如果竞争某资源的进程太多，这些进程还必须等待在一个队列中，如就绪队列，阻塞队列等
，一种极端的情况是，被阻塞进程永久得不到申请的资源，而死锁。
，进程竞争资源首先必须解决互斥问题，某些资源必须互斥使用，如打印机、表格、文件等。
，这类资源又称为临界资源，访问临界资源的那段代码成为临界区
，任何时刻，只允许一个进程进入到临界区，以此实现进程对临界资源的互斥访问；
，临界区使用原则（互斥条件）：忙则等待、有限等待、空闲让进、让权等待
，竞争资源可能引起死锁：
如两个进程P1，P2竞争资源R1，R2，假设，现在P1已经占用了R1，且P2占用了R2，如果此时P1申请R2，且P2申请R1，结果P1、P2双方都占用对方申请的资源而阻塞，谁也不让步永久等待，形成死锁
，竞争资源-饥饿 P1，P2，P3，假设只有P1，P2能申请到资源
-共同协作
，共享协作同样涉及到互斥、死锁、饥饿问题，但更强调对数据的写操作必须互斥地进行。
，必须保证数据的一致性。
-通信协作
，无须互斥，但仍可能出现死锁和饥饿问题
（36）、互斥与同步的解决策略
。软件方法：很难控制多个进程的互斥，增加系统额外开销代表性的软件方法有：Dekker算法、Peterson算法；
第一次改进：为临界区设置一个状态标志，标明临界区是否可用，不能实现互斥；
第二次改进：首先检测临界区状态，可能导致死锁
第三次改进：首先表示自己要使用临界区，再检测临界区的状态，若临界区被占用，可用等待一小会再申请
。硬件方法：减少系统额外开销
屏蔽中断：约束条件太强，付出代价太大
专用机器指令：非常简单，易于证明。testset指令、exchange指令
。信号量的方法：通用方法
-如交通信号灯，定义信号量的两个原子操作：wait(s)和singal(s)
-信号量分为：互斥信号量和资源信号量。s.count
-当仅有两个并发进程共享临界资源时，互斥信号量仅能取值0、1、-1，
-s.count=1，表示无进程进入临界区；s.count=0，表示已有一个进程进入临界区；s.count=-1表示已有以进程正在等待进入临界区
-当用s来实现n个进程的互斥时，s.count的取值范围为1~ -（n-1）
-经典进程互斥与同步问题：
：：生产者/消费者问题：循环使用缓冲区
：不控制生产者/消费者
：生产者/消费者必须互斥：某时刻只允许一个访问缓冲区
：生产者/消费者必须同步：即生产者不能向满缓冲区写数据，消费者不能在空缓冲区取数据。
：：读者/写者问题
：多个进程访问一个共享数据区。
：允许多个读者进程可以同时读数据；不允许多个写者进程同时写数据，只能互斥写数据；若有写者进程正在写数据，则不允许读者进程读数据。
：读者优先readcount，导致写者饥饿
：写者优先writecount，
：：哲学家进餐问题
：五个哲学家围坐在一张圆桌周围，每个哲学家面前都有一碗面，相邻两碗面条之间有一只筷子，只有同时获得两只筷子，才能开始吃面条，
。管程方法：面向对象的方法
。消息传递方法
（37）、死锁
。多个进程竞争资源，或执行时推进的顺序不当，或相互通信而永久阻塞现象，称为死锁。
。竞争可重用资源可能会死锁
。产生互斥的条件：
-互斥（必要条件）
-占有且等待（必要条件）
-非剥夺（必要条件）
-循环等待（充分条件），只要系统出现循环等待，则一定出现死锁
。解决死锁的方法：
-预防死锁：
：禁止“互斥”，互斥使用是临界资源固有的属性，不能因为互斥会导致死锁而禁止互斥
：禁止“占有且等待”，不合理，降低了系统吞吐量和资源利用率；浪费资源
：禁止“非剥夺”，实现起来比较复杂，而且付出很大代价
：禁止“循环等待”，
-避免死锁
银行家算法
-检测并解除死锁
（38）、进程通信
3、存储管理
（1）、存储管理的任务
。存储分配
》基本任务：管理内存空间的分配与释放
-分配基本内存空间
-增加新的内存空间----动态申请或释放内存空间
-回收内存空间
》用于内存管理的数据结构
》存储分配步骤：
-在内存分区中寻找一块满足进程需要的内存空间，将其分配给进程。
-更新进程的资源分配清单、内存分配情况清单等数据结构
。内存的回收
。地址映射：逻辑地址（相对地址）；物理地址（绝对地址）
。存储保护
。存储共享
。共享代码
。存储扩充
（2）、内存划分与分配技术
。内存划分：
-静态划分：划分预先进行，创建新进程时，在内存中找到一个合适的分区分配给它。
-动态划分：根据进程申请的空间大小，在这个分区中动态的划分给它。
：首次适应算法（FFA）
：外零头：紧凑
：下次适应算法（NFA）
：最佳适应算法（BFA）
：最差适应算法（WFA）
（3）、程序装入技术
。绝对装入：程序运行之前，按照程序的逻辑地址，将程序和数据装入内存指定的地方；
。重定位装入：程序可以装入到内存的任何位置，其逻辑地址与装入内存后的物理地址无直接关系。静态重定位技术：地址映射在程序装入时进行，以后不再更改程序地址。
。运行时动态装入：程序的地址转换在程序运行时动态进行。有利于多道程序环境下进程的换进/换出及实现紧凑技术。
（4）、静态链接、动态链接（装入时，运行时）
（5）、简单存储管理技术
。简单存储
。连续存储：最简单的存储管理技术
。非连续存储：允许进程的程序和数据分别装在不同分区中，常用的非连续存储技术：分页存储技术、分段存储技术及其结合。
（6）、分页存储管理技术：是一种特殊的固定分区方法
。页表
。页框
（7）、分段存储管理技术：
。段表
。空闲分区表
（8）、段页式存储管理：
（9）、虚拟存储技术的典型问题：如果系统花费大量的时间把程序和数据频繁的装入和移出内存而不是执行用户指令，称系统出现了抖动
。根本原因：选择的页面或段不恰当
（10）、负载控制
。负载控制主要解决系统应当保持多少个活动进程驻留在内存的问题，即控制多道程序系统的度。
。当内存中的活动进程数太少时，负载控制将增加新进程或**一些挂起进程进入内存；反之，内存中 的进程数太多时，负载控制将暂时挂起一些进程
4、设备管理
（1）、设备管理的主要功能
。设备分配：设备管理的基本任务
。设备映射
。设备驱动
。I/O缓冲区的管理
（2）、通用设备管理分层模块
。设备的控制
。设备驱动程序
。I/O控制方式
-程序I/O方式
-中断I/O方式
-DMA(直接存储器访问)方式
-通道方式
（3）、I/O缓冲技术
。缓解处理机与设备速度不匹配的矛盾
。实现设备与处理机一定程度的并行操作
。减少设备的中断频率，放宽对中断响应时间的限制
。单缓冲：
。双缓冲：两个缓冲可以交替使用
。循环缓冲：
。缓冲池：提高缓冲区的利用率，缓冲池中的缓冲区通常组织成链表结构
-块型设备的缓冲池
-字符型设备的缓冲池
。虚拟设备技术：解决独占设备利用率不高的问题
-虚拟设备技术的实现：在独占型设备与进程之间加入一个共享型设备作为过渡
。SPOOLing系统
（4）、磁盘的性能和安全性
。扇区是磁盘进行I/O传输的基本单位，也是磁盘空间分配的基本单位
。影响磁盘I/O性能的技术
-寻道时间
-旋转延迟
-数据传输时间
。磁盘的平均访问时间：寻道时间+旋转延迟（8.3ms）+数据传输时间(16.7ms)
。磁盘容错技术
。磁盘管理算法：磁盘调度、Disk Cache、高性能的文件系统（磁盘碎片整理，使磁盘文件尽可能完整）
（5）、磁盘容错技术
。通过系统中设置冗余部件来提高系统可靠性。使得当磁盘系统某部件出现缺陷或故障时，磁盘仍然正常工作，
。SFT-I低级磁盘容错技术
。SFT-II中级磁盘容错技术：防止磁盘驱动器或磁盘控制器发生故障
-磁盘镜像
-磁盘双工
RAID技术
。SFT-III高级磁盘容错技术
5、文件管理
（1）、文件系统概述
。文件系统功能：
。文件系统是指：操作系统中的各类文件、管理文件的软件
（2）、文件系统与数据库管理系统
。数据库管理系统依赖文件系统
-数据库管理系统负责：数据定义及操作
-文件系统只处理无结构、无格式的字节流
。数据库管理系统独立于文件系统
（3）、文件
。定义
。文件中的数据结构
-字段或域
-记录：关键字，唯一的标识一条记录
。文件分类：
（4）、目录文件
。一级目录文件
。二级目录文件
。树型目录文件
。无循环图结构
（5）、文件路径
。相对路径
。绝对路径
（6）、有结构文件、无结构文件
（7）、分区大小