Homework 5

Due 2/17/2012 [start of section]

Problem 1

Given the following program that uses three  memory segments in an address space as described in class (code segment, data segment ,and stack segment):

char a[100];
main(int argc, char ** argv)
    int d;
    staticdouble b;
    char *s = "boo", * p;

    p = malloc(300);
    return 0;

Identify the segment in which each variable resides and indicate if the variable is private to the thread or is shared among threads.
Be careful.

Problem 2

This question refers to an architecture using segmentation with paging (you may need to consult the text for details). In this architecture, the 32-bit virtual address is divided into fields as follows:

4 bit segment number 12 bit page number 16 bit offset

Here are the relevant tables (all values in hexadecimal):

Segment Table Page Table A Page Table B
0Page Table A 0CAFE 0F000
1Page Table B 1DEAD 1D8BF
x(rest invalid) 2BEEF x(rest invalid)
x(rest invalid)

Find the physical address corresponding to each of the following virtual addresses (answer "bad virtual address" if the virtual address is invalid):

  1. 00000000
  2. 20022002
  3. 10015555


Problem 3

In a 32-bit machine we subdivide the virtual address into 4 segments as follows:
8 bit
We use a 3-level page table, such that the first 10-bit are for the first level and so on.
  1. What is the page size in such a system?
  2. What is the size of a page table for a process that has 256K of memory starting at address 0?
  3. What is the size of a page table for a process that has a code segment of 48K starting at address 0x1000000, a data segment of 600K starting at address 0x80000000 and a stack segment of 64K starting at address 0xf0000000 and growing upward (like in the PA-RISC of HP)?

Problem 4

Consider a system with a virtual address size of 64MB (2^26), a physical memory of size 2GB (2^31), and a page size of 1K (2^10). Under the target workload, 32 processes (2^5) are running; half of the processes are smaller than 8K (2^13) and half use the full 64MB virtual address space. Each page has 4 control bits.
  1. What is the size of a single top-level page table entry (and why)?
  2. What is the size of a single bottom-level page table entry (and why)?
  3. If you had to choose between two arrangements of page table: 2-level and 3-level, which would you choose and why? Compute the expected space overhead for each variation: State the space overhead for each small process and each large process. Then compute the total space overhead for the entire system.

Problem 5

(Midterm 1 fall 2011)

Consider a virtual memory system with 42-bit physical addresses and 6 control bits per page. How large does the page size have to be to allow each page table entry to fit in a 4-byte word?

Problem 6

(Midterm 1 fall 2011) Consider a virtual memory system with 48-bit virtual addresses, 44-bit physical addresses, 16KB pages, and 7 control bits per word. Assuming a multi-level page table arrangement, how many levels of page tables should this system use?

Problem 7

(Midterm spring 2011) Suppose I am designing a new page table for a machine that must support 32GB of physical memory using 16KB pages and at least 8 control bits per page. I plan to use a 3-level page table and put each level's node on a single physical page. Assuming a reasonable design, what is the maximum virtual address space size I can support?

Problem 8

(Midterm fall 2010) Recall the (simplified) 32-bit x86 paging scheme described in class. We had 32-bit virtual addresses and 32-bit physical addresses, we had 4KB pages, we had a two-level page table, and each node in the two level page table t on one physical page. Note: 4KB = 212 bytes.
(a) What is the space overhead consumed by this scheme for an application with a sparse virtual address space that has just three regions in use:

    10MB of code starting from address 4MB,
    19KB of stack starting from address 1GB, and
    91KB of heap starting from address 2GB.

    internal fragmentation:
    external fragmentation:
    data structure overhead: