操作系统导论部分章节习题

进程

一。单选题（共1题，10.0分）

当某个进程进行系统调用以通过网络传输TCP数据包时，以下哪些步骤不会总是发生？

A进程进入内核模式。

B，CPU的程序计数器转移到地址空间的内核部分。

C，该进程被上下文切换出，一个单独的内核进程开始执行。

D，调用用于处理TCP / IP数据包的OS代码。

正确答案：C

二。多选题（共1题，10.0分）

以下哪个C库函数不直接对应于（类似命名的）系统调用？也就是说，这些C库函数中的哪一个不是对底层系统调用的直接调用？

A系统，执行bash shell命令。

B，fork，这将创建一个新的子进程。

C，退出，终止当前进程。

D，strlen，返回字符串的长度。

正确答案：AD

三。填空题（共2题，20.0分）

考虑下面的代码片段中分叉了一个孩子的父进程。

int count = 0;

ret = fork（）;

if（ret == 0）{

    printf（“ count in child =％d \ n”，count）;

} else {count = 1;

 }

父母在孩子第一次执行之前执行语句“ count = 1”。现在，上面的代码显示的计数值是多少？假设操作系统实现了常规分支（而不是写时复制分支）。

正确答案：

第一空： 0

2在下面的程序中，考虑一个分叉了子进程C的父进程P。

int a = 5;

int fd = open(...) //opening a file 

int ret = fork(); 

if(ret > 0) {

    close(fd);

    a = 6;

    ...

} else if (ret == 0) {

    printf("a=%d\n", a);

    read(fd, something); 

}

在分叉新流程之后，假设首先在父流程之前安排父流程。父级在派生后恢复后，它将关闭文件描述符并更改变量的值，如上所示。假定仅在父级完成这两个更改之后，才第一次调度子级进程。

（a）____是下一个计划在子进程中打印的变量a的值。

（b）在孩子中从文件描述符读取的尝试会成功吗？是还是不是

正确答案：

第一空： 5

第二空： 是

答案解析：

（a）5.仅在父级中更改值。

（b）是的，文件仅在父级中关闭。

四。判断题（共6题，60.0分）

1.两个进程可以同时执行同一程序可执行文件吗？

正确答案：√

2两个正在运行的进程是否可以在物理内存中共享完整的进程映像（而不仅仅是其中的一部分）？

正确答案：×

3用户模式下的进程无法执行某些特权硬件指令。

正确答案：√

4上下文切换只能在处理定时器中断之后发生，而不能在任何其他系统调用或中断之后发生。

正确答案：×

5每当进程从用户模式进入内核模式时，都会经历上下文切换。

正确答案：×

6.AC程序无法直接调用OS系统调用，因此必须始终使用C库。

正确答案：×

进程调度策略和内存虚拟化机制

一.多选题（共4题,100.0分）

1下面关于多层反馈队列（MLFQ）调度的描述，哪些是可能的（正确的）？

A、MLFQ了解有关运行作业的一些信息

B、MLFQ会使长期运行的作业挨饿

C、MLFQ为作业们使用了不同长度的时间片

D、MLFQ使用了轮转（round robin）

E、MLFQ有时候会忘记它已经了解到的有关作业的信息

正确答案： ACDE

2对于下面的作业，使用FIFO调度器，并且只有一个CPU。每个作业有一个“需要的”运行时间，即完成作业需要多少个CPU时间单元。作业A在时刻0到达，需要X个时间单元，作业B在时刻5到达，需要Y个时间单元，作业C在时刻10到达，需要Z个时间单元。假设平均周转时间在10到20（包含）之间，下面A、B和C的运行时间，哪些是可能的？

A、A=10, B=10, C=10

B、A=20, B=20, C=20

C、A=5, B=10, C=15

D、A=20, B=30, C=40

E、A=30, B=1, C=1

正确答案： AC

3对于虚拟化内存来说，最简单的技术是动态重定位，或者“基址-界限”，假设有以下的系统特征：一个1KB的地址空间，基址寄存器被设为10000，界限寄存器被设为100。下面哪些物理内存的位置能够被运行程序合法地访问？

A、0

B、1000

C、10000

D、10050

E、10100

正确答案： CD

4假设一个简单的分段系统支持两个段：一个用于代码和堆（正增长），一个用于堆栈（负增长）。虚拟地址空间大小是128个字节。物理内存大小是512个字节。段寄存器的信息：段0的基址（正向增长）：0，界限：20（十进制）。段1的基址（负向增长）：0x200（十进制512），界限：20（十进制）。下面哪些是有效的虚拟内存访问？

A、0x1d (十进制: 29)

B、0x17b (十进制: 123)

C、0x10 (十进制: 16)

D、0x5a (十进制: 90)

E、0x0a (十进制: 10)

正确答案： BCE

内存虚拟化

一。填空题（共3题，70.0分）

考虑一个具有6位虚拟地址空间和16字节页面/帧的系统。从虚拟页号到进程的物理帧号的映射是（0,8），（1,3），（2,11）和（3,1）。将以下虚拟地址转换为物理地址。请注意，所有地址均为十进制。用十进制形式写下答案。

（一）20

（b）40

正确答案：

第一空： 52

第二空： 184

答案解析：

（a）20 = 01 0100 = 11 0100 = 52

（b）40 = 10 1000 = 1011 1000 = 184

2考虑一个运行单个进程的简单系统。物理帧和逻辑页面的大小为16个字节。RAM可容纳3个物理帧。进程的虚拟地址大小为6位。该程序在CPU上运行时会生成以下20个虚拟地址引用：0、1、20、2、20、21、32、31、0、60、0、0、16、1、17、18、32， 31、0、61。（注意：此处的6位地址以十进制显示。）假定RAM中的物理帧最初是空的，并且没有映射到任何逻辑页。

（a）将上面的虚拟地址转换为该进程引用的逻辑页码。

即，写下与上述虚拟地址访问相对应的20页页码的参考字符串。假设页面的编号从0、1，...开始 答案示例：0、1、1、0、1、2、3、2、1、2、0、1、1、0、1、2、3、2、1、2

（b）假设使用FIFO页面替换算法，则计算由上述访问产生的页面错误数。

（c）对LRU页面替换算法重复以上（b）。

（d）假设要使用最佳页面替换算法，那么在此示例中可以实现的最少页面错误数是多少？

正确答案：

第一空：

0、0、1、0、1、1、2、1、0、3、0、0、1、0、1、1、2、1、0、3

第二空： 8

第三空： 6

第四空： 6

答案解析：（a）对于6位虚拟地址和4位页面偏移量（页面大小16字节），虚拟地址中最重要的2位将代表页码。因此，参考字符串为0、0、1、0、1、1、2、1、0、3（再次重复）。

2（b）FIFO = 8的页面错误.0、1、2、3（已替换0），0（已替换1），1（已替换2），2（已替换3），3上的页面错误。

（c）LRU = 6的页面错误。0、1、2、3（已替换2），2（已替换3），3上的页面错误。

（d）最佳算法将替换将来最不可能使用的页面，并且看起来像上面的LRU。

3考虑使用48位虚拟地址和16KB页面的操作系统。系统使用分层页表设计来存储进程的所有页表项，每个页表项的大小为4个字节。在分层页面表的所有级别上，存储一个进程的页面表项所需的页面总数是多少？

请使用2 ^ 10表示幂，例如2 到 10 的幂是2 ^ 10

答案示例：2 ^ 20 + 2 ^ 10 + 2

正确答案：第一空： 2 ^ 22 + 2 ^ 10 + 1

答案解析：页面大小= 2 ^ 14bytes。因此，页表条目的数量= 2 ^ 48/2 14 = 2 ^ 34。每页可以存储16KB / 4 = 2 ^ 12页表条目。因此，最里面的页面数= 2 ^ 34/2 ^ 12 = 2 ^ 22。

现在，指向所有这些最里面页面的指针必须存储在页面表的下一层中，因此页面表的下一层具有2 ^ 22/2 ^ 12 = 2 ^ 10页。最后，一个页面可以存储所有2 ^ 10个页面表条目，因此最外层有一页。

因此，存储页表项的页面总数为2 ^ 22 + 2 ^ 10 +1。

二。判断题（共5题，30.0分）

1.TLB 是现代分页系统中的一个关键部分。假设有下面的系统：页大小是64 个字节，TLB 包含了4 项，TLB 替换策略是LRU （最近最少使用）。下面的每一个代表了一个虚拟内存地址轨迹，即，一个程序引用的多个虚拟内存地址。在下面的轨迹中，可能通过TLB 加速执行的打“√”，不能加速的打“×”。

0，100，200，1，101，201，...（以这种模式重复）

正确答案：√

2．TLB 是现代分页系统中的一个关键部分。假设有下面的系统：页大小是64 个字节，TLB 包含了4 项，TLB 替换策略是LRU （最近最少使用）。下面的每一个代表了一个虚拟内存地址轨迹，即，一个程序引用的多个虚拟内存地址。在下面的轨迹中，可能通过TLB 加速执行的打“√”，不能加速的打“×”。

0、100、200、300、0、100、200、300，...（重复）

正确答案：√

3．TLB 是现代分页系统中的一个关键部分。假设有下面的系统：页大小是64 个字节，TLB 包含了4 项，TLB 替换策略是LRU （最近最少使用）。下面的每一个代表了一个虚拟内存地址轨迹，即，一个程序引用的多个虚拟内存地址。在下面的轨迹中，可能通过TLB 加速执行的打“√”，不能加速的打“×”。

0，1000，2000，3000，4000，0，1000，2000，3000，4000，...（重复）

正确答案：×

4．TLB 是现代分页系统中的一个关键部分。假设有下面的系统：页大小是64 个字节，TLB 包含了4 项，TLB 替换策略是LRU （最近最少使用）。下面的每一个代表了一个虚拟内存地址轨迹，即，一个程序引用的多个虚拟内存地址。在下面的轨迹中，可能通过TLB 加速执行的打“√”，不能加速的打“×”。

0、1、2、3、4、5、6、0、1、2、3、4、5、6 ...（重复）

正确答案：√

5．TLB 是现代分页系统中的一个关键部分。假设有下面的系统：页大小是64 个字节，TLB 包含了4 项，TLB 替换策略是LRU （最近最少使用）。下面的每一个代表了一个虚拟内存地址轨迹，即，一个程序引用的多个虚拟内存地址。在下面的轨迹中，可能通过TLB 加速执行的打“√”，不能加速的打“×”。

300，200，100，0，300，200，100，0，...（重复）

正确答案：√

并发

一。多选题（共5题，50.0分）

下面是一个并发程序（多线程的），pthread create（）  和pthread join（）运行正确，不返回错误。

该程序的可能输出是什么？

A.0

B，1000

C，999

D，998

E，1002

正确答案：CD

2假定以下列表插入代码将其插入到共享全局变量head指向的列表中：

int List_Insert(int key) { 

    node_t * n = malloc(sizeof(node_t));

    if (n == NULL) { return -1; } 

    n->key = key; 

    n->next = head; 

    head = n; 

    return 0; 

}

该代码由三个线程中的每个线程执行一次，而无需添加任何同步原语（例如锁）。假设malloc（）是线程安全的（即，可以在不担心数据争用的情况下调用）并且malloc（）成功返回，那么当这三个线程执行完毕时，列表可能需要多长时间？（假设列表开始时为空）

A.0

B，1

C，2

D，3

E，4

正确答案：BCD

答案解析：假设列表开头是空的。因为争相将节点包括在列表中，所以在插入期间可能会删除节点。如果我们有三个线程进行插入，则它们调用可能会成功（由于某种原因而被序列化），或者只有一个可能成功（其他两个更新丢失）。在任何情况下都不会迷路。

3这是更多的多线程代码：
Here is some more multi-threaded code:

void * printer(void * arg) { 

    char * p = (char * ) arg; 

    printf("%c", * p); 

    return NULL; 

}

int main(int argc, char * argv[]) { 

    pthread_t p[5];

    for (int i = 0; i < 5; i++) {

        char * c = malloc(sizeof(char)); * c = ’a’ + i; // hint: ’a’ + 1 = ’b’, etc. 

        pthread_create(&p[i], NULL, printer, (void * ) c);

    }

    for (int i = 0; i < 5; i++)

        pthread_join(p[i], NULL);

     return 0;

}

A.abcde

B，edcba

C，ccdde

D，eeeee

E，aaaaa

正确答案：AB

答案解析：每个线程都会被创建，并传递一个带有一个字母的唯一参数：“ a”，“ b”，“ c”，“ d”或“ e”。线程可以以任何顺序运行，因此任何输出，每个输出只有一个字母，但是可以以任意顺序运行。

4避免死锁的一种方法是仔细安排线程。假定线程T1，T2和T3具有以下特征：

T1（在某个时候）获取并释放锁L1，L2

T2（在某个时候）获取并释放锁L1，L3

T3（在某个时候）获取并释放锁L3，L1和L4

下列哪些时间表可能会陷入僵局？

A.T1运行完成，然后T2运行完成，然后T3运行

B，T1和T2同时运行直到完成，然后T3运行

C，T1，T2和T3同时运行

D，T3运行完成，然后T1和T2同时运行

E，T1和T3同时运行直到完成，然后T2运行

正确答案：C

答案解析：这个问题的关键：CAN死锁的线程是否曾经同时运行？如果是这样，他们可能会陷入僵局。如果不是，则不是。从上面可以看出，只有T2和T3可以死锁，因为它们每个都以某种顺序抓住两个锁（L1和L3）。

5假定以下多线程内存分配器大致如下所示：

#define  MAX_HEAP_SIZE 400

int bytes_left = MAX_HEAP_SIZE;

pthread_cond_t c;

pthread_mutex_t m;

void * allocate(int size) {

pthread_mutex_lock(&m);

while (bytes_left < size)

pthread_cond_wait(&c, &m);

void * ptr = ...; // get mem from internal data structs

bytes_left -= size;

pthread_mutex_unlock(&m);

return ptr;

}

void free(void * ptr, int size) {

pthread_mutex_lock(&m);

bytes_left += size;

pthread_cond_signal(&c);

pthread_mutex_unlock(&m);

}

假设所有内存都用完了（即，剩余字节为0）。然后：

一个线程（T1）调用allocate（100）

一段时间后，第二个线程（T2）调用allocate（1000）

最后，一段时间后，第三个线程（T3）调用free（200）

假设所有对线程库函数的调用均按预期工作，那么在发生此事件序列之后，下列哪项是可能的？

A.T1和T2在allocate（）中保持阻塞

B，T1变为无阻塞，分配了100个字节，然后从allocate（）返回

C，T2变为无阻塞，分配了1000个字节，然后从allocate（）返回

D，T3在free（）中被阻塞

E，T1，T2和T3陷入僵局

正确答案：AB

答案解析：此代码示例的问题是，当free（）向等待线程发出信号时，无法保证它会唤醒“正确的”线程，即，它可能会唤醒正在等待过多内存的线程。在这种情况下，我们让T1等待100个字节，T2等待1000个字节，然后T3仅释放200个字节（不足以使T2成功分配，但足以满足T1）。从而：

A.可能，因为信号可能唤醒T2，然后T2重新检查其状况，并可能永远回到睡眠状态。

B.可能如果我们很幸运（相反），T1被T3唤醒，然后成功完成其分配请求。

C.不可能没有1000字节的空闲空间，所以这不会发生。

D.不可能不可能（真的），因为没有什么可以永久阻止的。就是说，获取lock（）可能需要一点时间...

E.不可能只有一个锁，因此不会出现死锁。

二。判断题（共10题，50.0分）

1.进程中的线程是否必须具有单独的堆栈？

正确答案：√

2进程中的线程是否必须具有程序可执行文件的单独副本？

正确答案：×

3可以并行执行线程/进程而没有并行性吗？

正确答案：√

4考虑共享程序中全局变量的进程中的N个线程。如果一个线程对该变量进行了更改，则此更改对其他线程可见。

正确答案：√

5考虑一个进程中的N个线程。如果一个线程将某些参数传递给程序中的函数，则其他线程可以看到这些参数。

正确答案：×

6信号量是有用的同步原语。以下哪个陈述对信号量是正确的？

每个信号量都有一个整数值

正确答案：√

答案解析：通过定义，每个信号量都有一个值。

7信号量是有用的同步原语。以下哪个陈述对信号量是正确的？

如果将信号量初始化为1，则可以将其用作锁

正确答案：√

答案解析：这称为二进制信号量。

8单个锁和条件变量可以串联使用以实现信号量

正确答案：√

答案解析：这是正确的，还有一个用于跟踪信号量值的状态变量。

9调用sem post（）可能会阻塞，具体取决于信号量的当前值

正确答案：×

答案解析：只有sem wait（）块，sem post（）才起作用并返回。

10信号量可以初始化为大于1的值

正确答案：√

答案解析：如书中所述，这在某些情况下很有用。

持久化

一。单选题（共3题，60.0分）

1.考虑一个具有512字节块的文件系统。假设文件的inode包含指向2个直接数据块的指针和指向单个间接块的指针。此外，假设单个间接块可以保存指向其他4个数据块的指针。这样的inode设计可以支持的最大文件大小是多少？

A.512

B，1024

C，3072

D，4096

正确答案：C

2考虑一个FAT文件系统，其中磁盘分为512字节块，每个FAT条目可以存储4位块号。这样的FAT设计可以管理的磁盘分区的最大大小是多少？

A.4096

B，8192

C，2048

D，512

正确答案：B

答案解析：2 ^ N * M

3考虑一个具有512字节大小块的2 TB大小的辅助存储系统。假设文件系统使用多级inode数据结构来跟踪文件的数据块。索引节点具有64个字节的可用空间来存储指向数据块的指针，这些数据块包括一个间接块，一个双重间接块和几个直接块。在这样的文件系统中可以存储的最大文件大小是多少？

A.16526

B，72704

C，8461312

D，9306112

正确答案：C

答案解析：数据块的数量= 2 ^ 41/2 ^ 9 = 2 32，因此需要32位或4个字节来存储数据块的数量。索引节点中数据块指针的数量= 64/4 = 16，其中14个是直接块。单个间接块存储指向512/4 = 128个数据块的指针。双间接块指向128个单个间接块，每个间接块依次指向128个数据块。因此，一个文件中的数据块总数可以为14 + 128 + 128 * 128 = 16526，最大文件大小为16526 * 512字节。

二。判断题（共2题，40.0分）

1.考虑从另一个父目录D2硬链接的文件D1 / F1。然后，该文件在目录D1中的目录条目（包括文件名和索引节点号）必须与目录D2中的目录条目完全相同。

正确答案：×

答案解析：F（文件名可以不同）

2软链接可以在不同文件系统之间的文件之间创建链接，而硬链接只能在同一文件系统内的目录和文件之间创建链接。

正确答案：√

答案解析：T（因为硬链接存储索引节点号，仅在文件系统中唯一）