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 :
- New way of handling system /kernel calls
- New message passing system.
- Virtual timers: For keeping up of the time point as when the activity has to be done. Since only one timer is available throughout the system. Hence we have taken an approach of virtual timers in sharing the existing system wide timer.
- Semaphore To guarantee the timely order for the process activities.
- Modified interrupt handling.
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
- kernel to user process
- user process to kernel
- user process to user process message passing schemes.
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:
- Header: Source Destination process number and related information.
- Message content: As in Minix here also process can send any one of the determined structured messages.
- Vtimer: It includes information regarding the timer associated with the message. It has fields for period, action, and watch dog process number. Period tells the interval within which the message has to be processed action is whether to send or receive kind of info.
- Watchdog is the process number which is entrusted with the action to take in case the message cannot be delivered. A message can be requested from kernel with data fields to be filled by the user process that wants to send and the timer period action and watchdog process are also to be provided in the structure by the user. These are provided in the form of kernel calls. For the process to use this they have to be RT process.
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:
- Starts the timer with the specified interval and period.
- Checks to see if the destination is ready to receive.
- If so deliveries the message by copying from sender address space to receiver’s address space and stops the timer.
- If not the sending process is made to wait or allowed to continue or removed from the queue making it unready.
- If the message cannot be delivered on time a message is sent to the watch dog process saying unsuccessful delivery of message, which in turn has to take responsible of either resend or take corrective action.
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 .
- Virtual timers: Real time OS means timely occurrence of events. If something has to be scheduled then they should have timer associated with it but hardware provides only a single timer. Then how to share this. This is made possible by the use of virtual timers. Vtimers are implemented in the form of structure.
This structure has fields like:
- Limit: As how many times this timer can expire.
- Period: Provides the time interval in which this has to be executed.
- Action: Action to be taken is mentioned in this field.
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.
- MRT_vtimer _run is called to run the action of the expired timer.
- MRT_vtimer_flush is the function that is called to check if any timers have expired if so take them to the action center MRT_vtimer_run.
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.
- MRT_vtimer _free: Releases the vtimer back to the kernel.
- MRT_vtimer _set, MRT-vtimer _get: Sets and gets the internal attributes of the vtimer .
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.
- Semaphores: Minix3 lacked semaphores. In fact it didn't had any synchronization construct at all. Semaphore is introduced as a part of the project. Semaphores as we know are the synchronization construct. If several process are committed to single goal and have their critical section where if one process is executing in critical section rest other process should live outside of their respective critical sections in order to prevent race condition. If this has to be enforced among the process they have to be communicated according to some protocol. This requires something from kernel to put forth. Using the existing message passing and the newly introduced semaphore have removed this problem. Semaphore in this project is in the form of structure with the following fields :
- index-semaphore ID
- value-semaphore Value
- priority-Ceiling priority - for future uses
- flags-semaphore policy/status flags
- owner-semaphore owner
- ups-total # of sem up() calls
- downs-total # of sem down() calls
- carrier-the process that currently have the mutex sem
- alloclk-Allocated list link
- locklk-Locked list link
- name- name of the semaphore
- plist-Priority List of waiting process
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:
- Clock Handler: The vtimers are used. Handler has to make a inspection to see if any timers have expired if so they have to be executed.
- SYS_vect interrupt handler: New set of calls called kernel calls. If the callnr is in the range of the kernel call they kernel call handler is to be executed against of calling system call handler.
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
- mrtirq.c
- mrtlib.c
- mrtvt.c
- mrtmsg.c
- mrtsem.c
- mrtproc.c.
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.