xinyin025/learn.lianglianglee.com
1
0
Fork 0
mirror of https://github.com/zhwei820/learn.lianglianglee.com.git synced 2025-09-17 08:46:40 +08:00
Code Issues Actions Packages Projects Releases Wiki Activity
master
learn.lianglianglee.com/专栏/重学操作系统-完/21 哲学家就餐问题：什么情况下会触发饥饿和死锁？.md.html
周伟 0f006e4e9b add
2022-05-11 18:57:05 +08:00

2033 lines
39 KiB
HTML
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

<!DOCTYPE html>
<!-- saved from url=(0046)https://kaiiiz.github.io/hexo-theme-book-demo/ -->
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1.0, user-scalable=no">
<link rel="icon" href="/static/favicon.png">
<title>21 哲学家就餐问题：什么情况下会触发饥饿和死锁？.md.html</title>
<!-- Spectre.css framework -->
<link rel="stylesheet" href="/static/index.css">
<!-- theme css & js -->
<meta name="generator" content="Hexo 4.2.0">
</head>
<body>
<div class="book-container">
<div class="book-sidebar">
<div class="book-brand">
<a href="/">
<img src="/static/favicon.png">
<span>技术文章摘抄</span>
</a>
</div>
<div class="book-menu uncollapsible">
<ul class="uncollapsible">
<li><a href="/" class="current-tab">首页</a></li>
</ul>
<ul class="uncollapsible">
<li><a href="../">上一级</a></li>
</ul>
<ul class="uncollapsible">
<li>
<a href="/专栏/重学操作系统-完/00 开篇词 为什么大厂面试必考操作系统？.md.html">00 开篇词 为什么大厂面试必考操作系统？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/00 课前必读 构建知识体系，可以这样做！.md.html">00 课前必读 构建知识体系，可以这样做！.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/01 计算机是什么：“如何把程序写好”这个问题是可计算的吗？.md.html">01 计算机是什么：“如何把程序写好”这个问题是可计算的吗？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/02 程序的执行：相比 32 位，64 位的优势是什么？（上）.md.html">02 程序的执行：相比 32 位，64 位的优势是什么？（上）.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/03 程序的执行：相比 32 位，64 位的优势是什么？（下）.md.html">03 程序的执行：相比 32 位，64 位的优势是什么？（下）.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/04 构造复杂的程序：将一个递归函数转成非递归函数的通用方法.md.html">04 构造复杂的程序：将一个递归函数转成非递归函数的通用方法.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/05 存储器分级：L1 Cache 比内存和 SSD 快多少倍？.md.html">05 存储器分级：L1 Cache 比内存和 SSD 快多少倍？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/05 (1) 加餐 练习题详解（一）.md.html">05 (1) 加餐 练习题详解（一）.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/06 目录结构和文件管理指令：rm -rf 指令的作用是？.md.html">06 目录结构和文件管理指令：rm -rf 指令的作用是？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/07 进程、重定向和管道指令：xargs 指令的作用是？.md.html">07 进程、重定向和管道指令：xargs 指令的作用是？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/08 用户和权限管理指令： 请简述 Linux 权限划分的原则？.md.html">08 用户和权限管理指令： 请简述 Linux 权限划分的原则？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/09 Linux 中的网络指令：如何查看一个域名有哪些 NS 记录？.md.html">09 Linux 中的网络指令：如何查看一个域名有哪些 NS 记录？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/10 软件的安装： 编译安装和包管理器安装有什么优势和劣势？.md.html">10 软件的安装： 编译安装和包管理器安装有什么优势和劣势？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/11 高级技巧之日志分析：利用 Linux 指令分析 Web 日志.md.html">11 高级技巧之日志分析：利用 Linux 指令分析 Web 日志.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/12 高级技巧之集群部署：利用 Linux 指令同时在多台机器部署程序.md.html">12 高级技巧之集群部署：利用 Linux 指令同时在多台机器部署程序.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/12 (1)加餐 练习题详解（二）.md.html">12 (1)加餐 练习题详解（二）.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/13 操作系统内核：Linux 内核和 Windows 内核有什么区别？.md.html">13 操作系统内核：Linux 内核和 Windows 内核有什么区别？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/14 用户态和内核态：用户态线程和内核态线程有什么区别？.md.html">14 用户态和内核态：用户态线程和内核态线程有什么区别？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/15 中断和中断向量：Javajs 等语言为什么可以捕获到键盘输入？.md.html">15 中断和中断向量：Javajs 等语言为什么可以捕获到键盘输入？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/16 WinMacUnixLinux 的区别和联系：为什么 Debian 漏洞排名第一还这么多人用？.md.html">16 WinMacUnixLinux 的区别和联系：为什么 Debian 漏洞排名第一还这么多人用？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/16 (1)加餐 练习题详解（三）.md.html">16 (1)加餐 练习题详解（三）.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/17 进程和线程：进程的开销比线程大在了哪里？.md.html">17 进程和线程：进程的开销比线程大在了哪里？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/18 锁、信号量和分布式锁：如何控制同一时间只有 2 个线程运行？.md.html">18 锁、信号量和分布式锁：如何控制同一时间只有 2 个线程运行？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/19 乐观锁、区块链：除了上锁还有哪些并发控制方法？.md.html">19 乐观锁、区块链：除了上锁还有哪些并发控制方法？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/20 线程的调度：线程调度都有哪些方法？.md.html">20 线程的调度：线程调度都有哪些方法？.md.html</a>
</li>
<li>
<a class="current-tab" href="/专栏/重学操作系统-完/21 哲学家就餐问题：什么情况下会触发饥饿和死锁？.md.html">21 哲学家就餐问题：什么情况下会触发饥饿和死锁？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/22 进程间通信： 进程间通信都有哪些方法？.md.html">22 进程间通信： 进程间通信都有哪些方法？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/23 分析服务的特性：我的服务应该开多少个进程、多少个线程？.md.html">23 分析服务的特性：我的服务应该开多少个进程、多少个线程？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/23 (1)加餐 练习题详解（四）.md.html">23 (1)加餐 练习题详解（四）.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/24 虚拟内存 ：一个程序最多能使用多少内存？.md.html">24 虚拟内存 ：一个程序最多能使用多少内存？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/25 内存管理单元： 什么情况下使用大内存分页？.md.html">25 内存管理单元： 什么情况下使用大内存分页？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/26 缓存置换算法： LRU 用什么数据结构实现更合理？.md.html">26 缓存置换算法： LRU 用什么数据结构实现更合理？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/27 内存回收上篇：如何解决内存的循环引用问题？.md.html">27 内存回收上篇：如何解决内存的循环引用问题？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/28 内存回收下篇：三色标记-清除算法是怎么回事？.md.html">28 内存回收下篇：三色标记-清除算法是怎么回事？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/28 (1)加餐 练习题详解（五）.md.html">28 (1)加餐 练习题详解（五）.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/29 Linux 下的各个目录有什么作用？.md.html">29 Linux 下的各个目录有什么作用？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/30 文件系统的底层实现：FAT、NTFS 和 Ext3 有什么区别？.md.html">30 文件系统的底层实现：FAT、NTFS 和 Ext3 有什么区别？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/31 数据库文件系统实例：MySQL 中 B 树和 B+ 树有什么区别？.md.html">31 数据库文件系统实例：MySQL 中 B 树和 B+ 树有什么区别？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/32 HDFS 介绍：分布式文件系统是怎么回事？.md.html">32 HDFS 介绍：分布式文件系统是怎么回事？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/32 (1)加餐 练习题详解（六）.md.html">32 (1)加餐 练习题详解（六）.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/33 互联网协议群（TCPIP）：多路复用是怎么回事？.md.html">33 互联网协议群（TCPIP）：多路复用是怎么回事？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/34 UDP 协议：UDP 和 TCP 相比快在哪里？.md.html">34 UDP 协议：UDP 和 TCP 相比快在哪里？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/35 Linux 的 IO 模式：selectpollepoll 有什么区别？.md.html">35 Linux 的 IO 模式：selectpollepoll 有什么区别？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/36 公私钥体系和网络安全：什么是中间人攻击？.md.html">36 公私钥体系和网络安全：什么是中间人攻击？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/36 (1)加餐 练习题详解（七）.md.html">36 (1)加餐 练习题详解（七）.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/37 虚拟化技术介绍：VMware 和 Docker 的区别？.md.html">37 虚拟化技术介绍：VMware 和 Docker 的区别？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/38 容器编排技术：如何利用 K8s 和 Docker Swarm 管理微服务？.md.html">38 容器编排技术：如何利用 K8s 和 Docker Swarm 管理微服务？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/39 Linux 架构优秀在哪里.md.html">39 Linux 架构优秀在哪里.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/40 商业操作系统：电商操作系统是不是一个噱头？.md.html">40 商业操作系统：电商操作系统是不是一个噱头？.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/40 (1)加餐 练习题详解（八）.md.html">40 (1)加餐 练习题详解（八）.md.html</a>
</li>
<li>
<a href="/专栏/重学操作系统-完/41 结束语 论程序员的发展——信仰、选择和博弈.md.html">41 结束语 论程序员的发展——信仰、选择和博弈.md.html</a>
</li>
</ul>
</div>
</div>
<div class="sidebar-toggle" onclick="sidebar_toggle()" onmouseover="add_inner()" onmouseleave="remove_inner()">
<div class="sidebar-toggle-inner"></div>
</div>
<script>
function add_inner() {
let inner = document.querySelector('.sidebar-toggle-inner')
inner.classList.add('show')
}
function remove_inner() {
let inner = document.querySelector('.sidebar-toggle-inner')
inner.classList.remove('show')
}
function sidebar_toggle() {
let sidebar_toggle = document.querySelector('.sidebar-toggle')
let sidebar = document.querySelector('.book-sidebar')
let content = document.querySelector('.off-canvas-content')
if (sidebar_toggle.classList.contains('extend')) { // show
sidebar_toggle.classList.remove('extend')
sidebar.classList.remove('hide')
content.classList.remove('extend')
} else { // hide
sidebar_toggle.classList.add('extend')
sidebar.classList.add('hide')
content.classList.add('extend')
}
}
function open_sidebar() {
let sidebar = document.querySelector('.book-sidebar')
let overlay = document.querySelector('.off-canvas-overlay')
sidebar.classList.add('show')
overlay.classList.add('show')
}
function hide_canvas() {
let sidebar = document.querySelector('.book-sidebar')
let overlay = document.querySelector('.off-canvas-overlay')
sidebar.classList.remove('show')
overlay.classList.remove('show')
}
</script>
<div class="off-canvas-content">
<div class="columns">
<div class="column col-12 col-lg-12">
<div class="book-navbar">
<!-- For Responsive Layout -->
<header class="navbar">
<section class="navbar-section">
<a onclick="open_sidebar()">
<i class="icon icon-menu"></i>
</a>
</section>
</header>
</div>
<div class="book-content" style="max-width: 960px; margin: 0 auto;
overflow-x: auto;
overflow-y: hidden;">
<div class="book-post">
<p id="tip" align="center"></p>
<div><h1>21 哲学家就餐问题：什么情况下会触发饥饿和死锁？</h1>
<p><strong>这一讲给你带来的面试题目是：什么情况下会触发饥饿和死锁</strong>？</p>
<p>读题可知，这道题目在提问“场景”，从表面来看，解题思路是列举几个例子。但是在回答这类面试题前你一定要想一想面试官在考察什么，往往在题目中看到“<strong>什么情况下</strong>”时，其实考察的是你总结和概括信息的能力。</p>
<p>关于上面这道题目，如果你只回答一个场景，而没有输出概括性的总结内容，就很容易被面试官认为对知识理解不到位，因而挂掉面试。另外，<strong>提问死锁和饥饿还有一个更深层的意思，就是考察你在实战中对并发控制算法的理解，是否具备设计并发算法来解决死锁问题并且兼顾性能（并发量）的思维和能力</strong>。</p>
<p>要学习这部分知识有一个非常不错的模型，就是哲学家就餐问题。1965 年，计算机科学家 Dijkstra 为了帮助学生更好地学习并发编程设计的一道练习题，后来逐渐成为大家广泛讨论的问题。</p>
<h3>哲学家就餐问题</h3>
<p>问题描述如下：有 5 个哲学家，围着一个圆桌就餐。圆桌上有 5 份意大利面和 5 份叉子。哲学家比较笨，他们必须拿到左手和右手的 2 个叉子才能吃面。哲学不饿的时候就在思考，饿了就去吃面，吃面的必须前提是拿到 2 个叉子，吃完面哲学家就去思考。</p>
<p><img src="assets/CgqCHl-04I2AWTRGAABMYcirc5o121.png" alt="Drawing 0.png" /></p>
<p>假设每个哲学家用一个线程实现，求一种并发控制的算法，让哲学家们按部就班地思考和吃面。当然我这里做了一些改动，比如 Dijkstra 那个年代线程还没有普及，最早的题目每个哲学家是一个进程。</p>
<h3>问题的抽象</h3>
<p>接下来请你继续思考，我们对问题进行一些抽象，比如哲学是一个数组，编号 0~4。我这里用 Java 语言给你演示，哲学家是一个类，代码如下：</p>
<pre><code>static class Philosopher implements Runnable {
private static Philosopher[] philosophers;
static {
philosophers = new Philosopher[5];
}
}
</code></pre>
<p>这里考虑叉子也使用编号 0~4，代码如下：</p>
<pre><code>private static Integer[] forks;
private static Philosopher[] philosophers;
static {
for(int i = 0; i &lt; 5; i++) {
philosophers[i] = new Philosopher(i);
forks[i] = -1;
}
}
</code></pre>
<p><code>forks[i]</code>的值等于 x，相当于编号为<code>i</code>的叉子被编号为 x 的哲学家拿起；如果等于<code>-1</code>，那么叉子目前放在桌子上。</p>
<p>我们经常需要描述左、右的关系，为了方便计算，可以设计 1 个帮助函数（helper functions），帮助我们根据一个编号，计算它左边的编号。</p>
<pre><code> private static int LEFT(int i) {
return i == 0 ? 4 : i-1;
}
</code></pre>
<p>假设和哲学家编号一致的叉子在右边，这样如果要判断编号为<code>id</code>哲学家是否可以吃面，需要这样做：</p>
<pre><code>if(forks[LEFT(id)] == id &amp;&amp; forks[id] == id) {
// 可以吃面
}
</code></pre>
<p>然后定义一个<code>_take</code>函数拿起编号为<code>i</code>叉子; 再设计一个<code>_put</code>方法放下叉子：</p>
<pre><code>void _take(int i) throws InterruptedException {
Thread.sleep(10);
forks[i] = id;
}
void _put(int i){
if(forks[i] == id)
forks[i] = -1;
}
</code></pre>
<p><code>_take</code>函数之所以会等待 10ms，是因为<strong>哲学家就餐问题的实际意义，是 I/O 处理的场景，拿起叉子好比读取磁盘，需要有一等的时间开销，这样思考才有意义</strong>。</p>
<p>然后是对<code>think</code>和<code>eat</code>两个方法的抽象。首先我封装了一个枚举类型，描述哲学家的状态，代码如下：</p>
<pre><code>enum PHIS {
THINKING,
HUNGRY,
EATING
}
</code></pre>
<p>然后实现<code>think</code>方法，<code>think</code>方法不需要并发控制，但是这里用<code>Thread.sleep</code>模拟实际思考需要的开销，代码如下：</p>
<pre><code>void think() throws InterruptedException {
System.out.println(String.format(&quot;Philosopher %d thinking...&quot;, id));
Thread.sleep((long) Math.floor(Math.random()*1000));
this.state = PHIS.HUNGRY;
</code></pre>
<p>最后是<code>eat</code>方法：</p>
<pre><code>void eat() throws InterruptedException {
synchronized (forks) {
if(forks[LEFT(id)] == id &amp;&amp; forks[id] == id) {
this.state = PHIS.EATING;
} else {
return;
}
}
Thread.sleep((long) Math.floor(Math.random()*1000));
}
</code></pre>
<p><code>eat</code>方法依赖于<code>forks</code>对象的锁，相当于<code>eat</code>方法这里会同步——因为这里有读取临界区操作做。<code>Thread.sleep</code>依然用于描述<code>eat</code>方法的时间开销。<code>sleep</code>方法没有放到<code>synchronized</code>内是因为<strong>在并发控制时，应该尽量较少锁的范围，这样可以增加更大的并发量</strong>。</p>
<p>以上，我们对问题进行了一个基本的抽象。接下来请你思考在什么情况会发生死锁？</p>
<h3>死锁（DeadLock）和活锁（LiveLock）</h3>
<p>首先，可以思考一种最简单的解法，每个哲学家用一个<code>while</code>循环表示，代码如下：</p>
<pre><code>while(true){
think();
_take(LEFT(id));
_take(id);
eat();
_put(LEFT(id));
_put(id);
}
void _take(id){
while(forks[id] != -1) { Thread.yield(); }
Thread.sleep(10); // 模拟I/O用时
}
</code></pre>
<p><code>_take</code>可以考虑阻塞，直到哲学家得到叉子。上面程序我们还没有进行并发控制，会发生竞争条件。 顺着这个思路，就可以想到加入并发控制，代码如下：</p>
<pre><code>while(true){
think();
synchronized(fork[LEFT(id)]) {
_take(LEFT(id));
synchronized(fork[id]) {
_take(id);
}
}
eat();
synchronized(fork[LEFT(id)]) {
_put(LEFT(id));
synchronized(fork[id]) {
_put(id);
}
}
}
</code></pre>
<p>上面的并发控制，会发生死锁问题，大家可以思考这样一个时序，如果 5 个哲学家都同时通过<code>synchronized(fork[LEFT(id)])</code>，有可能会出现下面的情况：</p>
<ul>
<li>第 0 个哲学家获得叉子 4，接下来请求叉子 0；</li>
<li>第 1 个哲学家获得叉子 0，接下来请求叉子 1；</li>
<li>第 2 个哲学家获得叉子 1，接下来请求叉子 2；</li>
<li>第 3 个哲学家获得叉子 2，接下来请求叉子 3；</li>
<li>第 4 个哲学家获得叉子 3，接下来请求叉子 4。</li>
</ul>
<p>为了帮助你理解，这里我画了一幅图。</p>
<p><img src="assets/CgqCHl-1AGWABRYZAACklm4__ZQ120.png" alt="11111.png" /></p>
<p>如上图所示，可以看到这是一种循环依赖的关系，在这种情况下所有哲学家都获得了一个叉子，并且在等待下一个叉子。这种等待永远不会结束，因为没有哲学家愿意放弃自己拿起的叉子。</p>
<p>以上这种情况称为**死锁（Deadlock），<strong>这是一种</strong>饥饿（Starvation）**的形式。从概念上说，死锁是线程间互相等待资源，但是没有一个线程可以进行下一步操作。饥饿就是因为某种原因导致线程得不到需要的资源，无法继续工作。死锁是饥饿的一种形式，因为循环等待无法得到资源。哲学家就餐问题，会形成一种环状的死锁（循环依赖）， 因此非常具有代表性。</p>
<p>死锁有 4 个基本条件。</p>
<ol>
<li><strong>资源存在互斥逻辑：每次只有一个线程可以抢占到资源</strong>。这里是哲学家抢占叉子。</li>
<li><strong>持有等待</strong>：这里哲学家会一直等待拿到叉子。</li>
<li><strong>禁止抢占：如果拿不到资源一直会处于等待状态，而不会释放已经拥有的资源</strong>。</li>
<li><strong>循环等待</strong>：这里哲学家们会循环等待彼此的叉子。</li>
</ol>
<p>刚才提到死锁也是一种饥饿（Starvation）的形式，饥饿比较简单，就是线程长期拿不到需要的资源，无法进行下一步操作。</p>
<p>要解决死锁的问题，可以考虑哲学家拿起 1 个叉子后，如果迟迟没有等到下一个叉子，就放弃这次操作。比如 Java 的 Lock Interface 中，提供的<code>tryLock</code>方法，就可以实现定时获取：</p>
<pre><code>var lock = new ReentrantLock();
lock.tryLock(5, TimeUnit.SECONDS);
</code></pre>
<p>Java 提供的这个能力是拿不到锁，就报异常，并可以依据这个能力开发释放已获得资源的能力。</p>
<p>但是这样，我们会碰到一个叫作活锁（LiveLock）的问题。LiveLock 也是一种饥饿。可能在某个时刻，所有哲学及都拿起了左手的叉子，然后发现右手的叉子拿不到，就放下了左手的叉子——如此周而复始，这就是一种活锁。所有线程都在工作，但是没有线程能够进一步——解决问题。</p>
<p>在实际工作场景下，LiveLock 可以靠概率解决，因为同时拿起，又同时放下这种情况不会很多。实际工作场景很多系统，确实依赖于这个问题不频发。但是，优秀的设计者不能把系统设计依托在一个有概率风险的操作上，因此我们需要继续往深一层思考。</p>
<h3>解决方案</h3>
<p>其实解决上述问题有很多的方案，最简单、最直观的方法如下：</p>
<pre><code>while(true){
synchronized(someLock) {
think();
_take(LEFT(id));
_take(id);
eat();
_put(LEFT(id));
_put(id);
}
}
</code></pre>
<p>上面这段程序同时只允许一个哲学家使用所有资源，我们用<code>synchronized</code>构造了一种排队的逻辑。而哲学家，每次必须拿起所有的叉子，吃完，再到下一哲学家。 这样并发度是 1，同时最多有一个线程在执行。 这样的方式可以完成任务，但是性能太差。</p>
<p>另一种方法是规定拿起过程必须同时拿起，放下过程也同时放下，代码如下：</p>
<pre><code>while(true){
think();
synchronized(someLock) {
_takeForks();
}
eat();
synchronized(someLock) {
_puts();
}
}
void _takeForks(){
if( forks[LEFT(id)] == -1 &amp;&amp; forks[id] == -1 ) {
forks[LEFT(id)] = id;
forks[id] = id;
}
}
void _puts(){
if(forks[LEFT(id)] == id)
forks[LEFT(id)] = -1;
if(forks[id] == id)
forks[id] = -1;
}
</code></pre>
<p>上面这段程序，<code>think</code>函数没有并发控制，一个哲学家要么拿起两个叉子，要么不拿起，这样并发度最高为 2（最多有两个线程同时执行）。而且，这个算法中只有一个锁，因此不存在死锁和饥饿问题。</p>
<p>到这里，我们已经对这个问题有了一个初步的方案，那么如何进一步优化呢？</p>
<h3>思考和最终方案</h3>
<p>整个问题复杂度的核心在于哲学家拿起叉子是有成本的。好比线程读取磁盘，需要消耗时间。哲学家的思考，是独立的。好比读取了磁盘数据，进行计算。那么有没有办法允许 5 个哲学家都同时去拿叉子呢？这样并发度是最高的。</p>
<p>经过初步思考，马上会发现这里有环状依赖， 会出现<strong>死锁</strong>。 原因就是如果 5 个哲学家同时拿叉子，那就意味着有的哲学家必须要放弃叉子。但是如果不放下会出现什么情况呢？</p>
<p>假设当一个哲学家发现自己拿不到两个叉子的时候，他去和另一个哲学家沟通把自己的叉子给对方。这样就相当于，有一个转让方法。相比于磁盘 I/O，转让内存中的数据成本就低的多了。 我们假设有这样一个转让的方法，代码如下：</p>
<pre><code> void _transfer(int fork, int philosopher) {
forks[fork] = philosopher;
dirty[fork] = false;
}
</code></pre>
<p>这个方法相当于把叉子转让给另一个哲学家，这里你先不用管上面代码中的 dirty，后文中会讲到。而获取叉子的过程，我们可以进行调整，代码如下：</p>
<pre><code>void take(int i) throws InterruptedException {
synchronized (forks[i]) {
if(forks[i] == -1) {
_take(id);
} else {
Philosopher other = philosophers[forks[i]];
if(other.state != PHIS.EATING &amp;&amp; dirty[i]) {
other._transfer(i, forks[i]);
}
}
}
}
void _take(int i) throws InterruptedException {
Thread.sleep(10);
forks[i] = id;
}
</code></pre>
<p>这里我们把每个叉子看作一个锁，有多少个叉子，就有多少个锁，相当于同时可以拿起 5 个叉子（并发度是 5）。如果当前没有人拿起叉子，那么可以自己拿起。 如果叉子属于其他哲学家，就需要判断对方的状态。只要对方不在<code>EATING</code>，就可以考虑转让叉子。</p>
<p>最后是对 LiveLock 的思考，为了避免叉子在两个哲学家之间来回转让，我们为每个叉子增加了一个<code>dirty</code>属性。一开始叉子的<code>dirty</code>是<code>true</code>，每次转让后，哲学家会把自己的叉子擦干净给另一个哲学家。转让的前置条件是叉子是<code>dirty</code>的，所以叉子在两个哲学家之间只会转让一次。</p>
<p>通过上面算法，我们就可以避免死锁、饥饿以及提高读取数据（获取叉子）的并发度。最后完整的程序如下，给你做参考：</p>
<pre><code>package test;
import java.util.Arrays;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.StampedLock;
public class DiningPhilosophers {
enum PHIS {
THINKING,
HUNGRY,
EATING
}
static class Philosopher implements Runnable {
private static Philosopher[] philosophers;
private static Integer[] forks;
private static boolean[] dirty;
private PHIS state = PHIS.THINKING;
static {
philosophers = new Philosopher[5];
forks = new Integer[5];
dirty = new boolean[5];
for(int i = 0; i &lt; 5; i++) {
philosophers[i] = new Philosopher(i);
forks[i] = -1;
dirty[i] = true;
}
}
private static int LEFT(int i) {
return i == 0 ? 4 : i-1;
}
public Philosopher(int id) {
this.id = id;
}
private int id;
void think() throws InterruptedException {
System.out.println(String.format(&quot;Philosopher %d thinking...&quot;, id));
Thread.sleep((long) Math.floor(Math.random()*1000));
this.state = PHIS.HUNGRY;
}
System.out.println(Arrays.toString(forks));
//System.out.println(Arrays.toString(dirty));
if(forks[LEFT(id)] == id &amp;&amp; forks[id] == id) {
this.state = PHIS.EATING;
} else {
return;
}
}
System.out.println(String.format(&quot;Philosopher %d eating...&quot;, id));
Thread.sleep((long) Math.floor(Math.random()*1000));
synchronized (forks) {
dirty[LEFT(id)] = true;
dirty[id] = true;
}
var lock = new ReentrantLock();
lock.tryLock(5, TimeUnit.SECONDS);
state = PHIS.THINKING;
}
void _take(int i) throws InterruptedException {
Thread.sleep(10);
forks[i] = id;
}
void _transfer(int fork, int philosopher) {
forks[fork] = philosopher;
dirty[fork] = false;
}
void _putdown(int i) throws InterruptedException {
Thread.sleep(10);
forks[i] = -1;
}
void take(int i) throws InterruptedException {
synchronized (forks[i]) {
if(forks[i] == -1) {
_take(id);
} else {
Philosopher other = philosophers[forks[i]];
if(other.state != PHIS.EATING &amp;&amp; dirty[i]) {
other._transfer(i, forks[i]);
}
}
}
}
void takeForks() throws InterruptedException {
take(LEFT(id));
take(id);
}
@Override
public void run() {
try {
while(true) {
think();
while (state == PHIS.HUNGRY) {
takeForks();
System.out.println(&quot;here--&quot; + Math.random());
eat();
}
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
public static void main(String[] args) {
for(int i = 0; i &lt; 5; i++) {
new Thread(new Philosopher(i)).start();
}
}
}
</code></pre>
<h3>总结</h3>
<p><strong>那么通过这节课的学习，你现在可以尝试来回答本节关联的面试题目：什么情况下会触发饥饿和死锁</strong>？</p>
<p><strong>【解析】</strong> 线程需要资源没有拿到，无法进行下一步，就是饥饿。死锁（Deadlock）和活锁（Livelock）都是饥饿的一种形式。 非抢占的系统中，互斥的资源获取，形成循环依赖就会产生死锁。死锁发生后，如果利用抢占解决，导致资源频繁被转让，有一定概率触发活锁。死锁、活锁，都可以通过设计并发控制算法解决，比如哲学家就餐问题。</p>
</div>
</div>
<div>
<div style="float: left">
<a href="/专栏/重学操作系统-完/20 线程的调度：线程调度都有哪些方法？.md.html">上一页</a>
</div>
<div style="float: right">
<a href="/专栏/重学操作系统-完/22 进程间通信： 进程间通信都有哪些方法？.md.html">下一页</a>
</div>
</div>
</div>
</div>
</div>
</div>
<a class="off-canvas-overlay" onclick="hide_canvas()"></a>
</div>
<script defer src="https://static.cloudflareinsights.com/beacon.min.js/v652eace1692a40cfa3763df669d7439c1639079717194" integrity="sha512-Gi7xpJR8tSkrpF7aordPZQlW2DLtzUlZcumS8dMQjwDHEnw9I7ZLyiOj/6tZStRBGtGgN6ceN6cMH8z7etPGlw==" data-cf-beacon='{"rayId":"70997d7d0a713cfa","version":"2021.12.0","r":1,"token":"1f5d475227ce4f0089a7cff1ab17c0f5","si":100}' crossorigin="anonymous"></script>
</body>
<!-- Global site tag (gtag.js) - Google Analytics -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-NPSEEVD756"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag() {
dataLayer.push(arguments);
}
gtag('js', new Date());
gtag('config', 'G-NPSEEVD756');
var path = window.location.pathname
var cookie = getCookie("lastPath");
console.log(path)
if (path.replace("/", "") === "") {
if (cookie.replace("/", "") !== "") {
console.log(cookie)
document.getElementById("tip").innerHTML = "<a href='" + cookie + "'>跳转到上次进度</a>"
}
} else {
setCookie("lastPath", path)
}
function setCookie(cname, cvalue) {
var d = new Date();
d.setTime(d.getTime() + (180 * 24 * 60 * 60 * 1000));
var expires = "expires=" + d.toGMTString();
document.cookie = cname + "=" + cvalue + "; " + expires + ";path = /";
}
function getCookie(cname) {
var name = cname + "=";
var ca = document.cookie.split(';');
for (var i = 0; i < ca.length; i++) {
var c = ca[i].trim();
if (c.indexOf(name) === 0) return c.substring(name.length, c.length);
}
return "";
}
</script>
</html>
Reference in New Issue View Git Blame Copy Permalink