1. 操作系统概述
1）操作系统的定义和作用
计算机系统的软件分为系统软件和应用软件。
系统软件是计算机系统的一部分，支持应用软件的运行。如操作系统、语言处理程序、链接程序、诊断程序和数据库管理系统等。
应用软件是计算机用户利用计算机的软件、硬件资源为某一专门的应用目的而开发的软件。如科学计算、工程设计、数据处理、事务处理、过程控制程序，以及文字处理软件、表格处理软件、辅助设计软件和实时处理软件等。
操作系统(Operating System,OS)是计算机系统中的核心系统软件，其他软件建立在操作系统的基础上，并在操作系统的统一管理和支持下运行，是用户与计算机之间的接口。
操作系统定义：能有效地组织和管理系统中的各种软/硬件资源，合理地组织计算机系统工作流程，控制程序的执行，并且向用户提供一个良好的工作环境和友好的接口。
两个重要作用：
通过资源管理（软硬件资源管理），提高计算机系统的效率。
改善人机界面，向用户提供友好的工作环境。
操作系统的4个特征是并发性、共享性、虚拟性和不确定性。
操作系统的功能可分为进程管理、文件管理、存储管理、设备管理和作业管理5大部分。
进程管理：实质上是对处理机的执行时间进行管理，采用多道程序等技术将CPU的时间合理地分配给每个任务，主要包括进程控制、进程同步、进程通信和进程调度。
文件管理：主要包括文件存储空间管理、目录管理、文件的读/写管理和存取控制。
存储管理：是对主存储器空间进行管理，主要包括存储分配与回收、存储保护、地址映射（变换）和主存扩充。
设备管理：对硬件设备的管理，包括对输入/输出设备的分配、启动、完成和回收。
作业管理：包括任务、界面管理、人机交互、图形界面、语音控制和虚拟现实等。
操作系统的5大部分通过相互配合、协调工作来实现对计算机系统中资源的管理，控制任务的运行。
2）操作系统分类
操作系统可分为批处理操作系统、分时操作系统、实时操作系统、网络操作系统、分布式操作系统和嵌入式操作系统等类型。
批处理操作系统：即用户将一系列作业（如程序运行、数据处理等任务）作为一个批次提交给计算机，然后由操作系统控制自动顺序执行。
分时操作系统：一个计算机系统与多个终端设备连接。分时操作系统是将CPU的工作时间划分为许多很短的时间片，轮流为各个终端的用户服务。
实时操作系统：指计算机对于外来信息能够以足够快的速度进行处理，并在被控对象允许的时间范围内做出快速反应。
网络操作系统：使联网计算机能方便而有效地共享网络资源，为网络用户提供各种服务的软件和有关协议的集合。
分布式操作系统：由多个分散的计算机经连接而成的计算机系统，系统中的计算机无主、次之分，任意两台计算机可以通过通信交换信息。
嵌入式操作系统：系统运行在嵌入式智能芯片环境中，对整个智能芯片以及它所操作、控制的各种部件装置等资源进行统一协调、处理、指挥和控制。
2. 进程管理
1）进程基本概念和模型
进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。它由程序块、进程控制块（PCB）和数据块三部分组成。
进程与程序的区别：
- 进程是程序的一次执行过程，没有程序就没有进程。
- 程序是完成某个特定功能的一系列程序语句的集合，只要不被破坏，它就永远存在。
- 程序是一个静态的概念，而进程是一个动态的概念，它由创建而产生，完成任务后因撤销而消亡；
进程是系统进行资源分配和调度的独立单位，而程序不是。
三态模型对应的三态如下：
- 运行状态：占有处理器正在运行。
- 就绪状态：指具备运行条件，等待系统分配处理器以便运行。
- 等待状态：也称阻塞状态或睡眠状态，指不具备运行条件，正在等待某个事件的完成。
三态模型转换：
- 运行状态到等待状态，等待使用资源，如等待外设传输，等待人工干涉。
- 等待状态到就绪状态，资源得到满足，如外设传输结束，人工干预完成。
- 运行状态到就绪状态，运行时间片到，出现有更高优先权进程。
- 就绪状态到运行状态，CPU空闲时选择一个就绪进程。
五态模型图如下：
- 活跃就绪：指进程在主存并且可被调度的状态。
- 静止就绪：指就绪进程被对换到辅存时的状态，它是不能被直接调度的状态，只有当主存中没有活跃就绪状态进程，或者是挂起态进程具有更高的优先级时，系统将把挂起就绪进程调回主存并转换活跃就绪。
- 活跃阻塞：指进程在主存，一旦等待的事件产生便进入活跃就绪状态。
- 静止阻塞：指阻塞进程对换到辅存时的状态，一旦等待的事件产生便进入静止就绪状态。
- 挂起：将进程调出内存，保存到外存队列中，并释放资源。
- 激活：恢复挂起进程，重新调入内存。
目的：释放进程占用的资源以缓解资源不足。
原因：终端用户的请求，父进程的请求、OS的需要（如负荷调节、对换等）。
2）进程的控制
进程控制就是对系统中的所有进程从创建到消亡的全过程实施有效的控制。
前驱图，依次有序进行。
同步是合作进程间的直接制约问题，是指在系统中一些需要相互合作，协同工作的进程。
互斥是申请临界资源进程间的间接制约问题，是指系统中多个进程因争用临界资源而互斥执行。
（1）临界资源：一次只能供一个进程使用的资源，进程间需要互斥方式对其进行共享的资源，如打印机、磁带机等。
（2）临界区：进程中对临界资源实施操作的那段程序，或者每个进程中访问临界资源的那段代码称为临界区。对互斥临界区管理的4条原则如下：
有空即进。当无进程处于临界区时，允许进程进入临界区，并且只能在临界区运行有限的时间。
无空则等。当有一个进程在临界区时，其他欲进入临界区的进程必须等待，以保证进程互斥地访问临界资源。
有限等待。对于要求访问临界资源的进程，应保证进程能在有限的时间进入临界区，以免陷入“饥饿”状态。
让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等状态。
（3）信号量：是一种特殊的变量。
信号量S的物理意义：S≥0表示某资源的可用数，若S<O，则其绝对值表示阻塞队列中等待该资源的进程数。
PV操作是实现进程同步与互斥的常用方法。P操作和V操作是低级通信原语，在执行期间不可分割。其中，P操作表示申请一个资源，V操作表示释放一个资源。
P操作的定义：S:=S-1。若S≥0，则执行P操作的进程继续执行；若S<O，则将该进程置为阻塞状态(因为无可用资源)，并将其插入阻塞队列。Semaphore表示所定义的变量或者信号量，操作过程如下：
Procedure P(Var S:Semaphore); Begin S:S-1; if S<0 then W(S) {执行P操作的进程插入等待队列} End;
V操作定义：S:=S+1。若S>0，则执行V操作的进程继续执行；若S≤O，则从阻塞状态唤醒一个进程，并将其插入就绪队列，然后执行V操作的进程继续。
Procedure P(Var S:Semaphore); Begin S:S+1; if S<=0 then R(S) {从阻塞队列中唤醒一个进程} End;
利用PV操作实现进程的互斥。令信号量mutex的初值为1，当进入临界区时执行P操作，退出临界区时执行V操作。
利用PV操作实现进程的同步。假定用信号量S表示某条消息，进程可以通过调用P操作测试消息是否到达，调用V操作通知消息已准备好。最典型的同步问题是单缓冲区的生产者和消费者的同步问题。
PV与前驱图结合的例题，基本思想，PV不可分割，根据入度和出度可知有多少PV操作。
3）死锁
死锁概念：进程管理是操作系统的核心，但如果设计不当，就会出现死锁的问题。如果一个进程在等待一个不可能发生的事情，则进程就死锁了。而如果一个或多个进程产生死锁，就会造成系统死锁
若系统中有m个资源被n个进程共享，当每个进程都要求k个资源，而m<n(k-1)+1时，即资源数小于进程所要求的总数时，可能会引起死锁。
示例.系统有三个进程 A、B、C。这3个进程都需要5个系统资源。如果系统有多少个资源，则不可能发生死锁。
答：至少有 n*(w-1)+1 个资源不可能发生死锁，n为进程数，w为需要的资源。
产生死锁的4个必要条件是互斥条件、请求保持条件、不可剥夺条件和环路条件。当发生死锁时，在进程资源有向图中必构成环路，其中每个进程占有了下一个进程申请的一个或多个资源，导致进程申请的资源无法满足而产生死锁。
死锁的处理策略有鸵鸟策略（即不理睬策略），预防策略、避免策略和检测与解除死锁。
死锁预防是打破4大条件。有两种策略：预先静态分配法，破坏不可剥夺条件；资源有序分配法，破坏环路条件。
死锁避免是不严格地限制产生死锁的必要条件。
死锁检测时定时运行死锁检测程序，判断系统是否发生死锁，若有死锁设法解除。
死锁解除是采用资源剥夺法和撤销进程法。
银行家算法对于进程发出的每一个系统可以满足的资源请求命令加以检测，如果发现分配资源后系统进入不安全状态，则不予分配；若分配资源后系统仍处于安全状态，则实施分配。与死锁预防策略相比，它提高了资源的利用率，但检测分配资源后系统是否安全增加了系统开销。
分配资源的原则：
当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程。
进程可以分期请求资源，但请求的总数不能超过最大需求量。
当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源。
最大需求量 - 已分配资源数 = 还需资源数；现有资源（剩下的资源数）、需要资源数、已分配资源数、现有+已经分配。
线程作为调度和分配的基本单位，进程作为独立分配资源的单位。用户可以通过创建线程来完成任务，以减少程序并发执行时付出的时空开销。
3. 存储管理
存储器管理的对象是主存存储器，简称主存或内存。
存储器管理的主要功能包括主存空间的分配和回收、提高主存的利用率、扩充主存、对主存信息实现有效保护。
常用的存储器的结构有“寄存器一主存一外存”结构和“寄存器一缓存一主存一存储组织的功能外存”结构。
1）分区存储
分区存储管理基本思想是把主存的用户区划分成若干个区域，每个区域给一个用户作业使用，并限定它们只能在自己的区域中运行。按划分方式不同，可分为固定分区、可变分区和可重定位分区。
固定分区。静态分区方式，在系统生成时己将主存划分若干个分区，每个分区的大小可不等。
可变分区。动态分区方式，存储空间的划分是在作业装入时进行的，故分区的个数是可变的，分区的大小刚好等于作业的大小。可变分区的请求和释放分区主要有4种算法：最先匹配法、下次匹配法、最佳匹配法、最坏匹配法。最佳适应算法、最差适应算法、首次适应算法和循环首次适应算法。
- 可重定位分区。移动所有已分配好的分区，使之成为连续区域。
2）页式存储
分区存储的用户程序必须装入连续的地址空间中，但页式存储则是用虚拟空间存储。
纯分页式存储是将一个进程的地址空间划分成若干个大小相等的区域，称为页。相应地，将主存空间划分成与页相同的若干物理块，称为块或页框。在为进程分配主存时，将进程中若干页分别装入多个不相邻接的块中。当进程的多个页面离散地分配到主存的多个物理块时，系统应能保证在主存中找到进程要访问的页面所对应的物理块，因此建立一张页面映射表，简称页表。块号+页内地址就是物理地址。
优点：利用率高，碎片小，分配及管理简单。缺点：增加了系统开销；可能产生抖动现象。
示例.页式存储系统的逻辑地址是有页号和页内地址两部分组成。假定页面的大小为4K，
答：
方法一：4 K = 2 12 4K=2^{12}4K=2
12
页内地址用12位表示；8644->10 0001110001000，10 = 2 1 10=2^110=2
1
，所以页号为2，即 1000 0001110001000 ，1000 = 2 8 1000=2^81000=2
8
。
方法二：页号=8644/4k=8644/4096=2；页内地址=8644%4096=452；物理块号=8x4096+452
3）段式存储
段式存储。作业的地址空间被划分为若干个段，每个段是一组完整的逻辑信息，例如有主程序段、子程序段、数据段及堆栈段等，每个段都有自己的名字，都是从0开始编址的一段连续的地址空间，各段的长度是不等的。段号和段内地址组成。
优点：多到程序共享内存，各段程序修改互不影响；缺点：内存利用率低，内存碎片浪费大。
4）段页式存储
段页式存储的基本原理是先将整个主存划分成大小相等的存储块(页框)，将用户程序按程序的逻辑关系分为若干个段，并为每个段赋予一个段名，再将每个段划分成若干页，以页框为单位离散分配。地址结构由段号、段内页号和页内地址三部分组成。
优点：空间浪费小，存储共享容易，存储保护容易，能动态连接。缺点：由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降。
5）虚拟存储
虚拟存储器：具有部分装入和部分对换功能，能从逻辑上对内容容量大幅度扩充，使用方便的一种存储器系统。实际上是为扩大主存而采用的一种设计技巧。虚拟存储器的容量与主存大小无关。虚拟存储器的实现对用户来说是透明的。
虚拟存储器的实现有请求分页系统、请求分段系统、请求段页式系统。
页面置换算法：最佳置换算法（Optimal）、先进先出置换算法（FIFO）、最近最少未使用置换算法（Least Recently Used）、最近未用置换算法（Not Used Recently）。
4. 磁盘管理
磁盘是可被多个进程共享的设备。磁盘结构有磁道和扇区组成，最外层是0磁道。
磁盘的调度算法：
先来先服务（FCFS）。根据进程请求访问磁盘的先后次序进行调度。优点是公平和简单，且每个进程的请求都能依次得到处理，不会出现某进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。
最短寻道时间优先（SSTF）。选择要求访问的磁道与当前磁头所在的磁道距离最近，使得每次的寻道时间最短。但这种调度算法不能保证平均寻道时间最短。
扫描算法（SCAN）。又称电梯算法，扫描算法不仅考虑到要访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。
单向扫描调度算法（CSCAN）。与扫描算法类似，但规定磁头只能做单向移动。
读取磁盘数据的时间应包括以下三个部分：
找磁道的时间。
找块（扇区）的时间，即旋转延迟时间。
传输时间。
示例.某磁盘磁头从一个磁道移至另一个磁道需要10ms。文件在磁盘上非连续存放，逻辑上相邻数据块的平均移动距离为10个磁道，每块的旋转延迟时间及传输时间分别为100ms和2ms，则读取一个100块的文件需要___ms时间。
A.10200 B.11000 C.11200 D.20200
分析：100x(10x10+100+2)=20200，选择D。
非格式化容量 = 面数 x（磁道数/面）x 内圆周长 x 最大位密度；
格式化容量 = 面数 x （磁道数/面）x（扇区数/道）x（字节数/扇区）。
5. 文件管理
1）基本概念
文件(File)是具有符号名的、在逻辑上具有完整意义的一组相关信息项的集合。一个源程序、一个目标程序、编译程序、一批待加工的数据和各种文档等都可以各自组成一个文件。
信息项是构成文件内容的基本单位，可以是一个字符，也可以是一个记录，记录可以等长，也可以不等长。一个文件包括文件体和文件说明。
文件体是文件真实的内容。
文件说明是操作系统为了管理文件所用到的信息，包括文件名、文件内部标识、文件的类型、文件存储地址、文件的长度、访问权限、建立时间和访问时间等。
文件是一种抽象机制，它隐藏了硬件和实现细节，提供了将信息保存在磁盘上而且便于以后读取的手段，使用户不必了解信息存储的方法、位置以及存储设备实际操作方式便可存取信息。
文件管理系统是操作系统中实现文件统一管理的一组软件和相关数据的集合，专门负责管理和存取文件信息的软件机构，简称文件系统。
文件的类型：
按文件性质和用途可将文件分为系统文件、库文件和用户文件。
按信息保存期限分类可将文件分为临时文件、档案文件和永久文件。
按文件的保护方式分类可将文件分为只读文件、读/写文件、可执行文件和不保护文件。
UNIX系统将文件分为普通文件、目录文件和设备文件（特殊文件）。
目前常用的文件系统类型有FAT、Vfat、NTFS、Ext2和HPFS等。
2）文件的结构
文件的逻辑结构可分为两大类：一类是有结构的记录式文件，它是由一个以上的记录构成的文件，故又称为记录式文件; 二是无结构的流式文件，它是由一串顺序字符流构成的文件。
文件的物理结构是指文件的内部组织形式，即文件在物理存储设备上的存放方法。
顺序结构。也称连续结构，将逻辑上连续的文件信息（如记录）依次存放在连续编号的物理块上。
链接结构。也称串联结构，将逻辑上连续的文件信息（如记录）依次存放在不连续编号的物理块上。
索引结构。将逻辑上连续的文件信息（如记录）依次存放在不连续编号的物理块上，系统为每个文件建立一张索引表。
3）文件目录
文件控制块（FCB）要包括文件名和存放文件的物理地址，文件控制块的有序集合称为文件目录。
在多级目录结构的文件系统中，用户要访问一个文件，必须指出文件所在的路径名，路径名是从根目录开始到该文件的通路上所有各级目录名拼起来得到的。绝对路径是整个磁盘的路径，相对路径是相对目录下的路径。
4）文件存储空间的管理
要将文件保存到外部存储器(简称外存或辅存)上首先必须知道存储空间的使用情况，即哪些物理块是被“占用”的，哪些是“空闲”的。
常用的空闲空间的管理方法有空闲区表、位示图和空闲块链3种。
空闲区表。将外存空间上的一个连续的未分配区域称为“空闲区”。操作系统为磁盘外存上的所有空闲区建立一张空闲表，每个表项对应一个空闲区，空闲表中包含序号、空闲区的第一块号、空闲块的块数和状态等信息。
位示图。在外存上建立一张位示图(bitmap)，记录文件存储器的使用情况。每一位对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用。主要特点是位示图的大小由磁盘空间的大小(物理块总数)决定，位示图的描述能力强，适合各种物理结构。
空闲块链。每个空闲物理块中有指向下一个空闲物理块的指针，所有空闲物理块构成一个链表，链表的头指针放在文件存储器的特定位置上(如管理块中)，不需要磁盘分配表，节省空间。
成组链接法。UNIX系统使用改方法。
示例.某文件管理系统在磁盘上建立了位示图(bitmap)，记录磁盘的使用情况。若系统的字长为32位，磁盘上的物理块依次编号为0,1,2,…，那么4096号物理块的使用情况在位示图中的第 (1) 个字中描述:若磁盘的容量为200GB，物理块的大小为1MB，那么位示图的大小为 (2) 个字。
(1)A.129 B.257 C.513ms D.1025
(2)A.600 B.1200 C.3200 D.6400
分析：（1）答案A，系统的字长为32位，（4096+1)/32=129向上取整。（2）答案D，200x1024/32=6400个字。
6. 设备管理
设备是计算机系统与外界交互的工具，具体负责计算机与外部的输入/输出工作，所以常称为外部设备(简称外设)。
在计算机系统中，将负责管理设备和输入/输出的机构称为I/O系统。因此，I/O系统由设备、控制器、通道 (具有通道的计算机系统)、总线和I/O软件组成。
设备有不同的分类方式。
按数据组织分类：可分为块设备和字符设备。
按功能分类：设备可分为输入设备、输出设备、存储设备、网络联网设备、供电设备等。
从资源分配角度分类：可分为独占设备、共享设备和虚拟设备。
按数据传输率分类：可分低速设备、中速设备和高速设备。
设备管理的目标主要是如何提高设备的利用率，为用户提供方便、统一的界面。提高设备的利用率，就是提高CPU与I/O设备之间的并行操作程度。在设备管理中，主要利用的技术有中断技术、DMA技术、通道技术、缓冲技术和Spooling技术。
设备管理的任务是保证在多道程序环境下，当多个进程竞争使用设备时，按一定的策略分配和管理各种设备，控制设备的各种操作，完成I/O设备与主存之间的数据交换。
设备管理的主要功能是动态地掌握并记录设备的状态、设备分配和释放、缓冲区管理、实现物理I/O设备的操作、提供设备使用的用户接又及设备的访问和控制。
Spooling技术是用一类物理设备模拟另一类物理设备的技术，是使独占使用的设备变成多台虚拟设备的一种技术，也是一种速度匹配技术。由“预输入程序”“缓输出程序”和“井管理程序”以及输入和输出井组成的。其中，输入井和输出井是为了存放从输入设备输入的信息以及作业执行的结果，系统在辅助存储器上开辟的存储区域。
缓解了CPU和外围设备不匹配问题，使设备变成了共享设备，使设备变成了虚拟设备。
