Clicker Questions

2025-02-18

Consider two processes X and Y, running concurrently. Each has a pointer p; both ps are the same address (i.e. printf("%p\n", p); prints the same thing in both programs). They run the following code, swapping back and forth which is running in the CPU:

	X	Y
1.	`*p = 5;`
2.		`*p = 10;`
3.		`printf("%d\n", *p);`
4.	`printf("%d\n", *p);`
5.	`exit(0);`
6.		`exit(0);`

What happens when we run this?

Answer

X prints 5 and Y prints 10

Virtual memory implements the following idea:

map<VA, PA> pagetable;

uint64_t load64(VA virt_addr) {
    PA phys_addr = pagetable[virt_addr];
    return memory[phys_addr ... phys_addr+8];
}

… where both VA and PA are integer types. Because they are integers, the map implementation can be as simple as an array.

Why is doing this with an array not a good idea?

Answer

Arrays are as small and fast as we can get, but any data structure is much too big to store 2⁶⁴ entries in memory.

Virtual memory implements the following idea:

map<VA, PA> pagetable;

uint64_t load64(VA virt_addr) {
    VPN virt_pagenum = ⓕ(virt_addr);
    PO page_offset = ⓖ(virt_addr);
    PPN phys_pagenum = pagetable[virt_pagenum];
    PA phys_addr = ⓗ(phys_pagenum, page_offset);
    return memory[phys_addr ... phys_addr+8];
}

If the VA type is a 48-bit unsigned integer and we want a page (all addresses that share a single page number) to be 2¹² = 4096 bytes in size with contiguous addresses, what should function ⓖ look like?

Answer

virt_addr & 0xFFF

Suppose we have 64-bit addresses organized with a 12-bit page offset, four 9-bit virtual page numbers, and 16 unused bits. How many total memory accesses would be needed to execute a memory load instruction such as x[i]?

(This question only asks about main memory, not caches)

Answer