Abstract:
Disclosed is a multiprocessor system including a semaphore register and a semaphore interrupt register. In addition, for each processor in the multiprocessor system, there is a semaphore interrupt enable register. If a first processor finds that a semaphore cell of the semaphore register holds a “1” indicating that an associated shared resource is being accessed by a second processor, the first processor sets a corresponding semaphore interrupt enable cell of the semaphore interrupt enable register to “1” so as to enable semaphore interrupt. When the second processor finishes with the shared resource, the second processor writes a 0 into the semaphore cell, causing a corresponding semaphore interrupt cell of the semaphore interrupt register to hold a “1”. This, combined with the fact that the semaphore interrupt enable cell also holds a “1”, causes an interrupt to the first processor. In response, the first processor services the interrupt and accesses the shared resource. As a result, repetitive reading and writing the semaphore cell by the first processor via a system bus of the multiprocessor system can be avoided.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
   This application claims the benefit of U.S. provisional application No. 60/266,002, filed Feb. 2, 2001. 

   TECHNICAL FIELD 
   The invention generally relates to semaphores, and more particularly to semaphores in a multiprocessor system. 
   BACKGROUND ART 
     FIG. 1  shows a multiprocessor system  100  of the prior art. The multiprocessor system  100  includes a system bus  110 , a plurality of processors  120   a ,  120   b  coupled to the system bus  110 , a main memory  130  coupled to the system bus  110 , and a shared resource  150  coupled to the system bus  110 . The main memory  130  includes a semaphore  140  which is used to monitor access to the shared resource  150  by the processors  120   a ,  120   b . The processors  120   a ,  120   b  each include a register  125   a ,  125   b.    
   In the prior art, the semaphore  140  is implemented by using a location in the main memory  130  whose content the processors  120   a ,  120   b  examine to determine whether the shared resource  150  is available for access. Assuming that initially the shared resource  150  is available for access, that is, both the processors  120   a ,  120   b  are not using the shared resource  150 , then the content of the semaphore  140  would be a “0”, indicating that the shared resource  150  is available for access. Assuming further that the processor  120   a  needs to access the shared resource  150 , then the processor  120   a  would read the content of the semaphore  140  into its register  125   a  and then write a “1” into the semaphore  140 . Design of the multiprocessor system  100  guarantees that the reading of the semaphore  140  and writing a “1” into the semaphore  140  by the processor  120   a , or by any other processor, constitutes one bus transaction. That is, the processor  120   a  seizes the system bus  110  continuously for both the reading and writing of the semaphore  140 . Without this guarantee by design, a race condition may occur. A race condition occurs when at least two processors have access to a shared resource at the same time. 
   The processor  120   a  examines the copy of the content of the semaphore  140  which it receives in its register  125   a  and finds that the copy is a “0”, indicating that the shared resource  150  is currently available for access. The processor  120   a  accesses the shared resource  150 . Assume that while the processor  120   a  is using the shared resource  150 , the processor  120   b  needs to access the shared resource  150 . The processor  120   b  reads the content of the semaphore  140  into its register  125   b  and writes a “1” into the semaphore  140 . Again, the design of the multiprocessor system  100  guarantees that the reading of the semaphore  140  and writing a “1” into the semaphore  140  by the processor  120   b  would constitute one bus transaction. The processor  120   b  then examines the copy of the content of the semaphore  140  which it receives in its register  125   b  and finds that the copy is a “1” indicating that the shared resource  150  is currently not available for access. The processor  120   b  would then execute a program loop that includes: (a) reading the content of the semaphore  140  into its register  125   a , (b) writing a “1” into the semaphore  140 , and (c) examining the copy of the content of the semaphore  140  which it receives in its register  125   b . The processor  120   b  executes the program loop until the copy of the content of the semaphore  140  which the processor  120   b  receives in its register  125   b  is a “0”. 
   When the processor  120   a  finishes using the shared resource  150 , the processor  120   a  writes a “0” into the semaphore  140 . Recognizing that the content of the semaphore  140  becomes a “0”, the processor  120   b  exits the program loop and accesses the shared resource  150 . As a result, no race condition can occur. 
   While waiting for the shared resource  150  to be released by the processor  120   a , the processor  120   b  keeps reading and writing the semaphore  140 . This requires repeated use of the system bus  110 . When the number of processors in the multiprocessor system  100  increases, a higher percentage of system bus cycles will be wasted on the processors reading and writing the semaphore  140  to determine when the shared resource  150  is released. 
   It is the object of the present invention to provide a method and apparatus in which semaphore implementation does not require repeated reading and writing the semaphore and, therefore, effectively increases the system bus throughput. 
   SUMMARY OF THE INVENTION 
   The above objects have been achieved by a digital system comprising a semaphore cell, an interrupt generation circuit coupled to the semaphore cell, and a processor coupled to the interrupt generation circuit. The semaphore cell is configured to have a first state and a second state, the first state of the semaphore cell indicating that a shared resource is available for access, and the second state of the semaphore cell indicating that the shared resource is unavailable for access. The interrupt generation circuit is configured to generate a semaphore interrupt signal to the processor if the semaphore cell changes from the second state to the first state and if the processor need to access the shared resource. 
   In another embodiment of the present invention, a method of using semaphores to monitor shared resource accesses is described. The method comprises providing a the semaphore cell configured to have a first state and a second state, the first state of the semaphore cell indicating that the shared resource is available for access, and the second state of the semaphore cell indicating that the shared resource is unavailable for access. The method further comprises providing an interrupt generation circuit coupled to the semaphore cell and a processor coupled to the interrupt generation circuit. The method further comprises generating, with the interrupt generation circuit, a semaphore interrupt signal to the processor if the semaphore cell changes from the second state to the first state and if the processor need to access the shared resource. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  shows a block diagram of a multiprocessor system  100  of prior art. 
       FIG. 2  shows a circuit diagram of a digital system  200  for implementing semaphores according to one embodiment of the present invention. 
       FIG. 3  shows a circuit diagram of one embodiment of the hardware semaphore cell  220   a  of the hardware semaphore register  220  and the corresponding semaphore interrupt cell  230   a  of the semaphore interrupt register  230  of FIG.  2 . 
   

   DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
   With reference to  FIG. 2 , the digital system  200  includes, illustratively, a system bus  210 , processors  202   a  and  202   b , shared resources  206   a ,  206   b , and  206   c , a hardware semaphore register  220 , a semaphore interrupt register  230 , semaphore interrupt enable registers  240  and  250 , six AND gates  260   a ,  260   b ,  260   c ,  270   a ,  270   b , and  270   c , and two OR gates  280  and  290 . The processors  202   a  and  202   b  include registers  204   a  and  204   b , respectively. 
   The hardware semaphore register  220  includes, illustratively, three hardware semaphore cells  220   a ,  220   b , and  220   c . The hardware semaphore cells  220   a ,  220   b , and  220   c  are used to monitor access to the shared resources  206   a ,  206   b , and  206   c , respectively. In general, if a processor  202   i  (i=a or b) reads a hardware semaphore cell  220   j  (j=a, b, or c), the processor  202   i  receives the current content of the hardware semaphore cell  220   j  and the content of the hardware semaphore cell  220 J becomes a “1”. If a processor  202   i  writes a hardware semaphore cell  220   j , the content of the hardware semaphore cell  220   j  always becomes a “0”. In other words, if a processor  202   i  reads a hardware semaphore cell  220   j  which currently holds a “0”, the processor  202   i  receives a “0” and the content of the hardware semaphore cell  220   j  becomes “1”. If a processor  202   i  reads a hardware semaphore cell  220 J which currently holds a “1”, the processor  202   i  receives a “1” and the content of the hardware semaphore cell  220 J remains “1”. 
   The semaphore interrupt register  230  includes, illustratively, three semaphore interrupt cells  230   a ,  230   b , and  230   c , coupled to the hardware semaphore cells  220   a ,  220   b , and  220   c  via connection line  223 ,  225 , and  227 , respectively. The semaphore interrupt enable register  240  includes, illustratively, three semaphore interrupt enable cells  240   a ,  240   b , and  240   c . The semaphore interrupt enable cells  240   a ,  240   b , and  240   c  provides inputs to the AND gates  260   a ,  260   b , and  260   c  via connection lines  243 ,  245 , and  247 , respectively. The AND gates  260   a ,  260   b , and  260   c  also receive inputs from the semaphore interrupt cells  230   a ,  230   b , and  230   c  via connection lines  233 - 283 ,  235 - 285 , and  237 - 287 . The AND gates  260   a ,  260   b , and  260   c  generates three outputs to the OR gate  280  via connection lines  263 ,  265 , and  267 , respectively. The OR gate  280  generates a first semaphore interrupt signal to the processor  202   a  via connection line  281  if at least one of the AND gates  260   a ,  260   b , and  260   c  generates a “1” to the OR gate  280 . 
   Similarly, the semaphore interrupt enable register  250  includes, illustratively, three semaphore interrupt enable cells  250   a ,  250   b , and  250   c . The semaphore interrupt enable cells  250   a ,  250   b , and  250   c  provides inputs to the AND gates  270   a ,  270   b , and  270   c  via connection lines  253 ,  255 , and  257 , respectively. The AND gates  270   a ,  270   b , and  270   c  also receive inputs from the semaphore interrupt cells  230   a ,  230   b , and  230   c  via connection lines  233 - 293 ,  235 - 295 , and  237 - 297 . The AND gates  270   a ,  270   b , and  270   c  generates three outputs to the OR gate  290  via connection lines  273 ,  275 , and  277 , respectively. The OR gate  290  generates a second semaphore interrupt signal to the processor  202   b  via connection line  291  if at least one of the AND gates  270   a ,  270   b , and  270   c  generates a “1” to the OR gate  290 . 
   For illustration of the operation of the digital system  200 , assume that, initially, the hardware semaphore cell  220   a , the semaphore interrupt cell  230   a , and the semaphore interrupt enable cells  240   a  and  250   a  all hold a “0”. Assume further that the processor  202   a  needs to access the shared resource  206   a . The processor  202   a  reads the hardware semaphore cell  220   a  into its register  204   a . Reading the hardware semaphore cell  220   a  by the processor  202   a  automatically changes the content of the hardware semaphore cell  220   a  from “0” to “1”. The processor  202   a  then examines the copy of the hardware semaphore cell  220   a  which it gets in its register  204   a  and finds that the copy is a “0” indicating that the shared resource  206   a  is currently available for access. The processor  202   a  then accesses the shared resource  206   a.    
   Assume that while the processor  202   a  is using the shared resource  206   a , the processor  202   b  needs to access the shared resource  206   a . The processor  202   b  reads the hardware semaphore cell  220   a  into its register  204   b . Any reading of the hardware semaphore cell  220   a  by any processor automatically sets the content of the hardware semaphore cell  220   a  to “1”. Because the hardware semaphore cell  220   a  currently holds a “1”, reading the hardware semaphore cell  220   a  by the processor  202   b  does not change this content of hardware semaphore cell  220   a  (still a “1”). The processor  202   b  then examines the copy of the hardware semaphore cell  220   a  which it gets in its register  204   b  and finds that the copy is a “1” indicating that the shared resource  206   a  is currently unavailable for access. The processor  202   b  sets the content of the semaphore interrupt enable cell  250   a  to “1” and then switches to another task. As a result, the AND gate  270   a  receives as an input a “1” from the semaphore interrupt enable cell  250   a  via connection line  253 . 
   When the processor  202   a  no longer needs access to the shared resource  206   a , the processor  202   a  writes a “0” into the hardware semaphore cell  220   a . This causes the content of the semaphore interrupt cell  230   a  to change from “0” to “1”. This content of “1” of the semaphore interrupt cell  230   a  propagates to the AND gate  270   a  as an input via connection line  233 - 293 . In response, the AND gate  270   a  generates a “1” to the OR gate  290  which in turn generates a “1” as the second semaphore interrupt signal to the processor  202   b  causing an interrupt in the processor  202   b.    
   This content of “1” of the semaphore interrupt cell  230   a  also propagates to the AND gate  260   a  as an input via connection line  233 - 283 . However, because the semaphore interrupt enable cell  240   a  holds a “0”, the other input of the AND gate  260   a  is a “0”. As a result, the AND gate  260   a  generates a “0” to the OR gate  280  which in turn generates a “0”. Therefore, no interrupt occurs in the processor  202   a.    
   In response to the interrupt, the processor  202   b  services the interrupt by reading the contents of the semaphore interrupt register  230  and semaphore interrupt enable registers  250  via connection buses  239  and  259 , respectively. Because both the semaphore interrupt cell  230   a  and the semaphore interrupt enable cell  250   a  hold a “1”, processor  202   b  can determine that the release of the corresponding shared resource  260   a  caused the interrupt. The processor  202   b  then writes a “0” to both the semaphore interrupt cell  230   a  and semaphore interrupt enable cell  250   a  via connection buses  239  and  259 , respectively. The processor  202   b  then reads the hardware semaphore cell  220   a  into its register  204   b . The reading of the hardware semaphore cell  220   a  by the processor  202   b  also changes to content of the hardware semaphore cell  220   a  from “0” to “1”. The processor  202   b  then examines the copy of the hardware semaphore cell  220   a  which it gets in its register  204   b  and finds that the copy is a “0” indicating that the shared resource  206   a  is currently available for access. The processor  202   b  then accesses the shared resource  206   a . In summary, the processor  202   b  does not have to repeatedly check the hardware semaphore cell  220   a  via the system bus  210  to determine if the shared resource  206   a  is released. As a result, the throughput of the system bus  210  is increased. 
   In a similar manner, the hardware semaphore cell  220   b , the semaphore interrupt cell  230   b , and the semaphore interrupt enable cells  240   b  and  250   b  are used to monitor access to the shared resource  206   b  by the processors  202   a  and  202   b , respectively. Also in a similar manner, the hardware semaphore cell  220   c , the semaphore interrupt cell  230   c , and the semaphore interrupt enable cells  240   c  and  250   c  are used to monitor access to the shared resource  206   c  by the processors  202   a  and  202   b , respectively. 
   With reference to  FIG. 3 , the hardware semaphore cell  220   a  and the semaphore interrupt cell  230   a  of  FIG. 2  are shown in further detail according to one preferred embodiment. The hardware semaphore cell  220   a  includes an address decoder  310 , a multiplexer  320 , a D flip-flop  330 , an AND gate  340 , and a tri-state buffer  390 . The Q output of the D flip-flop  330  holds the current content of the hardware semaphore cell  220   a.    
   Assume the processor  202   a  ( FIG. 2 ) reads the hardware semaphore cell  220   a . The processor  202   a  reads the hardware semaphore cell  220   a  by putting a unique address of the hardware semaphore cell  220   a  on a semaphore address bus  313  and putting a “1” on a control line  315 . In response, the address decoder  310  generates a “1” to the multiplexer  320  via a connection line  325  causing the multiplexer  320  to electrically connect the control line  315  to the D input of the D flip-flop  330  via connection line  329 . AB a result, the output Q of the D flip-flop  330  will hold a “1” in the next clock cycle. The AND gate  340  receives a “1” from the address decoder  310  via connection line  323 . The AND gate  340  also receives a “1” from the control line  315 . As a result, the AND gate  340  generates a “1” to the buffer  390  causing the buffer  390  to pass the current content of the D flip-flop  330  at the output Q of the D flip-flop  330  to the processor  202   a  via connection lines  393 ,  317 , and the system bus  210 . In summary, the reading of the hardware semaphore cell  220   a  by the processor  202   a  gives the processor  202   a  the current content of the hardware semaphore cell  220   a  and puts a “1” into the hardware semaphore cell  220   a.    
   The semaphore interrupt cell  230   a  includes, illustratively, D flip-flops  350  and  380 , an OR gate  360 , and an AND gate  370 . The Q output of the D flip-flop  350  holds the current content of the semaphore interrupt cell  230   a . Assume that the hardware semaphore cell  220   a  currently holds a “1” indicating the processor  202   a  is using the shared resource  206   a  ( FIG. 2 ) and that the semaphore interrupt cell  230   a  currently holds a “0”. In other words, the Q output of the D flip-flop  330  currently holds a “1” and the Q output of the D flip-flop  350  currently holds a “0”. The D input and the Q output of the D flip-flop  380  also hold a “1”. 
   When the processor  202   a  finishes using the shared resource  206   a , the processor  202   a  writes a “0” into the hardware semaphore cell  220   a . The processor  202   a  writes a “0” into the hardware semaphore cell  220   a  by putting the unique address of the hardware semaphore cell  220   a  on the semaphore address bus  313  and putting a “0” on the control line  315 . The address decoder  310  generates a “1” to the multiplexer  320  causing the multiplexer  320  to pass the value “0” on the control line  315  to the D input of the D flip-flop  330 . As a result, the hardware semaphore cell  220   a  will hold a “0” in the next clock cycle. 
   When the Q output of the D flip-flop  330  changes from “1” to “0”, the output of the AND gate  370  changes from “0” to “1”. As a result, the output of the OR gate  360  changes from “0” to “1”, which is applied to the D input of the D flip-flop  350 . In the next clock cycle, the semaphore interrupt cell  230   a  will hold a “1”, which is applied to the AND gate  270   a  ( FIG. 2 ) via connection line  233 - 293 . In response, the AND gate  270   a  generates a “1” to the OR gate  290 , assuming that the semaphore interrupt enable cell  250   a  has been set to “1” by the processor  202   b . As a result, the OR gate  290  generates a “1” as the second semaphore interrupt signal to the processor  202   b  causing an interrupt in the processor  202   b . In response to the interrupt, the processor  202   b  services the interrupt by determining which semaphore caused the interrupt. The processor  202   b  makes this determination by comparing the contents of the semaphore interrupt register  230  and semaphore interrupt enable register  250 . Because both the semaphore interrupt cell  230   a  and the semaphore interrupt enable cell  250   a  hold a “1”, the processor  202   b  can determine that the semaphore interrupt cell  230   a  caused the interrupt. In other words, the processor  202   b  can determine that the release of the shared resource  206   a  caused the interrupt. The processor  202   b  then writes a “0” to both the semaphore interrupt cell  230   a  and semaphore interrupt enable cell  250   a  via connection buses  239  and  259 , respectively. The processor  202   b  then reads the hardware semaphore cell  220   a  into its register  204   b . The reading of the hardware semaphore cell  220   a  by the processor  202   b  also changes to content of the hardware semaphore cell  220   a  from “0” to “1”. The processor  202   b  then examines the copy of the hardware semaphore cell  220   a  which it gets in its register  204   b  and finds that the copy is a “0” indicating that the shared resource  206   a  is currently available for access. The processor  202   b  then accesses the shared resource  206   a . In summary, in the present invention, the use of hardware semaphores coupled with interrupt mechanism avoids race conditions and repetitive use of the system bus for checking the contents of the hardware semaphores. 
   In one embodiment of the present invention, “software semaphores” may be used in place of hardware semaphores  220 . The software semaphores may be registers like the hardware semaphores  220  but do not automatically change to a certain state (e.g., become “1”) when being read by a processor. If software semaphores are used, the instruction set must include a special test-and-set instruction which reads the software semaphores and sets the software semaphores to “1” in one atomic action. 
   In another embodiment of the present invention, the digital system  200  may have M processors  202  and N shared resources  206 . Accordingly, the digital system  200  has a hardware semaphore register  220  and a semaphore interrupt register  230  each of which has N cells corresponding to the N shared resources  206 . The digital system  200  further has M semaphore interrupt enable registers  240 ,  250  corresponding to the M processors  202 . Each semaphore interrupt enable register  240 ,  250  has N cells corresponding to the N shared resources  206 . In the embodiments of the present invention described above, M=2 and N=3.