数据竞争：我们为什么需要锁？

由变量递增引发的血案

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 强力驱动。