<?php
/**
 * ============================================================
 *  现代操作系统 · 第六章《死锁》大白话 + 代码例子
 * ============================================================
 *  作用：31 个死锁概念，每条 = 大白话 + 一段 PHP 代码示例。
 *  说明：死锁多为算法与模型，几乎全部用 PHP 代码模拟其思想。
 *  运行：php deadlock.php            全部
 *        php deadlock.php 260        看第 260 条(银行家算法)
 *        php deadlock.php 抢占        关键词搜索
 * ============================================================
 */

declare(strict_types=1);

final class Topic
{
    public function __construct(
        public readonly int $no,
        public readonly string $title,
        public readonly string $plain,
        public readonly string $code
    ) {}
}

final class DeadlockBook
{
    /** @var Topic[] */
    private array $topics = [];

    public function __construct()
    {
        $this->load();
    }

    private function load(): void
    {
        $data = [
            240 => ['资源的概念',
                '进程要用的东西(CPU、内存、打印机、文件、锁)统称资源，有的能共享有的得独占。',
                <<<'CODE'
$resources = [
    'printer' => ['count' => 1, 'shareable' => false], // 独占
    'memory'  => ['count' => 1024, 'shareable' => false],
    'file_ro' => ['count' => 1, 'shareable' => true],  // 只读可共享
];
CODE],

            241 => ['可抢占资源与不可抢占资源',
                '可抢占=能从进程手里安全抢走再还(如内存)；不可抢占=抢了就坏事(如刻录中的光盘)。',
                <<<'CODE'
$preemptable    = ['memory', 'cpu'];          // 可安全抢走再还
$nonPreemptable = ['printer', 'cd_burner'];   // 抢了会出错
function canPreempt($res) {
    return in_array($res, ['memory', 'cpu']);
}
CODE],

            242 => ['资源获取',
                '进程用资源的标准三步：申请→使用→释放；申请不到就阻塞等待。',
                <<<'CODE'
function useResource(&$res, $proc) {
    while ($res['owner'] !== null) block($proc); // 1.申请(占用就等)
    $res['owner'] = $proc;                        // 拿到
    /* 2.使用 ... */
    $res['owner'] = null;                         // 3.释放
}
CODE],

            243 => ['死锁的定义',
                '一组进程互相卡住：每个都在等别人手里的资源，谁也不肯放，于是永远僵着。',
                <<<'CODE'
// A 占R1 等R2; B 占R2 等R1 -> 谁都动不了
$state = [
    'A' => ['holds' => 'R1', 'wants' => 'R2'],
    'B' => ['holds' => 'R2', 'wants' => 'R1'],
];
// 形成环 -> 死锁
CODE],

            244 => ['资源死锁',
                '最常见的死锁：进程们卡在对独占资源的循环等待上。',
                <<<'CODE'
function resourceDeadlock($holds, $wants) {
    // 若 holds/wants 构成环, 即资源死锁
    return hasCycle($holds, $wants);
}
CODE],

            245 => ['死锁产生的条件',
                '四个条件同时满足才会死锁：互斥、占有并等待、不可抢占、循环等待。缺一个就不会。',
                <<<'CODE'
$conditions = [
    '互斥'       => true,  // 资源独占
    '占有并等待' => true,  // 拿着一个还要别的
    '不可抢占'   => true,  // 不能强行夺走
    '循环等待'   => true,  // 形成等待环
];
// 四者全 true 才可能死锁; 破坏任一即可预防
CODE],

            246 => ['死锁建模',
                '用有向图建模：进程、资源画成点，"占有"和"申请"画成箭头，图里有环就有死锁。',
                <<<'CODE'
$graph = [               // 边: 谁指向谁
    'R1' => 'A',         // R1 被 A 占有
    'A'  => 'R2',        // A 申请 R2
    'R2' => 'B',         // R2 被 B 占有
    'B'  => 'R1',        // B 申请 R1 -> 成环!
];
CODE],

            247 => ['资源分配图',
                '上面这种图的正式名称；检测死锁 = 在图里找环。',
                <<<'CODE'
function hasCycle($edges) {           // 简易找环(DFS)
    $visit = function($node, $path) use (&$visit, $edges) {
        if (in_array($node, $path)) return true;     // 回到走过的点=环
        return isset($edges[$node])
            && $visit($edges[$node], [...$path, $node]);
    };
    foreach ($edges as $n => $_) if ($visit($n, [])) return true;
    return false;
}
CODE],

            248 => ['处理死锁的策略',
                '四种态度：装看不见(鸵鸟)、出了再查再恢复、动态避免、从根上预防。',
                <<<'CODE'
$strategies = [
    'ostrich'   => '假装没问题(概率低就忍)',
    'detect'    => '允许发生, 检测后恢复',
    'avoid'     => '动态判断, 不进危险状态',
    'prevent'   => '破坏四条件之一, 根本杜绝',
];
CODE],

            249 => ['鸵鸟算法',
                '把头埋沙里假装看不见：死锁极少发生时，处理成本比偶尔重启还高，干脆不管。',
                <<<'CODE'
function ostrich($deadlockProbability) {
    if ($deadlockProbability < 0.001)
        return "忽略, 真卡了就重启";   // 大多数通用系统的选择
    return "需要正经处理";
}
CODE],

            250 => ['死锁检测与恢复',
                '不预防，让它发生；系统定期跑检测算法找出死锁，再想办法解开。',
                <<<'CODE'
function detectAndRecover($graph) {
    if (hasCycle($graph)) {           // 周期性检测
        echo "检测到死锁!\n";
        recover($graph);              // 抢占/回滚/杀进程
    }
}
CODE],

            251 => ['每种类型一个资源的死锁检测',
                '每类资源只有一个时，直接在资源分配图里找环，有环即死锁。',
                <<<'CODE'
// 每种资源仅1个 -> 找环即可
function detectSingle($edges) {
    return hasCycle($edges) ? "死锁" : "正常";
}
CODE],

            252 => ['每种类型多个资源的死锁检测',
                '每类有多个时用矩阵算法：拿现有资源逐个"满足并回收"，剩下凑不齐的进程就是死锁。',
                <<<'CODE'
function detectMulti($available, $request, $allocation) {
    $work = $available; $finish = array_fill(0, count($request), false);
    do {
        $progress = false;
        foreach ($request as $i => $need) {
            if (!$finish[$i] && lessEq($need, $work)) {
                foreach ($allocation[$i] as $r => $v) $work[$r] += $v; // 回收
                $finish[$i] = $progress = true;
            }
        }
    } while ($progress);
    return in_array(false, $finish);  // 还有没完成的 -> 死锁
}
CODE],

            253 => ['从死锁中恢复',
                '检测到死锁后解开它的三招：抢占资源、回滚到检查点、直接杀进程。',
                <<<'CODE'
function recover($deadlocked, $method) {
    return match ($method) {
        'preempt'  => preemptResource($deadlocked), // 抢
        'rollback' => rollbackToCheckpoint($deadlocked), // 退
        'kill'     => killProcess($deadlocked),      // 杀
    };
}
CODE],

            254 => ['利用抢占恢复',
                '临时把资源从某进程强行夺过来给别人用，缓解后再还回去(对某些资源很难)。',
                <<<'CODE'
function preemptResource(&$res, $from, $to) {
    $saved = $res['state'];           // 先保存被抢者的状态
    $res['owner'] = $to;              // 强行转交
    // ... 用完 ...
    $res['owner'] = $from; $res['state'] = $saved; // 再还回去
}
CODE],

            255 => ['利用回滚恢复',
                '进程定期存检查点，死锁时让它回退到之前某个安全点，释放资源重来。',
                <<<'CODE'
$checkpoints = [];
function checkpoint(&$cps, $proc, $state) { $cps[$proc][] = $state; }
function rollback(&$cps, $proc) {
    return array_pop($cps[$proc]);    // 回退到上一个检查点, 释放资源
}
CODE],

            256 => ['通过杀死进程恢复',
                '最粗暴：直接干掉死锁环里的一个进程，让它放出资源；挑代价最小的杀。',
                <<<'CODE'
function killVictim($deadlocked) {
    usort($deadlocked, fn($a,$b)=>$a['cost']-$b['cost']);
    $victim = $deadlocked[0];         // 挑重启代价最小的
    posix_kill($victim['pid'], SIGKILL);
}
CODE],

            257 => ['死锁避免',
                '不破坏条件，而是每次分配前算一算：分了会不会进入危险局面，会就不分。',
                <<<'CODE'
function tryAllocate($state, $req) {
    $next = applyRequest($state, $req);
    return isSafe($next) ? "批准" : "拒绝(会变不安全)"; // 算完再决定
}
CODE],

            258 => ['资源轨迹图',
                '用二维图画两个进程的执行轨迹，某些区域(都要独占资源)是禁区，进去就可能死锁。',
                <<<'CODE'
// 横轴=进程A进度, 纵轴=进程B进度
// 两者都要持有同一组资源的区域 = 不安全禁区
function isUnsafeRegion($a, $b, $forbidden) {
    return in_array([$a, $b], $forbidden); // 轨迹别踏入禁区
}
CODE],

            259 => ['安全状态与不安全状态',
                '安全=存在某个顺序能让所有进程都顺利跑完；不安全不一定死锁但有风险。',
                <<<'CODE'
function isSafe($available, $max, $allocation) {
    $need = []; foreach ($max as $i=>$m)
        foreach ($m as $r=>$v) $need[$i][$r] = $v - $allocation[$i][$r];
    // 能找到一个安全序列就是安全 (见银行家算法)
    return findSafeSequence($available, $need, $allocation) !== null;
}
CODE],

            260 => ['单个资源的银行家算法',
                '像银行放贷：只有当满足某客户后还能依次满足其他人时才放，保证不会全员要不到。',
                <<<'CODE'
function bankerSingle($has, $max, $alloc, $avail) {
    $need = array_map(fn($m,$a)=>$m-$a, $max, $alloc);
    $finish = array_fill(0, count($need), false);
    do {
        $found = false;
        foreach ($need as $i=>$n)
            if (!$finish[$i] && $n <= $avail) {        // 能满足
                $avail += $alloc[$i]; $finish[$i]=$found=true; // 跑完归还
            }
    } while ($found);
    return !in_array(false, $finish) ? "安全" : "不安全";
}
CODE],

            261 => ['多个资源的银行家算法',
                '把单资源版扩展成向量/矩阵：每类资源都要能依次满足，才算安全可放。',
                <<<'CODE'
function bankerMulti($avail, $max, $alloc) {
    $need = [];
    foreach ($max as $i=>$m) foreach ($m as $r=>$v) $need[$i][$r]=$v-$alloc[$i][$r];
    $work=$avail; $finish=array_fill(0,count($need),false);
    do { $found=false;
        foreach ($need as $i=>$n)
            if (!$finish[$i] && lessEq($n,$work)) {     // 向量比较
                foreach ($alloc[$i] as $r=>$v) $work[$r]+=$v; // 归还
                $finish[$i]=$found=true;
            }
    } while ($found);
    return !in_array(false,$finish) ? "安全" : "不安全";
}
CODE],

            262 => ['死锁预防',
                '从设计上破坏四个必要条件中的任意一个，让死锁压根没法形成。',
                <<<'CODE'
$prevention = [
    '破坏互斥'       => '资源尽量可共享(如假脱机)',
    '破坏占有并等待' => '一次性申请所有资源',
    '破坏不可抢占'   => '允许抢占',
    '破坏循环等待'   => '资源编号, 按序申请',
];
CODE],

            263 => ['破坏互斥条件',
                '尽量让资源可共享而非独占，比如打印机用假脱机，谁都往队列丢，不直接占设备。',
                <<<'CODE'
$printQueue = [];                     // 假脱机: 没人直接独占打印机
function spool(&$queue, $job) { $queue[] = $job; } // 都丢进队列
// 由打印守护进程一个个打 -> 进程间无需互斥争打印机
CODE],

            264 => ['破坏占有并等待条件',
                '要求进程一开始就一次性申请到全部资源，要么全给要么全不给，不许拿一半再等。',
                <<<'CODE'
function allOrNothing($need, $avail) {
    if (lessEq($need, $avail)) {      // 全部能满足才分配
        return "全部分配";
    }
    return "一个都不给, 等齐了再来";    // 不许占着一部分等其余
}
CODE],

            265 => ['破坏不可抢占条件',
                '允许把资源从等待中的进程手里抢走；它申请新资源不成时，得先释放已占的。',
                <<<'CODE'
function requestOrRelease(&$proc, $newRes, $avail) {
    if (!lessEq($newRes, $avail)) {
        releaseAll($proc);            // 拿不到新的, 就先放掉手里全部
        block($proc);                 // 然后整体重等
    }
}
CODE],

            266 => ['破坏环路等待条件',
                '给所有资源编号，规定只能按号从小到大申请，这样永远绕不成环。',
                <<<'CODE'
$resourceOrder = ['R1'=>1, 'R2'=>2, 'R3'=>3]; // 全局编号
function requestInOrder($held, $want, $order) {
    foreach ($held as $h)
        if ($order[$want] <= $order[$h])
            die("违规! 必须按编号递增申请"); // 强制有序 -> 无环
}
CODE],

            267 => ['通信死锁',
                '不是争资源，而是互相等对方的消息：A 等 B 的回复，B 也等 A 的，谁都不发。',
                <<<'CODE'
// A 等 B 的消息, B 也等 A 的 -> 通信死锁
// 解法: 超时重发
function recvWithTimeout($sock, $timeout) {
    $msg = recv($sock, $timeout);
    if ($msg === null) resend();      // 超时没收到就重发, 打破僵局
    return $msg;
}
CODE],

            268 => ['活锁',
                '没卡死但也没进展：进程们一直礼貌地互相让，结果谁都没占到，白忙活。',
                <<<'CODE'
// 两人过道互相让, 同时左闪右闪, 永远过不去
function livelock(&$a, &$b) {
    while ($a->pos == $b->pos) {
        $a->step(); $b->step();       // 都在动, 但同步避让 -> 永不通过
    }
}
// 解法: 加随机退避
CODE],

            269 => ['饥饿',
                '某进程一直被插队、永远轮不到资源；不是死锁(系统在动)，但它个人饿死。',
                <<<'CODE'
function alloc($queue, $policy) {
    if ($policy == 'shortest_first')
        return min($queue);           // 小任务总插队 -> 大任务饿死
    return array_shift($queue);       // FCFS 才公平, 不饿死
}
CODE],

            270 => ['两阶段加锁',
                '数据库常用：第一阶段只加锁(失败就全放重来)，全锁到手才进第二阶段干活，避免死锁。',
                <<<'CODE'
function twoPhaseLock($items) {
    $locked = [];
    foreach ($items as $it) {         // 阶段1: 只加锁
        if (!tryLock($it)) {
            foreach ($locked as $l) unlock($l); // 任一失败, 全放
            return retry();                       // 重来
        }
        $locked[] = $it;
    }
    doWork($items);                   // 阶段2: 全锁到手才干活
    foreach ($locked as $l) unlock($l);
}
CODE],
        ];

        foreach ($data as $no => [$title, $plain, $code]) {
            $this->topics[$no] = new Topic($no, $title, $plain, $code);
        }
    }

    public function renderAll(): void
    {
        $this->printHeader('现代操作系统 · 第六章《死锁》大白话 + 代码例子');
        foreach ($this->topics as $t) $this->printTopic($t);
        $this->printFooter(count($this->topics));
    }

    public function renderOne(int $no): void
    {
        if (!isset($this->topics[$no])) {
            echo "⚠️  没有第 {$no} 条（本章 240~270）\n";
            return;
        }
        $this->printHeader("第 {$no} 条");
        $this->printTopic($this->topics[$no]);
    }

    public function search(string $kw): void
    {
        $hit = array_filter(
            $this->topics,
            fn(Topic $t) => mb_strpos($t->title, $kw) !== false
                         || mb_strpos($t->plain, $kw) !== false
                         || mb_strpos($t->code, $kw) !== false
        );
        if (!$hit) { echo "🔍 没找到包含“{$kw}”的条目\n"; return; }
        $this->printHeader("搜索“{$kw}”，命中 " . count($hit) . " 条");
        foreach ($hit as $t) $this->printTopic($t);
    }

    private function printHeader(string $title): void
    {
        echo "\n" . str_repeat('=', 62) . "\n  {$title}\n" . str_repeat('=', 62) . "\n";
    }

    private function printTopic(Topic $t): void
    {
        printf("\n【%03d】%s\n", $t->no, $t->title);
        echo "  ▷ 大白话：" . wordwrap_cn($t->plain, 36, "\n            ") . "\n";
        echo "  ▶ 代码例子：\n";
        foreach (explode("\n", $t->code) as $line) {
            echo "      | " . $line . "\n";
        }
    }

    private function printFooter(int $count): void
    {
        echo "\n" . str_repeat('-', 62) . "\n";
        echo "  共 {$count} 条，每条含“大白话 + PHP代码例子”。\n";
        echo str_repeat('-', 62) . "\n";
    }
}

/** 中文换行 */
function wordwrap_cn(string $text, int $width, string $break): string
{
    $len = mb_strlen($text);
    if ($len <= $width) return $text;
    $out = '';
    for ($i = 0; $i < $len; $i += $width) {
        $out .= mb_substr($text, $i, $width);
        if ($i + $width < $len) $out .= $break;
    }
    return $out;
}

// ===================== 入口 =====================
$book = new DeadlockBook();
$arg = $argv[1] ?? null;
if ($arg === null)            $book->renderAll();
elseif (ctype_digit($arg))    $book->renderOne((int) $arg);
else                          $book->search($arg);