CS_learn/rust-based-os-comp2022
1
0
Fork 0
mirror of https://github.com/LearningOS/rust-based-os-comp2022.git synced 2026-02-07 20:34:08 +08:00
Code Issues Packages Projects Releases Wiki Activity
Files
gh-pages
rust-based-os-comp2022/chapter8/3semaphore.html
chyyuu 0e2365f9e9 deploy: 275767122c
2022-06-30 04:46:48 +00:00

643 lines
62 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>
<html class="no-js" lang="zh_CN">
<head><meta charset="utf-8"/>
<meta name="viewport" content="width=device-width,initial-scale=1"/>
<meta name="color-scheme" content="light dark"><link rel="index" title="索引" href="../genindex.html" /><link rel="search" title="搜索" href="../search.html" /><link rel="next" title="条件变量机制" href="4condition-variable.html" /><link rel="prev" title="锁机制" href="2lock.html" />
<meta name="generator" content="sphinx-4.1.2, furo 2021.08.31"/>
<title>信号量机制 - Open-Source-OS-Training-Camp-2022 文档</title>
<link rel="stylesheet" type="text/css" href="../_static/pygments.css" />
<link rel="stylesheet" type="text/css" href="../_static/styles/furo.css?digest=c7c65a82b42f6b978e58466c1e9ef2509836d916" />
<link rel="stylesheet" type="text/css" href="../_static/tabs.css" />
<link rel="stylesheet" type="text/css" href="../_static/styles/furo-extensions.css?digest=16fb25fabf47304eee183a5e9af80b1ba98259b1" />
<link rel="stylesheet" type="text/css" href="../_static/my_style.css" />
<style>
body {
--color-code-background: #f8f8f8;
--color-code-foreground: black;
}
body[data-theme="dark"] {
--color-code-background: #202020;
--color-code-foreground: #d0d0d0;
}
@media (prefers-color-scheme: dark) {
body:not([data-theme="light"]) {
--color-code-background: #202020;
--color-code-foreground: #d0d0d0;
}
}
</style></head>
<body>
<script>
document.body.dataset.theme = localStorage.getItem("theme") || "auto";
</script>
<svg xmlns="http://www.w3.org/2000/svg" style="display: none;">
<symbol id="svg-toc" viewBox="0 0 24 24">
<title>Contents</title>
<svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor"
stroke-width="1.5" stroke-linecap="round" stroke-linejoin="round">
<path stroke="none" d="M0 0h24v24H0z" />
<line x1="4" y1="6" x2="20" y2="6" />
<line x1="10" y1="12" x2="20" y2="12" />
<line x1="6" y1="18" x2="20" y2="18" />
</svg>
</symbol>
<symbol id="svg-menu" viewBox="0 0 24 24">
<title>Menu</title>
<svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor"
stroke-width="2" stroke-linecap="round" stroke-linejoin="round" class="feather-menu">
<line x1="3" y1="12" x2="21" y2="12"></line>
<line x1="3" y1="6" x2="21" y2="6"></line>
<line x1="3" y1="18" x2="21" y2="18"></line>
</svg>
</symbol>
<symbol id="svg-arrow-right" viewBox="0 0 24 24">
<title>Expand</title>
<svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor"
stroke-width="2" stroke-linecap="round" stroke-linejoin="round" class="feather-chevron-right">
<polyline points="9 18 15 12 9 6"></polyline>
</svg>
</symbol>
<symbol id="svg-sun" viewBox="0 0 24 24">
<title>Light mode</title>
<svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor"
stroke-width="1.5" stroke-linecap="round" stroke-linejoin="round" class="feather-sun">
<circle cx="12" cy="12" r="5"></circle>
<line x1="12" y1="1" x2="12" y2="3"></line>
<line x1="12" y1="21" x2="12" y2="23"></line>
<line x1="4.22" y1="4.22" x2="5.64" y2="5.64"></line>
<line x1="18.36" y1="18.36" x2="19.78" y2="19.78"></line>
<line x1="1" y1="12" x2="3" y2="12"></line>
<line x1="21" y1="12" x2="23" y2="12"></line>
<line x1="4.22" y1="19.78" x2="5.64" y2="18.36"></line>
<line x1="18.36" y1="5.64" x2="19.78" y2="4.22"></line>
</svg>
</symbol>
<symbol id="svg-moon" viewBox="0 0 24 24">
<title>Dark mode</title>
<svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor"
stroke-width="1.5" stroke-linecap="round" stroke-linejoin="round" class="icon-tabler-moon">
<path stroke="none" d="M0 0h24v24H0z" fill="none" />
<path d="M12 3c.132 0 .263 0 .393 0a7.5 7.5 0 0 0 7.92 12.446a9 9 0 1 1 -8.313 -12.454z" />
</svg>
</symbol>
<symbol id="svg-sun-half" viewBox="0 0 24 24">
<title>Auto light/dark mode</title>
<svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor"
stroke-width="1.5" stroke-linecap="round" stroke-linejoin="round" class="icon-tabler-shadow">
<path stroke="none" d="M0 0h24v24H0z" fill="none"/>
<circle cx="12" cy="12" r="9" />
<path d="M13 12h5" />
<path d="M13 15h4" />
<path d="M13 18h1" />
<path d="M13 9h4" />
<path d="M13 6h1" />
</svg>
</symbol>
</svg>
<input type="checkbox" class="sidebar-toggle" name="__navigation" id="__navigation">
<input type="checkbox" class="sidebar-toggle" name="__toc" id="__toc">
<label class="overlay sidebar-overlay" for="__navigation">
<div class="visually-hidden">Hide navigation sidebar</div>
</label>
<label class="overlay toc-overlay" for="__toc">
<div class="visually-hidden">Hide table of contents sidebar</div>
</label>
<div class="page">
<header class="mobile-header">
<div class="header-left">
<label class="nav-overlay-icon" for="__navigation">
<div class="visually-hidden">Toggle site navigation sidebar</div>
<i class="icon"><svg><use href="#svg-menu"></use></svg></i>
</label>
</div>
<div class="header-center">
<a href="../index.html"><div class="brand">Open-Source-OS-Training-Camp-2022 文档</div></a>
</div>
<div class="header-right">
<div class="theme-toggle-container theme-toggle-header">
<button class="theme-toggle">
<div class="visually-hidden">Toggle Light / Dark / Auto color theme</div>
<svg class="theme-icon-when-auto"><use href="#svg-sun-half"></use></svg>
<svg class="theme-icon-when-dark"><use href="#svg-moon"></use></svg>
<svg class="theme-icon-when-light"><use href="#svg-sun"></use></svg>
</button>
</div>
<label class="toc-overlay-icon toc-header-icon" for="__toc">
<div class="visually-hidden">Toggle table of contents sidebar</div>
<i class="icon"><svg><use href="#svg-toc"></use></svg></i>
</label>
</div>
</header>
<aside class="sidebar-drawer">
<div class="sidebar-container">
<div class="sidebar-sticky"><a class="sidebar-brand" href="../index.html">
<span class="sidebar-brand-text">Open-Source-OS-Training-Camp-2022 文档</span>
</a><form class="sidebar-search-container" method="get" action="../search.html" role="search">
<input class="sidebar-search" placeholder=搜索 name="q" aria-label="搜索">
<input type="hidden" name="check_keywords" value="yes">
<input type="hidden" name="area" value="default">
</form>
<div id="searchbox"></div><div class="sidebar-scroll"><div class="sidebar-tree">
<p class="caption" role="heading"><span class="caption-text">正文</span></p>
<ul class="current">
<li class="toctree-l1 has-children"><a class="reference internal" href="../0setup-devel-env.html">第零章：实验环境配置</a><input class="toctree-checkbox" id="toctree-checkbox-1" name="toctree-checkbox-1" role="switch" type="checkbox"/><label for="toctree-checkbox-1"><div class="visually-hidden">Toggle child pages in navigation</div><i class="icon"><svg><use href="#svg-arrow-right"></use></svg></i></label><ul class="simple">
</ul>
</li>
<li class="toctree-l1 has-children"><a class="reference internal" href="../chapter1/index.html">第一章：应用程序与基本执行环境</a><input class="toctree-checkbox" id="toctree-checkbox-2" name="toctree-checkbox-2" role="switch" type="checkbox"/><label for="toctree-checkbox-2"><div class="visually-hidden">Toggle child pages in navigation</div><i class="icon"><svg><use href="#svg-arrow-right"></use></svg></i></label><ul>
<li class="toctree-l2"><a class="reference internal" href="../chapter1/0intro.html">引言</a></li>
<li class="toctree-l2 has-children"><a class="reference internal" href="../chapter1/1app-ee-platform.html">应用程序执行环境与平台支持</a><input class="toctree-checkbox" id="toctree-checkbox-3" name="toctree-checkbox-3" role="switch" type="checkbox"/><label for="toctree-checkbox-3"><div class="visually-hidden">Toggle child pages in navigation</div><i class="icon"><svg><use href="#svg-arrow-right"></use></svg></i></label><ul class="simple">
</ul>
</li>
<li class="toctree-l2 has-children"><a class="reference internal" href="../chapter1/2remove-std.html">移除标准库依赖</a><input class="toctree-checkbox" id="toctree-checkbox-4" name="toctree-checkbox-4" role="switch" type="checkbox"/><label for="toctree-checkbox-4"><div class="visually-hidden">Toggle child pages in navigation</div><i class="icon"><svg><use href="#svg-arrow-right"></use></svg></i></label><ul class="simple">
</ul>
</li>
<li class="toctree-l2 has-children"><a class="reference internal" href="../chapter1/3mini-rt-usrland.html">构建用户态执行环境</a><input class="toctree-checkbox" id="toctree-checkbox-5" name="toctree-checkbox-5" role="switch" type="checkbox"/><label for="toctree-checkbox-5"><div class="visually-hidden">Toggle child pages in navigation</div><i class="icon"><svg><use href="#svg-arrow-right"></use></svg></i></label><ul class="simple">
</ul>
</li>
<li class="toctree-l2 has-children"><a class="reference internal" href="../chapter1/4mini-rt-baremetal.html">构建裸机执行环境</a><input class="toctree-checkbox" id="toctree-checkbox-6" name="toctree-checkbox-6" role="switch" type="checkbox"/><label for="toctree-checkbox-6"><div class="visually-hidden">Toggle child pages in navigation</div><i class="icon"><svg><use href="#svg-arrow-right"></use></svg></i></label><ul class="simple">
</ul>
</li>
</ul>
</li>
<li class="toctree-l1 has-children"><a class="reference internal" href="../chapter2/index.html">第二章：批处理系统</a><input class="toctree-checkbox" id="toctree-checkbox-7" name="toctree-checkbox-7" role="switch" type="checkbox"/><label for="toctree-checkbox-7"><div class="visually-hidden">Toggle child pages in navigation</div><i class="icon"><svg><use href="#svg-arrow-right"></use></svg></i></label><ul>
<li class="toctree-l2"><a class="reference internal" href="../chapter2/0intro.html">引言</a></li>
<li class="toctree-l2 has-children"><a class="reference internal" href="../chapter2/2application.html">实现应用程序</a><input class="toctree-checkbox" id="toctree-checkbox-8" name="toctree-checkbox-8" role="switch" type="checkbox"/><label for="toctree-checkbox-8"><div class="visually-hidden">Toggle child pages in navigation</div><i class="icon"><svg><use href="#svg-arrow-right"></use></svg></i></label><ul class="simple">
</ul>
</li>
<li class="toctree-l2 has-children"><a class="reference internal" href="../chapter2/3batch-system.html">实现批处理操作系统</a><input class="toctree-checkbox" id="toctree-checkbox-9" name="toctree-checkbox-9" role="switch" type="checkbox"/><label for="toctree-checkbox-9"><div class="visually-hidden">Toggle child pages in navigation</div><i class="icon"><svg><use href="#svg-arrow-right"></use></svg></i></label><ul class="simple">
</ul>
</li>
<li class="toctree-l2 has-children"><a class="reference internal" href="../chapter2/4trap-handling.html">实现特权级的切换</a><input class="toctree-checkbox" id="toctree-checkbox-10" name="toctree-checkbox-10" role="switch" type="checkbox"/><label for="toctree-checkbox-10"><div class="visually-hidden">Toggle child pages in navigation</div><i class="icon"><svg><use href="#svg-arrow-right"></use></svg></i></label><ul class="simple">
</ul>
</li>
</ul>
</li>
<li class="toctree-l1 has-children"><a class="reference internal" href="../chapter3/index.html">第三章：多道程序与分时多任务</a><input class="toctree-checkbox" id="toctree-checkbox-11" name="toctree-checkbox-11" role="switch" type="checkbox"/><label for="toctree-checkbox-11"><div class="visually-hidden">Toggle child pages in navigation</div><i class="icon"><svg><use href="#svg-arrow-right"></use></svg></i></label><ul>
<li class="toctree-l2"><a class="reference internal" href="../chapter3/0intro.html">引言</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter3/1multi-loader.html">多道程序放置与加载</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter3/2task-switching.html">任务切换</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter3/3multiprogramming.html">管理多道程序</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter3/4time-sharing-system.html">分时多任务系统</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter3/5exercise.html">chapter3练习</a></li>
</ul>
</li>
<li class="toctree-l1 has-children"><a class="reference internal" href="../chapter4/index.html">第四章：地址空间</a><input class="toctree-checkbox" id="toctree-checkbox-12" name="toctree-checkbox-12" role="switch" type="checkbox"/><label for="toctree-checkbox-12"><div class="visually-hidden">Toggle child pages in navigation</div><i class="icon"><svg><use href="#svg-arrow-right"></use></svg></i></label><ul>
<li class="toctree-l2"><a class="reference internal" href="../chapter4/0intro.html">引言</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter4/3sv39-implementation-1.html">实现 SV39 多级页表机制（上）</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter4/4sv39-implementation-2.html">实现 SV39 多级页表机制（下）</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter4/5kernel-app-spaces.html">内核与应用的地址空间</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter4/6multitasking-based-on-as.html">基于地址空间的分时多任务</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter4/7exercise.html">chapter4练习</a></li>
</ul>
</li>
<li class="toctree-l1 has-children"><a class="reference internal" href="../chapter5/index.html">第五章：进程及进程管理</a><input class="toctree-checkbox" id="toctree-checkbox-13" name="toctree-checkbox-13" role="switch" type="checkbox"/><label for="toctree-checkbox-13"><div class="visually-hidden">Toggle child pages in navigation</div><i class="icon"><svg><use href="#svg-arrow-right"></use></svg></i></label><ul>
<li class="toctree-l2"><a class="reference internal" href="../chapter5/0intro.html">引言</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter5/1process.html">与进程有关的重要系统调用</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter5/2core-data-structures.html">进程管理的核心数据结构</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter5/3implement-process-mechanism.html">进程管理机制的设计实现</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter5/4exercise.html">chapter5练习</a></li>
</ul>
</li>
<li class="toctree-l1 has-children"><a class="reference internal" href="../chapter6/index.html">第六章：文件系统与I/O重定向</a><input class="toctree-checkbox" id="toctree-checkbox-14" name="toctree-checkbox-14" role="switch" type="checkbox"/><label for="toctree-checkbox-14"><div class="visually-hidden">Toggle child pages in navigation</div><i class="icon"><svg><use href="#svg-arrow-right"></use></svg></i></label><ul>
<li class="toctree-l2"><a class="reference internal" href="../chapter6/0intro.html">引言</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter6/1file-descriptor.html">文件与文件描述符</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter6/1fs-interface.html">文件系统接口</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter6/2fs-implementation-1.html">简易文件系统 easy-fs (上)</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter6/2fs-implementation-2.html">简易文件系统 easy-fs (下)</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter6/3using-easy-fs-in-kernel.html">在内核中使用 easy-fs</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter6/4exercise.html">chapter6练习</a></li>
</ul>
</li>
<li class="toctree-l1 has-children"><a class="reference internal" href="../chapter7/index.html">第七章：进程间通信</a><input class="toctree-checkbox" id="toctree-checkbox-15" name="toctree-checkbox-15" role="switch" type="checkbox"/><label for="toctree-checkbox-15"><div class="visually-hidden">Toggle child pages in navigation</div><i class="icon"><svg><use href="#svg-arrow-right"></use></svg></i></label><ul>
<li class="toctree-l2"><a class="reference internal" href="../chapter7/0intro.html">引言</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter7/1pipe.html">管道</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter7/2cmdargs-and-redirection.html">命令行参数与标准 I/O 重定向</a></li>
<li class="toctree-l2"><a class="reference internal" href="../chapter7/3exercise.html">chapter7练习</a></li>
</ul>
</li>
<li class="toctree-l1 current has-children"><a class="reference internal" href="index.html">第八章：并发</a><input checked="" class="toctree-checkbox" id="toctree-checkbox-16" name="toctree-checkbox-16" role="switch" type="checkbox"/><label for="toctree-checkbox-16"><div class="visually-hidden">Toggle child pages in navigation</div><i class="icon"><svg><use href="#svg-arrow-right"></use></svg></i></label><ul class="current">
<li class="toctree-l2"><a class="reference internal" href="0intro.html">引言</a></li>
<li class="toctree-l2"><a class="reference internal" href="1thread-kernel.html">内核态的线程管理</a></li>
<li class="toctree-l2"><a class="reference internal" href="2lock.html">锁机制</a></li>
<li class="toctree-l2 current current-page"><a class="current reference internal" href="#">信号量机制</a></li>
<li class="toctree-l2"><a class="reference internal" href="4condition-variable.html">条件变量机制</a></li>
<li class="toctree-l2"><a class="reference internal" href="5exercise.html">chapter8 练习</a></li>
</ul>
</li>
</ul>
<p class="caption" role="heading"><span class="caption-text">附录</span></p>
<ul>
<li class="toctree-l1 has-children"><a class="reference internal" href="../appendix-a/index.html">附录 A：Rust 系统编程资料</a><input class="toctree-checkbox" id="toctree-checkbox-17" name="toctree-checkbox-17" role="switch" type="checkbox"/><label for="toctree-checkbox-17"><div class="visually-hidden">Toggle child pages in navigation</div><i class="icon"><svg><use href="#svg-arrow-right"></use></svg></i></label><ul class="simple">
</ul>
</li>
<li class="toctree-l1 has-children"><a class="reference internal" href="../appendix-b/index.html">附录 B：常见工具的使用方法</a><input class="toctree-checkbox" id="toctree-checkbox-18" name="toctree-checkbox-18" role="switch" type="checkbox"/><label for="toctree-checkbox-18"><div class="visually-hidden">Toggle child pages in navigation</div><i class="icon"><svg><use href="#svg-arrow-right"></use></svg></i></label><ul class="simple">
</ul>
</li>
<li class="toctree-l1 has-children"><a class="reference internal" href="../appendix-c/index.html">附录 C：深入机器模式：RustSBI</a><input class="toctree-checkbox" id="toctree-checkbox-19" name="toctree-checkbox-19" role="switch" type="checkbox"/><label for="toctree-checkbox-19"><div class="visually-hidden">Toggle child pages in navigation</div><i class="icon"><svg><use href="#svg-arrow-right"></use></svg></i></label><ul class="simple">
</ul>
</li>
<li class="toctree-l1"><a class="reference internal" href="../appendix-d/index.html">附录 D：RISC-V相关信息</a></li>
</ul>
<p class="caption" role="heading"><span class="caption-text">开发注记</span></p>
<ul>
<li class="toctree-l1 has-children"><a class="reference internal" href="../setup-sphinx.html">修改和构建本项目</a><input class="toctree-checkbox" id="toctree-checkbox-20" name="toctree-checkbox-20" role="switch" type="checkbox"/><label for="toctree-checkbox-20"><div class="visually-hidden">Toggle child pages in navigation</div><i class="icon"><svg><use href="#svg-arrow-right"></use></svg></i></label><ul class="simple">
</ul>
</li>
<li class="toctree-l1 has-children"><a class="reference internal" href="../rest-example.html">reStructuredText 基本语法</a><input class="toctree-checkbox" id="toctree-checkbox-21" name="toctree-checkbox-21" role="switch" type="checkbox"/><label for="toctree-checkbox-21"><div class="visually-hidden">Toggle child pages in navigation</div><i class="icon"><svg><use href="#svg-arrow-right"></use></svg></i></label><ul class="simple">
</ul>
</li>
</ul>
</div>
</div>
</div>
</div>
</aside>
<div class="main">
<div class="content">
<article role="main">
<div class="content-icon-container">
<div class="theme-toggle-container theme-toggle-content">
<button class="theme-toggle">
<div class="visually-hidden">Toggle Light / Dark / Auto color theme</div>
<svg class="theme-icon-when-auto"><use href="#svg-sun-half"></use></svg>
<svg class="theme-icon-when-dark"><use href="#svg-moon"></use></svg>
<svg class="theme-icon-when-light"><use href="#svg-sun"></use></svg>
</button>
</div>
<label class="toc-overlay-icon toc-content-icon" for="__toc">
<div class="visually-hidden">Toggle table of contents sidebar</div>
<i class="icon"><svg><use href="#svg-toc"></use></svg></i>
</label>
</div>
<div class="section" id="id1">
<h1>信号量机制<a class="headerlink" href="#id1" title="永久链接至标题"></a></h1>
<div class="section" id="id2">
<h2>本节导读<a class="headerlink" href="#id2" title="永久链接至标题"></a></h2>
<p>在上一节中，我们介绍了互斥锁（mutex 或 lock）的起因、使用和实现过程。通过互斥锁，
可以让线程在临界区执行时，独占临界资源。当我们需要更灵活的互斥访问或同步操作方式，如提供了最多只允许
N 个线程访问临界资源的情况，让某个线程等待另外一个线程执行完毕后再继续执行的同步过程等，
互斥锁这种方式就有点力不从心了。</p>
<p>在本节中，将介绍功能更加强大和灵活的同步互斥机制 – 信号量（Semaphore），它的设计思路、
使用和在操作系统中的具体实现。可以看到，信号量的实现需要互斥锁和处理器原子指令的支持，
它是一种更高级的同步互斥机制。</p>
</div>
<div class="section" id="id3">
<h2>信号量的起源和基本思路<a class="headerlink" href="#id3" title="永久链接至标题"></a></h2>
<p>1963 年前后，当时的数学家（其实是计算机科学家）Edsger Dijkstra 和他的团队在为 Electrologica X8
计算机开发一个操作系统（称为 THE multiprogramming system，THE 多道程序系统）的过程中，提出了信号量
（Semphore）是一种变量或抽象数据类型，用于控制多个线程对共同资源的访问。</p>
<p>信号量是对互斥锁的一种巧妙的扩展。上一节中的互斥锁的初始值一般设置为 1 的整型变量，
表示临界区还没有被某个线程占用。互斥锁用 0 表示临界区已经被占用了，用 1 表示临界区为空，再通过
<code class="docutils literal notranslate"><span class="pre">lock/unlock</span></code> 操作来协调多个线程轮流独占临界区执行。而信号量的初始值可设置为 N 的整数变量, 如果 N
大于 0， 表示最多可以有 N 个线程进入临界区执行，如果 N 小于等于 0 ，表示不能有线程进入临界区了，
必须在后续操作中让信号量的值加 1 ，才能唤醒某个等待的线程。</p>
<p>Dijkstra 对信号量设计了两种操作：P（Proberen（荷兰语），尝试）操作和 V（Verhogen（荷兰语），增加）操作。
P 操作是检查信号量的值是否大于 0，若该值大于 0，则将其值减 1 并继续（表示可以进入临界区了）；若该值为
0，则线程将睡眠。注意，此时 P 操作还未结束。而且由于信号量本身是一种临界资源（可回想一下上一节的锁，
其实也是一种临界资源），所以在 P 操作中，检查/修改信号量值以及可能发生的睡眠这一系列操作，
是一个不可分割的原子操作过程。通过原子操作才能保证，一旦 P 操作开始，则在该操作完成或阻塞睡眠之前，
其他线程均不允许访问该信号量。</p>
<p>V 操作会对信号量的值加 1 ，然后检查是否有一个或多个线程在该信号量上睡眠等待。如有，
则选择其中的一个线程唤醒并允许该线程继续完成它的 P 操作；如没有，则直接返回。注意，信号量的值加 1，
并可能唤醒一个线程的一系列操作同样也是不可分割的原子操作过程。不会有某个进程因执行 V 操作而阻塞。</p>
<p>如果信号量是一个任意的整数，通常被称为计数信号量（Counting Semaphore），或一般信号量（General
Semaphore）；如果信号量只有0或1的取值，则称为二值信号量（Binary Semaphore）。可以看出，
互斥锁是信号量的一种特例 — 二值信号量，信号量很好地解决了最多允许 N 个线程访问临界资源的情况。</p>
<p>信号量的一种实现伪代码如下所示：</p>
<div class="highlight-rust notranslate"><div class="highlight"><pre><span></span><span class="linenos"> 1</span><span class="k">fn</span> <span class="nf">P</span><span class="p">(</span><span class="n">S</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="linenos"> 2</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">S</span><span class="w"> </span><span class="o">&gt;=</span><span class="w"> </span><span class="mi">1</span><span class="w"></span>
<span class="linenos"> 3</span><span class="w"> </span><span class="n">S</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">S</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span><span class="w"></span>
<span class="linenos"> 4</span><span class="w"> </span><span class="k">else</span><span class="w"></span>
<span class="linenos"> 5</span><span class="w"> </span><span class="o">&lt;</span><span class="n">block</span><span class="w"> </span><span class="n">and</span><span class="w"> </span><span class="n">enqueue</span><span class="w"> </span><span class="n">the</span><span class="w"> </span><span class="n">thread</span><span class="o">&gt;</span><span class="p">;</span><span class="w"></span>
<span class="linenos"> 6</span><span class="p">}</span><span class="w"></span>
<span class="linenos"> 7</span><span class="k">fn</span> <span class="nf">V</span><span class="p">(</span><span class="n">S</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="linenos"> 8</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="o">&lt;</span><span class="n">some</span><span class="w"> </span><span class="n">threads</span><span class="w"> </span><span class="n">are</span><span class="w"> </span><span class="n">blocked</span><span class="w"> </span><span class="n">on</span><span class="w"> </span><span class="n">the</span><span class="w"> </span><span class="n">queue</span><span class="o">&gt;</span><span class="w"></span>
<span class="linenos"> 9</span><span class="w"> </span><span class="o">&lt;</span><span class="n">unblock</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">thread</span><span class="o">&gt;</span><span class="p">;</span><span class="w"></span>
<span class="linenos">10</span><span class="w"> </span><span class="k">else</span><span class="w"></span>
<span class="linenos">11</span><span class="w"> </span><span class="n">S</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">S</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span><span class="w"></span>
<span class="linenos">12</span><span class="p">}</span><span class="w"></span>
</pre></div>
</div>
<p>在上述实现中，S 的取值范围为大于等于 0 的整数。S 的初值一般设置为一个大于 0 的正整数，
表示可以进入临界区的线程数。当 S 取值为 1，表示是二值信号量，也就是互斥锁了。
使用信号量实现线程互斥访问临界区的伪代码如下：</p>
<div class="highlight-rust notranslate"><div class="highlight"><pre><span></span><span class="linenos"> 1</span><span class="kd">let</span><span class="w"> </span><span class="k">static</span><span class="w"> </span><span class="k">mut</span><span class="w"> </span><span class="n">S</span>: <span class="nc">semaphore</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span><span class="w"></span>
<span class="linenos"> 2</span>
<span class="linenos"> 3</span><span class="c1">// Thread i</span>
<span class="linenos"> 4</span><span class="k">fn</span> <span class="nf">foo</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="linenos"> 5</span><span class="w"> </span><span class="o">..</span><span class="p">.</span><span class="w"></span>
<span class="linenos"> 6</span><span class="w"> </span><span class="n">P</span><span class="p">(</span><span class="n">S</span><span class="p">);</span><span class="w"></span>
<span class="linenos"> 7</span><span class="w"> </span><span class="n">execute</span><span class="w"> </span><span class="n">Cricital</span><span class="w"> </span><span class="n">Section</span><span class="p">;</span><span class="w"></span>
<span class="linenos"> 8</span><span class="w"> </span><span class="n">V</span><span class="p">(</span><span class="n">S</span><span class="p">);</span><span class="w"></span>
<span class="linenos"> 9</span><span class="w"> </span><span class="o">..</span><span class="p">.</span><span class="w"></span>
<span class="linenos">10</span><span class="p">}</span><span class="w"></span>
</pre></div>
</div>
<p>下面是另外一种信号量实现的伪代码：</p>
<div class="highlight-rust notranslate"><div class="highlight"><pre><span></span><span class="linenos"> 1</span><span class="k">fn</span> <span class="nf">P</span><span class="p">(</span><span class="n">S</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="linenos"> 2</span><span class="w"> </span><span class="n">S</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">S</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span><span class="w"></span>
<span class="linenos"> 3</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">S</span><span class="w"> </span><span class="o">&lt;</span><span class="w"> </span><span class="mi">0</span><span class="w"> </span><span class="n">then</span><span class="w"></span>
<span class="linenos"> 4</span><span class="w"> </span><span class="o">&lt;</span><span class="n">block</span><span class="w"> </span><span class="n">and</span><span class="w"> </span><span class="n">enqueue</span><span class="w"> </span><span class="n">the</span><span class="w"> </span><span class="n">thread</span><span class="o">&gt;</span><span class="p">;</span><span class="w"></span>
<span class="linenos"> 5</span><span class="p">}</span><span class="w"></span>
<span class="linenos"> 6</span>
<span class="linenos"> 7</span><span class="k">fn</span> <span class="nf">V</span><span class="p">(</span><span class="n">S</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="linenos"> 8</span><span class="w"> </span><span class="n">S</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">S</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span><span class="w"></span>
<span class="linenos"> 9</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="o">&lt;</span><span class="n">some</span><span class="w"> </span><span class="n">threads</span><span class="w"> </span><span class="n">are</span><span class="w"> </span><span class="n">blocked</span><span class="w"> </span><span class="n">on</span><span class="w"> </span><span class="n">the</span><span class="w"> </span><span class="n">queue</span><span class="o">&gt;</span><span class="w"></span>
<span class="linenos">10</span><span class="w"> </span><span class="o">&lt;</span><span class="n">unblock</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">thread</span><span class="o">&gt;</span><span class="p">;</span><span class="w"></span>
<span class="linenos">11</span><span class="p">}</span><span class="w"></span>
</pre></div>
</div>
<p>在这种实现中，S 的初值一般设置为一个大于 0 的正整数，表示可以进入临界区的线程数。但 S
的取值范围可以是小于 0 的整数，表示等待进入临界区的睡眠线程数。</p>
<p>信号量的另一种用途是用于实现同步（synchronization）。比如，把信号量的初始值设置为 0 ，
当一个线程 A 对此信号量执行一个 P 操作，那么该线程立即会被阻塞睡眠。之后有另外一个线程 B
对此信号量执行一个 V 操作，就会将线程 A 唤醒。这样线程 B 中执行 V 操作之前的代码序列 B-stmts
和线程 A 中执行 P 操作之后的代码 A-stmts 序列之间就形成了一种确定的同步执行关系，即线程 B 的
B-stmts 会先执行，然后才是线程 A 的 A-stmts 开始执行。相关伪代码如下所示：</p>
<div class="highlight-rust notranslate"><div class="highlight"><pre><span></span><span class="linenos"> 1</span><span class="kd">let</span><span class="w"> </span><span class="k">static</span><span class="w"> </span><span class="k">mut</span><span class="w"> </span><span class="n">S</span>: <span class="nc">semaphore</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">0</span><span class="p">;</span><span class="w"></span>
<span class="linenos"> 2</span>
<span class="linenos"> 3</span><span class="c1">//Thread A</span>
<span class="linenos"> 4</span><span class="o">..</span><span class="p">.</span><span class="w"></span>
<span class="linenos"> 5</span><span class="n">P</span><span class="p">(</span><span class="n">S</span><span class="p">);</span><span class="w"></span>
<span class="linenos"> 6</span><span class="n">Label_2</span>:
<span class="linenos"> 7</span><span class="nc">A</span><span class="o">-</span><span class="n">stmts</span><span class="w"> </span><span class="n">after</span><span class="w"> </span><span class="n">Thread</span><span class="w"> </span><span class="n">B</span>::<span class="n">Label_1</span><span class="p">;</span><span class="w"></span>
<span class="linenos"> 8</span><span class="o">..</span><span class="p">.</span><span class="w"></span>
<span class="linenos"> 9</span>
<span class="linenos">10</span><span class="c1">//Thread B</span>
<span class="linenos">11</span><span class="o">..</span><span class="p">.</span><span class="w"></span>
<span class="linenos">12</span><span class="n">B</span><span class="o">-</span><span class="n">stmts</span><span class="w"> </span><span class="n">before</span><span class="w"> </span><span class="n">Thread</span><span class="w"> </span><span class="n">A</span>::<span class="n">Label_2</span><span class="p">;</span><span class="w"></span>
<span class="linenos">13</span><span class="n">Label_1</span>:
<span class="linenos">14</span><span class="nc">V</span><span class="p">(</span><span class="n">S</span><span class="p">);</span><span class="w"></span>
<span class="linenos">15</span><span class="o">..</span><span class="p">.</span><span class="w"></span>
</pre></div>
</div>
</div>
<div class="section" id="id4">
<h2>实现信号量<a class="headerlink" href="#id4" title="永久链接至标题"></a></h2>
<div class="section" id="semaphore">
<h3>使用 semaphore 系统调用<a class="headerlink" href="#semaphore" title="永久链接至标题"></a></h3>
<p>我们通过例子来看看如何实际使用信号量。下面是面向应用程序对信号量系统调用的简单使用，
可以看到对它的使用与上一节介绍的互斥锁系统调用类似。</p>
<p>在这个例子中，主线程先创建了信号量初值为 0 的信号量 <code class="docutils literal notranslate"><span class="pre">SEM_SYNC</span></code> ，然后再创建两个线程 First
和 Second 。线程 First 会先睡眠 10ms，而当线程 Second 执行时，会由于执行信号量的 P
操作而等待睡眠；当线程 First 醒来后，会执行 V 操作，从而能够唤醒线程 Second。这样线程 First
和线程 Second 就形成了一种稳定的同步关系。</p>
<div class="highlight-rust notranslate"><div class="highlight"><pre><span></span><span class="linenos"> 1</span><span class="k">const</span><span class="w"> </span><span class="n">SEM_SYNC</span>: <span class="kt">usize</span> <span class="o">=</span><span class="w"> </span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="c1">//信号量ID</span>
<span class="linenos"> 2</span><span class="k">unsafe</span><span class="w"> </span><span class="k">fn</span> <span class="nf">first</span><span class="p">()</span><span class="w"> </span>-&gt; <span class="o">!</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="linenos"> 3</span><span class="w"> </span><span class="n">sleep</span><span class="p">(</span><span class="mi">10</span><span class="p">);</span><span class="w"></span>
<span class="linenos"> 4</span><span class="w"> </span><span class="fm">println!</span><span class="p">(</span><span class="s">"First work and wakeup Second"</span><span class="p">);</span><span class="w"></span>
<span class="hll"><span class="linenos"> 5</span><span class="w"> </span><span class="n">semaphore_up</span><span class="p">(</span><span class="n">SEM_SYNC</span><span class="p">);</span><span class="w"> </span><span class="c1">//信号量V操作</span>
</span><span class="linenos"> 6</span><span class="w"> </span><span class="n">exit</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span><span class="w"></span>
<span class="linenos"> 7</span><span class="p">}</span><span class="w"></span>
<span class="linenos"> 8</span><span class="k">unsafe</span><span class="w"> </span><span class="k">fn</span> <span class="nf">second</span><span class="p">()</span><span class="w"> </span>-&gt; <span class="o">!</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="linenos"> 9</span><span class="w"> </span><span class="fm">println!</span><span class="p">(</span><span class="s">"Second want to continue,but need to wait first"</span><span class="p">);</span><span class="w"></span>
<span class="hll"><span class="linenos">10</span><span class="w"> </span><span class="n">semaphore_down</span><span class="p">(</span><span class="n">SEM_SYNC</span><span class="p">);</span><span class="w"> </span><span class="c1">//信号量P操作</span>
</span><span class="linenos">11</span><span class="w"> </span><span class="fm">println!</span><span class="p">(</span><span class="s">"Second can work now"</span><span class="p">);</span><span class="w"></span>
<span class="linenos">12</span><span class="w"> </span><span class="n">exit</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span><span class="w"></span>
<span class="linenos">13</span><span class="p">}</span><span class="w"></span>
<span class="linenos">14</span><span class="k">pub</span><span class="w"> </span><span class="k">fn</span> <span class="nf">main</span><span class="p">()</span><span class="w"> </span>-&gt; <span class="kt">i32</span> <span class="p">{</span><span class="w"></span>
<span class="linenos">15</span><span class="w"> </span><span class="c1">// create semaphores</span>
<span class="hll"><span class="linenos">16</span><span class="w"> </span><span class="fm">assert_eq!</span><span class="p">(</span><span class="n">semaphore_create</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span><span class="w"> </span><span class="k">as</span><span class="w"> </span><span class="kt">usize</span><span class="p">,</span><span class="w"> </span><span class="n">SEM_SYNC</span><span class="p">);</span><span class="w"> </span><span class="c1">// 信号量初值为0</span>
</span><span class="linenos">17</span><span class="w"> </span><span class="c1">// create first, second threads</span>
<span class="linenos">18</span><span class="w"> </span><span class="o">..</span><span class="p">.</span><span class="w"></span>
<span class="linenos">19</span><span class="p">}</span><span class="w"></span>
<span class="linenos">20</span>
<span class="linenos">21</span><span class="k">pub</span><span class="w"> </span><span class="k">fn</span> <span class="nf">sys_semaphore_create</span><span class="p">(</span><span class="n">res_count</span>: <span class="kt">usize</span><span class="p">)</span><span class="w"> </span>-&gt; <span class="kt">isize</span> <span class="p">{</span><span class="w"></span>
<span class="hll"><span class="linenos">22</span><span class="w"> </span><span class="n">syscall</span><span class="p">(</span><span class="n">SYSCALL_SEMAPHORE_CREATE</span><span class="p">,</span><span class="w"> </span><span class="p">[</span><span class="n">res_count</span><span class="p">,</span><span class="w"> </span><span class="mi">0</span><span class="p">,</span><span class="w"> </span><span class="mi">0</span><span class="p">])</span><span class="w"></span>
</span><span class="linenos">23</span><span class="p">}</span><span class="w"></span>
<span class="linenos">24</span><span class="k">pub</span><span class="w"> </span><span class="k">fn</span> <span class="nf">sys_semaphore_up</span><span class="p">(</span><span class="n">sem_id</span>: <span class="kt">usize</span><span class="p">)</span><span class="w"> </span>-&gt; <span class="kt">isize</span> <span class="p">{</span><span class="w"></span>
<span class="hll"><span class="linenos">25</span><span class="w"> </span><span class="n">syscall</span><span class="p">(</span><span class="n">SYSCALL_SEMAPHORE_UP</span><span class="p">,</span><span class="w"> </span><span class="p">[</span><span class="n">sem_id</span><span class="p">,</span><span class="w"> </span><span class="mi">0</span><span class="p">,</span><span class="w"> </span><span class="mi">0</span><span class="p">])</span><span class="w"></span>
</span><span class="linenos">26</span><span class="p">}</span><span class="w"></span>
<span class="linenos">27</span><span class="k">pub</span><span class="w"> </span><span class="k">fn</span> <span class="nf">sys_semaphore_down</span><span class="p">(</span><span class="n">sem_id</span>: <span class="kt">usize</span><span class="p">)</span><span class="w"> </span>-&gt; <span class="kt">isize</span> <span class="p">{</span><span class="w"></span>
<span class="hll"><span class="linenos">28</span><span class="w"> </span><span class="n">syscall</span><span class="p">(</span><span class="n">SYSCALL_SEMAPHORE_DOWN</span><span class="p">,</span><span class="w"> </span><span class="p">[</span><span class="n">sem_id</span><span class="p">,</span><span class="w"> </span><span class="mi">0</span><span class="p">,</span><span class="w"> </span><span class="mi">0</span><span class="p">])</span><span class="w"></span>
</span><span class="linenos">29</span><span class="p">}</span><span class="w"></span>
</pre></div>
</div>
<ul class="simple">
<li><p>第 16 行，创建了一个初值为 0 ，ID 为 <code class="docutils literal notranslate"><span class="pre">SEM_SYNC</span></code> 的信号量，对应的是第 22 行
<code class="docutils literal notranslate"><span class="pre">SYSCALL_SEMAPHORE_CREATE</span></code> 系统调用；</p></li>
<li><p>第 10 行，线程 Second 执行信号量 P 操作（对应第 28行 <code class="docutils literal notranslate"><span class="pre">SYSCALL_SEMAPHORE_DOWN</span></code>
系统调用），由于信号量初值为 0 ，该线程将阻塞；</p></li>
<li><p>第 5 行，线程 First 执行信号量 V 操作（对应第 25 行 <code class="docutils literal notranslate"><span class="pre">SYSCALL_SEMAPHORE_UP</span></code> 系统调用），
会唤醒等待该信号量的线程 Second。</p></li>
</ul>
</div>
<div class="section" id="id5">
<h3>实现 semaphore 系统调用<a class="headerlink" href="#id5" title="永久链接至标题"></a></h3>
<p>操作系统如何实现信号量系统调用呢？我们还是采用通常的分析做法：数据结构+方法，
即首先考虑一下与此相关的核心数据结构，然后考虑与数据结构相关的相关函数/方法的实现。</p>
<p>在线程的眼里，信号量是一种每个线程能看到的共享资源，且在一个进程中，可以存在多个不同信号量资源，
所以我们可以把所有的信号量资源放在一起让进程来管理，如下面代码第 9 行所示。这里需要注意的是：
<code class="docutils literal notranslate"><span class="pre">semaphore_list:</span> <span class="pre">Vec&lt;Option&lt;Arc&lt;Semaphore&gt;&gt;&gt;</span></code> 表示的是信号量资源的列表。而 <code class="docutils literal notranslate"><span class="pre">Semaphore</span></code>
是信号量的内核数据结构，由信号量值和等待队列组成。操作系统需要显式地施加某种控制，来确定当一个线程执行
P 操作和 V 操作时，如何让线程睡眠或唤醒线程。在这里，P 操作是由 <code class="docutils literal notranslate"><span class="pre">Semaphore</span></code> 的 <code class="docutils literal notranslate"><span class="pre">down</span></code>
方法实现，而 V 操作是由 <code class="docutils literal notranslate"><span class="pre">Semaphore</span></code> 的 <code class="docutils literal notranslate"><span class="pre">up</span></code> 方法实现。</p>
<div class="highlight-rust notranslate"><div class="highlight"><pre><span></span><span class="linenos"> 1</span><span class="k">pub</span><span class="w"> </span><span class="k">struct</span> <span class="nc">ProcessControlBlock</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="linenos"> 2</span><span class="w"> </span><span class="c1">// immutable</span>
<span class="linenos"> 3</span><span class="w"> </span><span class="k">pub</span><span class="w"> </span><span class="n">pid</span>: <span class="nc">PidHandle</span><span class="p">,</span><span class="w"></span>
<span class="linenos"> 4</span><span class="w"> </span><span class="c1">// mutable</span>
<span class="linenos"> 5</span><span class="w"> </span><span class="n">inner</span>: <span class="nc">UPSafeCell</span><span class="o">&lt;</span><span class="n">ProcessControlBlockInner</span><span class="o">&gt;</span><span class="p">,</span><span class="w"></span>
<span class="linenos"> 6</span><span class="p">}</span><span class="w"></span>
<span class="linenos"> 7</span><span class="k">pub</span><span class="w"> </span><span class="k">struct</span> <span class="nc">ProcessControlBlockInner</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="linenos"> 8</span><span class="w"> </span><span class="o">..</span><span class="p">.</span><span class="w"></span>
<span class="hll"><span class="linenos"> 9</span><span class="w"> </span><span class="k">pub</span><span class="w"> </span><span class="n">semaphore_list</span>: <span class="nb">Vec</span><span class="o">&lt;</span><span class="nb">Option</span><span class="o">&lt;</span><span class="n">Arc</span><span class="o">&lt;</span><span class="n">Semaphore</span><span class="o">&gt;&gt;&gt;</span><span class="p">,</span><span class="w"></span>
</span><span class="linenos">10</span><span class="p">}</span><span class="w"></span>
<span class="linenos">11</span>
<span class="linenos">12</span><span class="k">pub</span><span class="w"> </span><span class="k">struct</span> <span class="nc">Semaphore</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="linenos">13</span><span class="w"> </span><span class="k">pub</span><span class="w"> </span><span class="n">inner</span>: <span class="nc">UPSafeCell</span><span class="o">&lt;</span><span class="n">SemaphoreInner</span><span class="o">&gt;</span><span class="p">,</span><span class="w"></span>
<span class="linenos">14</span><span class="p">}</span><span class="w"></span>
<span class="linenos">15</span><span class="k">pub</span><span class="w"> </span><span class="k">struct</span> <span class="nc">SemaphoreInner</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="hll"><span class="linenos">16</span><span class="w"> </span><span class="k">pub</span><span class="w"> </span><span class="n">count</span>: <span class="kt">isize</span><span class="p">,</span><span class="w"></span>
</span><span class="hll"><span class="linenos">17</span><span class="w"> </span><span class="k">pub</span><span class="w"> </span><span class="n">wait_queue</span>: <span class="nc">VecDeque</span><span class="o">&lt;</span><span class="n">Arc</span><span class="o">&lt;</span><span class="n">TaskControlBlock</span><span class="o">&gt;&gt;</span><span class="p">,</span><span class="w"></span>
</span><span class="linenos">18</span><span class="p">}</span><span class="w"></span>
<span class="linenos">19</span><span class="k">impl</span><span class="w"> </span><span class="n">Semaphore</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="linenos">20</span><span class="w"> </span><span class="k">pub</span><span class="w"> </span><span class="k">fn</span> <span class="nf">new</span><span class="p">(</span><span class="n">res_count</span>: <span class="kt">usize</span><span class="p">)</span><span class="w"> </span>-&gt; <span class="nc">Self</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="linenos">21</span><span class="w"> </span><span class="bp">Self</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="linenos">22</span><span class="w"> </span><span class="n">inner</span>: <span class="nc">unsafe</span><span class="w"> </span><span class="p">{</span><span class="w"> </span><span class="n">UPSafeCell</span>::<span class="n">new</span><span class="p">(</span><span class="w"></span>
<span class="linenos">23</span><span class="w"> </span><span class="n">SemaphoreInner</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="linenos">24</span><span class="w"> </span><span class="n">count</span>: <span class="nc">res_count</span><span class="w"> </span><span class="k">as</span><span class="w"> </span><span class="kt">isize</span><span class="p">,</span><span class="w"></span>
<span class="linenos">25</span><span class="w"> </span><span class="n">wait_queue</span>: <span class="nc">VecDeque</span>::<span class="n">new</span><span class="p">(),</span><span class="w"></span>
<span class="linenos">26</span><span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="linenos">27</span><span class="w"> </span><span class="p">)},</span><span class="w"></span>
<span class="linenos">28</span><span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="linenos">29</span><span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="linenos">30</span>
<span class="linenos">31</span><span class="w"> </span><span class="k">pub</span><span class="w"> </span><span class="k">fn</span> <span class="nf">up</span><span class="p">(</span><span class="o">&amp;</span><span class="bp">self</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="linenos">32</span><span class="w"> </span><span class="kd">let</span><span class="w"> </span><span class="k">mut</span><span class="w"> </span><span class="n">inner</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="bp">self</span><span class="p">.</span><span class="n">inner</span><span class="p">.</span><span class="n">exclusive_access</span><span class="p">();</span><span class="w"></span>
<span class="linenos">33</span><span class="w"> </span><span class="n">inner</span><span class="p">.</span><span class="n">count</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span><span class="w"></span>
<span class="hll"><span class="linenos">34</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">inner</span><span class="p">.</span><span class="n">count</span><span class="w"> </span><span class="o">&lt;=</span><span class="w"> </span><span class="mi">0</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
</span><span class="hll"><span class="linenos">35</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="kd">let</span><span class="w"> </span><span class="nb">Some</span><span class="p">(</span><span class="n">task</span><span class="p">)</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">inner</span><span class="p">.</span><span class="n">wait_queue</span><span class="p">.</span><span class="n">pop_front</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
</span><span class="hll"><span class="linenos">36</span><span class="w"> </span><span class="n">add_task</span><span class="p">(</span><span class="n">task</span><span class="p">);</span><span class="w"></span>
</span><span class="linenos">37</span><span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="linenos">38</span><span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="linenos">39</span><span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="linenos">40</span>
<span class="linenos">41</span><span class="w"> </span><span class="k">pub</span><span class="w"> </span><span class="k">fn</span> <span class="nf">down</span><span class="p">(</span><span class="o">&amp;</span><span class="bp">self</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="linenos">42</span><span class="w"> </span><span class="kd">let</span><span class="w"> </span><span class="k">mut</span><span class="w"> </span><span class="n">inner</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="bp">self</span><span class="p">.</span><span class="n">inner</span><span class="p">.</span><span class="n">exclusive_access</span><span class="p">();</span><span class="w"></span>
<span class="linenos">43</span><span class="w"> </span><span class="n">inner</span><span class="p">.</span><span class="n">count</span><span class="w"> </span><span class="o">-=</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span><span class="w"></span>
<span class="hll"><span class="linenos">44</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">inner</span><span class="p">.</span><span class="n">count</span><span class="w"> </span><span class="o">&lt;</span><span class="w"> </span><span class="mi">0</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
</span><span class="hll"><span class="linenos">45</span><span class="w"> </span><span class="n">inner</span><span class="p">.</span><span class="n">wait_queue</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">current_task</span><span class="p">().</span><span class="n">unwrap</span><span class="p">());</span><span class="w"></span>
</span><span class="hll"><span class="linenos">46</span><span class="w"> </span><span class="nb">drop</span><span class="p">(</span><span class="n">inner</span><span class="p">);</span><span class="w"></span>
</span><span class="hll"><span class="linenos">47</span><span class="w"> </span><span class="n">block_current_and_run_next</span><span class="p">();</span><span class="w"></span>
</span><span class="linenos">48</span><span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="linenos">49</span><span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="linenos">50</span><span class="p">}</span><span class="w"></span>
</pre></div>
</div>
<p>首先是核心数据结构：</p>
<ul class="simple">
<li><p>第 9 行，进程控制块中管理的信号量列表。</p></li>
<li><p>第 16-17 行，信号量的核心数据成员：信号量值和等待队列。</p></li>
</ul>
<p>然后是重要的三个成员函数：</p>
<ul class="simple">
<li><p>第 20 行，创建信号量，信号量初值为参数 <code class="docutils literal notranslate"><span class="pre">res_count</span></code> 。</p></li>
<li><p>第 31 行，实现 V 操作的 <code class="docutils literal notranslate"><span class="pre">up</span></code> 函数，第 34 行，当信号量值小于等于 0 时，
将从信号量的等待队列中弹出一个线程放入线程就绪队列。</p></li>
<li><p>第 41 行，实现 P 操作的 <code class="docutils literal notranslate"><span class="pre">down</span></code> 函数，第 44 行，当信号量值小于 0 时，
将把当前线程放入信号量的等待队列，设置当前线程为挂起状态并选择新线程执行。</p></li>
</ul>
<p>Dijkstra, Edsger W. Cooperating sequential processes (EWD-123) (PDF). E.W. Dijkstra Archive.
Center for American History, University of Texas at Austin. (transcription) (September 1965)
<a class="reference external" href="https://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html">https://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html</a></p>
<p>Downey, Allen B. (2016) [2005]. “The Little Book of Semaphores” (2nd ed.). Green Tea Press.</p>
<p>Leppäjärvi, Jouni (May 11, 2008). “A pragmatic, historically oriented survey on the universality
of synchronization primitives” (pdf). University of Oulu, Finland.</p>
</div>
</div>
</div>
</article>
<footer>
<div class="related-pages">
<a class="next-page" href="4condition-variable.html">
<div class="page-info">
<div class="context">
<span>Next</span>
</div>
<div class="title">条件变量机制</div>
</div>
<svg><use href="#svg-arrow-right"></use></svg>
</a>
<a class="prev-page" href="2lock.html">
<svg><use href="#svg-arrow-right"></use></svg>
<div class="page-info">
<div class="context">
<span>Previous</span>
</div>
<div class="title">锁机制</div>
</div>
</a>
</div>
<div class="related-information">
Copyright &#169; OS2022Summer
|
Built with <a href="https://www.sphinx-doc.org/">Sphinx</a>
and
<a class="muted-link" href="https://pradyunsg.me">@pradyunsg</a>'s
<a href="https://github.com/pradyunsg/furo">Furo theme</a>.
|
<a class="muted-link" href="../_sources/chapter8/3semaphore.rst.txt"
rel="nofollow">
显示源代码
</a>
</div>
</footer>
</div>
<aside class="toc-drawer">
<div class="toc-sticky toc-scroll">
<div class="toc-title-container">
<span class="toc-title">
目录
</span>
</div>
<div class="toc-tree-container">
<div class="toc-tree">
<ul>
<li><a class="reference internal" href="#">信号量机制</a><ul>
<li><a class="reference internal" href="#id2">本节导读</a></li>
<li><a class="reference internal" href="#id3">信号量的起源和基本思路</a></li>
<li><a class="reference internal" href="#id4">实现信号量</a><ul>
<li><a class="reference internal" href="#semaphore">使用 semaphore 系统调用</a></li>
<li><a class="reference internal" href="#id5">实现 semaphore 系统调用</a></li>
</ul>
</li>
</ul>
</li>
</ul>
</div>
</div>
</div>
</aside>
</div>
</div><script data-url_root="../" id="documentation_options" src="../_static/documentation_options.js"></script>
<script src="../_static/jquery.js"></script>
<script src="../_static/underscore.js"></script>
<script src="../_static/doctools.js"></script>
<script src="../_static/scripts/main.js"></script>
<script kind="utterances">
var commentsRunWhenDOMLoaded = cb => {
if (document.readyState != 'loading') {
cb()
} else if (document.addEventListener) {
document.addEventListener('DOMContentLoaded', cb)
} else {
document.attachEvent('onreadystatechange', function() {
if (document.readyState == 'complete') cb()
})
}
}
var addUtterances = () => {
var script = document.createElement("script");
script.type = "text/javascript";
script.src = "https://utteranc.es/client.js";
script.async = "async";
script.setAttribute("repo", "LearningOS/rust-based-os-comp2022");
script.setAttribute("issue-term", "pathname");
script.setAttribute("theme", "github-light");
script.setAttribute("label", "comments");
script.setAttribute("crossorigin", "anonymous");
sections = document.querySelectorAll("div.section");
if (sections !== null) {
section = sections[sections.length-1];
section.appendChild(script);
}
}
commentsRunWhenDOMLoaded(addUtterances);
</script>
<script src="../_static/translations.js"></script>
</body>
</html>
Reference in New Issue View Git Blame Copy Permalink