Annotation of prex-old/doc/html/doc/kernel.html, Revision 1.1.1.1
1.1 nbrk 1: <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
2: <html>
3: <head>
4: <title>Prex Kernel Internals</title>
5: <meta content="text/html; charset=ISO-8859-1" http-equiv="content-type">
6: <meta name="keywords" content="Prex, embedded, real-time, operating system, RTOS, open source, free">
7: <meta name="author" content="Kohsuke Ohtani">
8: <link rel="stylesheet" type="text/css" href="../default.css" media="screen">
9: <link rel="stylesheet" type="text/css" href="../print.css" media="print">
10: </head>
11: <body>
12: <div id="top">
13: </div>
14: <div id="middle">
15:
16: <table id="content" cellpadding="0" cellspacing="0">
17: <tbody>
18:
19: <tr>
20: <td id="header" colspan="2" valign="top">
21: <table width="100%" border="0" cellspacing="0" cellpadding="0">
22: <tr>
23: <td id="logo">
24: <a href="http://prex.sourceforge.net/">
25: <img alt="Prex logo" src="../img/logo.gif" border="0"
26: style="width: 281px; height: 56px;"></a>
27: </td>
28: <td id="brief" align="right" valign="bottom">
29: An Open Source, Royalty-free,<br>
30: Real-time Operating System
31: </td>
32: </tr>
33: </table>
34: </td>
35: </tr>
36:
37: <tr>
38: <td id="directory" style="vertical-align: top;">
39: <a href="http://prex.sourceforge.net/">Prex Home</a> >
40: <a href="index.html">Document Index</a> >
41: Kernel Internals
42: </tr>
43: <tr><td class="pad" colspan="2" style="vertical-align: top;"></td></tr>
44:
45: <tr>
46: <td id="main" style="vertical-align: top;">
47: <h1>Prex Kernel Internals</h1>
48:
49: <i>Version 1.4, 2005/12/31</i>
50:
51: <h3>Table of Contents</h3>
52: <ul>
53: <li><a href="#over">Kernel Overview</a></li>
54: <li><a href="#design">Design Policy</a></li>
55: <li><a href="#thread">Thread</a></li>
56: <li><a href="#task">Task</a></li>
57: <li><a href="#sched">Scheduler</a></li>
58: <li><a href="#memory">Memory Management</a></li>
59: <li><a href="#ipc">IPC</a></li>
60: <li><a href="#except">Exception Handling</a></li>
61: <li><a href="#int">Interrupt Framework</a></li>
62: <li><a href="#timer">Timer</a></li>
63: <li><a href="#device">Device I/O Service</a></li>
64: <li><a href="#mutex">Mutex</a></li>
65: <li><a href="#debug">Debug</a></li>
66: </ul>
67: <br>
68:
69: <h2 id="over">Kernel Overview</h2>
70:
71: <h3>Kernel Structure</h3>
72: <p>
73: The following figure illustrates the Prex kernel structure.
74: </p>
75: <p>
76: <img alt="Kernel Components" src="img/kernel.gif" border="1"
77: style="width: 602px; height: 414px;"><br>
78:
79: <i><b>Figure 1. Prex kernel Structure</b></i>
80: </p>
81: <p>
82: A kernel object belongs in one of the following groups.
83: </p>
84: <ul>
85: <li><b>kern</b>: kernel core components</li>
86: <li><b>mem</b>: memory managers</li>
87: <li><b>ipc</b>: inter process communication (*)</li>
88: <li><b>sync</b>: synchronize objects</li>
89: <li><b>arch</b>: architecture dependent components</li>
90: </ul>
91: <p>
92: <i>*) Since all messages in Prex are transferred among threads, the name of
93: "IPC" is not appropriate.
94: However, "IPC" is still used as a general term of the message transfer
95: via the kernel, in Prex.</i>
96: </p>
97:
98: <h3>Naming Convention</h3>
99: <p>
100: The name of "group/object" in figure 1 is mapped to "directory/file" in the
101: Prex source tree. For example, the thread related functions are located
102: in "kern/thread.c", and the functions for semaphore are placed
103: in "sync/sem.c".
104: </p>
105: <p>
106: In addition, there is a standard naming convention about kernel
107: routines. The method named <i>bar</i> for the object named <i>foo</i>
108: should be named "foo_bar". For example, the routine to create a new
109: thread is named "thread_create", and locking mutex will be "mutex_lock".
110: This rule is not applied to the name of the local function.
111: </p>
112:
113:
114: <h2 id="design">Design Policy</h2>
115: <p>
116: The Prex kernel focuses the following points to be designed.
117: </p>
118: <ul>
119: <li>Portability</li>
120: <li>Scalability</li>
121: <li>Reliability</li>
122: <li>Interoperability</li>
123: <li>Maintainability</li>
124: </ul>
125:
126: <h3>Portability</h3>
127: <p>
128: The Prex kernel is divided into two different layers -
129: a common kernel layer and an architecture dependent layer.
130:
131: Any routine in the common kernel layer must not access to the H/W by itself.
132: Instead, it must request it to the architecture dependent layer.
133: The interface to the architecture dependent layer is strictly defined
134: by the Prex kernel. This interface is designed carefully to support various
135: different architecture with minimum code change.
136: So, it is easy to port the Prex kernel to different architecture.
137: </p>
138: <p>
139: The following functions must be provided by the architecture dependent layer.
140: </p>
141: <ul>
142: <li><b>CPU</b>: initializes processor registers before kernel boot</li>
143: <li><b>Context</b>: abstracts processor and hardware context</li>
144: <li><b>MMU</b>: abstracts memory management unit (*)</li>
145: <li><b>Trap</b>: abstracts processor trap</li>
146: <li><b>Interrupt</b>: abstracts the interrupt control unit</li>
147: <li><b>Clock</b>: abstracts clock timer unit</li>
148: <li><b>Misc.</b>: abstracts system reset, idle power state</li>
149: </ul>
150: <p>
151: <i>*) In case of no-MMU system, MMU related routines will be
152: defined as no-operation routine.
153: So, the kernel common layer can not assume MMU is always available.</i>
154: </p>
155:
156: <h3>Scalability</h3>
157: <p>
158: In order to obtain higher scalability, the kernel does not limit the maximum
159: number of the kernel objects to create.
160: So, the resource for all kernel objects are allocated dynamically after
161: system boot.
162: This can keep the memory prerequisite smaller than the static
163: resource allocation.
164: This means that the kernel can create task, thread, object, device,
165: event, mutex, timer as many as usable memory remains.
166: </p>
167: <p>
168: The kernel supports both of MMU and No-MMU systems. So, most of the kernel
169: components and VM sub-system are designed carefully to work without MMU.
170: </p>
171:
172: <h3>Reliability</h3>
173: <p>
174: When the remaining memory is exhausted, what should OS do?
175: If the system can stop with panic() there, the error checks of many
176: portions in the kernel are not necessary.
177: But obviously, this is not allowed with the reliable system.
178: Even if the memory is exhausted,
179: a kernel must continue processing.
180: So, all kernel code is checking the error status returned
181: by the memory allocation routine.
182: </p>
183: <p>
184: In addition, the kernel must not crush anytime even if any invalid parameter
185: is passed via kernel API. Basically, the Prex kernel code is written with
186: "garbage in, error out" principle.
187: The Prex kernel never stops even if any malicious
188: program is loaded.
189: </p>
190:
191: <h3>Interoperability</h3>
192: <p>
193: Although the Prex kernel was written from scratch, its applications
194: will be brought from the other operating systems like BSD. So, the system
195: call interface is designed with consideration to support general OS
196: API like POSIX or APIs for generic RTOS.
197: </p>
198: <p>
199: The error code for the Prex system call is defined as the same name
200: with POSIX. For example, EINVAL for "Invalid argument", or ENOMEM for
201: "Out of memory". So, peoples do not have to study new error codes if
202: they already have skills about POSIX programming.
203: This is important point to write applications and to read
204: the kernel code because study of a new error scheme will cause pain
205: for developers.
206:
207: In addition, it simplify the POSIX emulation library because it
208: does not have to remap the error code.
209: </p>
210:
211: <h3>Maintainability</h3>
212: <p>
213: All kernel codes are kept clean and simple for the maintenance.
214: All codes are well-commented and consistent.
215: It is easy to add or remove new system call into the kernel.
216: The kernel has the debugging facility like the function trace or
217: the dump of the kernel objects.
218: </p>
219:
220:
221: <h2 id="thread">Thread</h2>
222:
223: <h3>Thread Control Block</h3>
224: <p>
225: The thread control block includes data for
226: owner task, scheduler, timer, IPC, exception, mutex, and context.
227: The following thread structure is most important definition
228: in the kernel codes.
229: </p>
230: <pre>
231: struct thread {
232: int magic; /* magic number */
233: task_t task; /* pointer to owner task */
234: struct list task_link; /* link for threads in same task */
235: struct queue link; /* linkage on scheduling queue */
236: int state; /* thread state */
237: int policy; /* scheduling policy */
238: int prio; /* current priority */
239: int base_prio; /* base priority */
240: int ticks_left; /* remaining ticks to run */
241: u_int total_ticks; /* total running ticks */
242: int need_resched; /* true if rescheduling is needed */
243: int lock_count; /* schedule lock counter */
244: int suspend_count; /* suspend counter */
245: struct event *sleep_event; /* sleep event */
246: int sleep_result; /* sleep result */
247: struct timer timeout; /* thread timer */
248: struct timer *periodic; /* pointer to periodic timer */
249: struct queue ipc_link; /* linkage on IPC queue */
250: void *msg_addr; /* kernel address of IPC message */
251: size_t msg_size; /* size of IPC message */
252: struct thread *sender; /* thread that sends IPC message */
253: struct thread *receiver; /* thread that receives IPC message */
254: object_t send_obj; /* IPC object sending to */
255: object_t recv_obj; /* IPC object receiving from */
256: uint32_t exc_bitmap; /* bitmap of pending exceptions */
257: struct list mutexes; /* mutexes locked by this thread */
258: struct mutex *wait_mutex; /* mutex pointer currently waiting */
259: void *kstack; /* base address of kernel stack */
260: struct context context; /* machine specific context */
261: };</pre>
262:
263: <h3>Thread Creation</h3>
264: New thread can be created by thread_create().
265: The initial states of newly created thread are as follow:
266: <p>
267: </p>
268:
269: <i><b>Table 1. Initial thread state</b></i>
270: <table border="1" width="60%" cellspacing="0">
271: <tbody>
272: <tr>
273: <th>Data type</th>
274: <th>Initial state</th>
275: </tr>
276: <tr>
277: <td>Owner Task</td>
278: <td>Inherit from parent thread</td>
279: </tr>
280: <tr>
281: <td>Thread state</td>
282: <td>Suspended</td>
283: </tr>
284: <tr>
285: <td>Suspend count</td>
286: <td>Task suspend count + 1</td>
287: </tr>
288: <tr>
289: <td>Scheduling policy</td>
290: <td>Round Robin</td>
291: </tr>
292: <tr>
293: <td>Scheduling Priority</td>
294: <td>Default (= 200)</td>
295: </tr>
296: <tr>
297: <td>Time quantum</td>
298: <td>Default (= 50 msec)</td>
299: </tr>
300:
301: <tr>
302: <td>Processor registers</td>
303: <td>Default value</td>
304: </tr>
305:
306: </tbody>
307: </table>
308:
309: <p>
310: Since new thread is initially set to the suspended state, thread_resume()
311: must be called to start it.
312: </p>
313:
314: <p>
315: Creating a thread and loading its register state are isolated
316: in different routines. These two routines are used by fork(), exec(),
317: and pthread_create() in the POSIX emulation library.
318: </p>
319:
320: <i><b>Table 2. Usage of thread_create()/thread_load()</b></i>
321: <table border="1" width="80%" cellspacing="0">
322: <tbody>
323: <tr>
324: <th>Library routine</th>
325: <th>thread_create()</th>
326: <th>thread_load()</th>
327: </tr>
328: <tr>
329: <td>fork()</td>
330: <td align="center">O</td>
331: <td align="center">X</td>
332: </tr>
333: <tr>
334: <td>exec()</td>
335: <td align="center">X</td>
336: <td align="center">O</td>
337: </tr>
338: <tr>
339: <td>pthread_create()</td>
340: <td align="center">O</td>
341: <td align="center">O</td>
342: </tr>
343: </tbody>
344: </table>
345:
346: <h3>Thread Termination</h3>
347: <p>
348: The kernel will usually release all resources owned by the terminated thread.
349: But, there are some complicated process to release the resources.
350: The priority adjustment may be required if the thread inherits its
351: priority.
352: </p>
353: <p>
354: If the thread is terminated with mutex locking, all threads waiting for
355: that mutex does sleep forever. So, the mutex held by the terminated thread
356: must be unlocked, or change its mutex owner if some thread is waiting for.
357:
358: </p>
359: <p>
360: In general, there is a known issue about the thread termination.
361: If the termination target is current thread, the kernel can not release
362: the context of the current thread because the
363: thread switching always requires the current context.
364: There are the following 3 solutions for this.
365: </p>
366: <ol>
367: <li>Create "clean up thread" to terminate thread</li>
368: <li>Add condition check in thread switching code</li>
369: <li>Defer termination in next termination request</li>
370: </ol>
371: The Prex kernel is using #3.
372:
373: <h3>Thread Suspension</h3>
374: <p>
375: Each thread can be set to the suspended state by using thread_suspend()
376: interface.
377: Although a thread can be suspended any number of times,
378: it does not start to run unless it is resumed by the same
379: number of suspend.
380: </p>
381:
382: <h3>Kernel Thread</h3>
383: <p>
384: A kernel thread is always executed in kernel mode, and it does not have user
385: mode context.
386: The scheduling policy is set to SCHED_FIFO by default.
387: </p>
388: <p>
389: Currently, the following kernel threads are running in kernel mode.
390: </p>
391: <ul>
392: <li>Interrupt Service Threads</li>
393: <li>Timer Thread</li>
394: <li>Idle Thread</li>
395: <li>DPC Thread</li>
396: </ul>
397:
398: <h3>Idle Thread</h3>
399: <p>
400: An idle thread runs when no other thread is active.
401: It has the role of cutting down the power consumption of a system.
402: An idle thread has FIFO scheduling policy, and it does not
403: have time quantum.
404: The lowest scheduling priority (=255) is reserved for an idle thread.
405: </p>
406:
407: <h2 id="task">Task</h2>
408:
409: <h3>Task Creation</h3>
410: <p>
411: The task can be created by using task_create().
412: New child task will have the same memory image with the parent task.
413: Especially text region and read-only region are physically
414: shared among them.
415: The parent task receives the new task ID of child task from task_create(), but
416: child task will receive 0 as task ID.
417: </p>
418: <p>
419: The initial task states are as follow:
420: </p>
421:
422: <i><b>Table 3. Initial task state</b></i>
423: <table border="1" width="60%" cellspacing="0">
424: <tbody>
425: <tr>
426: <th>Data type</th>
427: <th>Inherit from parent task?</th>
428: </tr>
429:
430: <tr>
431: <td>Object List</td>
432: <td align="center">No</td>
433: </tr>
434:
435: <tr>
436: <td>Threads</td>
437: <td align="center">No</td>
438: </tr>
439:
440: <tr>
441: <td>Memory Map</td>
442: <td align="center">Yes</td>
443: </tr>
444:
445: <tr>
446: <td>Suspend Count</td>
447: <td align="center">No</td>
448: </tr>
449:
450: <tr>
451: <td>Exception Handler</td>
452: <td align="center">Yes</td>
453: </tr>
454:
455: </tbody>
456: </table>
457:
458: <p>
459: If the parent task is specified as NULL for task_create(),
460: all child state are initialized to default.
461: This is used in exec() emulation.
462: </p>
463:
464: <h3>Task Suspension</h3>
465: <p>
466: When the task is set to suspend state, the thread suspend count of all threads
467: in the task is also incremented.
468: A thread can start to run only when both of the thread suspend count
469: and the task suspend count becomes 0.
470: </p>
471:
472: <h3>Kernel Task</h3>
473: <p>
474: The kernel task is a special task that has only an idle thread
475: and interrupt threads. It does not have any user mode memory.
476: </p>
477:
478: <h2 id="sched">Scheduler</h2>
479: <h3>Thread Priority</h3>
480: <p>
481: The Prex scheduler is based on the algorithm known as priority based
482: multi level queue. Each thread is assigned the priority between
483: 0 and 255. The lower number means higher priority like BSD unix.
484: It maintains 256 level run queues mapped to each priority.
485: The lowest priority (=255) is used only for an idle thread.
486: </p>
487: <p>
488: A thread has two different types of priority:
489: </p>
490: <ul>
491: <li><b>Base priority:</b>
492: This is a static priority which can be changed only by user mode program.
493: <li><b>Current Priority:</b>
494: An actual scheduling priority.
495: A kernel may adjust this priority dynamically if it's needed.
496: </ul>
497: <p>
498: Although the base priority and the current priority are same value in almost
499: conditions,
500: kernel will sometimes change the current priority to avoid
501: "priority inversion".
502: </p>
503:
504: <h3>Thread State</h3>
505: <p>
506: Each thread has one of the following states.
507: </p>
508:
509: <ul>
510: <li><b>RUN</b> :Running or ready to run</li>
511: <li><b>SLEEP</b> :Sleep for some event</li>
512: <li><b>SUSPEND</b> :Suspend count is not 0</li>
513: <li><b>EXIT</b> :Terminated</li>
514: </ul>
515: <p>
516: The thread is always preemptive even in kernel mode.
517: There are following 4 events to switch thread:
518: </p>
519:
520: <i><b>Table 4. Events to switch thread</b></i>
521: <table border="1" width="90%" cellspacing="0">
522: <tbody>
523: <tr>
524: <th>Event</th>
525: <th>Condition</th>
526: <th>Run queue position</th>
527: </tr>
528: <tr>
529: <td><b>Block</b></td>
530: <td>Thread sleep or suspend</td>
531: <td>Move to the tail of runq</td>
532: </tr>
533: <tr>
534: <td><b>Preemption</b></td>
535: <td>Higher priority thread becomes runnable</td>
536: <td>Keep the head of runq</td>
537: </tr>
538: <tr>
539: <td><b>Quantum Expiration</b></td>
540: <td>The thread consumes its time quantum</td>
541: <td>Move to the tail of runq</td>
542: </tr>
543: <tr>
544: <td><b>Yield</b></td>
545: <td>The thread releases CPU by itself</td>
546: <td>Move to the tail of runq</td>
547: </tr>
548:
549: </tbody>
550: </table>
551:
552: <h3>Scheduling Policy</h3>
553: <p>
554: There are following three types of scheduling policy.
555: </p>
556: <ul>
557: <li><b>SCHED_FIFO</b>: First-in First-out
558: <li><b>SCHED_RR</b>: Round Robin (SCHED_FIFO + timeslice)
559: <li><b>SCHED_OTHER</b>: Not supported
560: </ul>
561: <p>
562: In early Prex development phase, SCHED_OTHER was implemented as a traditional
563: BSD scheduler. Since this scheduler changes the thread priority dynamically,
564: it is unpredictable and does not fit the real-time system.
565: Recently, SCHED_OTHER policy was dropped from Prex to
566: focus on real-time platform.
567: </p>
568:
569: <h3>Scheduling Parameter</h3>
570: <p>
571: An application program can change the following scheduling parameters via
572: kernel API.
573: </p>
574: <ul>
575: <li>Thread Priority</li>
576: <li>Scheduling Policy</li>
577: <li>Time Quantum (only for SCHED_RR)</li>
578: </ul>
579:
580: <h3>Scheduling Lock</h3>
581: <p>
582: The thread scheduling can be disabled by locking the scheduler.
583: This is used to synchronize the thread execution to protect the
584: access to the global resources.
585: Since any interrupt handler can work while scheduling lock state,
586: it does not affect to the interrupt latency.
587: </p>
588:
589: <h3>Named Event</h3>
590: <p>
591: The thread can sleep/wakeup for the specific event. The event works as
592: the queue of the sleeping threads. Since each event has its name,
593: it is easy to know which event the debugee is waiting for.
594: </p>
595:
596:
597: <h2 id="memory">Memory Management</h2>
598:
599: <h3>Physical Page Allocator</h3>
600: <p>The physical page allocator provides the service for
601: page allocation/deallocation/reservation.
602: It works on the bottom layer for other memory managers.
603: </p>
604: <p>
605: <img alt="Memory Structure" src="img/memory.gif" border="1"
606: style="width: 448px; height: 308px;"><br>
607:
608: <i><b>Figure 2. Prex Memory Structure</b></i>
609: </p>
610: <p>
611: The key point is that Prex kernel does not page out to
612: any external disk devices. This is an important design point to get
613: real-time performance and system simplicity.
614:
615: </p>
616:
617: <h3>Kernel Memory Allocator</h3>
618: <p>
619: The kernel memory allocator is optimized for the small
620: memory foot print system.
621: </p>
622: <p>
623: To allocate kernel memory, it is necessary to divide one page into
624: two or more blocks.
625: There are following 3 linked lists to manage used/free blocks for kernel
626: memory.
627: <ol>
628: <li>All pages allocated for the kernel memory are linked.</li>
629: <li>All blocks divided in the same page are linked.</li>
630: <li>All free blocks of the same size are linked.</li>
631: </ol>
632: <p>
633: Currently, it can not handle the memory size exceeding one page.
634: Instead, a driver can use page_alloc() to allocate large memory.
635: <br>
636: When the kernel code illegally writes data into non-allocated memory,
637: the system will crash easily. The kmem modules are called from
638: not only kernel code but from various drivers. In order to
639: check the memory over run, each free block has a tag with magic ID.
640: </p>
641: <p>
642: The kernel maintains the array of the block headers for the free blocks.
643: The index of an array is decided by the size of each block.
644: All block has the size of the multiple of 16.
645: </p>
646: <pre>free_blks[0] = list for 16 byte block
647: free_blks[1] = list for 32 byte block
648: free_blks[2] = list for 48 byte block
649: .
650: .
651: free_blks[255] = list for 4096 byte block
652: </pre>
653: <p>
654: In generic design, only one list is used to search the free block
655: for a first fit algorithm.
656: However, the Prex kernel memory allocator is using multiple lists
657: corresponding to each block size.
658: A search is started from the list of the requested size. So,
659: it is not necessary to search smaller block's list wastefully.
660: </p>
661: <p>
662: In most of the "buddy" based memory allocators, their algorithm are
663: using <b>2^n</b> bytes as block size.
664: But, this logic will throw away much memory in case
665: the block size is not fit. So, this is not suitable for the
666: embedded systems that Prex aims to.
667: </p>
668:
669: <h3>Virtual Memory Manager</h3>
670: <p>
671: A task owns its private virtual address space. All threads
672: in a same task share one memory space.
673: When new task is made, the address map of the parent task will be
674: automatically copied.
675: In this time, the read-only space is not copied and is shared with old map.
676: </p>
677: <p>
678: The kernel provide the following functions for VM:
679: </p>
680: <ul>
681: <li>Allocate/deallocate memory region</li>
682: <li>Change memory attribute (read/write/exec)</li>
683: <li>Map another task's memory to current task</li>
684: </ul>
685: <p>
686: The VM allocator is using the traditional list-based algorithm.
687: </p>
688: <p>
689: The kernel task is a special task which has the virtual memory mapping
690: for kernel. All other user mode tasks will have the same kernel memory
691: image mapped from the kernel task. So, kernel threads can work with the
692: all user mode task context without switching memory map.
693: </p>
694: <p>
695: <img alt="Memory Mapping" src="img/memmap.gif" border="1"
696: style="width: 504px; height: 271px;"><br>
697:
698: <i><b>Figure 3. Kernel Memory Mapping</b></i>
699: </p>
700:
701: <p>
702: Since the Prex kernel does not do page out to an external storage,
703: it is guaranteed that the allocated memory is always continuing
704: and existing. Thereby, a kernel and drivers can be constructed
705: very simply.
706: </p>
707: <p>
708: <i>Note: "Copy-on-write" feature was supported with the Prex kernel before.
709: But, it was dropped to increase the real-time performance.</i>
710: </p>
711:
712:
713: <h2 id="ipc">IPC</h2>
714: <p>
715: The message passing model of Prex is very simple compared with other
716: modern microkernels. The Prex message is sent to the "object" from thread
717: to thread.
718: The "object" in Prex is similar concept that is called as "port"
719: in other microkernel.
720: </p>
721:
722: <h3>Object</h3>
723: <p>
724: An object represents service, state, or policies etc.
725: For object manipulation, kernel provide 3 functions:
726: object_create(), object_delete(), object_lookup().
727: Prex task will create an object to publish its interface to other tasks.
728: For example, server tasks will create objects like "proc", "fs", "exec" to
729: allow clients to access their service.
730: And then, client tasks will send a request message to these objects
731: </p>
732: <p>
733: An actual object is stored in kernel space, and it is protected
734: from user mode code.
735: Each object data is managed with the hash table by using its name string.
736: Usually, an object has a unique name within a system. To send a
737: message to the specific object, it must obtain the target object ID
738: by looking up by the name.
739: </p>
740: <p>
741: An object can be created without its name. These objects can be used as
742: private objects for threads in same task.
743: </p>
744:
745: <h3>Message</h3>
746: <p>
747: Each IPC message must have the pre-defined message header in it.
748: The kernel will store the sender task's ID into the message header.
749: This mechanism ensures the receiver task can get the exact task ID
750: of the sender task. Therefore, receiver task can check the sender
751: task's capability for various secure services.
752: </p>
753: <p>
754: It is necessary to recognize the pre-defined message format between
755: sender and receiver.
756: </p>
757: <p>
758: Messages are sent to the specific object using msg_send().
759: The transmission of a message is always synchronous. This means that
760: the thread which sent the message is blocked until it receives
761: a response from another threads. msg_receive() performs reception
762: of a message. msg_receive() is also blocked when no message is
763: reached to the target object. The receiver thread must answer the
764: message using msg_reply() after it finishes processing.
765: </p>
766: <p>
767: The receiver thread can not receive another message until it
768: replies to the sender. In short, a thread can receive only one
769: message at once. Once the thread receives message, it can send
770: another message to different object. This mechanism allows threads
771: to redirect the sender's request to another thread.
772: </p>
773: <p>
774: A thread can receive a message from the specific object which is
775: created by itself or thread in same task.
776: If the message has not arrived, it
777: blocks until any message comes in. The following figure shows the IPC transmit
778: sequence of Prex.
779: </p>
780:
781: <img alt="ipc queue" src="img/msg.gif" border="1"
782: style="width: 505px; height: 347px;"><br>
783:
784: <i><b>Figure 4. IPC Transmit Sequence</b></i>
785:
786: <h3>Message Transfer</h3>
787: <p>
788: The message is copied to task to task directly without kernel
789: buffering. The memory region of sent message is
790: automatically mapped to the receiver's memory within kernel.
791: This mechanism allows to reduce the number of copy time while message
792: translation.
793: Since there is no page out of memory in Prex, we can
794: copy the message data via physical memory at anytime.
795: </p>
796: <img alt="Message transfer" src="img/ipcmap.gif" border="1"
797: style="width: 459px; height: 321px;"><br>
798:
799: <i><b>Figure 5. IPC message transfer</b></i>
800:
801: <h2 id="except">Exception Handling</h2>
802: <p>
803: A user mode task can specify its own exception handler with exception_setup().
804: There are two different types of exception.
805: </p>
806: <ul>
807: <li><b>H/W exception</b>:
808: This type of exception is caused by H/W trap & fault. The exception
809: will be sent to the thread which caused the trap.
810: If no exception handler is specified by the task, it will be
811: terminated by kernel.</li>
812:
813: <li><b>S/W exception</b>:
814: The user mode task can send S/W exception to another task by exception_raise().
815: The exception
816: will be sent to the thread that is sleeping with exception_wait().
817: If no thread is waiting for the exception, the exception is sent
818: to the first thread in the target task.</li>
819: </ul>
820: <p>
821: Kernel supports 32 types of exception.
822: The following pre-defined exceptions are raised by kernel itself.
823: </p>
824:
825: <i><b>Table 5. Kernel exceptions</b></i>
826: <table border="1" width="80%" cellspacing="0">
827: <tbody>
828: <tr>
829: <th>Exception</th>
830: <th>Type</th>
831: <th>Reason</th>
832: </tr>
833: <tr>
834: <td>SIGILL</td>
835: <td align="center">H/W</td>
836: <td>Illegal instruction</td>
837: </tr>
838: <tr>
839: <td>SIGTRAP</td>
840: <td align="center">H/W</td>
841: <td>Break point</td>
842: </tr>
843: <tr>
844: <td>SIGFPE</td>
845: <td align="center">H/W</td>
846: <td>Math error</td>
847: </tr>
848: <tr>
849: <td>SIGSEGV</td>
850: <td align="center">H/W</td>
851: <td>Invalid memory access</td>
852: </tr>
853: <tr>
854: <td>SIGALRM</td>
855: <td align="center">S/W</td>
856: <td>Alarm event</td>
857: </tr>
858: </tbody>
859: </table>
860:
861: <p>
862: POSIX emulation library will setup its own exception handler to convert
863: the Prex exceptions into UNIX signals. It will maintain its own signal mask.
864: And, it transfer control to the actual POSIX signal handler that is
865: defined by the user mode process.
866:
867: </p>
868:
869: <h2 id="int"> Interrupt Framework</h2>
870: <p>
871: Prex defines two different types of interrupt service to
872: optimize the response time of real-time operation.
873: </p>
874:
875: <h3>Interrupt Service Routine (ISR)</h3>
876: <p>
877: ISR is started by an actual hardware interrupt. The associated
878: interrupt is disabled in ICU and CPU interrupt is enabled
879: while it runs. If ISR determines that its device generates
880: the interrupt, ISR must program the device to stop the interrupt.
881: Then, ISR should do minimum I/O operation and return control
882: as quickly as possible.
883: ISR will run within the context of current running thread at
884: interrupt time. So, only few kernel services are available within
885: ISR. IRQ_ASSERT() macro can be used to detect the invalid
886: function call from ISR.
887: </p>
888:
889: <h3>Interrupt Service Thread (IST)</h3>
890: <p>
891: IST is automatically activated if ISR returns INT_CONTINUE to kernel. It
892: will be called when the system enters safer condition than ISR.
893: Any interrupt driven I/O operation should be done in IST not ISR.
894: Since ISR for same IRQ may be run during IST, the shared data,
895: resources, and device registers must be synchronized by using
896: irq_lock().
897: IST does not have to be reentrant, since it is not interrupted
898: by same IST itself.
899: </p>
900:
901: <h3>Interrupt Nesting & Priority</h3>
902: <p>
903: Each ISR has its logical priority level, with 0 being the highest
904: priority. While one ISR is running, all lower priority interrupts
905: are masked off.
906: This interrupt nesting mechanism avoids delaying of
907: high priority interrupt events.
908: </p>
909: <p>
910: IST is executed as a normal thread dispatched by the scheduler. So,
911: the interrupt thread which has higher priority is executed first.
912: The driver writer can specify the thread priority of IST when
913: IST is attached to the specific interrupt line.
914: The important point is that even a user mode task can be performed
915: prior to an interrupt thread.
916: </p>
917: <p>
918: The following figure is the sample of the Prex interrupt processing.
919: </p>
920: <p>
921: <img alt="Interrupt Processing" src="img/irq.gif" border="1"><br>
922: <i><b>Figure 6. Prex Interrupt Processing</b></i>
923: </p>
924: <p>
925: </p>
926:
927: <h3>Interrupt Locking</h3>
928: <p>
929: irq_lock() & irq_unlock() are used to disable all interrupts in
930: order to synchronize the access to the kernel or H/W resource. Since irq_lock()
931: increments a lock counter, irq_unlock() will automatically restore
932: to the original interrupt state when locking count becomes 0.
933: So the caller does not have to save the previous interrupt state.
934: </p>
935:
936: <h3>Interrupt Stack</h3>
937: <p>
938: If each ISR uses the kernel stack of the current running thread, the
939: stack area may be over-flow when continuous interrupts are occurred at
940: one same thread. So the kernel stack will be switched to the dedicated stack
941: while ISR is running.
942: </p>
943:
944:
945: <h2 id="timer">Timer</h2>
946:
947: <h3>Kernel Timers</h3>
948:
949: <p>
950: The kernel timer provides the following feature.
951: </p>
952: <ul>
953: <li><b>Sleep timer</b>: Put caller thread to sleep in the specified time.</li>
954: <li><b>Call back timer</b>: Call the routine after specified time passes.</li>
955: <li><b>Periodic timer</b>: Call the routine at the specified interval.</li>
956: </ul>
957:
958: <h3>Timer Jitter</h3>
959:
960: <p>
961: The periodic timer is designed to minimize the deviation between desired and
962: actual expiration.
963: </p>
964:
965: <h2 id="device">Device I/O Service</h2>
966:
967: The Prex device driver module is separated from the kernel, and this module
968: is linked with the kernel at the boot time.
969: The kernel provides only simple and minimum services to help the
970: communication between applications and drivers.
971:
972: <h3>Device Object</h3>
973: <p>
974: Since the Prex kernel does not have the file system in it, the kernel
975: provides a device object service for I/O interface.
976: The device object is created by the device driver to communicate to the
977: application. Usually, the driver creates a device object for an existing
978: physical device. But, it can be used to handle logical or virtual devices.
979: </p>
980:
981: <h3>Driver Interface</h3>
982: <p>
983: The interface between kernel and drivers are defined clearly as
984: "Driver Kernel Interface". The kernel provides the following services
985: for device drivers.
986: </p>
987: <ul>
988: <li>Device object service</li>
989: <li>Kernel memory allocation</li>
990: <li>Physical page allocation</li>
991: <li>Interrupt handling service</li>
992: <li>Scheduler service</li>
993: <li>Timer service</li>
994: <li>Debug service</li>
995: </ul>
996:
997: <h3>Application Interface</h3>
998: <p>
999: The kernel device I/O interface are provided to access the specific device
1000: object which is handled by a driver.
1001: The Prex kernel provides the following 5 functions for applications.
1002: </p>
1003: <ul>
1004: <li>Open a device</li>
1005: <li>Close a device</li>
1006: <li>Read from a device</li>
1007: <li>Write to a device</li>
1008: <li>Device I/O control</li>
1009: </ul>
1010:
1011: <h2 id="mutex">Mutex</h2>
1012: <h3>Priority Inheritance</h3>
1013: <p>
1014: The thread priority is automatically changed at one of the following conditions.
1015: </p>
1016: <ol>
1017: <li>
1018: When the current thread fails to lock the mutex and the mutex
1019: owner has lower priority than current thread, the priority
1020: of mutex owner is boosted to the current priority.
1021: If this mutex owner is waiting for another mutex, such related
1022: mutexes are also processed.
1023: </li>
1024: <li>
1025: When the current thread unlocks the mutex and its priority
1026: has already been boosted, kernel recomputes the current priority.
1027: In this case, the priority is set to the highest
1028: priority among the threads waiting for the mutexes locked by the
1029: current thread.
1030: </li>
1031: <li>
1032: When the priority is changed by the user request, the related(inherited)
1033: thread's priority is also changed.
1034: </li>
1035: </ol>
1036: <p>
1037: There are following limitations about priority inheritance
1038: with Prex mutex.
1039: </p>
1040: <ol>
1041: <li>
1042: If the priority is changed by the user request, the priority
1043: recomputation is done only when the new priority is higher
1044: than old priority. The inherited priority is reset to base
1045: priority when the mutex is unlocked.
1046: </li>
1047: <li>
1048: Even if thread is killed with mutex waiting, the related
1049: priority is not adjusted.
1050: </li>
1051: </ol>
1052: <h2 id="debug">Debug</h2>
1053: There are following debugging support functions:
1054: <ul>
1055: <li>printk(): Display the debug message in kernel.</li>
1056: <li>panic(): Dump processor registers and stop system.</li>
1057: <li>ASSERT(): If expression is false (zero), stop system and display information.</li>
1058: <li>trace_on(): If the kernel trace is enabled, all entry/exit of functions
1059: are logged.
1060: </ul>
1061: </tr>
1062: <tr>
1063: <td id="footer" colspan="2" style="vertical-align: top;">
1064: <a href="http://sourceforge.net">
1065: <img src="http://sourceforge.net/sflogo.php?group_id=132028&type=1"
1066: alt="SourceForge.net Logo" border="0" height="31" width="88"></a><br>
1067: Copyright© 2005-2007 Kohsuke Ohtani
1068: </td>
1069: </tr>
1070:
1071: </tbody>
1072: </table>
1073:
1074: </div>
1075: <div id="bottom"></div>
1076:
1077: </body>
1078: </html>
CVSweb
![[BACK]](/icons/back.gif){kind=icon}
Return to kernel.html CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / prex-old / doc / html / doc