| Question |
Max |
Grade |
| T/F |
10pts |
|
| 1-10 |
40 pts |
|
| 11. |
10 pts. |
|
| 12. |
10 pts. |
|
| 13. |
15pts. |
|
| 14. |
15pts. |
|
| Total: |
100pts. |
____ The last step in a fage fault is to retry the offending
instruction.
____ COFF is an executable file format used in in Windows.
____ The backing-store of the Stack is swap space.
____ TLBs speed up the translation from virtual to physical addresses. .
____ Best-Fit leads to more fragmentation than first-fit.
____ The page-table register is updated every time there is a
context switch from one thread to another.
____ Calling mutex_unlock in an arbitrary order may lead to deadlocks.
____ truss is a UNIX command to show the number of users in the system.
____ The file offset pased to mmap should be a multiple of a page size.
____ mmap() for a shared memory section returns the same address for
each caller process.
2. (4 pts) Explain why programs use a malloc library instead of
calling sbrk/mmap/unmap directly.
3. (4 pts) Explain what is "locality of reference".
4. (4 pts) Explain how you could make your malloc/free
implementation in lab7 tolerant to double free's.
5. (4 pts) Explain how VM memory speeds up the allocation of
zero-initialized memory for stack or heap.
6. (4 pts) Explain what is internal and external fragmentation.
7. (4 pts) Give the list of advantages and disadvantages of a single
free list allocator compared to a segregated free list allocator.
8. (4 pts) Compute the external fragmentation of a single free list
alocator that has objects of sizes 10, 30, 30, 20, 10 in the free list.
9. (4 pts) The following code shows an implementation of
a single linked list One thread runs the insert call and another thread
runs the removeFirst call.
a) give one sequence of steps that can make the same node to be returned twice by
removeFirst. Use the labels (1) to (7) at the left of each
instruction to describe your solution.
b) Add the mutex_lock/mutex_unlock()
calls to the code to solve the list corruption such that they cover the
minimum number of steps that
form the critical section.
struct List {
int val;
int next;
};struct List * head = NULL;
void insert( int val )
{
(1)List tmp = new List;
(2)tmp->val = val;
(3)tmp->next = head;
(4)head = tmp;
}
Struct List * removeFirst()
{
(5) List tmp = head;
(6) head = tmp->next;
(7) return tmp;
}
10. (4 pts) Add the necessary code to the insert() and removeFirst() functions to make them synchronized. removeFirst() will have to wait if the list is empty. insert() will have to wait if there are already 20 elements in the list. Use condition variables. Add also the variables you need.
struct List {
int val;
int next;
};struct List * head = NULL;
// More variables
main()
{// DO any initializations here
}
void insert( int val )
{
List tmp = new List;
tmp->val = val;
tmp->next = head;
head = tmp;
}
Struct List * removeFirst()
{
List tmp = head;
head = tmp->next;
}
| 11. (10 pts) IMPORTANT: Use condition
variables in this problem. Complete the class MReadNWriteLock that
is
a generalization of the read/write locks but that limits the
number
of readers to M and the number of writers to N. This kind of
locks
allows at most M readers or N writers but not both. For example, if at
least
one thread is holding the lock in write mode, reader threads will have
to
wait but not writer threads. If at least one thread is holding the lock
in
read mode, writer threads will have to wait. It is possible to have up
to
M reader threads. If thread M+1 tries to read, it will block until
another
reader thread unlocks the lock. It is possible to have up to N writer
threads.
If thread N+1 tries to write, it will block until another writer thread
unlocks
the lock. |
|
class MReadNWriteLock { |
| 12. (10 pts) Repeat problem 8 but now using semaphores. |
| class MReadNWriteLock { /* Add other fields here */ public: MReadNWriteLock( int m ); readLock(); writeLock(); readUnlock(); writeUnlock(); }; void MReadNWriteLock ::readLock() { } void MReadNWriteLock ::writeLock() { } void MReadNWriteLock ::readUnlock() { } void MReadNWriteLock ::writeUnlock()
|
| 13. (15 pts) From lab7
write the method int void
Allocator::freeObject( void * ptr )
that returns an object pointed by ptr back to the free list or unmaps
it. If you need
helper functions also include them in your implementation. |
|
void
|
| 14. (15 pts) IMPORTANT: Use condition variables in this problem. Write a class AlertTable that implements two methods: void insert(key, data) and char * remove(key). The method insert(key,data) will add the pair (key,data) to the table and will wakeup any thread calling remove(key) that is waiting for that specific key. The method remove(key) will check if there is an entry already with that key in the table and it will remove it if it is found. Otherwise, it will wait until that entry is inserted. remove(key) will return the data that corresponds to that key. If two remove(key) calls wait simultaneously for the same key, the oldest one will wakeup after the first insert call for that key and the newest one will wakeup after a subsequent insert call with the same key. Implement the table as a list, array, hash table or in any way you want. There is no limit in the size of the table. The type of the key is char * and the type of data is a generic pointer void * with unspecified length. |
struct AlerTableEntry { char * key; void * data; // Other fields }; class AlertTable { // Declare alert table and other fields public: AlertTable(); void insert(char * key, void * data); void * remove(char * key); }; Alerttable::AlertTable() { // Write ay initializations. } void AlertTableEntry::insert(char * key, void *data) { } char * AlertTableEntry::Remove(char * key) { } |