%
%        PAR-LANG.TEX :   1995-04-20 21:40:01
%
\documentstyle[a4j,jtwocolumn]{jarticle}
\input{mymacros}
\title{$BJY6/2q;qNA(B\\--- $BJBNs=hM}8@8l(B ---}
\author{$BDEM8(B $B8x6G(B}
\begin{document}
\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{$BF3F~(B}
$B%O!<%I%&%'%"5;=Q$NH/C#$K$h$j7W;;5!$NB.EY$OL\3P$7$$8~>e$r?k$2$F$-$?$,!$(B
$B$=$l$K$b8B3&$,$"$k!#$K$b94$i$:7W;;5!$,=hM}$9$kLdBj$OBg5,LO2=$7$F$$$k$?$a!$(B
$BJBNs=hM}$NI,MW@-$,9b$^$C$F$$$k!#$^$?BgNL@8;:$K$h$kHFMQ=hM}AuCV$N(B
$BDc2A3J2=$K$h$j!$D6Bg7?7W;;5!$r:n$k$h$jJ#?t$N=hM}AuCV$K$h$kJBNs=hM}(B
$B%7%9%F%`$NJ}$,%3%9%H%Q%U%)!<%^%s%9$,$h$/$J$k798~$K$"$k!#(B
$B$3$&$$$&E@$+$i$b!$JBNs=hM}8@8l$NI,MW@-$O9b$^$C$F$$$k!#(B

$B$^$?%=%U%H%&%'%"$NBg5,LO2=$KH<$$!$$=$N:n@.!&J]<i!&=$@5$,:$Fq$K$J$C$F(B
$B$-$F$$$k!#$3$l$r2r7h$9$k$K$O%W%m%0%i%`$N%b%8%e!<%k2=!$%G!<%?$NCj>]2=!$(B
$B>pJs1#JC!$%*%V%8%'%/%H;X8~%W%m%0%i%_%s%0Ey$,Ds0F$5$l$F$$$k$,!$(B
$B$3$l$i$r<B8=$9$k$K$OJBNs=hM}8@8l$,E,$7$F$$$k!#(B

$BJBNs=hM}8@8l$K$OFs$D$NN.$l$,$"$k!#0lJ}$O=>Mh$NC`<!=hM}8@8l$KJBNs=hM}5!G=$r(B
$BIU2C$9$k$b$N$G$"$j!$$b$&0lJ}$O%G!<%?!&%U%m!<8@8l$N$h$&$K?7$7$$4QE@$K(B
$BN)$D$b$N$G$"$k!#(B

$BJBNs=hM}%7%9%F%`$K$*$$$FJBNs$K<B9T$5$l$k!$J#?t$N=hM}4V$N>pJs8r49$r(B
$BG!2?$K5-=R$9$k$+$,JBNs=hM}8@8l$N4pK\E*2]Bj$H$J$C$F$$$k!#(B

$BJBNs=hM}8@8l$NFCD'$O!$JBNsF0:n$,5-=R$G$-$k$N$OL^O@$N$3$H!$O@M}9=B$$K4p$E$/(B
$B%b%8%e!<%kJ,3d$,2DG=$G$"$k$3$H$G$"$k!#C`<!=hM}8@8l$G$O%b%8%e!<%kJ,3d$,(B
$B=hM}$NN.$l$K0MB8$7$F$7$^$$!$0l$D$NO@M}E*5!G=$r0l$D$N%b%8%e!<%k$KBP1~(B
$B$5$;$k$3$H$OFq$7$$!#$3$NE@JBNs=hM}8@8l$G$O@)8f$NN.$l$N1F6A$r<u$1$:$K!$(B
$B%G!<%?$d<jB3$-$NCj>]2=$,2DG=$G$"$k!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{$BJBNs=hM}8@8l$N5!G=(B}
$BJBNs=hM}8@8l$KI,MW$J5!G=$O!$JBNsF0:n$,5-=R$G$-$k$3$H!#JBNs$KF0:n$9$k(B
$B%W%m%;%94V$NAj8_:nMQ$r5-=R$9$k$?$a$KI,MW$H$J$k!$%W%m%;%94VDL?.$N<jCJ!#(B
$B$=$7$FHs7hDj@-$G$"$k!#0J2<$=$l$>$l$K$D$$$F@bL@$9$k!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{$BJBNs@-(B}
$BJBNs@-$rL@<($9$kJ}K!$K$OBg$-$/J,$1$FFs$D$"$k!#0l$D$O3F%W%m%;%9$r(B
$B0l$D$N%b%8%e!<%k$H$7$F@k8@$7!$JBNsJ,4t$K$h$C$F5-=R$9$kJ}K!!#(B
$B$b$&0lJ}$O0l$D$N%b%8%e!<%kFb$GJBNs<B9T2DG=$JItJ,$r;XDj$9$kJ}K!$G$"$k!#(B

\begin{figure}[hbtp]
\vspace*{5cm}
\caption{$B%W%m%;%95-=R$NJ,N`(B}
\end{figure}

$B$^$?!$%W%m%;%9$N5/F0J}K!$K$h$C$F$bJ,N`$9$k$3$H$,$G$-$k!#%W%m%;%9$rF0E*$K(B
$B5/F0$G$-$k>l9g!$$9$J$o$A5/F0$5$l$k%W%m%;%9$N?t$,F~NO%G!<%?$K$h$C$F(B
$BJQ2=$7F@$k>l9g$H!$@EE*$K$7$+5/F0$G$-$J$$>l9g!$$9$J$o$A5/F0$5$l$k(B
$B%W%m%;%9$N?t$,8GDj$5$l$F$$$k>l9g$H$G$"$k!#(B

\vspace{1cm}
\begin{itemize}
\item{\bf cobegin/coend}

cobegin S1; S2; ...; Sn coend $B$H$$$&7A<0$r$7$F$$$k!#5/F0$5$l$k%W%m%;%9$N(B
$B?t$O8GDj$5$l$F$$$k!#5-=RJ}K!$,4JC1$G$"$k$N$G!$:Y$+$J%l%Y%k$NJBNs@-$r(B
$B5-=R$9$k$N$KE,$9$k!#(B

\item{\bf fork/join}

fork$B$GJ#?t$N%W%m%;%9$r5/F0$7!$(Bjoin$B$G=*N;$9$k!#(Bfork$BL?Na$O7+$jJV$7<B9T(B
$B$9$k$3$H$,$G$-$k$?$a!$%W%m%;%9$N5/F0$rF0E*$K9T$($k!#(B
\end{itemize}

$B0J>eFs$D$NNc$O!$0l$D$N%b%8%e!<%kFb$GJBNsJ,4t$r5-=R$9$kJ}K!$G$"$k!#(B
$B$3$NJ}K!$O8@8l5!G=$,C1=c$G:Q$`>e!$8zN($N$h$$%3!<%I@8@.$,9T$($k!#(B
$B$=$NH?LL!$JBNs$KF0:n$9$k%W%m%;%9$NA4$F$+$iJQ?t$,8+$($F$7$^$&$3$H$+$i!$(B
$BJQ?t$N%"%/%;%9@)8f$,:$Fq$H$J$j!$%b%8%e!<%k2=$b$G$-$J$$$H$$$&7gE@$,$"$k!#(B

$B$3$l$KBP$7!$3F%W%m%;%9$r0l$D$N%b%8%e!<%k$H$7$FDj5A$9$kJ}K!$J$i!$(B
$B%W%m%0%i%`$N3,AXE*J,3d$,2DG=$G!$JQ?t$N4IM}$bMF0W$G$"$k!#$^$?@)8f$NN.$l$K(B
$B$H$i$o$l$:O@M}9=B$$K4p$E$/%b%8%e!<%kJ,3d$,9T$($k!#$7$+$7JBNsF0:nIt$r(B
$BA4$F%b%8%e!<%k2=$9$kI,MW$,$"$k$?$a!$:Y$+$JJBNsF0:n$N5-=R$K$OIT8~$-$G$"$k!#(B

$B%W%m%;%9$r0l$D$N%b%8%e!<%k$H$7$F5-=R$9$k>l9g!$$=$N5/F0J}K!$K$b@EE*$J>l9g$H(B
$BF0E*$J>l9g$,$"$k!#%W%m%;%9$NDj5A$r4^$`%b%8%e!<%k$,<B9T3+;O$7$?;~E@$G!$(B
$B<+F0E*$K$=$N%W%m%;%9$,5/F0$5$l$k$N$,@EE*$J>l9g!#<+F0E*$K%W%m%;%9$,5/F0(B
$B$5$l$k$3$H$O$J$/!$$=$N%W%m%;%9Dj5A$r;2>H2DG=$J%b%8%e!<%kFb$G5/F0L?Na$rM[$K(B
$B<B9T$9$k$N$,F0E*$J>l9g$G$"$k!#@EE*$J>l9g$O!$5/F0$5$l$k%W%m%;%9?t$O(B
$BEvA3$=$N%b%8%e!<%kFb$GDj5A$5$l$F$$$k%W%m%;%9?t$KEy$7$$!#(B

$B%W%m%;%9$NF~$l;R$K$D$$$F$O!$%W%m%;%9$r%b%8%e!<%k$H$7$FDj5A$7$?>l9g$O(B
$BFbIt%b%8%e!<%k$,?F%b%8%e!<%kFb$GDj5A$5$l$F$?L>A0$r;2>H$G$-$k$?$a!$(B
$BF14|$dGSB>@)8f$,LdBj$H$J$k!#$h$C$F%W%m%;%9$r%b%8%e!<%k$H$7$F5-=R$9$k(B
$B8@8l$OBgItJ,$,%W%m%;%9$NF~$l;R$r6X;_$7$F$$$k!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{$B%W%m%;%94VAj8_:nMQ(B}

$BJBNs$KF0:n$9$k%W%m%;%9$,6(NO$7$F=hM}$r?J$a$k$K$O!$%W%m%;%94V$G>pJs8r49(B
$B$r9T$&I,MW$,$"$k!#$3$l$r%W%m%;%94VDL?.$H$$$&!#%W%m%;%94VDL?.$O!$(B
$B<u$1<j$,>pJs$r<u$1<h$k$^$GAw$j<j$,BT$?$5$l$kF14|<0$H!$$=$&$G$J$$(B
$BHsF14|<0$KJ,N`$G$-$k!#(B

$BF14|<0DL?.$G$O!$Aw?.B&$O>pJs$,<u?.$5$l$?$3$H$r3NG'$G$-!$$^$?%P%C%U%!$b(B
$BITMW$G$"$k$,!$BT$A$N4VAw?.B&$O=hM}$r9T$($J$$!#F14|<0DL?.$r<B8=$9$kJ}K!(B
$B$H$7$F$O!$>pJs<uM}$N%A%'%C%/$r7+$jJV$79T$$B3$1$k(Bbusy waiting($BHKK;BT5!(B)
$B$H!$>pJs<uM}$,40N;$9$k$^$G<B9T$rCfCG$9$kJ}K!$H$,$"$k!#(Bbusy waiting$B$O(B
$B$J$s$i@8;:E*$J;E;v$r9T$o$:$K(BCPU$B;~4V$rO2Hq$7$F$7$^$&!#(B

$BHsF14|<0DL?.$O9bEY$JJBNs@-$r<B8=$9$k$3$H$,$G$-$k$,!$%P%C%U%!4IM}$NI,MW$,$"$j!$(B
$B$^$?>pJs$N<uM}$r3NG'$G$-$J$$!#(B

$B0lHL$K0lJ}8~DL?.$r4pK\$H$9$k>l9g$K$OHsF14|<0!$APJ}8~DL?.$r4pK\$H$9$k(B
$B>l9g$K$OF14|<0$,8~$$$F$$$k!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{$BF14|$HGSB>@)8f(B}
$B%W%m%;%94VDL?.$r<B8=$7$h$&$H$9$k$H$-!$F14|$dGSB>@)8f$,LdBj$H$J$k!#(B

$B%W%m%;%94V$GF14|$r$H$k$H$$$&$3$H$O!$$"$k;v>]$,5/$-$k$N$rBT$D$3$H$G$"$k!#(B
$B5U$K$$$($P(B,$BBT$?$l$F$$$k(B($B$9$J$o$A5/$3$k$3$H$,4|BT$5$l$F$$$k(B)
$B;v>]$r0z$-5/$3$9%W%m%;%9$,B8:_$7!$$=$N;v>]$,5/$-$?$H$-(B
$B$=$N%W%m%;%9$OB>$N%W%m%;%9$K$=$N$3$H$rCN$i$;$kI,MW$,$"$k!#%W%m%;%94V$N(B
$BF14|$N<jCJ$O!$JBNs8@8l$N4pK\5!G=$H$7$F%7%9%F%`%k!<%A%s$N7A$G(B
$BDs6!$9$k$3$H$,B?$$!#(B

$BC`<!:F;HMQ2DG=$J;q8;$KBP$7$F$O>o$K0l$D$N%W%m%;%9$7$+;HMQ$G$-$J$$$h$&(B
$B4IM}$9$kI,MW$,$"$k!#$3$l$,GSB>@)8f$G$"$k!#$3$3$G!$$"$k%W%m%;%9$,GSB>@)8f$r(B
$BI,MW$H$9$k;q8;$r;HMQCf$K!$B>$N%W%m%;%9$,$=$N;q8;$r;HMQ$7$h$&$H$9$l$P!$(B
$B$=$N%W%m%;%9$O;q8;$,2rJ|$5$l$k$N$rBT$?$M$P$J$i$J$$!#$D$^$jGSB>@)8f$r<B8=(B
$B$9$k$K$OF14|<jCJ$,I,MW$G$"$k!#(B

$BF14|$dGSB>@)8f$N5-=R$r8m$k$H!$BT$A>uBV$K$J$C$?%W%m%;%9$,1J5W$K$=$N(B
$B>uBV$+$iH4$1=P$;$J$/$J$k4m81@-$,$"$k!#$3$l$r(Bdeadlock$B$H$$$&!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{$B%Z%H%j%M%C%H(B}
$B%Z%H%j%M%C%H$OJBNsF0:n$r5-=R$9$k$?$a$N7A<0E*%b%G%k$G$"$k!#(B
$B@)8f$NN.$l$rCj>]2=$7$?$b$N$G!$JBNs%W%m%0%i%`$N@-<A$rL@$i$+$K$9$k$N$K(B
$BMQ$$$i$l$k!#(B

$B%Z%H%j%M%C%H(BN$B$r!c(BT, P, A, ${\rm B^0}$$B!d$GI=$5$l$kM-8~%0%i%U$HDj5A$9$k!#(B

N=$B!c(BT, P, A, ${\rm B^0}$$B!d(B
\begin{center}
\begin{quote}
T=\{${\rm t_1, t_2, ... t_m}$\} :$BM-8B8D$N(Btransition$B$N=89g(B

P=\{${\rm p_1, p_2, ... p_n}$\} :$BM-8B8D$N(Bplace$B$N=89g(B

A=\{${\rm a_1, a_2, ... a_e}$\} :$BM-8B8D$NM-8~;^$N=89g(B

${\rm B^0 \subset P}$ :token$B$N=i4|G[CV(B
\end{quote}
\end{center}

place$B$O4]!$(Btransition$B$OK@!$(Btoken$B$O9u4]$GI=$9!#(Btransition$B$O;v>]$K!$(B
place$B$O>r7o$KBP1~$7!$$"$k(Bplace$B$K(Btoken$B$,B8:_$9$k$3$H$O!$$=$N(Bplace$B$K(B
$BBP1~$9$k>r7o$,@.N)$7$F$$$k$3$H$r<($9!#(B

\begin{figure}[hbtp]
\vspace*{4cm}
\caption{transition$B$NH/2P(B}
\end{figure}

$BJBNsF0:n$r%Z%H%j%M%C%H$G5-=R$9$k$3$H$K$h$j!$$=$N%7%9%F%`$,(Bdeadlock$B$K(B
$B4Y$k4m81@-$NH=DjEy$,2DG=$K$J$k!#0J2<$K6qBNE*$JLdBjNc$H$=$N%Z%H%j%M%C%H(B
$B$K$h$k5-=R$r5-$9!#(B

\begin{itemize}
\item{producer/consumer$BLdBj(B}

producer$B$O>CHq$5$l$k$Y$->pJs$r:n$j!$(Bconsumer$B$,$=$N>pJs$r=hM}$9$k!#(B
producer$B$O(Bconsumer$B$N?J9T>u67$H$OL54X78$K?7$7$$>pJs$r:n$j=P$9$3$H$,$G$-$k$,!$(B
consumer$B$O(Bproducer$B$,>pJs$r:n$j=P$9$^$GBT$?$M$P$J$i$J$$!#(B

\begin{figure}[hbtp]
\vspace*{45mm}
\caption{producer/consumer$BLdBj(B}
\end{figure}

producer$B$H(Bconsumer$B$N4V$K$OL58BD9$N%P%C%U%!$,B8:_$9$k$H2>Dj$5$l$F$$$k!#(B

\item{$BGSB>@)8fLdBj(B}
1$B$D$NC`<!:F;HMQ2DG=$J;q8;$r(BN$B8D$N%W%m%;%9$,6&M-$9$k$H$-!$F1;~$K$O(B1$B8D$N(B
$B%W%m%;%9$7$+$=$N;q8;$r;HMQ$G$-$J$$$h$&$K4IM}$9$kLdBj!#(BN=2$B$N>l9g$r(B
$B?^(B~\ref{haita}$B$K<($9!#(B

\begin{figure}[hbtp]
\vspace*{52mm}
\caption{$BGSB>@)8f$NLdBj(B}
\label{haita}
\end{figure}

\item{reader/writer$BLdBj(B}

$B<!$N(B2$B<oN`$N%W%m%;%9$,(B1$B$D$N;q8;$r;HMQ$9$k!#(B

\begin{tabular}{lcl}
writer & : & $B;q8;$rGSB>E*$K;HMQ(B         \\
reader & : & $BB>$N(Breader$B$HF1;~;HMQ2DG=(B \\
       &   & writer$B$H$OF1;~;HMQIT2D(B
\end{tabular}

reader$B$,(B2$B$D!$(Bwriter$B$,(B1$B$D$N>l9g$r?^(B~\ref{rw1}$B$K<($9!#$3$NNc$G$O(Bwriter$B$,(B
$B;q8;MW5a$r$7$FBT$?$5$l$F$$$k$H$-$K!$?7$7$$(Breader$B$,;q8;MW5a$r$9$k$H!$(B
writer$B$r:9$7CV$$$F(Breader$B$N;HMQ$,5v2D$5$l$k!#$3$N>l9g$r(Breader$BM%@h$H$$$&!#(B

\begin{figure}[hbtp]
\vspace*{11cm}
\caption{$BFI$_=q$-LdBj(B(reader$BM%@h(B)}
\label{rw1}
\end{figure}

$B$3$l$KBP$70lEY(Bwriter$B$,;q8;MW5a$9$k$H!$$=$l0J8e$N?7$7$$(Breader$B$NMW5a$,5v2D(B
$B$5$l$kA0$K(Bwriter$B$NMW5a$,K~$?$5$l$k$H$$$&>r7o$r$D$1$k!#$3$N>l9g$G!$(B
reader$B$H(Bwriter$B$,3F(B1$B8D$NNc$r?^(B~\ref{rw2}$B$K<($9!#(B

\begin{figure}[hbtp]
\vspace*{7cm}
\caption{$BFI$_=q$-LdBj(B(writer$BM%@h(B)}
\label{rw2}
\end{figure}

\item{$B5J1l2H$NLdBj(B}

$B1lAp$r5[$&$?$a$K!$$-$6$_1lAp$r;f$K4,$-!$%^%C%A$G2P$r$D$1$J$/$F$O$J$i$J$$(B
$B>u67$r9M$($k!#(B3$B?M$N5J1l2H$,$=$l$>$l$-$6$_1lAp!$4,;f!$%^%C%A$N$&$A$N(B
1$B$D$:$D$r;}$C$F%F!<%V%k$K:B$C$F$$$k!#3F5J1l2H$O<+J,$N:`NA$rB>?M$K(B
$BM?$($k$3$H$O5v$5$l$J$$!#%F!<%V%k$NCf1{$K(B3$B$D$N:`NA$N$&$AG$0U$N(B2$B$D$@$1$,(B
$BCV$+$l$k!#$=$3$G;D$j$N(B1$B$D$N:`NA$r;}$C$F$$$k5J1l2H$@$1$,1lAp$r5[$&$3$H$,(B
$B$G$-$k!#$3$l$r%Z%H%j%M%C%H$GI=$9$H?^(B~\ref{tabaco}$B$N$h$&$K$J$k!#(B

\begin{figure}[hbtp]
\vspace*{12cm}
\caption{$B5J1l2H$NLdBj(B}
\label{tabaco}
\end{figure}

$B:#$^$G$NLdBj$H0[$J$j!$$3$NLdBj$O(B2$B$D$N;q8;$G6%9g$,@8$8$k!#$=$N$?$a(B2$B$D$N(B
$B:`NA$r(B2$B?M$,(B1$B$D$:$D<h$C$?>l9g$O!$(Bdeadlock$B$K4Y$C$F$7$^$&!#(B

\item{Dining Philosopher$BLdBj(B}

5$B?M$NE/3X<T$,?^(B~\ref{table}$B$N$h$&$K%F!<%V%k$K:B$j!$?);v$H;W:w$r8r8_$K9T$&!#(B
$B3FE/3X<T$N4V$K$O%U%)!<%/$,(B1$BK\$:$D$"$j!$%F!<%V%k$NCf1{$K%9%Q%2%C%F%#$,(B
$BMQ0U$5$l$F$$$k!#E/3X<T$O<+J,$NN>OF$K$"$k%U%)!<%/$r;}$?$J$$$H%9%Q%2%C%F%#(B
$B$r?)$Y$k$3$H$,$G$-$J$$!#(B

\begin{figure}[hbtp]
\vspace*{4cm}
\caption{$BE/3X<T$NG[CV(B}
\label{table}
\end{figure}

$B3FE/3X<T$,?);v$H;W:w$=$l$>$l$KHq$d$9;~4V$,M=$aJ,$+$i$J$$$?$a!$A0$b$C$F?);v(B
$B$N=gHV$r7h$a$F$7$^$&$H8zN($,0-$$!#$h$C$F$A$g$&$I?);v$r;O$a$h$&$H$7$F$$$k(B
$BE/3X<TC#$N4V$@$1$G!$6%9g$r2r7h$9$kI,MW$,$"$k!#(B

\begin{figure}[hbtp]
\vspace*{105mm}
\caption{Dining Philosopher$BLdBj(B}
\end{figure}

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{$BHs7hDj@-(B}
$BJ#?t$N<B9T7ONs$N2DG=@-$,B8:_$9$k>l9g$=$l$rM#0l$K7h$a$kI,MW$O$J$$!#$`$7$m(B
$B7hDj@-$N%W%m%0%i%`$K$7$F$7$^$&$3$H$OB>$N2DG=@-$rH]Dj$7$F$7$^$&$3$H$G$"$j!$(B
$BK>$^$7$/$J$$!#$^$?!$Hs7hDjE*$JI=8=$r2DG=$K$9$k$3$H$K$h$j5-=R$,4JC1$K$J$k!#(B

$BHs7hDj@-$H$O<B9T2DG=$JL?Na7ONs$,J#?tB8:_$9$k$3$H$r0UL#$9$k!#$3$l$K$OFs$D$N(B
$B2r<a$,2DG=$G$"$k!#0l$D$O!$8D!9$NL?Na7ONs$,=P$97k2L$NCf$G!$M?$($i$l$?>r7o$r(B
$BK~$?$9$b$N$rA4BN$NEz$($H$9$k>l9g!#$3$N>l9g$OL5@)8B$N%P%C%/%H%i%C%/$,I,MW$G(B
$B$"$k!#$b$&0l$D$O!$8D!9$NL?Na7ONs$+$i@8$8$k7k2L$NCf$G$I$l$rA4BN$NEz$($H(B
$B$7$F$b$h$$>l9g$G$"$k!#$3$N>l9g$OA4$F$NL?Na7ONs$,F1$87k2L$r@8$8$k$3$H$,B?$$!#(B

$BHs7hDj@-$N9M$($r?J$a$?$b$N$K(Bguarded command$B$,$"$k!#<!$K<B9T$9$Y$-J8$NA*Br$r(B
$B@)8f$9$k$?$a$K3FJ8$NA0$KO@M}<0$rCV$-!$$=$NO@M}<0$,??$N$H$-$@$18e$m$NJ8$,(B
$B<B9T$5$l$k!#0lHL$N>r7oJ8$H0c$&$H$3$m$O!$$=$l$>$l$N>r7o$,8_$$$KGSB>E*$G(B
$B$"$kI,MW$,$J$$$H$$$&E@$G$"$k!#J#?t$NO@M}<0$,??$K$J$k>l9g$O!$$=$NCf$N0l$D$,(B
$BHs7hDjE*$KA*$P$l$k!#(Bguarded command$B$O<!$N$h$&$J7A<0$r$7$F$$$k!#(B

\begin{center}
${\rm B_1 \to S_1, B_2 \to S_2, ..., B_n \to S_n}$
\end{center}

$BHs7hDjE*5-=R$r0l$D$N%W%m%;%9Fb$@$1$G$J$/B>%W%m%;%9$H$N4X78$KMQ$$$k$3$H$,(B
$B$G$-$k$H!$Aj<j$N1~BP$K1~$8$F<+J,$NBVEY$rJQ$($k$h$&$J5-=R$,$G$-$k$h$&$K$J$j!$(B
$B>pJs8r49$K$h$k(Bdeadlock$B$N4m81$O8:>/$9$k!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{$BNc30=hM}(B}
$BNc30=hM}$H$ONc30E*$J;vJA!$$D$^$j%(%i!<$d6[5^;~$N>pJs8r49$,@8$8$?$H$-$N(B
$BBP1~$r5-=R$9$kItJ,$rI=$9!#(B

$BDL>o$N>pJs8r49$O!$>pJs$r8r49$9$kFs$D$N%W%m%;%9$NAPJ}$,$=$N$?$a$N%3!<%I$r(B
$B<B9T$7$F=i$a$F9T$o$l$k!#$7$+$7$"$k<o$N>pJs8r49$O!$<u$1<j%W%m%;%9$,(B
$B$=$N$?$a$N%3!<%I$r<B9T$7$F$$$J$/$H$b9T$o$l$kI,MW$,$"$k!#C"$7$"$k<o$N(B
$B>pJs$r>o$K<u$1<h$l$k$h$&$KDL>o$N=hM}$K:.:_$7$F5-=R$9$k$H!$%W%m%0%i%`$,(B
$BHQ;($K$J$k!#$h$C$F$3$l$ODL>o$N=hM}$HJ,N%$7!$Nc30=hM}$H$7$F5-=R$9$k!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{$B%W%m%;%94VDL?.(B}

$B8D!9$N%W%m%;%94V$G9T$o$l$k>pJs8r49$r%W%m%;%94VDL?.$H8F$V!#(B
$B<B8=J}K!$H$7$F$O<g$K0J2<$N(B4$B$D$,$"$k!#(B

\begin{itemize}
\item{$BJQ?t$rD>@\6&M-$9$k!#(B}
\item{$B6&M-JQ?t$r4IM}$9$k%b%K%?$J$I$r2p$9$k!#(B}
\item{$B%a%C%;!<%8$r8r49$9$k!#(B}
\item{$BAj<j%W%m%;%9Fb$N<jB3$-$r8F$S=P$9!#(B}
\end{itemize}

$B0J2<!$$=$l$>$l$NJ}K!$K$D$$$F@bL@$9$k!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{$B6&M-JQ?t(B}
$B$3$l$,%W%m%;%94VDL?.$r<B8=$9$k:G$b4JC1$JJ}K!$G$"$k!#6&M-JQ?t$K>pJs$r(B
$BFI$_=q$-$9$k$3$H$K$h$C$F>pJs$N$d$j<h$j$,2DG=$K$J$k!#(B

$BGSB>@)8fLdBj$r%=%U%H%&%'%"E*$K2r7h$7$h$&$H$9$kJ}K!$K$O!$(B
\begin{itemize}
\item{$BC1=c$JGSB>@)8f$K$b!$J#;($J5-=R$,I,MW(B}
\item{busy waiting}
\end{itemize}
$B$H$$$&Bg$-$J7gE@$,$"$k!#$3$l$i$rHr$1$k$?$a$KDs0F$5$l$?J}K!$N<g$J$b$N$K!$(B
$B%;%^%U%)$HNW3&NN0h$,$"$k!#0J2<$3$l$i$K$D$$$F@bL@$9$k!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{$B%;%^%U%)(B}
$BHsIi$N@0?tCM$r$H$k%;%^%U%)(BS$B$KBP$7!$(BP$B$H(BV$B$NFs$D$NA`:n$,$"$k!#(B

\begin{tabular}{ll}
P(S):   &       ~${\rm S>0}$$B$J$i$P(B${\rm S:=S-1}$ \\
        &       ~${\rm S=0}$$B$J$i$P!$BT$A>uBV$KF~$k(B     \\
V(S):   &       ~$BBT$A>uBV$K$"$k%W%m%;%9$,B8:_(B\\
        &       $B$9$l$P!$$=$N%W%m%;%9$r<B9T>u(B\\
        &       $BBV$K0\$9!#(B\\
        &       ~$BB8:_$7$J$1$l$P!$(B${\rm S:=S+1}$
\end{tabular}

$B$3$N$H$-!$%;%^%U%)CM$O;HMQ$5$l$F$$$J$$;q8;$N?t$rI=$9!#(B
$B$3$3$G!$(BP$B!$(BV$BA`:n$O$=$l$>$lIT2DJ,$K<B9T$5$l$M$P$J$i$J$$!#$D$^$j!$%;%^%U%)(B
$B$H$$$&6&M-JQ?t$rGSB>E*$K%"%/%;%9$9$kI,MW$,$"$k!#(B

$B$3$NJ}K!$K$h$j!$(BP$BA`:n$r<B9T$7$h$&$H$9$k%W%m%;%9$,%;%^%U%)$NCM$r7+$jJV$7(B
$BD4$Y$k(B(busy waiting)$BI,MW$,$J$/$J$k!#(B

$B$3$N%;%^%U%)$N3HD%$N0l$D$H$7$F!$%;%^%U%)CM$,Ii$NCM$r$H$l$k$h$&(B
$B$K$7$?$b$N$,$"$k!#%;%^%U%)$,Ii$N>l9g!$$=$l$OBT$A>uBV$K$"$k%W%m%;%9$N?t$rI=$9!#(B

$B$^$?!$J#?t$N;q8;$GF1;~$K6%9g$,5/$3$k>l9g$KBP1~$9$k$?$a!$0lEY$KJ#?t$N%;%^%U%)$r07$($k$h$&$K3HD%$7$?$b$N$b$"$k$,!$BT$A9TNs$N4IM}$,Fq$7$/$J$C$F$7$^$&!#(B

$B%;%^%U%)$rMQ$$$k$HF14|$HGSB>@)8f$NN>J}$r4JC1$K5-=R$G$-$k$,!$%G%C%I%m%C%/$K(B
$B4Y$j0W$$$H$$$&7gE@$,$"$k!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{$BNW3&NN0h(B}
$B6&M-JQ?t$KBP$7$F0lEY$K(B1$B$D$N%W%m%;%9$7$+%"%/%;%9$G$-$J$$$h$&$K@)8B$9$l$P!$(B
$BF14|$dGSB>@)8f$K4X$9$kLdBj$O2r7h$G$-$k!#$3$l$r<B8=$9$k$?$a$N$b$N$H$7$F(B
$BNW3&NN0h(B(Critical Section)$B$,$"$k!#NW3&NN0h$H$O<!$N$h$&$JJ8$H$7$F(B
$BDj5A$5$l$k!#(B

\begin{center}
{\bf region} v {\bf do} S
\end{center}

$B$3$l$O6&M-JQ?t(Bv$B$HJ8(BS$B$rBP1~$E$1$k$b$N$G$"$j!$6&M-JQ?t$N;HMQ$OBP1~$9$k(B
$BNW3&NN0h$NFbIt$K8B$i$l$k$N$G!$%3%s%Q%$%i$,$=$l$r%A%'%C%/$9$k$3$H$,(B
$B2DG=$G$"$k(B

$BNW3&NN0h$K$D$$$F0J2<$N$h$&$J2>Dj$r@_$1$k!#(B

\begin{itemize}
\item{$B$"$k%W%m%;%9$,NW3&NN0h$KF~$m$&$H$9$k$H!$M-8B;~4VFb$KF~$k$3$H$,$G$-$k!#(B}
\item{$BF10l$N6&M-JQ?t$KBP$7$F$O!$0lEY$K(B1$B$D$N%W%m%;%9$7$+NW3&NN0h$K(B
$BF~$k$3$H$,$G$-$J$$!#(B}
\item{$BNW3&NN0hFb$N%W%m%;%9$OM-8B;~4VFb$K$=$3$+$i=P$J$1$l$P$J$i$J$$!#(B}
\end{itemize}

$B0[$J$C$?6&M-JQ?t$KBP1~$9$kNW3&NN0h$OF1;~$K<B9T$7$F$b9=$o$J$$$7!$F~$l;R$K(B
$B$9$k$3$H$b$G$-$k!#$7$+$7F~$l;R$K$7$?>l9g(Bdeadlock$B$K$J$k>l9g$,$"$k!#(B
$B$=$NNc$r0J2<$K<($9!#(B

%\begin{verbatim}
%  cobegin
%    A: region v1 do region v2 do... ;
%    B: region v2 do region v1 do... ;
%  coend
%\end{verbatim}
{\tt
~~cobegin

~~~~A: region v1 do region v2 do... ;

~~~~B: region v2 do region v1 do... ;

~~coend
}

A$B$,NN0h(Bv1$B$KF~$k$HF1;~$K(BB$B$,NN0h(Bv2$B$KF~$C$F$7$^$&$H!$(BA$B$b(BB$B$bBT$A9TNs$KF~$C$?$^$^(B
$BH4$1=P$9$3$H$,$G$-$J$$!#$3$l$O(B3$BHVL\$N2>Dj$KH?$9$k!#(B

$BNW3&NN0h$N35G0$r3HD%$7$?$b$N$K!$>r7o$D$-NW3&NN0h$,$"$k!#$3$l$OG$0U$N(B
$B>r7o$,@.N)$9$k$^$G%W%m%;%9$rBT$A>uBV$K$5$;$k$b$N$G!$<!$N$h$&$J7A<0$G$"$k!#(B

\begin{center}
region v do begin... {\bf await} C; ...end
\end{center}

$B$3$N>l9g!$6&M-JQ?t(Bv$B$,>r7o(BC$B$r@.N)$5$;$k$^$G%W%m%;%9$rBT$?$;$k!#(Bawait$B$O(B
$BNW3&NN0h$NFbIt$G$7$+;HMQ$G$-$J$$!#(Bawait$B$K$h$C$FBT$A>uBV$K$J$C$F$$$k4V$O!$(B
$B6&M-JQ?t(Bv$B$KBP$9$kGSB>@)8f$O2r=|$5$l!$B>$N%W%m%;%9$,NW3&NN0h$KF~$k!#(Bawait$B$K(B
$B$h$C$FBT$A>uBV$K$J$C$?%W%m%;%9$O>r7o$,@.N)$7<!Bh!$NW3&NN0h$KF~$k$Y$/(B
$BB>$N%W%m%;%9$H6%9g$9$k!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{$B%b%K%?(B}
$B;q8;$NDj5A$H$=$N;q8;$X$NA`:n$H$r0l%v=j$K=8$a$k$3$H$K$h$C$F!$;q8;MxMQ$N:]$K(B
$BFbIt$N>\:Y$rCN$kI,MW$,$J$/$J$k!#(B

\begin{figure}[hbtp]
{\tt
~~$B%b%K%?L>(B:monitor;

~~~~begin

~~~~~~$B>uBVJQ?t$N@k8@(B

~~~~~~procedure~$B<jB3$-L>(B

~~~~~~~~begin

~~~~~~~~~~~~$B<jB3$-K\BN(B

~~~~~~~~end;

~~~~~~$BB>$N<jB3$-$NDj5A(B

~~~~~~$B>uBVJQ?t$N=i4|2=%3!<%I(B

~~~~end;}
\caption{$B%b%K%?Dj5A(B}
\end{figure}

$B%b%K%?$O;q8;$N>uBV$rJ];}$9$k>uBVJQ?t$H!$;q8;$X$NA`:n$r<B8=$9$k%0%m!<%P%k$J(B
$B<jB3$-$+$i$J$k!#>uBVJQ?t$O%m!<%+%k$G$"$j!$<jB3$-$r2p$7$F$N$_%"%/%;%92DG=(B
$B$G$"$k!#(B

$B%b%K%?$NF~$l;R$O6X;_$5$l$F$$$k!#6&M-JQ?t$KHf$Y$k$H!$%"%/%;%9J}K!$,8BDj(B
$B$5$l$kJ,%(%i!<860x$O8:>/$9$k$,!$%b%K%?$OA4$F$N%b%8%e!<%k$+$i%"%/%;%92DG=(B
$B$G$"$kE@$,%(%i!<$N860x$K$J$j0W$$!#(B

$B>uBVJQ?t$X$N%"%/%;%9$OGSB>E*$K9T$o$l$J$1$l$P$J$i$J$$$?$a!$<jB3$-<B9T$O(B
$BGSB>@)8f$5$l$k$N$,IaDL$@$,!$<B:]$K$OF1;~<B9T2DG=$J<jB3$-$NAH$_9g$;$b(B
$BB8:_$9$k!#$=$3$G%b%K%?$N35G0$r3HD%$7!$%b%K%?Fb$N<jB3$-$NF14|$dGSB>@)8f$r(B
$B5-=R$9$kJ}K!$H$7$F!$<!$N$h$&$J$b$N$,$"$k!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{condition$BJQ?t(B}
condition$BJQ?t$O%b%K%?Fb$G$N$_@k8@$5$l$kJQ?t$G$"$j!$%b%K%?Fb$N(B
$B<jB3$-<B9T$rF14|$5$;$k$?$a$K;HMQ$5$l$k!#(B

condition$BJQ?t$KBP$7$F(Bsignal$B$H(Bwait$B$H$$$&Fs$D$NA`:n$,Dj5A$5$l$k!#(B

wait$B$r<B9T$7$?<jB3$-$O(Bwait$B>uBV$K$J$k!#0lJ}(Bsignal$B$r<B9T$7$?$H$-!$(B
wait$B>uBV$K$"$k<jB3$-$,B8:_$7$J$1$l$P!$(Bsignal$B$r<B9T$7$?<jB3$-$N=hM}$r(B
$BB39T$9$k!#(Bwait$B>uBV$K$"$k<jB3$-$,B8:_$9$l$P!$(Bsignal$B$r<B9T$7$?<jB3$-$O(B
$B0l;~E*$K(Bsuspend$B>uBV$H$J$j!$(Bwait$B>uBV$K$"$C$?<jB3$-$r0l$D:F5/F0$9$k!#(B
suspend$B>uBV$K$J$C$?<jB3$-$O!$%b%K%?Fb$K<B9T$9$Y$-<jB3$-$,$J$/$J$C$?(B
$B$H$-$K5/F0$5$l$k!#<jB3$-$,Fs$D$N>l9g$NMM;R$r!$?^(B~\ref{cond} $B$K<($9!#(B
\begin{figure}[hbtp]
\vspace*{25mm}
\caption{condition$BJQ?t$K$h$kF14|(B}
\label{cond}
\end{figure}
$B$3$l$K$h$jF10l%b%K%?Fb$KJ#?t$N<jB3$-$,B8:_2DG=$G$"$k$,!$F1;~$K<B9T(B
$B$G$-$k$N$O0l$D$N<jB3$-$@$1$G$"$k!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{$B%Q%9<0(B}
$B3F<jB3$-$NJBNs@-$K4X$9$k@)Ls>r7o$r%b%K%?Fb$N0l%v=j$K$^$H$a$F5-=R$9$k(B
$BJ}K!$N0l$D$G!$A4BN$NM}2r!$5-=R$,MF0W$G$"$k!#(B

$B%Q%9<0$O3F<jB3$-$N<B9T=g=x$K4X$9$k@)Ls$r5-=R$9$k$b$N$G$"$j!$F14|L?Na$r(B
$B=q$/I,MW$,$J$$!#5-=RJ}K!$O0J2<$NDL$j!#(B

\begin{center}
{\bf path} $B!c%Q%9$NJB$S!d(B {\bf end}
\end{center}

$B%Q%9$NJB$S$K$O<!$N$h$&$J$b$N$,$"$k!#(B

\begin{itemize}
\item{p; q; r}

$B<jB3$-(Bp,q,r$B$N=g$KC`<!<B9T$7$J$1$l$P$J$i$J$$$3$H$rI=$9!#(B

\item{p, q, r}

p,q,r$B$O8_$$$KJBNs<B9T$9$k$3$H$,IT2DG=$G$"$k$3$H$rI=$9!#(B

\item{p; \{q; r\}}

$B@h$:(Bp$B$r<B9T$7!$<!$K(Bq;r$B$H$$$&7ONs$rJ#?t8DJBNs$K<B9T$7$F$b$h$$$3$H$rI=$9!#(B
\end{itemize}

$B%Q%9<0$O<B9T=g=x$NI=8=$KM%$l$F$$$k!#$^$?<jB3$-$NF0:n5-=R$H!$F14|$d(B
$BGSB>@)8f$K4X$9$k@)Ls$N5-=R$rJ,N%$7$?E@$GM-MQ$@$G$"$k!#$7$+$7!$>uBVJQ?t(B
$B$K0MB8$9$k$h$&$JJBNs<B9T2DG=@-$N5-=R$,$G$-$J$$!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{$BJBNs;XDj(B}
$B<jB3$-4V$NF14|$HGSB>@)8f$rJ,N%$9$k$H$$$&9M$(J}$G!$F14|A`:n$O8D!9$N<jB3$-(B
$B$NCf$K5-=R$7!$GSB>@)8f(B($BJBNs<B9T$N2DG=@-(B)$B$OJL$K5-=R$9$k!#(B

$BF14|$K4X$9$k5-=R$O4{=R$N(Bcondition$BJQ?t$rMQ$$$l$P2DG=$G$"$k!#GSB>@)8f$O!$(B
parallel$B6g$GJBNs<B9T2DG=$J<jB3$-$NAH$_9g$;$r5-=R$9$k$3$H$K$h$C$F<B8=$9$k!#(B
parallel$B6g$O<!$N$h$&$J7A<0$G$"$k!#(B

\[      \matrix{
        {\rm\bf parallel} & $B<jB3$-(B_1      & {\rm\bf with} & $B<jB3$-(B_2    & , \cr
                          &               & \vdots        &             &   \cr
                          & $B<jB3$-(B_{2n-1} & {\rm\bf with} & $B<jB3$-(B_{2n} & ; \cr
        }
\]

parallel$B6g$G;XDj$5$l$J$$<jB3$-$NAH$OGSB>@)8f$5$l$k!#$^$?!$$"$k<jB3$-$,(B
$BB>$N<jB3$-$r8F$S=P$9>l9g!$A0$N<jB3$-$NGSB>@)8f$O$=$N$^$^;D$k$N$,(B
$BIaDL$G$"$k$,!$A0$N<jB3$-$,8F$S=P$7$N%9%1%8%e!<%j%s%0$KMQ$$$i$l$F$$$k(B
$B>l9g$J$I$OGSB>@)8f$r2r=|$G$-$k$H8zN($,$h$/$J$k!#$=$l$r<B8=$9$k$N$,(B
exit$B6g$G$"$k!#(Bexit$B6g$O<!$N$h$&$J7A<0$r$7$F$$$k!#(B

\[      \matrix{
        {\rm\bf exit} & $B<jB3$-(B_1      & {\rm\bf to} & $B<jB3$-(B_2    & , \cr
                      &               & \vdots      &             &   \cr
                      & $B<jB3$-(B_{2n-1} & {\rm\bf to} & $B<jB3$-(B_{2n} & ; \cr
        }
\]

to$B$h$j:8B&$,%b%K%?Fb!$1&B&$,%b%K%?30$N<jB3$-$G$"$k!#:8B&$NFbIt<jB3$-$,(B
$B1&B&$N30It<jB3$-$r8F$S=P$9$H%b%K%?$NGSB>@)8f$O2r=|$5$l!$30It<jB3$-$+$i(B
$BLa$k$H:F$SGSB>@)8f$,$J$5$l$k!#(B

$B$3$NJ}K!$OGSB>@)8f$N5-=R$,@EE*$G$"$k$?$a!$%Q%9<0$h$j$bM}2r$,MF0W$G$"$k$,!$(B
$B0J2<$N$h$&$J7gE@$,$"$k!#(B

\begin{itemize}
\item{$B>uBVJQ?t$NCM$K0MB8$9$k$h$&$JJBNs2DG=@-$N;XDj$,$G$-$J$$!#(B}
\item{condition$BJQ?t$K$h$jF0E*$KF14|LdBj$r5-=R$7$F$$$k$?$a!$%(%i!<$,5/$-(B
$B0W$/!$(Bdeadlock$B$N860x$K$J$k!#(B}
\item{$BJBNs<B9T$N2DG=@-$,BP>N$G$J$$(B($B2D49$G$J$$(B)$B>l9g$N5-=R$,$G$-$J$$!#(B}
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{$B%a%C%;!<%8DL?.(B}
$B6&M-JQ?t$r;H$o$J$$>pJs8r49$NJ}K!$K%a%C%;!<%8DL?.$,$"$k!#$3$l$O(B
$BCN$i$;$?$$FbMF$rD>@\$d$j<h$j$9$k$b$N$G$"$j!$Aw?.B&$H<u?.B&$,$=$l$>$l(B
$BAw?.L?Na$H<u?.L?Na$r<B9T$7$F$O$8$a$F%G!<%?$N$d$j<h$j$,$J$5$l$k!#(B
$B<u?.L?Na$,=P$5$l$k$^$GAw?.B&$,BT$DF14|<0$H!$<u?.B&$K4X78$J$/Aw?.B&$O(B
$B%a%C%;!<%8$rAw?.$G$-$kHsF14|<0$H$,$"$k!#(B

$BHsF14|<0$NJ}$,B?$/$NJBNs=hM}$,2DG=$H$J$k$?$a$h$/MQ$$$i$l$k$,!$(B
$B%a%C%;!<%8$,=g$K<u?.$5$l$kJ]>Z$,$J$/!$ESCf$N%a%C%;!<%8$,:G8e$^$G(B
$B<u?.$5$l$J$$$G;D$k2DG=@-$b$"$k!#(B

$B%a%C%;!<%8DL?.$N$?$a$N5!G=$N0l$D$K(Bsend/re-ceive$B$,$"$k!#$3$l$O0J2<$N(B
$B$h$&$J7A<0$GI=$5$l$k!#(B

~~~~{\bf send} $B!c<0$NJB$S!d(B {\bf to} $B!c<u?.<T!d(B

~~~~{\bf receive} $B!cJQ?t$NJB$S!d(B {\bf from} $B!cAw?.<T!d(B

$BDL?.O)$r;XDj$9$k;~4|$K$O(B2$B<oN`$"$k!#0lJ}$O@EE*$J$b$N$G!$%3%s%Q%$%k;~$K(B
$BDL?.O)$,3NDj$7$F$*$j!$DL?.O)$N;XDj$K$ODj?t$,;H$o$l$k!#$b$&0lJ}$OF0E*$J(B
$BJ}K!$G!$%3%s%Q%$%k;~$K$O3NDj$G$-$:<B9T;~$KDL?.O)$rA*Br$9$k!#(B

$B@EE*$J;XDjK!$O;XDj$,4JC1$G<B9T8zN($b9b$$$,!$<B9T;~$KA*Br$,$G$-$J$$$?$a(B
$B%W%m%0%i%`$N=@Fp@-$K7g$1$k!#F0E*$J;XDjK!$G$ODL?.O)<+?H$r%a%C%;!<%8$H$7$F(B
$BAw$k$3$H$J$I$b2DG=$K$J$k$,!$8zN(E*$J<B8=$,Fq$7$$!#(B

$BDL?.O)$H$7$F2?$r;XDj$9$k$+$K$h$C$F$b(B2$B<oN`$KJ,$1$k$3$H$,$G$-$k!#Aj<j(B
$B%W%m%;%9$rD>@\;XDj$9$kJ}K!$H!$DL?.O)$H$7$F$N%]!<%H$r;XDj$9$kJ}K!$G$"$k!#(B

$BAj<j%W%m%;%9$rD>@\;XDj$9$kJ}K!$O(B1$BBP(B1$BDL?.$K$OE,$7$F$$$k$,!$(B1$BBPB?$dB?BPB?(B
$B$NDL?.$K$OE,$5$J$$!#%a%C%;!<%8$rJ#?t$N%W%m%;%9$N$&$A$I$N%W%m%;%9$,<u?.(B
$B$7$F$b$h$$>l9g!$$"$k$$$O<u?.$9$k:]$I$N%W%m%;%9$+$iAw?.$5$l$?%a%C%;!<%8(B
$B$G$b$h$$>l9g$J$I$O!$5-=R$,:$Fq$"$k$$$OIT2DG=$H$J$k!#(B

$B$3$l$KBP$7%]!<%H$rMQ$$$kJ}K!$O!$(B1$BBPB?$dB?BPB?$NDL?.$r4pK\$H$7$F$$$k!#(B
1$B$D$N%]!<%H$KBP$7$F(Bsend/receive$B$r9T$&%W%m%;%9$,$H$b$K0l$D$G$"$k>l9g!$(B
$B$3$l$O(B1$BBP(B1$BDL?.$K$J$k$,!$0lHL$K$O$H$b$KJ#?tB8:_$9$k!#(B

\begin{figure}[hbtp]
\vspace*{47mm}
\caption{$B%]!<%H$K$h$k%a%C%;!<%8DL?.(B}
\end{figure}

%========================

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{$B1s3V<jB3$-8F=P$7(B}\label{rendezvous}
$B%a%C%;!<%8DL?.$,0lJ}8~DL?.$r4pK\$H$7$?$b$N$G$"$k$N$KBP$7!$1s3V<jB3$-8F=P$7(B
$B$OAPJ}8~DL?.$r4pK\$H$7$F$$$k!#(B

$B%W%m%;%9$NDj5A$K$OJQ?t@k8@!$F0:n5-=R$H$$$C$?=>Mh$N@k8@$NB>$K!$1s3V<jB3$-$N(B
$B@k8@$r4^$`!#%W%m%;%9$O<+J,$N%m!<%+%kJQ?t$K$7$+%"%/%;%9$G$-$:!$6&M-JQ?t$O(B
$BB8:_$7$J$$!#(B

$B>pJs8r49$r9T$*$&$H$9$k>l9g$O!$Aj<j%W%m%;%9Fb$N1s3V<jB3$-$r(Bcall$B$7!$(B
$B8F$S=P$7$?<jB3$-$,=*N;$9$k$^$GBT$?$5$l$k!#%G!<%?$N$d$j<h$j$O0z?tE>Aw(B
$B$G9T$o$l$k!#(B

$B8F$P$l$?1s3V<jB3$-$,$$$D<B9T$5$l$k$+$H$$$&E@$G!$(B2$B$D$NJ}K!$,$"$k!#(B
$B%W%m%;%9$O@h$:DL>o$N=hM}$r<B9T$7!$$=$l$,=*N;$9$k$+BT$A>uBV$KF~$k$^$G(B
$B<B9T$rB3$1$k!#=hM}$,CfCG$9$k$HB>%W%m%;%9$+$i$N30ItMW5a(B($B1s3V<jB3$-$N(B
$B8F=P$7(B)$B$K$h$C$FJL$N=hM}$,;O$^$k!#<!$K$3$N=hM}$,CfCG$9$k$H!$JL$N=hM}$,(B
$B;O$^$k$+A0$N=hM}$,I|3h$9$k!#0J2<$3$l$,1J1s$KB3$-!$DL>o$N=hM}$,=*N;$7$?(B
$B8e$b%W%m%;%9$OB8:_$7B3$1!$30ItMW5a$r<u$1IU$1$k!#$3$NJ}K!$OJ,;6%W%m%;%9(B
$B$G:NMQ$5$l$F$$$k!#(B

$B$3$l$KBP$7(BAda$B$G$O!$1s3V<jB3$-$r<u$1IU$1$k$?$a$NJ8$H$7$F(Baccept$BJ8$rMQ0U$7$F$$$k!#(B

{\bf accept} $B!c<jB3$-L>!d(B ($B!c2>0z?t!d(B)
\begin{flushright}
do $B!c<jB3$-K\BN!d(B end
\end{flushright}

$B$3$l$r<B9T$9$k$H!$;XDj$5$l$?<jB3$-$,8F$S=P$5$l$k$^$GBT$?$5$l$k!#(B
$B$=$7$FF~NO0z?t$H!$J8$N%9%3!<%WFb$NJQ?t$rMQ$$$F<jB3$-K\BN$r<B9T$9$k!#(B
$B<jB3$-$,=*N;$9$k$H!$=PNO0z?t$r8F=P$7B&$N%W%m%;%9$KJV$7!$<!$NJ8$K(B
$B@)8f$r0\$9!#$3$NJ}K!$r%i%s%G%t$H8F$V!#(B

$BA0<T$G$O!$$$$D$I$N$h$&$JMW5a$r<u$1IU$1$k$+$H$$$&@)8f$r9T$($J$$!#$D$^$j(B
$B8F$S=P$5$l$kB&$O40A4$K<u?H$K$J$C$F$7$^$&$,!$8e<T$G$O$$$D$I$N<jB3$-$,(B
$B8F$S=P$5$l$k$+$r;XDj$G$-$k$?$aL@3N$J5-=R$,2DG=$G$"$k!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{$B%G!<%?%U%m!<%b%G%k(B}
$B=>Mh$NC`<!=hM}8@8l$N$h$&$K@)8f$NN.$l$rCf?4$K%W%m%0%i%`$r5-=R$9$k$N$G$O$J$/!$(B
$B%G!<%?$NN.$l$rCf?4$K5-=R$9$k$H$$$&9M$(J}$+$i@8$^$l$?8@8l$r%G!<%?%U%m!<8@8l(B
$B$H$$$&!#(B

$B%G!<%?%U%m!<8@8l$N<B9T$K$O%G!<%?%U%m!<7W;;5!$H$$$&!$(B von Neumann$B7?7W;;5!(B
$B$H$O4pK\E*$K0[$J$k%^%7%s$,I,MW$G$"$k!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{$B%G!<%?%U%m!<%0%i%U(B}
$B%G!<%?$NN.$l$K4p$E$$$?7W;;J}K!$r%0%i%U2=$7$?$b$N$r%G!<%?%U%m!<%0%i%U$H$$$&!#(B
$B$3$l$O=>Mh$N8@8l$N%U%m!<%A%c!<%H$KBP1~$9$k$b$N$G$"$j!$@)8f$NN.$l$G$O$J$/(B
$B%G!<%?$NN.$l$rI=$9!#(B

$BNc$($P(B$a+b \times c+d+e \times f$$B$H$$$&7W;;$r9M$($k!#=>Mh$NJ}K!$G$O(B
$B<!$N$h$&$J=g=x$G7W;;$9$k!#(B
\begin{itemize}
\item[(1)]{$X1 = b \times c$}
\item[(2)]{$X2 = e \times f$}
\item[(3)]{$X3 = a + X1$}
\item[(4)]{$X4 = X3 + d$}
\item[(5)]{$Answer = X4 + X2$}
\end{itemize}

$B$3$N<0$r2r@OLZ$GI=$9$H?^(B~\ref{kaiseki}$B$N$h$&$K$J$k!#$3$3$G@aE@(BA$B$O$9$0$K(B
$B7W;;$G$-$k$,!$@aE@(BB$B$N7W;;$O@aE@(BA$B$N7W;;$,$,=*N;$7$?8e$G$J$$$H9T$($J$$!#(B
$B$3$N$h$&$K$3$N?^$O7W;;$N0MB84X78$rI=$7$F$$$k!#1i;;AuCV$rB??tMQ0U$7$F$*$-!$(B
$B<B9T2DG=$K$J$C$?1i;;$+$i=g$K<B9T$7$F9T$1$P:GBg8B$NJBNs@-$,<B8=$G$-$k!#(B
$B$3$l$,%G!<%?%U%m!<7W;;$G$"$k!#(B

\begin{figure}[hbtp]
\vspace*{45mm}
\caption{$a+b \times c+d+e \times f$$B$N2r@OLZ(B}
\label{kaiseki}
\end{figure}

$B%G!<%?%U%m!<%0%i%U$O=hM}4V$N0MB84X78$rI=$7$?M-8~%0%i%U$G$"$j!$@aE@$G=hM}!$(B
$B;^$G>pJs$N5-21$,9T$o$l$k!#>pJs$K$O%G!<%?$H@)8f?.9f$,$"$j!$$=$l$>$lCf9u!$(B
$BCfH4$-$GLp0u$d(Btoken$B$,I=$5$l$k!#(B

$B@aE@$K$O(Btoken$B$rJ,4t$5$;$k(Blink$B$H!$F~NO$KBP$7=hM}$r9T$&(Bactor$B$,$"$k!#(B
$B0J2<$$$/$D$+$N(Bactor$B$K$D$$$F@bL@$9$k!#(B

\begin{figure}[hbtp]
\vspace*{23mm}
\caption{$B%j%s%/(B}
\end{figure}

\begin{figure}[hbtp]
\vspace*{36mm}
\caption{$B%j%s%/$NH/2P(B}
\end{figure}

\begin{figure}[hbtp]
\vspace*{85mm}
\caption{$B4pK\(Bactor$B$N<oN`(B}
\end{figure}

\begin{itemize}
\item{T-gate}

$B@)8fF~NO$,??$N>l9g$K$N$_F~NO%G!<%?$r$=$N$^$^=PNO$9$k!#@)8fF~NO$,56$N>l9g$O(B
$B2?$b=PNO$5$l$J$$!#(B

\item{F-gate}

T-gate$B$N5U$G!$H/2P>r7o$O@)8fF~NO$,56$G$"$k$3$H$G$"$k!#(B

\item{merge}

$B@)8fF~NO$H0lCW$9$k;^$NF~NO$r=PNO$9$k!#(B
\end{itemize}

$B%G!<%?%U%m!<%0%i%U$NNc$H$7$F!$(BZ=n!$B$r7W;;$9$k%0%i%U$r?^(B~\ref{kaijo}$B$K(B
$B<($9!#?^$G<($5$l$?>uBV$+$iF0:n$9$l$P!$:G=*E*$K(Bn!$B$NCM$,2<$+$i=PNO$5$l$k!#(B
$B$3$N%0%i%U$O(Bn$B$NCM$r(B1$B$:$D8=$8$kItJ,$H!$$=$NCM$r3]$1;;$9$kItJ,!$%k!<%W$r(B
$B@)8f$9$kItJ,$N(B3$B$D$KJ,$+$l$F$$$k!#(B

\begin{figure}[hbtp]
\vspace*{112mm}
\caption{Z=n!$B$r5a$a$k%0%i%U(B}
\label{kaijo}
\end{figure}

$B%G!<%?%U%m!<%0%i%U$O3F1i;;;R$N<B9T$K4X$7$F!$:GBg8B$NJBNs@-$,<B8=$G$-$k!#(B
$B$7$+$7!$MxMQ<T$,%W%m%0%i%`$H$7$F%G!<%?%U%m!<%0%i%U$r$=$N$^$^F~NO$9$k(B
$B$3$H$OIT2DG=$G$"$k!#$^$?%0%i%UI=8=<+?H$O%b%8%e!<%k2=$K8~$$$F$$$J$$$N$G!$(B
$B?M4V$,I=8=$9$k<jCJ$H$7$F$bIT8~$-$G$"$k!#$=$3$G!$?M4V$,%W%m%0%i%`8@8l$G(B
$BI=8=$7$?$b$N$r%3%s%Q%$%iEy$,<+F0E*$K%0%i%U2=$7!$7W;;5!$G<B9T$9$kJ}K!$,(B
$B$H$i$l$k!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{$B%G!<%?%U%m!<8@8l(B}
$B%G!<%?%U%m!<7W;;$rI=8=$9$k$?$a$N8@8l$G$"$k!#@)8f$NN.$l$r5-=R$9$k$N$G$O$J$/!$(B
$BL?Na4V$N0MB84X78$N5-=R$r:G>.8B$K$9$k!#(B

$B%G!<%?%U%m!<8@8l$rMQ$$$F%=%U%H%&%'%"$r5-=R$9$k$K$O!$0J2<$NE@$,=EMW$G$"$k!#(B
\begin{itemize}
\item{$BI{:nMQ$+$i$N2rJ|(B}

$BI{:nMQ(B\footnote{$B4X?t$NI>2AEy$K$*$$$F!$4X?tCM$rJV$90J30$K0z?t$d%0%m!<%P%kJQ?t$NCM$rJQ99$9$k$3$H(B}$B$,$"$k$HJBNs@-$N8!=P$,:$Fq$K$J$k!#(B

\item{$B1F6A$N6I=j@-(B}

$B%G!<%?4V$N0MB8@-$,6I=jE*$J$3$H!#(B

\item{$B%W%m%0%i%`$N<B9T7k2L$O%G!<%?$N0MB84X78$@$1$G7h$^$k(B}

\item{$BC10lBeF~5,B'(B}

$B0l$D$NJQ?t$K$O0l2s$NBeF~$7$+5v$5$l$J$$!#(B

\item{$B7+$jJV$7$N$?$a$NFCJL$J5;K!(B}

$BA09`!VC10lBeF~5,B'!W$N$?$a$K7+$jJV$7$,IT2DG=$H$J$k$?$a!$FCJL$J5-K!$,(B
$BI,MW$G$"$k!#(B

\item{$B<jB3$-$KMzNr0MB8@-$,$J$$(B}

$B8F$S=P$7$,<!2s$N8F$S=P$7$K1F6A$rM?$($J$$!#(B
\end{itemize}

$B$3$N$h$&$JE@$r9MN8$7$?%G!<%?%U%m!<8@8l$K$O!$(BIda$B!$(BVAL$B!$(BLucid$B$J$I$,$"$k!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{$BC10lBeF~5,B'(B}
$BF10l$NJQ?t$KBP$9$kBeF~J8$r0lEY$7$+5v$5$J$$5,B'!#(B
$BBeF~J8$G:8JU$NJQ?t$O1&JU$K8=$l$kJQ?t$K0MB8$9$k!#$7$+$7!$DL>o$OF10lJQ?t$K(B
$B2?EY$bBeF~$,9T$o$l$k$?$a!$$$$DBeF~$5$l$?CM$K0MB8$9$k$+$,LdBj$H$J$k!#(B
$B$3$l$r7hDj$7$h$&$H$9$k$H@)8f$NN.$l$rDI@W$7$J$1$l$P$J$i$J$$$,!$@)8f$NN.$l$O(B
$BF~NO%G!<%?$K$h$C$FJQ2=$9$k$N$G%3%s%Q%$%k;~$K7hDj$9$k$3$H$OIT2DG=$H$J$k!#(B
$B$3$l$r2r7h$9$k$?$a$KC10lBeF~5,B'$,:NMQ$5$l$k!#(B

$BC10lBeF~5,B'$G$OBeF~J8$O!$JQ?t$NDj5AJ8$H$_$J$9$3$H$,$G$-$k!#Nc$($P(B"S:=X+Y;"
$B$H$$$&J8$,$"$l$P!$(B"S=X+Y"$B$H$$$&4X78$O>o$K@.$jN)$D!#C10lBeF~5,B'$rF3F~$9$k(B
$B$3$H$K$h$j!$%G!<%?0MB84X78$,L@$i$+$K$J$k$@$1$G$J$/%W%m%0%i%`$N8!>Z$bMF0W$K(B
$B$J$k!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{$B7+$jJV$7$N5-K!(B}
$BC10lBeF~5,B'$rK~$?$9$?$a$K$O!$7+$jJV$7$KFCJL$J5-K!$rMQ$$$kI,MW$,$"$k!#(B
$B$3$N$?$a%G!<%?%U%m!<8@8l$G$OFCDj$N7A$N%k!<%W$7$+:n$i$;$J$$$h$&!$(B
$B%k!<%W$N$?$a$N<jCJ$r@)8B$7$F$$$k!#0lHL$K%k!<%W$O0J2<$N(B4$B$D$G9=@.$5$l$k!#(B

\begin{itemize}
\item{$B%k!<%WJQ?t$N=i4|@_Dj(B}
\item{$B%k!<%W=*N;>r7o(B}
\item{$B%k!<%W$,=*N;$7$?$H$-$KJV$9$Y$-CM$N;XDj(B}
\item{\underline{$B%k!<%WCf$G$N%k!<%WJQ?t$N:FDj5A(B}}
\end{itemize}

$B$3$&$9$l$P%k!<%WJQ?t$NCM$O<!!9$HJQ2=$9$k$,!$$=$NJQ2=$O?7$7$$%k!<%W$K(B
$BF~$k$H$-$K5/$-$k!#3F%k!<%WFb$G$OC10lBeF~5,B'$O<i$i$l$F$$$k!#$=$7$F?7$7$$(B
$B%k!<%WJQ?t$+8E$$%k!<%WJQ?t$+$rL@$i$+$K$9$k$?$a!$(BVAL$B$G$O(Biter$B$rMQ$$!$(B
Id$B$d(BLucid$B$G$O(Bnew$B$rMQ$$$k!#(BVAL$B$N%k!<%W5-=R$NNc$r?^(B~\ref{valloop}$B$K<($9!#(B

\begin{figure}[htbp]
{\tt
~~for I, J := 1, 0;

~~~~do if I = N

~~~~~~then J

~~~~~~else iter I, J := I+1, J+1;

~~~~end

~~end}
\caption{1$B$+$i(BN$B$^$G$NOB$r5a$a$k%W%m%0%i%`(B}
\label{valloop}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{$BMzNr0MB8@-(B}
$B$3$l$^$G$N5DO@$O!$=>Mh$N8@8l$G$OIaDL$K5-=R$G$-$kLdBj$G$"$k<B;~4V(B
$B=hM}(B----$BNc$($P@0?t$rF~NO$9$kEY$K$=$l$^$G$NOB$r=g$K=PNO$9$k(B
$B$h$&$JLdBj(B----$B$K$OIT8~$-$G$"$k!#(B

$B$3$NLdBj$OFs$D$NJ}K!$G2r7h$G$-$k!#0l$D$OMzNr0MB8@-$N$"$k4X?t!$$9$J$o$A(B
$B2a5n$NF~NO$r21$($F$$$k4X?t$rDs6!$9$k$b$N$G$"$k!#>e$NNc$G$O!$$=$l$^$G$NF~NO(B
$B$NOB$r5-21$7$F$*$-!$?7$7$$%G!<%?$rF~NO$9$kEY$K$=$NOB$K2C$($F9T$1$P$h$$!#(B

$B$b$&0l$D$NJ}K!$O%9%H%j!<%`$H$$$&35G0$rF3F~$7!$$=$l$KBP$7$F:nMQ$9$k4X?t$r(B
$B:n$k$b$N$G$"$k!#%9%H%j!<%`$OG[Ns$HF1$8$h$&$K07$o$l$k$,!$<B;~4V$G%G!<%?$,(B
$B6!5k$5$l$k!#OB$r5a$a$kLdBj$r(BId$B$rMQ$$$F5-=R$7$?Nc$r?^(B~\ref{stream}$B$K<($9!#(B

\begin{figure}[hbtp]
 
~~(initial {\bf SUM} $\leftarrow$ 0

~~~~for each T in {\bf IN\_DATA} do

~~~~~~~~new {\bf SUM} $\leftarrow$ {\bf SUM} + T

~~~~return all {\bf SUM} )

\caption{$B%9%H%j!<%`$NNc(B}
\label{stream}
\end{figure}

$B$3$3$G(BSUM$B$H(BIN\_DATA$B$,%9%H%j!<%`$G$"$k!#(BIN\_DATA$B$K$O<!!9$H?7$7$$CM$,F~$j(B,
$B$=$NCM$rE~Ce$7$?=g$K>CHq$7$F$$$/!#(BSUM$B$O7W;;7k2L$r=g$K=PNO(B
$B$9$k$?$a$N%9%H%j!<%`$G$"$k!#%9%H%j!<%`$O=>Mh7?$NJBNs=hM}8@8l$K$*$1$k(B
$B%]!<%H$HF1$8Lr3d$r$7$F$$$k!#C"$7>pJs8r49$O(B1$BBP(B1$B$G9T$o$l$k!#%G!<%?Aw?.B&$O(B
$B%9%H%j!<%`JQ?t$K<!!9$H%G!<%?$rBeF~$7(B,$B$3$l$i$NCM$,BeF~$5$l$?=g$K(B
$B<u?.B&$KEO$5$l$k!#%G!<%?%U%m!<8@8l$G$O%9%H%j!<%`$N35G0$rMQ$$$k$3$H$K$h$j(B
$B0lO"$N%G!<%?8r49$r1#$7$F$7$^$&!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{$BJBNs=hM}8@8l$NNc(B}
$BJBNs=hM}8@8l$N$$$/$D$+$N6qBNE*$JNc$K$D$$$F354Q$9$k!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{$BJBNs(BPascal}
\begin{itemize}
\item{$B%W%m%;%9(B}

process$BFb$d(Bmonitor$BFb$G(B~~process$B$d(Bmonitor$B$r@k8@$9$k$3$H$,$G$-$J$$$?$a!$(B
$B%W%m%0%i%`$r9=B$2=$9$k$3$H$,$G$-$J$$!#(B

\item{$B>pJs8r49(B}

$B>pJs$N8r49$O(Bmonitor$B$r2p$7$F$N$_9T$o$l$k!#(Bmonitor$B$O6&M-JQ?t$rMQ$$$F(B
$B>pJs8r49$r<B8=$7$F$$$k$,!$0l;~E*$K%G!<%?$rAw<u?.$9$k$@$1$G$=$N8e$O(B
$B2?$i8r49$r$7$J$$$h$&$J>l9g$bJQ?t$r6&M-$7$F$$$k!#$^$?>pJs8r49$NAj<j$r(B
$BFCDj$9$k$3$H$,$G$-$J$$!#(B

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Modula}
\begin{itemize}
\item{$B%W%m%;%9(B}

$B%W%m%0%i%`$r0l$D$N(Bmodule$B$H$7$FI=8=$9$k!#(Bmodule$B$NLr3d$O%*%V%8%'%/%H$N(B
$B%9%3!<%W$KJI$r@_$1$k$3$H$G$"$j!$$3$l$K$h$C$F%W%m%0%i%`$N%b%8%e!<%k2=$,(B
$B2DG=$G$"$k!#(B

$BJBNs=hM}$O(Bprocess$B$rMQ$$$F5-=R$5$l!$<B9T;~$KF0E*$K5/F0$5$l$k!#$7$+$7(B
process$B<+?H$O%l%Y%k(B0($B:G$b@u$$%V%m%C%/(B)$B$G$7$+@k8@$G$-$J$$$?$a!$F~$l;R(B
$B$K$9$k$3$H$OIT2DG=$G$"$j9=B$2=$NLL$GLdBj$,$"$k!#(B

\item{$B>pJs8r49(B}

proces$B4V$N>pJs8r49$O(Binterface module$B$r2p$7$F$N$_9T$o$l$k!#(B
interface module$B$O!$@8@.$,@EE*$K9T$o$l$k$?$a8GDj?t$7$+B8:_$;$:!$(B
$B>pJs8r49$,@)8B$5$l$k!#(B

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{CSP}
\begin{itemize}
\item{$B%W%m%;%9(B}

$B%b%8%e!<%k$H$$$&35G0$,B8:_$7$J$$$?$a!$%W%m%;%9Fb30$N4V$GJQ?t$N%9%3!<%W$K(B
$BJI$,$G$-$:!$JQ?t4IM}$,Fq$7$$!#$^$?@8@.$5$l$k%W%m%;%9$N?t$O8GDj$G$"$k$N$G!$(B
process$B$N?t$,F0E*$KJQ2=$9$k$h$&$J5-=R$OIT2DG=$G$"$k!#(B

\item{$B>pJs8r49(B}

$B%W%m%;%94V$NAj8_:nMQ$r5-=R$9$k<jCJ$H$7$F%a%C%;!<%88r49$rMQ0U$7!$Hs7hDjE*$J(B
$B%a%C%;!<%88r49$r2DG=$K$7$F$$$k!#$h$C$F%G!<%?$N0l;~E*$d$j<h$j$K$OE,$7$F$$$k$,!$(B
$B%W%m%;%94V$G%*%V%8%'%/%H$r6&M-$9$k$h$&$J>l9g$N5-=R$,:$Fq$G$"$k!#(B

$BAj8_:nMQ$OF~=PNOL?Na$rMQ$$$F5-=R$9$k$,!$$3$N:]Aj<j%W%m%;%9L>$r;XDj$9$k!#(B
$B$h$C$FITFCDj%W%m%;%9$rAj<j$K$9$k%5!<%P%W%m%;%9$r5-=R$9$k$3$H$O$G$-$J$$!#(B

\item{$BHs7hDj@-(B}

guarded command$B$r3HD%$7$FMxMQ$G$-$k!#6qBNE*$K$O(Bguard$BIt$KO@M}<0$K2C$($F(B
$BF~NOJ8$r=q$/$3$H$,$G$-$k!#F~NOJ8$,(Bguard$B$K4^$^$l$F$$$k>l9g$O!$O@M}<0$,??$G(B
$B3n$DF~NOJ8$NAj<j%W%m%;%9$N=`Hw$,$G$-$F$$$l$P(Bguard$B$O??$H$_$J$5$l$k!#(B
$B$3$l$K$h$jI,$:$7$bAj<j$N1~Ez$rBT$DI,MW$,$J$/!$2DG=$J%a%C%;!<%88r49$+$i(B
$B<B9T$G$-$k!#(B

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{$BJ,;6%W%m%;%9(B}
\begin{itemize}
\item{$B%W%m%;%9(B}

$B%j%"%k%?%$%`=hM}$rL\E*$H$7$?8@8l$G$"$k$+$i(Bprocess$B$N?t$,8GDj$7$F$*$j!$(B
$B<+F0E*$K<B9T$r3+;O$9$k!#8@8l$r4JC1$K$9$k$?$a(B1$B$D$N5!G=$G$5$^$6$^$J(B
$B$3$H$,5-=R$G$-$k$h$&$K$7$F$$$k$,!$$=$NJ,%(%i!<BP=h$,:$Fq$G$"$k!#(B
$B$^$?%b%8%e!<%k$H$7$F(Bprocess$B$7$+5v$5$l$F$*$i$:!$(Bprocess$B4V$NF~$l;R$O(B
$B6X;_$5$l$F$$$k$?$a!$%W%m%0%i%`$N3,AX9=B$$r%b%8%e!<%k9=B$$KH?1G$9$k$3$H$,(B
$B$G$-$J$$!#(B

\item{$B>pJs8r49(B}

$B>pJs8r49$O!$Aj<j(Bprocess$BFb$N(Bcommon procedure$B$KBP$7$F30ItMW5a$r=P$9$3$H$K(B
$B$h$C$F<B8=$9$k!#8F$S=P$9B&$OAj<j$r;XDj$G$-$k$N$KBP$7!$8F$S=P$5$l$kB&$O(B
$B;XDj$G$-$J$$!#(B

\item{$BHs7hDj@-(B}

guarded command$B$H(Bguarded region$B$,MQ0U$5$l$F$$$k!#$7$+$7<+J,$NFbIt$@$1$K(B
$B$*$1$kHs7hDj@-$G$"$j!$(BCSP$B$N$h$&$KB>%W%m%;%9$H$N>pJs8r49$N2DG=@-$r!$(B
$B>r7o$H$7$F=q$/$3$H$O$G$-$J$$!#(B

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Ada}
\begin{itemize}
\item{$B%?%9%/(B}

$B%?%9%/$N@8@.!?5/F0$OF0E*$K$b@EE*$K$b9T$($k$,!$5/F0;~$K0z?t$rEO$9$3$H$,(B
$B$G$-$J$$!#(B

\item{$B>pJs8r49(B}

$B>pJs8r49$N$?$a$N%i%s%G%t(B({\it c.f.} \ref{rendezvous}$B@a(B)$B$OJ,;6%W%m%;%9$N(B
$B>l9g$KHf$Y$F8F$S=P$9B&$H8F$S=P$5$l$kB&$NBP>N@-$OA}2C$7!$8F$S=P$5$l$kB&$G$b(B
$B8F$S=P$5$l$k;~E@$r7hDj$G$-$k$h$&$K$J$C$?$,!$Aj<j$r;XDj$9$k$3$H$O$G$-$J$$!#(B

$B$^$?>pJs8r49$N$b$&0l$D$N<jCJ$H$7$F6&M-JQ?t$,B8:_$9$k$,!$%W%m%0%i%`$N?.Mj@-!&(B
$BJ]<i@-$+$i9M$($k$HITMW$G$"$k!#(B

\item{$BHs7hDj@-(B}

$BA*BrBT$A!$>r7o$D$-%(%s%H%j8F=P$7!$;~8B$D$-%(%s%H%j8F=P$7$H$$$&(B3$B<oN`$N(B
select$BJ8$,Ds6!$5$l!$>pJs8r49$b4^$a$?BP30E*Hs7hDj@-$,5-=R2DG=$G$"$k!#(B

\item{$BNc30=hM}(B}

$B0[>o;vBV$dNc30E*;vBV$,H/@8$7$?$H$-$KBP1~$9$k$,!$%?%9%/%l%Y%k$G8+$k$H(B
$B<+J,$NCf$GBP=h$G$-$J$/$J$C$?$H$-$=$N%?%9%/$O0[>o=*N;$7!$B>$N%?%9%/$K(B
$BNc30$K4X$9$k>pJs$,EA$o$i$J$$!#(B

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{$BJBNsO@M}7?8@8l(BKL1}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{$B%W%m%0%i%`9=B$(B}
KL1$B$O0J2<$N7A<0$GI=$5$l$k!#(B
\[
\matrix{
H_1 :- G_{11}, ..., G_{1m_1} | B_{11}, ..., B_{1n_1}    \cr
\vdots                                                  \cr
H_l :- G_{l1}, ..., G_{lm_l} | B_{l1}, ..., B_{ln_l}}
\]

$B3F9T$O@a$H8F$P$l$k!#(B$H, G, B$ $B$O=R8l$G$"$j!$$=$l$>$l%/%m!<%:%X%C%I!$(B
$B%,!<%I%4!<%k!$%\%G%#%4!<%k$H8F$P$l$k!#(B

$B$"$k%4!<%k(B $H$ $B$,M?$($i$l$k$H!$(B$H$$B$H(B$H_i$$B$H$NF10l2=!$5Z$S%,!<%IIt(B
$G_{i1}, ..., G_{im_i}$ $B$N<B9T$rJBNs$K9T$&$3$H$,$G$-$k!#$3$3$G(B
$B%,!<%IIt$,@.8y$7$?%/%m!<%:$N$&$A0l$D$,A*Br$5$l!$$=$N%\%G%#It(B
$B_{k1}, ..., B_{kn_k}$ $B$,<B9T$5$l$k!#=R8l$NF1Dj$O!$=R8lL>$H0z?t$N?t$H$G(B
$B9T$o$l$k!#(B

$B=R8l$r(B"$B=R8lL>(B/$B0z?t$N?t(B"$B$GI=$9$H$9$k!#?^(B~\ref{stack}$B$K%9%?%C%/%W%m%;%9$N(B
$B%W%m%0%i%`$r<($9!#$3$N%W%m%0%i%`$GNc$($P=i4|%4!<%k(B{\tt stack(L,R,[])}$B$,(B
$BM?$($i$l$?$H$-!$(Bstack/3$B$KF1Dj$5$l$k$N$O(B{\tt [1][2][3][4][5]}$B$G$"$k!#(B
$B$3$N$&$ANc$($P(B{\tt [2]}$B$rA*Br$9$k$H!$<!4|%4!<%k$O?^(B~\ref{stack}$B$h$j(B
pop/3$B$H(Bstack/3$B$H$J$k!#0J2<F1MM$KF1Dj$,9T$o$l$k!#(B

\begin{figure}[hbtp]
{\tt
[1] stack([push(D)|I],O,S)

~~~~~~:- stack(I,O,[D|S]).

[2] stack([pop|I],O,S)

~~~~~~:- O=[A|NO], pop(A,S,NS),

~~~~~~~~~stack(??,??,??)

[3] stack([pop(N)|I],O,S)

~~~~~~:- O=[L|NO], pop(N,L,S,NS),

~~~~~~~~~stack(I,NO,NS).

[4] stack([reverse(N)|I],O,S)

~~~~~~:- O=[L|NO], rev:rev(R,L),

~~~~~~~~~pop(N,R,S,NS), stack(I,NO,NS).

[5] stack([],O,\_) :- O=[].

[6] pop(A,[X|S],NS) :- A=answer(X)

~~~~~~~~~~~~~~~~~~~~~~~NS=S.

[7] pop(A,[],NS) :- A=empty, NS=[].

[8] pop(N,L,S,OS)

~~~~~~:- N>0

~~~~~~~~~| L=[X|NL], pop(X,S,NS),

~~~~~~~~~~~NN:=N-1, pop(NN,NL,NS,OS).

[9] pop(0,L,S,OS) :- L=[], OS=S.}
\caption{$B%9%?%C%/%W%m%;%9$N%W%m%0%i%`(B}
\label{stack}
\end{figure}

\subsection{$B%G!<%?9=B$(B}
KL1$B$N%G!<%?NN0h$O!$%;%k$H8F$P$l$k:G>.C10L$G4IM}$5$l$k!#%G!<%?7?$K$O(B
$BC10l$N%;%k$GCM$rD>@\3JG<$9$k(Batom$B7?$d(Binteger$B7?!#J#?t$N%;%k$+$i@.$j!$JL$N(B
$B%G!<%?$KBP$9$k;2>H%]%$%s%?$r3JG<$9$k(Bfunctor$B7?$d(Blist$B7?!#B>$N%;%k$X$N;2>H(B
$B%]%$%s%?$G$"$k(Breference$B7?$J$I$,$"$k!#(BKL1$B$NJQ?t$O$3$N;2>H%]%$%s%?$GI=8=$5$l!$(B
$BCM$K4X$7$F$OFCDj$N7?$r;}$?$J$$!#=i4|>uBV$G$OL$6qBN2=$G$"$jCM$r;}$?$J$$$,!$(B
$BF10l2=$K$h$jBP>]$X$N%]%$%s%?$,3JG<$5$l$k!#6qBNCM$H$NF10l2=(B($B$3$l$r6qBN2=(B
$B$H8F$V(B)$B$,9T$o$l$k$H6qBNCM$X$N%]%$%s%?$,3JG<$5$l!$0J8e$3$NJQ?t$r;2>H$9$k$H(B
$B6qBNCM$rFI$_=P$9$3$H$,$G$-$k!#0lEY6qBN2=$5$l$?JQ?t$O!$B>$NCM$K=q$-49$($k(B
$B$3$H$O$G$-$J$$!#(B

\subsection{KL1$B=hM}7O(BKLIC}
KLIC$B$O(BICOT$B$G3+H/$,?J$a$i$l$F$$$k(BKL1$B$N=hM}7O$G$"$k(B\footnote{1994$BG/8=:_!#(B}$B!#(B
$B$3$l$O(BKL1$B%W%m%0%i%`$r0lC6(BC$B%W%m%0%i%`$KJQ49$7!$%*%V%8%'%/%H%3!<%I@8@.(B
$B$O(BC$B%3%s%Q%$%i$K9T$o$;$kJ}K!$r$H$C$F$$$k!#$h$C$F0\?"@-$N9b$$=hM}7O$H$J$C$F$$$k!#(B

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{thebibliography}{9}
\item
$B5\B<(B $B7.(B. $BJBNs=hM}8@8l(B.
$B%^%0%m%&%R%k(B, 1986.

\item
$BBgLn(B $BOBI'$[$+(B. $B@EE*2r@O$K$h$kJBNsO@M}7?8@8l$N<B9T:GE,2=(B.
1994.

\item
$BBgLn(B $BOBI'(B,$B0K@n(B $B2mI'$[$+(B. $BJBNsO@M}7?8@8l(BKL1$B$N:GE,2=<jK!(B.
1994.

\item
$BDEED(B $B9'IW$[$+(B. $B8=Be%*%Z%l!<%F%#%s%0%7%9%F%`$N4pAC(B.
$B%*!<%`<R(B, 1988.
\end{thebibliography}

\end{document}

















