nowcoder刷题——操作系统专项练习（一）_fork exec clone

1、虚拟存储

各种虚拟存储都是时间换空间，缓冲是用空间换时间。

---

2、操作系统的四个特征

操作系统有四个特征：并发，共享，异步，虚拟。
并发： 是指两个或多个事件在同一时间间隔内发生。操作系统的并发性是指计算机系统中同时存在多个运行着的程序，因此它应该具有处理和调度多个程序同时执行的能力。
共享： 是指系统中的资源（硬件资源和信息资源）可以被多个并发执行的程序共同使用，而不是被其中一个独占。资源共享有两种方式：互斥访问和同时访问。
异步： 在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底。而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。异步性使得操作系统运行在一种随机的环境下，可能导致进程产生与时间有关的错误。但是只要运行环境相同，操作系统必须保证多次运行程序，都获得相同的结果。
虚拟： 虚拟性是一种管理技术，把物理上的一个实体变成逻辑上的多个对应物，或把物理上的多个实体变成逻辑上的一个对应物的技术。采用虚拟技术的目的是为用户提供易于使用、方便高效的操作环境。

---

3、可重入代码

可重入代码也叫纯代码，是允许多个进程同时访问的，因此它不允许进程对其修改。

若一个 程序或 子程序可以安全的被并行执行，则称其为可重入（ reentrant或re-entrant）的；即，当该子程序正在运行时，可以再次进入并执行它。

---

4、文件索引结构

索引结构指一个文件的信息存放在若干不连续的物理块中，系统为每个文件建立一个专用的数据结构——索引表，并将这些块的块号存放在索引表中。有点是保留了链接结构的优点，同时解决了其缺点，即能顺序存取，又能随机存取，满足了文件动态增长，插入删除的需求，也能充分利用外存空间。缺点是索引表本身带来的系统开销。

---

5、抢占式 多任务处理

在抢占式多任务处理中，进程被抢占时，哪些运行环境需要被保存下来？

• 所有cpu寄存器的内容
• 页表
• 程序计数器

---

6、fork和exec和clone

在linux源码中这三个调用的执行过程是执行fork(),vfork(),clone()时，通过一个系统调用表映射到sys_fork(),sys_vfork(),sys_clone(),再在这三个函数中去调用do_fork()去做具体的创建进程工作。
fork和clone基本原理相同,都会产生子进程，而exec并不产生子进程,。

---

7、PV 操作

P原语： P是荷兰语Proberen（测试）的首字母。为阻塞原语，负责把当前进程由运行状态转换为阻塞状态，直到另外一个进程唤醒它。操作为：申请一个空闲资源（把信号量减1），若成功，则退出；若失败，则该进程被阻塞；

V原语 ：V是荷兰语Verhogen（增加）的首字母。为唤醒原语，负责把一个被阻塞的进程唤醒，它有一个参数表，存放着等待被唤醒的进程信息。操作为：释放一个被占用的资源（把信号量加1），如果发现有被阻塞的进程，则选择一个唤醒之。

信号量 S : 信号量的值表示相应资源的使用情况。

• 信号量 S>=0 时，S 表示可用资源的数量，执行一次P操作意味着请求分配一个资源，因此 S 的值减 1 ；

• 信号量 S<0 时，表示已经没有可用资源，S 的绝对值表示当前等待该资源的进程数，请求者必须等待其他进程释放该类资源才能继续运行，而执行一个V操作意味着释放一个资源，因此 S 的值加 1 ；

临界资源：同一时刻只允许一个进程访问的资源，与上面所说的 S 有关联。
临界区：每个进程中访问临界资源的那段程序叫做临界区。
进程对临界区的访问必须互斥，每次只允许一个进程进去临界区，其他进程等待

P(S)： S = S-1

• 如果S >= 0，进程继续执行
• 如果S < 0，进程停止执行，放入信号量等待队列中。

V(S)：S=S+1

• 如果S > 0，进程继续执行；
• 如果S <= 0，唤醒等待队列中的一个进程。

---

8、多关键字文件

多关键字文件的特点是，在对文件进行检索操作时，不仅仅对主关键词进行简单询问，还经常需要对次关键字进行其他类型的询问检索。
常见的有多重表文件、倒排文件。

文件在外存上的基本的组织方式有四种：
顺序组织，索引组织，散列组织和链组织；
对应的的文件名称分别为：顺序文件、索引文件、散列文件和多关键字文件。

• 选择哪一种文件组织方式，取决于对文件中记录的使用方式和频繁程度、存取要求、外存的性质和容量.
• 倒排文件（也称 倒排索引 ）：用记录的非主属性值（也叫副键）来查找记录而组织的文件叫倒排文件，即次索引。倒排文件中包括了所有副键值，并列出了与之有关的所有记录主键值，主要用于复杂查询。

---

9、管态、原语

管态： 管态又叫特权态，系统态，是操作系统管理的程序执行时，机器所处的状态。
原语： 通常由若干条指令组成，用来实现某个特定的操作。通过一段不可分割的或不可中断的程序实现其功能。是操作系统的一个组成部分，它必须在系统态下执行，并且常驻内存，而个别系统有一部分不在管态下运行。

原语和广义指令都可以被进程所调用，两者的差别在于原语有不可中断性，它是通过在执行过程中关闭中断实现的，且一般由系统进程调用。
许多广义指令的功能都可用目态(一种机器状态，通常把它作为用户程序执行时的状态)下运行的系统进程完成，而不一定要在管态下完成，例如文件的建立、打开、关闭、删除等广义指令，都是借助中断进入管态程序，然后转交给相应的进程，最终由进程实现其功能。因此题中描述是错误的。

---

10、系统抖动

如果分配给进程的存储块数量小于进程所需要的最小值,进程的运行将很频繁地产生缺页中断,这种频率非常高的页面置换现象称为抖动。

11、操作系统

• CP/M 是Control Program/Microprocessor(微处理器)的缩写，世界上第一个微机操作系统。
• MS-DOS 微软磁盘操作系统。
• UNIX 是一个强大的多用户、多任务操作系统，支持多种处理器架构，按照操作系统的分类，属于分时操作系统。

---

12、进程状态转换

进程运行时具有三个状态：运行态，就绪态，等待态（阻塞态）
A：一次I/O操作结束，阻塞态->就绪态
B：运行进程需要I/O操作，阻塞态->等待态
C：运行进程结束，直接转入释放
D：出现了比现运行进程优先级更高的进程，运行态->就绪态

---

13、进程控制原语

进程控制原语包括：进程创建，进程阻塞，唤醒进程和进程终止四个原语。

操作系统对进程的管理和控制主要是通过控制原语言实现的。（正确）

---

14、响应时间

响应时间：从发出命令到得到响应的时间。
包括三部分时间:
一是请求信息从键盘输入开始，直至将其传送到处理机的时间
二是处理机对请求信息进行处理的时间
三是将所形成的响应信息回送到终端显示器的时间。

---

15、优先级进程调度策略

判断下列说法是否正确：在使用优先级进程调度策略时，不存在高优先级进程等待低优先级进程的情况。（正确）

优先调度可以是抢占的或非抢占的。
当一个进程到达就绪队列时，比较它的优先级与当前运行进程的优先级。如果新到达进程的优先级高于当前运行进程的优先级，那么抢占优先级调度算法就会抢占 CPU。
非抢占优先级调度算法只是将新的进程加到就绪队列的头部。

补充：

• FCFS（先来先服务， 队列实现， 非抢占的）：先请求CPU的进程先分配到CPU。
• SJF（最短作业优先调度算法）：平均等待时间最短， 但难以知道下一个CPU区间长度。
• 优先级调度算法（可以是抢占的， 也可以是非抢占的）：优先级越高的越先分配到CPU， 相同优先级先到先服务， 存在的主要问题是：低优先级进程无穷等待CPU， 会导致无穷阻塞式饥饿，解决方案：老化（随着时间的推移， 那些越老的进程优先级反而越高）
• 时间片轮转调度算法（可抢占的）：队列中没有进程被分配超过一个时间片的CPU时间， 除非它是唯一可运行的进程。 如果进程的CPU区间超过了一个时间片， 那么该进程就被抢占并放回就绪队列
• 多级队列调度算法： 将就绪队列分成多个独立的队列， 每个队列都有自己的调度算法， 队列之间采用固定优先级抢占调度， 其中， 一个进程根据自身属性被永久地分配到一个队列中
• 多级反馈队列调度算法 ：与多级队列调度算法相比， 其允许进程在队列之间移动， 若进程使用过多CPU时间， 那么它会被转移到更低的优先级队列， 在较低优先级队列等待时间过长的进程会被转移到更高优先级队列， 以防止饥饿发生。

---

16、平均周转时间

平均周转时间 =（运行时间+等待时间）/ 作业数量
周转时间=作业完成时刻-作业到达时刻
带权周转时间=周转时间/服务时间；
平均带权周转时间=带权周转总时间/作业个数

假设系统按单值方式运行且采用最短作业优先算法，有J1,J2,J3,J4共4个作业同时到达，则以下哪几种情况下的平均周转时间为10分钟?
A 执行时间J1:1分钟 J2:5分钟 J3:9分钟 J4:13分钟
B 执行时间J1:1分钟 J2:4分钟 J3:7分钟 J4:10分钟
C 执行时间J1:2分钟 J2:4分钟 J3:6分钟 J4:8分钟
D 执行时间J1:3分钟 J2:6分钟 J3:9分钟 J4:12分钟

A： (J1执行1分钟 + J2等待1分钟 + J2执行5分钟 + J3等待6分钟 + J3执行9分钟 + J4等待15分钟 + J4执行13分钟) / 4 = 50/4 = 12.5
B： (J1执行1分钟 + J2等待1分钟 + J2执行4分钟 + J3等待5分钟 + J3执行7分钟 + J4等待12分钟 + J4执行10分钟) / 4 = 40/4 = 10
C： (J1执行2分钟 + J2等待2分钟 + J2执行4分钟 + J3等待6分钟 + J3执行6分钟 + J4等待12分钟 + J4执行8分钟) / 4 = 40/4 = 10
D： (J1执行3分钟 + J2等待3分钟 + J2执行6分钟 + J3等待9分钟 + J3执行9分钟 + J4等待18分钟 + J4执行12分钟) / 4 = 50/4 = 12.5

选BC

---

17、PCB、JCB

**进程控制块(PCB)**是系统为了管理进程设置的一个专门的数据结构。系统用它来记录进程的外部特征，描述进程的运动变化过程。同时，系统可以利用PCB来控制和管理进程，所以说，PCB（进程控制块）是系统感知进程存在的唯一标志。

JCB: Job Control Block
在操作系统的作业管理中，系统为每个作业建立一个 作业控制块 JCB。系统通过JCB感知作业的存在。JCB包括的主要内容有作业名、作业状态、资源要求、作业控制方式、作业类型以及作业优先权等。

---

18、操作系统的功能

操作系统的功能是进行处理机管理，存储器管理，设备管理，文件管理和作业管理等

19、不会引起指令流水线阻塞的是 数据旁路

指令流水线概述
一种将多条指令执行的过程相互重叠的实现技巧，是CPU可以通过并行执行多条指令来提高吞吐率。

流水线的三种冒险（阻塞）

• 同一个部件同时被不同指令使用
• 后面指令用到前面指令结果，但前面指令的结果还没有产生
• 转移或异常改变指令流程，顺序执行指令在目标地址产生前已被取出

解决流水线冒险（阻塞）的方法 - 硬件阻塞（stall）

• 软件插入“NOP”指令
• 转发（Forwarding）或旁路（ByPassing）技术
• 编译优化，调整指令顺序

20、生产者消费者模型

消费者是当队列为空了，不能取数据了，阻塞当前进程，然后给生产者发通知，表明现在队列为空了，可以生产了。
当存储空间为空时，消费者阻塞，当存储空间满时，生产者阻塞。
例题：

生产者与消费者模型是一个非常经典的同步与互斥问题，如下伪码实现了简单的消费者的功能(生产者的功能是往队列里面添加元素，消费者的功能是从队列里面取元素)

void consumption() {
    while(____){
         ____;
    }
    P(mutex);
    往队列里面取一个元素;
    V(mutex);
    ————————;
 }
1
2
3
4
5
6
7
8
9

里面的P,V就是指PV操作，mutex是互斥信号量；现有如下方法：
isFull() : 表示队列元素满了
isEmpty(): 表示队列元素为空
m_notFull.wait(): 阻塞当前进程，直到队列元素不满
m_notFull.notify(): 队列元素不满了，唤醒某个进程
m_notEmpty.wait()：阻塞当前进程，直到队列元素不为空
m_notEmpty.notify():队列元素不为空了，唤醒某个进程

请你按选好方法，填到上面空行，完成消费者的功能
isEmpty()， m_notEmpty.wait()， m_notFull.notify()

分页存储计算

分页存储管理将进程的逻辑地址空间分成若干个页，并为各页加以编号，从0开始，若某一计算机主存按字节编址，逻辑地址和物理地址都是32位，页表项大小为4字节，若使用一级页表的分页存储管理方式，逻辑地址结构为页号（20位），页内偏移量（12位），则页的大小是（ ）？页表最大占用（ ）？

1KB = 1024B = 2¹⁰B
页的大小=页内偏移量的大小 =2¹²B = 4KB。
页表占用的空间：页表项数目 * 页表项大小 = 2²⁰ * 4B = 4MB