• 哲学家就餐问题与python解决方案

    引言

    本篇是之前复习完哲学家就餐问题后，最近又回过头去感觉可以整理下思路，又在实验楼找到了python相关实验，故想在这里总结一下当前问题的方案。

    问题描述

    一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。
    在这里插入图片描述

    问题分析

    系统中有5个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系。即每个哲学家进程需要同时持有两个临界资源才能开始吃饭。该问题只会出现三种情况：

    1. 每个大哲都拿着左手边的的叉子，等着右手边有叉子好吃火锅
    2. 每个大哲都拿着右手边的的叉子，等着左手边有叉子好吃火锅
    3. 有人做适当牺牲，先让别人进行吃饭，吃完再轮到自己

    那这里情况1与情况2被称作死锁（deadlock），指当两个以上的运算单元，双方都在等待对方停止运行，以获取系统资源，但是没有一方提前退出时的状况。

    情况3是死锁的变种——活锁（livelock），活锁与死锁类似，都是需要获取对方的资源而等待导致停滞不前，唯一的区别是，察觉到停滞不前时会先释放自己的资源，过一段时间再进行获取资源的尝试，但如果双方的操作同步了的话，仍然会导致停滞不前的情况。

    这个过程我们可以通过python代码模拟为：

    #-*- coding:utf-8 -*-

import threading
from time import sleep
import os, random

#设置为2更容易重现死锁
numPhilosophers = numForks = 2

class Philosopher(threading.Thread):
   def __init__(self, index):
       threading.Thread.__init__(self)
       self.index = index
       self.leftFork = forks[self.index]
       self.rightFork = forks[(self.index + 1) % numForks]

   def run(self):
       while True:
           self.leftFork.pickup()
           self.rightFork.pickup()
           self.dining()
           self.leftFork.putdown()
           self.rightFork.putdown()
           self.thinking()
           
   def dining(self):
       print("Philosopher", self.index, " starts to eat.")
       sleep(random.uniform(1,3)/1000)
       print("Philosopher", self.index, " finishes eating and leaves to think.")

   def thinking(self):
       sleep(random.uniform(1,3)/1000)

class Fork():
   def __init__(self, index):
       self.index = index
       self._lock = threading.Lock()
       
   def pickup(self):
       self._lock.acquire()

   def putdown(self):
       self._lock.release()

if __name__ == '__main__':
   #创建叉子与哲学家实例
   forks = [Fork(idx) for idx in range(numForks)]
   philosophers = [Philosopher(idx) for idx in range(numPhilosophers)]

   #开启所有的哲学家线程
   for philosopher in philosophers:
       philosopher.start()

   # 方便 CTRL + C 退出程序
   try:
       while True: sleep(0.1)
   except Exception as e:
       raise e

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58

    事件截图为：
    在这里插入图片描述

    问题解法

    服务生解法

    引入一个餐厅服务生，哲学家必须经过他的允许才能拿起餐叉。服务生要保证桌子上始终有一只及以上的餐叉。

    其实也就是OS中的信号量设置。定义互斥信号量数组chopstick[5]={1,1,1,1,1} 用于实现对5个筷子的互斥访问。并对哲学家按0~4编号，哲学家 i 左边的筷子编号为 i，右边的筷子编号为 (i+1)%5。

    伪码为：

    semaphore chopstick[5]={1,1,1,1,1};
semaphore mutex = 1; //互斥地取筷子
Pi (){ //i号哲学家的进程
while(1){
P(mutex);
P(chopstick[i]); //拿左
P(chopstick[(i+1)%5]); //拿右
V(mutex);
吃饭…
V(chopstick[i]); //放左
V(chopstick[(i+1)%5]); //放右
思考…
}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    python的代码为：

    # -*- coding:utf-8 -*-

import threading
from time import sleep
import os, random


numPhilosophers = numForks = 5


class Philosopher(threading.Thread):
    def __init__(self, index):
        threading.Thread.__init__(self)
        self.index = index
        self.leftFork = forks[self.index]
        self.rightFork = forks[(self.index + 1) % numForks]

    def run(self):
        while True:
            if waiter.serve(self):
                self.dining()
                waiter.clean(self)
            self.thinking()

    def dining(self):
        print("Philosopher", self.index, " starts to eat.")
        sleep(random.uniform(1, 3) / 1000)
        print("Philosopher", self.index, " finishes eating and leaves to think.")

    def thinking(self):
        sleep(random.uniform(1, 3) / 1000)


class Fork():
    def __init__(self, index):
        self.index = index
        self._lock = threading.Lock()

    def pickup(self):
        self._lock.acquire()

    def putdown(self):
        self._lock.release()



class Waiter():
    def __init__(self):
        self.forks = [Fork(idx) for idx in range(numForks)]
        # 最开始餐叉还没有被分配给任何人，所以全部 False
        self.forks_using = [False] * numForks

    # 如果哲学家的左右餐叉都是空闲状态，就为这位哲学家服务提供餐叉
    def serve(self, philor):
        if not self.forks_using[philor.leftFork.index] and not self.forks_using[philor.rightFork.index]:
            self.forks_using[philor.leftFork.index] = True
            self.forks_using[philor.rightFork.index] = True
            self.forks[philor.leftFork.index].pickup()
            self.forks[philor.rightFork.index].pickup()
            return True
        else:
            return False

    #哲学家用餐完毕后，清理并回收餐叉
    def clean(self, philor):
        self.forks[philor.leftFork.index].putdown()
        self.forks[philor.rightFork.index].putdown()
        self.forks_using[philor.leftFork.index] = False
        self.forks_using[philor.rightFork.index]= False

if __name__ == '__main__':
    # 创建叉子与哲学家实例
    waiter = Waiter()
    forks = [Fork(idx) for idx in range(numForks)]
    philosophers = [Philosopher(idx) for idx in range(numPhilosophers)]

    # 开启所有的哲学家线程
    for philosopher in philosophers:
        philosopher.start()

    # 方便 CTRL + C 退出程序
    try:
        while True: sleep(0.1)
    except Exception as e:
        raise e

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85

    资源分级解法

    为资源分配一个偏序或者分级的关系，并约定所有资源都按照这种顺序获取，按相反顺序释放，而且保证不会有两个无关资源同时被同一项工作所需要。在哲学家就餐问题中，资源（餐叉）按照某种规则编号为1至5，每一个工作单元（哲学家）总是先拿起左右两边编号较低的餐叉，再拿编号较高的。用完餐叉后，他总是先放下编号较高的餐叉，再放下编号较低的。这样就能保证编号最大的餐叉不会被竞争了。

    我们只需要在模版的基础上修改哲学家的拿餐叉策略就可以了：

    # -*- coding:utf-8 -*-

import threading
from time import sleep
import os, random


numPhilosophers = numForks = 5

class Philosopher(threading.Thread):
    def __init__(self, index):
        threading.Thread.__init__(self)
        self.index = index
        self.leftFork = forks[self.index]
        self.rightFork = forks[(self.index + 1) % numForks]

    def run(self):
        while True:
            if self.leftFork.index > self.rightFork.index:
                firstFork = self.rightFork
                secondFork = self.leftFork
            else:
                firstFork = self.leftFork
                secondFork = self.rightFork

            firstFork.pickup()
            secondFork.pickup()

            self.dining()

            secondFork.putdown()
            firstFork.putdown()

            self.thinking()

    def dining(self):
        print("Philosopher", self.index, " starts to eat.")
        sleep(random.uniform(1, 3) / 1000)
        print("Philosopher", self.index, " finishes eating and leaves to think.")

    def thinking(self):
        sleep(random.uniform(1, 3) / 1000)


class Fork():
    def __init__(self, index):
        self.index = index
        self._lock = threading.Lock()

    def pickup(self):
        self._lock.acquire()

    def putdown(self):
        self._lock.release()


if __name__ == '__main__':
    # 创建叉子与哲学家实例
    forks = [Fork(idx) for idx in range(numForks)]
    philosophers = [Philosopher(idx) for idx in range(numPhilosophers)]

    # 开启所有的哲学家线程
    for philosopher in philosophers:
        philosopher.start()

    # 方便 CTRL + C 退出程序
    try:
        while True: sleep(0.1)
    except Exception as e:
        raise e

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70

    尽管资源分级能避免死锁，但这种策略并不总是实用的。例如，假设一个工作单元拿着资源3和5，并决定需要资源2，则必须先要释放5，之后释放3，才能得到2，之后必须重新按顺序获取3和5。本来只需要获取2这一个步骤的，现在却需要经过五个步骤了。对需要访问大量数据库记录的计算机程序来说，如果需要先释放高编号的记录才能访问新的记录，那么运行效率就不会高，因此这种方法在这里并不实用。

    但这种方法经常是实际计算机科学问题中最实用的解法，通过为分级锁指定常量，强制获得锁的顺序，就可以解决死锁问题。

    3. Chandy/Misra解法

    1984年，K. Mani Chandy和J. Misra提出了哲学家就餐问题的另一个解法，允许任意的用户（编号P1, …, Pn）争用任意数量的资源。与資源分級解法不同的是，这里编号可以是任意的。

    • 对每一对竞争一个资源的哲学家，新拿一个餐叉，给编号较低的哲学家。每只餐叉都是“干净的”或者“脏的”。最初，所有的餐叉都是脏的。
    • 当一位哲学家要使用资源（也就是要吃东西）时，他必须从与他竞争的邻居那里得到。对每只他当前没有的餐叉，他都发送一个请求。
    • 当拥有餐叉的哲学家收到请求时，如果餐叉是干净的，那么他继续留着，否则就擦干净并交出餐叉。
    • 当某个哲学家吃东西后，他的餐叉就变脏了。如果另一个哲学家之前请求过其中的餐叉，那他就擦干净并交出餐叉。

    这样就能保证没吃到面的大哲有着更高的吃面优先级，这个解法允许很大的并行性，适用于任意大的问题。

    该解法可以看GitHub中的dining_philosophers 项目，同样是用python写的，因为涉及代码很多，这里就不再转述。

  • 相关阅读:
    js使用canvas实现图片鼠标滚轮放大缩小拖拽预览，显示像素坐标，显示像素值
    解决缓存与数据库同步下的同步锁问题之分段锁
    【2023研电赛】华东赛区一等奖：电动叉车永磁同步电机MTPA及弱磁控制研究
    为什么要权值初始化
    【python】TypeError: unhashable type: ‘list‘ 解决方法——简单示例
    Hyperopt：分布式异步超参数优化(Distributed Asynchronous Hyperparameter Optimization)
    【Python】-- Turtle绘图（使用代码画喜欢的图形！）
    Java基础知识篇之函数调用基本原理
    2022 CSP-J 复赛题解
    高等教育心理学：学生情感与意志的发展
  • 原文地址：https://blog.csdn.net/submarineas/article/details/126454925