Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 170 lines (117 sloc) 5.389 kb
ab496fb2 »
2009-09-24 Initial commit
1 What
2 ====
3
4 I'm exploring world of compilers and interpreters.
5
6 This is a simple concurrent virtual machine. It can run many internal threads in few real OS threads.
7
8 Python is chosen as fast prototyping language.
9
10
ea1a1df2 »
2009-10-14 Project is closed. Wrote what i have learned.
11 What i've learned
12 =================
13
14 - Yay! Virtual machines work! :)
15 - It is stupid easy to create a stupid virtual machine
16 - Shared-state threads aren't bad or ugly while you only read from other virtual threads.
17 - Problem #1: scheduling virtual threads execution. This may be done in numerous different ways.
18
19 Assign a single virtual thread to single real executor (OS thread, CPU, etc) is probably the simplest, but definately not the best option.
20
21 Then, choosing how much instructions to execute before yielding control to another virtual thread is another problem.
22
23 Executing at most N instructions is probably simplest, but obviously not the best solution.
24
25 *Note*: The problem of scheduling instructions is a bit wider because sometimes
26 some parts of code inside single virtual thread may be paralleled as well (implicit micro threads, instruction level parallelism).
27 But i haven't got into that yet.
28
29 - Problem #2: sleeping and resuming virtual threads. Waiting for other virtual threads to finish. More generally, event system.
30
31 Clearly, virtual machine needs some kind of event system, at least to react on outside world events. Interrupts in x86 computers is an example of such event system.
32
33 My effort in doing event system for vm-001 drown in locks. Need a good design on thread-safe multi-producer, multi-consumer event dispatcher.
34
35
ab496fb2 »
2009-09-24 Initial commit
36 VM specification
37 ================
38
39 This is a register based virtual machine. Thus, it has registers for storing values. Values are signed integer numbers.
40
41 There are 8 (without a reason) thread-local registers named r0, r1, ... r7.
42 And 8 global registers named g0, g1, ... g7.
43
44
8978c927 »
2009-10-14 fixed VM instructions list markup
45 Instructions:
46
47 `copy D S`
48 copies value of thread-local register S to thread-local register D. Same as assembler instruction `mov`.
49 `gcopy D S`
50 copies value of register S to register D. Any or both registers may be global.
51
52 Copying from or to global register is special because it locks register for concurrent reading/writing.
53
54 `set R val`
55 sets thread-local register R to some constant value, which may be a constant expression, like '3 + 5'.
56 `gset R val`
57 sets global register R to some constant value.
58
59 `swap R1 R2`
60 swaps values of two thread-local registers.
61
62 `eval D op R1 R2`
63 puts result of evaluation `R1 op R2` into register D. All registers must be thread-local.
64
65 See operators below.
66
67 `jump R`
68 unconditionally jumps to instruction pointed by thread-local register R.
69 `jz A E`
70 jumps to instruction A if register E is equal to zero.
71
72 A may be a constant address or thread-local register. E must be thread-local register.
73 `jnz A E`
74 same as `jz`, but tests for `E != 0`.
75 `addr R`
76 puts current instruction address to thread-local register R.
77
78 `spawn D A`
79 spawns new thread with starting instruction A. A may be a constant address or thread-local register.
80
81 New thread's registers are copied from its parent.
82 Puts id of new thread into register D.
83 `spawna D A`
84 same as `spawn`, but VM deletes new thread when it does `tstop`.
85 Name 'spawna' means SPAWN Automatically deleted thread.
86 `tself D`
87 puts id of current thread into register D.
88 `tget D T S`
89 inter-thread `copy` of register S in thread T into register D in current thread.
90 `twait T`
91 stops current thread, until thread T is not stopped. When thread T does `tstop`, current thread resumes execution.
92 `tstop`
93 stops current thread.
94 Do this in main thread to gracefully shutdown VM.
95 `tdel T`
96 deletes thread T. After this instruction, `tget _ T _` and `twait T` will crash VM.
97
98 `print R`
99 prints the value in thread-local register R.
100
101 Operators:
102
103 math:
104 -, +, \*, /. Math operators evaluate to integer number.
105
106 `/` is integer division. Division by zero crashes the VM. Division is rounded towards zero.
107
108 logic:
109 <, >, <=, >=, ==, !=. Logic operators evaluate to 1 for true and 0 for false.
ab496fb2 »
2009-09-24 Initial commit
110
111
112 Sample
113 ======
114
115 This sample program prints GCD (greatest common denominator) of two integers supplied in g0 and g1.
116
117 gcopy r0 g0
118 gcopy r1 g1
119
120 :start
121 jz :done r1 # if b == 0, we're done
122
123 eval r2 < r0 r1 # a < b?
124 jz :sub r2 # continue if not
125 swap r0 r1 # swap a and b if yes
126
127 :sub
128 eval r0 - r0 r1 # a = a - b
129 jump :start
130
131 :done
132 print r0
133
134
135 This sample program concurrently calculates fib(x) of integer supplied in g0.
136
137 jump :start
138
139 :F-fib # F- for "function" fib(x), x is r0
140 eval r1 < r0 2 # x < 2?
141 jnz :F-fib-done r1 # return x if yes
142
143 eval r1 - r0 1 # a = x - 1
144 eval r2 - r0 2 # b = x - 2
145
146 copy r0 r1
147 spawn r3 :F-fib # spawn fib(a)
148 copy r0 r2
149 spawn r4 :F-fib # spawn fib(b)
150
151 twait r3
152 tget r1 r3 r0 # a = wait for result of fib(a)
153 tdel r3 # delete thread to avoid memory leaks
154 twait r4
155 tget r2 r4 r0 # b = wait for result of fib(b)
156 tdel r4 # delete thread to avoid memory leaks
157
158 eval r0 + r1 r2 # x = a + b
159
160 :F-fib-done
161 tstop
162
163 :start
164 gcopy r0 g0
165 spawn r1 :F-fib
166 twait r1
167 tget r0 r1 r0
168 print r0
169 # not deleting thread because VM stops anyway
Something went wrong with that request. Please try again.