【原创】批处理并发编程：浅谈锁的实现
数据竞争：我们为什么需要锁？
由变量递增引发的血案
pushd "%temp%"
for %%i in (inc10*) do del /f /q %%i 2>nul
:: 读取、相加、写回
(
echo @echo off
echo set /a times = 1
echo :loop
echo.
echo :retry1
echo ^( set /p n=^<share_var ^) 2^>nul ^|^| goto retry1
echo set /a n += 1
echo :retry2
echo ^( echo %%n%% ^>share_var ^) 2^>nul ^|^| goto retry2
echo.
echo if %%times%% lss 10 ^(
echo set /a times += 1
echo goto loop
echo ^)
echo exit /b
)>inc10.cmd
rem type inc10.cmd
串行：世界在我掌控
pushd "%temp%"
echo 0 >share_var
call inc10.cmd
call inc10.cmd
type share_var
20
并行：当潘多拉的魔盒打开
pushd "%temp%"
echo 0 >share_var
for /f "delims=" %%i in ('start /b "" cmd /c "inc10.cmd" ^& start /b "" cmd /c "inc10.cmd"') do (cd .)
type share_var
12
原因？
下面是一种可能的情形。
线程1 读取n
线程2 读取n
线程1 写回n+1
线程2 写回n+1
导致尽管进行了两次递增，变量却只增大了1。
锁与原子性：解决之道
原子性：不可拆分
一个或者多个操作在 CPU 执行的过程中不被中断的特性称为原子性。
若我们的递增操作具有原子性：
线程1 递增 n 至 n + 1
线程2 递增 n + 1 至 n + 2
我们就避免了数据竞争。
Peterson 算法：两个线程的锁实现
考虑如下协议：
A 或 B 想如厕时，首先举起自己手中的旗子，代表自己有如厕的意愿。
向厕所门上张贴对方的名字，请对方先上。
观察，若对方不想如厕（旗子未举起）、或门上的名字是自己，那么进入如厕。
如厕完成后放下旗子。
pushd "%temp%"
for %%i in (inc10*) do del /f /q %%i 2>nul
call :save inc10_A.cmd A B
call :save inc10_B.cmd B A
fc inc10_A.cmd inc10_B.cmd
goto :eof
:save <filename> <self> <another>
set "filename=%1"
set "self=%2"
set "another=%3"
(
echo @echo off
echo set /a times = 1
echo :loop
echo rem 获取锁
echo cd . ^> flag%self%
echo :retag
echo ^(echo %another%^>tag^) 2^>nul || goto retag
echo :check
echo if not exist flag%another% goto pass
echo ^( set /p tag=^<tag ^) 2^>nul || goto check
echo if "%%tag%%" == "%self%" goto pass
echo goto check
echo :pass
echo.
echo rem 临界区
echo :retry1
echo ^( set /p n=^<share_var ^) 2^>nul ^|^| goto retry1
echo set /a n += 1
echo :retry2
echo ^( echo %%n%% ^>share_var ^) 2^>nul ^|^| goto retry2
echo.
echo rem 释放锁
echo :retry_free_lock
echo ^( del /f /q flag%self% ^) 2^>nul ^|^| goto retry_free_lock
echo if %%times%% lss 10 ^(
echo set /a times += 1
echo goto loop
echo ^)
echo exit /b
)>%filename%
goto :eof
正在比较文件 inc10_A.cmd 和 INC10_B.CMD
***** inc10_A.cmd
rem 获取锁
cd . > flagA
:retag
(echo B>tag) 2>nul
:check
if not exist flagB goto pass
( set /p tag=<tag ) 2>nul
if "%tag%" == "A" goto pass
goto check
***** INC10_B.CMD
rem 获取锁
cd . > flagB
:retag
(echo A>tag) 2>nul
:check
if not exist flagA goto pass
( set /p tag=<tag ) 2>nul
if "%tag%" == "B" goto pass
goto check
*****
***** inc10_A.cmd
:retry_free_lock
( del /f /q flagA ) 2>nul || goto retry_free_lock
if %times% lss 10 (
***** INC10_B.CMD
:retry_free_lock
( del /f /q flagB ) 2>nul || goto retry_free_lock
if %times% lss 10 (
*****
pushd "%temp%"
del /f /q flagA flagB tag 2>nul
echo 0 >share_var
for /f "delims=" %%i in ('start /b "" cmd /c "inc10_A.cmd" ^& start /b "" cmd /c "inc10_B.cmd"') do (cd .)
type share_var
20
Filter 算法：当 Peterson 算法拓展到 N 个线程
考虑如下协议：
目前有至多 N 位等待如厕。
坑位只有一个。
设置从左到右 N - 1 个等待位（每个等待位可容纳多人）。
每个等待位上有一个牌子，写着：后来者之牌。
对于每位等待者，从最左边的等待位开始。
将等待位牌子上的名字换成自己的。
观察，若牌子上的名字还是自己，并且有人在和自己相同或更右边的等待位上，继续等待。
否则向右移动一个等待位。
若不能继续向右移动，
那么开始如厕（此时他人看来还保持在最右侧的等待位）。
如厕完成后离开最右侧的等待位。
pushd "%temp%"
for %%i in (inc10*) do del /f /q %%i 2>nul
set N=10
for /l %%i in (1 1 %N%) do (
call :save inc10_%%i.cmd %%i %N%
)
goto :eof
:save <file_name> <self_id> <N>
set "filename=%1"
set "self=%2"
set "N=%3"
(
echo @echo off
echo set /a times = 1
echo :loop
echo rem 获取锁
echo setlocal ENABLEDELAYEDEXPANSION
echo for /l %%%%i in ^( 1 1 %N% ^) do ^(
echo call :write_var standing_%self% %%%%i
echo call :write_var last_wait_%%%%i %self%
echo call :wait %%%%i
echo ^)
echo goto pass
echo :wait ^<level^>
echo set "level=%%1"
echo call :read_var "last_wait_^!level^!"
echo if not "^!re^!" == "%self%" goto :eof
echo set continue_wait=
echo for /l %%%%i in ^( 1 1 %N% ^) do ^(
echo title Thread: %self% level: "^!level^!" check: %%%%i
echo if not "%%%%i" == "%self%" ^(
echo call :test_read_var standing_%%%%i -1
echo set /a is_bigger = re - level
echo for /f "delims=" %%%%j in ^("^!is_bigger^!"^) do if %%%%j geq 0 ^(
echo set continue_wait=t
echo ^)
echo ^)
echo ^)
echo if defined continue_wait ^(
echo goto wait
echo ^) else ^(
echo goto :eof
echo ^)
echo :pass
echo.
echo rem 临界区
echo :retry1
echo ^( set /p n=^<share_var ^) 2^>nul ^|^| goto retry1
echo set /a n += 1
echo :retry2
echo ^( echo %%n%% ^>share_var ^) 2^>nul ^|^| goto retry2
echo.
echo rem 释放锁
echo :retry_free_lock
echo ^( del /f /q standing_%self% ^) 2^>nul ^|^| goto retry_free_lock
echo if %%times%% lss 10 ^(
echo set /a times += 1
echo goto loop
echo ^)
echo exit /b
echo :read_var ^<var_name^>
echo ^( set /p re=^<%%1 ^) 2^>nul ^|^| goto read_var
echo goto :eof
echo.
echo :test_read_var ^<var_name^> ^<default^>
echo ^( set /p re=^<%%1 ^) 2^>nul ^|^| set re=%%2
echo goto :eof
echo.
echo :write_var ^<var_name^> ^<value^>
echo ^( ^>%%1 echo %%2^) 2^>nul ^|^| goto write_var
echo goto :eof
echo.
)>%filename%
goto :eof
set N=10
pushd "%temp%"
echo 0 >share_var
for %%i in (standing_*) do del /f /q %%i 2>nul
for %%i in (last_wait_*) do del /f /q %%i 2>nul
for /l %%i in (1 1 %N%) do (
call inc10_%%i.cmd
)
type share_var
100
set N=10
pushd "%temp%"
echo 0 >share_var
for %%i in (standing_*) do del /f /q %%i 2>nul
for %%i in (last_wait_*) do del /f /q %%i 2>nul
setlocal ENABLEDELAYEDEXPANSION
set cmd=cd .
for /l %%i in (1 1 %N%) do (
set "cmd=!cmd! ^& start /b "" cmd /c "inc10_%%i.cmd""
)
for /f "delims=" %%i in ('!cmd!') do (cd .)
type share_var
100
文件移动：一种基于文件系统特性的自旋锁
考虑如下协议：
有若干人需要如厕，但钥匙只有一把。
所有人争抢钥匙，抢到钥匙的人如厕，如厕完成后将钥匙放回。
pushd "%temp%"
for %%i in (inc10*) do del /f /q %%i 2>nul
set N=10
for /l %%i in (1 1 %N%) do (
call :save inc10_%%i.cmd %%i
)
goto :eof
:save <file_name> <self_id>
set "filename=%1"
set "self=%2"
(
echo @echo off
echo set /a times = 1
echo :loop
echo rem 获取锁
echo :get_lock
echo move key hold_key_%self% 2^>nul ^>nul
echo if not exist hold_key_%self% goto get_lock
echo :pass
echo.
echo rem 临界区
echo :retry1
echo ^( set /p n=^<share_var ^) 2^>nul ^|^| goto retry1
echo set /a n += 1
echo :retry2
echo ^( echo %%n%% ^>share_var ^) 2^>nul ^|^| goto retry2
echo.
echo rem 释放锁
echo :retry_free_lock
echo ^( move hold_key_%self% key ^) 2^>nul ^>nul ^|^| goto retry_free_lock
echo if %%times%% lss 10 ^(
echo set /a times += 1
echo goto loop
echo ^)
)>%filename%
goto :eof
pushd "%temp%"
echo 0 >share_var
cd . >key
for %%i in (hold_key_*) do del /f /q %%i 2>nul
set N=10
for /l %%i in (1 1 %N%) do (
call inc10_%%i.cmd
)
type share_var
100
pushd "%temp%"
echo 0 >share_var
cd . >key
for %%i in (hold_key_*) do del /f /q %%i 2>nul
setlocal ENABLEDELAYEDEXPANSION
set cmd=cd .
set N=10
for /l %%i in (1 1 %N%) do (
set "cmd=!cmd! ^& start /b "" cmd /c "inc10_%%i.cmd""
)
for /f "delims=" %%i in ('!cmd!') do (cd .)
type share_var
100
其它
本文章由 Jupyter Notebook 及 iBatch Kernel 强力驱动。