CS250 Final Exam Homework
1. Assume the virtual address 0x45674237 and a page size of 4KB and
a 32 bit architecture.
a) obtain the page number and the offset.
Page number is the higher 20 bits: 0x45674 = 284276
Offset is the lower 12 bits: 0x237 = 567
b) Obtain the first-level index and the second-level
index from the page number assuming that each of them is 10 bits
long.
First-level index is determined by the first 10 bits of the page number, and second by the second
10 bits.
0x45674 = 0100 0101 01 10 0111 0100
(1st level index) (2nd level index)
first level index: 01 0001 0101 = 0x115 = 227
second level index: 10 0111 0100 = 0x274 = 628
c) Draw a first-level page table and one second-level
page table that will translate the above virtual address to address
0x83467237
| First level page table
| Second level page table
|
| 0x3ff | 0x70000 |
| | ... |
| 0x115 | 0x68000 |
| | ... |
| 0x000 | ... |
(0x3ff = 210-1)
|
| 0x3ff | 102 |
| | ... |
| 0x274 | 0x83467 |
| | ... |
| 0x000 | ... |
(addr: 0x68000)
|
2. Assuming a 32 bit architecture and a 4KB page size, how many
first level page tables are needed for a single process? How many
second-level page tables are needed for a single process?
Each process has one first level page table. Second level page tables are allocated as needed (up
to 210-1 tables).
3. Enumerate the page bits in the page table and what each of them
is used for.
- Resident bit: is the page in RAM or in swap space/file. If a page is not in RAM MMU
loads with a kernel interrupt.
- Modified bit: has the page been changed since last time the bit was reset?
- Access bit: has the page been read since last time the bit was reset?
- Permission bits: page readable? writable? executable? If CPU exceeds these permissions
an interrupt is thrown
4. Enumerate the five uses of virtual memory used to speed up the
execution of a program.
- mmap text segment: fast start up time as only pages needed are loaded and actual
pages shared between processes.
- mmap data segment: same memory pages until modification performed ("copy on write").
- fork/process creation: child and parent processes share the same memory pages until they are modified.
- zero-initialized memory: all maps to the same zero-initialized page until modified.
- communication: shared memory between processes.
5. Explain how copy-on-write works during fork().
The OS gives the child a copy of the parents memory that is read-only. Modifications cause page
faults which are caught by the OS and a new copy of the page is created.
6. Explain how allocating memory initialized with zeros is
accelerated by using Virtual Memory.
Zero-initialized memory is all maps to one read-only memory page. Only when a page is modified
is a page allocated and actually filled with zeros.
7. Explain what is L1, L2, L3 cache.
L1 cache is the closest to the processor, actually contained in the processor chip itself. This
means that communication between the CPU and the cache is very fast (think CPU register fast).
L2 cache is external to the processor.
L3 cache is much larger than L1 and L2 cache but also much slower, and is built into the
physical memory.
8. Explain what is locality of reference.
Locality of reference refers to the frequency of access of the same requests. Higher
locality means that there are many repetitions of the same request, low locality means there are
few repetitions.
9. Explain in what situations a memory cache will not give good
results.
This will happen when there are many cache misses. This occurs
when there is low locality of reference. The cache works well with repeated
references rather than random references.
10. Explain how it is possible in a direct mapping memory cache that
two items that are frequently used cannot be stored in the cache
simultaneously.
In direct mapping memory, cache segments of memory are assigned-mapped to certain parts of the
cache. If two pieces of data map to the same block in the cache they will constantly vie for
that space and never both be in the cache at the same time.
11. Explain how buffers are used to reduce the numbers of system
calls and device activity in a computer system.
Buffers are used to reduce the number of system calls. For example a cached read operation will
read first a large chunk of data in a single system call and then use the data in the buffer
to satisfy subsequent cached read operations. The same for cached write operations.
12. Explain the steps of a interrupt.
Interrupts is an asynchronous reaction based behavior of the CPU. When the interrupt line is set
to high the CPU immediatly stops and jumps to the handler for that interrupt. In doing this
the CPU first backs up all registers and looks up the interrupt in the interrupt vector, running
the handler. The registers are then restored and the CPU continues executing its previous task.
13. Explain the steps to process a page fault.
The page is found to not be in RAM, and a page fault is thrown. The CPU saves the registers and
runs the appropriate interrupt handler. The handler generates a segfault signal if the page does
not belong to the process, otherwise it loads the page, finding a free page or storing a page in
memory to disk and loading it to that page. Finally it clears the modified and access bits and
returns to the previous task and retries the instruction that generated the page fault.
14.In x86-64 Assembly language implement the function int addarray(int n, int * array) that add all the elements of the array
passed as parameter. n is the length of the array.
.text
.globl addarray
.type addarray, @function
# int addarray(int n, int * array) {
# // n = %rdi array = %rsi
addarray: # // i = %rdx sum = %rax
#
movq $0,%rdx # i=0 ;
movl $0,%eax # sum=0 ;
#
while: cmpq %rdx,%rdi # while (i<n) { // (n-i>0)
jle afterw #
#
addl (%rsi),%eax # sum += *array;
addq $1,%rdx # i++ ;
addq $4,%rsi # array++ ;
jmp while # }
afterw: ret # return sum; }
15. In x86-64 Assembly language implement a program "maxmin" that prompts two integer numbers fom stdin and then displays the maximum, minimum and average of both: numbers. Here is an example of the usage:
bash> maxmin
a=5
b=8
max=8
min=5
#maxmin.s
.data
.comm a,8
.comm b,8
str1: .string "a="
str2: .string "b="
str3: .string "%d"
str4: .string "max=%d\n"
str5: .string "min=%d\n"
.text
.globl main
.type main, @function
main:
movq $str1, %rdi
movq $0, %rax
call printf
movq $a, %rdx
movq $str3, %rax
movq %rdx, %rsi
movq %rax, %rdi
movq $0, %rax
call scanf
movq $str2, %rdi
movq $0, %rax
call printf
movq $b, %rdx
movq $str3, %rax
movq %rdx, %rsi
movq %rax, %rdi
movq $0, %rax
call scanf
movq $a, %rdi
movq $b, %rsi
movq (%rdi), %rax
movq (%rsi), %rdx
cmpq %rdx,%rax
jg tag
movq $a, %rdi
movq $b, %rsi
movq (%rsi), %r8
movq (%rdi), %r9
movq %r9, (%rsi)
movq %r8, (%rdi)
tag:
movq $a, %rdx
movq (%rdx), %rsi
movq $str4, %rdi
movq $0, %rax
call printf
movq $b, %rdx
movq (%rdx), %rsi
movq $str5, %rdi
movq $0, %rax
call printf
ret
16. From your lab7 compiler, complete the following code for
function definition. Add comments describing your code.
function:
var_type WORD
{
fprintf(fasm, "\t.text\n"); // part of the executable section of the file
fprintf(fasm, ".globl %s\n", $2);// declare a global function where the name is
fprintf(fasm, "%s:\n", $2); // the string contained in WORD ($2-2nd part)
// save callee saved registers that might change to the stack.
fprintf(fasm, "# Save registers\n");
fprintf(fasm, "\tpushq %%rbx\n");
fprintf(fasm, "\tpushq %%r10\n");
fprintf(fasm, "\tpushq %%r13\n");
fprintf(fasm, "\tpushq %%r14\n");
fprintf(fasm, "\tpushq %%r15\n");
// Reserve space for args and locals
fprintf(fasm, "\tsubq $%d,%%rsp\n", 8*MAX_LOCALS);
nlocals = 0;
top=0;
}
LPARENT arguments RPARENT
{
int i;
fprintf(fasm, "\t#Save arguments\n");
for (i=0; i<nlocals; i++) { // for each passed in argument
fprintf(fasm, "\tmovq %%%s,%d(%%rsp)\n",
regArgs[i], 8*(MAX_LOCALS-i) ); // move from register to reserved
// space on stack
}
}
compound_statement
{
// clean up and return in case return was not explicitly in program.
fprintf(fasm, "\taddq $%d,%%rsp\n", 8*MAX_LOCALS); // Restore space in stack for
fprintf(fasm, "# Restore registers\n"); // local vars
fprintf(fasm, "\tpopq %%r15\n");
fprintf(fasm, "\tpopq %%r14\n");
fprintf(fasm, "\tpopq %%r13\n");
fprintf(fasm, "\tpopq %%r10\n");
fprintf(fasm, "\tpopq %%rbx\n");
fprintf(fasm, "\tret\n", $2);
};
17. From your lab7 compiler, complete the following code for
addition and substraction. Add comments describing your code.
// to implement order of operations an addition_expr is categorized
// as a multiplicative expression or the addition or subtraction of
// an additive expression and a multiplicative expression
// (recursion results in left to right evaluation).
additive_expr:
multiplicative_expr
| additive_expr PLUS multiplicative_expr {
fprintf(fasm,"\n\t# +\n");
if (top<nregStk) { // if can fit in working registers
fprintf(fasm, "\taddq %%%s,%%%s\n", // pops two elements from stack, and puts
regStk[top-1], regStk[top-2]); // their sum on the top of the stack.
top--; // total change in stack size -1.
}
}
| additive_expr MINUS multiplicative_expr {
fprintf(fasm,"\n\t# -\n");
if (top<nregStk) {
fprintf(fasm,"\tsubq %%%s, %%%s\n", // pops two elements from the stack, and puts
regStk[top-1], regStk[top-2]); // their difference on the top of the stack.
top--; // total change in stack size -1.
}
};
18. From your lab7 compiler, complete the following code for WHILE
loop. Add comments describing your code.
statement:
assignment SEMICOLON
...
| WHILE LPARENT {
// start here: reserves a label for this while loop.
$1=nlabel;
nlabel++;
// label of last loop entered so you can break out of it.
// broken as you can call break after you leave an internal loop but was sufficient
// for required cases. Alternative would be to have a loop "stack" per function scope.
fprintf(fasm, "continue_%d:\n", $<my_nlabel>1); // continue loop from here
} expression RPARENT { // generate code to eval expression
// falls through to here
fprintf(fasm, "\tcmpq $0, %%rbx\n"); // if the top of the stack is zero, was false
fprintf(fasm, "\tje break_%d\n", $<my_nlabel>1);// leave loop.
top--;
} statement { // otherwise continue running loop
// act3
fprintf(fasm, "\tjmp continue_%d\n", $<my_nlabel>1);
fprintf(fasm, "break_%d:\n", $<my_nlabel>);
}
...
;
19. From your lab7 compiler, complete the following code for assignment. Add comments describing your code.
assignment:
// NOTE: atm, a > (b=c) not supported
WORD EQUAL expression {
char * id = $1; // get the variables name.
int i = lookupLocalVar(id); // look it up in the var list.
if (i>=0) {
// local variable, so assign to stack at proper offset.
fprintf(fasm, "\t#Assign to Local var %s\n", id);
fprintf(fasm, "\tmovq %%%s, %d(%%rsp)\n",
regStk[top-1], 8*(MAX_LOCALS-i) );
} else {
// global variable, assign to memory address labeled by id.
fprintf(fasm, "\t#Assign to Global var %s\n", id);
fprintf(fasm, "\tmovq %%%s, %s\n",regStk[top-1], id);
}
top--;
}
| WORD LBRACE expression RBRACE EQUAL expression {
int i, type;
char * id = $1;
i = lookupLocalVar(id);
// a[loc]=val; stack: ... loc val top
fprintf(fasm,"\n\t# %s[x]=a\n",id);
if (i>=0) { // if in the local var list
// get type.
type = local_vars_type[i];
fprintf(fasm, "\t#Push Local var %s\n", id);
// shift "loc" by appropriate amount so that
// "loc" (top-2) is the memory offset.
if(type==charstar_t) {
} else if(type==charstarstar_t) {
fprintf(fasm, "\tshlq $8, %%%s\n",regStk[top-2]);
} else if(type==longstar_t) {
fprintf(fasm, "\tshlq $8, %%%s\n",regStk[top-2]);
} else {
fprintf(stderr, "\n%s (%d) is not a pointer.\n",id,type);
exit(0);
}
// move "val" (top-1) onto the memory address on the stack+offset
// where the shifted "loc" (top-2) specifies the offset.
fprintf(fasm, "\taddq %d(%%rsp), %%%s\n",
8*(MAX_LOCALS-i), regStk[top-2] );
if(type==charstar_t) {
// use temperary register to avoid overwriting adjacent bytes
fprintf(fasm, "\tmovq %%%s, %%r12\n",
regStk[top-1]);
fprintf(fasm, "\tmovb %%r12b, (%%%s)\n",
regStk[top-2]);
} else {
fprintf(fasm, "\tmovq %%%s, (%%%s)\n",
regStk[top-1], regStk[top-2] );
}
top-=2;
} else {
// behavior similar to above method, however uses
// a global variable instead of a local variable
// to store the base memory address
i = lookupGlobalVar(id);
type = global_vars_type[i];
fprintf(fasm, "\t#Push Local var %s\n", id);
if(type==charstar_t) { // size is 1, do nothing
} else if(type==charstarstar_t) {
fprintf(fasm, "\tshlq $8, %%%s\n",regStk[top-2]);
} else if(type==longstar_t) {
fprintf(fasm, "\tshlq $8, %%%s\n",regStk[top-2]);
} else {
fprintf(stderr, "\n%s %d is not a pointer.\n",id,type);
exit(0);
}
fprintf(fasm, "\taddq %s, %%%s\n",
id, regStk[top-2]);
if(type==charstar_t) {
fprintf(fasm, "\tmovq %%%s, %%r12\n",
regStk[top-1]);
fprintf(fasm, "\tmovb %%r12b, (%%%s)\n",
regStk[top-2]);
} else {
fprintf(fasm, "\tmovq %%%s, (%%%s)\n",
regStk[top-1], regStk[top-2] );
}
top-=2;
}
}
;