【操作系统概念 - 作业 5】Process Synchronization

Operating System Concepts Exercises 5

Process Synchronization

操作系统作业 5

• 课后学习面向对象编程概念（类、对象、继承、多态）
• 5.4 5.5
• 5.10 5.11 5.15 5.17 5.18 5.20 5.23 5.28

每题最后一个引用块是老师提供的参考答案

课后学习面向对象编程概念（类、对象、继承、多态）

已学习

Practice Exercises

5.4 5.5

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

说明为什么自旋锁不适用于单处理器系统，但是经常在多处理器系统中使用。

答：

在单处理器系统中，使用自旋锁会造成其他进程忙等待（任何其他试图进入临界区的进程都必须在其进入代码中连续地循环），这样就浪费了 CPU 时钟。而对于多处理器系统，当一个进程在一个处理器自旋时，另一个进程可以在另一处理器上在其临界区内执行，且使用自旋锁，进程在等待锁时还在运行，不用进行上下文切换。

Reference:操作系统学习笔记（五）—进程同步_雲的博客-CSDN 博客

Answer:

On a single-processor system, the thread holding a lock cannot be running while another thread is testing the lock, because only one thread/process can be running at a time. Therefore the thread will continue to spin and waste CPU cycles until its time slice end. That is why threads on a single-processer system should always sleep rather than spin, if they encounter a lock that is held.

On a multiprocessor system, multiple threads (the thread holding a lock, and the thread testing the lock) can actually be running at the same time. Therefore, it is appropriate for a thread waiting for lock to go into a spin wait, because the lock could be released while it is waiting.

在一个单处理器系统中，当另一个线程在测试锁的时候，持有锁的线程不能运行，因为一次只能有一个线程/进程在运行。因此，该线程将继续旋转并浪费 CPU 周期，直到其时间片结束。这就是为什么在单处理器系统上的线程，如果遇到一个被持有的锁，应该总是睡觉而不是旋转。

在多处理器系统中，多个线程（持有锁的线程和测试锁的线程）实际上可以在同一时间运行。因此，等待锁的线程进入自旋等待是合适的，因为锁可能在它等待时被释放。

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

证明如果wait()和signal()信号操作不是原子执行的，那么可能会违反互斥。

证明：

The definition of wait() is as follows:

wait(S) {
    while(S <= 0)
        ; //busy wait
    S--;
}

The definition of signal() is as follows:

signal(S) {
	S++;
}

如果非原子执行，那么可能会发生以下情况：

//S==1
wait1(S) {
    while(S <= 0)
        ; //busy wait
    wait2(S) {
        while(S <= 0)
            ; //busy wait
        S--;
    }
    S--;
}

1 和 2 都同步运行了，违反互斥。

Answer:

A wait operation atomically decrements the value associated with a semaphore. If two wait operations are executed on a semaphore when its value is 1, and if the two operations are not performed atomically, then it is possible that both operations might proceed to decrement the semaphore value, thereby violating mutual exclusion.

一个等待操作会以原子方式递减与信号灯相关的值。如果当一个信号灯的值为 1 时，在其上执行两个等待操作，并且这两个操作不是原子执行的，那么这两个操作就有可能继续递减信号灯的值，从而违反了互斥原则。

Exercises

5.10 5.11 5.15 5.17 5.18 5.20 5.23 5.28

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

如果同步原语要用于用户级程序，请解释为什么在单处理器系统中通过禁用中断来实现同步原语是不合适的。

答：

Implementing synchronization primitives by disabling interrupt is not appropriate because it reduces the flexibility of the system.

Synchronization primitives will make a program at user level to be able to switch interupts, thereby disabling the timer interrupt. Once a program at user-level has the ability to disable interrupts it also disables context switching which is not recommended for a program at that level.

Once the context switching is disabled, the program can now run on the processor without allowing other programs to execute, which is bad considering the fact that it is to be used in a single-processor system because single processor systems contain only one process, and only one program can run at a time.

Reference: Explain why implementing synchronization primitives by disabling interrupts is not appropriate in a - Brainly.com

Answer:

If a user-level program is given the ability to disable interrupts, then it can disable the timer interrupt and prevent context switching from taking place, thereby allowing it to use the processor without letting other processes to execute.

如果一个用户级程序被赋予禁用中断的能力，那么它可以禁用定时器中断，防止上下文切换，从而允许它使用处理器而不让其他进程执行。

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

解释为什么中断不适合在多处理器系统中实现同步原语。

答：多处理器之间的中断静止会很耗时，因为消息要传递到所有处理器。

Answer:

Depends on how interrupts are implemented, but regardless of how, it is a poor choice of techniques.

Case 1 – interrupts are disabled for ONE processor only – result is that threads running on other processors could ignore the synchronization primitive and access the shared data.

Case 2 – interrupts are disabled for ALL processors – this means task dispatching, handling I/O completion, etc. is also disabled on ALL processors, so threads running on all CPUs can grind to a halt.

这取决于中断是如何实现的，但无论如何，这都是一种糟糕的技术选择。

情况 1 – 中断只对一个处理器禁用 – 其结果是，在其他处理器上运行的线程可以忽略同步原语并访问共享数据。

情况 2 – 中断在所有处理器上被禁用 – 这意味着任务调度、处理 I/O 完成等也在所有处理器上被禁用，因此在所有 CPU 上运行的线程都可能陷入停顿。

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:

考虑如何使用原子硬件指令实现互斥锁。假设以下定义互斥锁的结构可用：

typedef struct {
    int available;
} lock;

(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:

(available == 0)表示该锁是可用的，值为 1 表示该锁不可用。使用这个结构，说明如何使用test_and_set()和compare_and_swap()指令实现以下函数：

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

Be sure to include any initialization that may be necessary. 请确保包括任何可能需要的初始化。

答：

void acquire(lock *mutex) {
    while(test_and_set(&(mutex->available)))
        ;
    return;
}

void release(lock *mutex) {
    mutex->available = 0;
    return
}

void acquire(lock *mutex) {
    while(compare_and_swap(mutex->available,0,1))
        ;
    return;
}

void release(lock *mutex) {
    mutex->available = 0;
    return
}

Answer:

Test and Set :

typedef struct { int available; } lock;

void init(lock *mutex) {
	// available=0 -> lock is available, available=1 -> lock is unavailable
	mutex->available = 0;
}

void acquire(lock *mutex) {
	while (test_and_set(&(mutex->available))) // TEST the available
		; // spin-wait (do nothing)
}

void release(lock *mutex) {
	mutex->available = 0;
}

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. 一个线程在持有锁的时候可能会进入睡眠状态。

答：

Answer:

(1) If the lock is to be held for a short duration, it makes more sense to use a spinlock as it may in fact be faster than using a mutex lock which requires suspending - and awakening - the waiting process.

(2) If it is to be held for a long duration, a mutex lock is preferable as this allows the processing core to schedule another process while the locked process waits.

(3) If the thread may be put to sleep while holding the lock, a mutex lock is definitely preferable as you wouldn’t want the waiting process to be spinning while waiting for the other process to wake up.

(1) 如果锁要保持很短的时间，使用自旋锁更有意义，因为事实上它可能比使用互斥锁更快，因为互斥锁需要暂停 - 和唤醒 - 等待的进程。

(2) 如果要保持较长的时间，最好使用互斥锁，因为这允许处理核心在被锁进程等待时安排另一个进程。

(3) 如果线程在持有锁的时候可能会进入睡眠状态，那么互斥锁肯定是最好的，因为你不希望等待的进程在等待另一个进程醒来的时候还在旋转。

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.

假设一个上下文切换需要 T 时间。建议一个持有自旋锁的上限（以 T 为单位）。如果自旋锁保持的时间再长一些，那么突变锁（等待的线程会进入睡眠状态）是一个更好的选择。

答：

Answer:

The maximum time that can be tolerable in terms of time t will be <2xT Thus exceeding the maximum time, a mutex lock will be used instead of spin lock where the threads that are in wait mode are switched to sleep mode

就时间 t 而言，可以容忍的最大时间将是<2xT 因此，超过最大时间，将使用互斥锁而不是自旋锁，处于等待模式的线程被切换到睡眠模式。

==?==

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

Figure 5.23 Allocating and releasing processes.

#define MAX_PROCESSES 255
int number_of_processes = 0;

/* the implementation of fork() calls this function */
int allocate_process() {
    int new_pid;
    if (number_of_processes == MAX_PROCESSES)
        return -1;
    else {
        /* allocate necessary process resources */
        ++number_of_processes;
        return new_pid;
    }
}

/* the implementation of exit() calls this function */
void release_process()
{
    /* release process resources */
    --number_of_processes;
}

a. Identify the race condition(s).

识别竞争条件。

答：

number_of_processes可能产生竞争

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).

假设你有一个名为 mutex 的互斥锁，操作是acquire()和release()。指示需要将锁定放置在何处以防止出现竞争条件。

答：

#define MAX_PROCESSES 255
int number_of_processes = 0;

/* the implementation of fork() calls this function */
int allocate_process() {
    int new_pid;
    if (number_of_processes == MAX_PROCESSES)
        return -1;
    else {
        /* allocate necessary process resources */
        acquire();
        ++number_of_processes;
        release();
        return new_pid;
    }
}

/* the implementation of exit() calls this function */
void release_process()
{
    /* release process resources */
    acquire();
    --number_of_processes;
    release();
}

c. Could we replace the integer variable

int number_of_processes = 0

with the atomic integer

atomic_t number_of_processes = 0

to prevent the race condition(s)

答：

对于 Java 中的运算操作，例如自增或自减，若没有进行额外的同步操作，在多线程环境下就是线程不安全的。num++ 解析为 num=num+1，明显，这个操作不具备原子性，多线程并发共享这个变量时必然会出现问题。[1]

可见，使用 atomic integer 仍然不足以解决竞争问题。

Answer:

a. There is a race condition on the variable number of processes.

b. A call to acquire() must be placed upon entering each function and a call to release() immediately before exiting each function.

c. No, it would not help. The reason is because the race occurs in the allocate process() function where number of processes is first tested in the if statement, yet is updated afterwards, based upon the value of the test. It is possible that number of processes = 254 at the time of the test, yet because of the race condition, is set to 255 by another thread before it is incremented yet again.

a. 进程的可变数量上存在一个竞赛条件。

b. 在进入每个函数时必须调用acquisition()，在退出每个函数前必须立即调用release()。

c. 不，这没有帮助。原因是竞赛发生在allocate process()函数中，其中进程数首先在 if 语句中被测试，但之后又根据测试值被更新。有可能在测试时进程数=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.

展示如何在多处理器环境中使用test_and_set()指令实现wait()和signal()信号操作。该方案应表现出最小的繁忙等待。

答：

Answer:

int guard = 0;
int semaphore value = 0;
wait() {
 while (TestAndSet(&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;
 }
}
signal() {
 while (TestAndSet(&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;
}

另一种答案：

int guard = 0;
typedef struct {
 int value;
 struct process *list;
} semaphore;

Semaphore s;

wait(s) {
 while (TestAndSet(&guard) == 1)
     ;
 s.value--;

 if (s.value < 0){
     atomically add process to a queue of processes
     guard = 0;
     waiting for the semaphore;
 }
 guard = 0;
}

signal(s) {
 while (TestAndSet(&guard) == 1)
     ;
 s.value++
     if (s.value <= 0)
         remove and wake up the first process in the queue of waiting processes
     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.

讨论读者 - 写者问题中操作的公平性和吞吐量之间的权衡。提出一种解决读者 - 写作者问题的方法，而不造成饥饿。

答：

Answer:

Throughput in the readers-writers problem is increased by favoring multiple readers as opposed to allowing a single writer to exclusively access the shared values. On the other hand, favoring readers could result in starvation for writers.

相对于允许单个写作者专门访问共享值而言，偏向于多个读者，可以提高读者 - 写作者问题的吞吐量。另一方面，偏爱读者可能会导致写手的饥饿。

When a reader arrives and notices that another reader is accessing the database, then it would enter the critical section only if there are no waiting writers.

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

The starvation in the readers/writers problem could be avoided by keeping timestamps associated with waiting processes. When a writer is finished with its task, it would wake up the process that has been waiting for the longest duration.

读者/写作者问题中的饥饿现象可以通过保留与等待进程相关的时间戳来避免。当一个写手完成其任务时，它将唤醒等待时间最长的进程。

---

注：

参考资料：

[1] 原子操作类 AtomicInteger 详解_分享传递价值-CSDN 博客_atomicinteger

[2] Operating System Concepts – 9th Edition 及其答案