操作系统概念-第五章
本文最后更新于一年前或更久前,其中的信息可能已经有所发展或是发生改变。

Tips:此为⬛⬛⬛⬛⬛⬛大学⬛⬛⬛⬛⬛⬛⬛学院2019级《操作系统原理》课程中的部分课程作业题目解析和展示

5.4 5.5 5.10 5.11 5.15 5.17 5.18 5.20 5.23 5.28

5.4 解释为什么自旋锁不适合单处理器系统,而经常用于多处理器系统。

对于单处理器来说,防止中断处理中的并发可简单采用关闭中断的方式,即在标志寄存器中关闭/打开中断标志位,不需要自旋锁。

5.5 试说明如果wait( )和signal( )操作不是原子化操作,那么互斥可能是不稳定的。

原子操作的定义是不可中断的一个或一系列操作,就是该操作绝不会在执行完毕前被任何其他任务或事件打断,也就是说,它是最小的执行单位,不可能有比它更小的执行单位。如果wait()和signal( )操作不是原子化操作,那么互斥锁(二进制信号量)就有可能在进程执行中被修改,那么互斥就会变得不稳定。

5.10 如果一个同步元是在一个用户级程序中使用的,解释在一个单处理器系统中为什么通过停止中断去实现这个同步元是不适合的?

如果一个用户级程序具有停止中断的能力,那么它能够停止计时器中断,防止上下文切换的发生,从而允许它使用处理器而不让其他进程执行。

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

在其他处理器上运行的其他程序可以请求访问该数据。

在多处理器系统中中断是不够的,因为禁用中断只会阻止其他进程在禁用中断的处理器上执行;对于哪些进程可以在其他处理器上执行没有限制,因此禁用中断的进程不能保证对程序状态的互斥访问。

5.15 考虑如何使用原子硬件指令实现互斥锁……

Q:考虑如何使用原子硬件指令实现互斥锁。假设定义互斥锁的以下结构是可用的 typedef struct { int available; } lock;其中(available == 0)表示该锁可用;取值为1表示该锁不可用。使用这个结构体,说明如何使用test和set()以及compare和swap()指令实现下列函数:1.void acquire(lock mutex) 2.void release(lock mutex);确保包含任何可能需要的初始化。

// 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 假设一个系统有多个处理核心。对于下面的每个场景,请描述哪个是更好的锁定机制:自旋锁还是互斥锁,其中等待的进程在等待锁可用时处于休眠状态。

锁将被持有一小段时间:

锁被持有的时间很短——使用自旋锁。如果进程等待3-4个周期,然后执行两个上下文切换(第一个用于删除一个阻塞的线程并放置一个新的线程来运行,第二个用于反转这个进程),那么开销就会少得多。Linux内核倾向于使用自旋锁来处理那些应该忙于等待一段短时间的进程。

锁要被长时间保持:

锁将被长时间持有——使用互斥锁。在前面的回答中给出的自旋锁的原因在这里不成立。

持有锁的线程可能会进入休眠状态:

线程可能会在按住锁的状态下进入睡眠状态-如果您的代码输入线程/进程在关键区域进入睡眠状态,请考虑重新设计您的关键部分。 这是错误的代码。 但是,关键部分中的线程/进程可能会进入睡眠状态。线程/进程运行的时间越长,此概率就越大。 在这种情况下,您应该使用互斥锁。 与繁忙等待相比,无法访问关键部分的线程将浪费更少的周期。

5.18 假设上下文切换需要T时间。建议持有自旋锁的上界(根据T)。如果自旋锁被持有的时间更长,互斥锁(等待的线程在这里休眠)是一个更好的选择。

上限是2T。保持自旋锁的时间越长,就需要让线程进入睡眠状态并进行上下文切换,这样一个进程就可以唤醒处于睡眠状态的线程,而不需要进行第二次上下文切换。

在过程同步中,合作过程可能会影响或受到系统中执行的其他过程的影响,或者直接共享代码和数据的逻辑地址空间,或者被允许仅通过文件或消息共享数据,尽管同时访问共享数据 可能会导致数据不一致。 但是有几种机制可以帮助有序共享共享逻辑地址空间的协作流程的有序执行,从而保持数据一致性。

5.20 考虑图5.23中所示的分配和释放过程的代码示例

a.识别竞争条件

增加/减少可变进程数。这里的推理是简单的读取-修改-写入竞争条件。创建一个新进程(P2),并在创建新进程(P2)的同时创建另一个进程(P3)。 P3读取进程数被P2中断,P2也会读取编号或进程。两个进程将会具有相同的编号。他们要求将数字递增1并写入相同的值。所以是读取-修改-写入竞争。

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

互斥锁应保护可修改进程数或可用于比较,赋值等操作的任何区域。这意味着:①当函数获取将进程数与最大进程数进行比较时,应将其锁定。②递增/递减进程数的操作应使用互斥锁进行保护。

c.我们能否将整数变量int number of processes = 0替换为原子整数atomic_t number_of_processes = 0以防止竞争条件

如果增量/减量和比较是原子完成的,我们可以用原子整数代替普通整数。

5.23 试采用test_and_set()指令,实现用于多处理器环境的信号量的wait()和signal()操作。该实现应具有最小忙等待。

int guard = 0;
int semaphore value = 0;
wait()
{
    while (Test_And_Set(&guard) == 1)
        ;

    if (semaphore value == 0)
    {
        //add to the queue which is wating for the semaphore
        guard = 0;
    }
    else
    {
        semaphore value--;

        guard = 0;
    }
}
    signal()
{
    while (TestAndSet(&guard) == 1)
        ;
    if (semaphore value == 0 && wait_process())
        //wake and run the first process in the queue
    guard = 0;

        else
    {
        semaphore value++;
        guard = 0;
    }
}

5.28 讨论在读写器问题中操作的公平性和吞吐量之间的权衡。提出一种既能解决读者写作问题又不会引饥饿的方法

如果两个线程想要访问同一个资源,我们需要一个同步机制。通常使用互斥。如果多个线程想要读取一个资源,这应该是允许的。这是有意义的,因为对相同内存位置的并发处理是一个安全的操作。//访问和读取不同

当有人想要写入内存位置时,问题就来了。有三种可能性:

  1. 读者——总是允许读者阅读位置。这可能会导致写线程的紧缺,因为系统总是偏爱读线程,当写线程希望锁定一个互斥锁时,可能会被读线程否决,这是不公平的,因为写线程优先。
  2. 写入器——只要队列中有写入器,就让它运行。这种解决方案可能会导致读者的饥饿,因为系统总是偏爱作者。另外,不要忘记作者一次只能操作一个。
  3. 没有任何工作应该永远在队列中——这是正确的解决方案。如果我们在这个问题上使用可以保证先进先出(FIFO)在它的阻塞队列上的标志而且如果它能确保没有线程会比解决方案不会导致饥饿的时间还要等的久。

所以,如果没有线程卡在等待队列中,队列保持先进先出的解决方案是正确的。它不会引起饥饿。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇