Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1996-03-22
2003-04-01
Courtenay, III, St. John (Department: 2126)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C711S170000, C711S163000
Reexamination Certificate
active
06542919
ABSTRACT:
TECHNICAL FIELD
This invention relates to the field of computer operating systems, and in particular, to the area of real-time operating systems in embedded computing environments.
BACKGROUND OF THE INVENTION
Computer operating systems such as UNIX provide a sophisticated degree of protection among processes concurrently executing on the system. A process is defined as a program in execution which utilizes system resources, such as memory and computing time. At each step of execution the process generates the address or addresses, in memory which is needed to successfully execute the step, e.g., a) the address where an instruction to be executed is stored, b) the address where required data is to be found, or c) the address where output data is to be stored. The range of addresses that a computer can generate defines its address space.
Under control of a conventional operating system, e.g., UNIX, the addresses generated by a process do not directly address a location in the computer's physical memory. Instead, the addresses generated by the process are translated to a physical location using well known virtual memory techniques. A description of virtual memory can be found in the book “Operating Systems Concepts”, by Peterson and Silbersatz. Each process executes its steps and generates addresses as if it is executing on its own private computer which has a very large memory. The size of the memory on this virtual private computer is the size of the process' address space. The addresses generated by the process in this virtual memory are translated to physical memory locations, also known as real memory addresses, using a page table mechanism, typically implemented in a memory management unit (MMU). Thus, each process is provided a different address space, which is mapped onto the real memory. The MMU translations are briefly described below.
The physical memory is divided into fixed units called pages. The page size is determined by the hardware architecture of the processor. The address space of each process is also divided into pages, each having the same size as a page of the physical memory. For each process, a page table is maintained in memory by the operating system which contains a mapping of the page number in the address space to the page number in the physical memory. The page table also contains some attributes bits for each page. The attribute bits indicate a) whether the page with which they are associated is valid or invalid, i.e., whether or not the associated page has a corresponding page in physical memory, and b) if the process has permission to read or to modify the contents of the page.
When an address is generated by a process, the MMU first looks up the page table in the memory and determines the corresponding physical page in the memory. The permissions for the page are also checked during the look up process to verify that the process is authorized to access the memory in the manner, e.g., read or write, that it is attempting. The physical page number is attached to the offset of the address within the page and a new physical address is generated. The physical address is then used to look up the contents of the memory. Thus, each memory access translates into two sequential accesses, the first one for generating the physical address and checking the validity, with the second one being for actually accessing the physical memory.
The two accesses are usually expedited by means of caching techniques, in which frequently used areas of the page tables (and memory) are stored in a smaller higher speed memory called a cache so as to reduce the probability of actually accessing the physical memory.
One of the advantages of going through a page table is that processes can execute relatively independent of each other. A process has exclusive access to its address space and no other process can modify the contents of the address space, unless the process explicitly provides access to parts of its address space to other processes.
In a system with multiple concurrent processes, switching between processes is a complex, and so “expensive” in processing terms, operation. A process may be further broken down into several threads, each thread being a sequence of executing instructions. All threads within a process execute in the same address space. As such, switching from the currently active thread to another thread is a relatively simple and inexpensive operation. However, all threads have identical privileges to all of the address space of the process to which they belong, and so there is no protection among threads executing in the same address space.
In the area of embedded systems, such as 1) digital television receivers, 2) television set top units, and 3) network switch controllers, there is only one process in the entire system. This process may consist of multiple concurrent threads. However, typically, there is no support for virtual memory because such systems have only so-called “primary memory”, e.g., RAM, ROM or combination thereof, and no so-called “secondary storage”, e.g., a disk. Thus, all the threads have access to the entire memory, including data structures maintained by the operating system.
This global access is a serious problem in the development and debugging of embedded system software. For example, an errant thread, e.g., one still under development, can alter a data structure or code used by an already debugged and “trusted” thread. The trusted code will eventually be affected by the corruption of its data structure or code, and either generate an error or behave unexpectedly. It is very difficult to determine the cause of the problem in such an environment, since the point in the code at which the software crashes or generates a warning is unrelated to the point in the code that caused the problem.
An identical problem exists in digital television receivers which are used for the downloading of multiple applications from a server. The downloaded application may cause the receiver to crash, and it is difficult to isolate the cause of the fault, which could lie in the downloaded application software, the operating system software, or any other supporting library. When the software in the embedded system originates from multiple program development organizations that are cooperating, it is difficult to isolate the cause of the problem. As a result, each organization typically blames the other for the failure.
In embedded systems where an MMU is present, groups of threads can be logically clustered into processes, which are each provided their own address space using MMU page mapping. In this manner, different threads can be provided isolation from one another. In some systems, the MMU is preloaded so that the physical page numbers correspond to the virtual page numbers and the physically generated address is identical to the virtual address. Unfortunately, the cost of having an MMU is usually unacceptable in an embedded system. In those cases, there is no protection provided among the threads.
We have realized that, from both the debugging and development perspective, providing protection among threads executing in the same address space is an attractive idea. Thus, in concurrently filed application Serial No. (case PHA 23-102), assigned to the same assignee as the present application, protection among threads executing in the same address space of a computer system is provided without using virtual memory techniques that require each thread actually, or logically, to be isolated in its own, separate address space. This is achieved by grouping the threads into protection domains, each of the threads in a protection domain having the same rights to access memory as the other threads in that protection domain, so that each thread in a protection domain can access all the information available to the others. At least one protection domain, referred to herein as the “system” domain, which typically is the protection domain of the operating system and has unrestricted access to the entire memory, is predefined prior to execution of a
Rath Kamlesh
Verma Dinesh
Wendorf James W.
Courtenay III St. John
Koninklijke Philips Electronics , N.V.
Vodopia John
LandOfFree
Operating system for use with protection domains in a single... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Operating system for use with protection domains in a single..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Operating system for use with protection domains in a single... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3115196