2020-2021学年上学期期中

2020-2021学年上学期期中试卷（含答案）

说明

原卷标题：华东师范大学期中考试试卷2020—2019学年第一学期，应为误写

一、判断题（20 分，每小题 2 分）

判断下列每句话是否正确，如错误请说明理由。

如果信号量 S 的当前值为 -6 时，则表示系统中共有 6 个等待的进程。

答案：
错。S=-6 表示当前有 6 个进程等待进入该信号量所对应的临界区。
取值为 0 或者 1 的信号量只能实现互斥访问。

答案：
错。信号量可以实现互斥和同步。
线程都保存有各自的栈信息、CPU 状态（寄存器、指令计数器等）、堆信息，以及打开文件列表等。

答案：
错。线程保存栈信息、CPU 状态；而堆信息，以及打开文件列表等是进程保存的。
（线程实现了资源和调度单位相分离）
资源分配图中存在环时，系统中某些进程处于死锁状态。

答案：
错。当每种资源实例个数为一时，在环中的每个进程处于死锁状态。但是当资源实例数量不唯一时，不一定处于死锁状态。
在微内核结构的操作系统中，进程间通讯可以不在微内核内。

答案：
错。进程通讯是内核的核心功能，对微内核系统，也在微内核内实现。
在多处理器系统中，通过关中断的方式可以解决进程间互斥访问的问题。

答案：
错。在多处理器系统中，关中断不能保证临界区的互斥访问。
进程所请求打开的文件打开后，将使进程状态从运行态变为就绪态。

答案：
错。等待态变为就绪态。
在生产者-消费者问题中，生产者进程和消费者进程只要解决互斥访问的问题即可。

答案：
错。当 buffer 为空时，只有等待生成者进程完成一个产品生成后，消费者才可以消费。因此，还要解决进程间同步的问题。
时间片轮转算法，核心思想是限定任务每次执行的时间，SJF 策略和 STCF 策略，RR 策略不仅无需预知任务的运行时间，且不会出现长任务饥饿的情况。

答案：
对
管程中对条件变量的 signal（）和信号量中的 signal（）操作具有相同的效果。

答案：
错。管程中对条件变量的 signal（）可以什么都不做，而信号量中的 signal（）操作必然改变信号量的值。

二、不定项选择题（30 分，每小题 3 分）

每题有一个或多个答案，答错、少选、多选均不给分。

下列哪个计算机系统的组件定义了使用系统资源解决计算问题的方法？（）

A. 应用程序

B. 操作系统

C. 计算机硬件

D. 计算机 logo

答案：
B
以下哪种进程间通信在微内核中使用？（）

A. 消息传递

B. 共享内存

C. 套接字通信

D. 全部都是

答案：
A
下面哪一个包含可执行代码？（）

A. 文本（text）部分

B. 数据（data）部分

C. 堆（heap）部分

D. 栈（stack）部分

答案：
A
以下哪种情况可能会导致进程从 CPU 中移出？（）

A. I/O 请求

B. 创建一个子进程

C. 中断或者时间片到期

D. 全部都会

答案：
ABCD
多线程编程具有以下哪些好处？（）

A. 反应性

B. 资源共享

C. 经济

D. 可扩展性

E. 全部都是

答案：
ABCDE
（）是一个用于计算通过向具有并行和串行组件的应用程序中添加其他计算内核而可能获得的性能提升的方法。

A. 任务并行

B. 数据并行

C. 数据分割

D. 阿姆达尔（Amdahl）定律

答案：
D
可以在以下哪种情况下进行抢占式调度？（）

A. 当进程从运行状态切换到等待状态时

B. 当进程从等待状态切换到就绪状态时

C. 进程终止时

D. 以上都不是

答案：
B
以下哪种调度算法可能会出现护航效应（convoy effect）？（）

A. SJF

B. FCFS

C. RR

D. Multilevel queue

答案：
B
假设 count 是一个变量名，以下哪个操作是原子的？（）

A. count++

B. count--

C. 两者都是

D. 两者都不是

答案：
D
通常认为 OpenMP 中的临界区编译器指令比标准互斥锁更易于使用，因为（）

A. 进入和退出代码由 OpenMP 库管理，从而减少了编程错误的可能性。

B. 程序员不必担心竞争条件。

C. 线程不能在临界区内部阻塞。

D. 不会发生死锁。

答案：
A

三、简答题（15 分，每小题 5 分）

列举 3 种减少上下文切换（context switch）开销的方法。
答案：
- 使用较少的内核线程（例如，事件驱动编程或有界线程池）。
- 减少模式切换的次数（例如，用户级调度）。
- 使用较少切换线程的调度算法（例如，FIFO 而不是 RR）。
（每个要点包含多个可能的答案。列出部分即可）
SRTF 在什么指标上是最优的；在什么指标上 FCFS 优于 RR？

答案：
SRTF（最短剩余时间调度）具有最佳平均响应时间的调度。
FCFS 在吞吐量指标上优于 RR，也节省了上下文切换的开销。
某系统的线程有 3 个状态分别是 Ready，Running 和 Waiting，请列出所有可能的转化情况和典型条件。
答案：
1. Ready->Running：当进程调度程序从就绪队列中选取一个进程投入运行；
2. Running->Ready：正在执行的进程如因时间片用完而被暂停执行；
3. Running->Waiting：正在执行的进程因等待的事件尚未发生而无法执行（如进程请求完成 I/O）；
4. Waiting->Ready：当进程等待的事件发生时（如 I/O 完成）。

四、综合题（35 分）

（10 分）下面有三段程序，对每段程序，判断在程序的所有进程结束后，file.txt 可能的内容是？（多选）

A. （空）

B. a

C. b

D. aa

E. ab

F. ba

G. bb

提示：

open、fopen、fork、pthread_create、malloc、realloc 调用默认成功。
read、write、dup、dup2 调用默认成功（如果文件描述符参数合法）。
必要的头文件已包含。
file.txt 初始为空。
所有进程都能进展，但对调度先后没有预设。

程序一：

int main(int argc, char** argv)
{
    if (fork() == 0) {
        int fd1 = open("file.txt", O_WRONLY);
        write(fd1, "a", 1);
    } else {
        int fd2 = open("file.txt", O_WRONLY);
        write(fd2, "b", 1);
    }
}

答案：

程序二：

char buffer;

int main(int argc, char** argv)
{
    int fd = open("file.txt", O_WRONLY);
    if (fork() == 0) {
        buffer = 'a';
    } else {
        buffer = 'b';
    }
    write(fd, &buffer, 1);
}

答案：

程序三：

int fd;

void* helper(void* arg)
{
    write(fd, "a", 1);
}

int main(int argc, char** argv)
{
    fd = open("file.txt", O_WRONLY);
    pthread_t thread;
    pthread_create(&thread, NULL, helper, NULL);
    write(fd, "b", 1);
}

答案：

CEF

（25 分，每小题 5 分）阅读以下 C 程序，回答相应死锁与调度的问题。
```
pthread_mutex_t x, y, z;

void* a(void* arg)
{
    pthread_mutex_lock(&y);
    pthread_mutex_lock(&z);
    pthread_mutex_unlock(&y);
    pthread_mutex_unlock(&z);
    return NULL;
}

void* b(void* arg)
{
    pthread_mutex_lock(&z);
    pthread_mutex_lock(&x);
    pthread_mutex_unlock(&z);
    pthread_mutex_unlock(&x);
    return NULL;
}

void* c(void* arg)
{
    pthread_mutex_lock(&x);
    pthread_mutex_lock(&y);
    pthread_mutex_unlock(&x);
    pthread_mutex_unlock(&y);
    return NULL;
}

int main(int argc, char** argv)
{
    pthread_mutex_init(&x, NULL);
    pthread_mutex_init(&y, NULL);
    pthread_mutex_init(&z, NULL);

    pthread_t a_thread, b_thread, c_thread;

    pthread_create(&a_thread, NULL, a, NULL);
    pthread_create(&b_thread, NULL, b, NULL);
    pthread_create(&c_thread, NULL, c, NULL);

    pthread_join(&a_thread, NULL);
    pthread_join(&b_thread, NULL);
    pthread_join(&c_thread, NULL);

    return 0;
}
```
（1）写出一种导致死锁的执行顺序。执行顺序是指线程获取和释放锁的序列。以类似以下语句序列的形式写出，例如“THREAD 调用 lock_acquire(LOCK)”或“THREAD 调用 lock_release(LOCK)”，其中 THREAD 指 a, b, c 之一，LOCK 指 x, y, z 之一。

答案：
a 调用 lock_acquire(&y)，
b 调用 lock_acquire(&z)，
c 调用 lock_acquire(&x)，
a 调用 lock_acquire(&z)，
b 调用 lock_acquire(&x)，
c 调用 lock_acquire(&y)

（2）在以上你提供的执行顺序中，第一个不安全（unsafe）的状态是什么，它在序列中发生的位置？

答案：
上述执行顺序中的第一个不安全状态是 a 持有 y、b 持有 z、c 持有 x。它出现在前三个语句之后。

（3）是否可以通过改变每个线程解锁互斥锁的顺序来解决死锁？（如是请写出；如否请解释）

答案：
不，因为死锁发生在任何线程解锁互斥锁之前。

（4）假设底层操作系统使用 FCFS 调度程序。对于这个特定的调度程序，程序容易死锁吗？（如是请写出；如否请解释）

答案：
不。FCFS 调度程序会运行每个线程直到结束。因此，锁没有竞争问题（所有锁操作都不会阻塞）。

（5）使用抢占式线程调度程序会消除死锁的可能性吗？

答案：
不，不会消除死锁的可能性。虽然抢占式调度程序会从线程抢占 CPU，但它不会抢占他们持有的锁。

2020-2021学年上学期期中试卷（含答案）​

说明​

一、判断题（20 分，每小题 2 分）​

二、不定项选择题（30 分，每小题 3 分）​

三、简答题（15 分，每小题 5 分）​

四、综合题（35 分）​

2020-2021学年上学期期中试卷（含答案）

说明

一、判断题（20 分，每小题 2 分）

二、不定项选择题（30 分，每小题 3 分）

三、简答题（15 分，每小题 5 分）

四、综合题（35 分）