系统架构设计师重要知识点集-操作系统

重点1：进程管理

要点1：进程的状态

1、进程至少具有就绪、运行、阻塞三种状态，即称三态模型。进程的状态会随着自身的推进或外界条件的变化而变化。

（1）就绪状态是指进程已被分配了除CPU以外的全部资源，在获得CPU之后能立刻执行的状态；在一个系统中，可以有多个进程同时处于就绪状态，通常称为就绪队列。

（2）运行状态是指进程已经获得CPU，正在执行。

（3）阻塞状态是指进程因发生某件事（如请求I/O、申请缓冲空间等）而暂停执行时的状态，即进程的执行受到了阻塞；通常把它们排成一列，称为阻塞队列。

注意：任何一个结束阻塞的进程必须先变成就绪状态，待分配到处理器后才能运行。

2、在三态模型的基础上，引入挂起状态，则可衍生为五态模型，即运行、静止就绪、活跃就绪、静止阻塞、活跃阻塞五种状态。

原来处于就绪状态的进程，由于时间片用完等因素正常退出后，就进入静止就绪状态，等待下次进入活跃就绪状态；原来处于阻塞状态的进程，在还未退出阻塞原因之前，就进入静止阻塞状态继续完成就绪前准备。

要点2：进程的同步与互斥

1、临界资源指的是一次仅允许一个进程使用的资源，比如，物理设备如打印机、磁带机等，某些软件的变量、数据、表格等。

2、临界区指的是进程访问临界区的那段程序代码。

3、互斥指的是临界资源在某一时刻只被能被一个进程访问，即互斥是进程间资源竞争的关系。

4、同步指的是多个进程可以并发的执行，但它们相互之间需保持一定的制约顺序和速度，即同步是进程间协作的关系。

5、进程之间对于临界区的协调准则为：空闲让进、忙则等待、有限等待、让权等待。在让权等待中，可以使用信号量机制实现进程的同步与互斥。信号量是一个整数，当信号量大于等于0时，代表可供并发进程使用的资源实体数，当信号量小于零时则表示正在等待使用临界区的进程数。

6、信号量的原语操作分为P操作和V操作。原语操作是指在执行期间不能发生中断的原子操作。

（1）PV操作的对象是信号量，根据对信号量的控制来实现进程间的同步与互斥。P操作会将信号量值减1，如果操作前信号量值为负数，那么调用P操作的进程将暂停执行，直到另一个进程对该信号量做V操作；V操作是将信号量值加1，若此时信号量值仍小于零，操作系统会从需要使用该信号量的进程等待队列中唤醒一个进入该临界区。

P(sem) 操作定义：
P(sem)  {
  sem = sem - 1;
  if ( sem < 0 )
    进程进入等待状态;
  else
    继续进行;
}

V(sem) 操作定义：
V(sem)  {
  sem = sem + 1;
  if ( sem ≤ 0 )
    唤醒队列中的一个等待进程;
  else
    继续进行;
}

（2）使用PV操作实现进程的互斥：假设信号量mutex是用于互斥的信号量，初值为1，表示没有并发进程使用该临界区。

P(信号量 S)；
  临界区
V(信号量 S)；

（3）使用PV操作实现进程的同步：首先为各并发进程设置私有信号量，然后为私有信号量赋初值，最后利用 P、V原语和私用信号量定义各进程的执行顺序。

最简单的同步控制是进程A在另一个进程B到达L2以前，不应前进到超过点L1。要确保进程B执行V操作之前，不让进程A的运行超过L1，就要设置信号量S的初值为0，这样，如果进程A先执行到L1，那么执行P操作（S=S-1）后，则S<0，就停止执行，让其进入阻塞状态，直到进程B执行到L2时，再执行V操作（S=S+1），唤醒进程A让其继续执行 。

7、生产者-消费者

生产者－消费者是经典的同步问题，其要求存后再取，取后再存，即存在两个制约关系，即缓存区如果满了，就停止生产；而缓存区如果空了，则停止消费。

生产者-消费者问题不仅要解决生产者进程与消费者进程的同步关系，还要处理缓冲区的互斥关系，因此需要3个信号量来实现：

注意，如果对缓冲区的读写不进行互斥控制的话，那么就不需要互斥信号量mutex。假设我们只对生产者与消费者进行同步控制，那么程序如下：

生产者程序：
loop
  生产一个物品;
  P(empty);   // 空闲的缓冲区数量-1
  物品存入缓冲区;
  V(full);  // 填充的缓冲区数量 + 1
endloop

消费者程序：
Loop
  P(full);  // 填充的缓冲区数量-1
  从缓冲区中取出物品;
  V(empty);  // 空闲的缓冲区数量+1
  使用它;
endloop

在资源使用之前，会使用P操作，表示占用资源；在资源使用完之后，会使用V操作，表示释放资源。

在互斥关系中，PV操作是在一个进程中成对出现的；而在同步关系中，PV操作是在两个进程甚至是多个进程中成对出现的。

要点3：死锁问题

1、死锁就是多个进程因争夺资源而造成的循环等待状态。

2、产生死锁的主要原因是共享资源不足、资源分配策略和进程的推进顺序不当，系统资源既可能是可重复使用的永久性资源，也可能是消耗性的临时资源。

3、产生死锁的必要条件是：互斥条件、保持和等待条件、不剥夺条件和环路等待条件：

（1）互斥条件：即一个资源每次只能被一个进程使用；

（2）保持与等待条件：有一个进程已获得了某些资源，但因请求其他资源而被阻塞时，又对所获得的资源保持不放；

（3）不可抢占条件：有些系统资源是不可抢占的，当某个进程已获得这种资源后系统不能强行收回，只能由进程使用完资源后自己释放；

（4）循环等待条件：若干个进程形成环形链，每个都占用对方要申请的下一个资源。

4、解决死锁的策略为：

（1）死锁预防：破坏导致死锁必要条件中的任意一个就可以预防死锁；

（2）死锁避免：指进程在每次申请资源时判断这些操作是否安全；

（3）死锁检测：死锁预防和避免都是事前措施，而死锁的检测则是判断系统是否处于死锁状态，如果是，则执行死锁解除策略；

（4）死锁解除：将进程所拥有的资源强行回收，分配给其他的进程。

实际上，系统出现死锁的概率很小，故从系统所花的代价上来看，采用死锁发生后的检测与解除策略要比采用死锁发生前的预防与避免策略代价要小一些，所以，推荐采用死锁发生后的检测与恢复策略。

要点4：进程调度算法

1、引起进程调度的原因有以下几类：

（1）正在执行的进程执行完毕；

（2）执行中的进程自己调用阻塞原语将自己阻塞起来进入睡眠状态；

（3）执行中的进程调用了P原语操作，然后因资源不足而被阻塞；或调用 V原语操作激活了等待资源的进程队列；

（4）在分时系统中，当一个进程用完了一个CPU时间片；

（5）就绪队列中某个进程的优先级变得高于当前执行进程的优先级，也将引起进程调度。

2、对于不同的系统与目标，会采取不同的进程调度算法：

（1）先来先服务（First Come and First Server，FCFS）调度算法，又称先进先出（First In and First Out，FIFO）；

（2）优先级调度算法；

（3）轮转算法（Round Robin）：每个进程执行一次占有处理器时间都不能超过规定的时间单位（时间片）；如果超过，则自行释放自己所占有的CPU资源，然后排到就绪队列的末尾，等待下一次调度。

重点2：存储管理

要点1：页式存储管理

1、分页的基本思想

把程序的逻辑空间和内存的物理空间按照同样的大小划分成若干页面，并以页面为单位进行分配；在页式存储管理中，系统中虚地址是一个有序对（页号，位移），系统为每一个进程建立一个页表，其内容包括进程的逻辑页号与物理页号的对应关系、状态等。

2、页式存储管理的优缺点

（1）页式存储管理的优点是利用率高、碎片小、分配及管理简单。

（2）页式存储管理的缺点是增加了系统开销，可能产生抖动现象。

3、页式存储管理的过程

当进程运行时，其页表的首地址已在系统的动态地址转换机构中的基本地址寄存器中，执行的指令访问虚存地址（p，d）时，首先根据页号p查页表，由状态可知，这个页是否已经调入内存，若已调入内存，则得到该页的内存位置p2，然后，与页内相对位移d组合，得到物理地址r，如果该页尚未调入内存，则产生缺页中断，以装入所需的页，如图所示。

当内存中无空闲块时，为了装入一个页面而必须按某种算法从已在内存的页中选择一页，将它暂时调出内存，让出内存空间以存放所需装入的页面，这个工作称为“页面调度”。

4、抖动现象：刚被调出的页面又立即要用，因而又要把它装入。

5、页面置换算法

一个好的调度算法应减少或避免抖动现象，常用的有：

（1）最优（OPT）算法：选择不再使用或最远的将来才被使用的页，这是理想的算法，但是难以实现。

（2）随机（RAND）算法：随机地选择需要被淘汰的页，开销小，但是可能选中立即就要访问的页

（3）先进先出（FIFO）算法：调出在内存驻留时间最长的页，但可能淘汰掉频繁使用的页；该算法简单，易实现，可以把装入内存的那些页的页号按进入的先后顺序排成队列，每次总是调出队首的页，当装入一个新页后，把新页的页号排到队尾；

（4）最近最少使用（Least Recently Used， LRU）算法：选择离当前时间最近的一段时间内使用得最少的页，这个算法的主要理论依据是，如果某个页被访问了，则它可能马上就要被访问；反之，如果某个页长时间未被访问，则它在最近一段时间也不会被访问（即局部性原理）。

要点2：段式存储管理

1、分段的基本思想

分段的基本思想是把用户作业按逻辑上有完整意义的段来进行划分，并以段为单位作为内外存交换的空间尺度。

分段系统中虚地址是一个有序对（段号，位移），系统为每个作业建立一个段表，其内容包括段号、段长、内存起始地址和状态等。

2、段式存储管理的过程

进程执行时，其段表的首地址已在基本地址寄存器中，执行的指令访问虚存（s，d）（取指令或取操作数）时，首先根据段号s查段表，若段已经调入内存，则得到该段的内存起始地址，然后与段内相对地址（段内偏移量d）相加，得到实际地址。如果该段尚未调入内存，则产生缺段中断，以装入所需要的段。

3、段式存储管理的优缺点

（1）段式存储管理的优点是多道程序共享内存，各段程序修改互不影响。

（2）段式存储管理的缺点是内存利用率低，内存碎片浪费大。

要点3：段页式存储管理

1、段页式存储管理的组成

段页式管理是段式和页式两种管理方法结合的产物，综合了段式组织与页式组织的特点，根据程序模块分段，段内再分页，内存被分划成定长的页；段页式系统中虚地址形式是（段号、页号、页内偏移），如图所示；系统为每个进程建立一个段表，为每个段建立一个页表，段页式管理采用段式分配、页式使用的方法，便于动态连接和存储的动态分配，这种存储管理能提高内存空间的利用率。

2、段页式存储管理的过程

段页式虚拟存储管理为每一个装入内存的作业建立一张段表，还要为每一段建立页表，段表中指出该段的页表存放位置及长度，页表中应指出该段的各页在磁盘上的位置以及页是否在内存中，若在内存中，则填上占用的内存块号，作业执行时按段号查段表，找到相应的页表再根据页号查页表，由标志位判定该页是否已在内存，若是，则进行地址转换；否则进行页面调度。

段页式虚拟存储管理结合了段式和页式的优点，但增加了设置表格（段表、页表）和查表等开销，段页式虚拟存储器一般只在大型计算机系统中使用。

要点4：快表

快表是一块小容量的相联存储器（Associative Memory），由高速缓存器组成，速度快，并且可以从硬件上保证按内容并行查找，一般用来存放当前访问最频繁的少数活动页面的页号。

快表是将页表存于Cache上，慢表将页表存于内存上。

重点3：文件管理

要点1：文件的物理结构

文件的存储设备通常划分为大小相同的物理块（通常单位为byte），物理块是分配和传输信息的基本单位。

1、常用的物理块分配策略有：

（1）顺序分配（连续分配）：存取速度快，不能动态调整长度，不宜用于需要经常修改的文件。

（2）链接分配（串联分配）：优点是可以解决存储器的碎片问题，提高存储空间利用率，由于链接文件只能按照队列中的链接指针顺序查找，因此搜索效率低，一般只适用于顺序访问，不适用于随机存取。

（3）索引分配：一般采用多级（间接索引）技术，这时在由索引表指出的物理块中存放的不是文件存放处而是存放文件信息的物理块地址；如果一个物理块能够存储n个地址，则一级间接索引，将可寻址的文件长度变为n的二次方块，对于更大的文件可以采用二级甚至三级间接索引。

在存取文件时需要访问两次磁盘，一次是访问索引表，另一次是根据索引表提供的物理块号访问文件信息。

重点4：设备管理

要点1：数据传输控制方式

1、程序控制（查询）方式：分为无条件传送和程序查询方式两种；此方法简单，硬件开销小，但I/O能力不高，严重影响CPU的利用率。

2、程序中断方式：与程序控制方式相比，中断方式因为CPU无需等待而提高了传输请求的响应速度。

3、DMA方式：是为了在主存与外设之间实现高速、批量数据交换而设置的；DMA方式比程序控制方式与中断方式都高效。

4、通道方式

5、I/O处理机

要点2：虚设备与SPOOLING技术

重点5：微内核操作系统

重点6：嵌入式操作系统

1、嵌入式操作系统的特点：微型化、代码质量高、专业化、实时性强、可裁减、可配置。

2、实施嵌入式操作系统的内核服务有：异常和中断、计数器、I/O管理。

3、常见的嵌入式RTOS（实时操作系统）VxWorks、RT-Linux、QNX、pSOS。