Difficulties in understanding the representation of memory.

Task: Suppose you have an architecture with a 32-bit logical address space (that is, a logical address is a 32-bit number). The architecture uses a 2-level page table, i.e., the logical address is divided into three sections: two indexes in the page table and an offset (exactly as it was in the example on the slides).

And in the tables at each level of the page table exactly 1024 entries (respectively, the index in each table takes 10 bits), and you use pages of 4096 bytes in size (i.e. the offset is a 12-bit number, it is easy to notice that together we get 32 ​​bits = 10 + 10 + 12).

Attention question (it is not necessary to answer it specifically): if the process uses only two sections of the logical address space: 4MB, starting with the logical address 0x0, and 2MB, starting with the address 0xbfe00000, how many entries in the root table will point to the next level tables? enter image description here

My understanding of this task (please indicate and correct errors):

1) Lvl1 and Lvl0 index take up 10 bits each, Offset 12.

2) Each table labeled Level Num holds 1024 entries of something and indexes of 10 bits (in the scheme, only 10 bits in the size of each cell were indicated. It is assumed that there are + n more bits). So the indexes occupy 1024 * 10/8 bytes, which is equal to 1280 bytes. The total table is 4096 bytes, so some other data of 2816 bytes is stored in the table.

3) At this point, stupor. I do not understand how to connect these 4MB and logical addresses with the information above.

I ask you to explain the principle of the memory and give an explanation to the task. Specifically, the solution to the task, please do not write, because my goal is to understand, and then give the answer myself.

  • I do not understand your calculations. rather what they relate to. About the size of the table you have in the description of the problem, nothing is said and it should not be measured in bytes at all. It is necessary to consider how much memory one table can describe. One lvl0 entry should describe one page, i.e. 4096 bytes, so the whole table lvl0 can describe 1024 * 4096 bytes of memory, i.e. 4 MB. The root table will need as many records as the lvl0 tables you will need to use. - Mike
  • one
    By the way, the tables themselves do not occupy 4096 bytes. For example, in x86 processors in 32-bit mode, one table occupies 32Kb, 1024 entries of 32 bits each. But this has nothing to do with your task, since the pages themselves are in physical memory. And the need to describe in the tables the memory of the tables itself, for the OS to access it, is clearly beyond the scope of the task, because the creation of the tables themselves in the task is not affected. If they had to be taken into account, then the problem would say what size one record of the table lvl0 - Mike
  • @Mike I think I understand you. Thank you, now I will answer my own question. - AlexIdest
  • one
    Yes that's right. only you have a simple task. Ideally, one should take into account that one page table (lvl0) describes non-breaking 4 MB of virtual memory. This means that if we were told that we have 6 MB in the form of three regions for displacements far from each other, say 0, 0x0fe00000 and 0xbfe00000, then we would already need 3 tables. And you can also come up with a task, let's say you need to allocate just 8Kb at 0x3FF000, then we would need two whole tables, because the first one will cover only the region to 3FFFFF, which will only have the first page, and the second one will be 400000 and go to another table - Mike
  • but in your task, addresses have a lot of zeros at the end, so they are guaranteed to start on the sections described by one table - Mike

1 answer 1

Because we have only two tables according to the condition of the problem, then we need to find out how many records pointing to the table Lvl 0 in the root table are required (aka Lvl 1).

How many describes the table Lvl 0? Each table has 1024 records, each record describes one page of 4096 bytes. 1024 * 4096 = 4 MB.

We need to describe 6 MB by the condition of the problem . If one table Lvl 0 can describe 4Mb, then we need at least 2 such tables. So, you need two entries from the root table Lvl 1.

Thanks to Mike for clarifying in the comments about my interpretation of the problem and its solutions:

By the way, the tables themselves do not occupy 4096 bytes. For example, in x86 processors in 32-bit mode, one table occupies 32Kb, 1024 entries of 32 bits each. But this has nothing to do with your task, since the pages themselves are in physical memory. And the need to describe in the tables the memory of the tables itself, for the OS to access it, is clearly beyond the scope of the task, because the creation of the tables themselves in the task is not affected. If they had to be taken into account, then the task would say what size one record of the table lvl0