Yanyan's Wiki 操作系统 (2022)

本周阅读材料

教科书

教科书 Operating Systems: Three Easy Pieces:

  • 第 28 章 - Locks
  • 第 30 章 - Condition Variables
  • 第 31 章 - Semaphores

阅读理解示例代码

  • thread-sync.h 给出了一些互斥和同步操作的封装,它们可以和 thread.h 联合使用
    • 你可以自行测试互斥锁的 scalability,例如你可以修改 sum-scalability.c,查看临界区大小不同时、线程不同时、锁的争抢程度不同时,在你自己计算机上程序的 scalability。当然——你需要一个好的统计程序自动帮你收集这些数据并绘制成图形。这能够帮助你验证你的一些直觉。
  • 我们展示了 model checker 的建模能力:我们唯一的假设就是 “每一行原子执行且立即写入共享内存”。这比实际的机器的内存模型稍强一些,但依然能帮助我们理解并发程序的行为。例如,在 futex.py 中,我们就建模了一部分操作系统的行为 (操作系统维护的队列):

    @thread
    def t1(self):
        while True:
            if self.tryacquire() == '🔒':     # User
                self.waits = self.waits + '1' # Kernel
                while '1' in self.waits:      # Kernel
                    pass
            cs = True                         # User
            del cs                            # User
            self.release()                    # Kernel
    

    虽然操作系统不会实际地在 waits 队列上自旋,但 “切换到另一个线程执行” 的语义和自旋的语义是完全等价的。如果你有兴趣,甚至可以试着实现你自己的 futex,使得 fast path 下 release 不需要陷入内核——你会发现正确的实现要困难得多。

    在《操作系统》课上的温馨提示:总是使用简单、robust 的方式实现正确的代码。Premature optimization is the root of all evil.

  • 在同步操作上,model checker 也很好地帮助我们理解线程同步 API 的 “严格定义”,例如条件变量:

    while not self.tryacquire(): pass # mutex_lock()
    if not cond: # cond_wait
        _, self.waits = self.release(), self.waits + '1'
        while '1' in self.waits: pass
        while not self.tryacquire(): pass
    ...
    self.waits = self.waits[1:] # cond_signal
    self.release() # mutex_unlock()
    

    以及信号量:

    def P(self, tid):
        if self.token > 0:
            self.token -= 1
            return True
        else:
            self.waits = self.waits + tid
            return False
    
    def V(self):
        if self.waits:
            self.waits = self.waits[1:]
        else:
            self.token += 1
    

    确保你阅读了这些代码,正确理解了同步操作的行为。 - 我们提供了生产者/消费者问题的一些例子,例如 pc-sem.c。更重要的是,我们给出了很多错误的实现,例如 pc-cv.cphilosopher.c。这些例子提醒大家,并发编程远非易事,务必多加小心。

动手实践

OSTEP 的教科书给了我们许多互斥、同步的代码例子,并附有习题。在理解了原理以后,你就会发现教科书上的课后代码习题做起来容易了。

Creative Commons License    苏 ICP 备 2020049101 号