04.1 (conspect) Cache

What is it – cache?

Memory cache
Display the actual part of the data scheduled in a fast device. Synchronically data. Cache - is a high-speed storage layer at which the required data set is typically of a temporary nature.
Example of caching

it is exchange data with disk, but nobody remembers about it anymore. Several times ago, it was a critical component of the operating system. The hard drive is a million times slower. Operating systems that are heavily tied to constant disk sharing have suffered from having to do a lot of things all the time. A (real) hard drive works like this: there is a surface (flat pancake) with heads, and to read the data you first have to move the head horizontally on the track and wait for the track to spin to the desired area. And even if it's fast, it's still very slow :( compared to RAM operation. It is millions of times faster.

The solution to this problem is to allocate a piece of RAM to read data from it and write into it while the processor is doing nothing. Data from five is written to disk. When we are done or have written too much, the content (cache) is written to memory.

There are two modes of cache operation:

Caching data on a floppy disk in the early days was very useful because the disk speed is slower than the RAM speed. And if a piece of RAM is used to exchange with the disk, we open the file and start reading from there. If we change something, we write it into memory - and the operating system will do it later. And there are disadvantages:

Speed:

There are two different speed parameters: Speed - there are two different speed parameters - response time and bandwidth. If we say the drive is slow - we say both things - at this point we wait for it to read the data - this is response time. The read operation is not happening. Bandwidth is a metric characteristic that shows the ratio of the limit quantity. Example of Bandwidth: 1 Megabyte per second - even if the drive is physically fast and makes positioning operations fast or reads the entire track at once (like modern drives) - there are different drive spins - very fast 5400, 7200 and even more spins per minute. 7200 - reads everything we need in a second. However, even if the drive is like this, but if it is connected to a car with 1 Megabyte per second - the speed will still be 1 Megabyte per second.

There is another third thing, which in the case of CAOS is a technological problem - the third property of the cache is when it is faster than a slow disk - we can write a large piece of data quickly and read a small one. We can't read only 1 byte from the disk. So, if we read each byte directly from the disk by sectors - each reading of a sector is very slow. We have read a whole Megabyte of kilobytes and we need a byte from there - that's fine. The situation when the External Devices are designed to read in large pieces and then we crush them. Our slow devices, in an effort to get the job done faster, communicate in large pieces.

And why is the fast memory cache smaller than the device we cache on the slow one?

Perhaps we can intuitively assume that fast devices are undoubtedly more expensive in terms of money because of technology or high power consumption. RAM uses less power than hardware memory (processor memory). And the second - in fact, the more memory, the slower it is. We have 5 wires - reference to the register and so we get the address. And now the real OP, which doesn't only store, for example, 64-bit address, but also the memory organization itself doesn't allow you to set 32 wires and the size of cells - hardware circuitry that includes 32 wires turns it all into a circuit and reads from there. The difference is that we can use 5 wires and circuitry around them or we can use 2 in 32 pieces. Especially if our memory requires a search - not addressable, but actual - the search procedure is linear. From here the search time is increased. Far not always the size of the cache is smaller than the size of the device cache.

!!! We rely on the data we need and our next conversation will be to define the concept of relevance.

Two not universal principles of computer architects - our data is arranged in such a way - they are the display of what is topicality:

* Temporary locale
if we have referred to some cell(s), it implies that we will refer to it again.

Example for code: loop; Example for data: array.

* Spatial address locale
we address some cell in memory and it follows that we address the next cell later.

Example for code: after this instruction the following will be executed; Example for data: any data array, stack.

Brunch Predictions
predict which cell we'll do next. Let's cache the beginning of the cycle in memory and not the continuation.

Equidistant references

A very frequent situation: we address a cell with the address n, then (n+16), then (n+32) and so on - this is an example when any array of complex data - an array of structures looks like: read the structure of field 'A' and then read the next structure of field 'A' and then compare it. In memory, we are climbing through the exact step shift. However, until we start addressing memory, nothing follows which step we are walking with. What should we cache? Answer: The data we've already read have been accessed because the principle of temporal localization says that what we've accessed we'll do again. And there's a third of any pattern that's more complex than addressing the next cell - we can predict what we'll do - what step through.

!

The cache isn't rubber and it's gonna run out one day... - what should we throw away? On what principle should we do that?

Algorithm for obsolescence of data

Remember that we must always do a cache search - this is the weakest place!!!! Strategies:

What's been cached?

1 memory cell is expensive. We should know the counter (for LRU), the address of the cell (30 bits) and say the cell (32 bits) - why 30 bytes? The address is a multiple of 4, and we store an entire machine word - we do not remember the last zeros.

| 00 | 10 04 00 00 | a0 78 4f 95 |

On 32 data - it is 38 age + address - it is a lot. We can mean it by the principle of localization then we can cache not one, but many consecutive cells. So we enter the concept of a cache string - it's some machine word (256) with metadata (age and address). Why the address is 22 bits - because we store the address (a0 78 4f 95 ... 34 45| 8000 ) then the total is 1024 bytes - 10 bits extra . We don't have to store the whole address, we store the smaller part.

Tag
is to store only a significant amount of memory that we're going to cache.

In OS, it's a piece of running data. The ratio of data to metadata is human. Modern caching uses strings. Statistically, it's justified. Caching tactics:

../dCache.png

By the way, any PC breaks the principle of spatial localization as it is any preemptive multitasking - and this is a little less than all the PCs in the world. The OS has a kernel and several tasks are running - and when we switch from code to code, from a system call to another call - this principle is broken.

We combine two principles.

../aCache.png

../mCache.png

Write cache

Increases speed and is able to increase more than the reading cache. It's easy to break. 1 If we write to memory and don't read from it - we lose one cache hit if we don't write what we save to memory and then go there - if we duplicate the read and write operation - it's hard hardware. You can read in parallel but you cannot write in parallel. It is inefficient in case there is no cache to write - the question is: is it possible to cache something if it is written? The answer is no. Write back: fundamentally use the cache for recording and only then synchronize its status in memory 'Hot Cache': when the contents of the cache do not match what is contained in memory.

HSE/ProgrammingOS/04_Cache/Cospect_en (последним исправлял пользователь FrBrGeorge 2020-02-12 10:05:11)