【软件设计师-从小白到大牛】上午题基础篇：第二章 操作系统

前言

​
本系列文章为观看b站视频以及b站up主@zst_2001系列视频所做的笔记，感谢相关博主的分享。如有侵权，立即删除。
视频链接：视频链接（注：文章中有关图片、以及网友的相关评论与总结等内容未标明出处均出自该视频，感谢大家的分享！）
b站up主页：b站up

章节提要

占比 5-7分
​​​​

一、进程管理

• （注：下图来自前言中up主视频）
  （说明：计算机系统层次结构）

1、进程的状态

1）运行：当一个进程在CPU上运行时，则称该进程处于运行状态。

2）就绪：当一个进程除CPU外其他一切资源全部获得，则称该进程处于就绪状态

3）等待（阻塞或睡眠）：当一个进程除CPU外还缺少其他资源，则称该进程处于等待状态。

（时间片轮转来分配CPU资源，即一个进程从就绪到运行只能运行一个时间片，等时间片到无论任务是否完成均退出运行态转为就绪态，等待下一次调度（时间片轮转））

2、前趋图

前趋图是一个 有向无循环图。
（注：下图来自《软件设计师教程》（第5版）（褚华、霍秋艳主编，清华大学出版社））

3、进程的同步与互斥

1） 同步与互斥不互为“反义词”。同步是合作进程间的直接制约问题，互斥是申请临界资源进程间的间接制约问题。

2）进程的同步：在系统中一些需要相互合作、协同工作的进程。

2）进程的互斥：系统中多个进程因争用临界资源而互斥执行。

4、PV操作

1）临界资源：诸进程间需要互斥方式对其进行共享的资源，如打印机、磁带机等。

2）临界区：每个进程中访问临界资源的那段代码称为临界区。

3）信号量S：是一种特殊的变量。S>=0表示某资源的可用数，若S<0,则其绝对值表示阻塞队列中等待该资源的进程数。

4）P操作定义：S=S-1，若S>=0，则执行P操作的进程继续执行；若 S<0,则置该进程为 阻塞 状态（因为无可用资源），并将其插入阻塞队列。

5）V操作定义：S=S+1，若S>0，则执行V操作的进程继续执行；若 S<=0,则从阻塞状态 唤醒 一个进程，并将其插入就绪队列，然后执行V操作的进程继续。

6）练习题

正确答案：AC
解析：付款后需要有V操作来唤醒收银员的收费操作，即a1为V操作，来唤醒b1相同信号量的P操作（没有人付款收银员的收款操作处于“阻塞”状态，有人付款才唤醒收银员的收费操作）；而购书者付款后，需要等待收银员的收费操作完成，即付款后还需要P操作进行阻塞（a2）,等待收费完成后的V操作进行唤醒（b2）。由此可知a1和b1是相同信号量的V操作和P操作，a2和b2是相同信号量的P操作和V操作。
PV操作解题的核心是找出约束关系（假设先执行某一个进程，然后看会发生什么问题，加入PV操作后可以解决此问题则为正确答案）。

6、PV操作与前趋图

1）例题

正确答案：CAA
解析：（v处理，P等待），将用到的信号量标到线上（从上到下，从左到右）

每条线箭头的起点位置是V操作，箭头的终点位置是P操作.

• （注：下图来自希赛网解析）
  
  （说明：前驱图解题方法）
• 前驱图解题具体方法说明：有几个箭头需要几个信号量（每个箭头信号量按进程编号组成的十进制数从小到大或者直接按上面的方法进行编号），每个进程完成后 （即指出的箭头）需要执行V操作；每个进程开始前（即指入的箭头）需要执行P操作。
  （注：下图来自前言中up主视频）
  
  （说明：共4个箭头，需4个信号量；四个箭头分别是P1->P2、P2->P3、P3->P4、P1->P3。按箭头两端的进程编号组成的十进制数从小到大排序：P1->P2、P1->P3、P2->P3、P3->P4（因为12<13<23<34）。所以依次对四个箭头赋予四个信号量：S1、S2、S3、S4。针对每个箭头对箭头指出端为V操作，箭头指入端为P操作即可）
• PV操作是操作系统提供的具有特定功能的原语。利用PV操作可以 实现资源的互斥使用。
  P操作用来检查资源是否可用；V操作用来释放资源。
• （注：下图来自希赛网）
  
  （说明：进程管理PV操作相关）
• 信号量的取值范围：（资源数-进程数）~ 资源数（常考）
• （注：下图来自前言中up主视频）（了解即可，重点掌握前趋图）
  
  （说明：互斥信号量在一个图中成对出现，而同步信号量在两个图中交叉出现）

7、死锁问题

1）概念：

• （注：下图来自前言中up主视频）
  （说明：发生死锁条件）

2）例题：

正确答案：13
解析：系统不可能发生死锁的最小资源数n：n>=(w-1)*m+1
（m个进程，每个进程需要资源w个）
利用上述可求得n>=(5-1)*3+1=13。

3）银行家算法

-内容：

-例题:

正确答案：B
解析：

进程资源图（补充）

• （注：下图来自前言中up主视频）
  
  
  （说明：处理进程资源图相关问题原则：先分配（资源），再申请（资源）；或者先申请（资源）再分配（资源），从而判断是否能够满足要求，如果可以则为非阻塞结点，不可满足则为阻塞结点。方法：从非阻塞结点开始化简，当非阻塞结点满足条件后释放其申请的资源，对剩余进程继续进行分配/申请。当所有进程均可完成时，称该图是 可化简的）
  （分配：指向P的箭头；申请：P指出的箭头）
  （非阻塞结点：可完成；可化简（存在一种次序，可以使进程完成））
• 当一个进程资源图中所有结点均为阻塞结点时，处于死锁状态。
• 线程可与同属一个进程的其它线程共享进程所拥有的全部资源（注：线程与线程之间是不可见的）。

真题链接

• 在支持多线程的操作系统中，假设进程P创建了若干个线程，那么 该进程中某线程的栈指针 是不能被这些线程共享的。

二、存储管理

1、分区存储组织

（25k空间空出来原因：可能之前分配的作业已经执行完）

2、页式存储组织

• 页面淘汰原则：淘汰在内存中的页号（即状态位为1），优先淘汰访问位为0的页号；若访问位都为1，则优先淘汰修改位为0的页号。（注：淘汰的页号需要在内存中（即淘汰内存中的页号））
• 分页存储管理：页面大小为4k时，地址结构如图：
  （注：下图来自前言中up主视频）
  
  （说明：做题方法：如果逻辑地址为四位十六进制数表示，则 该十六进制数的第一位表示页号，后三位表示页内地址。若要求该逻辑地址转化为的物理地址（ 物理地址=物理块号（页帧号）+页内地址 （该+不是算术加法，是直接将物理块号（页帧号）和页内地址拼接起来就可以），即 求页号对应的物理块号（页帧号）[直接查表]，然后物理块号后面接上页内地址即为物理地址（转换后的物理地址仍然是十六进制））
• 页面大小为多少kb就看其是2的多少次方，这个次方数就是页内地址的位数，逻辑地址/物理地址中，从后往前，去掉页内地址位数个数字，剩下的为页号。（逻辑地址/物理地址转为二进制后，然后再去掉页内地址位数个数字）

1）例题

正确答案：D、B
解析：逻辑地址=页号+页内地址。页面大小4K=2¹²，说明一个页的页内地址是12位（二进制），高于12位的部分为页号（从右往左数），对应的16进制，页内地址就是3位（从右往左数高于3位的为页号），所以页内地址为A29H，页号为5，物理块号（页帧号）为6（查表），物理地址=页帧号+页内地址，所以物理地址为6A29H。页面淘汰原则：1）淘汰访问位为0；2）多个访问位为0，则淘汰修改位为0。所以淘汰1号页。

3、段式存储组织

4、段页式存储组织

• （注：下图来自前言中up主视频）
  
  （说明：分别数有多少位数字（数的位数=大数-小数+1）来表示段号、段内页号或页内地址即可，所求结果即为 2^数的位数分别可代表最多的段数、每个段最大允许的页数、页的大小）

5、快表

（快表放在Cache中，慢表放在内存中）

6、页面置换算法

抖动：刚被换出的页面很快又被访问，需重新调入，导致系统频繁地更换页面，以至于一个进程在运行过程中把大部分时间花费在完成页面置换的工作上。
1）例题

2）例题

正确答案：B、C
解析：没有使用快表说明每读一次程序的块，需要先在内存上来查表，然后读取相应的内存块，所以每一个块需要进行两次内存的访问，总共6个块，所以访问12次内存。默认指令一次性调入（无论占几个块），指令跨页产生一次缺页中断，操作数跨页产生两次缺页中断。 所以产生5次缺页中断。

单缓冲区、双缓冲区（补充）

了解即可

• （注：下图来自前言中up主视频）
  

磁盘调度算法（补充）

• 先来先服务（FCFS）：根据进程请求访问磁盘的先后次序进行调度。
• 最短寻道时间优先（SSTF）：要求访问的磁道与当前磁头所在的磁道距离最近，使得每次的寻道时间最短。
• 扫描算法（SCAN）或电梯调度算法：
  （注：下图来自前言中up主视频）
  
• 单向扫描调度算法（CSCAN）或循环扫描算法：
  （注：下图来自前言中up主视频）
  

真题链接

• 在移臂（磁盘）调度算法中，先来先服务和最短寻找（道）时间优先 算法可能会随时改变移动臂（磁头）的运动方向。（重复考，重点记忆）

• 旋转调度算法：
  • 读取记录时间=磁盘旋转速度/记录数。
  • 如果是顺序处理，而且没有对信息存储进行优化，则磁头（磁头初始在0）在读取完一个记录后，然后进行处理，由于磁头在处理过程中不会停止，所以，当磁头处理完之后，到达了按顺序读取的下一个记录的下一个记录（应该处理2，但磁头此时已经到达3），即磁头需要旋转一圈，然后来读取下一个记录。所以处理时间为 读取第一个记录的时间+处理第一个记录的时间+（总记录数-1）*（磁头旋转到应该读取的记录的开始位置的时间+读取单条记录的时间+处理单条记录的时间）（单缓冲区）
  • 如果对信息存储进行优化，即将记录进行顺序处理的间隔分步，即将每一个记录的下一个读取的记录安排在磁头读取完并处理完记录后，这样磁头处理完记录后就可以直接读取下一条记录，不用再旋转一圈，则时间为 总记录数 *（读取单条记录的时间+处理单条记录的时间）（单缓冲区）。
  • 存取时间=寻道时间+旋转延迟时间+传输时间（看清题目是读取多少块，每块之间的寻道时间+块之间的旋转延迟时间和传输时间）。
• 例题：
  （注：下图来自《软件设计师教程》（第5版）（褚华、霍秋艳主编，清华大学出版社））
  
  

三、文件管理

1、索引文件结构

• 多级索引结构：
  （注：下图来自前言中up主视频）
  
• 磁盘块=数据块=索引块。
  1）例题
  

正确答案：C、D
解析：逻辑块号往往从0开始算，逻辑块号为5的存在58号物理块中，1个物理盘块1k大，1个地址4个字节，所以1个索引块可以存1k/4=256个地址，所以逻辑块号为261的存在187号物理块中，101号物理块存放的是二级地址索引表。

2、文件和树型目录结构

• 目录结构：“××路径”不写（不包括）文件名；“××名”写（包括）文件名。
  （注：下图来自前言中up主视频）
  

真题链接

• 若系统正在将 目录 文件修改的结果写回磁盘时系统发生崩溃，则对系统的影响相对较大。

3、空闲存储空间的管理

• 位示图：每一位对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用。
• 一字节（Byte）等于8bit，字长视具体机器而定。
• 块号从0开始，字号题目没有给出则默认从1开始。
• 一个字对应32个物理块。
• （注：下图来自前言中up主视频）
  

1）例题

正确答案：D、B
解析:4195号物理块是第4196个物理块（因为从0开始编号），所以用（4195+1）/32=131.125，所以前面已经填满了131个，当前物理块所占的位在第132个字当中。因为需要占用所以取值必须为“1”，而由图可知4195号物理块在第32个字的第3位置。

第多少个字从1开始算
多少位置从0开始算

真题链接

• 在Windows XP操作系统中，用户利用“磁盘管理”程序可以对磁盘进行初始化、创建卷，可以选择使用FAT、FAT32或NTFS文件系统格式化卷。通常将"C:\Windows\myprogram.exe"文件设置成只读和隐藏属性，以便控制用户对该文件的访问，这一级安全管理称之为 文件级 安全管理。
• 如果系统采用信箱通信方式，当进程调用Send原语被设置成“等信箱”状态时，其原因是 指定的信箱中存满了信件。
• 设计操作系统时不需要考虑的问题是语言编译器的设计实现。
• 嵌入式系统初始化过程主要有3个环节，按照自底向上、从硬件到软件的次序依次为 片级初始化->板级初始化->系统级初始化。系统级初始化主要任务是 以软件初始化为主，主要进行操作系统的初始化。
• 当用户通过键盘或鼠标进入某应用系统时，通常最先获得键盘或鼠标输入信息的是 中断处理 程序。
• 实时操作系统主要用于有实时要求的过程控制等领域。实时操作系统对于来自外部的事件必须在
  被控对象规定的时间内做出及时响应并对其进行处理。
• 从减少成本和缩短研发周期考虑，要求嵌入式操作系统能运行在不同的微处理器平台上，能针对硬件变化进行结构与功能上的配置。该要求体现了嵌入式操作系统的 可定制性。
• I/O软件隐藏了I/O操作实现的细节，方便用户使用I/O设备。
• 在磁盘调度管理中通常 先进行移臂调度，再进行旋转调度。
• 若磁盘的转速提高一倍，则 旋转等待时间减半。
• 云计算有多种部署模型（Deployment Models）。若云的基础设施是为某个客户单独使用而构建的，那么该部署模型属于 私有云。
• （注：下图来自前言中up主视频）

四、设备管理

1、数据传输控制方式

• （注：下图来自前言中up主视频）
  （说明：I/O系统的层次结构与每层的主要功能）

2、虚设备与SPOOLING技术

3、微内核操作系统