操作系统基本原理

操作系统的类型与结构

操作系统是计算机系统中最基本的系统软件，它既管理计算机系统的软、硬件资源，又控制程序的执行。操作系统的基本类型有：批处理操作系统、分时操作系统和实时操作系统。从资源管理的角度看，操作系统主要是对处理器、存储器、文件、设备和作业进行管理。操作系统（Operating System，OS）是计算机系统中的核心系统软件，负责管理和控制计算机系统中的硬件和软件资源，合理地组织计算机工作流程和有效地利用资源，在计算机与用户之间起接口的作用。操作系统为用户提供的接口表现形式一般为：命令、菜单、窗口之类的，而操作系统为应用程序提供的接口为 API。操作系统与硬件/软件的关系如下图所示。

操作系统基本原理

操作系统的主要功能是进行处理机与进程管理、存储管理、设备管理、文件管理和作业管理的工作。

进程管理

处理机管理也被称为进程管理。处理机管理的功能就是组织和协调用户对处理机的争夺使用，把处理机分配给进程，对进程进行管理和控制，最大限度也发挥处理机的作用。

进程
       进程的概念用静态的观点看，操作系统是一组程序和表格的集合。用动态的观点看，操作系统是进程的动态和并发执行的。
       顺序程序是指程序中若干操作必须按照某种先后次序来执行，并且每次操作前和操作后的数据、状态之间都有一定的关系。在早期的程序设计中，程序一般都是按顺序执行的。
       在多道程序系统中，程序的运行环境发生了很大的变化。主要体现在资源共享和程序的并发执行/并行执行。程序的并行执行和资源共享之间是相辅相成的。一方面，只有允许程序并行执行，才可能存在资源共享的问题；另一方面，只有有效地实现资源共享，才可能使得程序并行执行。
进程的状态转换
由进程运行的间断性，决定了进程至少具有以下三种状态：
（1）就绪状态。当进程已分配了除 CPU 以外的所有必要的资源后，只要能再获得处理机，便能立即执行，把这时的进程状态称为就绪状态。在一个系统中，可以有多个进程同时处于就绪状态，通常把它们排成一个队列，称为就绪队列。
（2）执行状态指进程已获得处理机，其程序正在执行。在单处理机系统中，只能有一个进程处于执行状态。
（3）阻塞状态指进程因发生某事件（如请求 I/O、申请缓冲空间等）而暂停执行时的状态，亦即进程的执行受到阻塞，故称这种暂停状态为阻塞状态，有时也称为“等待”状态，或“睡眠”状态。通常将处于阻塞状态的进程排成一个队列，称为阻塞队列。

进程的状态可以动态地相互转换，具体转换条件见下图，但阻塞状态的进程不能直接进入执行状态，就绪状态的进程不能直接进入阻塞状态。
挂起状态
在不少系统中，进程只有就绪、运行、阻塞三种状态。但在另外一些系统中，又增加了一些新状态，其中最重要的是挂起状态。引入挂起状态的原因有：对换的需要、终端用户的请求、父进程请求、负荷调节的需要、操作系统的需要。
互斥与同步
       进程互斥与同步进程互斥定义为：一组并发进程中一个或多个程序段，因共享某一共有资源而导致必须以一个不允许交叉执行的单位执行。也就是说互斥是要保证临界资源在某一时刻只被一个进程访问。
       进程同步定义为：把异步环境下的一组并发进程因直接制约而互相发送消息而进行互相合作、互相等待，使得各进程按一定的速度执行的过程称为进程同步。也就是说进程之间是异步执行的，同步即是使各进程按一定的制约顺序和速度执行。
       互斥是资源的竞争关系，而同步是进程间的协作关系。
前趋图
前趋图是一个由结点和有向边构成的有向无循环图。该图通常用于表现事务之间先后顺序的制约关系。图中的每个结点可以表示一个语句、一个程序段或是一个进程，结点间的有向边表示两个结点之间存在的前趋关系。

图中 A1 没有前趋结点，称为开始结点，它不受任何制约，可以直接执行；而 B1 与 A2 只能在 A1 执行完成之后才能开始，而 B2 必须在 B1 与 A2 完成之后才能开始；C3 没有后继结点，称为终止结点。
进程调度与死锁
       进程调度即处理器调度（又称上下文转换），它的主要功能是确定在什么时候分配处理器，并确定分给哪一个进程，即让正在执行的进程改变状态并转入就绪队列的队尾，再由调度原语将就绪队列的队首进程取出，投入执行。
       调度算法：先来先服务(FCFS/FIFO)、优先数调度、轮转法。
       当若干个进程互相竞争对方已占有的资源，无限期地等待，不能向前推进时会造成“死锁”。死锁是系统的一种出错状态，它不仅会浪费大量的系统资源，甚至还会导致整个系统的崩溃，所以死锁是应该尽量预防和避免的。
       产生死锁的必要条件是：互斥条件、保持和等待条件、不剥夺条件和环路等待条件。
       解决死锁有两种策略：一种是在死锁发生前采用的预防和避免策略；另一种是在死锁发生后采用的检测与恢复策略。
       实际上，系统出现死锁的概率很小，故从系统所花的代价上看，采用死锁发生后的检测与恢复策略要比采用死锁发生前的预防与避免策略代价小一些。

存储管理

存储管理主要是指对内存储器的管理，负责对内存的分配和回收、内存的保护和内存的扩充。存储管理的目的是尽量提高内存的使用效率。存储管理的机制经历了多次变迁，由以前的单一连续区管理到分区存储管理再发展为段页式管理。

页式存储管理
分页的基本思想是把程序的逻辑空间和内存的物理空间按照同样的大小划分成若干页面，并以页面为单位进行分配。

当内存中无空闲块时，为了装入一个页面而必须按某种算法从已在内存的页中选择一页，将它暂时调出内存，让出内存空间以存放所需装入的页面，这个工作称为“页面调度”。常用的页面调度算法有:最优（OPT）算法、随机（RAND）算法、先进先出算法、最近最少使用（Least Recently Used，LRU）算法
段式存储管理
段式存储管理与页式存储管理相似。分段的基本思想是把用户作业按逻辑意义上有完整意义的段来划分，并以段为单位作为内外存交换的空间尺度。
段页式存储管理
段页式管理是段式和页式两种管理方法结合的产物，综合了段式组织与页式组织的特点，根据程序模块分段，段内再分页，内存被分划成定长的页。

如果按段页式存储管理的方式，把每一段再分成若干页面，那么，每一段不必占用连续的存储空间；甚至当内存块不够时，可只将一段中的部分页面装入内存，这种管理方式称为“段页式虚拟存储管理”。段页式虚拟存储管理结合了段式和页式的优点，但增加了设置表格（段表、页表）和查表等开销，段页式虚拟存储器一般只在大型计算机系统中使用。

设备管理

在计算机系统中，除了处理器和内存之外，其他的大部分硬设备称为外部设备。它包括输入/输出设备，辅存设备及终端设备等。

文件管理

文件管理的功能包括：建立、修改、删除文件；按文件名访问文件；决定文件信息的存放位置、存放形式及存取权限；管理文件间的联系及提供对文件的共享、保护和保密等。

文件的逻辑结构
文件的结构是指文件的组织形式，从用户角度所看到的文件组织形式，称为文件的逻辑结构。
文件的物理结构
文件的物理结构是指文件在存储设备上的存放方法。文件的物理结构涉及文件存储设备的组块策略和文件分配策略，决定文件信息在存储设备上的存储位置。常用的文件分配策略有：
顺序分配（连续分配）：其缺点是在文件建立时必须指定文件的信息长度，以后不能动态增长，一般不宜用于需要经常修改的文件。
链接分配（串联分配）：链接分配的优点是可以解决存储器的碎片问题，提高存储空间利用率。由于链接文件只能按照队列中的链接指针顺序查找，因此搜索效率低，一般只适用于顺序访问，不适用于随机存取。
索引分配（见下图）：索引分配既可以满足文件动态增长的要求，又可以方便而迅速地实现随机存取

索引分配既可以满足文件动态增长的要求，又可以方便而迅速地实现随机存取。索引文件的优点是既适用于顺序存取，又适用于随机存取。缺点是索引表增加了存储空间的开销。
文件存储设备管理
文件存储设备的管理实质上是对空闲块的组织和管理问题。它包括空闲块的组织，空闲块的分配与空闲块的回收等问题。有3种不同的空闲块管理方法，它们分别是索引法、链接法和位示图法。

作业管理

从用户的角度看，作业是系统为完成一个用户的计算任务（或一次事务处理）所做的工作总和。一个作业从交给计算机系统到执行结束退出系统，一般都要经历提交、后备、执行和完成 4 个状态。

提交状态
作业由输入设备进入外存储器（也称输入井）的过程称为提交状态。处于提交状态的作业，其信息正在进入系统。
后备状态
当作业的全部信息进入外存后，系统就为该作业建立一个作业控制块（Job Control Block，JCB）。系统通过 JCB 感知作业的存在。JCB 主要内容包括作业名、作业状态、资源要求、作业控制方式、作业类型及作业优先权等。
执行状态
一个后备作业被作业调度程序选中而分配了必要的资源并进入了内存，作业调度程序同时为其建立了相应的进程后，该作业就由后备状态变成了执行状态。
完成状态
完成状态。当作业正常运行结束，它所占用的资源尚未全部被系统回收时的状态为完成状态。