MESI cache consistency protocol for concurrent programming

MESI Cache consistency protocol , Used to solve the cache consistency problem in multi-threaded environment .

Cache consistency issues

In a multiprocessor system , Each processor has its own cache , And they share the same main memory . When the operation tasks of multiple processors involve the same main memory area , It may lead to inconsistent cache data , If this happens , Whose cache data shall prevail when synchronizing back to main memory ？！ This is the cache consistency problem .

In order to solve the problem of consistency , Each processor needs to follow some protocols when accessing the cache , Read and write according to the protocol . The main protocols used are ：MESI Cache consistency protocol .

Early computers used 【 The bus is locked 】 The way , But the performance of this method is too low , Now the basic 【 Cache consistency protocol 】, But there are also bus locks , In some cases, the bus locking mode will be used .

Atomicity visibility Orderliness

Atomicity , visibility , Orderliness is one of the three important concepts in concurrent programming .

• visibility ： It refers to when a thread modifies the value of a shared variable , Can other threads immediately know the modified value .
• Orderliness ： It refers to the single thread execution code , We always think that code is executed in sequence （ After the program is compiled into machine code instructions, instruction rearrangement may occur , The rearranged instruction may not be in the same order as the original instruction ）.
• Atomicity ： It means that an operation cannot be interrupted , Even in a multithreaded environment , Once an operation is started, it will not be affected by other threads .

Cache consistency protocols are not omnipotent , it It just solves the visibility problem nothing more , There is no way to solve the problems of order and atomicity .

Cache line (Cache line)

Before understanding the cache consistency protocol , First, learn about the next cache line (Cache line).

CPU cache (cache) It's made up of a lot of Cache line Composed of .Cache line yes CPU Cache and main memory exchange data Smallest unit ,Cache line The size is fixed , Usually it is 64Byte.

When the data size exceeds Cache line Fixed size of , You can't use the cache consistency protocol , Will switch to bus locking .

When fetching data from memory to cache In the middle of the day , One at a time Cache line Memory area of size to cache in , Then save the corresponding Cache line in .

MESI Cache consistency protocol

effect ： Solve the cache consistency problem in multi-threaded environment .

MESI yes 4 Initials of States ：Modified、Exclusive、Shared、Invalid.

state	describe	Monitoring task
M modify (Modified)	The Cache line It works , The data has been modified , And data in memory atypism , Data only exists in Ben Cache in .	The cache line must always listen for all attempts to read the cache line relative to main memory , This operation must write the cache row back to main memory in the cache and change the state to S（ share ） The state was delayed .
E exclusive 、 Mutually exclusive (Exclusive)	The Cache line It works , Data and data in memory Agreement , Data only exists in Ben Cache in .	The cache line must also listen to other caches reading the cache line in main memory , Once there's this kind of operation , The cache line needs to become S（ share ） state .
S share (Shared)	The Cache line It works , Data and data in memory Agreement , Data exists in quite a lot Cache in .	The cache line must also listen for requests from other caches to invalidate the cache line or to own the cache line , And change this cache line to I（ Invalid ） state .
I Invalid (Invalid)	The Cache line Invalid .	nothing

working principle ：

1. Variable X=1 Read CPU1 The cache , Mark as exclusive (E), this CPU Will listen （ Bus sniffer mechanism ） other CPU Operations on this memory
2. CPU2 Also from memory X=1 Read into cache , This is the time CPU1 This operation will be known through the bus sniffing mechanism , At this time, I will put X Change the state of to shared state (S), Of course ,CPU2 in X It is also a shared state
3. CPU1 Zhongba X Change to 2, Ready to write back to main memory ,CPU1 The cache line will be locked in the , And then put X Change the status to modified status (M), Then send a message to the bus
4. other CPU At this time, this message is detected , If so CPU There are also X Cache of , Will be changed to invalid status (I)
5. CPU1 Will succeed X=2 Write back to main memory , Will be able to X Change to exclusive state (E)
6. other CPU You need to visit again X Words , Invalid state found , You need to re read from the master and slave

If two CPU At the same time, we have to revise X What will happen ？

A decision will be made in one instruction cycle , Only one can be modified successfully ！

If the decision fails , The entire cache line (Cache line) Will fail as a whole .

When the cache consistency protocol is triggered

Then there is another very important question , When does the cache consistency protocol trigger ？

First , The cache consistency protocol requires Hardware support , But this question need not be considered , Because the hardware now supports . But the agreement is Weak agreement , Under normal circumstances , System operation does not perform cache consistency (MESI) The check .

To trigger the cache consistency protocol , You need to add... To the assembly instructions #Lock The signal ！

But we usually program , It is obviously impossible to write anything by hand #Lock The signal . about java Come on , Namely volatile keyword , because volatile Keywords can trigger #Lock The signal , Thus, the cache consistency protocol can be triggered . Of course ,volatile Keyword has more than one function , It can also prevent instruction reordering to some extent ！ in other words ,volatile Keywords can solve both visibility and ordering problems , But it can't solve the problem of atomicity ！

When the cache consistency protocol will fail

1. If X The storage length exceeds one cache line , Can use bus locking . One data cannot span multiple cache rows （ Data can span multiple cache rows , Only the cache consistency protocol will fail ）
2. CPU Cache consistency protocol is not supported . Of course , This must be early CPU