Inhibiting starvation in a multitasking operating system

Details Inhibiting starvation in a multitasking operating system Inhibiting starvation in a multitasking operating system

2000-06-28

2004-02-03

Banankhah, Majid (Department: 2127)

Electrical computers and digital processing systems: virtual mac

Task management or control

C718S102000

Reexamination Certificate

active

06687903

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This application relates to the field of computer operating systems and more particularly to the field of multitasking-based operating systems that may be used on a microprocessor.
2. Description of Related Art
Operating systems may be used to facilitate sharing of a processor among a variety of separate processes. The operating system manages the sharing of the processor by providing each process with separate time slices for executing code.
For microprocessors, and for microprocessors used in device oriented applications, such as for data communication, it is often useful to provide an operating system that can manage processor sharing among the processes that handle different aspects of running the device. However, such operating systems may provide a number of drawbacks, such as requiring a significant amount of stack space that needs to be managed for each separate process. In addition, different mechanisms may be used for preempted task swapping (i.e., task swapping that uses interrupts) versus cooperative task swapping (i.e., processes relinquish the processor voluntarily). Furthermore, many operating systems are hardware and architecture specific so that an operating system implemented on one processor may not be easily be ported to another processor.
In addition, even in instances where it would be advantageous to use multiple process schedulers, many operating systems use a single process scheduler because of difficulties associated with changing process schedulers during run time. Context swapping in these operating systems may be cumbersome and, when both cooperative and preemptive techniques are used together, it may be difficult to avoid process starvation of a current process that is swapped in when a previous process voluntarily relinquishes the processor and the current process is subsequently preempted.
It is desirable to provide an operating system that overcomes the deficiencies discussed above.
SUMMARY OF THE INVENTION
According to the present invention, inhibiting process starvation in a multitasking operating system includes providing a first type of scheduling event at periodic timer intervals, providing a second type of second scheduling event in response to a running processes voluntarily relinquishing the processor, and, in response to a scheduling event, replacing an old process with a new process only if the old process has run for more than a predetermined amount of time. The predetermined amount of time may be one half of the timer interval. Further included may be determining if the old process has run for more than a predetermined amount of time by using clock slice checking. Further included may be determining if the old process is running in response to a second type of scheduling event and setting a flag in response thereto. Further included may be determining if the old process has run for more than a predetermined amount of time by checking the state of the flag. Further included may be, if the flag has been set, rerunning the old process in response to a first type of scheduling event. Further included may be clearing the flag following rerunning the old process. Further included may be, if the flag has been set and the old process has run for less than the predetermined amount of time, rerunning the old process in response to a first type of scheduling event. Further included may be clearing the flag following rerunning the old process. Further included may be determining if the old process is running in response to a second type of scheduling event and if the old process has run for less than the predetermined amount of time and setting a flag in response thereto. Further included may be determining if the old process has run for more than a predetermined amount of time by checking the state of the flag. Further included may be, if the flag has been set, rerunning the old process in response to a first type of scheduling event. Further included may be clearing the flag following rerunning the old process. The predetermined amount of time may be one half of a timer interval.
The system described herein provides a small kernel that can run on a variety of hardware platforms, such as a PowerPC based Symmetrix adapter board used in a Symmetrix data storage device provided by EMC Corporation of Hopkinton, Mass. The core kernel code may be written for the general target platform, such as the PowerPC architecture. Since the PowerPC implementation specific modules are well defined, the system may be quite portable between PowerPC processors (such as the 8260 and 750), and should prove relatively easy to port to any PowerPC based Symmetrix adapter board/CPU combination. The kernel may also be ported to run on other RISC machines (Hitachi SH series) and can be ported to CISC architectures.
The system described herein may be implemented using approximately 8000 lines of commented source code and approximately 1200 lines of assembly code (e.g., PowerPC assembly code) that may be used for a vector table and context swapping routines. The rest of the source code may be written in a higher-level language, such as C. The system core kernel may include a context swapping model, a process and threading model, a locking and process synchronization model, a simple scheduler, base system calls, and a basic device driver model.
The system described herein does not necessarily require specific device drivers, specific boot up or processor initialization code, a specific memory management model (for example, sbrk, malloc and free), specific networking code, and/or specific applications, although some of these functions may be useful for the system. Since the system is meant to function as an embedded operating system rather than as a general purpose base platform, everything not directly connected to essential kernel services may be designed for each implementation. For example, even if inter-process communications were not part of the core kernel, a very rich set of signals, semaphores and process synchronization functions may be provided as part of the core kernel to allow virtually any model of inter-process communication to be incorporated.
The system may be built using the Cygnus GnuPRO tool. The Cygnus GnuPRO libraries (e.g., the multi-threaded libc) may be used to provide basic routines such as string functions, etc. The kernel may use standard calling conventions based on traditional Unix API calls (open, close, read, write, ioctl, etc.) and traditional Unix libc system calls (printf, strcpy, atoi, etc.). There are some calls that may be specific to the system described herein.
The system described herein is fully 32-bit, pre-emptive and/or cooperative, multi-threaded, and multi-tasking. However, the system may run in a single address space. In some embodiments, there is no definable “user” or “kernel” memory space enforced by the operating system. In addition, in some embodiments, the kernel memory areas may be statically defined, thus reducing the need for dynamic memory allocation. However, although there may be no kernel support for such routines as sbrk( ), malloc( ) and free( ), any task thread may employ analogous functions as desired. For example, a TCP/IP stack application can manage its own buffer space, and provide callable functions for buffer management.
In order to run on many different types of hardware, the system described herein supports a very simple and powerful organization that includes CPU initialization and boot code, a CPU vector table, a context swapping model, a scheduler interrupt service routine, a process/threading model, critical regions (non-preemptable areas), a scheduler, a simple locking mechanism, process synchronization, a device driver model, system calls, and general API's. Some of these items may be hardware specific, but comprise a very small portion of the kernel. The modules for these items may be written in assembly language. The rest of the items may all be written in a high level language, such as C. With the exception of the context block informat

Affiliated with

Also associated with

Rating

Inhibiting starvation in a multitasking operating system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Inhibiting starvation in a multitasking operating system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inhibiting starvation in a multitasking operating system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3299024