0
$\begingroup$

There's an interview question.

In my opinion, os can calculate cache hit rate and miss rate(with the total running time of process and the number of transfer of block of memory to cache). But how can know the size of cache? Is it possible to calculate with os's certain information? (such as size of transfer size to cache)

We can assume anyting we need to calculate easily(like only one cache-no l1 l2 and so on, cache is fully associative or set associative or directed mapped and so on)

$\endgroup$
4
  • 1
    $\begingroup$ Which cache? Modern memory hierarchies have multiple levels of caches. What are your thoughts? Are we allowed to write an arbitrary program, or are we limited to only using certain quantities already measured by the OS? What are your assumptions/restrictions? Is this a practical question or a theoretical one? If it's a practical one, there might be a way the OS can query information about the processor and learn it directly. $\endgroup$
    – D.W.
    May 5, 2017 at 18:25
  • $\begingroup$ @D.W. It's an theoritical one. And we assumw that there is only one cache(no l1 l2 and so on).So we have only one cache one main memory one secondary storage. And it's only one block(whatever the size is). The other things should be assumed when we need. $\endgroup$
    – A.Cho
    May 6, 2017 at 0:34
  • $\begingroup$ Please edit the question to incorporate that information into the question, so the question is self-contained and people don't need to read the comments to understand what you are asking. $\endgroup$
    – D.W.
    May 6, 2017 at 0:37
  • $\begingroup$ @D.W. thks i just edited it $\endgroup$
    – A.Cho
    May 6, 2017 at 0:40

2 Answers 2

3
$\begingroup$

It's not clear to me what you want.

An OS can query the processor about its cache structure as long as the processor have the feature (for instance, X86 has this possibility tied with the CPUID instruction).

An OS could deduce the information from any mean of identifying the processor (nowadays something like CPUID, but in a given processor family there always had been more or less precise means to deduce which member your were running on, especially if you have access to privileged instructions as an OS does) and having hardcoded tables giving the sizes for each model.

Any program can try to measure the number of cache levels, their size, associativity, line size and latency. What you have to do is measure the latency of memory accesses using well-thought-out patterns and plotting the the latency versus the total memory touched by the pattern. You get some plateaus giving the latency of the cache, and the jumps positions give the cache sizes. Comparing the results of different patterns give the associativity and the line sizes. The more the cache is advanced (eviction buffers, pre-loading, ...) the more you have to be careful in the way the patterns are computed (a common technique is implementing the pattern as a pointer chase so that it is more difficult for the processor to guess the next address to be loaded) or you'll measure something different from what you want. Other factors to take into account is the effect of TLB, the presence of shared cache between cores and processors the load on the other cores, the effect of process migrations between cores by the OS, the effect of throttle by the OS or the hardware due to temperature or battery load. In conclusion such measurements are pretty technical, and although you can deduce a lot of things it is better to have a preconceived notion of the memory structure and of the external factors which may have an influence.

$\endgroup$
3
  • $\begingroup$ what I want was something like an idea of how we can know cache size? using os's knowledge like how many faults were there and so on. Not the cpu instrutions you mentuon $\endgroup$
    – A.Cho
    May 6, 2017 at 13:25
  • $\begingroup$ It seems to me that the third paragraph covers that aspect. $\endgroup$ May 6, 2017 at 13:29
  • $\begingroup$ @A.Cho The rule is that you solve a problem in the easiest and in a proven correct way. Using CPU instructions that return the cache size is the easiest way to find the cache size. $\endgroup$
    – gnasher729
    May 6, 2017 at 23:17
2
$\begingroup$

When your computer is started, and the first bit of software starts running on it, that software knows what class of processor it is running on - it knows that because it has been compiled for a certain class of processor, and if your computer had a different kind of processor the software would immediately crash, so the fact that the software is running proves what kind of processor it is running on.

Each class of processor comes with concrete processors that each behave slightly different. These differences are documented and can be used to determine what exact kind of processor there is. For example, the documention for x86 processors might say "on this group of processors, bit 12 of some condition code register is always zero, so after trying to set this bit to one it, will still be read as zero. On this other group of processor, the bit will be read as one after setting it to one". With that knowledge, the software can determine exactly which kind of processor there is.

And then, the software developers check their manuals again, and they read things like "this kind of processor always has 16KB of L1 data cache. For that kind of processor, you execute a certain instruction, and after that instruction, register two will contain the size of the L1 data cache in bytes". That's just an example, but these things will be documented, and the software developers use them to find out anything they want to know.

Now when you say "cache size", things are more complicated nowadays (they always are). As an example, an Intel server might have two sockets containing two separate physical chips, each chip might contain 8 cores, and each core might support two virtual cores. In that case, you might get the knowledge "there is 64 Kbyte of L1 cache, shared between two virtual cores, 256 KByte of L2 cache, shared between two real cores, and 12 MB of L3 cache, shared between all cores in one physical chip". So your computer would have a total of 64 x 8 x 2 KByte of L1 cache, 256 x 4 x 2 KByte of L2 cache, and 12 MByte x 2 of L3 cache, but each processor thread only sees a limited amount of that, and may have to share that cache with other processor threads.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.