174 lines
7.1 KiB
TeX
174 lines
7.1 KiB
TeX
\documentclass[12pt, a4paper]{article}
|
||
\usepackage[UTF8]{ctex}
|
||
\usepackage{geometry}
|
||
\usepackage{amsmath}
|
||
\usepackage{amsthm}
|
||
\usepackage{amssymb}
|
||
\usepackage{enumitem}
|
||
\usepackage{float}
|
||
\usepackage{graphicx}
|
||
\usepackage{extarrows}
|
||
\usepackage{booktabs}
|
||
\usepackage{diagbox}
|
||
\usepackage{siunitx}
|
||
\usepackage{subcaption}
|
||
\usepackage{fontspec}
|
||
\usepackage{listings}
|
||
\usepackage{xcolor}
|
||
\usepackage{siunitx}
|
||
\usepackage[ruled,vlined]{algorithm2e}
|
||
|
||
\sisetup{
|
||
group-separator={,},
|
||
}
|
||
|
||
\definecolor{vscodeBlue}{RGB}{0,0,255} % 关键字/语句
|
||
\definecolor{vscodeRed}{RGB}{163,21,21} % 字符串
|
||
\definecolor{vscodeGreen}{RGB}{0,128,0} % 注释
|
||
|
||
\newfontfamily\codefont{Fira Code}
|
||
\lstset{
|
||
basicstyle = \footnotesize\codefont,
|
||
% ---
|
||
tabsize = 4,
|
||
showstringspaces = false,
|
||
numbers = left,
|
||
numberstyle = \codefont,
|
||
% ---
|
||
breaklines = true,
|
||
captionpos = t,
|
||
% ---
|
||
frame = l,
|
||
flexiblecolumns,
|
||
commentstyle=\color{vscodeGreen}, % 注释样式
|
||
keywordstyle=\color{vscodeBlue}, % 关键字样式
|
||
stringstyle=\color{vscodeRed}, % 字符串样式
|
||
rangebeginprefix = //\ BEGIN_LST_,
|
||
rangeendprefix = //\ END_LST_
|
||
}
|
||
|
||
\renewcommand{\qedsymbol}{}
|
||
|
||
\lstMakeShortInline|
|
||
|
||
\geometry{a4paper,scale=0.8}
|
||
|
||
\allowdisplaybreaks[4] %允许公式跨页
|
||
|
||
\setenumerate[1]{label=\arabic{*}. }
|
||
\setenumerate[2]{label=(\arabic{*})}
|
||
|
||
\title{\Huge{{\bf 操作系统大作业实验1报告}}}
|
||
\author{高艺轩 2022010639}
|
||
\date{}
|
||
|
||
\begin{document}
|
||
\maketitle
|
||
\section{实验目的}
|
||
\begin{enumerate}
|
||
\item 通过对进程间通信同步/互斥问题的编程实现，加深理解信号量和P、V操作的原理；
|
||
\item 对Windows或Linux涉及的几种互斥、同步机制有更进一步的了解；
|
||
\item 熟悉Windows或Linux中定义的与互斥、同步有关的函数。
|
||
\end{enumerate}
|
||
|
||
\section{实验题目}
|
||
本次实验选择的题目是“银行柜员服务问题”。
|
||
|
||
\section{问题描述}
|
||
银行有 n 个柜员负责为顾客服务，顾客进入银行先取一个号码，然后等着叫号。当某个柜员空闲下来，就叫下一个号。
|
||
|
||
编程实现该问题，用 P、V 操作实现柜员和顾客的同步。
|
||
|
||
\section{思路与程序结构}
|
||
这个问题的场景实际上就是一个典型的生产者-消费者问题。把顾客看作资源，柜员看作消费者，那么顾客在不停地到来就是生产者生产的过程，柜员服务即为消费者。因此所要竞争的主要内容即为“正在等待的顾客”，由柜员对顾客数执行P，由到来的顾客对顾客数执行V；另外，为了存储正在等待的顾客，用于在顾客线程和柜员线程中交换对应的顾客信息，需要维护一个队列以及对应的互斥锁，在访问前使用P原语锁定，访问结束后使用V原语释放。
|
||
|
||
为了便于观察现象和验证程序运行，本次实验中我将时间刻间隔设置为\SI{200}{ms}。
|
||
|
||
具体来讲，在全局设置代表待服务的顾客数量的信号量：
|
||
\lstinputlisting[language=c++, linerange=COUNT_SEM]{../banker.cpp}
|
||
同时设置一个正在等待服务的客户队列，并用一个互斥锁保护它：
|
||
\lstinputlisting[language=c++, linerange=CUS_Q]{../banker.cpp}
|
||
|
||
在设置好全局变量后，分别实现柜员和顾客。对于柜员，每到一个时间刻，如果正在服务的客户还没有服务完，那么就继续服务；如果处于空闲状态，则尝试执行|P(customer_num_sem)|获得一个新的客户。如果能获得客户，则进一步锁定客户队列，取出队头进行服务，再解锁客户队列。伪代码如下：
|
||
\begin{algorithm}[htbp]
|
||
\caption{Server Procedure}
|
||
\SetKwFunction{FMain}{Teller}
|
||
\SetKwProg{Fn}{Function}{:}{}
|
||
\Fn{\FMain{}}{
|
||
\While{true}{
|
||
P(customers\_num\_sem)\;
|
||
|
||
P(mutex)\;
|
||
customer\_number $\leftarrow$ dequeue(customer\_queue)\;
|
||
V(mutex)\;
|
||
|
||
serve(customer\_number)\;
|
||
}
|
||
}
|
||
\end{algorithm}
|
||
|
||
实际实现的代码：
|
||
\lstinputlisting[language=c++, linerange=TELLER]{../banker.cpp}
|
||
|
||
对于客户线程，首先不断等待直到到达设定的进入时间，首先锁定客户队列，将自己加入，同时执行|V(customer_num_sem)|来向柜员线程提示有一个新的客户产生。伪代码如下：
|
||
\begin{algorithm}[htbp]
|
||
\caption{Customer Procedure}
|
||
\SetKwFunction{FMain}{Customer}
|
||
\SetKwProg{Fn}{Function}{:}{}
|
||
\Fn{\FMain{info}}{
|
||
sleep\_until(arrival\_time)\;
|
||
|
||
P(mutex)\;
|
||
enqueue(customer\_queue, info)\;
|
||
V(mutex)\;
|
||
|
||
V(customers\_num\_sem)\;
|
||
}
|
||
\end{algorithm}
|
||
|
||
实际实现的代码：
|
||
\lstinputlisting[language=c++, linerange=CUSTOMER]{../banker.cpp}
|
||
|
||
在实现了客户与柜员时，|main|函数只需要读取配置文件、创建所有的柜员和客户进程即可：
|
||
\lstinputlisting[language=c++, linerange=MAIN]{../banker.cpp}
|
||
|
||
\section{程序运行情况}
|
||
使用指导书中给出的测试数据和自己编写的测试数据都进行了测试。使用指导书中的输入：
|
||
\lstinputlisting{../test_data/1.txt}
|
||
得到的输出为
|
||
\lstinputlisting{../test_data/1_out.txt}
|
||
|
||
再使用自己编写的测试数据：
|
||
\lstinputlisting{../test_data/2.txt}
|
||
得到的输出为
|
||
\lstinputlisting{../test_data/2_out.txt}
|
||
|
||
可以看到正确实现了客户排队与柜员依次服务。
|
||
|
||
\section{思考题}
|
||
\begin{enumerate}
|
||
\item 柜员人数和顾客人数对结果分别有什么影响？
|
||
\begin{proof}[答]
|
||
当顾客人数很少时，几乎每时每刻都会有空闲的柜员，因此所有的客户刚到来就能获得服务，很少会有顾客等待，服务的总时间基本上只取决于$(\text{到达时间}+\text{服务时间})$最长的客户服务结束的时间；当柜员人数很少时，几乎时时刻刻所有的柜员都在工作，因此总时间将会取决于$\frac{\text{所有顾客所需要服务的总时间}}{\text{柜员的数量}}$。
|
||
\end{proof}
|
||
\item 实现互斥的方法有哪些？各自有什么特点？效率如何？
|
||
\begin{proof}[答]
|
||
\begin{enumerate}
|
||
\item 将临界区设置禁止中断：简单有效，但是可靠性不高，且不适用于多处理器；
|
||
\item 锁变量：出现忙等，效率不高；
|
||
\item 严格轮转法：临界区外的进程也会阻塞其它进程，效率不高；
|
||
\item Peterson算法：可以正常工作，但是也会出现忙等，效率比较低
|
||
\item 硬件实现：需要硬件支持，可以支持任意数目的进程，但是也可能出现忙等。
|
||
\item 信号量：效率比较高，但是信号量的控制不容易分析。
|
||
\end{enumerate}
|
||
\end{proof}
|
||
\end{enumerate}
|
||
|
||
\section{实验总结}
|
||
在本次实验中，我在实践中学习了线程间的同步和互斥，从实践中考虑问题，进一步让我理解了P、V原语工作的核心思路与应用，也在编程过程中学习了一些C++标准库的应用。
|
||
|
||
\appendix
|
||
\section{完整源代码}
|
||
\lstinputlisting[language=C++]{../banker.cpp}
|
||
|
||
\end{document} |