Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
2001-08-20
2004-10-05
Kim, Kenneth S. (Department: 2111)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
C710S200000, C711S141000, C711S145000, C711S150000
Reexamination Certificate
active
06801986
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to multiprocessor computer systems, and more particularly to the implementation of instructions used to achieve synchronization, mutual exclusion, and atomic read write.
2. Background Information
In a multiprocessor computer system the individual processors must write to the shared memory of the system in a synchronized fashion. That is, if more than one processor is attempting to read and then write to a particular region of shared memory, then each processor must complete its read write before another processor begins to write to that memory location. Synchronization is achieved by the processor obtaining a lock on that memory location. The lock is usually achieved by the processor executing a sequence of special assembly language instructions. Assembly language instructions are executed by a processor, and in response to some instructions the processor issues commands to the system. Commands issued to the system may be classified into three types: Requests, Probes, and Responses.
Requests are commands issued by a processor when, as a result of executing a load or store instruction, it must obtain a copy of data. Requests are also used to gain exclusive ownership to a data item (cache line) from the system. Requests include Read (Rd) commands, Read/Modify (RdMod) commands, Change-to-Dirty (CTD) commands, Victim commands, and Evict commands, the latter of which specify removal of a cache line from a respective cache. A RdMod command is a read of a block of memory, coupled with a request for ownership of the block of memory which was read. That is, the RdMod command reads and modifies the ownership of the block.
A CTD command is issued by a processor and is executed by the system (often the controller coupled to the memory directory) and obtains ownership of a memory block. After the CTD executes, the processor may then change its cache value of the data by writing to its cache. At some point the cache value may be written back to the memory block, depending on writeback policy.
Probes are commands issued by the system to one or more processors requesting data and/or cache tag status updates. Probes include Forwarded Read (Frd) commands, Forwarded Read Modify (FRdMod) commands and Invalidate (Inval) commands. An Inval command is sent to a processor to invalidate a cache line in that processor's cache. When a processor P issues a request to the system, the system may issue one or more probes (via probe packets) to other processors. For example if P requests a copy of a cache line (a Rd request), the system sends a Frd probe to a processor having a dirty copy of the data (if any). If P requests exclusive ownership of a cache line (a CTD request or RdMod request), the system sends Inval probes to one or more processors having copies of the cache line.
Moreover, if P requests both a copy of the cache line as well as exclusive ownership of the cache line (a RdMod request) the system sends a forwarded Read Modify command (Fr_RdMod) in a probe to a processor currently storing a “dirty” copy of the line of data in its cache. In this context, a dirty copy of a cache line represents the most up-to-date version of the corresponding cache line or data block.
In response to the Fr_RdMod probe, the dirty copy of the cache line is returned to the initiating processor where the dirty copy is stored in the corresponding cache. The previous cache is invalidated by the system sending Inval Probes to processors holding the previous cache line in their caches. Upon gaining ownership the processor can then write to the valid copy of the data in its cache.
An Inval Probe may be issued by the system to a processor storing a copy of the cache line in its cache, when the cache line is to be updated by another processor.
Responses are commands from the system to processors and/or the Input Output Ports (IOP). The responses carry the data requested by the processor or an acknowledgment corresponding to a request. For Rd and RdMod requests, the responses are Fill and FillMod responses, respectively, each of which carries the requested data. For a CTD request, the response is a CTD-Success (Ack) or CTD-Failure (Nack) response, indicating success or failure of the CTD, whereas for a Victim request, the response is a Victim-Release response.
In a single processor system, when it is desired to read a memory block, and then to write to that memory block, only one processor reads and writes to that memory block. So the read and the write are simply executed in sequence by the assembly language code.
However, in a multiprocessor system having many processors all of which have access to the target memory block, if processor P
1
executes a read, then processor P
2
may write to that memory block before processor P
1
can write to that memory block. Processor P
1
then writes to the memory block, and processor P
2
data is corrupted. The processors are not properly synchronized.
Further, each processor has a cache memory. Cache coherency methods must be used in order to establish ownership by a processor of a memory block, and to maintain a cache with the current version of the data in the memory block. The cache with the current version of the data of the memory block is referred to as the “dirty” cache line.
An “atomic read write” is a read and then a write to a memory block by a single processor, where other processors of a multiprocessor system are excluded from writing to that memory block between the read and the write.
An atomic read write may be implemented by a pair of instructions in assembly language code, where the second instruction returns a value from which it can be deduced by the executing assembly language code whether the pair of instructions was executed as if the instructions were atomic. The pair of instructions appears atomic if it appears as if all other operations executed by any processor appear before or after the pair. Thus, when an instruction pair appears atomic, no other processor has changed the value between the instruction pair.
Atomic test-modify-instructions appear in the instruction set of most processors. These are used to implement mutual exclusion and synchronization between processes running on a uni- or multi-processor system. The test-and-modify instructions read a memory location and modify it only if it satisfies some predicate. For instance, a test-and-set instruction typically reads a memory location, tests if the value is “0”. If so, it writes a “1” to the same location and “succeeds”. If not, it leaves the memory location unchanged and “fails”. The instruction is considered atomic since one process must complete its test-and-set sequence before another process is allowed to access the location.
In some modern processors, atomicity is simulated using a pair of instructions such as a LOAD_LOCKED and STORE_CONDITIONAL pair, coupled with a mechanism to detect whether or not the execution proceeded atomically. The mechanism is referred to as the “atomicity-violation-detection mechanism”. To perform an atomic test-and-modify operation on a memory location, a LOAD_LOCKED (LD_L) instruction and a STORE_CONDITIONAL (ST_C) instruction are executed in sequence and with the same memory location (the “lock location”) as argument. One or more instructions may occur between the LD_L and ST_C instructions. The atomicity-violation-detection mechanism is activated when the LD_L instruction is executed. The ST_C instruction performs a write to the lock location only if the preceding LD_L succeeds and the atomicity-violation-detection mechanism indicates that atomicity has not been violated.
The design of the atomicity-violation-detection mechanism may vary from processor to processor. Here we consider a typical design. Consider a process running on a processor, executing a LD_L and ST_C sequence in an attempt to acquire a lock. The atomicity-violation-detection mechanism signals a violation when: (1) another process or processor performs a write to the lock variable or to any other address in the same c
Sharma Madhumitra
Steely, Jr. Simon C.
Van Doren Stephen R.
Hewlett--Packard Development Company, L.P.
Kim Kenneth S.
LandOfFree
Livelock prevention by delaying surrender of ownership upon... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Livelock prevention by delaying surrender of ownership upon..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Livelock prevention by delaying surrender of ownership upon... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3318214