| /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. |