Cache coherency and consistency in OS

 

Caching:

 

Caching is an important principle of computer systems.  Information is normally kept in main memory. As it is used, it is copied into a faster storage system - the cache on a temporary basis. When we need a particular piece of information, we first check whether it is in the cache.  If it is, we use the information directly from the cache. If it is not, we use the information from the main memory and put a copy in the cache with an assumption that we will need soon in future.

 

Also the internal programmable registers like index registers provide a high speed cache for a main memory. The programmer or compiler implements the register allocation and register replacement algorithms to decide which information to keep in registers and which to keep in main memory.

 

Caches can also be implemented totally in hardware. Most systems have an instruction cache to hold the next instructions to be executed.  Without this cache the CPU would have to wait several cycles while an instruction is fetched from main memory thus making the overall processing far slow. For this reason, most systems have one or more high speed data cache in the memory hierarchy.

 

Cache management is an important design problem as cache memory has limited size.  Careful selection of the cache size and of a replacement policy can result in 80 to 99% of all accesses being in the cache, greatly increasing performance.

 

The main memory can be viewed as a fast cache for secondary storage since data in secondary storage must be copied into main memory for use and data must be in main memory before being moved to secondary storage for storing it.

 

The movement of information between levels of storage hierarchy may be either explicit or implicit depending on the hardware design and the OS software being used.  The data transfer from cache to CPU and registers is usually a hardware function. There is no intervention from the OS. Whereas the transfer of data from disk to memory is under the control of an OS.

Cache Coherency and Consistency:

 

Consider an example, suppose that an integer A is located in file B that is to be incremented by 1, and file be resides on magnetic disk. The increment operation proceeds by first issuing an IO operation to copy the disk block on which A resides to main memory. This operation is followed by copying A to the cache and to an internal register. Thus the copy of A appears in several places:  on the magnetic disk, in main memory, in the cache and in an internal register.

Fig:  Migration of integer A from disk to register

Once the increment takes place in the internal register, the value of A differs in the various storage systems. The value of A becomes the same only after the new value of A is written from the internal register back to the magnetic disk.

 

In a computing environment where only one process execute at a time, this arrangement poses no difficulties, since an access to the integer A will always be to the copy at the highest level of the hierarchy.  However, in a multitasking environment where the CPU is switched back and forth among various processes extreme care must be taken to ensure that if several processes wish to access A, then each of these processes will obtain the most recently updated value of A.

 

The situation becomes more complicated in a multiprocessor environment where in addition to maintaining internal registers each of the CPU also contains a local cache. In such an environment a copy of A may exist simultaneously in several caches. Since the various CPUs can all execute concurrently we must make sure that an update to the value of A in one cache is immediately reflected in all other caches where A resides.  This situation is called cache coherency and it is usually a hardware problem.

 

In a distributed environment the situation becomes even more complex.  In such an environment several copies of the same file can be kept on different computers that are distributed in space. Since the various replicas may be accessed and updated concurrently we must ensure that when a replica is updated in one place all other replicas are brought up to date as soon as possible.