操作系统

一、操作系统引论

1.操作系统的目标

(1)方便性 (2)有效性 (3)可扩充性 (3)开放性

2.各操作系统的特点

单道批处理系统、多道批处理系统、分时系统、实时系统

批处理系统：多道性、无序性、调度性，系统利用率高、吞吐量大、平均周转时间长、但无交互能力。

分时系统：有多路性、独立性、及时性和交互性。有较好的人机交互的特性，并且可以实现共享主机。

实时系统：有多路线、独立性、及时性、交互性和可靠性。实际上是指操作系统工作时，其各种资源可以根据需要随时进行动态分配。由于各种资源可以进行动态分配，因此，其处理事务的能力较弱、速度较快。

总结：从可靠性：实时系统更强，从交互性：分时系统更强。

3.操作系统的基本特性

并发、共享、虚拟、异步

4.概念

并发性是指两个或多个事件在同一时刻发生。

并行性是指两个或多个事件在同一时间间隔内发生。

在OS中，把通过某种技术将一个物理试实体变为若干个逻辑上的对应物的功能称为虚拟。

二、进程的描述与控制

1.程序并发执行的特征

(1)间断性：程序在并发执行的时候，因为是共享资源，以及完成同一项任务而相互合作，致使在这些并发执行的程序之间形成了相互制约的关系，导致程序执行呈现：执行–暂停–执行。

(2)失去封闭性：当系统中有多个并发执行的程序时，各个资源是他们所共享的，这些资源的状态也由这些程序所改变，所以一个程序的运行环境会受到其他程序的影响。

(3)不可再现性：程序在并发执行时，由于失去了封闭性，也将导致其有失去可再现性。

3.进程的特征与三种基本状态

特征：

(1)动态性 (2)并发性 (3)独立性 (4)异步性

状态：

(1)就绪状态 (2)执行状态 (3)阻塞状态

三种基本状态转换：

处于就绪状态的进程，在调度程序为之分配了处理机之后便开始执行，就绪 → 执行

正在执行的进程如果因为分配它的时间片已经用完，而被剥夺处理机，执行 → 就绪

如果因为某种原因致使当前的进程受阻，使之不能执行。 执行 → 阻塞

4.进程控制块PCB的作用

(1) 作为进程存在的唯一标志

(2) 能实现间断性运行方式

(3) 提供进程管理所需要的信息

(4) 提供进程调度所需要的信息

5.线程与进程的区别联系

定义：

进程：进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的一个独立单位（包括程序段，相关数据段，进程控制块PCB）。

线程：线程是进程的一个实体，是CPU调度和分派的基本单位，它是比进程更小的能独立运行的基本单位。线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源（如程序计数器，一组寄存器和栈)，但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。

关系：

一个线程可以创建和撤销另一个线程。同一个进程中的多个线程之间可以并发执行。相对进程而言，线程是一个更加接近于执行体的概念，它可以与同进程中额度其他线程共享数据，但拥有自己的栈空间，拥有独立的执行序列。

区别：

主要差别在于它们是不同的操作系统资源管理方式。进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其他进程产生影响，而线程只是一个进程中的不同执行路径。线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个线程死掉就等于整个进程死掉，所以多进程的程序要比多线程的程序健壮，但在进程切换时，耗费资源较大，效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作，只能用线程，不能用进程。

优缺点：

线程和进程在使用上各有优缺点：线程执行开销小，但不利于资源的管理和保护；而进程相反。同时，线程适合于在SMP机器上允许，而进程则可以跨机器迁移。

6.进程间的通信是如何实现的？

  早期的的属于低级通信，原因：(1)效率低，生产者每次只能向缓冲池投放一个信息。(2)通信对用户不透明，隐藏了通信的具体细节。现在发展为高级通信：用户可以利用操作系统所提供的一组通信命令传送大量数据。操作系统隐藏了进程通信的实现细节，或者说，通信过程对用户是透明的。

高级通信机制：

1.共享存储器系统

实际操作中对应的是“剪贴板”（剪贴板实际上是系统维护管理的一块内存区域）的通信方式。

2.消息传递系统（进程间的数据交换以消息(message)为单位)

当今最流行的微内核操作系统中，微内核与服务器之间的通信，都采用了消息传递机制

3.管道通信系统（连接读写进程实现他们之间通信的共享文件）

(pipe文件，类似于先进先出的队列，由一个进程写，一个进程读)

管道分为匿名管道、命名管道。匿名管道是未命名的、单向管道，通过父进程和一个子进程之间传输数据。匿名管道只能实现本地机器上两个进程之间的通信，不能实现跨网络的通信。命名管道不仅可以在本机上实现两个进程间的通信，还可以跨网络实现进程间的通信。

4.客户机-服务器系统

包括：套接字（socket），远程过程调用和远程方法调用。

7.什么是临界区？如何解决冲突？

每个进程中访问临界资源的那段程序成为临界区，每次只准许一个进程进入临界区，进入后不允许其他进程进入。

(1)如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入；

(2)任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其他所有试图进入临界区的进程必须等待；

(3)进入临界区的进程要在有限的时间内推出，以便其他进程能及时进入自己的临界区。

(4)如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。

8.进程同步原则

  进程同步的主要任务：是对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。同步机制遵循的原则：

(1) 空闲让进

(2) 忙则等待（保证对临界区的互斥访问）

(3) 有限等待（避免死等）

(4) 让权等待（当进程不能进入自己的临界区时，应该释放处理机，以免陷入忙等状态）

9.进程同步

  由于进程同步产生了一系列经典的同步问题“生产者-消费者”问题，“哲学家进餐”问题，“读者-写者”问题。

解决方法：

(1)整型信号量

(2)记录型信号量，针对多个并发进程仅共享一个临界资源的情况。

(3)AND信号量，针对一个进程需要获得两个或更多的共享资源后才能执行其任务。

(4)管程

P(S)：请求资源，V(S)：释放资源。

10.程序和进程的区别

程序：计算机指令的集合，它以文件的形式存储在磁盘上。程序是静态实体，在多道程序系统中，它是不能独立运行的，更不能与其他程序并发执行。

使用系统资源情况：不使用（程序不能申请系统资源，不能被系统调度，也不能作为独立运行的单位，它不占用系统的运行资源）。

进程：进程是进程实体（包括：程序段、相关的数据段、进制控制块PCB）的运行过程，是一个程序在其自身的地址空间中的一次执行活动。是系统进行资源分配和调度的一个独立单位。

使用系统资源情况：使用（进程是资源申请、调度和独立运行的单位，因此，它使用系统中的运行资源）。

三、处理机调度与死锁

1.处理机调度的层次

(1) 高级调整

主要用于多道批处理系统中，又称长作业调度，调度对象是作业，根据某种算法决定将后备队列中的哪个作业调入内存。

(2) 低级调度

操作系统中最基本的一种调度方式（频率最高），其所调度的对象是进程(或内核级线程)。主要功能是，根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给选中的进程。在多道批处理、分时和实时三种类型的OS中都存在，又称为短作业调度。

(3) 中级调度

又称为内存调度，目的是为了提高内存利用率和系统吞吐率。

2.作业调度的算法

(1) 先来先服务算法（FCFS）

最简单额度调度算法，既可以用于作业调度，也可用于进程调度，系统按照作业到达的先后顺序进行调度，或者是优先考虑在系统中等待时间最长的作业

(2) 短作业优先调度算法（SJF）

实际情况短作业占有比例很大，为了使他们比长作业优先执行，而产生了短作业优先的调度算法，作业越短优先级越高，缺点是必须知道作业的运行时间，对长作业不利，人机无法实现交互，未完全考虑作业的紧迫程度。

(3) 优先级调度算法（PSA）

优先级：

对于先来先服务算法，作业的等待时间就是他的优先级，等待时间越长优先级越高。

对于短作业优先算法，作业时间的长短就是它的优先级。

在优先级算法中，基于作业的紧迫程度。

(4) 高响应比优先调度算法（HRRN）

在FSFS中只是考虑作业的等待时间而忽略作业的运行时间，SJF算法正好相反。高响应比算法既考虑作业的等待时间，又考虑作业的运行时间。

优先权 = （等待时间 + 要求服务时间）/ 要求服务时间

由于等待时间与服务时间之和就是作业的响应时间，顾优先级相当于响应比：Rp

Rp = （等待时间 + 要求服务时间）/ 要求服务时间 = 响应时间 / 要求服务时间

3.什么是死锁，死锁产生的4个条件

死锁定义：

在两个或多个并发进程中，如果每个进程持有某种资源而又都等待别的进程释放它或它们现在保持着的资源，在未改变这种状态之前都不能向前推进，称这一组进程产生了死锁。通俗的讲，就是两个或多个进程被无限期地阻塞、相互等待的一种状态。

产生死锁的必要条件(缺一不可)：

(1) 互斥条件 一个资源一次只能被一个进程调用。

(2) 请求保持条件 一个进程因请求资源而阻塞时，对已经获得资源保持不放。

(3) 不可抢占条件 进程已获得的资源在未使用完之前不能被抢占。

(4) 循环等待条件 若干进程之间形成一种头尾相接的循环等待资源的关系。

4.预防避免死锁的方法

(1) 破坏”互斥”条件

所有进程可以同时访问共享资源。但由于互斥条件是非共享设备所必须的，不仅不能改变，还应加以保证。

(2) 破坏”请求和保持”条件

规定所有进程在开始运行之前，都必须一次性的申请其在整个运行过程所需要的全部资源。

优点：简单，安全。 缺点：资源严重浪费，恶化了系统的利用率。

(3) 破坏“不剥夺“条件

进程逐个的提出资源请求，当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源，待以后需要时再重新申请。

缺点：实现复杂，代价大，反复地申请和释放资源，而使进程的执行无限的推迟、延长了进程的周转时间，增加系统开销，降低系统吞吐量。

(4) 破坏”环路等待”条件

将所有的资源按类型进行线性排队，并赋予不同的序号。所有进程请求资源必须按照资源递增的次序提出，防止出现环路。

缺点：1.序号必须相对稳定，限制了新设备类型的增加。2.作业（进程）使用资源顺序和系统规定的顺序不同而造成资源浪费。3.限制了用户编程。

算法：利用银行家算法避免死锁

Available，可利用资源 ，表示一类可利用的资源数目。

Max，最大需求矩阵，表示进程i需要Rj类资源的最大数目。

Allocation，分配矩阵，表示进程i当前已分的Rj类资源的数目。

Need，需求矩阵，表示进程i还需要Rj类资源K个方能完成任务。

Work，工作向量，表示系统可提供给进程继续运行所需的各类资源数目。

5.死锁的检测和解除

(1)死锁的检测

①资源分配图：

圆圈代表一个进程，方框代表一类资源。

资源请求边由进程P指向资源R；资源分配便由资源R指向进程P。

②死锁原理

S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。

③死锁中的数据结构

(2)死锁的解除

①抢占资源：从一个或多个进程中抢占足够数量的资源，分配给死锁进程，以解除死锁状态。

②终止进程：终止系统中的一个或多个死锁进程，直至打破循环环路，使系统从死锁状态解脱出来。

四、存储器管理

1.存储器的多层结构

最高层为CPU寄存器，紧接着三层为主存，最底两层是辅存。

2.程序的装入和链接

用户程序要在系统中运行，必须先将它装入内存，然后再将其转变为一个可以执行的程序，通常都要经过以下几个步骤：

(1)编译，由编译程序(Compiler)对用户源程序进行编译，形成若干个目标模块（Object Module）。

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

(3)装入，由装入程序（Loader）将装入模块装入内存。

3.连续分配存储管理方式

(1) 单一连续分配

(2) 固定分区分配

(3) 动态分区分配

(4)动态可重定位分区分配算法

其中动态分区分配将涉及到分区分配中实际需要的数据结构，分区分配算法和分区的分配与回收操作。

回收操作包括，三中合并以及一种插入。

内存分配流程：

4.动态分区分配算法

(1) 首次适应算法（FF）

要求地址空间递增的顺序链接，在分配内存时从链首开始查找，直到有一个满足的空间为止。该算法优先利用内存中低址空间，保留了高址空间，缺点是低址部分不断被划分，留下许多内存碎片。

(2) 循环首次适应算法（NF）

为了防止留下碎片，减少低址空间开销，NF算法每次从上一次分配的地方继续分配，该算法需要一个起始查询的指针用于指示下一次查询的空间地址。缺点是：缺乏大的空间分区。

(3) 最佳适应算法（BF）

每次作业分配时，总是把满足要求，又是最小的空间分配给作业，该算法把空间分区按其容量大小从小到大排列成空闲区链，缺点是：留下许多内存碎片。

(4) 最坏适应算法（WF）

总是挑选最大的空闲区域分配给作业使用，优点是不至于使空间区间太小，产生碎片的可能性小，缺点是：缺乏大的空间分区。

5.动态可重定位分区分配

(1)紧凑

通过移动内存中作业的位置，把原来多个分散的小分区拼接成一个大分区的方法。

缺点：需要对移动了的程序或数据进行重定位。

(2)动态重定位

当系统对内存进行了“紧凑”，而使若干程序从内存的某处移至另一处时，不需对程序做任何修改，只要用该程序在内存的新起始地址去置换原来的起始地址即可。这一过程需要硬件支持——重定位寄存器。

6..对换

是指把内存中暂时不能运行的进程或者暂时不用的程序和数据换出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据换入内存。

对换是改善内存利用率的有效措施，它可以直接提高处理机的利用率和系统的吞吐量。

类型：

①整体对换：进程对换，在中级调度中以整个进程为单位。

需要系统实现三方面功能：对对换空间的管理、进程的换出和进程的换入

②页面(分段)对换。

7.分页存储管理方式

分页存储的基本方法：

(1) 页面和物理块

页面：分页存储管理将进程的逻辑地址空间分成若干页，并从0开始编号，把内存的物理地址分成若干块（物理块）

(2) 地址结构

前一部分为也好P，后一部分为位(偏)移量W，对于特定的机器，其地址结构一定。给定逻辑地址A，页面的大小为L，则页面P和页内地址D有以下关系： P=INT[A/L]; d=[A] MOD L ，INT是整除函数。

例如：页面大小1kb ，设A=2170B，得P=2,d=122。

物理地址=（P=2对应的物理块地址)*1024B+122B

(3) 页表

记录相应页在内存中对应的物理块号

(4) 地址转换机构

将用户逻辑空间的地址，转变为空间中的物理地址。

8.分段存储管理方式

分段管理方式的引入原因：

(1) 一般程序分为若干段，如：主程序段、数据段、栈段等，每个段大多试一个相对独立的单位。

(2) 实现满足信息共享、信息保护、动态链接、以及信息动态增长等需要。

9.分页和分段的区别

共同点：二者都采用离散分配方式，且都地址映射机构来实现地址的转换

不同点：

(1) 页是信息的物理单位。采用分页存储管理方式是为了实现离散分配方法。提高内存的利用率，采用分段目的主要在于能更好的满足用户的需求。

(2) 页的大小固定且有由系统决定，在采用分页存储管理方式中直接由硬件实现。而段的大小不固定，决定于用户所填写的程序

(3) 分页的用户程序地址空间是一维的。分页完全是系统的行为，分段系统中是二维的。

10.段页式存储管理方式

基本原理是分段和分页相结合，其地址结构由：段号、段内页号、页内地址三部分组成。在段页式系统中获得一条指令需要三次访问内存，第一次访问内存中的短标，第二次访问内存中的页表，第三次访问内存中的数据。

11.Windows下的内存是如何管理的？

Windows提供了3中方法来进行内存管理：

(1) 虚拟内存，最适合用来管理大型对象或者结构数组；

(2) 内存映射文件，最适合用来管理大型数据流（通常来自文件）以及单个计算机上运行多个进程之间共享数据；

(3) 内存堆栈，最适合用来管理大量的小对象

Windows操作内存可以分两个层面：物理内存和虚拟内存。

其中物理内存由系统管理，不允许应用程序直接访问。

五、虚拟存储器

1.操作系统的内容分为几块？为什么叫做虚拟内存？他和主机的关系如何？内存管理属于操作系统的内容吗？

操作系统的主要组成部分：进程和线程的管理，存储管理，设备管理，文件管理。虚拟内存是一些系统页文件，存放在磁盘上，每个系统页文件大小为4K，物理内存也被分页每个页大小也为4k，这样虚拟页文件和物理内存也就可以对应，实际上虚拟内存就是用于物理内存的临时存放的磁盘空间。页文件就是内存页，物理内存中每页叫物理页，磁盘上的页文件叫虚拟页，物理页+虚拟页就是系统所有使用的页文件的总和。

2.请求分页存储管理方式

请求页面机制：作用是把用户的逻辑地址映射为内存空间中的物理地址。

结构：

状态P：指示页面是否调入内存，供程序访问时参考。

访问字段A：用于记录本页在一段时间内被访问的次数，供换出页面时参考。

修改位M：标识页面调入内存是否被修改过，供置换页面时参考。

外存地址：用于指示该页在外存上指示地址。

内存分配：

最小物理块数：

若采用单地址指令,且采用直接寻址，需要物理块数是2，一块用于存放指令页面，另一块用于存放数据页面。

若采用间接寻址至少需要3块。

3.虚拟存储器页面置换算法

(1) 最佳置换算法（Optimal）

一种理论的算法，选择淘汰的页面是以后一定不再使用的页面（理想化的），该算法无法实现，只能作为其他算法好坏的一个评价对比。

(2) 先进先出算法（FIFO）

总是最先淘汰最先进去的页面，该算法容易实现。缺点：通常程序调入内存的先后顺序和程序执行的先后顺序不一致，导致缺页率高。

(3) 最近最久未使用（LEU）

FIFO算法性能差，LRU算法根据页面调入内存的先后顺序决定，因为违反预测未来的使用情况，就是用过去的使用情况作为将来的使用情况的近似。

(4) 最少使用算法（LFU）

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

六、输入输出系统

1.IO软件的层次结构

(1)用户层IO软件 (2)设备独立性软件 (3)设备驱动程序 (4)中断处理程序 (5)硬件

I/O设备一般是由执行I/O操作的机械部分和执行控制I/O的电子部件组成。通常将这两部分分开，执行I/O操作的机械部分就是一般的I/O设备，而执行控制I/O的电子部件则称为设备控制器或适配器。

设备控制器的主要功能是：控制一个或多个I/O设备，以实现I/O设备和计算机之间的数据交换。

2.对IO设备的控制方式

(1) 使用轮询的可编程方式

CPU不停地检查设备的状态，以字节为单位，非中断方式，利用率低

(2) 使用中断可编程的IO方式

添加CPU中断，提高了CPU的利用率

(3) 直接存储方式

以数据块为单位，放宽响应时间

(4) IO通道的方式

以数据块组成的一组数据块为单位，大幅度提高CPU的利用率

3.设备分配

(1) 设备分配中的数据结构

①设备分配表DCT ②控制器控制表，通道控制表，系统设备控制表

(2) 设备分配需要考虑的因素

①设备的固有属性 ②独占设备的分配策略 ③设备的分配算法 ④设备分配中的安全性

(3) 独占设备的分配程序

4.设备驱驱动程序

设备处理程序又称为设备驱动程序，它是I/O系统的高层与设备控制器之间的通信程序。

设备驱动程序的处理过程：

(1)将抽象要求转换为具体要求。

(2)对服务请求进行校验。

(3)检查设备的状态。

(4)传送必要的参数。

(5)启动I/O设备

5.SpooLing系统的构成

(1) 输入井和输出井

(2) 输入缓冲区和输出缓冲区

(3) 输入进程和输出进程

(4) 井管理程序

6.与设备无关的I/O软件

为了实现与设备的无关性而引入了逻辑设备与物理设备两个概念。逻辑设备表LUT*。

7.缓存区

引入缓冲区的原因：

(1)缓和CPU与I/O设备间速度不匹配的矛盾。

(2)减少对CPU的中断频率，放宽对CPU中断响应时间的限制。

(3)解决数据粒度不匹配的问题。

(4)t提高CPU和I/O设备之间的并行性。

分类：

(1) 单缓冲区，处理时间是：max(c,T) + M

(2) 双缓冲区，处理时间是：max(C+T)

缓冲池：在池中设置了多个可供若干个进程共享的缓冲区。

缓冲池与缓冲区的区别：缓冲区仅仅是一组内存块的链表，而缓冲池则是包含了一个管理的数据结构及一组操作函数的管理机制，用于管理多个缓冲区。

缓冲池组成：空白缓冲队列emq，输入队列inq，输出队列outq。

8.磁盘系统的性能改善

(1)选择好的磁盘调度算法，以减少磁盘的寻道时间。

(2)提高磁盘I/O速度，以提高对文件的访问速度。

(3)采取冗余技术，提高磁盘系统的可靠性。

七、文件管理

1.文件逻辑结构管理

(1) 按文件的有无结构分

① 有结构文件（记录式文件） ② 无结构文件（流式文件）

(2) 按文件组织方式分

① 顺序文件 ② 索引文件 ③ 索引顺序文件

八、磁盘存储器管理

1.外存的组织方式

(1) 连续组织方式

又称为连续分配方式，要求每一个文件分配一个相邻的盘块

优点：顺序访问容易，访问连续文件非常容易，访问速度非常快

缺点：要求为文件分配连续的空间，必须事先知道文件的长度，不能灵活的删除插入记录动态增长的文件难分配空间

(2) 链接组织方式（分为隐式链接和显示链接）

采用链接组织的方式可以为文件分配多个不连续的盘块。

优点：①消除磁盘的外部碎片，提高内存的利用率。

②对插入删除修改非常容易。

③可以适应文件的动态增长。

(3)索引组织方式

分为单索引和多索引组织方式。