在准备软件评测师考试，借此给知识点进行整理汇总。

操作系统定义与分类

操作系统的定义：操作系统(OS)直接控制和管理计算机硬件和软件资源，合理的对各类作业进行调度，以方便用户使用的进程集合。

操作系统的基本类型：批处理操作系统、实时操作系统、分时操作系统、网络式操作系统和分布式操作系统。

操作系统功能分类：处理机管理、存储管理、文件管理、设备管理和作业管理。

处理机管理

进程管理是操作系统部分的核心内容，是历年考试的重点。主要偏重于进程的同步与互斥、信号量和P-V操作、进程的基本概念、管程以及线程。

1. 什么是进程

进程是可以与其他程序并发执行的段程序的一次执行过程，是系统进行资源分配和调度的基本单位。进程是一个程序关于某个数据集的一次运行。也就是说，进程是运行中的程序，是程序的一次运行活动。进程是动态概念，而程序是静态概念，是指令的集合，因此，进程具有并发性和动态性。

进程实体是由程序块、进程控制块(PCB)、数据块3部分组成。

程序块：描述该进程所要完成的任务

数据块：包括程序在执行时所需要的数据和工作区

进程控制块：包括该进程的描述信息、控制信息、资源管理信息和CPU现场保护信息，反映了进程的动态特征

进程控制块(PCB)是进程存在的唯一标识，描述了进程的基本情况。

考题：

（1）进程是操作系统的一个重要概念。进程是一个具有一定独立功能的程序在某个数据集合上的一次 _____ 。

（2）进程是一个 _____ 的概念，而程序是一个 _____ 的概念。

（3） _____ 是操作系统中可以并行工作的基本单位，也是核心调度及资源分配的最小单位，它由 _____ 组成，它与程序最主要的区别之一是 _____ 。（最后一个空格：他有状态而程序没有）

2. 进程的状态转换

就绪状态：指进程分配到除了处理机以外的必需的资源(已经具备执行条件)的状态。进程创建后处于就绪状态，处于就绪状态可以有多个。

执行状态：指进程占有处理机在CPU上执行的状态。在单CPU系统中，每一时刻只有一个进程处于执行状态。

阻塞状态：指进程因等待某个事件的发生而放弃处理机进入等待状态。系统中处于这种状态的进程可以有多个。

在现代操作系统中还有挂起状态

引起挂起状态的原因：

  • 终端用户的请求（比如我们编写代码之后的调试编译）
  • 父进程的请求
  • 负调节的作用
  • 操作系统的需要

为什么需要引入挂起状态？

我的理解：是内存容量太小，放不下所以的进程，因此将一些处于内存中的就绪状态和堵塞状态转到外存去变成挂起就绪状态和挂起堵塞状态，以此来缓解内存压力。

考题：

（1）进程的最基本状态有 _____ 。在一个单处理机中，若有6个用户进程，在非管态的某一时刻，处于就绪状态的用户进程最多有 _____ 个。（最后一个空格：5）

注：

非管态：用户进程处于执行状态

因为是单处理机，所以处于执行状态的进程至少且最多只有一个，so就绪状态的进程最多为进程总数-1；最少为0个，其他都处于阻塞状态。

3. 进程的创建过程

  • 申请空白的进程控制块(PCB)
  • 为新的过程分配资源
  • 初始化PCB
  • 将新进程插入就绪队列

4. 进程的临界资源

临界资源：一次只能供一个进程访问的资源

临界区：把不允许多个并发进程交叉执行的一个程序称为临界区(进程中访问临界资源的那段代码)

5. 进程的同步与互斥

（1）同步与互斥的定义

进程同步：是进程之间直接的制约关系，是为完成某种任务而建立的两个或多个线程。也就是说，进程之间是异步的，同步即是使各个进程按照一定的制约顺序和速度执行。

同步机制应该遵循的规则：

  • 空闲让进
  • 忙则等待
  • 有限等待(不能让其死等）
  • 让权等待(当进程不能进入临界区时应该立即释放处理机，防止等待时仍占用CPU资源)

进程互斥：是进程之间间接制约关系，互斥是要保证临界资源在某一时刻只被一个进程访问。也就是说，两个进程不能同时进入同一个临界区。

注：

解决进程同步与互斥的方法主要有：加锁法、信号量机制、管程机制等。

（2）什么是信号量？

信号量是OS提供的管理公有资源的有效手段。

信号量(S)代表可用资源实体的数量。

记录型信号量：引入整形变量value(代表资源数目)、进程链表L(链接所有等待进程）

（3）P-V操作

P操作：

  • 申请资源，减量操作，S.value:=S.value-1
  • 当S.value<0时，表示资源分配完，进行自我阻塞

代码：

1
2
3
4
5
6
wait(S)
  begin
  	S.value:=S.value-1;
  	if S.value<0 then
  		block(S,L)
  end

V操作：

  • 释放资源，增量操作，S.value:=S.value+1
  • 当S.value>0时,唤醒S.L链表中等待的进程

代码：

1
2
3
4
5
6
signal(S)
  begin
  	S.value:=S.value+1;
  	if S.value<=0 then
  		wakeup(S,L)
  end

注：

value>0,代表可用资源的数量

value<0,代表由于申请资源而阻塞的进程数

信号量是由一个整形变量和一个等待队列构成，对这个整形变量除了初始化以外就只能实施P-V操作。其中P-V操作是属于低级的进程通信原语。

采用P-V操作实现进程同步的步骤：

  • 各并发进程设置私用信号量
  • 为私用信号量赋初值
  • 利用P-V原语和私用信号量规定各进程的执行顺序

经典同步问题的例子：生产者-消费者的问题：

这要求存后再取，取后再存，即有两个制约关系。为此需要两个信号量，记Bufempty=1，Buffull=0。

生产者：

1
2
3
4
5
6
loop
生产一个产品next
P(Bufempty);
next产品存入缓存区;
V(Buffull);
endloop

消费者：

1
2
3
4
5
6
loop
P(Buffull);
从缓存区中取出next产品;
V(Bufempty);
使用产品
endloop

采用P-V操作实现进程互斥的步骤：

  • 为临界资源设置共用信号量
  • 为公用信号量赋初值
  • 利用P-V原语和公用信号量实现并发进程的互斥，使用临界资源

信号量mutex表示的是互斥信号量，初值为1，表示没有并发进程使用该临界值。

1
2
3
P(mutex)
临界区
V(mutex）

考题：

（1）在某个超市里有一个收银员，且同时最多允许n个顾客购物，我们可以将顾客和收银员看成是两类不同的进程，且工作如下图所示。为了利用P-V操作正确地协调这两类进程之间的工作，设置了3个信号量S1，S2和Sn，且初值分别为0，0，n。这样图中的a应填写 _____ ,图中的b1、b2应分别填写 _____ ,图中的c1、c2应分别填写 _____ 。

超市购物流程图

（2）若有一个仓库，可以存放P1,P2两种产品，但是每次只能存放一种产品。要求：w=P1的数量-P2的数量； -i<w<k (i,k为正整数）。若用P-V操作实现P1和P2产品的入库过程，至少需要 _____ （答案：2）个同步信号量和 _____ (答案：1)个互斥信号量，其中，同步信号量的初值分别为 _____ (答案：i-1，k-1),互斥信号量的初值分别为 _____ (答案：1)。

注：

P1，P2两个产品同时竞争一个仓库

so，Sp1表示存放产品P1， Sp2表示存放产品P2

只有一个仓库，因此只需一个初值为1的互斥信号量mutex

管程

管程：一种新的同步机制，它是由过程、变量以及数据结构等组成的集合。它把分散在各个进程中互斥访问公共变量的那些临界区集中起来，统一管理。

管程实现了进程之间的互斥，使临界区互斥实现了自动化，它比信号量更容易保证并发进程的正确性。

考题：

在操作系统中。管程由管程名、局部变量与管程变量说明、使用共享资源并在数据结构上进行操作的若干过程,以及对变量赋初值的语句等4个基本部分组成，一个管程管理一个临界资源。任何一个进程请求使用某临界资源时，对于其他相关进程而言必须互斥的进入管程。其方法是通过调用特定的管程入口才能进入管程，然后通过管程中使用临界资源的一个过程使用临界资源。在执行中发现共享临界资源被告或条件不成立时，调用管程的进程必须等待使用临界资源的另一进城来欢喜。为了表示不同的等待原因，设置了条件变量，条件变量是与普通变量不同的变量，条件变量不能取任何值，只是一个排队栈。

线程

线程是进程中的一个实体，是系统实施调度的独立单位。

考题：

（1）在SMP系统中，操作系统还提供了 _____ 机制，它是 _____ 的最小单位。（线程，处理器分配）

注：

SMP：多处理器系统

在多线程系统中，一个进程可以由一个或多个线程构成，进程是资源分配的基本单位，而线程是处理器分配的最小单位。

进程调度和死锁

（1）进程调度的两个基本方式

  1. 非剥夺方式：分派程序一旦把处理机分配给某个进程后则使其一直运行下去，知道进程完成或发生某事件而堵塞时才把处理机给另一个进程。
  2. 剥夺方式：当一个进程正在运行时，系统可以基于某种原则剥夺已为其分配的处理机，并且分配给其他进程。剥夺原则有优先权原则、短进程优先原则以及时间片原则等。

衡量进程调度性能的指标一是周转时间,即从提交开始到完成为止的时间间隔；二是响应时间，即从提交一个请求到首次产生响应的时间间隔。

（2）进程调度算法

  1. 先进先出算法（FIFO)

    该算法总是把处理机分配给最先进入就绪队列的进程，一旦进程分到处理机，就会一直执行下去，知道该进程完成或阻塞时才会释放处理机。

  2. 优先数调度算法（SCBF)

    可分为静态优先级和动态优先级，静态优先级是指进程的优先级在进程开始执行前确定，执行过程中不变；动态优先级则可以在进程执行过程中改变。

  3. 时间片转轮法

    分时系统中通常采用时间片转轮法。系统吧所有就绪进程按照FIFO规则排队，按一定的时间间隔把处理机分配给队列中的进程。

考题：

（1）在有一台处理机CPU和两台输出设备IO1和IO2，且能够实现抢先式多任务并行工作的多道程序内，投入运行优先级由高到低P1，P2，P3这3个作业。他们使用设备的先后顺序和占用设备时间分别是：

作业P1：IO2（30毫秒） CPU（10毫秒） IO1（30毫秒） CPU（10毫秒）

作业P2：IO1（20毫秒） CPU（20毫秒） IO2（40毫秒）

作业P3：CPU（30毫秒） IO1（20毫秒）

假设对于其他辅助操作时间可以忽略不计，作业P1，P2
，P3从投入到完成所用的时间分别是 _____ 毫秒， _____ 毫秒和 _____ 毫秒。3个作业从投入运行到全部完成，CPU的利用率为 _____ %，IO1的利用率约为 _____ %。（80,90,90,78,78）

假设在系统中有且仅有3个作业投入运行，各设备的利用率指该设备的使用时间同作业进程全部完成所占用最长时间的比率。

注：

在抢先式多任务系统中，CPU是可抢先的，即任何时刻CPU总是分配给需要CPU的优先级最高的作用。

设备利用率=设备的有效工作时间 / 设备总的运行时间

作业的执行时序图

作业时序图

跟着图画一遍，这中类似的题，就会做了

（3）死锁

死锁是指两个或两个以上进程在执行过程中因争夺资源而造成的一种互相等待的现象。若无外力，则其均无法继续。

例子：进程A锁住了资源1并等待资源2，而进程B锁住了资源2并等待资源1。

产生死锁的原因：

  • 系统资源不足
  • 进程运行推进顺序不合适
  • 资源分配不当

产生死锁的必要条件：

  • 互斥条件（一个资源每次只能被一个进程使用）
  • 请求与等待条件（一个进程因请求资源而阻塞时对已经获得的资源保持不放）
  • 不剥夺条件（进程已经获得的资源，在未使用完之前不能被强行剥夺）
  • 循环等待条件（若干个进程之间形成一种头尾相接的循环等待资源的关系）

考题：
（1）为了解决进程间的同步和互斥问题，通常使用一种称为 _____ 机制的方法。若系统中有5个进程共享若干个资源R，每个进程都需要4个资源，那么使系统不发生死锁的资源R的最少数目是 _____ 。（信号量，3*5+1=16）

（2）因争用资源产生死锁的必要条件是互斥、循环等待、不可抢占和 _____ 。对于缓冲池（大量的缓冲区）的管理采用生产者-消费者方式解决同步与互斥问题时，通常需要 _____ 信号量。（<font color=red

保持和等待，3）

注：

两个私用信号量empty、full和一个公用信号量mutex

一定不会发生死锁：m>n*(w-1)

m表示资源总数

n表示进程总数

w表示每个进程对资源的最大需求

Ending

整理了很久，还是有些是云里雾里的，但是比最初的时候是要好一些，加油，小姑凉。