Operating System Concepts 课后答案（部分）

学习笔记

Operating System Concepts 课后答案（部分）

搬运&排版&部分题目答案修正：我

校对：你

Chapter 1

1.5

How does the distinction between kernel mode and user mode function as a rudimentary form of protection (security) system?

只有当CPU处于内核模式时，才能执行特权指令。如果尝试在用户模式下执行特权指令，则不会执行并视为非法指令。硬件将其陷阱到操作系统。

1.6

Which of the following instructions should be privileged?

a. Set value of timer
c. clear memory
e. turn off interrupts
f. modify entries in device-status table
g. Switch from user to kernel mode
h. access I/O device.

1.12

In a multiprogramming and time-sharing environment, several users share the system simultaneously. This situation can result in various security problems.

Q.a

在内存中的另一个程序（属于另一个用户或操作系统）区域上写入；
当其他用户的文件正在打印时，通过发送数据使打印机混合输出。

Q.b

不会，任何分时环境保护方案都可能被破坏且该方案越复杂，就越有可能出错

1.15

Describe the differences between symmetric and asymmetric multiprocessing. What are three advantages and one disadvantage of multiprocessor systems?

Symmetric processing：每个处理器都参与完成操作系统的所有任务，所有处理器对等，处理器之间没有主从关系

Asymmetric processing ：每个处理器都有各自特定的任务，有一个主处理器控制系统，调度从处理器并安排工作。

序号	键	非对称多处理	对称多处理
1	中央处理器	所有处理器的优先级都不相同。	所有处理器的优先级相同。
2	操作系统任务	操作系统任务由主处理器完成。	操作系统任务可以由任何处理器完成。
3	通信开销	处理器之间没有通信开销，因为它们是由主处理器控制的。	所有处理器都使用共享内存相互通信。
4	进程调度	采用主从式方法	使用就绪的进程队列。
5	成本	非对称多处理的实现成本较低。	对称多重处理的实施成本较高。
6	设计复杂度	非对称多处理的实现成本较低。	对称多重处理的设计很复杂。

advantage：

规模经济：多处理器系统的价格要低于相同功能的多个单处理器系统的价格。可以通过共享外设、大容量存储和电源供给节约资源，多个程序处理同一数据集时可以只要一个副本，节省开销
增加吞吐量：通过增加处理器的数量，可以在更短的时间内完成更多的工作
增加可靠性：可以将功能分布在多个处理器上，提高容错。

disadvantage：

多处理器系统在硬件和软件方面都更加复杂，管理协作需要额外的CPU周期，因此每个CPU的效率会下降。产生1+1<2的效果。

1.19

What is the purpose of interrupts? How does an interrupt differ from a trap? Can traps be generated intentionally by a user program? If so, for what purpose?

操作系统是中断驱动的，事件的发生通常通过硬件或软件的中断来通知。

中断又称为外中断，是由外部事件引起的并且发生时间是不可预测的，而陷阱是由软件生成的中断，或源于出错，或源于用户的特定请求。

陷阱可以由用户程序故意产生，比如调试模式

1.22

Many SMP systems have different levels of caches; one level is local to each processing core, and another level is shared among all processing cores. Why are caching systems designed this way?

设计存储设备的层次结构可以更好的利用各种类型的存储设备，更快速的存储价格也更高，因此可以只在更接近核的位置上对每一个核使用更加快速更加昂贵的存储，而在所有处理器核之间共享相对价格较为便宜的较慢但容量较大的存储，这样可以平衡不同类型存储的优势。

1.23

Consider an SMP system similar to the one shown in Figure 1.6. Illustrate with an example how data residing in memory could in fact have a different value in each of the local caches.

两个不同的CPU，如CPU1和CPU2，先后从内存中读取同一个数据，随后CPU1将本地缓存中的该数据，但是CPU2的本地缓存中的数据没有受到修改，因此两个数据不同。

1.27

Describe some of the challenges of designing operating systems for mobile devices compared with designing operating systems for traditional PCs.

存储容量相对减少
电池容量减少，功耗需要降低
相对于PC端，待机和使用状态转换速度要快
要更加注意安全性
要适应长期驻于后台的多功能设计

Chapter 2

2.1

What is the purpose of system calls?

系统调用提供操作系统服务接口，允许用户进程调用操作系统服务。

2.2

What are the five major activities of an operating system with regard to process management?

创建和删除用户进程和系统进程
暂停和重启进程
提供进程同步机制
提供进程通信机制
提供死锁处理机制

2.3

What are the three major activities of an operating system with regard to memory management?

记录内存的哪部分正在被使用以及被谁使用
当内存可用时，决定哪些进程加载到内存
根据需要分配和释放内存

2.4

What are the three major activities of an operating system with regard to secondary-storage management?

空闲空间管理
存储空间分配
硬盘调度

2.5

What is the purpose of the command interpreter? Why is it usually separate from the kernel?

命令解释器的主要功能是获取并执行用户指定的下一条命令。用于在用户和操作系统之间提供直接的通讯，从用户或命令文件中读取命令，并创建执行这些命令的进程，通常是将它们转换为一个或多个系统调用。

将命令解释器与内核分开，便于对命令解释器进行修改。

2.6

What system calls have to be executed by a command interpreter or shell in order to start a new process?

2024.03.14 修正
注：Linux中并不存在 exec 这个 syscall，有且仅有 execve，exec是 UNIX 的 syscall，并非 POSIX 标准

在Unix/Linux系统中，需要先执行 fork 系统调用，然后再执行 exec / execve 系统调用才能启动新进程。fork 调用克隆当前执行的进程，而 exec / execve 调用基于不同的可执行文件覆盖调用进程上的新进程。

2.7

What is the purpose of system programs?

系统程序充当操作系统的一部分，位于用户界面和系统调用之间，为用户提供基本的系统级功能。

2.8

What is the main advantage of the layered approach to system design? What are the disadvantages of using the layered approach?

Advantage

模块化：每一层只执行其计划执行的任务。
简化调试与验证：由于各层是离散的，所以很容易调试。假设CPU调度层出现错误，因此开发人员只能搜索要调试的特定层，这与所有服务都集中在一起的单片系统不同。
方便更新：在特定层中所做的修改不会影响其他层
不能直接访问硬件：硬件层是设计中存在的最内层。因此，用户可以使用硬件服务，但不能直接修改或访问它，这与用户可以直接访问硬件的简单系统不同。
抽象：每一层都涉及到它自己的功能。因此，其他层的功能和实现对它是抽象的。

Disadvantage

实施较为困难：由于上层只能访问下面的层的服务，所以层间的顺序难以确定。例如，后备存储层使用内存管理层的服务，因此，它必须保持在内存管理层以下。
执行速度较慢：如果一层想要与另一层交互，需要发送一个请求，而且该请求必须遍历两个交互层之间存在的所有层，会大幅增加响应时间。

2.9

List five services provided by an operating system, and explain how each creates convenience for users. In which cases would it be impossible for user-level programs to provide these services? Explain your answer.

version 1

程序执行：操作系统将可执行文件的内容(或部分)加载到内存中并开始执行。用户级程序难以实现正确分配CPU时间
I/O 操作：磁盘、磁带、串行线和其他设备必须以非常低的级别进行通信。用户只需指定设备和要在其上执行的操作，而系统将该请求转换为特定于设备或特定于控制器的命令。用户级程序难以实现只能访问它们有权访问的设备，并且只有在它们未被使用时才能访问它们。
文件系统操作：在文件创建、删除、分配和命名方面有许多用户不应该执行的细节。删除文件需要删除名称文件信息并释放分配的空间，还必须检查保护措施，以确保正确访问文件。用户程序既不能确保遵守保护方法，也不能被信任在文件删除时只分配空闲块和释放块。
通信：系统之间的消息传递需要将消息转换为信息包，通过通信介质传输，发送到网络控制器，并由目的地系统重新组装。必须进行分组排序和数据校正。同样，用户程序可能不会协调对网络设备的访问，或者可能会接收发往其他进程的数据包。
错误检测：错误检测在硬件和软件两个级别上进行。在硬件级别，必须检查所有数据传输，以确保数据在传输过程中没有损坏。必须检查介质上的所有数据，以确保它们在写入介质后没有更改。在软件级别，必须检查介质的数据一致性；例如，已分配和未分配的存储块数量是否与设备上的总数匹配。此时，错误通常与进程无关(例如，磁盘上的数据损坏)，因此必须有一个全局程序(操作系统)来处理所有类型的错误。此外，通过由操作系统处理错误，进程不需要包含代码来捕获和纠正系统上可能出现的所有错误。

version 2

进程管理：操作系统处理进程的创建、调度和终止。这使得多个程序能够同时并有效地运行，通过管理CPU时间，为用户提供便利，使他们可以同时运行多个应用程序，而无需管理资源。用户级程序通常无法有效提供此服务，因为它们无法访问管理CPU调度和进程优先级所需的底层硬件控制。
内存管理：涉及为程序执行时分配和回收内存空间。操作系统确保每个应用程序都有足够的内存，并且不同应用程序的内存空间不会相互干扰。这为用户提供了便利，因为他们不必为他们运行的每个应用程序手动分配内存。用户级程序缺乏直接管理物理内存所需的必要权限，这是确保系统稳定性和安全性所必需的。
文件系统管理：操作系统提供了一种在存储设备上存储、检索和组织文件的方法。这包括管理文件权限和目录。用户在轻松访问、组织和保护他们的文件方面的便利性在于他们无需了解底层存储硬件。用户级程序通常无法提供这些服务，因为需要操作系统有效执行一致和安全的存储资源管理。
设备管理：操作系统通过各自的驱动程序管理设备通信。这包括输入/输出设备，如键盘、鼠标、打印机和显示器。用户从这项服务中受益，因为他们能够无需担心如何在低级别与这些设备通信即可无缝使用这些设备。用户级程序通常无法直接管理硬件设备，因为需要对硬件资源进行统一和安全的访问。
安全性和访问控制：操作系统提供了身份验证、授权、加密和审计等功能。这确保只有授权用户才能访问系统和数据，为用户的信息提供了一个安全的环境。用户级程序很难提供这项服务，因为它们没有执行系统范围内安全策略所需的提升权限。

2.12

The services and functions provided by an operating system can be divided into two main categories. Brieﬂy describe the two categories, and discuss how they differ.

一种是为了提供对用户有帮助的功能，另一种是为了确保系统本身的有效运行。

第一种包括用户界面、程序执行、I/O操作、文件系统操作、通信和错误检测。第二种包括资源分配、记录和保护以及安全。

不同之处在于其目的一种只是服务于用户，而另一种只是服务于系统

2.13

Describe three general methods for passing parameters to the operating system.

将参数置于寄存器（当参数的个数多于寄存器时不可行
将块或表中的参数存储在内存汇总，并将其地址作为参数传递给寄存器
将参数压栈，由操作系统弹出

（2、3两种方法不限制传递的参数的数量和长度

2.15

What are the five major activities of an operating system in regard to file management?

创建和删除文件

文件创建和删除是计算机操作的基础。对于前者，除非以某种形式的文件结构来安排，数据不能以有效的方式存储。对于后者，如果不删除文件并将它们占用的空间重新分配给新文件，存储空间将很快填满。

作为在文件中存储数据的需要的必然结果，文件本身需要被安排在目录或文件夹中，以便能够高效地存储和检索。与文件删除非常类似，为了保持系统整洁，需要删除不必要的目录或文件夹。

由于操作系统允许应用软件使用符号指令执行文件操作，因此操作系统本身需要具有机器级指令集，以便直接与硬件交互。应用程序的符号指令需要由解释器或通过编译应用程序代码转换为机器级指令。操作系统包含用于管理此机器级别文件操作的配置。

映射到外存

操作系统需要能够将文件和文件夹映射到它们在永久存储上的物理位置，以便能够存储和检索它们。这将被记录在某种形式的磁盘目录中，该目录根据操作系统使用的一个或多个文件系统而有所不同。操作系统将包括一种机制，用于定位其已划分文件的单独文件段。

备份文件

计算机的永久存储设备通常包含许多可能发生故障的机械设备，并且存储介质本身可能会降级。操作系统的一个功能是通过在冗余系统中的额外安全和稳定的介质上备份文件来避免数据丢失的风险。

2.16

What are the advantages and disadvantages of using the same system- call interface for manipulating both files and devices?

Advantage
可以像访问文件系统中的文件一样访问每个设备。由于大多数内核通过此文件接口处理设备，因此通过实现特定于硬件的代码来支持此抽象文件接口，添加新的设备驱动程序相对容易。有利于用户程序代码和设备驱动程序代码的开发，用户程序代码可以被编写来以相同的方式访问设备和文件，设备驱动程序代码可以被编写来支持明确定义的API。

Disadvantage
难以在文件访问API的上下文中捕获某些设备的功能，从而导致功能损失或性能损失。其中一些问题可以通过使用ioctl操作来克服，ioctl操作为进程提供通用接口以调用设备上的操作。

2.17

Would it be possible for the user to develop a new command interpreter using the system-call interface provided by the operating system?

可以，命令解释程序允许用户创建和管理进程，还可以确定它们的通信方式(例如通过管道和文件)。而这些功能都可以有系统调用的用户级程序访问，所以用户可以开发新的命令解释程序。

2.18

What are the two models of inter-process communication? What are the strengths and weaknesses of the two approaches?

消息传递模型（message-passing model）：
- strength：消息可以在进程之间直接交换，也可以通过公共邮箱间接交换。适用于数据量较小的情况，并且更容易实现计算机间的通信。
- weakness：它的速度比共享内存模型慢
共享内存模型（shared-memory model）：
- strength：允许更快的速度和更方便的通信
- weakness：在保护和进程之间的同步方面存在一些问题

2.19

Why is the separation of mechanism and policy desirable?

便于对操作系统进行修改。

将mechanism和policy进行分离，policy可以随意进行更改，而mechanism不变，使操作系统更加灵活，便于操作系统更易满足用户需要。

2.21

What is the main advantage of the microkernel approach to system design? How do user programs and system services interact in a microkernel architecture? What are the disadvantages of using the microkernel approach?

Advantage

添加新的服务不需要修改内核
安全性更高
使操作系统更加可靠

用户程序和系统服务通过使用进程间通信机制(例如消息传递)在微内核体系结构中交互。这些消息由操作系统传递。

Disadvantage

与进程间通信相关的开销，以及为了使用户进程和系统服务能够彼此交互而频繁使用操作系统的消息传递功能(上下文切换)。

2.22

What are the advantages of using loadable kernel modules?

可以在需要的时候动态加载模块。如果没有loadable kernel modules，操作系统需要将所有可能用到的功能直接编译到内核中，占据了大量的内存而且其中有很多模块不会被经常使用，并且每次需要新功能时候都需要重新构建并重启内核。

Chapter 3

3.1

Using the program shown in Figure 3.30, explain what the output will be at LINE A.

#include <sys/types.h> 
#include <stdio.h> 
#include <unistd.h>
#include <sys/wait.h>
int value = 5;
int main()
{
    pid_t pid;
    pid = fork();
    if (pid == 0) { /* child process */ value += 15;
    printf("CHILD: value = %d\n",value);
    printf("CHILD: %d\n",&value);
    return 0;
    }
    else if (pid > 0) { /* parent process */
    wait(NULL);
    printf("PARENT: value = %d\n",value); /* LINE A */
    printf("PARENT: %d\n",&value);
    return 0;
} }

运行结果是5

CHILD: value = 20
CHILD: 20652064
PARENT: value = 5
PARENT: 20652064

由此可得：**子进程产生时会拷贝父进程的变量的值，然后生成自己的一份。**两者的指针是相同的（逻辑地址相同），但是属于不同进程空间，会映射到不同的物理内存，是相互独立的。

3.5

When a process creates a new process using the fork() operation, which of the following states is shared between the parent process and the child process?

共享内存段会被共享，堆和栈都会被在子进程被创建一个副本

3.8

Describe the differences among short-term, medium-term, and long- term scheduling.

Long Term	Short Term	Medium Term
作业调度程序	CPU调度程序	用于交换
速度较短期调度程序慢	速度非常快	速度介于两者之间
用于控制多道程序程度	用于从准备执行的进程中选择进程送入CPU执行	将进程从内存中移出，从而降低多道程序程度

Long Term Scheduler

被称为作业调度程序
用于从大容量存储设备的缓冲池中选择进程加载到内存中，以便执行
用于控制多道程序程度。
如果多道程序设计的程度是稳定的，那么进程创建的平均速度必须等于进程离开系统的平均速度。
在一些分时系统中通常没有长期调度程序
当流程将状态从NEW更改为READY时，将使用长期调度程序

Short Term Scheduler

被称为CPU调度程序
将就绪状态更改为进程的运行状态。
CPU调度器从准备执行的进程中选择进程，并将CPU分配给其中一个进程。
执行频率最高
执行速度最快

Medium Term Scheduler

用于交换
用于从内存中移出和移入进程
降低多道程序程度

3.9

Describe the actions taken by a kernel to context-switch between processes.

中断发生后，操作系统首先保存当前执行进程的PC和用户堆栈指针，并将控制权交给内核中断处理程序
中断处理程序将其余寄存器和其他状态保存至PCB中
操作系统调用调度程序确定下一个要执行的进程
操作系统从下一个进程的PCB中加载其信息，将处理器还原至之前中断的状态，之后重新继续执行。

3.12

Including the initial parent process, how many processes are created by the program shown in Figure 3.32?

#include <stdio.h>
#include <unistd.h>

int main()
{
    int i;
    for (i = 0; i < 4; i++)
        fork();
    return 0;
}

由图中的第一代进程有1个，第二代进程有4个，第三代进程有6个，第四代进程有4个，第五代进程有1个

一共1 + 4 + 6 + 4 + 1 = 16个

3.13

Explain the circumstances under which which the line of code marked printf("LINE J") in Figure 3.33 will be reached.

#include <sys/types.h> 
#include <stdio.h> 
#include <unistd.h>

int main()
{
    pid_t pid;  /* fork a child process */
    pid = fork();
    if (pid < 0) { /* error occurred */ 
        fprintf(stderr, "Fork Failed"); 
        return 1;
    }
    else if (pid == 0) { /* child process */
        execlp("/bin/ls","ls",NULL);
        printf("LINE J");
    }
    else { /* parent process */
        /* parent will wait for the child to complete */
        wait(NULL);
        printf("Child Complete");
    }
    return 0;
}

execlp() 函数如果执行成功则函数不会返回, 执行失败则直接返回-1, 失败原因存于errno 中.

因此如果调用 execlp() 函数执行成功，则不会到达“LINE J”，如果 execlp() 执行失败，到达“LINE J”

3.14

Using the program in Figure 3.34, identify the values of pid at lines A, B, C, and D. (Assume that the actual pids of the parent and child are 2600 and 2603, respectively.)

#include <sys/types.h> 
#include <stdio.h> 
#include <unistd.h>

int main()
{
    pid_t pid, pid1;
    /* fork a child process */
    pid = fork();
    if (pid < 0) { /* error occurred */ 
        fprintf(stderr, "Fork Failed"); 
        return 1;   
    }
    else if (pid == 0) { /* child process */
        pid1 = getpid();
        printf("child: pid = %d",pid); /* A */
        printf("child: pid1 = %d",pid1); /* B */
    }
    else { /* parent process */
        pid1 = getpid();
        printf("parent: pid = %d",pid); /* C */
        printf("parent: pid1 = %d",pid1); /* D */
        wait(NULL); 
    }
    return 0;
}

pid = fork()有两个返回值，在父进程中返回子进程id，在子进程中返回0（用于区分父进程与子进程，非有效进程id），在父进程中getpid（）获取父进程id，子进程中getpid（）获取子进程id

所以有如下结果：

parent: pid = 2603
parent: pid1 = 2600
child: pid = 0
child: pid1 = 2603

经过学习还可以发现，如果父进程wait（null），则子进程输出的getppid（）会是父进程的进程号，但是如果主进程不wait子进程，子进程输出的getppid（）就是1。

#include <sys/types.h> 
#include<stdlib.h>
#include <stdio.h> 
#include <unistd.h>
#include <sys/wait.h>

int main()
{
    pid_t pid, pid1;
    /* fork a child process */
    pid = fork();
    if (pid < 0) { /* error occurred */ 
        fprintf(stderr, "Fork Failed"); 
        return 1;   
    }
    else if (pid == 0) { /* child process */
        pid1 = getpid();
        printf("child: pid = %d\n",pid); /* A */
        printf("child: pid1 = %d\n",pid1); /* B */
        printf("parent: %d\n",getppid());
    }
    else { /* parent process */
        pid1 = getpid();
        printf("parent: pid = %d\n",pid); /* C */
        printf("parent: pid1 = %d\n",pid1); /* D */
        wait(NULL);
    }
    return 0;
}

原因如下：

因为如果父进程不wait子进程返回，在父进程终止之后，子进程就会成为孤儿进程，成为init进程的子进程，而init进程的pid为1

3.17

Using the program shown in Figure 3.35, explain what the output will be at lines X and Y.

#include <sys/types.h> 
#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>

#define SIZE 5
int nums[SIZE] = {0,1,2,3,4};

int main()
{
    int i;
    pid_t pid;
    pid = fork();
    if (pid == 0) {
        for (i = 0; i < SIZE; i++) {
            nums[i] *= -i;
            printf("CHILD: %d ",nums[i]); /* LINE X */
        }      
    }
    else if (pid > 0) { 
            wait(NULL);
        for (i = 0; i < SIZE; i++)
            printf("PARENT: %d ",nums[i]); /* LINE Y */
    }
    return 0;
}

输出如下：

X: CHILD: 0 CHILD: -1 CHILD: -4 CHILD: -9 CHILD: -16 
Y: PARENT: 0 PARENT: 1 PARENT: 2 PARENT: 3 PARENT: 4

因为子进程是父进程的副本，因此子对象所做的任何更改都将发生在其数据副本中，而不会反映在父对象中。因此，子对象在X行输出的值是0、-1、-4、-9、-16。父项在Y行的输出值为0、1、2、3、4

Chapter 4

4.2

What are two differences between user-level threads and kernel-level threads? Under what circumstances is one type better than the other?

User-level Thread

用户级线程由用户实现，内核不知道这些线程的存在。它将它们当作单线程进程来处理。用户级线程很小，而且比内核级线程快得多。它们由程序计数器(PC)、堆栈、寄存器和一个小的进程控制块表示。此外，用户级线程的同步与内核无关。

Advantages of User-Level Threads

用户级线程比内核级线程更容易、更快地创建、更容易地管理。
用户级线程可以在任何操作系统上运行。
在用户级线程中切换线程不需要内核模式权限。

Disadvantages of User-Level Threads

用户级线程中的多线程应用程序对应一个内核级线程，无法在多处理器中实现并行化。
如果一个用户级线程执行阻塞操作，则整个进程被阻塞。

Kernel-Level Threads

内核级线程由操作系统直接处理，线程管理由内核完成。线程以及线程的上下文信息都由内核管理。正因为如此，内核级线程比用户级线程慢。

Advantages of Kernel-Level Threads

同一进程的多个线程可以在不同的处理器上以内核级线程进行调度。
内核例程也可以是多线程的。
如果一个内核级线程被阻塞，则内核可以调度同一进程的另一个线程。

Disadvantages of Kernel-Level Threads

进程中将控制权从一个线程转移到另一个线程，需要切换到内核模式。
与用户级线程相比，内核级线程的创建和管理速度较慢。

综上所述，在多线程时使用Kernel-Level Threads更好，在控制权时常需要切换和单线程时使用User-level Thread更好

4.4

What resources are used when a thread is created? How do they differ from those used when a process is created?

创建线程时需要分配一个数据结构TCB（thread control block）来保存寄存器集、堆栈、状态和优先级，统一进程的线程之间共享内存，而创建一个进程时需要分配一个数据结构PCB（process control block）包含内存映射、打开文件列表和环境变量。线程是进程的一部分，一个进程中可以有多个线程，因此创建进程意味着需要更大的开销。

4.7

Under what circumstances does a multithreaded solution using multiple kernel threads provide better performance than a single-threaded solution on a single-processor system?

当内核线程出现页面故障时，可以切换另一个内核线程，以有用的方式使用交错时间。另一方面，当发生页面故障时，单线程进程将无法执行有用的工作。因此，在程序可能经常出现页面故障或不得不等待其他系统事件的情况下，即使在单处理器系统上，多线程解决方案也会表现得更好。

4.8

Which of the following components of program state are shared across threads in a multithreaded process?
a. Register values
b. Heap memory
c. Global variables
d. Stack memory

b. Heap memory和c. Global variables，创建线程是会分配一个TCB保存程序计数器、栈、寄存器组和线程ID。

4.9

Can a multithreaded solution using multiple user-level threads achieve better performance on a multiprocessor system than on a single- processor system? Explain.

不能，因为用户级多线程由线程池管理，操作系统只能看到一个进程，因此只能使用到一个内核线程，只会用到一个处理器，多处理器的优势无法体现。

4.14

A system with two dual-core processors has four processors available for scheduling. A CPU-intensive application is running on this system. All input is performed at program start-up, when a single file must be opened. Similarly, all output is performed just before the program terminates, when the program results must be written to a single file. Between startup and termination, the program is entirely CPU-bound. Your task is to improve the performance of this application by multithreading it. The application runs on a system that uses the one-to-one threading model (each user thread maps to a kernel thread).

• How many threads will you create to perform the input and output? Explain.
• How many threads will you create for the CPU-intensive portion of the application? Explain.

1个输入线程、1个输出线程，因为输入输出只需要一个线程进行处理，创建更多的线程没有意义并且会造成开销
4个线程，因为处理器总共只有4个核，更多的线程也无法同时运行

4.15

Consider the following code segment:

pid t pid;

pid = fork();
if (pid == 0) { /* child process */
    fork();
    thread create( . . .);
}
fork();

a. How many unique processes are created?

b. How many unique threads are created?

父进程创建两个子进程，第一个子进程创建三个子进程，共有6个进程
第一个子进程创建一个线程，第一个子进程的一个子进程创建一个线程，共有2个线程

4.16

As described in Section 4.7.2, Linux does not distinguish between processes and threads. Instead, Linux treats both in the same way, allowing a task to be more akin to a process or a thread depending on the set of flags passed to the clone() system call. However, other operating systems, such as Windows, treat processes and threads differently. Typically, such systems use a notation in which the data structure for a process contains pointers to the separate threads belonging to the process. Contrast these two approaches for modeling processes and threads within the kernel.

Linux操作系统将线程和进程视为任务，不进行区分，相比之下，Windows操作系统的线程和流程不同。

优点：

简化操作系统代码
Linux操作系统中的调度器不需要特殊代码来检查与进程相关的线程。
在调度期间，它可以平等的看待进程和线程

缺点：

这种一致性可能会使以直接方式施加进程范围的资源约束变得更加困难
识别哪些线程对应于哪个进程并执行相关的记账任务需要一些额外的复杂性

4.17

The program shown in Figure 4.16 uses the Pthreads API. What would be the output from the program at LINE C and LINE P?

#include <pthread.h>
#include <stdio.h> 
#include <types.h>

int value = 0;
void *runner(void *param); /* the thread */
int main(int argc, char *argv[])
{
    pid_t pid;
    pthread_t tid; 
    pthread_attr_t attr;
    pid = fork();
    if (pid == 0) { /* child process */ 
        pthread_attr_init(&attr);
        pthread_create(&tid,&attr,runner,NULL); 
    pthread_join(tid,NULL);
    printf("CHILD: value = %d",value); /* LINE C */
    }
    else if (pid > 0) { /* parent process */
        wait(NULL);
    printf("PARENT: value = %d",value); /* LINE P */
    } 
}
void *runner(void *param) { 
    value = 5;
    pthread_exit(0);
}

输出为：

CHILD: value = 5PARENT: value = 0

因为进程之间不共享全局变量，同一进程的线程之间共享全局变量

4.21

Write a multithreaded program that calculates various statistical values for a list of numbers. This program will be passed a series of numbers on the command line and will then create three separate worker threads. One thread will determine the average of the numbers, the second will determine the maximum value, and the third will determine the minimum value. For example, suppose your program is passed the integers
90 81 78 95 79 72 85
The program will report
The average value is 82
The minimum value is 72
The maximum value is 95
The variables representing the average, minimum, and maximum values will be stored globally. The worker threads will set these values, and the parent thread will output the values once the workers have exited. (We could obviously expand this program by creating additional threads that determine other statistical values, such as median and standard deviation.)

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

int average = 0;
int min = 65535;
int max = 0;
int array[100];
int n;

void *find_min(){
    int i;
    for(i = 0; i < n; i++){
        if(array[i] < min){
            min = array[i];
        }
    }
    pthread_exit(NULL);
}

void *find_max(){
    int i;
    for(i = 0; i < n; i++){
        if(array[i] > max){
            max = array[i];
        }
    }
    pthread_exit(NULL);
}

void *find_average(){
    int i;
    for(i = 0; i < n; i++){
        average += array[i];
    }
    average = average / n;
    pthread_exit(NULL);
}

int main(){
    printf("Enter the number of elements in the array: ");
    scanf("%d", &n);
    printf("Enter the elements of the array: ");
    for(int i = 0; i < n; i++){
        scanf("%d", &array[i]);
    }
    pthread_t thread1, thread2, thread3;
    pthread_create(&thread1, NULL, find_min, NULL);
    pthread_create(&thread2, NULL, find_max, NULL);
    pthread_create(&thread3, NULL, find_average, NULL);
    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);
    pthread_join(thread3, NULL);

    printf("The average value is: %d\n", average);
    printf("The minimum value is: %d\n", min);
    printf("The maximum value is: %d\n", max);
    
}

5.4

Explain why spinlocks are not appropriate for single-processor systems yet are often used in multiprocessor systems.

在单处理器系统中，一次只能有一个线程running，自旋锁会导致线程一直空转（忙等待），直到锁被释放，但是持有锁的线程无法运行，锁就无法被释放，直到时间切片结束。

在多处理器系统中，一次可以有多个线程同时运行，持有锁的线程和等待锁的线程可以同时运行，因此在合理的时间内持有锁的进程会释放锁，等待锁的进程可以获取到锁

5.5

Show that, if the wait() and signal() semaphore operations are not executed atomically, then mutual exclusion may be violated.

如果wait()和signal()没有原子执行，则有可能在同一时间wait()和signal()被同时调用，最终信号量的值无法预测，造成无法预测的结果

5.10

Explain why implementing synchronization primitives by disabling interrupts is not appropriate in a single-processor system if the syn- chronization primitives are to be used in user-level programs.

系统时钟是通过中断进行正常运行的，如果用户级程序能够禁止中断，则系统时钟将无法正常运行，从而导致上下文切换可能无法正常运行，该程序可以一直占用CPU

5.11

Explain why interrupts are not appropriate for implementing synchronization primitives in multiprocessor systems.

因为消息要传递到所有处理器，多处理器的中断禁止十分耗时，效率较低。

5.15

Consider how to implement a mutex lock using an atomic hardware instruction. Assume that the following structure defining the mutex lock is available：

(available == 0) indicates that the lock is available, and a value of 1 indicates that the lock is unavailable. Using this struct, illustrate how the following functions can be implemented using the test and set() and compare and swap() instructions:

void acquire(lock *mutex)
void release(lock *mutex)

Be sure to include any initialization that may be necessary.

// initialization
mutex->available = 0;

// acquire using compare and swap()
void acquire(lock *mutex) {
    while (compare_and_swap(&mutex->available, 0, 1) != 0);
    return;
}

// acquire using test and set()
void acquire(lock *mutex) {
    while (test_and_set(&mutex->available) != 0);
    return;
}
void release(lock *mutex) {
    mutex->available = 0;
    return;
}

5.17

Assume that a system has multiple processing cores. For each of the following scenarios, describe which is a better locking mechanism—a spinlock or a mutex lock where waiting processes sleep while waiting for the lock to become available:

The lock is to be held for a short duration.

The lock is to be held for a long duration.

A thread may be put to sleep while holding the lock.

spinlock
Mutex lock
Mutex lock

5.18

Assume that a context switch takes T time. Suggest an upper bound (in terms of T) for holding a spinlock. If the spinlock is held for any longer, a mutex lock (where waiting threads are put to sleep) is a better alternative.

持有自旋锁的上限应为2T，因为上下文切换需要2T，如果大于2T，使用互斥锁使等待线程睡眠更好

5.20

Consider the code example for allocating and releasing processes shown in Figure 5.23.

a. Identify the race condition(s).

b. Assume you have a mutex lock named mutex with the operations acquire() and release(). Indicate where the locking needs to be placed to prevent the race condition(s).

c. Could we replace the integer variable with an atomic integer?

a. 对于变量number_of_process存在竞争条件

b.在每个函数的开始acquire()锁，在每一个函数的结束 release()锁

c. 不能，因为是竞争发生在allocate_process()函数中，其中number_of_process首先在if语句中测试，然后根据测试值进行更新。测试时，number_of_process=254，但由于竞争条件，在再次增加之前，另一个线程可能将其设置为255。

5.23

Show how to implement the wait() and signal() semaphore operations in multiprocessor environments using the test and set() instruction. The solution should exhibit minimal busy waiting.

int guard = 0;
int semaphore_value = 0;
void wait(){
    while(test_and_set(&guard) == 1);
    if (semaphore_value = 0){
      atomically add process to a queue of processes waiting for the semaphore and set guard to 0;
    }
    else
    {
      semaphore_value--;
      guard = 0;
    }
}

void signal(){
    while(test_and_set(&guard) == 1);
    if (semaphore_value = 0 && there is a process on the wait queue){
      wake up the first process in the queue of waiting processes
    }
    else
    {
      semaphore_value++;
    }
    guard = 0;
}

5.28

Discuss the tradeoff between fairness and throughput of operations in the readers–writers problem. Propose a method for solving the readers–writers problem without causing starvation.

通过偏袒多个读者而不是允许单个作者独家访问共享值，从而提高了读者-作者问题的吞吐量。另一方面，p偏袒读者可能会导致作家挨饿。

当读者到达并注意到另一个读者正在访问数据库，那么只有当没有等待的作者时，它才会进入关键部分。

通过保留与等待过程相关的时间戳，可以避免读者/作家问题的饥饿。当作家完成任务时，它会唤醒等待时间最长的进程。

6.2

Explain the difference between preemptive and nonpreemptive scheduling.

抢占式调度允许在进程从运行状态转变为就绪状态和从等待状态转变为就绪状态时进行调度，而非抢占式调度只允许在进程从运行状态转变为等待状态和终止时进行调度。

6.3

Suppose that the following processes arrive for execution at the times indicated. Each process will run for the amount of time listed. In answering the questions, use nonpreemptive scheduling, and base all decisions on the information you have at the time the decision must be made.

Process	Arrival time	Burst time
P1	0.0	8
P2	0.4	4
P3	1.0	1

What is the average turnaround time for these processes with the FCFS scheduling algorithm?

What is the average turnaround time for these processes with the SJF scheduling algorithm?

The SJF algorithm is supposed to improve performance, but notice that we chose to run process P1 at time 0 because we did not know that two shorter processes would arrive soon. Compute what the average turnaround time will be if the CPU is left idle for the first 1 unit and then SJF scheduling is used. Remember that processes P1 and P2 are waiting during this idle time, so their waiting time may increase. This algorithm could be called future-knowledge scheduling.

( 8 + (12 - 0.4) + (13 - 1)) / 3 = 10.53
( 8 + (9 - 1) + (13 – 0.4)) / 3 = 9.53
((2 - 1) + ( 6 – 0.4 ) + ( 14 - 0)) / 3 = 6.87

6.6

Suppose that a scheduling algorithm (at the level of short-term CPU scheduling) favors those processes that have used the least processor time in the recent past. Why will this algorithm favor I/O-bound programs and yet not permanently starve CPU-bound programs?

因为I/O密集型程序的所需要的CPU事件较少，所以多优先执行，但是又由于这类程序有大量的I/O，所以在I/O密集型程序等待I/O的时候，可以执行CPU密集型程序，从而CPU密集型程序不会产生饥饿。

6.9

The traditional UNIX scheduler enforces an inverse relationship between priority numbers and priorities: the higher the number, the lower the priority. The scheduler recalculates process priorities once per second using the following function:
Priority = (recent CPU usage / 2) + base
where base = 60 and recent CPU usage refers to a value indicating how often a process has used the CPU since priorities were last recalculated.
Assume that recent CPU usage for process P1 is 40, for process P2 is 18, and for process P3 is 10. What will be the new priorities for these three processes when priorities are recalculated? Based on this information, does the traditional UNIX scheduler raise or lower the relative priority of a CPU-bound process?

P1 = 80
P2 = 69
P3 = 65

降低优先级

6.10

Why is it important for the scheduler to distinguish I/O-bound programs from CPU-bound programs?

I/O密集型程序使用大量的I/O而只使用少量的计算，而CPU密集型程序很少产生I/O请求，需要大量的计算。

将两者区分可以赋予I/O密集型程序更高的优先级，并且允许其在CPU密集型程序之前允许，从而更好的利用计算机资源。

6.13

In Chapter 5, we discussed possible race conditions on various kernel data structures. Most scheduling algorithms maintain a run queue, which lists processes eligible to run on a processor. On multicore systems, there are two general options: (1) each processing core has its own run queue, or (2) a single run queue is shared by all processing cores. What are the advantages and disadvantages of each of these approaches?

（1）的优点在于多个处理核之间不会竞争同一个进程并且能够更好的利用处理器的亲和性，（2）不具备这些优点，而（2）可以更好的进行负载平衡，但（1）需要进行周期性检查并进行推拉迁移才能负载平衡

6.16

Consider the following set of processes, with the length of the CPU burst given in milliseconds:

The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0.

Draw four Gantt charts that illustrate the execution of these processes using the following scheduling algorithms: FCFS, SJF, nonpreemptive priority (a larger priority number implies a higher priority), and RR (quantum = 2).
What is the turnaround time of each process for each of the scheduling algorithms in part a?
What is the waiting time of each process for each of these schedul- ing algorithms?
Which of the algorithms results in the minimum average waiting time (over all processes)?

6.17

The following processes are being scheduled using a preemptive, round-robin scheduling algorithm. Each process is assigned a numerical priority, with a higher number indicating a higher relative priority. In addition to the processes listed below, the system also has an idle task (which consumes no CPU resources and is identified as Pidle ). This task has priority 0 and is scheduled whenever the system has no other available processes to run. The length of a time quantum is 10 units. If a process is preempted by a higher-priority process, the preempted process is placed at the end of the queue.
a. Show the scheduling order of the processes using a Gantt chart.
b. What is the turnaround time for each process?
c. What is the waiting time for each process?
d. What is the CPU utilization rate?

a.
b. P1: 20-0 =20, P2: 80-25 = 55, P3: 90 - 30 = 60, P4: 75-60 = 15, P5: 120-100 = 20, P6: 115-105 = 10
c. P1: 0, p2: 40, P3: 35, P4: 0, P5: 10, P6:0
d. 105/120 = 87.5%

6.19

Which of the following scheduling algorithm could result in starvation?

First-come, first-served

Shortest job first

Round robin

Priority

最短作业优先调度 Shortest job first
优先级调度 priority

6.21

Consider a system running ten I/O-bound tasks and one CPU-bound task. Assume that the I/O-bound tasks issue an I/O operation once for every millisecond of CPU computing and that each I/O operation takes 10 milliseconds to complete. Also assume that the context-switching overhead is 0.1 millisecond and that all processes are long-running tasks. Describe the CPU utilization for a round-robin scheduler when:
a. The time quantum is 1 millisecond
b.The time quantum is 10 milliseconds

a. 1/1.1=91%
b. 20/21.1*100=95%

6.23

Consider a preemptive priority scheduling algorithm based on dynami- cally changing priorities. Larger priority numbers imply higher priority. When a process is waiting for the CPU (in the ready queue, but not running), its priority changes at a rate $\alpha$ . When it is running, its priority changes at a rate $\beta$ . All processes are given a priority of 0 when they enter the ready queue. The parameters $\alpha$ and $\beta$ can be set to give many different scheduling algorithms.

What is the algorithm that results from $\beta$ > $\alpha$ > 0?

What is the algorithm that results from $\alpha$ < $\beta$ < 0?

FCFS

准备就绪队列中的所有进程都具有相同的初始优先级0。他们的优先级以相同的速度增加a（a>0）。因此，进程越早进入就绪队列，优先级就越高。一旦优先级最高的进程（与就绪队列中的其他进程相比先到先得）运行，其优先级的增加速度（b>a>0）高于准备就绪队列中这些进程的优先级。因此，没有其他过程会抢占它，直到运行完成。

LCFS

准备就绪队列中的所有进程都具有相同的初始优先级0。他们的优先级以相同的速度下降a（a<0）。因此，进程越早进入就绪队列，其优先级就越低。一旦具有最高优先级的进程（与就绪队列中的其他进程相比，最后来）运行，就绪队列中的其他进程都不会抢占它，因为它的优先级下降速度低于准备就绪队列中这些进程的优先级（a<b<0）。但任何即将到来的新进程都将抢占，因为新进程的优先级为0，这是尽可能高的优先级。

6.28

Assume that two tasks A and B are running on a Linux system. The nice values of A and B are −5 and +5, respectively. Using the CFS scheduler as a guide, describe how the respective values of vruntime vary between the two processes given each of the following scenarios:

Both A and B are CPU-bound.

A is I/O-bound, and B is CPU-bound.

A is CPU-bound, and B is I/O-bound.

由于A的优先级高于B，因此A的vruntime值较B更小（A减小，B增大）。如果A和B都是CPU密集型（也就是说，只要分配给它们，它们都会使用CPU），A的vruntime比B小，因此A运行的优先级更高。
A的vruntime比B的小得多，因为(1)由于优先级的差异，A的vruntime值较B更小；(2)A需要的CPU时间更少，A的vruntime值较B更小
无法判断，因为(1)由于优先级的差异，A的vruntime值较B更小；(2)A需要的CPU时间更少，A的vruntime值较B更大，两个因素相互矛盾。

代码可重入

可重入的定义

简单定义:"可以正确重复使用"，有两个关键：1，可以重复使用；2，并能正确使用。意味着在多次执行的时候能得到正确的值，并不受其他调用的影响。
官方定义：若一个程序或子程序可以“在任意时刻被中断然后操作系统调度执行另外一段代码，这段代码又调用了该子程序不会出错”，则称其为可重入（reentrant或re-entrant）的。即当该子程序正在运行时，执行线程可以再次进入并执行它，仍然获得符合设计时预期的结果。与多线程并发执行的线程安全不同，可重入强调对单个线程执行时重新进入同一个子程序仍然是安全的。
这里也有一段比较好的英文阐释：
A computer program or routine is described as reentrant if it can be safely called again before its previous invocation has been completed (i.e it can be safely executed concurrently)
可重入函数主要用于多任务环境中，一个可重入的函数简单来说就是可以被中断的函数，也就是说，可以在这个函数执行的任何时刻中断它，转入OS调度下去执行另外一段代码，而返回控制时不会出现什么错误；而不可重入的函数由于使用了一些系统资源，比如全局变量区，中断向量表等，所以它如果被中断的话，可能会出现问题，这类函数是不能运行在多任务环境下的。

产生背景

可重入概念是在单线程操作系统的时代提出的。一个子程序的重入，可能由于自身原因，如执行了jmp或者call，类似于子程序的递归调用；或者由于操作系统的中断响应。UNIX系统的signal的处理，即子程序被中断处理程序或者signal处理程序调用。所以，可重入也可称作“异步信号安全”。这里的异步是指信号中断可发生在任意时刻。重入的子程序，按照后进先出线性序依次执行。

编写可重入代码注意的条件

若一个函数是可重入的，则该函数应当满足下述条件：

不能含有静态（全局）非常量数据。
不能返回静态（全局）非常量数据的地址。
只能处理由调用者提供的数据。
不能依赖于单实例模式资源的锁。
调用(call)的函数也必需是可重入的。
上述条件就是要求可重入函数使用的所有变量都保存在呼叫堆叠的当前函数栈（frame）上，因此同一执行线程重入执行该函数时加载了新的函数帧，与前一次执行该函数时使用的函数帧不冲突、不互相覆盖，从而保证了可重入执行安全。

多“用户/对象/进程优先级”以及多进程（Multiple processes），一般会使得对可重入代码的控制变得复杂。同时，IO代码通常不是可重入的，因为他们依赖于像磁盘这样共享的、单独的（类似编程中的静态、全域）资源。

与线程安全的关系

可重入与线程安全两个概念都关系到函数处理资源的方式。但是，他们有重大区别：可重入概念会影响函数的外部接口，而线程安全只关心函数的实现。大多数情况下，要将不可重入函数改为可重入的，需要修改函数接口，使得所有的数据都通过函数的调用者提供。要将非线程安全的函数改为线程安全的，则只需要修改函数的实现部分。一般通过加入同步机制以保护共享的资源，使之不会被几个线程同时访问。

操作系统背景与CPU调度策略：
可重入是在单线程操作系统背景下，重入的函数或者子程序，按照后进先出的线性序依次执行完毕。

多线程执行的函数或子程序，各个线程的执行时机是由操作系统调度，不可预期的，但是该函数的每个执行线程都会不时的获得CPU的时间片，不断向前推进执行进度。可重入函数未必是线程安全的；线程安全函数未必是可重入的。

例如，一个函数打开某个文件并读入数据。这个函数是可重入的，因为它的多个实例同时执行不会造成冲突；但它不是线程安全的，因为在它读入文件时可能有别的线程正在修改该文件，为了线程安全必须对文件加“同步锁”。
另一个例子，函数在它的函数体内部访问共享资源使用了加锁、解锁操作，所以它是线程安全的，但是却不可重入。因为若该函数一个实例运行到已经执行加锁但未执行解锁时被停下来，系统又启动该函数的另外一个实例，则新的实例在加锁处将转入等待。如果该函数是一个中断处理服务，在中断处理时又发生新的中断将导致资源死锁。fprintf函数就是线程安全但不可重入。

可重入锁

可重入锁也叫递归锁，它俩等同于一回事，指的是同一线程外层函数获得锁之后，内层递归函数仍然能获得该锁的代码，同一线程在外层方法获取锁的时候，再进入内层方法会自动获取锁。也就是说，线程可以进入任何一个它已经拥有的锁所同步着的代码块。ReentrantLock 和 synchronized 就是典型的可重入锁！

8.1

Name two differences between logical and physical addresses.

逻辑地址和物理地址的基本区别是，逻辑地址是由CPU从正在运行的程序的角度生成的。另一方面，物理地址是内存单元中存在的位置，可以物理访问。

CPU为程序生成的所有逻辑地址集称为逻辑地址空间。然而，映射到相应逻辑地址的所有物理地址的集合称为物理地址空间。编译时和加载时地址绑定方法生成相同的逻辑地址和物理地址，然而执行时的地址绑定方案生成不同的逻辑地址和物理地址

8.4

Consider a logical address space of 64 pages of 1,024 words each, mapped onto a physical memory of 32 frames.

How many bits are there in the logical address?
How many bits are there in the physical address?
16 bits
15 bits

8.5

What is the effect of allowing two entries in a page table to point to the same page frame in memory? Explain how this effect could be used to decrease the amount of time needed to copy a large amount of memory from one place to another. What effect would updating some byte on the one page have on the other page?

通过允许页面表中的两个条目指向内存中的同一页面帧，用户可以共享代码和数据。如果代码重新输入，可以通过共享文本编辑器、编译器和数据库系统等大型程序来节省大量内存空间。通过让不同的页面表指向相同的内存位置，可以“复制”大量内存。

然而，共享非重新输入代码或数据意味着任何有权访问该代码的用户都可以对其进行修改，这些修改将反映在其他用户的“副本”中。因此，应该使用“写时复制”。

8.6

Describe a mechanism by which one segment could belong to the address space of two different processes.

由于段表是基址寄存器的集合，当两个不同进程的段表中的条目指向同一个物理位置时，段可以被共享。这两个段表必须有相同的基址指针，而且两个进程中的共享段号必须相同。

8.7

Sharing segments among processes without requiring that they have the same segment number is possible in a dynamically linked segmentation system.

Define a system that allows static linking and sharing of segments without requiring that the segment numbers be the same.
Describe a paging scheme that allows pages to be shared without requiring that the page numbers be the same.
可以通过共享页来实现，不同的段指向相同的页
不同页映射到相同的帧

8.9

Explain the difference between internal and external fragmentation.

分配给进程固定大小的内存块时，如果分配的内存比进程需要内存大，就会产生内部碎片，这种碎片是被进程占用但是不被进程使用的区域，在这段空间释放之前，操作系统无法使用这段空间

当可变大小的内存空间被分配给进程时，就会产生外部碎片，将空闲内存空间分为小的片段，当总的可用内存之和可以满足请求但是并不连续时，就会产生外部碎片问题。

8.12

Most systems allow a program to allocate more memory to its address space during execution. Allocation of data in the heap segments of programs is an example of such allocated memory. What is required to support dynamic memory allocation in the following schemes?

Contiguous memory allocation
Pure segmentation
Pure paging
程序全部重新分配
分配拓展段
分配新分页

8.13

Compare the memory organization schemes of contiguous memory allocation, pure segmentation, and pure paging with respect to the following issues:

a. External fragmentation

b. Internal fragmentation

连续内存分配：有；纯分段：有；纯分页：无
连续内存分配：无；纯分段：无；纯分页：有
连续内存分配：不行；纯分段：可以；纯分页：可以

8.14

On a system with paging, a process cannot access memory that it does not own. Why? How could the operating system allow access to other memory? Why should it or should it not?

分页系统上的一个地址是一个逻辑页号和一个偏移量。物理页是通过搜索一个基于逻辑页号的表来产生一个物理页号的。因为操作系统控制着这个表的内容，它可以限制一个进程只访问分配给该进程的物理页。一个进程不可能引用它不拥有的页面，因为该页面不在页表中。为了允许这种访问，操作系统只需要允许非进程内存的条目被添加到进程的页表中。当两个或更多的进程需要交换数据时，这是非常有用的，它们只是对相同的物理地址（可能在不同的逻辑地址）进行读写。这使得进程间的通信非常有效。

8.15

Explain why mobile operating systems such as iOS and Android do not support swapping.

闪存容量小，写入次数有限制，闪存与内存之间的吞吐量差。

8.18

Explain why address space identifiers (ASIDs) are used.

ASIDs在TLB中提供了地址空间保护，并支持TLB条目同时用于几个不同的进程。

如果TLB不支持独立的ASID，那么每次选择新的页表（上下文切换）时，必须刷新TLB以确保下一个执行进程不会使用错误的翻译信息。

8.19

Program binaries in many systems are typically structured as follows. Code is stored starting with a small, fixed virtual address, such as 0. The code segment is followed by the data segment that is used for storing the program variables. When the program starts executing, the stack is allocated at the other end of the virtual address space and is allowed to grow toward lower virtual addresses. What is the significance of this structure for the following schemes?

Contiguous memory allocation
Pure segmentation
Pure paging
固定大小防止重新分配内存
方便拓展
方便新分配

8.20

Assuming a 1-KB page size, what are the page numbers and offsets for the following address references (provided as decimal numbers):

a. 3085

b. 42095

c. 215201

d. 650000

e. 2000001

Logical address (decimal)	Page # (decimal)	Offset (decimal)
3085	3	13
42095	41	111
215201	210	161
650000	634	784
2000001	1953	129

8.21

The BTV operating system has a 21-bit virtual address, yet on certain embedded devices, it has only a 16-bit physical address. It also has a 2-KB page size. How many entries are there in each of the following?

A conventional, single-level page table
An inverted page table
2^21/(2*1024)=1024
2^16/(2*1024)=32

8.23

Consider a logical address space of 256 pages with a 4-KB page size, mapped onto a physical memory of 64 frames.

How many bits are required in the logical address?
How many bits are required in the physical address?
12 + 8 = 20 bits
12 + 6 = 18 bits

8.28

Consider the following segment table:

![image-20220612002441323](/Users/ouritsusei/Documents/学习笔记/操作系统/Chapter 8.assets/image-20220612002441323.png)

What are the physical addresses for the following logical addresses?

a. 0,430

b. 1,10

c. 2,500

d. 3,400

e. 4,112

219+430=649
2300+10=2310
非法
1327+400=1727
非法

8.29

What is the purpose of paging the page tables?

页表本身可能会很大，以至于通过分页来分页表，可以简化内存分配问题（通过确保一切被分配为固定大小的页面，而不是可变大小的块），并且还启用交换当前未使用的页表部分。与之相关的缺点是，地址转换可能需要更多的内存访问。

9.1

Under what circumstances do page faults occur? Describe the actions taken by the operating system when a page fault occurs.

当一个进程试图访问一个在页表条目中被标记为无效的页时，就会发生页故障。
页面故障会产生一个中断，在特权模式下调用操作系统的代码。然后操作系统检查一些内部表（通常与该进程的进程控制块一起保存）以确定该页是否在磁盘上。如果该页在磁盘上（即它确实是一个有效的内存引用），操作系统就会分配一个空闲的帧，启动磁盘I/O，将所需的页读入新分配的帧，并启动下一个进程。
当磁盘I/O完成后，与进程和页表一起保存的内部表被更新，以表明该页现在在内存中。被非法地址陷阱打断的指令被重新启动。该进程现在可以访问该页。

9.3

Consider the page table shown in Figure 9.30 for a system with 12-bit virtual and physical addresses and with 256-byte pages. The list of free page frames is D, E, F (that is, D is at the head of the list, E is second, and F is last).

![image-20220612002733376](/Users/ouritsusei/Documents/学习笔记/操作系统/Chapter 9.assets/image-20220612002733376.png)

Convert the following virtual addresses to their equivalent physical addresses in hexadecimal. All numbers are given in hexadecimal. (A dash for a page frame indicates that the page is not in memory.)

• 9EF

• 111

• 700

• 0FF

9EF -> 0EF
111 -> 211
700 -> D00
0FF -> EFF

9.4

Consider the following page-replacement algorithms. Rank these algo- rithms on a five-point scale from “bad” to “perfect” according to their page-fault rate. Separate those algorithms that suffer from Belady’s anomaly from those that do not.

LRU replacement
FIFO replacement
Optimal replacement
Second-chance replacement

排序：OPT>LRU>Second-chance replacement>FIFO

其中FIFO replacement受到Belady’s anomaly影响

9.5

Discuss the hardware support required to support demand paging.

对于每个内存访问操作，都需要查询页表，以检查相应的页是否驻留在内存中，并确定是否触发了页故障。这些检查必须在硬件（MMU）中进行。一个TLB可以作为一个缓存，并提高查询操作的性能。

9.7

Consider the two-dimensional array A:

![image-20220612003025373](/Users/ouritsusei/Documents/学习笔记/操作系统/Chapter 9.assets/image-20220612003025373.png)![image-20220612003036733](/Users/ouritsusei/Documents/学习笔记/操作系统/Chapter 9.assets/image-20220612003036733.png)

在这个系统中，每页可以容纳50个整数（整数的大小为4字节），因此A的一行需要2页，整个A需要2*100=200页。

a. 在这种情况下，数组A被逐行访问，因此每行产生2个页面故障，因为对一个页面的第一次引用总是产生一个页面故障。使用LRU，它将产生200个页面故障。

b. 在这种情况下，数组A被逐列访问，因此进程在每个外部循环（I）中引用了100个页面，这就是程序的工作集。但是我们只有2个框架，因此每个数组引用将产生一个页面故障。使用LRU，它将产生100*100=10,000个页面故障。

9.8

Consider the following page reference string:

1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6.

How many page faults would occur for the following replacement algorithms, assuming one, two, three, four, five, six, and seven frames? Remember that all frames are initially empty, so your first unique pages will cost one fault each.

• LRU replacement

• FIFO replacement

• Optimal replacement

Number of frames	LRU	FIFO	OPT
1	20	20	20
2	18	18	15
3	15	16	11
4	10	14	8
5	8	10	7
6	7	10	7
7	7	7	7

9.15

A simplified view of thread states is Ready, Running, and **Blocked, where a thread is either ready and waiting to be scheduled, is running on the processor, or is blocked (for example, waiting for I/O). This is illustrated in Figure 9.31. Assuming a thread is in the Running state, answer the following questions, and explain your answer:

Will the thread change state if it incurs a page fault? If so, to what state will it change?

Will the thread change state if it generates a TLB miss that is resolved in the page table? If so, to what state will it change?

Will the thread change state if an address reference is resolved in the page table? If so, to what state will it change?

会，当一个页面故障发生时，一个线程从运行状态变为阻塞状态。当一个页面故障发生时，线程开始等待I/O操作的完成。操作系统检查该页是否真的无效或只是在磁盘上，找到一个空闲的内存帧，安排一次磁盘访问将该页加载到该帧中，当磁盘I/O完成后用新的逻辑-物理映射更新页表，更新该条目的有效位，并最终重新启动线程，将其状态从阻塞状态变为就绪状态。
不一定。如果在TLB中没有找到一个页表项（TLB缺失），页号被用来索引和处理页表。如果该页已经在主内存中，那么TLB被更新以包括新的页条目，同时由于不需要I/O操作，进程继续执行。如果该页不在主存中，就会产生一个页故障。在这种情况下，进程需要改变为阻塞状态，等待I/O访问磁盘。这与第一个问题中的程序相同。
不会，因为不需要I/O操作，因为地址引用在页表中被解决了，这表明需要的页已经加载在主存中

9.18

由于页面大小为2^12^，所以页表大小为2^20^。因此，低阶的12位0100 0101 0110被用作进入页面的位移，而剩下的20位0001 0001 0001 0010 0011被用作页表的位移。然后将偏移位与产生的物理页号（来自页表）相连接，形成最终地址。

9.21

Consider the following page reference string:

7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6, 2, 3, 0 , 1.

Assuming demand paging with three frames, how many page faults would occur for the following replacement algorithms?

• LRU replacement

• FIFO replacement

• Optimalreplacement

LRU：18

7; 7 2; 7 2 3; 1 2 3; 1 2 5; 3 2 5; 3 4 5; 3 4 6; 7 4 6; 7 1 6; 7 1 0; 5 1 0; 5 4 0; 5 4 6; 2 4 6; 2 3 6;
2 3 0; 1 3 0

FIFO：17

7; 7 2; 7 2 3; 1 2 3; 1 5 3; 1 5 4; 6 5 4; 6 7 4; 6 7 1; 0 7 1; 0 5 1; 0 5 4; 6 5 4; 6 2 4; 6 2 3; 0 2 3;
0 1 3

OPT ： 13
7; 7 2; 7 2 3; 1 2 3; 1 5 3; 1 5 4; 1 5 6; 1 5 7; 1 5 0; 1 4 0; 1 6 0; 1 2 0; 1 3 0

9.22

The page table shown in Figure 9.32 is for a system with 16-bit virtual and physical addresses and with 4,096-byte pages. The reference bit is set to 1 when the page has been referenced. Periodically, a thread zeroes out all values of the reference bit. A dash for a page frame indicates the page is not in memory. The page-replacement algorithm is localized LRU, and all numbers are provided in decimal.

a. Convert the following virtual addresses (in hexadecimal) to the equivalent physical addresses. You may provide answers in either

- 0xE12C -> 0x312C
- 0x3A9D -> 0xAA9D
- 0xA9D9 -> 0x59D9
- 0x7001 -> 0xF001
- 0xACA1 -> 0x5CA1
C001、C121等将给出页面错误，因为对于页码12，没有帧导致页面错误。
{9,1,14,13,8,0,4,2}

9.32

What is the cause of thrashing? How does the system detect thrashing? Once it detects thrashing, what can the system do to eliminate this problem?

抖动是由于进程所需的最小页数分配不足而造成的，迫使它不断出现页面故障。系统可以通过评估CPU的利用率与多道程序程度的比较来检测阻塞。它可以通过减少多道程序程度来消除。

9.34

Consider the parameter 􏰉 used to define the working-set window in the working-set model. When 􏰉 is set to a small value, what is the effect on the page-fault frequency and the number of active (nonsuspended) processes currently executing in the system? What is the effect when 􏰉 is set to a very high value?

当设置为一个较小的值时，有可能低估一个进程的驻留页集，允许一个进程被安排，即使它所需要的所有页面没有被托管。这可能导致大量的页面错误。
当设置为一个较大的值时，高估一个进程的驻留集可能会阻止许多进程被安排，即使它们需要的页面驻留了。然而，一旦一个进程被调度，当高估驻留集时，就不可能产生一个页面错误

229610.4 Why is it important to balance file-system I/O among the disks and controllers on a system in a multitasking environment?

由于木桶效应，一个系统只能以其最慢的瓶颈的速度运行。在现代系统中，磁盘或磁盘控制器经常成为瓶颈，因为它们的单个性能无法跟上CPU和系统总线的性能。通过在磁盘和控制器之间平衡I/O，可以避免瓶颈的出现。

10.5

What are the tradeoffs involved in rereading code pages from the file system versus using swap space to store them?

如果代码页存储在交换空间中，它们可以更快地被转移到主内存中（因为交换空间的分配被调整为比一般文件系统分配更快的性能）。如果代码页是在进程调用时被复制到那里，而不是在需要时被分页到交换空间，那么使用交换空间可能需要启动时间。另外，如果交换空间同时用于代码和数据页，就必须分配更多的交换空间。

10.9

None of the disk-scheduling disciplines, except FCFS, is truly fair (starvation may occur).

Explain why this assertion is true.

Describe a way to modify algorithms such as SCAN to ensure fairness.

Explain why fairness is an important goal in a time-sharing system.

Give three or more examples of circumstances in which it is important that the operating system be unfair in serving I/O requests.

理论上，对磁头当前所在轨道的新请求可以在这些请求得到服务的同时迅速到达。
所有超过预定年龄的请求可以被 "强制 "到队列的顶部，每个请求的相关位可以被设置，以表明没有新的请求可以被移到这些请求之前。对于SSTF来说，队列的其他部分将不得不根据这些 "老 "请求中的最后一个进行重新组织。
保证所有响应得到应答，不会出现长时间等待。
分页和交换应该优先于用户请求。其他由内核发起的I/O，例如文件系统元数据的写入，可能需要优先于用户I/O。如果内核支持实时进程的优先级，这些进程的I/O请求应该被优先考虑。

10.10

Explain why SSDs often use an FCFS disk-scheduling algorithm.

SSD没有磁头调度问题，随机读取所花费的时间是一样的

10.11

Suppose that a disk drive has 5,000 cylinders, numbered 0 to 4,999. The drive is currently serving a request at cylinder 2,150, and the previous request was at cylinder 1,805. The queue of pending requests, in FIFO order, is:

2,069, 1,212, 2,296, 2,800, 544, 1,618, 356, 1,523, 4,965, 3681

Starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests for each of the following disk-scheduling algorithms?

a. FCFS b. SSTF

c. SCAN d. LOOK

e. C-SCAN f. C-LOOK

Method	1	2	3	4	5	6	7	8	9	10	11	12	13	Total
FCFS	2150	2069	1212	2296	2800	544	1618	356	1523	4965	3681			13011
SSTF	2150	2069	2296	2800	3681	4965	1618	1523	1212	544	356			7586
SCAN	2150	2296	2800	3681	4965	4999	2069	1618	1523	1212	544	356		7492
C-SCAN	2150	2296	2800	3681	4965	4999	0	356	544	1212	1523	1618	2069	9917
LOOK	2150	2296	2800	3681	4965	2069	1618	1523	1212	544	356			7424
C-LOOK	2150	2296	2800	3681	4965	356	544	1212	1523	1618	2069			9137

10.14

Describe some advantages and disadvantages of using SSDs as a caching tier and as a disk-drive replacement compared with using only magnetic disks.

优点

比硬盘驱动器更快。固态硬盘的优点是比磁性磁盘快，因为没有移动部件，因此没有寻道时间或旋转延迟。

SSD比典型的HDD快25到100倍。这意味着启动时间更快，文件传输更快，企业计算的带宽更大。

低功耗，比硬盘驱动器更紧凑和耐用。这意味着固态硬盘适用于节能的计算机和消费类电子设备。

缺点

价格较高

存储容量有限

比硬盘驱动器的寿命更短。固态硬盘的闪存只能用于有限的写入次数。

如果不先擦除然后一次性重写非常大的数据块，固态硬盘就无法写入一个位的信息。#### 1.1 What are the three main purposes of an operating system?

充当计算机用户和计算机硬件之间的中介程序，主要有以下三个功能：

执行用户程序，解决用户问题更便捷。为计算机用户提供一个以方便和高效的方式在计算机硬件上执行程序的环境
使计算机系统使用方便。根据需要分配计算机的独立资源以解决给定的问题且分配过程尽可能公平和高效。
以有效的方式使用计算机硬件。（1）监督用户程序的执行，以防止错误和不当使用计算机；（2）管理I/O设备的操作和控制。

如果觉得文章对你有用，请随意赞赏

learn

Operating System Concepts 课后答案（部分）

https://koito.fun/archives/1710159811974

作者

可可今天吃什么

发布于

2024-03-11

更新于

2024-05-13

许可协议

CC BY 4.0

Operating System Concepts 课后答案（部分）

Operating System Concepts 课后答案（部分）

Chapter 1

1.5

1.6

1.12

1.15

1.19

1.22

1.23

1.27

Chapter 2

2.1

2.2

2.3

2.4

2.5

2.6

2.7

2.8

2.9

2.12

2.13

2.15

2.16

2.17

2.18

2.19

2.21

2.22

Chapter 3

3.1

3.5

3.8

3.9

3.12

3.13

3.14

3.17

Chapter 4

4.2

4.4

4.7

4.8

4.9

4.14

4.15

4.16

4.17

4.21

5.4

5.5

5.10

5.11

5.15

5.17

5.18

5.20

5.23

5.28

6.2

6.3

6.6

6.9

6.10

6.13

6.16

6.17

6.19

6.21

6.23

6.28

代码可重入

8.1

8.4

How many bits are there in the logical address?

How many bits are there in the physical address?

8.5

8.6

8.7