饮食哲学家的问题是经典的计算机科学教科书问题，用于演示多线程的使用。作为Wikipedia says:
Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers.
Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when they have both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher. After an individual philosopher finishes eating, they need to put down both forks so that the forks become available to others. A philosopher can only take the fork on their right or the one on their left as they become available and they cannot start eating before getting both forks.
Eating is not limited by the remaining amounts of spaghetti or stomach space; an infinite supply and an infinite demand are assumed.
The problem is how to design a discipline of behavior (a concurrent algorithm) such that no philosopher will starve; i.e., each can forever continue to alternate between eating and thinking, assuming that no philosopher can know when others may want to eat or think.
The problem was designed to illustrate the challenges of avoiding deadlock, a system state in which no progress is possible.
总之，这是多线程中的经典问题，表明需要使用互斥原理来避免资源匮乏。
我想在实模式DOS中实现这样的程序，但是DOS显然缺少多线程功能。
我知道像RTKernel这样的第三方软件，但是对于这种情况，这似乎有些过头了。
是否有任何模拟多线程的解决方案，以便我可以使用16位x86汇编语言在DOS中编写对餐饮哲学家问题的模拟？
最佳答案
Multithreading是关于创建一个幻觉，即程序中的多个执行路径会同时运行。在当今的multi-core computers上，如果线程数保持在限制范围内，这不再是一种幻想。
多线程的另一条路
在preemptive multitasking模型中，时间片用尽会触发线程切换。切换从正在运行的线程外部启动。
在我编写的多线程模块中，如果没有运行线程的批准和协作，切换就不会发生。
这是运行线程确定的位置，而不是何时，可以进行切换。为此，程序员必须在线程中策略性选择的位置向函数MaybeYieldThread插入call。循环是实现此目的的好地方。
如果在进行此类调用时，时间片尚未过去，则该调用将立即返回。如果时间片已过去，则MaybeYieldThread会立即充当真正的YieldThread，并进行切换。
这种方法的主要优点是，它可以避免通常使用同步对象(例如互斥体，信号量或关键部分)的许多race conditions。您可以在线程安全的地方插入call MaybeYieldThread指令，仅此而已!
主要特点
多线程功能被编码在单个源文件mtModule.INC中，该文件包含在应用程序中您喜欢的任何位置。
api说明
我提出的api很小，但是我相信它提供了DOS程序可能需要的所有多线程功能。
在某些时候，我实现了诸如线程句柄，线程优先级和线程间通信之类的功能。回顾并牢记“少即是多”的说法，我很高兴我删除了所有这些内容。
一切都以一个BegintThread的
call开头。您定义 session 内存的边界，所有线程堆栈都将放置在该内存中，定义时间片，并指向第一个在没有遇到错误的情况下立即获得控制权的线程。第一个线程将要做的事情之一就是使用CreateThread创建其他线程。您提供的是另一个线程的代码地址以及您希望用于其堆栈的内存量。
一旦线程启动并运行，他们可以使用YieldThread放弃对下一个线程的控制，使用MaybeYieldThread放弃控制，前提是(仅)当它们正在运行的时间片已经过去时，然后使用SleepThread放弃控制并从计划中移开自己，直到请求的持续时间结束为止。
如果线程已超出其目的，则向ExitThread发送
call(或jmp)或仅ret指令(当然是从平衡堆栈中!)将线程从调度程序中永久删除，并将其堆栈占用的内存返回到内存池中。可用的 session 内存。当不再需要多线程时，EndSessionThread的
call(或jmp)将把控制权返回到直接从 session 开始的位置下面的指令(call BeginSessionThread指令)。可以传递一个退出码。或者，从最后一个 Activity 线程退出也将结束 session ，但是在这种情况下，退出码将为零。
为了挂起多线程 session ，可以调用StopSessionThread。它将定时器频率重置为标准的18.2 Hz，并冻结所有未决的SleepTimes。要恢复多线程 session ，只需要向ContSessionThread发送一个
call。暂停 session 是一种在不影响 sleep 时间的情况下临时暂停程序的方法。
而且，如果您要执行子程序甚至启动嵌套的多线程 session ，则必须暂停当前 session 才能成功。
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
mov word [di], 240Dh ; CR and '$'
mov di, EOF+6 ; Creating 10 counting threads
mov dx, Count
mov cx, 8 ; 128 bytes stack
.a: mov byte [di], "0"
call CreateThread ; -> CF
jc EndSessionThread ; CX=8
add di, 8
cmp di, EOF+79
jb .a
mov byte [Flag], 0
mov dx, 10 ; Sleep while counters run (10 sec)
.b: mov cx, 1000
call SleepThread
mov ah, 01h ; BIOS.TestKey
int 16h ; -> AX ZF
jz .c
mov ah, 00h ; BIOS.GetKey
int 16h ; -> AX
call StopSessionThread
mov ah, 00h ; BIOS.GetKey
int 16h ; -> AX
call ContSessionThread
.c: dec dx
jnz .b
not byte [Flag] ; Forces all other threads to exit
call YieldThread
; Exiting from the sole thread == EndSessionThread
mov dl, 10
mov ah, 02h ; DOS.PrintChar
int 21h
ret ; == ExitThread
; --------------------------------------
; IN (di,bp) ; DI=Counter, BP=ModeOfOperation
Count: mov si, di ; Position of the ones in our counter
.a: mov al, [si]
inc al
cmp al, "9"
jbe .b
mov byte [si], "0"
dec si
cmp byte [si], " "
jne .a
mov al, "1"
.b: mov [si], al
mov dx, EOF
mov ah, 09h ; DOS.PrintString
int 21h
cmp bp, MsgPE
je .PE
.CO: call YieldThread
cmp byte [Flag], 0
je Count
jmp ExitThread
.PE: call MaybeYieldThread
cmp byte [Flag], 0
je Count
ret ; == ExitThread
; --------------------------------------
MsgCO: db 13, 10, '10 seconds of cooperative multithreading '
db 'using YieldThread():', 13, 10, '$'
MsgPE: db 13, 10, '10 seconds of preemptive multithreading '
db 'using MaybeYieldThread():', 13, 10, '$'
Flag: db 0
; --------------------------------------
INCLUDE 'mtModule.INC'
; --------------------------------------
EOF:
; --------------------------------------
关于multithreading - 例如，在解决进餐哲学家的问题时，是否有一种方法可以在DOS中模拟多线程？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/63101012/