____ Mutex-locks are needed only on multi-threaded programs.
____ Critical-sections should be small to increase parallelism in multi-processor
machines.
____ The number of page registers in a computer is equal to the number
of processes.
____ All processes running on the same CPU share the same page
table.
____ The user-time plus the system time is always larger than the real
time in a multi-processor machine.
____ The page-table register is updated every time there is a context
switch from one process to another.
____ The offset in a virtual memory address may be 345.
____ Non-accessed pages are prefered for replacement instead of modified
pages.
____ Read-only pages that are replaced may be written back to the backing
store.
____ Text, data and BSS is backed by swap space.
____ Semaphores may have a negative count after calling sema_post().
____ COFF is an executable format used on Windows.
____ Semaphores initialized with 0 may be used as mutex_locks.
____ Multiple processes may share the data section of a program in
physical memory as long as the memory is not modified.
____ Most threads in a system are in ready state.
____ There are less than two running process in a dual processor computer.
____ Most of the CPU time is spent on interrupts.
____ TLBs speed up the translation from virtual to physical addresses.
____ Non-preemptive scheduling does not need mutex-locks.
____ The number of stacks in a process is equal than the number of
threads.
____ Best-Fit leads to more fragmentation than first-fit.
____ An object returned by malloc could have an address like 0x100283
____ Most of the processes' CPU bursts are completed before the time
quantum expires.
____ Calling mutex_unlock in an arbitrary order may lead to deadlocks.
____ During starvation at least one thread will never be able to run
again.
____ open() is implemented in user space.
____ When a process updates memory that has been memory mapped from
a file, the OS updates the file in disk immediately.
____ pthread_create() is faster than forking a process.
____ In the bounded buffer problem solution using semaphores, the readBuffer()
procedure waits on a semaphore that is initialized to the number of buffers
available.
____ cond_signal() will need to wait if no other thread is waiting
on cond_wait().
2. Write the inequality for system, user and system time in a multiprocessor
system. Mention in which situation the system time plus the user time could
be larger than the real time.
3. Enumerate and describe the problems involved using malloc and free.
4. Write the steps for cond_wait( cond, mutex ) and cond_signal( cond
) calls.
5. Explain step by step what will happen after a process tries to load
data from an address in a non-resident page.
6. Explain step by step what will happen the first time a process tries
to write into a data page.
7. Explain how the context switch among threads is different than the
context switch among processes.
8. Mention the synchronization problems you see in the following malloc implementation:
void * malloc( int size ) {9. The following three threads have access to five databases. Each database has its own mutex lock.mutex_lock(&m);
if ( size < 0 ) {
return;
}if ( no memory in free list to satisfy request ) {
new_mem = get memory from os
free( new_mem );
}mem = search memory in free list
return mem;
}void free( void * mem ) {
mutex_lock( &m);
return memory to free list
mutex_unlock(&m);
}
thread1()
{
while (1) {
mutex_lock( &mutex_dbA);
mutex_lock( &mutex_dbF);
mutex_lock( &mutex_dbI);// Access dbA, dbF, dbI
mutex_unlock( &mutex_dbA);
mutex_unlock( &mutex_dbF);
mutex_unlock( &mutex_dbI);
}
}thread2()
{
while (1) {
mutex_lock( &mutex_dbB);
mutex_lock( &mutex_dbF);
mutex_lock( &mutex_dbG);// Access dbB, dbF, dbG
mutex_unlock( &mutex_dbB);
mutex_unlock( &mutex_dbF);
mutex_unlock( &mutex_dbG);
}
}thread3()
{
while (1) {
mutex_lock( &mutex_dbB);
mutex_lock( &mutex_dbG);
mutex_lock( &mutex_dbI);// Access dbB, dbG, dbI
mutex_unlock( &mutex_dbB);
mutex_unlock( &mutex_dbG);
mutex_unlock( &mutex_dbI);
}
}
10. The procedures insert()adds an item
to the list pointed by head. The procedure removeFirst()removes
an item from the list. If insert()
is used by one thread and removeFirst()is
used by another thread,
a) give one sequence of steps that can corrupt the list. You may use
the labels (1) to (6) 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;
}
const int MAX_BUFF_SIZE=256;
char common_buffer[ MAX_BUFF_SIZE]
void initialize()
{
// Add initializations here
}
void writemany( int wsize, char * wdata){
}
void readmany( int rsize, char * rdata) {
}
12. From your malloc implementation write the code for free(). Add comments
to describe the outline of the procedure. Be as detailed as possible.
| void free( void * ptr )
{ }
|
13. IMPORTANT: Use semaphores in this problem. Complete
the class MReadNWriteLock that implements a generalization of read/write
locks. These locks either allow at most M readers or at most N writers
but not both. For example, if one thread is holding the lock in write mode,
reader threads will have to wait. If one thread is holding the lock in
read mode, writer threads will have to wait. It is possible to have up
to N writers holding the lock in write mode. If writer thread N+1 tries
to write, it 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.
| class MReadNWriteLock {
/* Add other fields here */ public:
MReadNWriteLock ::MReadNWriteLock ( int m, int n )
} MReadNWriteLock ::readLock()
} MReadNWriteLock ::writeLock()
} MReadNWriteLock ::readUnlock()
} MReadNWriteLock ::writeUnlock()
}
|