Abstract:
A system, method and medium for utilizing data indicative of operating system activity to determine if a process should continue to attempt to acquire a lock, or make a call to an operating system.

Description:
BACKGROUND OF THE INVENTION 
   1. Field of the Invention 
   The present invention generally relates to a system, method and medium for improving the acquisition time for acquiring a lock and, more particularly, to a system, method and medium for using and/or providing operating system information to acquire a hybrid user/operating system lock. 
   2. Background Description 
     FIG. 1 , generally at  100 , is a conventional computer system that shows the relationship between application programs  101   a - n , kernel  105 , and hardware  107 . Application programs  101   a - n  can include, for example, conventional word processing, graphic and/or web browser programs, that directly interact with an end user. Application programs  101   a - n  are executed in user-space  103 , and can be referred to as “processes,” or “tasks” when program instructions are executed by the central processing unit (CPU) (not shown). 
   Kernel  105  includes system call interface  109 , kernel subsystems  111 , and device drivers  113 . Application programs  101   a - n  communicate with kernel  105  by making a conventional system call. System call interface  109  can receive requests from processes to access hardware  107  such as printers, monitors, storage devices and/or network devices. Kernel  105  can execute these requests via kernel subsystems  111  and device derivers  113  in a conventional manner. Kernel subsystems  111  can also include interrupt handlers to service interrupt requests, a memory management system to manage address spaces, and system services such as networking and interprocess communication (IPC). 
   When performing, for example, conventional asynchronous input-output (AIO) between application programs  101   a - n  and kernel  105 , application programs  101   a - n  invoke a system call to kernel  105  to initiate each input-output (I/O). For example, application program  101   a - n  typically calls a function in a library, such as a C library, that in turn relies on system call interface  109  to instruct kernel  105  to conduct one or more tasks on its behalf. When a system call takes place, an application program  101   a - n  that makes the call is suspended, and the kernel  105  takes over. The context switch from the application program  101   a - n  to kernel  105  is costly in terms of performance, as system calls can take, for example, 10 to 1000 times more processing time than a normal processing operation, such as a CPU adding two numbers together. 
   Conventional techniques of acquiring a lock can be done in user-space  103  where, for example, an application program  101   a - n  acquires a lock, or by the kernel  105 , where the kernel  105  acquires a lock. As used herein, a lock is used to deny access to a given resource, such as a file, memory location, input/output port, and the like, usually to ensure that only one application program  101   a - n , and/or process associated therewith, at a time uses the resource. 
   Although user-space  103  will typically acquire a lock more quickly than kernel  105 , user-space  103  does not know, for example, the overall state of the various processes and threads being executed and/or managed by kernel  105 . On the other hand, although kernel  105  knows the overall state of the various processes and threads being executed and/or managed by kernel  105 , an application program  101   a - n  call into kernel  105 , as indicated above, typically takes at least an order of magnitude more processing time to acquire a lock than if application program  101   a - n  requests a lock and acquires the lock without making a call to kernel  105 . If application program  101   a , requests a lock and does not acquire the lock, application program  101   a , short of making a call to kernel  105 , can keep attempting to acquire the lock. However, using known techniques, application program  101   a  cannot tell if it cannot obtain the lock because, for example, another program (e.g., application program  101   c ) is being executed on (or by) the same processor has the lock, or because another program (e.g., application program  101   d ) being executed on (or by) another processor in a multiprocessor system has the lock. 
   One conventional technique attempts to reduce the number of system calls by having application program  101   a - n  first attempt to acquire a lock in user-space  103 . If the lock, after one or more attempts, is not acquired in user-space  103 , application program  101   a - n  then makes a call to kernel  105 . However, in using this technique, kernel  105  does not make information available to a memory space that is shared by application program  101   a - n  and kernel  105 , so that application program  101   a - n  can use the information to determine the state and/or status of various processes, tasks, etc. being processed by, or waiting to be processed by, kernel  105 . 
   SUMMARY OF THE INVENTION 
   In one embodiment embodiments of the present invention, a system, method and medium are provided for utilizing data indicative of operating system scheduling in shared user-operating system memory space. The method includes the steps of providing, by the operating system, data to a shared user-operating system memory space indicative of scheduled operating system activities. An attempt by a user process to acquire a lock is detected, wherein, upon the user process not being able to acquire the lock, the user process reads the data. The operating system receives a call from the user process when the number of operating system activities exceeds a predetermined number. If the number of processes scheduled to run does not exceed a predetermined number, the user process attempts a second time to acquire the lock. 
   In another embodiment of the present invention, a system, method and medium are provided for utilizing data that is not indicative of operating system scheduling in shared user-operating system memory space. In this embodiment, the purpose for utilizing data that is not indicative of operating system scheduling may be to facilitate operation in accordance with kernel policy. For example, if kernel resides on a laptop computer, kernel policy may be to conserve battery power, possibly at the expense of kernel efficiency. In this case, by kernel providing more data indicative of operating system activities than is actually occurring, a process may make a kernel call, rather than keep spinning, in order to save battery power. 
   This method also includes detecting an attempt by a user process to acquire a lock, wherein, upon the user process not being able to acquire the lock, the user process reads the data. The operating system receives a call from the user process when the number of operating system activities exceeds a predetermined number. If the number of processes scheduled to run does not exceed a predetermined number, the user process attempts a second time to acquire the lock. 
   The operating system may operate in the context of a single processor system, or a multiprocessor system. In the case of a multiprocessor system, data in the shared user-operating system memory space is indicative of scheduled operating system activities for each processor of the multiprocessor system. The kernel of the operating system can provide the data to the shared user-operating system memory space. 
   There has thus been outlined, rather broadly, the features of the invention in order that the detailed description thereof that follows may be better understood, and in order that the present contribution to the art may be better appreciated. There are, of course, additional features of the invention that will be described hereinafter and which will form the subject matter of the claims appended hereto. 
   In this respect, before explaining at least one embodiment of the invention in detail, it is to be understood that the invention is not limited in its application to the details of construction and to the arrangements of the components set forth in the following description or illustrated in the drawings. The invention is capable of other embodiments and of being practiced and carried out in various ways. Also, it is to be understood that the phraseology and terminology employed herein are for the purpose of description and should not be regarded as limiting. 
   As such, those skilled in the art will appreciate that the conception, upon which this disclosure is based, may readily be utilized as a basis for the designing of other structures, methods and systems for carrying out the several purposes of the present invention. It is important, therefore, that the claims be regarded as including such equivalent constructions insofar as they do not depart from the spirit and scope of the present invention. 
   These together with other objects of the invention, along with the various features of novelty which characterize the invention, are pointed out with particularity in the claims annexed to and forming a part of this disclosure. For a better understanding of the invention, its operating advantages and the specific objects attained by its uses, reference should be had to the accompanying drawings and descriptive matter in which there is illustrated preferred embodiments of the invention. 
   Other features of the present invention will be evident to those of ordinary skill, particularly upon consideration of the following detailed description of the embodiments. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The detailed description of the present application showing various distinctive features may be best understood when the detailed description is read in reference to the appended drawing in which: 
       FIG. 1  is a diagram of an exemplary conventional operating system user space and kernel space; 
       FIG. 2   a  is a diagram of an exemplary architecture in accordance with an embodiment of the present invention; 
       FIG. 2   b  is a second diagram of an exemplary architecture in accordance with an embodiment of the present invention; 
       FIG. 2   c  is a third diagram of an exemplary architecture in accordance with an embodiment of the present invention; 
       FIG. 2   d  is a fourth diagram of an exemplary architecture in accordance with an embodiment of the present invention; and 
       FIG. 3  is flow diagram illustrating an exemplary method of reducing system calls in accordance with an embodiment of the present invention. 
   

   DETAILED DESCRIPTION OF EMBODIMENTS 
     FIG. 2   a , generally at  200 , is a diagram of an exemplary architecture in accordance with an embodiment of the present invention. Processes  224   a - n  represent various end-user application processes associated with various end-user application programs. For example, processes  224   a  can represent various processes of a standard word processing program such as Microsoft Word. As used herein, a process is an active program and related resources that may include, for example, open files and associated signals, an address space, and/or one or more threads of execution. 
   Kernel  202  is a module of the operating system that loads and remains in main memory. Kernel  202  is responsible for handling system calls, scheduling and handling completion of tasks, inter-process communication, memory management, managing input and output from hardware (such as printers, keyboards, and a mouse), and providing a copy of or data pertaining to request/process  242  to shared user-kernel space  250 . 
   Scheduler  206  is responsible for controlling process access to the central processing unit(s) (CPU(s) of a computer (not shown)). Scheduler  206  can enforce a policy that ensures that processes  224   a - n  will have access to the CPU, while ensuring that other kernel subsystems (e.g., interprocess communication  214 , memory management  216 , device drivers  235 ) are afforded adequate CPU processing time. For example, scheduler  206  may be responsible for ensuring that hardware  220  actions are performed by device drivers  235  in a timely manner. In connection with I/O queue  208 , scheduler  206  can utilize any known scheduling technique, such as round robin scheduling, scheduling by task priority, and/or scheduling by the shortest task first. 
   In one or more embodiments of the present invention, scheduler  206  provides an interface for user processes  224   a - n  to register for timer notification. This leads to a flow of control from scheduler  206  to the user processes. Finally, scheduler  206  communicates with the CPU(s) (not shown) to suspend and resume processes. The CPU(s) is responsible for interrupting the currently executing process and allowing kernel  202  to schedule another process. 
   Memory management  216  permits multiple processes  224   a - n  to securely share the main memory system of a computer, and supports virtual memory operations that accommodates, for example, a process (e.g., process  224   a ) that utilizes more memory than is available in the computer. 
   Interprocess communication (IPC)  214  can utilize known IPC mechanisms (e.g., pipes, sockets, and/or streams) to enable one process to communicate with another process. There are at least two reasons why processes may need to communicate. One is data transfer, where one process needs to transfer data to one or more other processes. The second reason is synchronization. For example, IPC  214  can coordinate processing of process  224   a  and process  224   d , where process  224   a  may require that process  224   d  prepares data for it before it can continue executing. Device drivers  235  can communicate with hardware  220  through standard device registers (e.g., status, control, and data device registers) to transfer data between the hardware  220  and kernel  202 . 
   In accordance with one or more embodiments of the invention, a user process  224   a - n  can add one or more requests in request/process  242  to I/O queue  208 . For example, the application program associated with the process can, for example, complete fields of a new request (e.g.,  226   a ), and add request  226   a  to I/O queue  228 . Thus, in  FIG. 2   a , request/process  242  may contain, for example, request  226   a  associated with process  224   a , request  227   c  associated with process  224   c , request  226   b  associated with process  224   a , etc. In a standard manner, kernel  202  can also add other tasks to request/process  242  that do not, for example, directly originate from process  224   a - n . Each request preferably is attached atomically to I/O queue  208 . 
   In one or more embodiments of the invention, kernel  202  makes available a copy  242   a  of request/process  242  to shared user-kernel space  250 . In this manner, process  224   a - n  is made aware, for example, of the various processes and threads being executed and/or managed by kernel  202 . In accordance with kernel  202  policy, process  224   a - n  can read, access and utilize request/process  242   a  to determine whether one or more of process  224   a - n  should, for example, keep spinning, go to sleep, or make a call to kernel  202 . 
   More particularly, as an example of kernel  202  policy, suppose process  224   b  attempts to acquire a particular memory space (e.g., a memory address or range of addresses), and there are one or more processes that have already requested the memory space. In such a case, the process may make a call to kernel  202 , knowing that a queue having one or more processes wishing to acquire the memory space already exists. On the other hand, suppose process  224   b  attempts to acquire a particular memory space (e.g., a memory address or range of addresses), and there are no processes that are queued to acquire the desired memory space. In such a case, the process may spin in shared space  250 , thereby avoiding a call to kernel  202 . 
     FIG. 2   b  is a second diagram of an exemplary architecture in accordance with an embodiment of the present invention.  FIG. 2   b  indicates that the present invention can also be used in the context of a multiprocessor system, as indicated, for example, by processor  290   a - n , and processor/request/process  242   b . More than one process (e.g., process  224   a - d ) can be associated with a single processor (e.g., processor  290   a ). In this case, kernel  202  maintains processor/request/process  242   b  with respect to each one of processors  290   a - n , and makes available a copy  242   c  of processor/request/process  242   b  in shared user-kernel space  250 . In this manner, process  224   a - n  is made aware of, for example, the various processes and threads being executed and/or managed by kernel  202 . In accordance with kernel  202  policy as, for example, described above, process  224   a - n  can read and use request/process  242   c  to determine whether one or more of process  224   a - n  should, for example, keep spinning, go to sleep, or make a call to kernel  202 , in a manner as described with reference to  FIG. 1   a.    
     FIG. 2   c  is a third diagram of an exemplary architecture in accordance with an embodiment of the present invention.  FIG. 2   c  indicates that kernel  202  makes available a version  242   e  of request/process  242   d  to shared user-kernel space  250 . In accordance with kernel  202  policy as, for example, described above, process  224   a - n  can read and use request/process  242   e  to determine whether one or more of process  224   a - n  should, for example, keep spinning, go to sleep, or make a call to kernel  202 . 
   In this embodiment, kernel  202  is providing to shared space  250  a version  242   e  of request/process  242   d  that is different than the actual content of request/process  242   d . The purpose for doing so may be so that processes  224   a - n  operate in accordance with kernel  202  policy. For example, if kernel  202  resides on a laptop computer, kernel  202  policy may be to conserve battery power, possibly at the expense of kernel  202  efficiency. In this case, by kernel  202  providing more data in request/process  242   e  than is in request/process  242   d , process  224   a - n  will make a call to kernel  202 , rather than keep spinning, thus saving battery power. 
     FIG. 2   d  is a fourth diagram of an exemplary architecture in accordance with an embodiment of the present invention.  FIG. 2   d  is another embodiment of the present invention can also be used in the context of a multiprocessor system, as indicated, for example, by processors  290   a - n , and processor/request/process  242   f  and  242   g . More than one process (e.g., process  224   a - d ) can be associated with a single processor (e.g., processor  290   a ). In this case, kernel  202  makes available a version  242   g  of processor/request/process  242   f  to shared user-kernel space  250 . In accordance with kernel  202  policy, process  224   a - n  can read and use processor/request/process  242   g  to determine whether one or more of process  224   a - n  should, for example, keep spinning, go to sleep, or make a call to kernel  202 . 
   In this embodiment, kernel  202  is providing a version  242   g  of processor/request/process  242   f  that is different than the actual content of processor/request/process  242   f . The purpose for doing so may be so that processes  224   a - n  operate in accordance with kernel  202  policy. For example, if kernel  202  is operating on a laptop computer, kernel  202  policy may be to conserve battery power, possibly at the expense of kernel  202  efficiency. In this case, by kernel  202  providing more data in processor/request/process  242   g  than is in processor/request/process  242   f , process  224   a - n  will make a call to kernel  202 , rather than keep spinning. 
     FIG. 3  is flow diagram illustrating an exemplary method of reducing system calls in accordance with an embodiment of the present invention. At step  302 , kernel  202  provides information, such as tables  242   a ,  242   c ,  242   e  and  242   g  respectively shown in  FIGS. 2   a - d , to shared space  250 . At step  303 , one or more processes  224   a - n  attempts to acquire a lock. At decision step  304 , kernel  202  determines if a lock requested by a particular process (e.g.,  224   c ) is available. If the lock is available, the method ends. If, at decision step  304 , kernel  202  determines that a lock is not available, then, at decision step  306 , process  224   c  determines, from reading a respective one of tables  242   a ,  242   c ,  242   e  and  242   g , respectively shown in  FIGS. 2   a - d , if one or more other processes are waiting to run. If a predetermined number of other processes are waiting to run, the process  224   c  makes a call to kernel  202 , and the method ends. If, at decision step  306 , there are less than the predetermined number of processes waiting to run, process  224   c  returns to decision step  304 . 
   The many features and advantages of embodiments of the present invention are apparent from the detailed specification, and thus, it is intended by the appended claims to cover all such features and advantages of the invention which fall within the true spirit and scope of the invention. Further, since numerous modifications and variations will readily occur to those skilled in the art, it is not desired to limit the invention to the exact construction and operation illustrated and described, and accordingly, all suitable modifications and equivalents may be resorted to, falling within the scope of the invention.