Understanding Computer Systems: A Deep Dive into Operating Systems, Memory Management, and Assembly Language

1. For the following questions circle True or False The operating system has the power to suspend your program when it is running. TRUE FALSE The only reason the operating system is “special” is because it is the first program Loaded. TRUE FALSE In a time sharing system multiple process take turns running on the CPU. TRUE FALSE Caches would work well for a program that randomly accesses locations in memory.
TRUE FALSE An an Interrupt Drive I/O system the hardware is responsible for doing all of the Work necessary to service an interrupt. TRUE FALSE An a I/O Polling system the software is responsible for doing all of the work Necessary to service I/O. TRUE FALSE Intel is a little endian machine TRUE FALSE 2. On a little endian machine the least significant byte of a word appears at the lowest address but On a big endian machine the most significant byte of a word appears at the lowest address. 3. Explain the difference between I/O mapped I/O and Memory Mapped I/O. Which does Intel Use? In I/O mapped memory we partition the I/O and memory address space into two separate Spaces. The hardware has to support addintional instructions so as to disambiguate wether we Are writing to an I/O device or memory. Intel is uses I/O mapped approach and used IN and OUT for I/O but MOV for memory. In memory mapped I/O there is 1 unified address space for Both memory and I/O devices but we reserve certain addresses for I/O devices. The remaining Addresses are used for memory 4. Convert 0x17ADB to binary. : 1 0111 1010 1101 1011 5. Convert 101 1101 1011 1010 to hex.: 5DBA 6. Convert 7456
8 to base 5.: 111021 7. Write down the IEEE floating point format for the following number
63.25.
111111.01 * 2^0
1.111101 * 2^5
exponent = 127 + 5 = 132
mantissa = 111101 followed by 17 zeros Sign Exponent Mantissa 0 ‘10000100’ ‘11110100000000000000000’ 8. Assume that the label x contains the value 500. The following table shows the current contents Of memory Address 500 501 502 503 504 505 506 507 Value 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 After executing this instruction:
movl $0x12A96B7C, x. Show what the contents of Memory will be Address 500 501 502 503 504 505 506 507 Value 0x7C 0x6B 0xA9 0x12 0x4 0x5 0x6 0x7 9. What is wrong with the following assembly code? Write code that correctly implements the User’s intent. You may assume that all registers besides EAX are free to use.
movl x, (%eax)

2 operands are in memory, but instructions only support 1
1. Movl x, %ebx
2. Movl %ebx, (%eax) 10. Given that array is defined as int array[100][50][25] translate the following line of C To assembly code: X = Array[I][J][K]. Assume the following Array is stored in ESI X is EDI I is stored in EAX J is stored in EBX K is stored in ECX That all registers besides the ones mentioned are available to use. That I, J, K, and Array are not need after this line completes.
#first calculate I displacement
Imull $50
Imull $25
movl %eax, %edi
#then calculate J displacement
movl %ebx, %eax
Imull $25
addl %eax, %edi
#then calculate K displacement
addl %ecx, %edi
#finally assign X the value
movl (%esi, %edi, 4), %edi 11. Given that array is defined as int** array translate the following line of C to assembly Code: X = Array[I][J][K]. Assume the following Array is stored in ESI X is EDI I is stored in EAX J is stored in EBX K is stored in ECX That all registers besides the ones mentioned are available to use. That I, J, K, and Array are not need after this line completes.
movl (%esi, %eax, 4), %esi
movl (%esi, %ebx, 4), %esi
movl (%esi, %ecx, 4), %edi 12. Complete the following function, illegal. This function returns the ith argument of the nth stack frame located above this current frame. Arguments are numbered left to right from 0 to Number of arguments – 1. If we consider illegal, i would be argument 0 and n would be Argument 1. If n is 0 then we are considering illegal’s stack frame. If n is 1 then the frame of the Function that called illegal and so on.
int illegal(int i, int n){
//accesses the ith argument of the nth stack frame
int result;
__asm__(
//ecx will be used to keep track of how many frames we have
//passed through
“movl $0, %%ecx;”
//esi will contain the pointer to the current stack frame we are on
“movl %%ebp, %%esi;”
//first locate correct stack frame
“locate_frame:;”
“cmpl %[n], %%ecx;”
“jge get_arg;”
“movl (%%esi), %%esi;”
“incl %%ecx;”
“jmp locate_frame;”
//now that we are are at the correct frame access the variable
“get_arg:;”
“movl 8(%%esi, %[i], 4), %[result];”
:
[result] “=r” (result) :
[i] “r” (i), [n] “r” (n) :
“%ecx”, “%esi”, “cc”);
return result;
} 13. 14. Question showing stack ask what is and isn’t part of stack and stack frame. 15. Explain what direct memory access is. What is the purpose of direct memory access?



ECS 50 Final Review 1. Be able to convert hex to binary and vice versa.
1. Binary to hex
1. Group bits into groups of 4 starting from the right
2. Convert each group of 4 into its corresponding hex digit
2. Hex to binary
1. Convert each hex digit its 4 bit binary representation. 2. Be able to convert a number from one base to any other base.
1. Convert number to base 10
2. Repeatedly divide by new base until quotient is 0
3. Remainder written top down from right to left will be the number in the new base 3. Know how signed integers can be represented, 2’s compliment and sign magnitude.
1. See chapter 1 4. Be able to convert a real number to its floating point representation and vice versa.
1. IEEE format stores number as 1.Mantissa * 2^(exponent – 127)
2. First write number in its unsigned base 2 representation
3. If there is no decimal point place it at the end of the number
4. Multiply by 2^0
5. Shift decimal point so that decimal point comes just after leading 1
6. Adjust exponent so that the value of the number does not change
7. Exponent field will be exponent + bias of 127
8. Mantissa is 23 bits that come after decimal point. If there are not 23 bits append 0’s to
the right of the number until there are
9. Sign is 1 if number is negative and 0 if number is positive Sign Exponent Mantissa 31 30-23 22-0 5. Understand the two different ways of storing multidimensional arrays in memory: one Contiguous chunk and arrays of arrays 1. For one contiguous chunk 1. Know the difference between row major and column major 2. Given an array and indices be able to generate the equivalent single dimensional address 3. Given an array and indices be able to generate assembly code that could access the array At those indices
4. See: http://en.Wikipedia.Org/wiki/Row-major_order 2. For arrays of arrays 1. Given an array and indices be able to generate assembly code that could access the array At those indices
2. Just keep chasing those pointers 6. If a machine is little endian, what does that mean? If it is big endian?
1. Little Endian: the least significant byte of a word is stored at the lowest address
2. Big Endian: the most significant byte of a word is stored at the lowest address 3. Is Intel little endian or big endian?
1. Intel is little endian 7. Given C code be able to translate it to assembly. 8. What are the gcc C calling conventions?
1. Arguments are passed via the stack and are pushed in reverse order
2. EAX, ECX, and EDX are not considered to have live values when a function is called
3. Return values are placed in EAX 9. What is considered the stack?
1. Wherever ESP points and all addresses higher than it 10. All accesses to the stack must be of what size?
1. Word size 11. What is considered the stack frame?
1. All addresses of memory between EBP and ESP inclusive 12. (VERY IMPORTANT) Stack frames are chained, write assembly code to access the stack frame 2 levels above the current stack frame
1. Movl %ebp, %eax
2. Movl (%eax), %eax
3. Movl (%eax), %eax 13. Explain the difference between I/O mapped and Memory Mapped I/O
1. In I/O mapped I/O we separate the I/O space and the memory space
1. We use different instructions to access I/O devices (in and out) and memory (mov)
2. In memory mapped I/O we use a unified address space but reserve a portion of it for
I/O devices
1. We use the same instruction to access both memory and I/O devices
3. Intel uses the I/O mapped approach 14. Explain how I/O Polling works
1. The CPU repeatedly keeps asking the I/O device if it has input and once the I/O device
has input, the CPU reads it. This is extremely wasteful of time as it generally takes a
long time (relative to CPU speeds) for input to appear and the CPU is just spinning its
wheels until it does. 2. What does the software do?
1. Basically everything 3. What does the hardware do?
1. Basically nothing 15. Explain how Interrupt driven I/O works
1. See chapter 8.6 in the book 2. What does the software do?
1. Sets up the interrupt vector table
2. Provides the code for the interrupt service routines 3. What does the hardware do?
1. Provides interrupt capability 16. What is Direct Memory Access? How is it helpful?
1.
DMA is allowing I/O devices to directly access memory. This is helpful because it frees
up the CPU to do other work while I/O is being preformed 17. Given that the OS is just an ordinary program, what makes it “special?”
1. It is the first program loaded into memory 18. Explain how the OS loads a program into memory.
1. See chapter 9.2 in the book 19. Explain how the OS is loaded into memory.
1. See chapter 9.3 in the book 20. What does it mean for a program to be running?
1. The PC is pointing to an instruction that belongs to your program. 21. Can the OS stop your program while it is running?
1. No it cannot, because if your program is running then the OS isn’t. Your program can
be halted by either voluntarily giving up control by making a call to code located in the
OS when an interrupt occurs. 22. What does it mean if a program is marked as being in Sleep State?
1. The program is not currently runnable. Generally a program enters sleep state
because it is waiting for I/O to be preformed on its behalf. 23. What does it mean if a program is marked as being in Run State?
1. The program is eligible for a turn to be run. 24. Explain what time sharing is and how it works.
1. See chapter 9.4 in the book 2. What does the software do?
1. Sets up and maintains process table. Provides the code to do the actual switching of
the processes. 3. What does the hardware do?
1. Provides interrupt capabilities. 25. What are the principles that make caching work?
1. Temporal and Spatial locality 26. Where does the cache lie?
1. Between the CPU and memory 27. What does it mean for the cache to be transparent?
1. Neither the CPU or memory is aware that the cache is there 28. Explain how the cache is structured.
1. Sets of lines. Each line is made up of a contiguous sequence of bytes. 29. What is the purpose of the Valid bit?
1. It tells you if the information in a line is valid or not. It will be set to 0 when the
computer turns on and when a context switch happens. It will be set to 1 when a read
or write is performed on the line. 30. What is the purpose of the Tag bits?
1. They are used to identify lines. 31. What is the purpose of the Dirty bit?
1. It is used to determine if 32. What is the formula for determining what set a line is placed?
1. Floor(Address / line size) % Number of Sets 33. What is the formula for determining the line offset of an address?
1. Address & line size 34. How many ways are there in a Direct Mapped cache?
1. 1 35. How many sets are there in a Fully Associative cache? In a Set Associative cache?
1. FA = 1, SA: design parameter 36. Why are the cache’s designed to have the number of Sets and line size as powers of 2?
1. It turns the division into just bit look ups in the address, which is really fast. 37. (IMPORTANT) Be able to write inline assembly code. 38. Explain what each of the following inline constraint modifiers do 1. =
1. After the assembly code is completed the value in this register will be copied to the
associated C variable 2. +
1. This variable is both input and output 3. &
1. This variable is early clobber. This means that this value will be written to before
all the inputs are used up. This will force gcc to place it in its own register. 39. Translate the following C code into inline assembly Int* left_right_add(int* array, int len){ Int* result = malloc(len *sizeof(int)); Int index; Result[0] = array[0] + array[1] Result[len -1] = array[len-1] + array[len-2]; For(index = 1; index < len – 1; index++) Result[i] = array[i-1] + array[i] + array[i + 1]; Return result; }