Sol–一个阳光灿烂的小虚拟机

2020-06-06 17:42:34

在这个周末和本周早些时候的几个晚上,我创建了一个相当简单的虚拟机,命名为“Sol”,取自瑞典语中“太阳”的意思。我读了很多关于VM设计的书,我对操作系统设计、编程语言和其他围绕计算机作为通用工具的概念的难懂和书呆子的东西很感兴趣。

虚拟机(VM)是像物理机一样执行程序的机器(即计算机)的软件实现。-维基百科。

SOL是在操作系统进程内部运行的进程虚拟机。但是,SOL内部有多个任务(就像大多数操作系统都有进程一样),因此对于在SOL中运行的程序来说,外部世界是什么样子并不重要。我们甚至可以让Sol直接从硬件启动,但那将是疯狂的。请相信我。我以前也走过那条路。

索尔的目的是学习。当我们定义我们的世界时,我们拥有极高的自由度。虚拟机的一个主要组件是提供的指令集。指令是程序可以执行的最简单的操作类型,因此虚拟机提供给在其中运行的程序的指令集需要是通用的和高效的。

在SOLVM中有一个或多个调度器,每个调度器在一个CPU核心上运行(在撰写本文时尚未实现)。

每个调度器维护要运行的任务列表。该列表称为运行队列。调度器还维护I/O监视器、计时器、处理操作系统中断等。调度器在SOL中完成大部分工作,因为它不仅执行我刚才描述的所有那些奇妙的事情,而且还执行程序代码。

运行队列是按任务调度方式排序的任务列表。

如果任务以“End”或“Error”状态结束,则任务将从运行队列…中删除

如果有任何I/O监视器或计时器,请检查计时器是否超时,并可能调用主机操作系统内核来检查挂起的“异步”I/O事件。如果发生了事件(如计时器超时或触发),则相关任务将添加到运行队列中,以便该任务可以读取它正在等待的事件。

调度器重复该过程(例如,从点1开始)。只要运行队列中有任何任务。

正如我们所看到的,任务主要是抽象的,并且只包含一个重要的组件:激活记录。它们包括任务的调用堆栈,并且每个激活记录对应于一个(活动的)函数调用。激活记录包含对它正在执行的函数原型的引用(稍后详细介绍)、程序计数器(通常称为PC),它是当前执行的程序指令的游标,最后是值的注册表。

函数原型是函数的常量和指令,但没有上下文(或“函数闭包”)和局部变量等。函数原型有点像没有任何人或家具的建筑。尽管名称如此,但它并不能真正与蓝图相提并论,因为功能原型不是复制或实现的,而是实际按原样使用的。

程序计数器只是一个数字,它对应于函数原型程序中的偏移量(指令的有序列表)。当执行激活记录(我们可以将其视为一段运行代码)时,程序计数器(PC)随着每条指令的执行而递增。有时,当程序向后跳转(例如,执行循环时)时,PC会递减。PC在基于指令的程序中扮演着中心角色(就像您的计算机或手机的硬件,它现在很可能正在递增PC)。

注册表本质上是执行程序可以用来存储变量数据的临时存储器区域。想象一下这个简单的函数:

def foo(x,y):x=x*5 x=x*y返回x。

在这里,程序需要一种方法来存储由x*5创建的值,然后它可以将该值传递给x*y,x*y也需要在使用返回之前将其结果值存储在某个地方。所有局部变量都存储在寄存器中,因此访问非常高效。执行“foo”函数(“R(X)”表示“寄存器x”)时会发生如下情况:

自变量0和1已经在R(0)中,R(1)将常量";5&34;加载到R(2)中,将结果放入R(0)乘以R(0)的值-与R(2)的值-,将结果放入R(0)乘以R(0)的值-,将结果放入R(0)返回R(0)。

SOL是基于寄存器的虚拟机。操作数和结果是从编号寄存器读取和存储到编号寄存器的,而不是从堆栈“推入”和“弹出”的(与基于堆栈的虚拟机一样)。基于寄存器的虚拟机避免了通常围绕其他指令的推入和弹出操作,从而减少了代码大小,但在某些情况下也提高了执行速度(与基于堆栈的虚拟机相比)。

在最优秀的论文“Lua 5.0的实现”Roberto中,Luiz和Waldemar描述了代码大小和解码开销的问题(不是真正的问题):

通常与基于寄存器的机器相关的问题有两个:代码大小和解码开销。寄存器机器中的指令需要指定其操作数,因此它通常比堆栈机器中的相应指令大。(例如,Lua的虚拟机中的指令大小为4字节,而几个典型的堆栈机器(包括Lua以前使用的机器)中的指令大小为1或2字节。)。另一方面,寄存器机器生成的操作码比堆栈机器少,因此总代码大小不会太大。

0-3个操作数(例如“寄存器a和寄存器b,结果为寄存器c”)。

因为虚拟机有…的缺点。虚拟,我们必须尽我们所能确保良好的性能,这样这些指令中的一条就可以放在一个机器字中。今天的大多数硬件都能够非常高效地处理32位长的数据块,因此受Lua5的启发,我选择了32位表示法来表示SOL的指令。

每条指令及其操作数都以三种布局中的一种进行编码(看,棒极了的ASCII艺术!)。

0 5|6 13|14 22|23 31 Bit-|-OP|A|B|C字段-|。-6 8 9 9位[0..63][0..255][0..511][0..511]范围

有些操作只需要两个操作数,如果其中一个操作数足够大,则可以提高效率。为满足此需要,我们定义了指令的备用布局:

0 5|6 13|14 31 Bit-|-|-OP|A|Bs/Bu字段-|。-6 8 18位[0..63][0..255]Bu:[0..255]范围Bu:[-131071..131072]。

第三类操作仅使用一个大小与效率相关的操作数,因此我们定义了指令的第三个替换布局,其中三个操作数有效地折叠成一个26位整数值:

0 5|6 31 Bit-|-OP|bss/buu Field-|。-6 26位[0..63]BUU:[0..67108863]范围bss:[-33554431..33554432]。

A、B、C、Bu和Buu表示无符号整数,而B和Bss表示有符号整数。如上所述,这种配置有64个操作和256个寄存器(OP=6位,A=8位)的空间。超出我们的需要:)。

在SOL中,更改和维护指令(操作+操作数)非常简单。我故意使出浑身解数,以使操作指导组变得容易。文件instr.h包含指令列表:

/*控制流*/\_(Year,ABC)/*暂停并重新计划*/\_(JUMP,BSS)/*PC+=BSS*/\_(Call,ABC)/*R(A),.,R(A+C-1):=R(A)(R(A+1),.,R(A+B))*/\_(RETURN,AB_)/*RETURN R(A),.,R(A+B-1)*/\/*DATA*/\_(LOADK,ABU)/*R(A)=K(Bu)*/\_(MOVE,AB_)/*R(A)=R(B)*/\_(DBGREG,ABC)/*特殊:调试转储寄存器值*/\/*算术*/\_(ADD,ABC)/*R(A)=RK(B)+RK(C)*/\_(SUB,ABC)/*R(A)=RK(B)-RK(C)*/\_(MUL,ABC)/*R(A)=RK(B)*RK(C)*/\.。

SOL的源代码设置方式是,除了每条指令的实际实现之外,只需更改此列表即可。添加或重命名指令会自动使方便符号和功能可用。假设我们添加了一条Ding指令,它在每次执行时都会播放一点声音:

_(MUL,ABC)/*R(A)=RK(B)*RK(C)*/\_(DING,BUU)/*A=要播放的声音号码*/\.。

现在有了一个名为S_OP_Ding的新操作标识符,以及用于编码Ding指令的构造函数:

现在运行包含Ding操作的程序将在VM中导致错误:“意外操作”。我们还没有实现丁行为!操作(在编写本文时)在sched_exec.h中实现,它是虚拟机的核心,因为它读取和执行SOL程序的指令。可以这样概括:

void Execute(Instr*Instructions){Instr*PC=指令;而(1){Switch(*++PC){CASE S_OP_LOADK://从指令*PC读取操作数A和B。//将B处的常量放入寄存器A。Break;案例S_OP_MOVE://从指令*PC读取操作数A和B。//将寄存器B的值放入寄存器A。Break;.}//Switch}//While}。

差不多是个不错的旧开关环路。当用CLANG或GCC这样的现代编译器编译这段C代码时,它将相当高效,因为我们的每个虚拟操作实际上只对应于几条机器指令。这就是我们需要添加丁丁的地方。

..。案例S_OP_DING://从指令*PC读取操作数BUU。uint32_t SOUND_INDEX=SInstrGetBuu(*PC);//找到SOUND_INDEX的备注并播放SoundNote*NOTE=SoundGetNote(SOUND_INDEX);SoundPlay(备注);Break;.。

这里的Sound类型以及SoundGet和SoundPlay表示您提供的某种声音播放函数。现在我们可以编写播放音乐的SOL程序:

定义旋律0条目:丁0#播放音符0丁1#播放音符1丁1#播放音符1丁2#播放音符2丁0#播放音符0 RETURN 0 0#RETURN

除非能够同时执行多个任务、同时执行多个任务,或者至少给程序员一种并发的错觉,否则任何玩具VM都不可能毫无羞耻地呈现出来。

SOL有一个名为“Year”的操作,它能够暂停处于任何状态的任务,并在稍后使该任务在完全相同的状态下恢复。

从任务的角度来看,它从不知道它被暂停和恢复。这是一个强大的原语,因为我们可以在此基础上实现许多功能。在编写本文时,SOL已经有两种不同类型的让步:让步于其他任务(以便它们可以从I/O等事件运行或调度),以及让步于计时器超时。在本文的末尾有几个示例程序,它们都使用了Year。

产出量用于实现协作多任务,其中所有任务协作使用处理资源。当一个任务执行了一系列计算并解除对另一个任务的控制时,会发生以下三种情况之一:

该任务发起外部(“阻塞”)操作,如从文件中读取或等待特定时间发生,

大多数与其环境和国外通信的系统,如网络服务器或文本编辑器,花费其大部分时间(相对于实时的CPU时间)等待环境响应;例如,在网络插座上产生数据、将内容写入文件或返回步进电机位置。这些系统通常受益于协作多任务处理,特别是连贯的专用系统(与本质上通用的操作系统不同)。

SOL提供的本质上是用于并发的协程。协程程序(又名“绿色线程”,又名“用户线程”)的一个很好的特性是它们能够在并发系统中运行顺序代码。像这样的任务:

涉及对环境的三个“阻塞”调用,这会导致任务产生:

打开要求操作系统按名称打开文件。该文件可能会在将来的某个时候打开。调度程序注意到任务正在等待这种情况发生,暂时将其从运行队列中删除。

操作系统告诉调度器“您想让我打开的那个文件,这是文件描述符”,因此调度器再次将任务放到运行队列中。

任务再次调用环境,这一次请求读取f的内容。

和以前一样,调度器告诉操作系统,记下笔记,取消对任务的调度,然后继续执行其他任务。

操作系统告诉调度器“我已经读了您要我读的那个文件,这是数据”(实际上这稍微复杂一些,但原理是一样的)。

def read_file(name,callback):open(name,def(error,f):if(Error):callback(Error):false:read(f,def(read_error,data):close(f,def(Error):callback(error,data)#在打开文件之前返回此处。

显然很难跟上。SOL中的任务可以派生新任务,以便同时执行几项任务,例如在通过网络回复时写入文件。

定义WRITE_AND_REPLY(Destination_id,message):Writer=write_file(Destination_id+";.msg";,message)send_message(Destination_id,message)while(recv(Writer)!=TaskEnd)noop#等待WRITE_FILE结束

因为协作式多任务系统依赖于每个进程有规律地将时间让给系统上的其他进程,所以一个设计不佳的程序可能会独占所有的CPU时间,或者导致整个系统挂起。

当程序执行一组非常长的计算时,可能会发生这种情况,并可能导致各种问题,特别是对于其他依赖计时器的任务。由于SOL调度程序仅在任务执行之间检查计时器过期,因此计时器可能会在其应该触发很长时间之后才有效地触发。想象一下,控制一个玩具四旋翼飞机,其中一个任务需要每50毫秒更新一个转子的角度,而另一个任务需要整整200毫秒,那么你的四旋翼飞机可能会崩溃和燃烧。

为了解决这个问题,SOL采用了操作成本计数器。每次执行迭代(当调度器运行任务的程序时),每个任务都被赋予预定数量的“操作值”。当操作成本计数器达到其极限时,该任务将被简单地强制让给其他任务。在源代码中,查找S_VM_EXEC_LIMIT。

下面的代码是用简化的汇编语言表示的,它与C API几乎是1:1,用于以编程方式定义这些程序,因此除了解释执行的指令之外,汇编语言本身应该被认为是无关紧要的。

在输出中,如下所示的行:[VM]_.。表示计划程序在运行任务且任务返回或放弃后重新获得控制的时间。这是一个“执行迭代”。当运行多个任务时,您通常会看到这些“执行迭代”标记行之间的任务以循环顺序交织在一起。

在输出中,以“…”开头的行。是注释和/或简化,不是实际输出的一部分。

在汇编注释中,R(X)表示“寄存器x”,Rk(X)表示“如果x小于k,则寄存器x为常量(x-k)”,其中k是特定值,K(X)表示“常量x”。

在汇编注释中,PC表示“程序计数器”,它在某种程度上是指向程序指令的光标。每执行一条指令,它就加1。一些指令将进一步修改该计数器,例如跳转指令。

当变量x大于0时,将x减1,并让位给调度程序,让其他任务运行。最终会回来。

def main():x=5,而(x>;0):x=x-1收益率。

是否定义主0常量5#K(0)=5常量0#K(1)=0常量1#K(2)=1条目:LOADK 0 0#R(0)=K(0)LE 0 0 256#(0==RK(k+1)<;RK(0))?继续,否则PC++JUMP 3#PC+=3返回SUB 0 0 257#R(0)=R(0)-RK(k+1)收益率0 0 0#收益率A=TYPE=预定跳转-5#PC-=5到LE返回0 0#RETURN。

$build/debug/bin/solSol 0.1.0 x64[VM]_[VM]任务函数PC操作值[VM]0x7fdf28c03c00 0x7fdf28c000e0 LOADK。0,257[VM]0x7fdf28c03c00 0x7fdf28c000e0 4产量abc:0,0,0[VM]_[VM]任务函数PC操作值[VM]0x7。256[VM]0x7fdf28c03c00 0x7fdf28c000e0 3子abc:0,0,257[VM]0x7fdf28c03c00 0x7fdf28c000e0 4产量abc:0,0,0[VM]_.与上述块相同的另外三个执行迭代.[VM]_。_[VM]任务函数PC操作值[VM]0x7fdf28c03c00 0x7fdf28c000e0 5 Jump bss:-5[VM]0x7fdf28c03c00 0x7fdf28c000e0 1 le abc:0,0,256[VM]0x7fdf28c03c00 0x7fdf28c000e0 2跳转bss:3[VM]0x7fdf28c03c00 0x7fdf28c000e0 6 Return AB:0,0计划程序运行循环退出。

该程序使用两个函数。入口点是主函数,它只使用一个参数‘500’调用kitten函数。kitten函数在传递给它的毫秒数内“休眠”(作为第一个参数)。然后,kitten函数将数字“123”返回给调用者(主函数),调用者转储寄存器值并最终返回,导致任务退出,随后调度程序和VM也退出。

定义Kitten 1#参数:(r(0)=睡眠_ms)const 123#K(0)=123 Entry:Year 1 0#Year A=type=Timer,RK(B)=R(0)=arg0 LOADK 0 0#R(0)=K(0)=123 return 0 1#return R(0)..R(0)=R(0)=123定义主要0#参数:()const@kitten#K(0)=<;函数。const 500#K(1)=500条目:LOADK 0 0#R(0)=K(0)=小猫函数LOADK 1 1#R(1)=K(1)=500 CALL 0 1 1#R(0)..R(0)=R(0)(R(1)..R(1))=a(R(1))DBGREG 0 1 0#转储寄存器值的VM调试函数RETURN 0 0#RETURN。

$time生成/调试/bin/solSol 0.1.0 x64[VM]_[VM]任务函数PC操作值[VM]0x7f8c9bc03bf0 0x7f8c9bc03910。1[VM]0x7f8c9bc03bf0 0x7f8c9bc000e0 1产量abc:1,0,计划在500.000000毫秒之后触发的0D计时器(调度.c:81)#.时间已过,在这种情况下调度程序正在空闲.D计时器已触发--调度任务(调度.c:57)[VM]_。_[VM]任务函数PC操作值[VM]0x7f8c9bc03bf0 0x7f8c9bc000e0 2 LOADK AB:0,0[VM]0x7f8c9bc03bf0 0x7f8c9bc000e0 3返回AB:0,1[VM]0x7f8c9bc03bf0 0x7f8c9bc03910 3 DBGREG[VM]R(0)=123.000000(sched_exec.h:214)D[VM]R(1)=500.000000(sched_exec.h:215)D[VM]R(0。

$build/debug/bin/solSol 0.1.0 x64[sched 0x7fc219403930]运行队列:[任务0x7fc219403c00]->;[任务0x7fc219403cd0]->;[任务0x7fc219403da0][VM]_[VM]任务函数PC操作值[VM]0x7fc219403c00 0x7fc2194000e0 LOADK AB:0。257[VM]0x7fc219403c00 0x7fc2194000e0 4产量abc:0,0,0[VM]_

..