软件设计师(二)：操作系统基本原理

✅✅作者主页：🔗孙不坚1208的博客
🔥🔥精选专栏：🔗软件设计师（持续更新中）

💞💞觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论💬支持博主🤞
👉👉你的一键三连是我更新的最大动力❤️❤️

操作系统基本原理

1、操作系统概述

2、进程管理

进程：为了能使程序并发执行，并且可以对并发执行的程序加以控制和描述，人们引入了“进程”的概念。

2.1 进程的状态

2.2 前驱图

2.3 进程的同步与互斥

• 互斥的反义词是共享

• 同步的反义词是异步
  
  生产者消费者

• 市场就是互斥的

• 同步就是生产者在市场放入资源会等待消费者把资源拿走后再次放入资源

2.4 PV操作

对于上面的生产者——消费者问题，s1的初值为1、s2的初值为0，我们参照上面的图，假设s1为空区，s2为满区。
①先执行生产者，后执行消费者：首先P（s1），表示生产者生产产品，要在空区中进行，当执行完P（s1），就代表生产了一个产品，此时空区数量减少1，再执行V（s2），满区数量增加1，即此时s1=s1-1=0、s2=s2+1=1。接下来我们如果继续执行生产者操作P（s1），s1=s1-1=-1，此时s1＜0，对于P操作，就要进入等待队列中等候。所以我们此时只能执行消费者操作，首先P（s2），表示消费者消费产品，要在满区中进行，当执行完P（s2），就代表消费了一个产品，此时满区数量减少1，再执行V（s1），空区数量增加1，即此时s2=s2-1=0、s1=s1+1=0。
②先执行消费者，后执行生产者：首先P（s2），表示消费者消费产品，要在满区中进行，s2的初值为0，经过P操作，s2=s2-1=-1，此时s2小于0，无法继续执行下去。换一种思路理解就是，这种情况下，生产者还没有生产任何一个产品，那么消费者自然是无法消费产品的（因为空区的数量为0）。

PV操作练习

答案选 A C
解析：我们来看上面这道题，购书者和收银员两个进程，设置了三个信号量：S1、S2、Sn（初值分别为0、0、n），可以假设有两种情况：①先执行购书者进程，后执行收银员进程（此情况符合大家日常去书店买书的情形），②先执行收银员进程，后执行购书者进程（此情况不太符合常理，如果没有人来书店买书，那收银员去为谁结账呢？？？），所以我们只能采取第一种情况：先执行购书者进程、后执行收银员进程。
首先P（Sn）：Sn=Sn-1，表示有一个购书者进入书店，此时书店最多允许进入的购书者人数就应该减少1；之后购书者可以进行购书，后面进入付款步骤（联系到a1和a2），此时我们想，在购书者没有选择购书付款之前，收银员应该是被阻塞的（通俗的讲：就是坐在那里喝茶，闲着没事干），所以在b1这里需要一个P操作来阻塞它，只有当购书者付款步骤中的a1来到收银员面前结账时，收银员才有事情可做，即a1这里应该是与b1（收银员为购书者结账）相对应的V操作，所以a1：V（S1）、b1：P（S1）。即购书者买书付款→收银员进行结账，购书者不买书或者没有购书者→收银员没事干（阻塞）。
下面我们这样考虑，因为购书者此时在收银员这里等待付款，并不是说购书者直接扔几张100的红票子直接就走人了，而是需要等待收银员把购书者所买书籍一一扫码消磁、计算出总价之后，再由购书者付款，所以在这期间，购书者是在等待（即购书者处于阻塞状态），也就是说a2这里需要一个P操作来阻塞购书者，而b2需要一个V操作与a2相对应，所以a2：P（S2）、b2：V（S2）。即收银员将总价计算好→购书者进行付款，收银员结账过程中→购书者等待（阻塞）。

2.5 PV操作与前驱图

答案：C、A、A

2.6 死锁问题

死锁的预防与避免

2.7 银行家算法

分配资源的原则

对于银行家算法这类问题，其实并不是太难。上面这道题，首先我们需要计算的就是当前系统中还有多少可用的资源，因为三类资源的总数分别为9、8、5，而已经分配给5个进程的三类资源数为：7、7、5，所以此时这三类资源还剩2、1、0。下面的做法其实就是将当前可用的资源数分配给5个进程中的一个，看能否达到它的最大需求量，如果不能，则选择其他进程；如果能，就加上该进程已分配的资源数，运行完释放，此时资源数=已分配给该进程的资源数+当前系统中剩余的资源数。后面是同样的道理，继续分配给其他的进程，能满足最大需求量就分配，直到所有进程都可以顺序运行，就可以找到这样一条安全序列来保证系统不发生死锁。
而下面这种情况，当运行完P2进程，将可用资源数分配给P1进程时，无法达到P1的最大需求量，所以系统无法继续运行下去，就会发生死锁，这就是一个不安全序列！！！

过程：

3、存储管理

3.1 分区存储组织

①首次适应算法：空闲分区以地址递增的次序链接。对于上面这个题，作业4申请内存9k，按照地址递增的情况，此时作业4会被分配到25k的空闲分区，占用9k，剩余25-9=16k。
②循环首次适应算法：与首次适应算法的区别是：不是每次都从链首开始查找，而是从上一次找到的空闲分区的下一个空闲分区开始查找。所以作业4申请9k，而作业2和作业3所在的空闲分区的下一个空闲分区为28k，即作业4被分配到了28k这个空闲分区，占用9k，剩余28-9=19k。
③最佳适应算法：空闲分区按其容量从小到大的顺序链接。作业4申请9k，而当前空闲分区的容量从小到大依次为：10k、25k、28k，所以作业4被分配到10k这个空闲分区，占用9k，剩余10-9=1k。
④最差适应算法：空闲分区按其容量从大到小的顺序链接（与最佳适应算法相反）。作业4被分配到容量最大的空闲分区28k中，占用9k，剩余28-9=19k。

3.2 页式存储

我们来看上面这道例题，首先页面大小为4K=2^12，表示页内地址为12位，所以在对逻辑地址变换的时候，就要保留它的低12位作为物理地址，因为逻辑地址是16进制数5A29H，它的低12为是A29，那么只需要对前面的页号进行变换就可以了，由页表可知，页号5对应的物理块号（页帧号）为6，所以经变换后的物理地址为：6A29H。
第二空，进程P要访问的页面4不在内存，应该淘汰哪个页面？这里我们考虑的是：只能淘汰在内存中的页面，因为如果一个页面压根就不在内存，那你是无法淘汰它的（换句话说，你淘汰它有何意义呢？），所以我们看到状态位是1表示在内存（有页面0、1、2、5），而对于淘汰而言，我们不能淘汰刚刚被访问过的页面，只能淘汰没有被访问过的页面（即访问位为0），查表得，页面1的访问位为0，所以将其淘汰。即第一空选D，第二空选B。

3.3 段式存储

3.4 段页式存储

3.5 快表

3.6 页面置换算法

• 最优（Optimal OPT）算法
• 随机（RAND）算法
• 先进先出(FIFO)算法：有可能产生“抖动”。例如，432143543215序列，用3个页面，比4个缺页要少
• 最近最少使用（LRU）算法：不会抖动
  
  

练习题：

4、文件管理

4.1 索引文件结构

练习题

这道题中，物理块号50对应逻辑块号0，物理块号67对应逻辑块号1，物理块号68对应逻辑块号2，物理块号78对应逻辑块号3，物理块号89对应逻辑块号4，这五个采取的是直接地址索引；而物理块号90和91采取的是一级间接地址索引，90→58对应的是逻辑块号5，所以逻辑块号5对应的物理块号为58。
因为题目中说每个地址项的大小为4字节，而对于一级和二级间接地址索引，每个物理块可以存1024字节的内容，所以在每个一级、二级间接地址索引中，有1024/4=256个地址项。所以在物理块号90中，存放的是从5260（5+256-1）；在物理块号91中，存放的就是从261516（261+256-1），所以逻辑块号261对应的物理块号为187。
观察上图可知，101号物理块显然采取的是二级间接地址索引的方式，所以其中存放的是二级地址索引表。

4.2 文件和树型目录结构

4.3 空闲存储空间的管理

这道例题，首先物理块是从0开始编号的，系统中字长为32位（相当于一个字中包含了32个物理块），那么对于4195号物理块，实际上是第4196个物理块，那么，每个字的长度均为32位，所以4196/32=131.125，表示的是超过第131个字了，要将前131个字都填满，而当前物理块是在第132个字中描述，第一空选D。
第二空问系统应该怎么样？既然要将物理块分配给某文件，必须取值为1（1表示占用），所以排除A和C；我们再来看，前131个字所表示的物理块范围是0131×31：04191，所以第132个字中，第0位置表示4192，第1位置表示4193，第2位置表示4194，第3位置表示4195，所以在第132个字的第3位置对应上了4195号物理块。所以第二空选B。

5、设备管理

5.1 数据传输控制方式

5.2 虚设备与Spooling技术

6、微内核操作系统