面试题：并发与同步之哲学家进餐死锁问题解决

资源分配图算法（银行家算法）
- 同步机制：使用一个数据结构来记录每个哲学家的需求（需要的筷子数量）、已分配的筷子数量以及当前可用的筷子数量。在Python中，可以用字典来表示这些信息。
- 资源获取顺序控制：银行家算法通过检查分配资源后系统是否仍处于安全状态来决定是否分配资源。当一个哲学家请求筷子时，系统模拟分配筷子的过程，如果模拟分配后系统存在一个安全序列（即每个哲学家都能依次获得足够的筷子并进餐完成，然后释放资源），则实际分配筷子；否则拒绝分配。
- 示例代码（Python 伪代码）：

# 假设哲学家数量为n
n = 5
# 记录每个哲学家已分配的筷子数量
allocated = {i: 0 for i in range(n)}
# 记录每个哲学家的需求
need = {i: 2 for i in range(n)}
# 当前可用的筷子数量
available = 5

def request_chopsticks(philosopher_id):
    if need[philosopher_id] <= available:
        # 模拟分配
        available -= need[philosopher_id]
        allocated[philosopher_id] += need[philosopher_id]
        need[philosopher_id] = 0
        # 检查是否处于安全状态
        work = available.copy()
        finish = {i: False for i in range(n)}
        while True:
            found = False
            for i in range(n):
                if not finish[i] and need[i] <= work:
                    work += allocated[i]
                    finish[i] = True
                    found = True
            if not found:
                break
        if all(finish.values()):
            # 实际分配
            return True
        else:
            # 撤销模拟分配
            available += need[philosopher_id]
            allocated[philosopher_id] -= need[philosopher_id]
            need[philosopher_id] = 2
            return False
    else:
        return False

破坏死锁的循环等待条件
- 同步机制：可以使用互斥锁（如Python中的threading.Lock）来保护对筷子资源的访问。
- 资源获取顺序控制：规定所有哲学家按照一定的顺序（比如编号从小到大）获取筷子。例如，编号为偶数的哲学家先获取左边的筷子，再获取右边的筷子；编号为奇数的哲学家先获取右边的筷子，再获取左边的筷子。这样就不会形成循环等待，从而避免死锁。
- 示例代码（Python 伪代码，使用threading模块）：

import threading

# 假设哲学家数量为n
n = 5
# 筷子（用锁表示）
chopsticks = [threading.Lock() for _ in range(n)]

def philosopher(philosopher_id):
    if philosopher_id % 2 == 0:
        left = philosopher_id
        right = (philosopher_id + 1) % n
    else:
        left = (philosopher_id + 1) % n
        right = philosopher_id
    chopsticks[left].acquire()
    chopsticks[right].acquire()
    try:
        # 进餐
        pass
    finally:
        chopsticks[right].release()
        chopsticks[left].release()


# 创建并启动线程
threads = []
for i in range(n):
    t = threading.Thread(target=philosopher, args=(i,))
    threads.append(t)
    t.start()

限制同时进餐的哲学家数量
- 同步机制：使用一个信号量（如Python中的threading.Semaphore）来限制同时进餐的哲学家数量。
- 资源获取顺序控制：不需要额外控制资源获取顺序。信号量初始值设置为n - 1（n为哲学家数量），这样最多允许n - 1个哲学家同时尝试获取筷子。因为只有n - 1个哲学家竞争n根筷子，必然至少有一个哲学家能获取到两根筷子，从而打破死锁。
- 示例代码（Python 伪代码，使用threading模块）：

import threading

# 假设哲学家数量为n
n = 5
# 筷子（用锁表示）
chopsticks = [threading.Lock() for _ in range(n)]
# 信号量，限制同时进餐的哲学家数量
semaphore = threading.Semaphore(n - 1)

def philosopher(philosopher_id):
    semaphore.acquire()
    left = philosopher_id
    right = (philosopher_id + 1) % n
    chopsticks[left].acquire()
    chopsticks[right].acquire()
    try:
        # 进餐
        pass
    finally:
        chopsticks[right].release()
        chopsticks[left].release()
        semaphore.release()


# 创建并启动线程
threads = []
for i in range(n):
    t = threading.Thread(target=philosopher, args=(i,))
    threads.append(t)
    t.start()

星途面试题库

面试题：并发与同步之哲学家进餐死锁问题解决

知识考点

面试题答案