summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorAlex Auvolat <alex.auvolat@ens.fr>2014-11-30 17:21:50 +0100
committerAlex Auvolat <alex.auvolat@ens.fr>2014-11-30 17:21:50 +0100
commit696be5d1f72a9e666d3fa1cd1e2ebddfce67e444 (patch)
tree8f3898f036dec96a131318f3b6ef49b5cbbbb8fe
parent1f27167dcfdddc75c83ab746bbd3589f003458b9 (diff)
downloadNARP-696be5d1f72a9e666d3fa1cd1e2ebddfce67e444.tar.gz
NARP-696be5d1f72a9e666d3fa1cd1e2ebddfce67e444.zip
Add details on NARP OS
-rw-r--r--doc/narp.tm267
1 files changed, 182 insertions, 85 deletions
diff --git a/doc/narp.tm b/doc/narp.tm
index 30450f3..8639045 100644
--- a/doc/narp.tm
+++ b/doc/narp.tm
@@ -707,9 +707,6 @@
implement repetition in the case where the message hasn't been acknowledge?
...
- Reserved message IDs : <math|<around*|[|20,30|)>> and
- <math|<around*|[|10020,10030|)>>.
-
<subsection|Authentification and rights managment commands>
<paragraph|Authenticate<math|\<uparrow\>>>
@@ -751,45 +748,19 @@
TODO : request account creation, manage user groups and ACLs, ...
- <subsection|File protocol>
-
- Client messages [50,100) ; server messages [10050,10100). TODO
-
- <subsection|UI protocols>
-
- Client messages <math|<around*|[|100,200|)>> and server messages
- <math|<around*|[|10100,10200|)>>.
-
- <subsubsection|Terminal protocol>
-
- TODO
-
- <subsubsection|Graphical user interface protocol>
+ <subsection|TODO>
- TODO
-
- <subsection|Communication protocols>
-
- Client messages <math|<around*|[|200,300|)>> and server messages
- <math|<around*|[|10200,10300|)>>.
-
- <subsubsection|Email and newsgroups protocol>
-
- Client messages <math|<around*|[|200,220|)>>, server messages
- <math|<around*|[|10200\<nocomma\>,10220|)>>.
+ <\itemize>
+ <item>file protocol
- <subsubsection|Instant messaging protocol>
+ \;
- Client messages <math|<around*|[|220,250|)>>, server messages
- <math|<around*|[|10220\<nocomma\>,10250|)>>.
+ <item>system protocols (see section on OS design using NARP)
- <subsection|Other protocols>
+ <item>UI protocols (terminal, GUI)
- Protocols not discussed in this specification may use client messages with
- type IDs <math|<around*|[|1000,10000|)>> and server messages
- <math|<around*|[|11000,20000|)>>. Overlaps between several protocols are
- allowed : the information about implemented interfaces for an object is
- meant to disambiguate such situations.
+ <item>communication protocols (mail, IM)
+ </itemize>
<subsection|Table of IDs>
@@ -896,7 +867,121 @@
implementing a standard filing protocol, much like memory mapped files in
standard OSes (only this would work with arbitrary ressources).
- TODO
+ In this section we will develop on a concrete proposal for a NARP-based
+ operating system.
+
+ <subsection|Architecture of the OS>
+
+ The basic primitive of the system being message-passing, the system looks a
+ lot like a micro-kernel. Only the message format has a complex semantic and
+ the communication layer is not really ``simple''. Furthermore, the system
+ has device drivers, file system and networking running as kernel-mode
+ processes, making the kernel more monolithic (but still having a
+ micro-kernel spirit). It should be easy to make any user mode process run
+ as a kernel mode process instead, for the sake of performance (eg :
+ graphical server & compositor).
+
+ The kernel land is divided in three major parts, with strict dependency
+ order:
+
+ <\itemize>
+ <item>Level 0 : System ressource managment : physical memory, virtual
+ memory, hardware interaction (IRQ, v86), debug output
+
+ <item>Level 1 : Scheduler, IPC & NARP core server : builds on top of
+ level 0, adds support for processes and communication between them
+ restricted to NARP protocol data.
+
+ <item>Level 2 : System processes : hardware, file systems, network, ...
+ (may access level 0 and level 1 features)
+ </itemize>
+
+ User processes are restricted to syscalls that call level 1 primitives.
+
+ Here are a few basic principles for the design of these three levels :
+
+ <\itemize>
+ <item>Level 2 processes may not communicate directly nor share memory :
+ they must go through level 0 and level 1 primitives to achieve such a
+ goal. Each level 2 process has a separate heap, which is completely freed
+ when the process dies. Level 2 processes do not use separate virtual
+ memory spaces : since the kernel memory space is mapped in all page
+ directories, a level 2 process may run with any page directory.
+
+ Benefits : critical system parts are restricted to level 0 and level 1.
+ Level 2 components may leak or crash with less consequences.
+
+ <item>All synchronization & locking is handle by level 1, except for
+ level 0 that must implement its own locking devices (since it cannot rely
+ on level 1).
+
+ Benefits : no complex synchronization in most of the code (which is
+ either level 2 or userland), only simple message passing and waiting for
+ stuff to happen
+
+ <item>No concept of ``threads'' : system processes are actually kernel
+ threads, but we call them processes since they use separate parts of
+ memory. Userlands processes cannot spawn multiple threads of execution
+ either : they must fork and communicate through NARP if they want to do
+ so (eg: launching an expensive communication in the background).
+
+ (since fork is a complicated system call, and features such as
+ copy-on-write depend on processes using different paging directories, the
+ fork system call is accessible only to userland processes : level 2
+ processes may not fork, but only create new processes)
+
+ <item>Level 1 also has a memory heap ; it is used with
+ <verbatim|core_malloc/core_free>. Level 2 proceses use standard
+ <verbatim|malloc/free>, which are modified to act on the heap of the
+ current process.
+
+ <item>Each process (system or user) has a <em|mailbox>, ie a queue of
+ incoming NARP messages waiting to be transferred. The mailbox has a
+ maximum <em|size> (buffer size), and a <em|send> call may fail with a
+ <em|no space left in queue> error. This is the only possible failure for
+ a <em|send> call.
+
+ System processes (level 2) spend most of their time in <em|waiting mode>
+ ; they may be waked up by either recieving a NARP messsage or by a
+ hardware event. Therefore the <em|wait_for_event> function that composes
+ the main loop may return either : <em|a message was recieved> or <em|a
+ system event happenned>. If the reason is <em|a message was recieved>,
+ the process is free not to read the message immediately.
+
+ On the other hand, user processes can wait for only one thing : recieving
+ a NARP message. Each user process has a <em|message zone> in its memory
+ space, and the <em|wait for message> function just copies the first
+ message of the mailbox into this zone (overwriting whatever was there
+ before) and returns control to the process (returning the length of the
+ message).
+
+ <item>Handling of IRQs : some hardware stuff requires action as soon as
+ the interrupt is fired, therefore a specifi IRQ handler may be used. Such
+ a handler must do as little as possible, and when it is done signal level
+ 1 that an IRQ has happenned (it may add specific data to the ``IRQ
+ happenned'' message). Level 1 adds a message to the queue of the
+ recipient process (if there is one) and returns immediately : the IRQ
+ handler must leave as soon as possible. An IRQ is handled on whatever
+ stack is currently used, and the IF flag is constantly off while the IRQ
+ handler is running. The timer IRQ is the only one that behaves
+ differently, since it has to trigger a task switch.
+ </itemize>
+
+ <subsection|Steps of the developpment of the OS>
+
+ <\enumerate>
+ <item>Develop level 0 completely and with cleanest possible design
+
+ <item>Develop level 1 with only basic funcionnality
+
+ <item>Develop some basic applications in level 2 : display, keyboard,
+ mini kernel shell, mini file system, ...
+
+ <item>Improve level 1 with more complex stuff ; try to quickly attain a
+ complete level 1
+
+ <item>Work on the rest of the stuff
+ </enumerate>
</body>
<\initial>
@@ -952,44 +1037,44 @@
<associate|auto-48|<tuple|3.3.0.23|9>>
<associate|auto-49|<tuple|3.3.0.24|9>>
<associate|auto-5|<tuple|2.3|2>>
- <associate|auto-50|<tuple|3.3.0.25|9>>
- <associate|auto-51|<tuple|3.3.0.26|9>>
+ <associate|auto-50|<tuple|3.3.0.25|10>>
+ <associate|auto-51|<tuple|3.3.0.26|10>>
<associate|auto-52|<tuple|3.4|10>>
<associate|auto-53|<tuple|3.5|10>>
<associate|auto-54|<tuple|3.5.0.27|10>>
<associate|auto-55|<tuple|3.5.0.28|10>>
<associate|auto-56|<tuple|3.5.0.29|10>>
<associate|auto-57|<tuple|3.6|10>>
- <associate|auto-58|<tuple|3.7|10>>
- <associate|auto-59|<tuple|3.7.1|10>>
+ <associate|auto-58|<tuple|3.7|11>>
+ <associate|auto-59|<tuple|3.7.1|11>>
<associate|auto-6|<tuple|2.4|2>>
- <associate|auto-60|<tuple|3.7.2|10>>
- <associate|auto-61|<tuple|3.8|10>>
- <associate|auto-62|<tuple|3.8.1|10>>
- <associate|auto-63|<tuple|3.8.2|11>>
- <associate|auto-64|<tuple|3.9|11>>
- <associate|auto-65|<tuple|3.10|11>>
- <associate|auto-66|<tuple|3.10.1|11>>
- <associate|auto-67|<tuple|3.10.1.1|11>>
- <associate|auto-68|<tuple|3.10.1.2|11>>
- <associate|auto-69|<tuple|3.10.2|11>>
+ <associate|auto-60|<tuple|3.7.1.1|11>>
+ <associate|auto-61|<tuple|3.7.1.2|11>>
+ <associate|auto-62|<tuple|3.7.2|11>>
+ <associate|auto-63|<tuple|3.7.3|11>>
+ <associate|auto-64|<tuple|3.7.3.1|11>>
+ <associate|auto-65|<tuple|3.7.3.2|11>>
+ <associate|auto-66|<tuple|3.7.3.3|11>>
+ <associate|auto-67|<tuple|4|11>>
+ <associate|auto-68|<tuple|5|11>>
+ <associate|auto-69|<tuple|5.1|12>>
<associate|auto-7|<tuple|2.5|3>>
- <associate|auto-70|<tuple|3.10.3|12>>
- <associate|auto-71|<tuple|3.10.3.1|12>>
- <associate|auto-72|<tuple|3.10.3.2|12>>
- <associate|auto-73|<tuple|3.10.3.3|?>>
- <associate|auto-74|<tuple|4|?>>
- <associate|auto-75|<tuple|5|?>>
+ <associate|auto-70|<tuple|5.2|12>>
+ <associate|auto-71|<tuple|4|12>>
+ <associate|auto-72|<tuple|5|12>>
+ <associate|auto-73|<tuple|3.10.3.3|12>>
+ <associate|auto-74|<tuple|4|12>>
+ <associate|auto-75|<tuple|5|13>>
<associate|auto-8|<tuple|2.5.1|3>>
<associate|auto-9|<tuple|2.5.2|3>>
- <associate|error-nums|<tuple|3.10.2|11>>
+ <associate|error-nums|<tuple|3.7.2|12>>
<associate|footnote-1|<tuple|1|2>>
<associate|footnote-2|<tuple|2|?>>
<associate|footnr-1|<tuple|1|2>>
<associate|footnr-2|<tuple|2|?>>
- <associate|interface-nums|<tuple|3.10.3|11>>
+ <associate|interface-nums|<tuple|3.7.3|12>>
<associate|rev-sock|<tuple|2.4|2>>
- <associate|type-nums|<tuple|3.10.1|11>>
+ <associate|type-nums|<tuple|3.7.1|11>>
</collection>
</references>
@@ -1188,103 +1273,115 @@
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
<no-break><pageref|auto-48><vspace|0.15fn>>
+ <with|par-left|<quote|4tab>|Unbox<with|mode|<quote|math>|\<uparrow\>>
+ <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
+ <no-break><pageref|auto-49><vspace|0.15fn>>
+
+ <with|par-left|<quote|4tab>|Plug<with|mode|<quote|math>|\<uparrow\>>
+ <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
+ <no-break><pageref|auto-50><vspace|0.15fn>>
+
+ <with|par-left|<quote|4tab>|Unplug<with|mode|<quote|math>|\<uparrow\>>
+ <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
+ <no-break><pageref|auto-51><vspace|0.15fn>>
+
<with|par-left|<quote|1tab>|3.4<space|2spc>Big message protocol
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-49>>
+ <no-break><pageref|auto-52>>
<with|par-left|<quote|1tab>|3.5<space|2spc>Authentification and rights
managment commands <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-50>>
+ <no-break><pageref|auto-53>>
<with|par-left|<quote|4tab>|Authenticate<with|mode|<quote|math>|\<uparrow\>>
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-51><vspace|0.15fn>>
+ <no-break><pageref|auto-54><vspace|0.15fn>>
<with|par-left|<quote|4tab>|NewToken<with|mode|<quote|math>|\<uparrow\>>
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-52><vspace|0.15fn>>
+ <no-break><pageref|auto-55><vspace|0.15fn>>
<with|par-left|<quote|4tab>|NewTokenR<with|mode|<quote|math>|\<downarrow\>>
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-53><vspace|0.15fn>>
+ <no-break><pageref|auto-56><vspace|0.15fn>>
<with|par-left|<quote|1tab>|3.6<space|2spc>File protocol
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-54>>
+ <no-break><pageref|auto-57>>
<with|par-left|<quote|1tab>|3.7<space|2spc>UI protocols
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-55>>
+ <no-break><pageref|auto-58>>
<with|par-left|<quote|2tab>|3.7.1<space|2spc>Terminal protocol
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-56>>
+ <no-break><pageref|auto-59>>
<with|par-left|<quote|2tab>|3.7.2<space|2spc>Graphical user interface
protocol <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-57>>
+ <no-break><pageref|auto-60>>
<with|par-left|<quote|1tab>|3.8<space|2spc>Communication protocols
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-58>>
+ <no-break><pageref|auto-61>>
<with|par-left|<quote|2tab>|3.8.1<space|2spc>Email and newsgroups
protocol <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-59>>
+ <no-break><pageref|auto-62>>
<with|par-left|<quote|2tab>|3.8.2<space|2spc>Instant messaging protocol
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-60>>
+ <no-break><pageref|auto-63>>
<with|par-left|<quote|1tab>|3.9<space|2spc>Other protocols
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-61>>
+ <no-break><pageref|auto-64>>
<with|par-left|<quote|1tab>|3.10<space|2spc>Table of IDs
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-62>>
+ <no-break><pageref|auto-65>>
<with|par-left|<quote|2tab>|3.10.1<space|2spc>Message types
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-63>>
+ <no-break><pageref|auto-66>>
<with|par-left|<quote|4tab>|Base protocol
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-64><vspace|0.15fn>>
+ <no-break><pageref|auto-67><vspace|0.15fn>>
<with|par-left|<quote|4tab>|Authentication & privileges
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-65><vspace|0.15fn>>
+ <no-break><pageref|auto-68><vspace|0.15fn>>
<with|par-left|<quote|2tab>|3.10.2<space|2spc>Error messages
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-66>>
+ <no-break><pageref|auto-69>>
<with|par-left|<quote|2tab>|3.10.3<space|2spc>Object interfaces
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-67>>
+ <no-break><pageref|auto-70>>
<with|par-left|<quote|4tab>|Servable
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-68><vspace|0.15fn>>
+ <no-break><pageref|auto-71><vspace|0.15fn>>
<with|par-left|<quote|4tab>|non-NARP inside
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-69><vspace|0.15fn>>
+ <no-break><pageref|auto-72><vspace|0.15fn>>
<with|par-left|<quote|4tab>|NARP service
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-70><vspace|0.15fn>>
+ <no-break><pageref|auto-73><vspace|0.15fn>>
<vspace*|1fn><with|font-series|<quote|bold>|math-font-series|<quote|bold>|4<space|2spc>Architecture
of a NARP implementation in OCaml or Haskell>
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-71><vspace|0.5fn>
+ <no-break><pageref|auto-74><vspace|0.5fn>
<vspace*|1fn><with|font-series|<quote|bold>|math-font-series|<quote|bold>|5<space|2spc>Using
NARP to design an Operating System>
<datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>>
- <no-break><pageref|auto-72><vspace|0.5fn>
+ <no-break><pageref|auto-75><vspace|0.5fn>
</associate>
</collection>
</auxiliary> \ No newline at end of file