/SPARTAN/trunk/doc/synchronization |
---|
0,0 → 1,29 |
SPINNING LOCKS |
spinlock_lock, spinlock_trylock, spinlock_unlock |
+------------+ |
| spinlock_t | |
+------------+ |
WAIT QUEUES |
waitq_sleep_timeout, waitq_wakeup |
+---------+ |
| waitq_t | |
+---------+ |
/ \ |
SEMAPHORES / \ CONDITION VARIABLES |
semaphore_down_timeout, semaphore_up condvar_wait_timeout, condvar_signal |
+--------------+ / \ +-----------+ |
| semaphore_t |<-+ +->| condvar_t | |
+--------------+ +-----------+ |
| ^ |
| | |
| +------+ |
V / |
MUTEXES / READERS/WRITERS LOCKS |
mutex_lock_timeout, mutex_unlock rwlock_reader/writer_lock_timeout, rwlock_unlock |
+---------+ / +----------+ |
| mutex_t |------------------------------->| rwlock_t | |
+---------+ / +----------+ |
| / |
+------------------------+ |
/SPARTAN/trunk/doc/preemption |
---|
0,0 → 1,58 |
Kernel makes it possible for a thread to be preempted anytime when |
IRQ's are enabled on local CPU. This arrangement triggers a discussion |
about its correctness and efficiency. |
The correctness issue relates to the possibility of preempting a |
thread holding a spinlock. It is natural to ask whether such a |
preemption can lead to a deadlock. By proving the following lemma, we |
will show that deadlock is actually not possible. |
Lemma: |
On condition that each spinning lock is always locked on the same |
CPU priority level (either always with IRQ's disabled or always |
with IRQ's enabled), otherwise correct code never deadlocks. |
Proof: |
Let all assumptions from the lemma hold. |
Let us further assume that we have encountered a deadlock. |
We will analyse all likely ways how that could have happened. |
a) Deadlock happened between two CPUs. This means that there must |
have been wrong lock-ordering. Code with lock-ordering problems is |
considered incorrect and contradicts our assumptions. |
b) Deadlock happened between two threads of execution executing on |
the same CPU. |
b1) If one thread of execution was servicing an interrupt and the |
other was executing in thread context, our assumption that each |
spinning lock is acquired always on the same CPU priority level is |
violated. |
b2) The last likely scenario is that the deadlock happened between |
two threads executing on the same CPU with IRQ's enabled. Again, |
this means that we were working with incorrect code because it |
contained wrong ordering of lock operations. |
Since there is no possibility left, except for trivial errors, we |
have shown that the deadlock contradicts with our assumptions and |
therefore is not possible. |
Q.E.D. |
Notes on the proof: |
ad a) Deadlock between two CPUs is independent on the preemption |
model. If we have this kind of deadlock, we would have had |
the same kind of deadlock on an ordinary SMP system with |
kernel preemption disabled. |
This preemption model makes UP behave more like SMP because |
it introduces some SMP specific specialities. |
ad b2) Notice that the scenario when thread A acquires lock X and |
gets preempted in favor of thread B which is trying to |
acquire lock X, doesn't deadlock the two threads. Of course, |
B won't be allowed to get X until A releases it, but that |
will certainly happen because B too will sooner or later be |
preempted. This scenario emphasizes the efficiency issues, |
though. |
/SPARTAN/trunk/doc/requirements |
---|
0,0 → 1,36 |
ia32 port |
========= |
HARDWARE REQUIREMENTS |
o IA-32 processor (Pentium and successors) |
COMPILER REQUIREMENTS |
o binutils 2.15 |
o gcc 2.95 |
o gcc 3.3.2 - gcc 3.3.5 |
SMP COMPATIBILITY |
o Bochs 2.0.2 - Bochs 2.1 |
o 2x-8x 686 CPU |
o ASUS P/I-P65UP5 + ASUS C-P55T2D REV. 1.41 |
o 2x 200Mhz Pentium CPU |
EMULATORS AND VIRTUALIZERS |
o Bochs 2.0.2 - Bochs 2.1 |
o VMware Workstation 4 |
mips port |
========= |
HARDWARE REQUIREMENTS |
o no real hardware supported |
o msim emulated MIPS R4000 CPU (see mips) |
COMPILER REQUIREMENTS |
o binutils 2.14 mips cross binutils |
o gcc 2.8.1 mips cross compiler |
o gcc 3.2.3 mips cross compiler |
EMULATORS AND VIRTUALIZERS |
o msim |
/SPARTAN/trunk/doc/TODO |
---|
0,0 → 1,22 |
+ implement true memory management |
+ [ia32] use int 0x15 ax=0xe820 to get memory map and memory size |
+ [mips] use some heuristics to get memory map and memory size |
+ reimplement heap so that it can allocate/deallocate itself frames as necessary |
+ provide native four-level portable page table interface |
+ every architecture uses its native page table format |
+ kernel provides unified four-level page table interface for all architectures |
+ track usage of frames containing middle-level page tables (frame leak) |
+ get user mode support for all architectures |
+ when a new thread enters scheduler, at least one CPU in |
cpu_sleep() should be woken up by an IPI |
+ save/restore floating point context on context switch |
+ [ia32] lazy context switch using TS flag |
+ [ia32] review privilege separation |
+ zero IOPL in EFLAGS |
+ before IRET (from SYSCALL), zero NT in EFLAGS |
+ [ia32] review the cache controling bits in CR0 register |
+ [ia32] zero the alignment exception bit in EFLAGS |
+ make emulated architectures also work on real hardware |
+ bring in support for other architectures (e.g. PowerPC) |
/SPARTAN/trunk/doc/mips |
---|
0,0 → 1,37 |
SPARTAN kernel currently supports emulated MIPS R4000 32-bit |
little-endian architecture. In other words, it can only run in MIPS |
R4000 emulator called msim. This emulator is being developed by Viliam |
Holub: |
http://nenya.ms.mff.cuni.cz/~holub/msim |
Note that msim diverges from real MIPS hardware in some aspects. |
Therefore, some non-trivial changes will be necessary for a real |
hardware port. The simulator is described in this manual: |
http://nenya.ms.mff.cuni.cz/~holub/msim/msim.ps |
You'll need a msim.conf script like this: |
# |
# MSIM configuration script |
# |
add dcpu mips1 |
add rwm mainmem 0 16M load "kernel.bin" |
add rom startmem 0x1fc00000 1k load "load.bin" |
add dprinter printer 0xA000000 |
BOOTSTRAP |
========= |
Because the mips port uses binary executable format and for some other |
architectural reasons, it shares one address for bootstrap entry |
(address where control is passed from loader) and for TLB refill |
exception entry. The former is used only once during system bootstrap. |
From that point further, only TLB refill exception entry uses that |
address. Note that this is the reason why main_bsp() is called from |
tlb_refill() code. |