CPSC 213, Final Exam Review Questions
1 Execution in a Simple Machine
1.1 For each of the following, indicate whether the value is know statically or dynamically by placing the
word static or dynamic next to each.
1.1a The address of a global variable in C:
1.1b The address of an element of a static array in Java:
1.1c The address of an instance variable in Java.
1.1d The offset of an instance variable from the beginning of the object that contains it in Java:
1.1e The address of the code that implements a return statement.
1.1f The address of the instruction that executes immediately after a return statement.
1.1g The value of &a.i where a is a global variable in the C program with the following declaration.
typedef struct { int i; } A;
A a;
1.1h The value of &a->i where a is a global variable in the C program with the following declaration. typedef struct { int i; } A;
A* a;
1.1i The address of a local variable.
1.1j The position of a local variable in its activation frame.
1.1k The code address of a static method.
1.1l The code address of an instance method (i.e., a method that is not declared static).
1.2 What is the value of i after the following C code executes?
int a[10] = {0,1,2,3,4,5,6,7,8,9};
int i = *( &a[3] + 2 + *(a+1) );
1.3 Consider the following C snippet. All three variables are global variables.
int i;
int a[i];
int * b;
void foo () {
a[i] = b[3]; }
Give the SM213 instructions that implement the statement a[i] = b[3];. Give all variables allocated by the compiler some arbitrary address and clearly comment your code.
1.4 Java and C deallocate dynamically created objects (i.e., heap-allocated objects) differently. Briefly describe the approach each uses. Give one significant benefit of each approach.
1.5 What is a memory leak? Give an example of a type of program where it could be a big problem. State whether Java solves this problem entirely, somewhat or not at all. Justify your answer.
1.6 Would it be possible to implement a compiler that used the heap, instead of the stack, to store activation frames? Give one important drawback of this approach and explain.
1.7 What is the difference between pc-relative and absolute jumps? Give one advantage of each. Explain.
1.8 Java and C do not allow the size of local variables or instance variables to be determined at run- time. How does this restriction simplify the machine instructions the compiler generates for accessing these variables?
2 Device I/O
2.1
2.1a Give one advantage and one disadvantage of interrupts. What operating system feature is designed
Short Answer.
to compensate for this disadvantage. Explain very briefly.
2.1b What are Programmed IO (PIO) and DMA used for? In what way is DMA better? List one thing PIO can do that DMA can’t.
2.2 Give Java pseudo code necessary to add interrupt handling to the Simple Machine. Assume the CPU has the following new registers:
• isDeviceInterrupting — 0 iff a device has interrupted
• interruptType — number (starting at 0) of the device that has interrupted • interruptVectorBase — base address of the interrupt-transfer jump table
3 Virtual Processors
3.1
3.1a What is it about device access that lead to the development of the virtual processor?
3.1b Give one key difference between virtual processors (i.e., threads and/or processes) and the physical CPU.
3.1c What is the difference between a process and a thread?
3.2 Use the memory-register-access syntax (e.g.,, m[a] ← r[n]) to list all of the steps necessary to perform a thread switch between the current thread and a thread who’s thread-control block’s base address is stored in register r0. Be sure to save what is necessary about the current thread so that it can be started sometime later. You may layout the thread control block any way you like. Document your assumptions and show your work.
Short Answers.
2
4 Synchronization 4.1 Short Answers.
4.1a Is any special memory hardware needed to implement synchronization in a multi-processor system?
4.1b What is the difference between spin waiting and blocking waiting. Give one advantage of each
relative to the other.
4.1c Why is it better to spin-wait reading a lock with a normal read instruction first before attempting to lock the lock with an atomic read-write instruction?
4.1d Do semaphores provide spin- or blocking-based synchronization?
4.2 Give pseudo code of a program that uses semaphores to implement mutual exclusion.
4.3 Givepseudocodeofaprogramthatusessemaphorestoimplementasharedqueuewithtwooperations: enqueue and dequeue. Store the queue in an array. Use semaphores to have dequeue block if the queue is empty and to have enqueue unblock a waiting dequeue when it adds an item to the queue.
3