# 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 0 Page Table A 0 CAFE 0 F000 1 Page Table B 1 DEAD 1 D8BF x (rest invalid) 2 BEEF x (rest invalid) 3 BA11 x (rest invalid)

1. 00000000
2. 20022002
3. 10015555

## Problem 3

In a 32-bit machine we subdivide the virtual address into 4 segments as follows:

 10-bit 8-bit 6-bit 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: