软件设计师之操作系统万字大总结（莽起来）

软件设计师之操作系统

• • • 1.概述
    • 2.进程管理
    • • 2.1 进程的状态
      • 2.2 前趋图
      • 2.3 进程的同步与互斥
      • 2.4 PV操作
      • 2.5 死锁
      • 2.6 银行家算法
    • 3. 存储管理
    • • 3.1 分区存储组织
      • 3.2 段页式存储
      • • 3.2.1 页式存储组织
        • 3.2.2 段式存储组织
        • 3.2.3 段页式存储组织
      • 3.3 快表
      • 3.4 页面置换算法
    • 4. 文件管理
    • • 4.1 索引文件结构
      • 4.2 文件和树形目录结构
      • 4.3 空闲存储空间的管理
    • 5. 设备管理
    • • 5.1 数据传输控制方式
      • 5.2 虚设备与SPOOLING技术
    • 6. 微内核操作系统

1.概述

• 管理系统的硬件、软件、数据i资源
• 控制程序运行
• 人机之间的接口
• 应用软件与硬件之间的接口

操作系统具备哪些方面的管理职能：

• 进程管理
  • 进程的状态
  • 前趋图
  • PV操作
  • 死锁问题
• 存储管理
  • 段页式存储
  • 页面置换算法
• 文件管理
  • 索引文件
  • 位示图
• 作业管理
• 设备管理
• 微内核操作系统

2.进程管理

2.1 进程的状态

进程状态是指在操作系统当中对进程进行管理的时候为进程指定的几种状态，以便于给进程分配相应的资源把它管理起来。

• 

2.2 前趋图

哪些任务可以并行，哪些任务有前后关系。

2.3 进程的同步与互斥

• 互斥：在同一时刻，只允许某一个进程使用这个资源。就如：千军万马过独木桥。

  

• 同步：速度上有差异，在一定情况停下等待。

  

• 互斥的反义词是共享；同步的反义词是异步。

• 

2.4 PV操作

• 临界资源：进程间需要互斥方式对其进行共享的资源，如打印机、磁带机等
• 临界区：每个进程中访问临界资源的那段代码称为临界区
• 信号量：是一种特殊的变量

• 在没有加入PV操作时，不管是先进行生产者还是消费者都会出现问题，比如先进行消费者，是没有生产者的，缓冲区里没有东西，就不能消费。

  

  • 加入PV操作后再来看
    • 先进行生产者：这时候s1 = 0，不是<0，进行下面的操作，s2 = 1；之后如果在进行生产者操作，这时候s1 = -1，是<0的，就会被放入进程的等待队列，并将此进程阻塞起来；接下来进行消费者：s2 = 0，继续往下执行，s1 = 0，这个时候就去队列里把阻塞的激活，也就是生产者激活了，这样就能继续执行了。
    • 先进行消费者，此时s2 = -1，是不能继续往下走的。
• PV操作所解决的问题，其实是并发性能之间约束关系的问题的解决
• 例题：

  

  • P(Sn)与V(Sn)这一对信号量就表明最多允许n个购书者进入，因为这个一旦多一个人进来，就会进行阻塞。

  • 

  • V就相当于唤醒，而P就是阻塞，V可以唤醒P。
  • 在进行解题时，假设先进行某个问题，会面临什么问题，怎么使用PV操作进行可以解决这个问题，就是正确答案了。

• 

• 例题：

  

  caa
• 不妨先标一下信号量，遵循从左到右，从上到下。箭头的起点位置时V操作，箭头的终点位置时P操作。

2.5 死锁

死锁：系统当中有一系列的资源，有一系列需要用到这些资源的进程，这些进程需要系统给它分配资源才能够运行。如果说系统在某一时刻发现系统中所有能用的资源都已经分配出去了，而所有的进程都没办法去完成它本身的职责任务，从而释放该有的资源，这就会产生死锁。

• 进程管理时操作系统的核心，但如果设计不当，就会出现死锁的问题。如果一个进程在等待一件不可能发生的事情，则进程就死锁了，而如果一个或多个进程产生死锁，就会造成系统死锁。
• 例：系统有3个进程：A，B，C。这3个进程都需要5个系统资源，系统至少有多少个资源，才不可能发生死锁？
• 公式：至少需要k * （n - 1）+1个资源，其中k为进程数量，n为需要的系统资源量

2.6 银行家算法

死锁有四大条件，这4个条件缺一不可：

• 互斥
• 保持和等待：各个进程会保持自己的资源并且会等待别人释放更多的资源给自己
• 不剥夺：系统不会去把分配给其他进程的资源剥夺掉分配给某个资源
• 环路等待： A等B，B等C，C等A

  • 

• 死锁的预防：打破四大条件
• 死锁的避免：
  • 有序资源分配法
  • 银行家算法

• 银行家算法：分配资源的原则

  分配资源出去的时候要考虑能不能把资源按时收回来，如果仔细评估后发现收不回来，银行家就不会放这笔资源出去。

  • 当一个进程对资源的对打需求量不超过系统中的资源数时可以接纳该进程。
  • 进程可以分期请求资源，但请求的总数不能超过最大需求量
  • 当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源。
• 例题：

  

  • 

  • 也可以通过验证其他选项来进行验证，

    

3. 存储管理

3.1 分区存储组织

某计算机系统的内存大小为128k，采用可变分区分配方式进行内存分配，当前系统的内存分块情况如下图所示，现有作业4申请内存9张，几种不同的的存储分配算法在分配中，会产生什么样的结果呢

• 首次适应法：从上到下，找到能容纳作业的第一个块
• 最佳适应法：从上到下，找到能容纳作业并且留下的空间的最少的块
• 最差适应法：从上到下，找到内存最大的块，就是它
• 循环首次适应法：将剩余的块称为一个循环，比如第一次用25k的内存分块，第二次就用28k的内存分块

3.2 段页式存储

3.2.1 页式存储组织

• 把用户程序分成等分大小的页

• 

  • 页面大小为4k，确定为2 ^ 12，有12位，这是2进制的，转换成16进制，就是需要3位，也就是A29，页号为5对应的页帧号（物理块号）为6，最终敲定答案为6A29H。
  • 状态位为0说明访问的页面不在内存，为1的是在内存中的。然后淘汰的时候就需要看访问位，访问位为1的是不能淘汰的，也就是淘汰页号为1的。

3.2.2 段式存储组织

3.2.3 段页式存储组织

3.3 快表

快表是放在cache中，慢表是放在内存中。

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

3.4 页面置换算法

• 最优（Optimal，OPT）算法
  • 从主存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。
• 随机（RAND）算法
• 先进先出（FIFO）算法：有可能产生“抖动”，例如，432143543215序列，用3个页面，比4个缺页要少。
  • 是最简单的页面置换算法。这种算法的基本思想是：当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰。其理由是：最早调入主存的页面不再被使用的可能性最大。
• 最近最少使用（LRU）算法：不会”抖动“
  • 利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。

• 例题：

• 例题：

  

  AC

  没有使用快表这就表示需要在内存中查一下表，然后在读取

  指令是一次性读入，只产生一次中断；而数据是有两个页，这个是需要两次的

4. 文件管理

4.1 索引文件结构

地址对应盘块，盘块对应内容

• 由上图可知：直接索引是4k * 13 = 54k
• 如果规定0-9前面10个节点为直接索引，一共是4k * 10 = 40k
• 第11个采取一级简介索引：第10个节点指向的物理盘块：一级间接索引是4k * 1024
• 二级间接索引是4k * 1024 * 1024

逻辑块号往往是从0开始算的，一个块中存放的是256个。

4.2 文件和树形目录结构

主要考察的是相对路径和绝对路径的概念。

4.3 空闲存储空间的管理

在磁盘上面会有大量的空间，我们需要把空闲的空间管理起来，以便某一个文件想要申请相应的存储空间的时候能够由依据的相应的分配相应的存储空间。

分为以下几类

• 空闲区表法（空闲文件目录）
  • 我们用一个表来记录哪个表是空闲的的，以便把它管理起来
• 空闲链表法
  • 是把这些空闲区都链起来，链成一条链表，需要进行空间分配的时候，从这条链表上划出相应的空间来

• 位示图法

  画图，1表示的区域已经被占用，0表示的区域表示空闲。

  

• 成组链接法
  • 成组也分链

5. 设备管理

5.1 数据传输控制方式

主要是指的内存和外设之间的数据传输问题，解决这一问题有集中方案。分别是程序控制方式，程序中断方式，DMA方式，通道，输入输出处理机。

• 程序控制方式：这是最低级的方式，也是CPU介入最多的方式，数据的传输控制很多时候都需要CPU的介入。就比如现在问你东西做完了吗？你说没有，很可能过了很长一段时间了再来问做完了吗？你说我老早就完成了
• 程序中断方式：如果外设完成了相应程序的数据的传输发布，这个时候会发一个中断出来，系统就会做下一步的处理。
• DMA：直接存取控制方式。有专门的DMA控制器，只要是外设和内存之间的数据交换，过程之中就由这个控制器去管控，CPU只要在开头的时候做一个介入即可。中间由DMA来。完成之后再由CPU接手

5.2 虚设备与SPOOLING技术

SPOOLING技术：核心在于开辟了缓存区，把输入和输出的数据先缓存起来，这样就解决了外设的低速和内存之间的高速这样的一个差距

6. 微内核操作系统

以上是学习过程中的学习笔记