有没有办法在 DOS 中模拟多线程，例如，在解决哲学家就餐的问题时？
Sep*_*and 1 x86 assembly multithreading dos dining-philosopher
哲学家进餐问题是一个经典的计算机科学教科书问题，用于演示多线程的使用。正如维基百科所说：
五位沉默的哲学家端着一碗意大利面坐在圆桌旁。叉子放在每对相邻的哲学家之间。
每个哲学家都必须交替思考和进食。但是，哲学家只有在左叉和右叉同时拥有时才能吃意大利面。每个叉子只能由一个哲学家持有，因此只有当叉子没有被其他哲学家使用时，哲学家才能使用它。在一个哲学家吃完饭后，他们需要放下两个叉子，以便其他人可以使用这些叉子。哲学家只能在有可用的时候拿走他们右边或左边的叉子，并且在拿到两把叉子之前他们不能开始吃饭。
进食不受剩余意大利面条或胃空间的限制；假设无限供给和无限需求。
问题是如何设计行为准则（并发算法），使哲学家不会挨饿；即，每个人都可以永远继续在吃饭和思考之间交替，假设没有哲学家可以知道其他人什么时候想吃饭或思考。
该问题旨在说明避免死锁的挑战，死锁是一种不可能取得进展的系统状态。
总之，这是多线程中的一个经典问题，表明需要使用互斥原则来避免资源匮乏。
我想在实模式 DOS 中实现这样的程序，但是 DOS 显然缺乏多线程功能。
我知道第三方软件，例如RTKernel，但这对于这种情况似乎有点过分。
是否有任何模拟多线程的解决方案，以便我可以使用 16 位 x86 汇编语言在 DOS 中对哲学家进餐问题的模拟进行编程？
多线程是关于创建程序中多个执行路径同时运行的错觉。在今天的多核计算机上，如果线程数保持在限制范围内，这不再是一种幻觉。
多线程的另一条道路
在抢占式多任务模型中，时间片用完会触发线程切换。切换是从正在运行的线程外部启动的。
在我写的多线程模块中，没有运行线程的批准和协作，切换是不可能发生的。正在运行的线程决定了可以在何处而不是何时进行切换。为此，程序员必须在线程中战略性选择的位置将calls插入到函数MaybeYieldThread中。循环是这样做的好地方。如果在进行此类调用时，时间片尚未过去，则调用将立即返回。如果时间片已经过去，那么MaybeYieldThread 会暂时像一个真实的YieldThread和切换发生。
这种方法的主要优点是它可以避免许多您通常使用同步对象（如互斥锁、信号量或临界区）来解决的竞争条件。您将call MaybeYieldThread指令插入线程安全的地方，就是这样！
主要特点
多线程功能编码在单个源文件mtModule.INC 中，您可以将其包含在您喜欢的应用程序中的任何位置。
- 占地面积小。包含文件少于 600 个字节。
- 非常快。线程切换器很便宜。
- 广泛的允许堆栈大小。它们的范围可以从 128 到 65536 字节，以 16 字节为增量。
- 最佳内存使用。很少的开销和合并空闲块的分配器。
- 可选择的时间片。时间片的范围可以从 1 到 55 毫秒。（55 使用标准 54.925494 毫秒）
- 循环调度程序。
- 只是几个，易于使用的功能。
- 非常慷慨的参数传递方案。每个未被 api 本身用作 arg 的（整数）寄存器确实是线程第一次调用时的参数。
api说明
我提议的 api 很小，但我相信它提供了 DOS 程序可能需要的所有多线程功能......在某个时候我已经实现了诸如线程句柄、线程优先级和线程间通信等功能。回顾并记住“少即是多”这句话，我很高兴我删除了所有这些。
这一切都从一个callto BeginSessionThread开始。您定义会话内存的边界，所有线程的堆栈将放置在其中，您定义要使用的时间片，并指向第一个在没有遇到错误时立即接收控制权的线程。
第一个线程要做的事情之一是使用CreateThread创建其他线程。您提供的是另一个线程的代码地址以及您希望用于其堆栈的内存量。
一旦线程是启动和运行，他们可以使用YieldThread放弃控制权有利于下一个线程的，使用MaybeYieldThread放弃控制权，当且仅当它们在运行时间片已经过去，并使用SleepThread放弃控制并从计划中删除自己，直到请求的持续时间结束。
如果一个线程已经超出了它的目的，一个call（或jmp）到ExitThread或一个单纯的ret指令（当然来自平衡堆栈！）从调度程序中永久删除线程并将其堆栈占用的内存返回到空闲会话内存池.
当不再需要多线程时，EndSessionThread的call(或jmp)会将控制权返回到会话开始处（指令）正下方的指令。可以传递退出代码。
或者，从最后一个活动线程退出也将结束会话，但在这种情况下，退出代码将为零。call BeginSessionThread
为了暂停多线程会话，您可以调用StopSessionThread。它将定时器频率重置为标准 18.2 Hz 并冻结所有未决睡眠时间。要恢复多线程会话，只需要一个callto ContSessionThread。暂停会话是在不干扰睡眠时间的情况下暂时暂停程序的一种方法。如果您想执行子程序甚至启动嵌套多线程会话，则必须暂停当前会话才能成功。
api 快速参考
BeginSessionThread
Input
BX timeslice in milliseconds [1,55]
CX requested stacksize for first thread
DX near address of first thread
SI para address begin session memory
DI para address end session memory
-- everything else is user defined parameter
Output
CF=0 Session has ended, AX is SessionExitcode
CF=1 'Insufficient memory'
'Invalid stacksize'
'Invalid timeslice'
--------------------------------------
CreateThread
Input
CX requested stacksize for thread
DX near address of thread
-- everything else is user defined parameter
Output
CF=0 OK
CF=1 'Invalid stacksize'
'Out of memory'
--------------------------------------
SleepThread
Input
CX is requested duration in milliseconds
Output
none
--------------------------------------
MaybeYieldThread
Input
none
Output
none
--------------------------------------
YieldThread
Input
none
Output
none
--------------------------------------
ExitThread
Input
none
Output
none
--------------------------------------
EndSessionThread
Input
CX is SessionExitcode
Output
none
--------------------------------------
StopSessionThread
Input
none
Output
none
--------------------------------------
ContSessionThread
Input
none
Output
none
--------------------------------------
一些兴趣点
线程必须不更改SS段寄存器并且在堆栈上留下大约 80 个字节以供mtModule.INC使用。
为了获得最佳的“抢占性”，您不应过于稀疏地使用MaybeYieldThread。另一方面，出于效率原因，您可能不应该在紧密循环中使用MaybeYieldThread。
; mtModule.INC Multithreading in DOS (c) 2020 Sep Roland
; ------------------------------------------------------
; assemble with FASM, compatible with CMD and DOSBox
; Functions:
; BeginSessionThread(BX,CX,DX,SI,DI,..) -> AX CF
; CreateThread(CX,DX,..) -> CF
; SleepThread(CX)
; MaybeYieldThread()
; YieldThread()
; ExitThread()
; EndSessionThread(CX)
; StopSessionThread()
; ContSessionThread()
; Session header:
; +0 wSessionHighMem
; +2 wSessionNumberOfThreads
; +4 dwSessionParentStackptr
; +8 wSessionTickVarStep
; +10 wSessionMicroTimeslice
; +12 wSessionTickVar
; Thread header:
; +0 wThreadLowMem
; +2 wThreadStacksize
; +4 wThreadStatus: DEAD/FREE (-1), AWAKE (0), ASLEEP (1+)
; +6 wThreadStackptr
; --------------------------------------
; IN (bx=0,cx,dx,ss:si,fs) OUT (ax,CF) MOD (cx,si,di,bp,ds,es)
mtAlloc:cmp cx, 4096 ; Max 64KB stack
ja .NOK
cmp cx, 8 ; Min 128 bytes stack
jb .NOK
; Find a free alloc that is big enough
mov ax, fs
inc ax ; Skipping session header
.a: mov ds, ax
cmp [bx+4], bx ; ThreadStatus
jge .b ; Is occupied
mov bp, [bx+2] ; ThreadStacksize (size of free alloc)
sub bp, cx
jae .OK
.b: add ax, [bx+2] ; ThreadStacksize
cmp ax, [fs:bx] ; SessionHighMem
jb .a
.NOK: stc
ret
.OK: je .c ; Tight fit, no split up
; Init header of a free alloc
add ax, cx
mov ds, ax
mov [bx], fs ; ThreadLowMem
mov [bx+2], bp ; ThreadStacksize
mov word [bx+4], -1 ; ThreadStatus = FREE
sub ax, cx
mov ds, ax
; Init thread header
.c: mov [bx], fs ; ThreadLowMem
mov [bx+2], cx ; ThreadStacksize
mov [bx+4], bx ; ThreadStatus = AWAKE
imul di, cx, 16 ; -> DI is total stacksize in bytes
sub di, (32+8+4)+2+2 ; Initial items that go on this stack
mov [bx+6], di ; ThreadStackptr
; Init thread stack
mov es, ax
mov cx, (32+8+4)/2 ; GPRs, SRegs, EFlags
cld
rep movs word [di], [ss:si]
mov [di], dx ; ThreadAddress
mov word [di+2], ExitThread
inc word [fs:bx+2] ; SessionNumberOfThreads
clc
ret
; --------------------------------------
; IN (bx,cx,dx,si,di,..) OUT (ax,CF)
; BX timeslice in milliseconds [1,55] (55 uses standard 54.925494 msec)
; CX requested stacksize for first thread, DX near address of first thread
; SI para address begin session memory, DI para address end session memory
;
; CF=0 Session has ended, AX is SessionExitcode
; CF=1 'Insufficient memory' or 'Invalid stacksize' or 'Invalid timeslice'
BeginSessionThread:
pushfd ; '..' Every register is considered
push ds es fs gs ; parameter on the first invocation
pushad ; of the thread
; Test parameters
mov bp, di ; SessionHighMem
sub bp, si ; ThreadLowMem
jbe mtFail
dec bp
jz mtFail
dec bx ; Timeslice in msec
cmp bx, 55
jnb mtFail
inc bx
; Turn MilliTimeslice BX into TickVarStep AX and MicroTimeslice CX
mov ax, 65535 ; Standard step is 'chain always'
mov cx, 54925 ; Standard slice is 54925.494 microsec
cmp bx, 55
je .a
push dx ; (1)
mov ax, 1193180 Mod 65536 ; TickVarStep = (1193180 * BX) / 1000
mul bx ; BX = [1,54]
imul cx, bx, 1193180/65536
add dx, cx
mov cx, 1000
div cx ; -> AX = {1193, 2386, ..., 64431}
imul cx, bx ; -> CX = {1000, 2000, ..., 54000}
pop dx ; (1)
; Init session header
.a: xor bx, bx ; CONST
mov ds, si ; -> DS = Session header
mov [bx], di ; SessionHighMem
mov [bx+2], bx ; SessionNumberOfThreads = 0
mov [bx+4], sp ; SessionParentStackptr
mov [bx+6], ss
mov [bx+8], ax ; SessionTickVarStep
mov [bx+10], cx ; SessionMicroTimeslice
;;mov [bx+12], bx ; SessionTickVar = 0
; Init header of a free alloc
mov [bx+16], ds ; ThreadLowMem
mov [bx+18], bp ; ThreadStacksize, all of the session
mov word [bx+20], -1 ; ThreadStatus = FREE memory
; Create first thread
mov fs, si ; ThreadLowMem -> FS = Session header
mov si, sp ; -> SS:SI = Initial registers
mov cx, [ss:si+24] ; pushad.CX
call mtAlloc ; -> AX CF (CX SI DI BP DS ES)
jc mtFail
mov [cs:mtTick+5], fs ; ThreadLowMem
mov [cs:mtChain+3], cs ; Patch far pointer
call mtSwap ; Hook vector 08h/1Ch
jmp mtCont
; --------------------------------------
; IN (ss:sp)
mtFail: popad ; Return with all registers preserved
pop gs fs es ds ; to caller
popfd
stc
ret
; --------------------------------------
; IN (cx,dx,..) OUT (CF)
; CX requested stacksize for thread, DX near address of thread
;
; CF=0 OK
; CF=1 'Invalid stacksize' or 'Out of memory'
CreateThread:
pushfd ; '..' Every register is considered
push ds es fs gs ; parameter on the first invocation
pushad ; of the thread
xor bx, bx ; CONST
mov fs, [ss:bx] ; ThreadLowMem -> FS = Session header
mov si, sp ; -> SS:SI = Initial registers
; Coalescing free blocks
mov ax, fs
inc ax
.a: mov ds, ax ; -> DS = Thread header
mov bp, [bx+2] ; ThreadStacksize
cmp [bx+4], bx ; ThreadStatus
jge .c ; Is occupied
mov es, ax
.b: add ax, bp ; BP is size of a free alloc
cmp ax, [fs:bx] ; SessionHighMem
jnb .d
mov ds, ax
mov bp, [bx+2] ; ThreadStacksize
cmp [bx+4], bx ; ThreadStatus
jge .c
add [es:bx+2], bp ; ThreadStacksize, BP is size of
jmp .b ; the free alloc that follows
.c: add ax, bp ; BP is size of an actual thread stack
cmp ax, [fs:bx] ; SessionHighMem
jb .a
.d: call mtAlloc ; -> AX CF (CX SI DI BP DS ES)
jc mtFail
; --- --- --- --- --- --- --
; IN (ss:sp)
mtFine: popad ; Return with all registers preserved
pop gs fs es ds ; to caller
popfd
clc
ret
; --------------------------------------
; IN (cx) OUT ()
; CX is requested duration in msec
SleepThread:
pushf
pusha
push ds
xor bx, bx ; CONST
mov ds, [ss:bx] ; ThreadLowMem -> DS = Session header
mov ax, 1000 ; TICKS = (CX * 1000) / MicroTimeslice
mul cx
mov cx, [bx+10] ; SessionMicroTimeslice
shr cx, 1 ; Rounding to nearest
adc ax, cx
adc dx, bx
div word [bx+10] ; SessionMicroTimeslice
mov [ss:bx+4], ax ; ThreadStatus = TICKS
pop ds
popa
popf
jmp YieldThread
; --------------------------------------
mtTick: push ds ; 1. Decrement all sleep counters
pusha
xor bx, bx ; CONST
mov ax, 0 ; SMC Start of session memory
mov ds, ax ; ThreadLowMem -> DS = Session header
mov cx, [bx+8] ; SessionTickVarStep
stc
adc [bx+12], cx ; SessionTickVar
pushf ; (1)
mov dx, [bx] ; SessionHighMem
inc ax
.a: mov ds, ax ; -> DS = Thread header
mov cx, [bx+4] ; ThreadStatus
dec cx
js .b ; AX was [-1,0], ergo not ASLEEP
mov [bx+4], cx ; ThreadStatus
.b: add ax, [bx+2] ; ThreadStacksize -> End current stack
cmp ax, dx
jb .a
mov byte [cs:$+23], 90h ; 2. Turn 'MaybeYield' into 'Yield'
popf ; (1)
popa
pop ds
jc mtChain
push ax
mov al, 20h
out 20h, al
pop ax
iret
mtChain:jmp far 0:mtTick ; 3. Chain to original vector 08h/1Ch
; --------------------------------------
; IN () OUT ()
MaybeYieldThread:
ret ; SMC {90h=nop,C3h=ret}
; --- --- --- --- --- --- --
; IN () OUT ()
YieldThread:
mov byte [cs:$-1], 0C3h ; Back to 'MaybeYield'
pushfd ; Save context current thread
push ds es fs gs
pushad
xor bx, bx ; CONST
mov ax, ss ; Begin current stack
mov ds, ax ; -> DS = Thread header
mov [bx+6], sp ; ThreadStackptr
mov fs, [bx] ; ThreadLowMem -> FS = Session header
sti ; Guard against every thread ASLEEP!
.a: add ax, [bx+2] ; ThreadStacksize -> End current stack
cmp ax, [fs:bx] ; SessionHighMem
jb .b
mov ax, fs ; Session header
inc ax ; Stack lowest thread
.b: mov ds, ax
cmp [bx+4], bx ; ThreadStatus
jne .a ; Is DEAD/FREE (-1) or ASLEEP (1+)
; --- --- --- --- --- --- --
; IN (ax,bx=0)
mtCont: mov ss, ax
mov sp, [ss:bx+6] ; ThreadStackptr
popad ; Restore context new current thread
pop gs fs es ds
popfd
ret
; --------------------------------------
; IN () OUT ()
ExitThread:
xor bx, bx ; CONST
dec word [ss:bx+4] ; ThreadStatus = DEAD/FREE
mov ds, [ss:bx] ; ThreadLowMem -> DS = Session header
dec word [bx+2] ; SessionNumberOfThreads
jnz YieldThread ; Not exiting from the sole thread
xor cx, cx ; SessionExitcode
; --- --- --- --- --- --- --
; IN (cx) OUT (ax,CF=0)
EndSessionThread:
call mtSwap ; Unhook vector 08h/1Ch
xor bx, bx ; CONST
mov ds, [ss:bx] ; ThreadLowMem -> DS = Session header
lss sp, [bx+4] ; SessionParentStackptr
mov [esp+28], cx ; pushad.AX, SessionExitcode
jmp mtFine
; --------------------------------------
; IN () OUT ()
StopSessionThread:
ContSessionThread:
push ax
mov ax, [ss:0000h] ; ThreadLowMem -> AX = Session header
mov [cs:mtTick+5], ax ; ThreadLowMem (In case there's been a
pop ax ; nested session)
; --- --- --- --- --- --- --
; IN () OUT ()
mtSwap: push ds
pushad
xor bx, bx ; CONST
mov ds, bx ; -> DS = IVT
mov ax, [046Ch] ; BIOS.Timer
.Wait: cmp ax, [046Ch]
je .Wait
cli
mov ds, [cs:mtTick+5] ; ThreadLowMem -> DS = Session header
mov [bx+12], bx ; SessionTickVar = 0
mov dx, [bx+8] ; SessionTickVarStep
mov ds, bx ; -> DS = IVT
mov bl, 1Ch*4 ; BH=0
inc dx ; SessionTickVarStep
jz .Swap
dec dx
mov bl, 08h*4 ; BH=0
mov ax, cs
cmp [cs:mtChain+3], ax
je .Hook
.Unhook:xor dx, dx
.Hook: mov al, 34h
out 43h, al
mov al, dl
out 40h, al
mov al, dh
out 40h, al
.Swap: mov eax, [bx]
xchg [cs:mtChain+1], eax
mov [bx], eax ; Hook/Unhook vector 08h/1Ch
sti
popad
pop ds
ret
; --------------------------------------
一个示例应用程序
下一个演示程序使用上述 api 中可用的每个函数。它的唯一目的是演示如何使用 api 函数，仅此而已。
尝试不同的时间片很容易，因为您可以在命令行上指定时间片的长度（以毫秒表示）。
该程序在真正的实地址模式和仿真（Windows CMD 和DOSBox）下运行良好。
; mtVersus.ASM Multithreading in DOS (c) 2020 Sep Roland
; ------------------------------------------------------
; assemble with FASM, compatible with CMD and DOSBox
DefaultTimeslice=55 ; [1,55]
ORG 256
mov sp, $
cld
; Was timeslice specified on commandline ?
xor cx, cx ; RequestedTimeslice
mov si, 0081h ; Commandline
Skip: lodsb
cmp al, " "
je Skip
cmp al, 9
je Skip
Digit: sub al, "0"
jb Other
cmp al, 9
ja Other
cbw
imul cx, 10 ; Reasonably ignoring overflow
add cx, ax
lodsb
jmp Digit
Other: mov bx, DefaultTimeslice
cmp cx, 1
jb Setup
cmp cx, 55
ja Setup
mov bx, cx
Setup: mov di, [0002h] ; PSP.NXTGRAF -> end of session memory
lea si, [di-128] ; 2KB session memory (11 threads)
mov dx, Main
mov cx, 8 ; 128 bytes stack
mov bp, MsgCO
call BeginSessionThread ; -> AX CF
jc Exit
mov bp, MsgPE
call BeginSessionThread ; -> AX CF
;;;jc Exit
Exit: mov ax, 4C00h ; DOS.Terminate
int 21h
; --------------------------------------
; IN (bp) ; BP=ModeOfOperation
Main: mov dx, bp ; Displaying title
mov ah, 09h ; DOS.PrintString
int 21h
mov di, EOF ; Preparing output string
mov cx, 79
mov al, " "
rep stosb
m