操作系统期末复习

操作系统

1.用户级线程优于内核级线程的地方：**(1)线程交换不需要内核模式特权，因为所有线程管理数据结构都在单个进程的用户地址空间中。因此，进程不会切换到内核模式来执行线程管理。这节省了两个模式切换的开销(用户到内核;内核返回用户)。(2)调度可以是特定于应用的。一个应用程序可能从简单的循环调度算法中获益最多，而另一个应用程序可能从基于优先级的调度算法中获益最多。调度算法可以在不影响底层OS调度程序的情况下针对应用程序进行调整。结果可以在任何操作系统上运行。不需要对底层内核进行任何更改就可以支持结果。线程库是一组由所有应用程序共享的应用程序级实用程序。 **

2.死锁必要条件：1.互斥 2.请求与等待 3.非抢占 4.出现环路

3.列出并简要描述定义目录逻辑结构的三种常见方案 ：1.一级目录 2.二级目录 3.目录树

4.简单分页和虚拟分页的区别：简单分页：一个程序中所有页都必须在主存储器中程序才能使用；虚拟内存分页：不是每一页都必须在，只在需要的时候进行读取

5.磁盘空间分配的三种方法：空闲表法、空闲链表法、位图法（Unix：成组连接法）

6.使说明进程在三个基本状态之间转换的典型原因：就绪态->运行态：分配到CPU资源；运行态->就绪态：时间片用完；运行态->阻塞态：I/O请求；阻塞态->就绪态：I/0完成

7.生产者消费者问题中，如果把wait(full)和wait(mutex)位置互换，结果如何？**可能会引起死锁【正确顺序应该是先wait(full)再wait(mutex)**那将signal(empty)和signal(mutex)互换呢？只会影响进程对临界资源的释放次序，不会引起死锁，因此可以互换位置

8.高级调度与低级调度的主要任务是什么？为什么要引入中级调度？

高级调度的主要任务是根据某种算法，把外存上处于后备队列中的那些作业调入内存。低级调度是保存处理机的现场信息，按某种算法先取进程，再把处理器分配给进程。引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。使那些暂时不能运行的进程不再占用内存资源，将它们调至外存等待，把进程状态改为就绪驻外存状态或挂起状态。

9.

10.侏罗纪公园包括一个恐龙博物馆和一个狩猎骑乘公园。有m个乘客和n个单人车厢。乘客们在博物馆里逛了一会儿，然后排队乘坐游猎车。当一辆车可用时，它会载上它所能载的一名乘客，并在公园里随机行驶一段时间。如果n辆车都出来搭载乘客，那么想要搭载的乘客就会等待;如果一辆车已经准备好装载，但是没有等待的乘客，那么这辆车就会等待。使用信号灯、wait()和signal()同步m个乘客进程和n个轿厢进程 ：

11.

12.解释名词：虚拟机：用软件实现的机器。虚拟机是一种严密隔离的软件容器，它可以运行自己的操作系统和应用程序，就好像一台物理计算机一样。虚拟机的运行完全类似于一台物理计算机，它包含自己的虚拟(即基于软件实现的)CPU、RAM 硬盘和网络接口卡 (NIC)。操作系统无法分辨虚拟机与物理机之间的差异，应用程序和网络中的其他计算机也无法分辨。即使是虚拟机本身也认为自己是一台“真正的”计算机。不过，虚拟机完全由软件组成，不含任何硬件组件。

13.为什么要区分内核态和用户态：区分执行态的主要目的是保护系统程序。用户态到和核心态的转换发生在中断产生时，而核心态到用户态的转换则发生在中断返回到用户程序时。【I/O,中断都在内核态执行】

14.读者问题（读者优先和写者优先）【读者优先：https://blog.csdn.net/c1194758555/article/details/52805918；写者优先：https://blog.csdn.net/lllllyt/article/details/80507084

15.？下列并发模型中不含同步问题的是：D哲学家就餐问题

16.在动态分区的放置算法中，性能最差的算法通常是：最佳适配算法

17.64位操作系统一般采用：三级页表；32位操作系统一般采用：二级页表

18.竟态【计算结果有时正确，有时不正确】值一组并发执行的进程产生了不可预测的结果，它发生的最关键一点的原因是：共享内存的变量

19.存储文件三种方式：1.连续存储：支持随机；2.链式存储：不支持随机；3.索引存储：支持随机

20.为什么多线程比多进程效率更高：线程不拥有资源且与进程其它线程共享进程的代码和地址空间，切换的开销小

21.把作业地址空间中使用的逻辑地址变成物理地址称为：重定位

22.一般来说，为了实现多道程序设计，计算机最需要：更大的内存

23.文件控制块不包括：磁盘环块位置【文件控制块包含的信息有：文件号、文件名、文件的物理位置、文件的逻辑结构、文件的存取控制权限、文件的建立日期和时间以及文件的修改日期和世家按、当前已打开该文件的进程数以及是否被进程锁住等等】

24.为了提高设备分配的灵活性，用户申请设备时应指定：设备类相对号

25.进程所请求的一次打印输出结束后，将使进程状态从：等待态变为就绪态

26.分页式存储管理中，地址转换工作由：硬件完成，【分页式存储管理采用动态重定位方式装入作业，因而需要有硬件地址转换机制的支持

27.磁盘是直接存取的设备

28.SPOOLING技术是利用：内存作为虚拟设备的

29.B

30.DMA控制方式是在：I/O设备和主存之间建立一条直接数据通路

31.资源的有序分配策略可以破坏死锁的：循环等待条件

32.[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wRrGB5xS-1580956535923)(C:\Users\11370\AppData\Roaming\Typora\typora-user-images\image-20200110084814423.png)]D

33.[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4SzXD9p3-1580956535923)(C:\Users\11370\AppData\Roaming\Typora\typora-user-images\image-20200110084959188.png)]B

34.[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1MTuMJEP-1580956535925)(C:\Users\11370\AppData\Roaming\Typora\typora-user-images\image-20200110085222738.png)]B

程序与程序之间的并行操作是需要多处理器的。在单核处理器系统中可能发生的并发和并行的现象如下：进程与进程之间的并发、处理器与设备之间的并行、处理器与通道之间的并行、通道与通道之间的并行、设备与设备之间的并行。【并发：多进程是并发执行，就是一个时间段内有多个进程在执行，但是在某个时间点上只有一个进程在执行】

35.[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QN3cRy85-1580956535925)(C:\Users\11370\AppData\Roaming\Typora\typora-user-images\image-20200110091320906.png)]

(a) 段号1对应基址为2300 长度14>10（段内位移）所以物理地址为：2300+10=2310

(b)段号为4对应基址1952 长度96<112 所以发生段越界，产生越界中断

36.操作系统的资源分配单位和调度单位：线程

37.进程在内存中是如何布局的：进程在内存中包含：代码段、数据段、堆、栈、BSS；代码段：保存程序执行码，在进程并发时，代码段时共享且只读的，在存储器中只需有一个副本。数据段：包含了程序中已初始化的全局变量、静态变量。堆：按照程序需要动态分配的空间，malloc,calloc,realloc函数分配的空间都在堆上分配。栈：程序执行前静态分配的内存空间，栈的大小可在编译时指定，Linux环境默认8M，栈段是存放局部变量，函数调用信息，中断现场保留信息的空间

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sgwEmKSh-1580956535926)(C:\Users\11370\AppData\Roaming\Typora\typora-user-images\image-20200110100639661.png)]

38.在页式管理寄存器中，页表的初始位置存放在：寄存器

39.内核和普通用户进程并不在同一个线性地址空间内，为什么内核仍然可以访问用户进程的页面？

虽然内核和用户进程不再同一个线性地址空间内，但是用户进程的页面要从物理内存中分配，而内核的分页机制即页目录表、页表等，正好管理着16M物理内存，所以内核可以访问普通用户进程的页面。【同一个程序运行起来的两个进程，虚拟地址空间相同但是对应的物理空间是不相同的。OS需要给每一个进程设置一份页表，在进程调度过程中，上下文切换会做页表的切换。每个进程的页表都是由OS来管理的

40.[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Vt7qxTH1-1580956535927)(C:\Users\11370\AppData\Roaming\Typora\typora-user-images\image-20200111083433744.png)]

41.进程A1、A2，…An1通过m个缓冲区向进程B1、B2、…Bn2不断发送消息。发送和接收工作遵循下列规则：（1）每个发送进程一次发送一个消息，写入一个缓冲区， 缓冲区大小等于消息长度（2）对每个消息，B1，B2，…，Bn2都须各接收一次，读 入各自的数据区内（3）m个缓冲区都满时，发送进程等待，没有可读消息 时，接收进程等待。试用P、V操作组织正确的发送和接收工作。 提示：每个缓冲区只需写一次但要读n2次，因此，可以看成n2组缓冲区，每个发送者要同时写n2组缓冲区中相应的n2个缓冲区，而每个接收者只要读它自己对应的那组缓冲区的对应单元。Sin[n2]=m，表示每组缓冲区中可放的（空的）缓冲区的数目，初值为m;Sout[n2]=0，表示每组缓冲区中可取的（已用的）缓冲区的数目，初值为0;
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rVMo7ODP-1580956535928)(C:\Users\11370\AppData\Roaming\Typora\typora-user-images\image-20200111084109362.png)]

42.死锁产生原因：1.竞争资源引起进程死锁（资源分配策略） 2.进程推进顺序不当

43.SPOOLING技术：假脱机：提高了I/O速度；将独占设备改造为共享设备；实现了虚拟设备功能.【在SPOOLING技术的系统中，用户打印的数据首先被送到磁盘固定区域】

【在SPOOLING技术中，用户进程可以直接高效地使用字符设备。F，不能直接使用设备，要通过缓冲区

44.假定磁盘总大小为512GB，每个簇包含16个扇区，每个扇区512B，采取位示图的磁盘空闲空间管理方式，则位示图占用空间为：512G/16/512=64M个二进制数字，即64Mbit.所以对应8MB

45.某文件系统采用混合索引的方式组织元数据，包含5个直接块，一个一次间接块和2个两次间接块，若每个物理块为4KB，每个地址指针长度为32bit,则本文件系统可支持的最大文件规模约为：

*直接块：5x4KB=20KB; 一次间接块：1x(4K/(32/8))4K=4MB; 两次间接块：2x(4K/(32/8))^2x4K=8GB

46.假定把磁盘上一个数据块中的信息输入一个双缓存区的时间T=0.2ms,将缓冲区中的数据送到用户区的时间M=0.1ms,而CPU对数据处理时间C=0.1ms，这样系统对每个数据块的处理时间为：0.2ms

对于单缓存：【缓冲数据传输到用户区之后才能再从磁盘读取数据】由于T和C是可以并行的，当T>C时，系统对每一块数据的处理时间为M+T，反之则为M+C

对于双缓存：【缓冲区数据传输到用户区的同时，也能从磁盘读取数据】所以答案是MAX(C,T)】

47.当系统发送抖动（thrashing）时，可采取得到有效措施是：撤销部分进程【抖动现象是指刚刚被换出的页很快又要被访问，如此频繁地置换页面，以至大部分时间被花在置换页面上。撤销部分进程可以减少所要用到的页面数，防止抖动。对换区大小和进程优先级都对其无影响】

48.FCFS有利于CPU繁忙型作业，而不利于I/O繁忙型作业【CPU繁忙型作业是指该类作业需要大量地CPU时间进行运算，而很少请求I/O操作；I/O繁忙型作业是指CPU处理时，需要频繁地请求I/O操作

49.设与某资源关联的信号量K初值为3，当前值为1，若M表示该资源的可用个数，N表示该资源等待的进程数，则M,N分别是：1,0 【信号量大于0时，表明的是可用的资源数，等待的进程数为0；信号量小于0时，信号量的绝对值表示等待的进程数，可用的资源数为0】

50.死锁的避免是根据：防止系统进入不安全状态；死锁的预防是：破环死锁的四个必要条件之一

51.某系统中有三个并发进程需要四个同类资源，该系统不会发生死锁的最小资源数（10个【(4-1)x3+1=10】）

52.空间局部性是指：如果一个存储器的位置被引用，那么将来他附近的位置也会被引用

​ 时间局部性是指：被引用过一次的存储器在未来会被多次引用

53.文件目录存放的信息是：该目录中所有子目录文件和数据文件的目录。【文件目录是FCB的集合，里面既有目录也有数据文件，因此文件目录中存放的是该目录中所有子目录文件】

54.操作系统是根据：PCB来对并发执行的进程控制和管理的

55.长（作业）调度控制：多道作业的道

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-G4mIlkkh-1580956535929)(C:\Users\11370\AppData\Roaming\Typora\typora-user-images\image-20200114160017438.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1MPeWFyC-1580956535930)(C:\Users\11370\AppData\Roaming\Typora\typora-user-images\image-20200114160331858.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MJXYBCr3-1580956535931)(C:\Users\11370\AppData\Roaming\Typora\typora-user-images\image-20200114162318020.png)]

物理内存和虚拟内存的区别：虚拟内存：机器可以用来执行操作的内存。虚拟内存：是一种方法，通过它可以执行比物理内存更大的空间的程序

系统调用是由硬件触发的 F 是由用户态程序执行的过程中调用了一个系统调用陷入到了内核态中。系统调用只是一种特殊的中断

微内核：提供操作系统核心功能的精简版本，它的优点是易于扩展，所有新服务可以添加到用户空间而不用修改内核

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GiZZdwPF-1580956535932)(C:\Users\11370\AppData\Roaming\Typora\typora-user-images\image-20200114164438133.png)]

当CPU切换到另一个进程时，系统必须保存旧进程的状态（到PCB),并通过上下文切换为新进程加载保存的状态

通常exec()【exec函数族提供在一个进程中启动另一个程序执行的方法，调用完成后，除pid号之外其它全部被新进程的内容替换】调用紧跟再fork()之后。如果在fork之前使用了exec会怎么样？因为exec会覆盖进程，所以不会执行exec后面的fork操作了

多级队列调度：系统中不同类型或性质的就绪进程固定分配到不同的就绪队列中，每个就绪队列可以采用自己的调度算法；在队列之间采用固定优先权的抢占调度方式

优先级反转：是指在使用信号量时会出现的一种不合理现象：高优先级的任务被低优先级的任务阻塞，从现象上来看，好像是低优先级的任务比高优先级的任务具有更高的优先权

信号量和自旋锁最大的不同在于：当一个进程试图去获得一个已经锁定的信号量时，该进程不会像自旋锁一样在自旋忙等待，而是会将自身加入一个等待队列去睡眠，知道其它进程释放信号量之后，处于等待队列的进程才会被唤醒

RAID结构主要：用于确保更高的数据可靠性

RAID5是最常用的奇偶校验RAID系统

RAID0不提供冗余，它只是将数据块分为多个子块，从而提升性能

SSD（固态硬盘）：通常使用FCFS的调度策略

影响磁盘调度算法选择的因素有哪些：调度算法的性能很大程度上取决于请求的数量和类型，磁盘服务请求可能会受文件分配方式的很大影响。目录和索引块的位置也很重要。其它因素有：旋转延迟、操作系统约束（比如请求分页）

---

XV6系统：

进程

xv6实现了一个基于进程（没有实现线程）的简单进程管理机制，xv6的proc.h文件中定义了一个context结构，一个枚举类型proc_state定义了UNUSED,EMBRYO,SLEEPING,RUNNABLE,RUNNING,ZOMBIE六种进程状态。

xv6中的proc类中的proc定义了进程ID，进程状态，父进程，context保存寄存器为内核的上下文切换。get_raw_proc方法可以创建一个新进程并对进程进行初始化分配进程页表和内核堆栈.进程的上下文切换包括当前程序计数器PC和当前运行的CPU中各个寄存器的内容

一个 xv6 进程由两部分组成，一部分是：用户内存空间（指令，数据，栈），另一部分是：仅对内核可见的进程状态。xv6 提供了分时特性：它在可用 CPU 之间不断切换，决定哪一个等待中的进程被执行。当一个进程不在执行时，xv6 保存它的 CPU 寄存器，当他们再次被执行时恢复这些寄存器的值。内核将每个进程和一个 pid (process identifier) 关联起来。xv6的最大进程数写在param.h文件中#define NPROC 64属性中，默认最大进程数为64

内存管理

xv6对于物理内存的管理较为简单，只是将每一空闲页用链表链接起来，向上提供kalloc和kfree接口来屏蔽管理物理内存的细节，xv6将内存管理分为内核地址空间管理和用户地址空间管理，并提供几个函数供系统调用过程调用，很多需要管理内存的系统函数例如exec，fork都需要使用到这些接口，vm.c和kalloc.c包含了内存管理的大部分内容，系统调用过程使用这些函数来初始化和处理页表结构。

kalloc:负责在需要的时候为空户空间、内核栈、页表页以及缓冲区分配物理内存，将物理内存转为虚拟地址返回，物理页答案小薇4k.void kfree接收一个虚拟地址，找到对应的物理地址进行释放。

xv6使用空闲内存的前部分作为指针域来指向下一页空闲内存。物理内存上空闲的每一页都有一个指针域（虚拟地址）指向下一个空闲页，最后一个空闲页为null。通过这种方式，kmem只要保存着虚拟地址空间的freelist地址即可。

相关问题

• xv6初始化之后执行到main.c时，内存布局是怎样的(其中已有哪些内容)？

• xv6的动态内存管理是如何完成的？

有一个kmem(链表，用于管理可分配的物理内存页)

struct run{
    struct run* next;
};
struct{
    struct spinlock lock;
    int use_lock;
    struct run* freelist;
}kmem;

• xv6的虚拟内存是如何实现初始化的？

main函数通过调用kinit1,kinit2,kvmalloc函数来实现内核新页表的初始化

void kinit1(void)
{
    initlock(&kmem.lock,"kmem");
    kmem.unse_lock=0;
    freerange(vstart,vend);
}
void kinit2(void* vstart,void* vend)
{
    freerange(vstart,vend);
    kem.use_lock=1;
}

t2,kvmalloc函数来实现内核新页表的初始化**

void kinit1(void)
{
    initlock(&kmem.lock,"kmem");
    kmem.unse_lock=0;
    freerange(vstart,vend);
}
void kinit2(void* vstart,void* vend)
{
    freerange(vstart,vend);
    kem.use_lock=1;
}