Abstract:
Synchronizing processes in a computer system includes creating a predictability model for a process. The predictability model establishes a predicted time slot for a resource that will be needed by the process. The method further requires establishing a predictive request for the resource at the predicted time slot. The predictive request establishes a place holder associated with the process. In addition, the method requires accessing another resource needed by the process for a period of time before the predicted time slot, submitting a request for the resource at the predicted time slot, and processing the request for the process at the resource.

Description:
[0001]    This non-provisional application claims the benefit of the provisional application filed with the United States Patent and Trademark Office as Ser. No. 61/158,491 entitled “Synchronizing Resources In A Computer System”, filed Mar. 9, 2009. 
     
    
     BACKGROUND 
       [0002]    Exemplary embodiments of the invention relate to the art of computer system and, more particularly, to synchronizing resources in a computer system. 
         [0003]    Current computer systems run a plurality of processes/threads in series and in parallel. Each process/thread vies independently, or in conjunction with associated processes and/or threads, for various shared computer resources. Shared computing resources can be either hardware resources or software resources. Examples of hardware resources are Input/Output systems, memory systems, processing systems, networking systems and the like. Examples of Input/Output systems include keyboard, mouse, and automatic data input/output devices such as, sensors and file read/write systems, USB drives and the like. Examples of memory systems include hard-drives, random access memory (RAM), read only memory (ROM) and/or variations such as, Persistent RAM (PSRAM), Dynamic RAM (DRAM), Static RAM (SRAM), as well as auxiliary memory systems such as, floppy drive, CD-RAM, DVD-RAM, Flash Memory and the like. Examples of processing systems include a Central Processing Unit (CPU) having one or multiple cores, graphics cards, auxiliary processing units such as, floating point accelerators, field programmable gate arrays (FPGA) or ASIC-s, and the like. Examples of network systems include sockets, USB ports, and Ethernet ports. Examples of software resources include virtual memory systems, network monitor programs, network daemons and various other Operating systems and monitoring programs and the like. 
         [0004]    Resource synchronization concerns sharing resources between a plurality of process or threads such as shown in  FIG. 1 . When ready, a process/thread  101  generates a request  102  for a needed resource  103 . The request for any particular type of resource depends on the type of computing the requesting process/thread is engaged in at the instant of generating the request. For example, an input request may be generated when the process/thread is expecting a data from an input device, and a memory request may be generated when the device is expected to “fetch” some data from the memory. If available, the resource is locked for access using a lock mechanism  104 . Examples of lock mechanisms includes semaphore, mutex and the like. At this point process  101  utilizes the resource as needed. When no longer required, process  101  unlocks  105  resource  103  and exits. At this point, resource  103  is made available for other processes/threads such as indicated at  110 . If resource  103  is not available when requested, process  110  joins a queue  115  until process  103  is available. 
         [0005]    Items waiting in queue  115  are picked up using methods and algorithms such as Last In First Out (LIFO), First In First Out (FIFO), Least Recently Used (LRU) etc. or based on the priority assigned to the jobs being run by these processes or threads. While in queue  115  for resource  103 , process/thread  103  is idle and valuable computations time is wasted. Effectively sharing resources with minimum down time or latency time is an active area of research in the Synchronization of Resources. However, process and threads still spend a lot of time waiting in the queue. Time in the queue could otherwise have been used for computation purposes. 
         [0006]    Another serious consequence of making a process wait in a queue is the so-called “DeadLock”. Deadlock occurs when a set of blocked processes each holding a resource is waiting to acquire a resource held by another process in the set such as shown in  FIG. 2  which illustrates four processes P, P 2 , P 3  and P 4  and two resources R 1  and R 2 . Process P 1  is waiting in a queue for Resource R 2  and also making a request for Resource R 1 . Process P 3  is waiting in a queue for Resource R 1  and also making a request for Resource R 2 . Given that P 1  can not come out of R 2  unless R 1  is available, and P 3  can not get out of R 1  until R 2  becomes available, the system gets into an infinite idle state thereby creating a deadlock. 
       SUMMARY 
       [0007]    Exemplary embodiments of the invention include creating a predictability model for a process. The predictability model establishes a predicted time slot for a resource that will be needed by the process. The exemplary embodiments also include establishing a predictive request for the resource at the predicted time slot. The predictive request establishes a place holder associated with the process. In addition, the exemplary embodiments include accessing another resource needed by the process for a period of time before the predicted time slot, submitting a request for the resource at the predicted time slot, and processing the request for the process at the resource. 
         [0008]    System and computer program products corresponding to the above-summarized exemplary embodiments are also described and claimed herein. 
         [0009]    Additional features and advantages are realized through the techniques of exemplary embodiments of the present invention. Other embodiments and aspects of the invention are described in detail herein and are considered a part of the claimed invention. For a better understanding of the invention with advantages and features, refer to the description and to the drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
         [0010]    The subject matter which is regarded as the invention is particularly pointed out and distinctly claimed in the claims at the conclusion of the specification. The foregoing and other objects, features, and advantages of the invention are apparent from the following detailed description taken in conjunction with the accompanying drawings in which: 
           [0011]      FIG. 1  is block diagram illustrating resource sharing in accordance with the prior art; 
           [0012]      FIG. 2  is a block diagram illustrating a deadlock occurrence in the prior art; 
           [0013]      FIG. 3  is a flow chart illustrating a method of synchronizing processes in a computer in accordance with an exemplary embodiment of the invention; 
           [0014]      FIG. 4  is flow chart illustrating a method of establishing a predictability model in accordance with exemplary embodiments of the invention; 
           [0015]      FIG. 5  illustrates a generated probability density function p(i,k,l) 
           [0016]      FIG. 6  illustrates a method of establishing a predictive resource synchronization for each resource; and 
           [0017]      FIG. 7  is a schematic block diagram of a general-purpose computer suitable for practicing the present invention exemplary embodiments. 
       
    
    
       [0018]    The detailed description explains the exemplary embodiments of the invention, together with advantages and features, by way of example with reference to the drawings. 
       DETAILED DESCRIPTION 
       [0019]    With reference to  FIG. 3 , a method of synchronizing processes in a computer system in accordance with exemplary embodiments of the invention is indicated generally at  20 . At this point, it should be understood that as the synchronization for a process and a thread is similar, the use of the term “process” should be construed to include either a process, a thread or both a process and a thread. Initially, a predictability model is created for each process operating on the computer system as indicated in block  22 . The predictability model determines a predicted time slot needed by each process for each computer resource such, as, but not limited to, central processing unit time, memory allocation, keyboard input, mouse input, network access etc. The predicted time slot is based on a probability density function established for the computer system. Once the predicted time slot is determined in block  22 , a pseudo or predictive request, e.g., a predictive place holder is established for each resource required by each process, as indicated in block  24 . While waiting for the predicted time slot, each process is active or processing on available resources as indicated in block  26 . That is, in accordance with exemplary embodiments of the invention, processes do not remain idle while waiting for necessary resources to become available if other needed resources are free. 
         [0020]    In further accordance with the exemplary embodiment a process may generate a request for predictive multiple place holders for multiple resources. Also, the predicted place holders may overlap in time for multiple resources. For example, it might be necessary to use a processing resource such as a graphics card and a memory device at the same time. The process may generate predictive place holders for both the graphics card and the memory device which may overlap in the time. 
         [0021]    Once the predicted time slot approaches, a determination is made whether the process is ready for the resource as indicated in block  28 . If the process is ready for the resource as determined in block  28 , an actual request for the resource is submitted as indicated in block  30 . At this point, once the time slot arrives, and the resource becomes available, the resource is locked, and accessed/utilized by the process, as indicated in block  40 . When the process is complete, the resource is un-locked and made available for additional processes. If, however, the process in not ready for the resource as determined in block  28 , the predictive placeholder is released and the time slot made available to other processes as indicated in block  60 . 
         [0022]    After releasing the place holder in block  60 , a new request for a time slot is submitted to the resource as indicated in block  62 . At this point, a determination is made as to an overall priority of the process as indicated in block  64 . That is, processes having a higher priority are placed ahead of lesser priority processes waiting for the resource. In any event, after determining process priority, a new time slot is established for the process as indicated in block  66 . Once the new time slot arrives, the process is ready, and the resource is available, the resource is locked, and accessed/utilized by the process, as indicated in block  40 . When the process is complete, the resource is un-locked and made available for additional processes. 
         [0023]    Reference will now be made to  FIG. 4  in describing a method of establishing the predictability model in accordance with exemplary embodiments of the invention. Initially, it should be understood that the predictability model is executed for every time slot t_j for j=1, 2, until infinity such as shown in block  301 . For all practical purposes, infinity is a large number or until the system is halted, stopped, shutdown or booted down. In addition, the predictability model is determined for every process in the system P_i for j=1, 2, thru N, where N is the total number of processes or threads in the system, or the number of processes and/or threads that are participating in predictive synchronization such as indicated in block  302 . Note that this number N may vary as the number of active processes or threads may change from one time slot to another. This may happen as and when new jobs are created and finished jobs are taken out of the system. The predictability model is also set for every system resources R_k for k=1, 2, thru K, where K is the total number of resources in the system, or the number of resources that are participating in predictive synchronization such as indicated in block  303 . Note that this number K may vary as the number of available resources may change from one time slot to another. This may happen as and when new resources are added to the system and faulty or non-functional resources are taken out of the system. 
         [0024]    For each process P_i for j=1, 2, thru N, a need for a resource R_k for k=1, 2, thru K, is predicted for each time slots in the future, t_l, where l=j, j+1, j+2, . . . , j′, where both j and j′ are limited as 1&lt;j&lt;j′&lt;M, where M is a large number such as shown in block  304 . The value of M can be decided by the computational efficiency of the system. The system becomes less and less predictable and less and less computationally efficient as M becomes large. A typical value of M can be between about 200 to about 2000. 
         [0025]    For each time slot, t_l, where l=j, j+1, j+2, . . . , j′, 1&lt;j&lt;j′&lt;M, the probability density function is computed as p(i,k,l)=pdf(P_i, R_k, t_l), where P_i is a process for j=1, 2, thru N; and R_k is a resource for k=1, 2, thru K such as indicated in block  305 . In another embodiment, however, p(i,k,l) is only selectively recomputed or updated. The function p(i,k,l) is computed either as a Predictive Linear Gaussian Model, or Predictive Gauss—Markov Model. They both take the form of: 
         [0000]      ψ (t+n+l) =γ 0   Zt+Σ   i=0, . . . ,n Ω(ν t−i+1 , π t+n+1 ) 
         [0026]    The computation of: ψ (t+n−1)  can be simplified by choosing selective values in the series. 
         [0027]    It should also be understood that a threshold probability p_t is given where 0&lt;p_t&lt;1 such as shown in  FIG. 5  which illustrates a generated probability density function p(i,k,l) is plotted along the time scale l and the threshold probability p_t. 
         [0028]    The probability density function p(i,k,l) is compared against the threshold probability p_t as indicated in block  306 . If the value of p(i, k, l) is greater than the threshold probability p_t, a pseudo request PSR(i,k,l) is created for the process P_i for Resource R_k for the time slot t_l such as indicated in block  307 . At this point it should be understood that a pseudo request PSR(i,k,l) is not an actual request but rather a predicted request with a high probability that an actual request might happen for the process P_i for Resource R_k for the time slot t_l. This can also be construed as the place holder established in block  24 . 
         [0029]    At any time instance t_j, besides generating pseudo or predicted request for a time slot t_l in the future, the system can also generate an actual request for a resource such as shown in block  308 . If a process P_i generates an actual request for a resource R_k at the current instant t_j in block  308  a real request is generated in block  309 . Otherwise, the predictability model returns to block  303  for the next resource. 
         [0030]    After the request RQ(i,k,j) is created in block  309 , a check for pseudo requests is performed in block  310 . More specifically, a determination is made whether a pseudo request PSR (i,k,j) exists for the process P_i for Resource R_k for the time slot t_j. This pseudo request might have been created in the past based on the predictive model as described in block  304  thru block  307 . If a pseudo request exists, the pseudo request is replaced by an replaced by the actual request RQ(i,k,j) as indicted in block  311 , otherwise RQ(i,k,j) is attached to the resource queue corresponding to the resource R_k in block  312 . 
         [0031]      FIG. 6  illustrates a method of establishing a predictive resource synchronization for each resource. Initially, it should be understood that resource synchronization is executed for every time slot t_j for j=1, 2, until infinity as indicated in block  315 . For all practical purposes, infinity is a large number or until the system is halted, stopped, shutdown or booted down. In addition, resource synchronization is executed for every Resources in the system R_k for k=1, 2, thru K, where K is the total number of resources in the system, or the number of resources that are participating in the predictive synchronization as indicated in block  352 . Note that this number K may vary as the number of available resources may change from one time slot to another. This may happen as and when new resources are added to the system and faulty or non-functional resources are taken out of the system. 
         [0032]    At this point, a determination is made whether the Resource R_k is available as indicated in block  353 . If R_k is available, a request is taken from the queue as indicated in block  354 . Otherwise, the next resource is selected in block  352 . In block  354 , the next request is taken from the queue associated with R_k. As discussed above, items waiting in the queue can be picked up from the queue using methods and algorithms such as Last In First Out (LIFO), First In First Out (FIFO), Least Recently Used (LRU) etc. or based on the priority assigned to the jobs being run by these processes or threads. 
         [0033]    After a request is taken in block  354 , resource R_k is locked by the process picked up from the queue in block  355 . At this point, resource R_k is utilized by the process picked up from the queue as indicated in block  356 . A determination is then made whether the process is finished with resource R_k is finished in block  357 . If the process is finished, resource R_k is unlocked in block  358 , if the process is not finished, the next resource R_k is checked for availability in block  352 . 
         [0034]    The capabilities of the present invention can be implemented in software, firmware, hardware or some combination thereof. As one example, the method of synchronizing processes in a computer system described herein is practiced with a general-purpose computer and the method may be coded as a set of instructions on removable or hard media for use by the general-purpose computer.  FIG. 7  is a schematic block diagram of a general-purpose computer suitable for practicing the present invention embodiments. In  FIG. 7 , computer system  400  has at least one microprocessor or central processing unit (CPU)  405 . CPU  405  is interconnected via a system bus  410  to a random access memory (RAM)  415 , a read-only memory (ROM)  420 , an input/output (I/O) adapter  425  for a connecting a removable data and/or program storage device  430  and a mass data and/or program storage device  435 , a user interface adapter  440  for connecting a keyboard  445  and a mouse  450 , a port adapter  455  for connecting a data port  460  and a display adapter  465  for connecting a display device  470 . 
         [0035]    ROM  420  contains the basic operating system for computer system  400 . The operating system may alternatively reside in RAM  415  or elsewhere as is known in the art. Examples of removable data and/or program storage device  430  include magnetic media such as floppy drives and tape drives and optical media such as CD ROM drives. Examples of mass data and/or program storage device  435  include hard disk drives and non-volatile memory such as flash memory. In addition to keyboard  445  and mouse  450 , other user input devices such as trackballs, writing tablets, pressure pads, microphones, light pens and position-sensing screen displays may be connected to user interface  440 . Examples of display devices include cathode-ray tubes (CRT) and liquid crystal displays (LCD). 
         [0036]    A computer program with an appropriate application interface may be created by one of skill in the art and stored on the system or a data and/or program storage device to simplify the practicing of this invention. In operation, information for or the computer program created to run the present invention is loaded on the appropriate removable data and/or program storage device  430 , fed through data port  460  or typed in using keyboard  445 . 
         [0037]    The flow diagrams depicted herein are just examples. There may be many variations to these diagrams or the steps (or operations) described therein without departing from the spirit of the invention. For instance, the steps may be performed in a differing order, or steps may be added, deleted or modified. All of these variations are considered a part of the claimed invention. 
         [0038]    At this point it should be appreciated that exemplary embodiments of the invention enable prediction of a time slot when a resource will be required by a process and establish a predictive place holder at the time slot for the resource. While waiting for the time slot, the process is free to utilize other available resources. As the time slot approaches, the predictive place holder is replaced by an actual request for the resource. In this manner, computing efficiencies are achieved by allowing processes to utilize available resources while waiting for other resources to become available instead of sitting idle in a resource queue. 
         [0039]    While the preferred embodiment to the invention has been described, it will be understood that those skilled in the art, both now and in the future, may make various improvements and enhancements which fall within the scope of the claims which follow. These claims should be construed to maintain the proper protection for the invention first described.