About

Project Site

Downloads

Documentation

Kernel Calls

Message Passing

Interrupt Handling

Changes

Realtime Minix

This Page discusses Real Time Minix implemented using Minix3 & Minix4RT.

Minix is miniature micro-kernel operating system with foot print of just a few kilobytes. It is POSIX complaint, efficient kernel that promotes modular approach with just simple system call handling and message passing mechanisms. With a small footprint, Minix is the ideal candidate for microprocessors and microcontrollers of stringent memory requirement. Added to this if Minix is extended as Real time Operating system it would further benefit not only as an educational tool in understanding operating system concept but also as simple realtime OS.

Realtime OS's are built either from scratch or an existing OS is tailored. The second approach is taken in this project. This Realtime Minix is not a complete realtime operating system but just adds certain features that makes Minix as a soft realtime OS.

A process can perform basic activities like put a process to sleep, wake up a sleeping process, send or receive a message, request for something or reply to the request. If these activities of process are timely guaranteed then, by that virtue, the operating system becomes realtime. If the guaranteed service is not timely delivered, concerned process should be warned.

Project Scope

Our project aims to a make all the basic activities like message passing and interrupt handling all timely mannered.

The major modification to the minix3 kernel are :

Let us have brief introduction to all of the above mentioned facts before we can discuss the code change.

Kernel calls

Minix3 has system calls which prepare a message with system call number as its content and deliveries it to the destination waiting process. If the process is unready it is made ready and put into scheduling queue for processing. This is how the system calls are handled. Here it involves a context switch from kernel into destination process which ultimately is a user process .Thus it takes relatively long time in serving system call.

A new approach is used in the project. If a kernel call (against system call) is made to serve entirely inside a kernel instead of sending message to destine process. Example below demonstrates the tradeoff between system calls and kernel calls.

printf is a standard C function. It uses a system call to get the service of displaying output. The printf function invokes file system because the display is in the form of file in POSIX like system
The file system then calls the responsible driver, tty driver in this case for displaying the output. Thus it involves user process, kernel, file system and tty driver.  But if a kernel call directly is made (MRT_PRINT: name of this rtk call) it invokes the tty driver for displaying output. Thus effectively one context switch is saved. This way it improves the performance.

Kernel calls are exactly made as system calls using interrupt int SYS_VECTOR. But they are differentiated using the different set of system call numbers. If the parameter sent is in between the lower and upper bound of the kernel calls, rtK-call handler is invoked in handling that call. The rtk_call handler doesn't deliver the message to the destination process as it was in the system calls. But the kernel calls are said to be limited in their scope. That is they can only perform the predefined actions like wakening a process, put a process to sleep, send a message (Deliberate action to send), receive a message, raise request, reply to request or print a message. Kernel is so modular that new kernel calls can be implemented and recompiled kernel can be used in accessing the new kernel call.
The implemented kernel calls are:

Sl.No Kernel Call Number Description Callnr Value
01 rtk_set2rt used to set to rt mode  0 = mrt_set2rt
02 rtk_set2nrt used to non rt mode back 1 = mrt_set2nrt
03 rtk_sleep put a process to sleep 2 = mrt_sleep
04 rtk_wakeup wake up a process 3 = mrt_wakeup
05 rtk_print printing a message  4 = mrt_print
06 rtk_rqst raise a request 5 = mrt_rqst 
07 rtk_reply-reply reply to a request 6 = mrt_reply
08 rtk_arqst Asynchronous request to send 7 = mrt_arqst
09 rtk_uprqst Rising an up request 8 = mrt_uprqst 
10 rtk_sign signal the process of completion of some activity 9 = mrt_sign
11 rtk_receive recieve message 10 = mrt_rcv 
12 rtk_rqrcv request receive 11 = mrt_rqrcv   
13 rtk_semup semaphore up action 12 = mrt_semup 
14 rtk_semdown semaphore down 13 = mrt_semdown

(Handlers for each of these kernel calls can be found in proc.c of kernel directory of code base )

Caution of using kernel calls are that if a process has to use these calls then it should be an rt process, except for first kernel call mrt_set2rt which converts the NRT process into RT process. Its complimentary call is mrt_set2nrt which converts back to NRT process. If a process is in rt mode it is advisory to call only the kernel calls as they take higher priority than the system calls. Hence if the process stays in RT mode for a longer duration then normal minix operations will lose its performance.

Message passing system

Minix 3 has message passing utility which is present in the kernel as the core of the utility available for processes for communication with each other. Shared memory is not used as Minix3 has continuous allocation scheme where if a new process is forked the required amount of memory is allocated to the process in single chunk. However if the processes are having text segment in common they can be shared. Not in order to make big mess in the change to Minix shared memory is not used. Minix3 didn't provide process to process passing of message. It provides message passing from user process to either to a system task of to a driver task.
But message passing in this project is made look more elegant by providing options like

Not only this, options for raising request to send, receive, asynchronous send receive, non rendezvous message passing and option to request are provided .
In this scheme each process has 15 message queue sorted on priorities. If a priority message has to be sent using high priority provides upper hand against other messages for the same process.
Message queue entry is a structure having fields for:

The kernel calls in this regard are:


rtk_print
rtk_rqst
rtk_reply
rtk_arqst
rtk_uprqst
rtk_receive
rtk_rqrcv


The calls are self explanatory of their purpose.

Kernel on behalf of handling message passing does the following things:

Watch dog by default is kernel process number whose default action is to ignore. But it can be set to any process number by its owner(Message's )who is entrusted with the action to make things right if in the case has gone wrong .

 

This structure has fields like:

But action of the vtimer cannot be arbitrary. It is one of the actions defined in the code base.
The possible actions are as below:

MRT_ACT_NON To execute by a virtual timer: none
MRT_ACT_SCHED To execute by a virtual timer: schedule
MRT_ACT_MSGOWN To send a message to the vtimer owner
MRT_ACT_MSGWDOG To send a message to the process in param field
MRT_ACT_IRQTRIG To trigger and IRQ
MRT_ACT_SNDTO Send time out
MRT_ACT_RCVFR Receive time out
MRT_ACT_WAKEUP Wakeup a slept process
MRT_ACT_DEBUG Print the param field
MRT_ACT_PERIODIC Sched a periodic process idem WAKEUP
MRT_ACT_STOP Block the owner process
MRT_ACT_DOWN Down timeout

vtimers are allocated from kernel by the use of system call vtimer_alloc. The structure of the timer is filled with parameters send to the system call. As on the end of the system call the timer is started by putting this timer into queue of active timers.
Active timers are maintained in the form of queue (MRT_sv.actQ). Each entry in it is the next expiration to occur expressed in clock ticks. And another variable 'expiration 'holds the least clock tick as when the timer nearest to the present clock tick will expire. The clock handler for every clock tick that would be executed is modified to see if any timer has expired. If so then it is removed from active queue and put into queue of expired timers. The expired timers are maintained in the form of queue as active timers are (MRT_sv.expQ). This queue holds the timer that has expired whose actions have yet to be executed. On every restart that function which is called on every context switch to run a new process, check is made to see if any expired timers are present in expired queue of timers. If so they are removed and executed. The action specified in its field is executed as discussed earlier. Like this timely occurrence of events are controlled by the use of vtimers.

Vtimers has also priorities. If 2 timers has expired then the timer of higher priority is executed first than the other timers in the queue. Thus the active queue is single list. whereas the expired queue of timers is priority queue of 15 queues corresponding to the 15 priorities.

A process can have any number of timers associated with it. But the global number of timers is restricted. vtimers are also used by the message passing system as described in previous section.

 

Structure would look like:


struct MRT_sem_s {
int                     index;  
int                     value;   
priority_t           priority;
unsigned int       flags;    
int                     owner;
long                   ups;      
long                  downs;
MRT_proc_t    *carrier;              

link_t                alloclk; 
link_t                locklk;

char                  name[MAXPNAME];
plist_t               plist;     
};

MRT_sem_alloc is used to allocate a semaphore .
Semaphore here is effectively same as you have studied. It provides options for up and down. If in the case it cannot up the process, the process is removed from the ready queue and put on the list of blocked process with the associated semaphore. If down is called and check is made if any waiting process is present it made woken up by putting it back into ready queue. Semaphore Up and Semaphore Down are the function central to its working.

Interrupt handling

Interrupts are frequent if the time spent in serving the interrupt is controlled lot more events will be under control. The processing at every interrupt handlers is just like to prepare a message and wake up the destination process. This is very simple and doesn't require enough time but the time to react to the interrupt by the destination is postponed thus a weak response. However the system gets ready to accept the next interrupt. This is similar to bottom half and top half approach to the interrupt handler. Minix 3 Thus had an acceptable behavior in this regard. But the handlers for clock interrupt and system call interrupt are changed for:

The Restart function is modified. This is the context switch procedure called to run the newly selected process. The restart is modified to checks if any pending interrupts or timers are there if so they are executed before the new process is run. Interrupts can be delayed by putting them to queue and timer associated with it. If the interrupts are real time they have priority higher than ordinary interrupts. Interrupts can be event or time driven. Event driven interrupts are those generated by the devices. Time driven interrupts are those not generated by the devices but they are tied with timers to be executed timely driven passion. Interrupts can be postponed for their processing and timer if so have expired the handler is invoked as in the case .

 

Code Changes

Let us discuss the code base for the change we have made.

                                                
The new files added are

Let us start with mpx386.s
Here restart is changed to call one more function MRT_flush_int to check if any pending interrupts need to be serviced. Interrupt handler for interrupts from 1 to 15 are changed to call function MRT_IRQ_dispatch instead of intr_handle But the function MRT_IRQ_dispatch  in turn will call  intr_handle  which in turn call the requested handler for serving the request. A part from this MRT_IRQ_dispatch  we will update interrupt statistics. MRT_IRQ_dispatch   is in the file mrtirq.c

mrtirq.c

This file contains function for interrupt handling. As said earlier there event driven interrupts and time driven interrupts. Some are served as they occur others are scheduled. They are serviced by the function MRT_IRQ_dispatch in mrtirq.c
MRT_irqd_flush flushes interrupts pending.
MRT_vtimer_flush flushes pending timers.
MRT_do_handler is called by MRT_IRQ_dispatch for serving the interrupt.
MRT_irqd_rst is to reset the interrupt descriptor structure that contains the required info regarding the interrupt.
Rests are the auxiliary functions their names are self explanatory.

mrtlib.c

This file contains auxiliary functions used by the other functions in other files. They involve function to insert and delete elements from the priority queue.

mrtproc.c

This file Contains rtk_call for handling the kernel calls. Handlers for kernel calls are found in this file like: rtk_set2nrt
rtk_set2rt
rtk_sleep
rtk_wakeup
rtk_print
rtk_semdown and others.

It contains functions to initialize the process table attributes.

Changes in main.c

Except for calling a function to initialize the process tables and the interrupt descriptor rest of the file remains same. MRT_proc_init is called in initializing the process table.

Changes in  interrupt .c

Here put_irq_handler is changed such that the real attributes of the interrupts are also set such that they are updated on every service of that interrupt. A new function spurious_irq_handler is added to initialize the vector table of unused interrupts.

Changes in clock.c

This file contains the function for handling the clock interrupt. This is changed to check if any active timer is about to expire. If so it removed and added to expired queue.

mrtvt.c

This file has the functions for handling virtual timers. They are:
MRT_vtimer_rmv removes a timer from a queue specified in the parameter.

MRT_timer_set sets the values for the timer.
MRT_act_none
MRT_act_sched
MRT_act_msgown
MRT_act_msgwdog
MRT_act_irqtrig
MRT_act_rcvfr
MRT_act_wakeup
MRT_act_debug
MRT_act_sndrcv
MRT_act_stop
MRT_act_down are the action handlers called for the expired timers which in turn call their respective functional procedures in other files.

 

mrtmsg.c

This file contains procedure for the message passing system.
rtk_receive for receiving the message.
rtk_rqst raise request.
rtk_arqst asynchronous request and other functions that are self explanatory.
MRT_mpool_init: initializing message pool of empty request.
MRT_mqe_rst: initialize the message queue entry.
MRT_msgQ_init initialize message queue.

mrtsem.c

Semaphore handling routines are put in this file.
MRT_spool_init: This function initializes the semaphore pool.
MRT_sem_alloc: Allocates the semaphore.
MRT_sem_free: Frees the semaphore.

Changes in system.c

Here new system call and its handlers are included.

Changes in types.h in kernel

This file contains the types required by the real time operating system.

 

About

This project is developed by RT team. The main developers are Vivek YS, Bhuvan L, Ashrith G, Aditya DSVN. I would like to thank Mr. Ajay Kumar KS who has designed the logo.This project is done under the guidance of Dr. Kris Kumar of PESIT Bangalore. We are the final semester computer science students of PESIT Bangalore.



SourceForge.net Logo