哲学家进餐问题是一个经典的计算机科学教科书问题,用于演示多线程的使用。正如维基百科所说:
五个沉默的哲学家坐在一张圆桌旁,桌上放着几碗意大利面条。叉子被放置在每对相邻的哲学家之间。
每个哲学家都必须交替思考和进食。然而,一个哲学家只有在有左右叉子的情况下才能吃意大利面。每把叉子只能由一位哲学家持有,因此只有在另一位哲学家没有使用叉子的情况下,一位哲学家才能使用叉子。当一个哲学家吃完后,他们需要放下两个叉子,这样其他人就可以使用叉子了。哲学家只能在有叉子的时候拿右边的叉子或左边的叉子,而且他们不能在两个叉子都拿出来之前就开始吃饭。
进食不受剩余的意大利面或胃空间的限制;假设无限供给和无限需求。
问题是如何设计一种行为准则(并行算法),使哲学家不会挨饿;i、 例如,每个人都可以永远在饮食和思考之间交替,假设没有一个哲学家知道别人什么时候想吃东西或思考。
该问题旨在说明避免死锁的挑战,死锁是一种无法取得进展的系统状态。
总之,这是多线程中的一个经典问题,证明了使用互斥原则避免资源短缺的必要性。
我想在实时模式DOS中实现这样一个程序,但是DOS显然缺乏多线程功能。
我知道有第三方软件,比如RTKernel,但在这种情况下,这似乎有些过头了。
有没有什么方法可以模拟多线程,这样我就可以用16位x86汇编语言在DOS中编写一个关于哲学家进餐问题的模拟程序?
多线程是关于创建程序中多个执行路径同时运行的幻觉。在今天的多核计算机上,如果线程数量保持在限制范围内,这不再是一种幻觉。
在抢占式多任务模型中,时间片耗尽会触发线程切换。该开关从运行线程的外部启动
在我编写的多线程模块中,如果没有运行线程的批准和协作,则无法进行切换。正是运行中的线程决定了切换可以在何处发生,而不是何时发生。为此,程序员必须在线程中策略性选择的位置向函数maybeyeldthread插入call
s。循环是实现这一点的好地方。如果在这样一个调用的时刻,时间片还没有过去,那么调用将立即返回。如果时间片已过,则MaybeyeldThread会立即像真正的YieldThread一样运行,并发生切换。
这种方法的主要优点是,它可以避免许多通常使用同步对象(如互斥体、信号量或关键部分)的竞争条件。在线程安全的位置插入调用maybeyeldthread
指令,就这样!
多线程功能编码在单个源文件模块中。INC,您可以将其包含在应用程序中的任意位置。
我建议的api是一个小的,但我相信它提供了DOS程序可能需要的所有多线程功能...在某个时刻,我实现了线程句柄、线程优先级和线程间通信等功能。回想起来,记住“少即是多”这句话,我很高兴我删除了所有这些。
这一切都始于对开始会话线程的调用
。您定义了会话内存的边界,所有线程的堆栈都将放置在那里,您定义了要使用的时间片,如果没有遇到错误,您将指向第一个立即接收控件的线程。
第一个线程将要做的事情之一是使用CreateThread创建其他线程。您提供的是另一个线程的代码地址以及希望用于其堆栈的内存量。
一旦线程启动并运行,它们就可以使用YieldThread放弃控制以支持下一个线程,当且仅当它们运行的时间片已过时,使用maybeyeldthread放弃控制,并使用SleepThread放弃控制并从调度中移除自己,直到请求的持续时间结束。
如果一个线程已经超过了它的目的,一个调用
(或jmp
)到ExitThread或一个仅仅的ret
指令(当然是从一个平衡的堆栈!)从调度程序中永久删除线程,并将其堆栈占用的内存返回到空闲会话内存池。
当不再需要多线程时,对EndSessionRead的调用(或
指令)。可以传递exitcodejmp
)会将控制权返回到会话启动位置正下方的指令(调用BeginSessionThread
或者,从最后一个活动线程退出也将结束会话,但在这种情况下,exitcode将为零。
为了挂起多线程会话,可以调用StopSessionRead。它会将计时器频率重置为标准18.2 Hz,并冻结所有等待的睡眠时间。要恢复多线程会话,只需调用ContSessionThread即可。暂停会话是在不干扰睡眠时间的情况下暂时暂停程序的一种方法。如果要执行子程序,甚至要启动嵌套的多线程会话,必须挂起当前会话才能成功。
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个字节供mtMoules使用。
为了获得最佳的抢占性,您不应该过于稀疏地使用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:
; --------------------------------------
问题内容: 假设我有以下代码: 这段代码的问题在于,协程内部的循环永远不会完成第一次迭代,而大小会不断增加。 为什么会这样发生,我该怎么解决? 我无法摆脱单独的线程,因为在我的真实代码中,我使用了单独的线程与串行设备进行通信,而且我还没有找到使用的方法。 问题答案: 不是线程安全的,因此您不能直接在多个线程中直接使用它。相反,您可以使用,它是提供线程感知队列的第三方库: 还有(全披露:我写了它),
我正在努力解决这个问题。 就我而言,每个哲学家都应该吃100万次。问题是好像只有“1”,是“3”吃完了。我使用的线程与关键部分锁定,这是我的代码: 每个哲学家都必须交替思考和进食。然而,一个哲学家只有在有左右叉子的情况下才能吃意大利面。每把叉子只能由一位哲学家持有,因此只有在另一位哲学家没有使用叉子的情况下,一位哲学家才能使用叉子
问题内容: 我希望能够在一个程序包中编写一个Java类,该程序包可以访问另一个程序包中某个类的非公共方法,而不必使其成为另一个类的子类。这可能吗? 问题答案: 这是我在JAVA中用来复制朋友机制的一个小技巧。 可以说我有一节课和另外一节课。由于仇恨原因,他们处于不同的包裹(家庭)中。 想要并且只想让她。 在中,将声明Romeo为(情人),friend但是在Java中没有这样的东西。 这是类和技巧:
我们可以使用这些jvm标志来确定编译阈值,但是有没有一种方法可以在运行时以编程方式确定它?
简而言之:有没有一种方法可以在gcc或CLANG中不推荐命名空间? 长: 现在我想知道是否有更好的方法来做类似的事情,比如将名称空间util的使用标记为不推荐使用。 我们使用GCC4.7.3作为生产编译器,但是针对clang进行构建和测试,以尝试捕捉gcc的细节;因此,在这些编译器上工作的东西会有所帮助。
问题内容: 嗨,我想使用WMI类来查找应用程序和产品信息。但是问题是我想使用Java或任何脚本语言(如python,javascript或perl)。我听说过JWMI,这可能是一个选择。有人可以帮我吗??? 问题答案: JavaScript和Java不是一回事。 JavaScript Windows脚本宿主(WSH)下提供了JavaScript。有了它,访问WMI相当容易: jWMI(Java)