Quiz
CS1550 Midterm Prep
This quiz has question types that open in the usual player.
Questions in this quiz (107)
1A Mutex is safer to use for mutual exclusion than a counting semaphore because a Mutex can only be up()’ed by the same process that down()’ed it.
- ATrue
- BFalse
2Making a system call results in a voluntary transition from user mode to kernel mode.
- ATrue
- BFalse
3A zombie process switches to the terminated state immediately after being in the waiting state.
- ATrue
- BFalse
4Assuming lock is a shared integer, initialized as lock = 0;, if two processes execute the instruction TestAndSet(&lock) in parallel at the same time on two CPU cores, both processes will get the same return value from the instruction
- ATrue
- BFalse
5A semaphore that is used to enforce mutual exclusion should be initialized to 0
- ATrue
- BFalse
6When the following program runs, the fork system call will be called exactly two times by
each process.
int main(){
fork();
fork();
}- ATrue
- BFalse
7Copy-on-Write is a mechanism that avoids unnecessary memory copying when fork() is immediately followed by an exec() call by the child process.
- ATrue
- BFalse
8All child processes created using fork() will eventually get adopted by the init process
- ATrue
- BFalse
9Zombie processes may waste system resources because the operating system does not completely free up their resources until their parents wait() on them or exit().
- ATrue
- BFalse
10A process that has multiple threads also has multiple stacks and multiple heaps.
- ATrue
- BFalse
11On a single-core system, since the CPU can do only one thing at a time, there is no need to
protect shared data in a multi-process application.- ATrue
- BFalse
12With Hoare semantics, the ConditionVariable.wait operation must be implemented as a system call.
- ATrue
- BFalse
13This question refers to the semaphore-based implementation of Lock and ConditionVariable that we discussed in class (the one with mutex, next, and condSem semaphores).
The waiting queue of the next semaphore cannot have more than one process waiting.- ATrue
- BFalse
14This question refers to the semaphore-based implementation of Lock and ConditionVariable that we discussed in class (the one with mutex, next, and condSem semaphores).
It is possible for one process to start at the mutex’s waiting queue, move out of it then enter the next’s waiting queue, move out of it then enter the waiting queue of condSem of a condition variable, move out of it then enter the waiting queue of condSem of another condition variable.- ATrue
- BFalse
15• address of f1() is 0x79229
• address of f2() is 0x27170
• address of f6() is 0x21237
Assume also that the contents of the syscalls table are as follows:
• syscalls[0] = 0x27170
The pseudo-code for the functions is as follows.
f2 () :
X : print 21 ,729
ret
f6 () :
print 50 ,698
iret
Which mode will the CPU be while executing the code of f2()?
- AKernel
- BUser
- CNot enough information
16• address of f1() is 0x79229
• address of f2() is 0x27170
• address of f6() is 0x21237
Assume also that the contents of the syscalls table are as follows:
• syscalls[0] = 0x27170
The pseudo-code for the functions is as follows.
f2 () :
X : print 21 ,729
ret
f6 () :
print 50 ,698
iret
Which mode will the CPU be while executing the code of application?- AKernel
- BUser
- CNot enough information
17• address of f1() is 0x79229
• address of f2() is 0x27170
• address of f6() is 0x21237
Assume also that the contents of the syscalls table are as follows:
• syscalls[0] = 0x27170
The pseudo-code for the functions is as follows.
f2 () :
X : print 21 ,729
ret
f6 () :
print 50 ,698
iret
The address of the IDT table is 0x45931. What would be the content of the IDT register inside
the CPU?- A0
- B0x45931
- C0x459
- DNot enough information
18• address of f1() is 0x79229
• address of f2() is 0x27170
• address of f6() is 0x21237
Assume also that the contents of the syscalls table are as follows:
• syscalls[0] = 0x27170
The pseudo-code for the functions is as follows.
f2 () :
X : print 21 ,729
ret
f6 () :
print 50 ,698
iret
Assuming there is only one syscall and you are to add a second one. The function implementing
the new syscall is f1(). What is the index of the syscalls entry that you will need to change to add the
new system call?- A0
- B1
- C15
- D0x63342
19• address of f1() is 0x79229
• address of f2() is 0x27170
• address of f6() is 0x21237
Assume also that the contents of the syscalls table are as follows:
• syscalls[0] = 0x27170
The pseudo-code for the functions is as follows.
f2 () :
X : print 21 ,729
ret
f6 () :
print 50 ,698
iret
To add the second syscall, what value would you put in the syscalls entry that you will change?- A6
- B0x45931
- C0x63342
- D0x79229
20• address of f1() is 0x79229
• address of f2() is 0x27170
• address of f6() is 0x21237
Assume also that the contents of the syscalls table are as follows:
• syscalls[0] = 0x27170
The pseudo-code for the functions is as follows.
f2 () :
X : print 21 ,729
ret
f6 () :
print 50 ,698
iret
When a keyboard key was pressed, 50,698 was printed. What address is stored at IDT[1]?- A0x21237
- B0x50968
- C6
- D0x63342
- ENot Enough Information
21Which of the following may occur when a process calls up() on a semaphore?
Assume a multi-core system.- Amore than one process wake up and all of them immediately run
- B2 more than one process wake up and all of them stay in the ready queue
- C2 more than one process wake up but only one of them immediately runs
- Done process wakes up and stays in the ready queue
- Eno process wakes up
- Fone process wakes up and immediately runs
22Consider a parent process P that has forked a child process C. What happens when P exits while C is waiting for an I/O operation?
- AC immediately becomes a zombie process
- BP cannot exit while C is waiting for an I/O operation
- CC immediately switches to another parent process
- DP immediately becomes an orphan process.
23In the below pseudo-code, the programmer intends that g() not execute unless f() has executed.
The programmer used a monitor with two methods t1() and t2(). Each method is called by a different
thread. The monitor (i.e., class Ordering) has other methods that call cv.broadcast(&l).
public class Ordering {
private int f_ran = FALSE ;
private Lock l ;
private ConditionVariable cv ;
// The below method is called by a thread
public void t1 () {
l . acquire () ;
if ( f_ran == FALSE )
cv . wait (& l ) ;
g () ; /* <-- It is an error if g () executes before f () */
l . release () ;
}
// The below method is called by another thread
public void t2 () {
l . acquire () ;
f () ;
cv . signal (& l ) ;
f_ran = TRUE ;
l . release () ;
}
}
(Mark all the apply) Which of the following will guarantee that the above solution is correct?- Amove cv.broadcast after l.release
- Bchange the if condition to (f_ran == TRUE)
- Cchange cv.broadcast to cv.signal
- Dchange the if statement in t1() to a while loop
- Emove f_ran = TRUE; before cv.broadcast
24Consider the following code. Draw a diagram illustrating the created process tree.
int main(){
int a=-1, b=-1, c=-1, d=-1;
a = fork();
b = fork();
if(c == 0){
d = fork();
}
fork();
printf("Hi!\n");
return 0;
}
The number of times the string Hi is printed is [blank_start].[blank_end]- A8
25List two cases that cause a process’s state to change from “running" to “terminated"?
- AProcess calls wait()
- BProcess calls halt()
- CProcess calls exit()
- DProcess calls fork()
- EAnother process calls kill()
26The address of the IDT table is 57,960. What would be the content of the IDT register inside the CPU?
[blank_start]______[blank_end]
- A57960
27Which of the functions in memory is more likely to be the Interrupt Service Routine (ISR) for handling system calls?
- ANone of these
- Bf2
- Capplication
- Df7
- Ef8
- Ff1
- Gf3
- Hf6
- If5
- Jf4
28Assume the addresses of the depicted functions in memory are the following:
address of f1() is 62,912
address of f2() is 21,466
address of f3() is 72,509
address of f4() is 32,089
address of f5() is 57,629
address of f6() is 39,867
address of f7() is 52,414
address of f8() is 57,469
address of f9() is 85,464
address of the application is 80,277
Assume also that the contents of the IDT table are as follows:
IDT[0] = 21,466
IDT[1] = 57,469
IDT[2] = 57,629
IDT[3] = 32,089
IDT[4] = 39,867
IDT[5] = 72,509
IDT[6] = 85,464
IDT[64] = 52,414
IDT[100] = 62,912
Given the following pseudo-code for the functions (iret is the return-from-interrupt instruction),
f1()
print 62,912
iret
f2()
X: print 21,466
iret
f3()
print 72,509
iret
f4()
print 32,089
iret
f5()
print 57,629
iret
f6()
print 39,867
iret
f7()
call syscalls[%eax]
iret
f8()
print 57,469
iret
f9()
print 85,464
iret
application
L1: a = a + 1
---> network packet received
L2: b = a*b
ret
What will be printed when the application executes? Note that a network card interrupt will be triggered between the execution of L1 and L2 in the application.
[blank_start]________[blank_end]- A32089
29Assume the addresses of the depicted functions in memory are the following:
address of f1() is 19,113
address of f2() is 95,139
address of f3() is 32,398
address of f4() is 50,867
address of f5() is 65,452
address of f6() is 25,164
address of f7() is 76,081
address of f8() is 33,222
address of f9() is 10,881
address of f10() is 63,881 (not shown in the diagram)
address of f11() is 65,674 (not shown in the diagram)
address of f12() is 47,165 (not shown in the diagram)
address of f13() is 84,015 (not shown in the diagram)
address of f14() is 29,290 (not shown in the diagram)
address of the application is 35,211
Assume also that the contents of the IDT table are as follows:
IDT[0] = 95,139
IDT[1] = 33,222
IDT[2] = 65,452
IDT[3] = 50,867
IDT[4] = 25,164
IDT[5] = 32,398
IDT[64] = 76,081
IDT[100] = 19,113
Assume also that the contents of the syscalls table are as follows:
syscalls[0] = 63,881
syscalls[1] = 10,881
syscalls[2] = 47,165
syscalls[3] = 29,290
syscalls[4] = 84,015
syscalls[5] = 65,674
Given the following pseudo-code for the functions (iret is the return-from-interrupt instruction and int is the software interrupt instruction),
f1()
print 19,113
iret
f2()
X: print 95,139
iret
f3()
print 32,398
iret
f4()
print 50,867
iret
f5()
print 65,452
iret
f6()
print 25,164
iret
f7()
call syscalls[%eax]
iret
f8()
print 33,222
iret
f9()
print 10,881
ret
f10()
print 63,881
iret
f11()
print 65,674
iret
f12()
print 47,165
iret
f13()
print 84,015
iret
f14()
print 29,290
iret
application
L1: a = a + 1
L2: b = a*b
L3: move 4, %eax //eax = 4
L4: int 64
ret
What will be printed when the application executes?
[blank_start]________[blank_end]- A84015
30Assume the addresses of the depicted functions in memory are the following:
address of f1() is 57,261
address of f2() is 30,737
address of f3() is 80,384
address of f4() is 60,413
address of f5() is 58,147
address of f6() is 90,188
address of f7() is 44,141
address of f8() is 51,093
address of f9() is 36,385
address of f10() is 61,595 (not shown in the diagram)
address of f11() is 10,343 (not shown in the diagram)
address of f12() is 61,933 (not shown in the diagram)
address of f13() is 27,075 (not shown in the diagram)
address of f14() is 75,765 (not shown in the diagram)
address of the application is 97,487
Assume also that the contents of the IDT table are as follows:
IDT[0] = 30,737
IDT[1] = 51,093
IDT[2] = 58,147
IDT[3] = 60,413
IDT[4] = 90,188
IDT[5] = 80,384
IDT[64] = 44,141
IDT[100] = 57,261
Assume also that the contents of the syscalls table are as follows:
syscalls[0] = 61,595
syscalls[1] = 36,385
syscalls[2] = 61,933
syscalls[3] = 75,765
syscalls[4] = 27,075
syscalls[5] = 10,343
Assuming that 0 means kernel mode and 1 means user mode, what will be the value of the mode bit inside the CPU when line X (inside f2) starts executing?
[blank_start]______[blank_end]- A0
31Assume the addresses of the depicted functions in memory are the following:
address of f1() is 20,444
address of f2() is 62,221
address of f3() is 31,235
address of f4() is 38,903
address of f5() is 18,138
address of f6() is 94,542
address of f7() is 83,916
address of f8() is 56,732
address of f9() is 78,828
address of f10() is 57,056 (not shown in the diagram)
address of f11() is 70,978 (not shown in the diagram)
address of f12() is 99,910 (not shown in the diagram)
address of f13() is 30,703 (not shown in the diagram)
address of f14() is 97,368 (not shown in the diagram)
address of the application is 82,197
Assume also that the contents of the IDT table are as follows:
IDT[0] = 62,221
IDT[1] = 56,732
IDT[2] = 18,138
IDT[3] = 38,903
IDT[4] = 94,542
IDT[5] = 31,235
IDT[64] = 83,916
IDT[100] = 20,444
Assume also that the contents of the syscalls table are as follows:
syscalls[0] = 57,056
syscalls[1] = 78,828
syscalls[2] = 99,910
syscalls[3] = 97,368
syscalls[4] = 30,703
syscalls[5] = 70,978
Assuming that 0 means kernel mode and 1 means user mode, what will be the value of the mode bit inside the CPU when line Y (inside the application) starts executing?
[blank_start]______[blank_end]- A1
32Assume the addresses of the depicted functions in memory are the following:
address of f1() is 93,909
address of f2() is 26,322
address of f3() is 63,820
address of f4() is 65,994
address of f5() is 17,305
address of f6() is 56,378
address of f7() is 35,702
address of f8() is 21,578
address of f9() is 85,152
address of f10() is 18,044 (not shown in the diagram)
address of f11() is 22,044 (not shown in the diagram)
address of f12() is 15,847 (not shown in the diagram)
address of f13() is 98,972 (not shown in the diagram)
address of f14() is 92,151 (not shown in the diagram)
address of the application is 14,375
Assume also that the contents of the syscalls table are as follows:
syscalls[0] = 18,044
syscalls[1] = 85,152
syscalls[2] = 15,847
syscalls[3] = 92,151
syscalls[4] = 98,972
syscalls[5] = 22,044
Also assume the following pseudo-code for the functions (iret is the return-from-interrupt instruction, and int is the software interrupt instruction),
f1()
print 93,909
iret
f2()
X: print 26,322
iret
f3()
print 63,820
iret
f4()
print 65,994
iret
f5()
print 17,305
iret
f6()
print 56,378
iret
f7()
call syscalls[%eax]
iret
f8()
print 21,578
iret
f9()
print 85,152
ret
f10()
print 18,044
iret
f11()
print 22,044
iret
f12()
print 15,847
iret
f13()
print 98,972
iret
f14()
print 92,151
iret
application
L1: a = a + 1
L2: b = a*b
L3: move [eax], %eax //eax = [eax]
L4: int 64
ret
Which of the following CANNOT be used as an entry in the IDT table?
93,909, 26,322, 14,375,35,702- A93,909
- B26,322
- C14,375
- D35,702
33Assume the addresses of the depicted functions in memory are the following:
address of f1() is 74,110
address of f2() is 34,342
address of f3() is 50,040
address of f4() is 92,406
address of f5() is 42,267
address of f6() is 47,537
address of f7() is 96,444
address of f8() is 55,630
address of f9() is 39,899
address of f10() is 61,144 (not shown in the diagram)
address of f11() is 70,986 (not shown in the diagram)
address of f12() is 89,744 (not shown in the diagram)
address of f13() is 54,701 (not shown in the diagram)
address of f14() is 76,284 (not shown in the diagram)
address of the application is 38,822
Assume also that the contents of the syscalls table are as follows:
syscalls[0] = 61,144
syscalls[1] = 39,899
syscalls[2] = 89,744
syscalls[3] = 76,284
syscalls[4] = 54,701
syscalls[5] = 70,986
Recall that an ISR ends with a return-from-interrupt instruction (iret), whereas a syscall implementation function ends with a regular return instruction (ret).
Which of the following CANNOT be used as an entry in the IDT table?
74,110, 34,342, 47,537,61,144- A74,110
- B34,342
- C47,537
- D61,144
34Assume the addresses of the depicted functions in memory are the following:
address of f1() is 28,822
address of f2() is 12,918
address of f3() is 23,095
address of f4() is 93,362
address of f5() is 57,749
address of f6() is 35,474
address of f7() is 90,742
address of f8() is 18,402
address of f9() is 44,847
address of f10() is 43,227 (not shown in the diagram)
address of f11() is 49,298 (not shown in the diagram)
address of f12() is 39,084 (not shown in the diagram)
address of f13() is 65,781 (not shown in the diagram)
address of f14() is 31,720 (not shown in the diagram)
address of f15() is 96,344 (not shown in the diagram)
address of the application is 34,867
Assume also that the contents of the syscalls table are as follows:
syscalls[0] = 43,227
syscalls[1] = 44,847
syscalls[2] = 39,084
syscalls[3] = 31,720
syscalls[4] = 65,781
syscalls[5] = 49,298
Assuming only six syscalls exist, you are to add a seventh one. The function implementing the new syscall is f15(). What is the index of the syscall entry that you will need to change to add the new system call?
[blank_start]_____[blank_end]- A6
35Assume the addresses of the depicted functions in memory are the following:
address of f1() is 56,531
address of f2() is 10,590
address of f3() is 99,918
address of f4() is 46,531
address of f5() is 55,702
address of f6() is 67,921
address of f7() is 56,432
address of f8() is 22,587
address of f9() is 73,614
address of f10() is 37,528 (not shown in the diagram)
address of f11() is 22,191 (not shown in the diagram)
address of f12() is 43,519 (not shown in the diagram)
address of f13() is 11,369 (not shown in the diagram)
address of f14() is 25,898 (not shown in the diagram)
address of f15() is 58,085 (not shown in the diagram)
address of the application is 35,864
Assume also that the contents of the syscalls table are as follows:
syscalls[0] = 37,528
syscalls[1] = 73,614
syscalls[2] = 43,519
syscalls[3] = 25,898
syscalls[4] = 11,369
syscalls[5] = 22,191
Assuming only six syscalls exist, you are to add a seventh one. The function implementing the new syscall is f15(). What value would you put in the syscall entry that you change to add the new syscall?
[blank_start]_______[blank_end]- A58085
36System Call [blank_start]____[blank_end]
Interrupt [blank_start]_____[blank_end]
Return from system call [blank_start]_____[blank_end]
Fill in the blanks with either:
a. transition from kernel mode to user mode
b. voluntary transition from user mode to kernel mode
c. involuntary transition from user mode to kernel mode- Aa.
- Bb.
- Cc.
- Da.
- Eb.
- Fc.
- Ga.
- Hb.
- Ic.
37The operating system continuously runs on the CPU and is always resident in physical memory.
- ATrue
- BFalse
38Microkernel operating systems are faster than monolithic systems.
- ATrue
- BFalse
39Which of the following is not part of the operating system?
- AInterrupt Descriptor Table
- BInterrupt Descriptor Table Register
- CInterrupt Service Routines
- DSystem call table
- ESystem call implementations
40In a single-core system, it is safe to assume that mutual exclusion is guaranteed when interrupts are disabled around a critical section.
- ATrue
- BFalse
41
The code below is free from race conditions because every access to the shared variable x is surrounded by lock/unlock pair.
int x = 0; // shared variable
Lock l;
l.acquire();
if (x == 0) {
l.release();
l.acquire();
x++;
}
l.release();- ATrue
- BFalse
42On a single-core system, since the CPU can do only one thing at a time, there is no need to protect shared data in a multi-process application.
- ATrue
- BFalse
43Consider a system with two or more processes that run concurrently and share some variables. If errors in shared variables may result depending on the exact interleaving of the processes' instructions, the system has:
- Adeadlock
- Bstarvation
- Crace condition
- Dbusy waiting
44System calls change the privilege mode of the processor.
- ATrue
- BFalse
45At any point in time on a multi-core system, at least once CPU core must be running operating system code.
- ATrue
- BFalse
46Assuming lock is a shared integer, initialized to 0, if two processes concurrently execute TestAndSet(lock), both processes will get 1 as a return value.
- ATrue
- BFalse
47A shared integer that is used to implement a spinlock using the TestAndSet instruction should be initialized to 0.
- ATrue
- BFalse
48When the following program runs, how many processes will be created (including the first process)
int main(){
fork();
fork();
fork();
fork();
}- A4
- B32
- C8
- D16
- E0
49Copy-on-Write is a mechanism that avoids unnecessary memory copying when fork() is immediately followed by _______ in the child process.
- Aanother fork()
- Bwrite()
- Cexec()
- Dwait()
50All child processes created using fork() have a process ID of 0.
- ATrue
- BFalse
51Zombie processes waste system resources because the operating system does not free up their resources until their parents wait() on them.
- ATrue
- BFalse
52
The code below is free from race conditions because every access to the shared variable x is surrounded by lock/unlock pair.
int x = 0; // shared variable
Spinlock l;
l.lock();
if (x == 0) {
l.unlock();
l.lock();
x++;
}
l.unlock();- ATrue
- BFalse
53Each running thread has its own stack that is separate from every other thread's stack.
- ATrue
- BFalse
54Threads are cheaper to context switch than processes.
- ATrue
- BFalse
55The stack of a thread can be corrupted by a thread of another process.
- ATrue
- BFalse
56Threads within the same process automatically share memory, whereas processes need to explicitly share memory.
- ATrue
- BFalse
57Consider a parent process P that has forked a child process C. When P terminates while C is still running, C immediately switches to another parent process.
- ATrue
- BFalse
58Orphan processes waste system resources because they will immediately turn into zombie processes.
- ATrue
- BFalse
59Which of the following functions doesn't return in all cases? (Select all correct answers)
- Aint f(){ while(1); return 0;}
- Bfork()
- Cexecl()
- Dabort()
60Assume that p0 and scheduler are two pointers to struct proc (defined in proc.h). That is,
struct proc *p0, *scheduler;
Also, assume that p0 points to the PCB of process P0, and scheduler points to the PCB of the scheduler process. Which of the following is(are) correct way(s) of invoking the swtch routine that implements context switch in Xv6?- Aswtch(p0->context, scheduler->context)
- Bswtch(&(p0.context), scheduler.context)
- Cswtch(&(p0->context), scheduler->context)
- Dswtch(&(scheduler->context), p0->context)
- Eswtch(scheduler->context, p0->context)
61In Linux, a Zombie process may become an Orphan, but an Orphan process cannot become a Zombie.
- ATrue
- BFalse
62A child process created using fork() has the same process ID as its parent process.
- ATrue
- BFalse
63Identify all possible problems with the following code. TestAndSet is an atomic instruction that is explained in the lectures. Assume that the compiler and the CPU may reorder instructions to optimize performance.
int lock = 0; //lock is a shared variable
//Process P0
while(TestAndSet(&lock))
;
//critical section code
lock = 0;
//Process P1
while(TestAndSet(&lock))
;
//critical section code
lock = 0;- ADeadlock
- BA process may never be able to enter its critical section
- CRace condition
- DPriority inversion
64In the code below, how can we prevent instruction reordering (by the compiler or by the CPU) from causing race conditions?
int lock = 0; //lock is a shared variable
//Process P0
while(TestAndSet(lock))
;
//critical section code
lock = 0;
//Process P1
while(TestAndSet(lock))
;
//critical section code
lock = 0;- AAdd memory barrier instructions before the while loop and after lock = 0;
- BNothing. Race conditions will never happen even with instruction reordering.
- CUse CompareAndSwap instead of TestAndSet
- DAdd memory barrier instructions after the while loop and before lock = 0;
65A livelock happens when two or more processes are running but not making progress.
Why would the code below result in a livelock? Select the most accurate answer.
int lock = 1; //lock is a shared variable
Process P0:
while(TestAndSet(lock))
;
//critical section code
lock = 0;
Process P1:
while(TestAndSet(lock))
;
//critical section code
lock = 0;- Alock is initialized to 1 instead of 0
- BDeadlock
- CStarvation
- DInstruction reordering
- EPriority Inversion
66The code below resulted in a deadlock. Select the most accurate reason.
Semaphore s(0);
Process P0:
down(s);
//critical section code
up(s);
Process P1:
down(s);
//critical section code
up(s);- AStarvation
- Bs is initialized to 0 instead of 1
- CLivelock
- DInstruction reordering
- EPriority inversion
67The code below resulted in a race condition. Select the most accurate reason.
Semaphore s(1);
P0:
down(s);
//critical section code
up(s);
P1:
down(s);
//critical section code
up(s);
P2:
up(s);- As is initialized to 1 instead of 0
- BP0 was interrupted while in the critical section
- Cup(s) was called by P2 after P0 finished its critical section code but before P1 finished its critical section code
- DPriority inversion
- Eup(s) was called by P2 before both P0 and P1 finish their critical section code
- Fup(s) was called by P2 after both P0 and P1 finished their critical section code
68Which sequence of execution would result in priority inversion in the code below?
Semaphore s(1);
P0: //highest priority process
down(s);
//critical section code
up(s);
P1: //middle priority process
//long-running computation
P2: //lowest priority process
down(s);
//critical section code
up(s);- A1. P1
2. down(s) by P2
3. down(s) by P0 - B1. down(s) by P0
2. down(s) by P2
3. P1 - C1. P1
2. down(s) by P0
3. down(s) by P2 - D1. down(s) by P2
2. down(s) by P0
3. P1
- A1. P1
69Which sequence of execution would result in priority inversion in the code below?
int lock = 0; //lock is a shared variable
P0: //high-priority process
while(TestAndSet(lock))
;
//critical section code
lock = 0;
P1: //low-priority process
while(TestAndSet(lock))
;
//critical section code
lock = 0;- A1. TestAndSet() by P1
2. lock = 0 by P1
3. TestAndSet() by P0 - B1. TestAndSet() by P0
2. lock = 0 by P0
3. TestAndSet() by P1 - C1. TestAndSet() by P1
2. TestAndSet() by P0 - D1. TestAndSet() by P0
2. TestAndSet() by P1
- A1. TestAndSet() by P1
70Which of the following sequences of execution would result in the value of the shared variable x increased by 2 instead of 1.
int x = 0; // shared variable
Lock l;
P0:
l.acquire(); //line 1
if (x == 0) { //line 2
l.release(); //line 3
l.acquire(); //line 4
x++; //line 5
}
l.release(); //line 6
P1:
l.acquire(); //line 7
if (x == 0) { //line 8
l.release(); //line 9
l.acquire(); //line 10
x++; //line 11
}
l.release(); //line 12- A1. line 1-6
2. line 7-12 - B1. line 1
2. line 2
3. line 3
4. line 7-12
5. line 4-6 - C1. line 1-4
2. line 7-12
3. line 5-6 - D1. line 7-11
2. line 1-6
3. line 12
- A1. line 1-6
71Mutex and Binary Semaphore are different names for the same synchronization primitive.
- ATrue
- BFalse
72Every semaphore that is initialized to 1 is a binary semaphore.
- ATrue
- BFalse
73In the figures below, P0 and P1 are processes. P0 runs first and gets interrupted inside the critical section code. The scheduler then selects P1 to run. In part (a) of the figure, P1 runs until a timer interrupt occurs and P1 gets switched out, whereas in part (b), P1 is switched out before a timer interrupt occurs. Match each part of the figure with the code that is more likely to have caused the depicted behavior.
Code 1
int lock = 0; // shared variable
// The code for both P0 and P1
while ( TestAndSet ( lock ) == 1)
;
// critical section
lock = 0;
Code 2
Semaphore mutex (1); // shared variable
// The code for both P0 and P1
down ( mutex )
// critical section
up( mutex )
Code 1 [blank_start]____[blank_end]
Code 2 [blank_start]____[blank_end]
- APart (a)
- BPart (b)
- CPart (a)
- DPart (b)
74(Mark all that apply) Which of the following may occur when a process calls broadcast on a condition variable? Assume a single-core system.
- Ano process wakes up
- Bone process wakes up and immediately runs
- Cone process wakes up and stays in the ready queue
- Dmore than one process wake up but only one of them immediately runs
- Emore than one process wake up and all of them stay in the ready queue
- Fmore than one process wake up and all of them immediately run
75Consider the following implementation of an array-based stack data structure for a multi-threaded application.
1: const MaxStackSize = 100;
2:
3: class Stack {
4: // throws an exception when popping an empty stack,
5: // and when pushing into a full stack
6: //Shared variables
7: private int s[MaxStackSize]; //stack array
8: private int stackp; // stack top
9: private Semaphore sem; // For mutual exclusion.
10:
11: public Stack() {
12: stackp = 0;
13: sem = new Semaphore(1);
14: }
15:
16: public int Stack::pop() {
17: sem.down();
18: if(stackp == 0) {
19: throw new EmptyStackException("empty stack");
20: }
21: sem.up();
22: return s[--stackp];
23: }
24:
25: public void push(int item) {
26: sem.down();
27: if(stackp == MaxStackSize) {
28: throw new FullStackException("full stack");
29: }
30: s[stackp++] = item;
31: sem.up();
32: }
33: }
The implementation has three synchronization bugs. Match each line of code with the bug that it has.
Line 19 [blank_start]____[blank_end]
Line 22 [blank_start]____[blank_end]
Line 28 [blank_start]____[blank_end]
Options:
a. Forgetting to up the semaphore before leaving the pop method, potentially leading to deadlock.
b. Popping from an empty stack.
c. Pushing onto a full stack.
d. Forgetting to up the semaphore before leaving the push method, potentially leading to deadlock.
e. Accessing a shared variable outside of the critical section
f. No bugs- Aa.
- Bb.
- Cc.
- Dd.
- Ee.
- Ff.
- Ga.
- Hb.
- Ic.
- Jd.
- Ke.
- Lf.
- Ma.
- Nb.
- Oc.
- Pd.
- Qe.
- Rf.
76We are to write a program with two kinds of threads. Multiplier threads multiply a shared counter by N, and Divider threads divide the shared counter by N (where N is an integer > 0). There can be an arbitrary number of Multipliers and Dividers. The shared counter is set to one initially. Here are the program's requirements:
• The shared counter should never be less than 1.
• The shared counter should never stay at a value of N or more as long as there is a Divider in the system.
• Dividers must block until they can safely divide (i.e., without making the shared counter < 1).
We are implementing a Monitor to solve this problem.
// shared data
constant int N;
Monitor m;
Let's model the Multiplier and Divider threads using the following pseudocode.
//function executed by each Multiplier thread
void multiplier() {
while (1) {
m.multiply();
}
}
//function executed by each Divider thread
void divider() {
while (1) {
m.divide();
}
}
Select the correct implementation of the Monitor constructor.
public class Monitor {
private int counter; //shared counter
private ConditionVariable cv;
private Mutex l;
public Monitor(){
//TODO Initialize the instance and synchronization variables
}
public void multiply(){
//TODO Fill this method in, taking note of the constraints outlined above
}
public void divide(){
//TODO Fill this method in, taking note of the constraints outlined above
}
}- Acounter = 0;
cv.init();
l.init(); - Bcounter = 1;
cv.init();
l.init(); - Ccounter = N;
cv.init();
- Acounter = 0;
77We are to write a program with two kinds of threads. Multiplier threads multiply a shared counter by N, and Divider threads divide the shared counter by N (where N is an integer > 0). There can be an arbitrary number of Multipliers and Dividers. The shared counter is set to one initially. Here are the program's requirements:
• The shared counter should never be less than 1.
• The shared counter should never stay at a value of N or more as long as there is a Divider in the system.
• Dividers must block until they can safely divide (i.e., without making the shared counter < 1).
We are implementing a Monitor to solve this problem.
// shared data
constant int N;
Monitor m;
Let's model the Multiplier and Divider threads using the following pseudocode.
//function executed by each Multiplier thread
void multiplier() {
while (1) {
m.multiply();
}
}
//function executed by each Divider thread
void divider() {
while (1) {
m.divide();
}
}
Select the correct implementation of the Monitor multiply method.
public class Monitor {
private int counter; //shared counter
private ConditionVariable cv;
private Mutex l;
public Monitor(){
//TODO Initialize the instance and synchronization variables
}
public void multiply(){
//TODO Fill this method in, taking note of the constraints outlined above
}
public void divide(){
//TODO Fill this method in, taking note of the constraints outlined above
}
}- Apublic void multiply() {
l.acquire();
if(counter <= N)
cv.wait(&l);
counter = counter * N;
l.release();
} - Bpublic void multiply() {
l.acquire();
counter = counter * N;
cv.broadcast(&l);
l.release();
} - Cpublic void multiply() {
l.acquire();
counter = counter * N;
l.release();
} - Dpublic void multiply() {
l.acquire();
while(counter <= N)
cv.wait(&l);
counter = counter * N;
l.release();
}
- Apublic void multiply() {
78We are to write a program with two kinds of threads. Multiplier threads multiply a shared counter by N, and Divider threads divide the shared counter by N (where N is an integer > 0). There can be an arbitrary number of Multipliers and Dividers. The shared counter is set to one initially. Here are the program's requirements:
• The shared counter should never be less than 1.
• The shared counter should never stay at a value of N or more as long as there is a Divider in the system.
• Dividers must block until they can safely divide (i.e., without making the shared counter < 1).
We are implementing a Monitor to solve this problem.
// shared data
constant int N;
Monitor m;
Let's model the Multiplier and Divider threads using the following pseudocode.
//function executed by each Multiplier thread
void multiplier() {
while (1) {
m.multiply();
}
}
//function executed by each Divider thread
void divider() {
while (1) {
m.divide();
}
}
Select the correct implementation of the Monitor divide method.
public class Monitor {
private int counter; //shared counter
private ConditionVariable cv;
private Mutex l;
public Monitor(){
//TODO Initialize the instance and synchronization variables
}
public void multiply(){
//TODO Fill this method in, taking note of the constraints outlined above
}
public void divide(){
//TODO Fill this method in, taking note of the constraints outlined above
}
}- Apublic void divide() {
l.acquire();
while(counter < N)
cv.wait(&l);
counter = counter / N;
l.release();
} - Bpublic void divide() {
l.acquire();
counter = counter / N;
cv.broadcast(&l);
l.release();
} - Cpublic void divide() {
l.acquire();
while(counter >= N)
cv.wait(&l);
counter = counter / N;
l.release();
} - Dpublic void divide() {
l.acquire();
if(counter <= N)
cv.wait(&l);
counter = counter / N;
l.release();
}
- Apublic void divide() {
79A job is in the ready queue if it:
- Ahas all resources needed to execute
- Bhas all resources needed to execute except the CPU
- Cis waiting for I/O
- Dis waiting for an interrupt
80When a process is created using the classical fork() system call, which of the following is not inherited by the child process?
- Aprocess address space
- Bprocess ID
- Csignal handlers
- Dopen files
81Consider a system with two or more processes running concurrently and sharing variables. If errors in the values of the shared variables may occur depending on the exact interleaving of the processes' instructions, the system has:
- Arace condition
- Bstarvation
- Cbusy waiting
- Ddeadlock
82(Mark all that apply) Which of the following operations require(s) the executing code to be operating with high privilege (i.e., in kernel mode)?
- Arunning the implementation of wait() and signal() of a Condition Variable that has Hoare semantics
- Bsetting the system clock
- Cdisabling interrupts
- DInvoking a system call
83A running user process is interrupted by the timer, and the interrupt handler determines that the process has to be switched out. The process switches from the [blank_start]_____[blank_end] state to the [blank_start]_____[blank_end] state. Does the OS (short-term) scheduler have to run in that case? [blank_start]____[blank_end]
- AWaiting
- BReady
- CTerminated
- DRunning
- ENew
- FWaiting
- GReady
- HTerminated
- IRunning
- JNew
- Kyes
- Lno
84Consider the following C code that calls fork(). If you assume that a child process is always scheduled before its parent process, what will be the output?
int main () {
int i;
for (i = 0; i < 2; i++) {
if (fork () == 0) {
printf ("Child sees i = %d\n", i);
exit(0);
} else {
printf ("Parent sees i = %d\n", i);
wait(NULL);
}
}
}- AChild sees i = 0
Parent sees i = 0
Child sees i = 1
Parent sees i = 1 - BChild sees i = 0
Parent sees i = 1
Child sees i = 2
Parent sees i = 3 - CChild sees i = 0
Child sees i = 1
Parent sees i = 2
Parent sees i = 3 - DChild sees i = 0
Child sees i = 1
Parent sees i = 0
Parent sees i = 1
- AChild sees i = 0
85With modern hardware architectures, which have out-of-order execution and multiple cores, it is possible to solve the Critical Section Problem using user-level software only without any operating system support and without any support from the hardware (e.g., without using memory barrier instructions).
- ATrue
- BFalse
86A shared integer that is used to implement a spinlock using the TestAndSet instruction should be initialized to 0, whereas a semaphore that is used for mutual exclusion should be initialized to 1.
- ATrue
- BFalse
87In the below pseudo-code, the programmer intends that g() never executes before f(). The programmer used a Monitor with two methods, t1() and t2(). Assume that there are two threads; one calls t1() and the other calls t2(). Assume the Monitor has other methods, not shown in the code below, that call cv.broadcast(&l).
public class Ordering {
private int f_ran = FALSE;
private Mutex l;
private ConditionVariable cv;
// The below method is called by one thread
public void t1() {
l.acquire();
if (f_ran == FALSE)
cv.wait(&l);
g(); /* <-- It is an error if g() executes before f() */
l.release();
}
// The below method is called by another thread
public void t2() {
l.acquire();
f();
f_ran = TRUE;
cv.broadcast(&l);
l.release();
}
...
}
Which of the following will cause the above solution to allow g() to execute before f()?- Abusy waiting
- Brace condition
- Cspurious wakeup (wakeup by a broadcast that was intended to wakeup other thread(s))
- Dstarvation
88
Consider the following solution to the Sleepy Barber problem.
WaitingRoom wr = new WaitingRoom(NCHAIRS);
BarberChair bc = new BarberChair();
//Customer Process:
status = wr.custEnter();
if(status == WR_FULL){
return;
}
bc.wakeBarber();
bc.sitInChair(); // Wait for chair to be EMPTY, Change state to LONG_HAIR_CUSTOMER,
//Wait until state becomes SHORT_HAIR_CUSTOMER, Change state to EMPTY and return
//Barber Process:
while(TRUE){
status = wr.callNextCustomer();
if(status == WR_EMPTY){
bc.napInChair();
}
bc.cutHair(); // Wait until state becomes LONG_HAIR_CUSTOMER, then return with state being SHORT_HAIR_CUSTOMER
bc.tellCustomerDone(); // Return when state is EMPTY
}
public class WaitingRoom {
private Lock l;
private ConditionVariable cond;
private int NCHAIRS;
private int nfull;
private int ticketAvail;
private int ticketTurn;
public WaitingRoom(int NCHAIRS) {
nfull = 0;
ticketAvail = 0;
ticketTurn = -1;
this.NCHAIRS = NCHAIRS;
}
public int custEnter() {
l.acquire();
int ret;
if(nfull == NCHAIRS){
return WR_FULL; //<=================== A
}
else {
ret = MY_TURN;
int myTicket = ticketAvail++;
nfull++;
if(myTicket > ticketTurn){ //<=================== B
cond.wait(&l);
}
nfull--;
}
l.release();
return ret;
}
public int callNextCustomer() {
l.acquire();
ticketTurn++;
if(nfull == 0){
ret = EMPTY;
}
else {
ret = BUSY;
cond.broadcast(&l);
}
l.release();
return ret;
}
}
public class BarberChair {
private Lock l;
private ConditionVariable custUp, barberGetUp, sitDown, seatFree, cutDone;
private int state; //EMPTY, BARBER_IN_CHAIR, LONG_HAIR_CUSTOMER, SHORT_HAIR_CUSTOMER
private int custWalkedIn;
public BarberChair () {
state = EMPTY;
custWalkedIn = 0;
}
public void napInChair()
l.acquire();
if(custWalkedIn == 0){ // Cust could arrive before barber naps
state = BARBER_IN_CHAIR;
}
while(custWalkedIn == 0){
barberGetUp.wait(&l);
}
custWalkedIn = 0;
if(state == BARBER_IN_CHAIR){ /<================= E
state = EMPTY;
seatFree.signal(&l);
}
l.release();
}
public void wakeBarber() {
l.acquire();
custWalkedIn = 1; //<================= C
barberGetUp.signal(&l); //<================= D
l.release()
}
public void sitInChair() {
l.acquire()
while(state != EMPTY){
seatFree.wait(&l);
}
state = LONG_HAIR_CUSTOMER;
sitDown.signal(&l);
while(state != SHORT_HAIR_CUSTOMER){
cutDone.wait(&l);
}
state = EMPTY;
custUp.signal(&l);
l.release();
}
public void cutHair() {
l.acquire();
while(state != LONG_HAIR_CUSTOMER){
sitDown.wait(&l);
}
state = SHORT_HAIR_CUSTOMER;
cutDone.signal(&l);
l.release();
}
public void tellCustomerDone() {
l.acquire();
while(state != EMPTY){
custUp.wait(&l);
}
l.release();
}
}
What is wrong with line A in the above solution to the SleepBarber problem?- AShould call wait instead of return
- BReturning an invalid value
- CReturning without releasing the lock
- DThe line is correct
89
Consider the following solution to the Sleepy Barber problem.
WaitingRoom wr = new WaitingRoom(NCHAIRS);
BarberChair bc = new BarberChair();
//Customer Process:
status = wr.custEnter();
if(status == WR_FULL){
return;
}
bc.wakeBarber();
bc.sitInChair(); // Wait for chair to be EMPTY, Change state to LONG_HAIR_CUSTOMER,
//Wait until state becomes SHORT_HAIR_CUSTOMER, Change state to EMPTY and return
//Barber Process:
while(TRUE){
status = wr.callNextCustomer();
if(status == WR_EMPTY){
bc.napInChair();
}
bc.cutHair(); // Wait until state becomes LONG_HAIR_CUSTOMER, then return with state being SHORT_HAIR_CUSTOMER
bc.tellCustomerDone(); // Return when state is EMPTY
}
public class WaitingRoom {
private Lock l;
private ConditionVariable cond;
private int NCHAIRS;
private int nfull;
private int ticketAvail;
private int ticketTurn;
public WaitingRoom(int NCHAIRS) {
nfull = 0;
ticketAvail = 0;
ticketTurn = -1;
this.NCHAIRS = NCHAIRS;
}
public int custEnter() {
l.acquire();
int ret;
if(nfull == NCHAIRS){
return WR_FULL; //<=================== A
}
else {
ret = MY_TURN;
int myTicket = ticketAvail++;
nfull++;
if(myTicket > ticketTurn){ //<=================== B
cond.wait(&l);
}
nfull--;
}
l.release();
return ret;
}
public int callNextCustomer() {
l.acquire();
ticketTurn++;
if(nfull == 0){
ret = EMPTY;
}
else {
ret = BUSY;
cond.broadcast(&l);
}
l.release();
return ret;
}
}
public class BarberChair {
private Lock l;
private ConditionVariable custUp, barberGetUp, sitDown, seatFree, cutDone;
private int state; //EMPTY, BARBER_IN_CHAIR, LONG_HAIR_CUSTOMER, SHORT_HAIR_CUSTOMER
private int custWalkedIn;
public BarberChair () {
state = EMPTY;
custWalkedIn = 0;
}
public void napInChair()
l.acquire();
if(custWalkedIn == 0){ // Cust could arrive before barber naps
state = BARBER_IN_CHAIR;
}
while(custWalkedIn == 0){
barberGetUp.wait(&l);
}
custWalkedIn = 0;
if(state == BARBER_IN_CHAIR){ /<================= E
state = EMPTY;
seatFree.signal(&l);
}
l.release();
}
public void wakeBarber() {
l.acquire();
custWalkedIn = 1; //<================= C
barberGetUp.signal(&l); //<================= D
l.release()
}
public void sitInChair() {
l.acquire()
while(state != EMPTY){
seatFree.wait(&l);
}
state = LONG_HAIR_CUSTOMER;
sitDown.signal(&l);
while(state != SHORT_HAIR_CUSTOMER){
cutDone.wait(&l);
}
state = EMPTY;
custUp.signal(&l);
l.release();
}
public void cutHair() {
l.acquire();
while(state != LONG_HAIR_CUSTOMER){
sitDown.wait(&l);
}
state = SHORT_HAIR_CUSTOMER;
cutDone.signal(&l);
l.release();
}
public void tellCustomerDone() {
l.acquire();
while(state != EMPTY){
custUp.wait(&l);
}
l.release();
}
}
What is wrong with line B in the above solution to the SleepBarber problem?- AThe line uses if instead of while
- BThere should be no if condition; wait should be called unconditionally.
- CThe line is correct
- DThe if condition is invalid
90
Consider the following solution to the Sleepy Barber problem.
WaitingRoom wr = new WaitingRoom(NCHAIRS);
BarberChair bc = new BarberChair();
//Customer Process:
status = wr.custEnter();
if(status == WR_FULL){
return;
}
bc.wakeBarber();
bc.sitInChair(); // Wait for chair to be EMPTY, Change state to LONG_HAIR_CUSTOMER,
//Wait until state becomes SHORT_HAIR_CUSTOMER, Change state to EMPTY and return
//Barber Process:
while(TRUE){
status = wr.callNextCustomer();
if(status == WR_EMPTY){
bc.napInChair();
}
bc.cutHair(); // Wait until state becomes LONG_HAIR_CUSTOMER, then return with state being SHORT_HAIR_CUSTOMER
bc.tellCustomerDone(); // Return when state is EMPTY
}
public class WaitingRoom {
private Lock l;
private ConditionVariable cond;
private int NCHAIRS;
private int nfull;
private int ticketAvail;
private int ticketTurn;
public WaitingRoom(int NCHAIRS) {
nfull = 0;
ticketAvail = 0;
ticketTurn = -1;
this.NCHAIRS = NCHAIRS;
}
public int custEnter() {
l.acquire();
int ret;
if(nfull == NCHAIRS){
return WR_FULL; //<=================== A
}
else {
ret = MY_TURN;
int myTicket = ticketAvail++;
nfull++;
if(myTicket > ticketTurn){ //<=================== B
cond.wait(&l);
}
nfull--;
}
l.release();
return ret;
}
public int callNextCustomer() {
l.acquire();
ticketTurn++;
if(nfull == 0){
ret = EMPTY;
}
else {
ret = BUSY;
cond.broadcast(&l);
}
l.release();
return ret;
}
}
public class BarberChair {
private Lock l;
private ConditionVariable custUp, barberGetUp, sitDown, seatFree, cutDone;
private int state; //EMPTY, BARBER_IN_CHAIR, LONG_HAIR_CUSTOMER, SHORT_HAIR_CUSTOMER
private int custWalkedIn;
public BarberChair () {
state = EMPTY;
custWalkedIn = 0;
}
public void napInChair()
l.acquire();
if(custWalkedIn == 0){ // Cust could arrive before barber naps
state = BARBER_IN_CHAIR;
}
while(custWalkedIn == 0){
barberGetUp.wait(&l);
}
custWalkedIn = 0;
if(state == BARBER_IN_CHAIR){ /<================= E
state = EMPTY;
seatFree.signal(&l);
}
l.release();
}
public void wakeBarber() {
l.acquire();
custWalkedIn = 1; //<================= C
barberGetUp.signal(&l); //<================= D
l.release()
}
public void sitInChair() {
l.acquire()
while(state != EMPTY){
seatFree.wait(&l);
}
state = LONG_HAIR_CUSTOMER;
sitDown.signal(&l);
while(state != SHORT_HAIR_CUSTOMER){
cutDone.wait(&l);
}
state = EMPTY;
custUp.signal(&l);
l.release();
}
public void cutHair() {
l.acquire();
while(state != LONG_HAIR_CUSTOMER){
sitDown.wait(&l);
}
state = SHORT_HAIR_CUSTOMER;
cutDone.signal(&l);
l.release();
}
public void tellCustomerDone() {
l.acquire();
while(state != EMPTY){
custUp.wait(&l);
}
l.release();
}
}
Assume that Hoare semantics are used to implement the Condition Variables. What would happen if line C and line D were swapped?
Hint: Consider the scenario where the Barber is napping, and a customer arrives.- AStarvation
- BRace condition
- CNo error would be caused by swapping these two lines
- DA deadlock
91
Consider the following solution to the Sleepy Barber problem.
WaitingRoom wr = new WaitingRoom(NCHAIRS);
BarberChair bc = new BarberChair();
//Customer Process:
status = wr.custEnter();
if(status == WR_FULL){
return;
}
bc.wakeBarber();
bc.sitInChair(); // Wait for chair to be EMPTY, Change state to LONG_HAIR_CUSTOMER,
//Wait until state becomes SHORT_HAIR_CUSTOMER, Change state to EMPTY and return
//Barber Process:
while(TRUE){
status = wr.callNextCustomer();
if(status == WR_EMPTY){
bc.napInChair();
}
bc.cutHair(); // Wait until state becomes LONG_HAIR_CUSTOMER, then return with state being SHORT_HAIR_CUSTOMER
bc.tellCustomerDone(); // Return when state is EMPTY
}
public class WaitingRoom {
private Lock l;
private ConditionVariable cond;
private int NCHAIRS;
private int nfull;
private int ticketAvail;
private int ticketTurn;
public WaitingRoom(int NCHAIRS) {
nfull = 0;
ticketAvail = 0;
ticketTurn = -1;
this.NCHAIRS = NCHAIRS;
}
public int custEnter() {
l.acquire();
int ret;
if(nfull == NCHAIRS){
return WR_FULL; //<=================== A
}
else {
ret = MY_TURN;
int myTicket = ticketAvail++;
nfull++;
if(myTicket > ticketTurn){ //<=================== B
cond.wait(&l);
}
nfull--;
}
l.release();
return ret;
}
public int callNextCustomer() {
l.acquire();
ticketTurn++;
if(nfull == 0){
ret = EMPTY;
}
else {
ret = BUSY;
cond.broadcast(&l);
}
l.release();
return ret;
}
}
public class BarberChair {
private Lock l;
private ConditionVariable custUp, barberGetUp, sitDown, seatFree, cutDone;
private int state; //EMPTY, BARBER_IN_CHAIR, LONG_HAIR_CUSTOMER, SHORT_HAIR_CUSTOMER
private int custWalkedIn;
public BarberChair () {
state = EMPTY;
custWalkedIn = 0;
}
public void napInChair()
l.acquire();
if(custWalkedIn == 0){ // Cust could arrive before barber naps
state = BARBER_IN_CHAIR;
}
while(custWalkedIn == 0){
barberGetUp.wait(&l);
}
custWalkedIn = 0;
if(state == BARBER_IN_CHAIR){ //<================= E
state = EMPTY;
seatFree.signal(&l);
}
l.release();
}
public void wakeBarber() {
l.acquire();
custWalkedIn = 1; //<================= C
barberGetUp.signal(&l); //<================= D
l.release()
}
public void sitInChair() {
l.acquire()
while(state != EMPTY){
seatFree.wait(&l);
}
state = LONG_HAIR_CUSTOMER;
sitDown.signal(&l);
while(state != SHORT_HAIR_CUSTOMER){
cutDone.wait(&l);
}
state = EMPTY;
custUp.signal(&l);
l.release();
}
public void cutHair() {
l.acquire();
while(state != LONG_HAIR_CUSTOMER){
sitDown.wait(&l);
}
state = SHORT_HAIR_CUSTOMER;
cutDone.signal(&l);
l.release();
}
public void tellCustomerDone() {
l.acquire();
while(state != EMPTY){
custUp.wait(&l);
}
l.release();
}
}
Assume that the if statement condition at line E was replaced by if(TRUE). The two statements state = EMPTY; seatFree.signal(&l); always execute.
Order the following events to build a deadlock scenario that can happen in that case.
Barber finds out the waiting room is empty [blank_start]____[blank_end]
Before Barber calls napInChair, a customer arrives and proceeds to call sitInChair [blank_start]____[blank_end]
The customer changes state to LONG_HAIR_CUSTOMER and waits for hair cut to be done [blank_start]____[blank_end]
Barber calls napInChair, doesn't sleep, and changes state to EMPTY [blank_start]____[blank_end]
Barber waits for state to be LONG_HAIR_CUSTOMER [blank_start]_____[blank_end]
- AEvent 1
- BEvent 2
- CEvent 3
- DEvent 4
- EEvent 5
- FEvent 1
- GEvent 2
- HEvent 3
- IEvent 4
- JEvent 5
- KEvent 1
- LEvent 2
- MEvent 3
- NEvent 4
- OEvent 5
- PEvent 1
- QEvent 2
- REvent 3
- SEvent 4
- TEvent 5
- UEvent 1
- VEvent 2
- WEvent 3
- XEvent 4
- YEvent 5
92Which of the following is a safer way to call wait on a Condition Variable named cv while holding a lock named lock?
- Aif(some condition) cv.wait(&lock)
- Bwhile(some condition) cv.wait(&lock)
93Which of the following can NOT happen in the semaphore-based solution of the Readers Writers Problem?
- AThe value of the writing semaphore is 0 and the mutex is locked
- BThe value of the writing semaphore is 0 and the mutex is unlocked
- CThe value of the writing semaphore is 0 and nReaders == 1
- DThe value of the writing semaphore is 0 and nReaders > 1
- EAll the above scenarios can happen
94Which of the following can NOT happen in the semaphore-based solution of the Bounded Buffer Problem?
- Aempty 0 and full 0
- Bempty > 0 and full > 0
- Cempty <= 0 and full == n
- Dempty == n and full > 0
95We can use a Mutex for the writing semaphore.
- ATrue
- BFalse
96In a _________________ the kernel saves the state of the currently running process and restores the state of the next process to run.
- Asave-and-restore
- Bcontext switch
- Cstate switch
- Dnone of the above
97It is possible that the CPU executes an instruction from a process in non-privileged mode followed immediately by an instruction from another process in non-privileged mode.
- ATrue
- BFalse
98a critical section (region) is
- Aa section/region of data that cannot be shared by processes
- Ba section/region of code that cannot be shared by processes
- Ca region/section of data that only one process can access at a time
- Da section/region of code that only one process can run at a time (code itself may or may not be shared but usually accesses shared data)
99in busy waiting, what happens when process A tries to access a critical section while process B is already in the critical section?
- Aprocess A blocks
- Bprocess B goes to the ready queue and process A runs the critical section
- Cprocess A continues running
100a process calls a down/wait/P on a semaphore S to enter a critical section. what happens to the process?
- Ait may block
- Bit may continue execution
- Cit may become ready for execution (goes to the ready queue)
- Dit requires the OS to take over and carry out the system call
- Eany of the above
101When a child process is created, which of the following is a possibility in terms of the execution or address space of the child process?
- AThe child process runs concurrently with the parent.
- BThe child process has a new program loaded into it.
- CThe child is a duplicate of the parent.
- DAll of the above
102Assuming all variables are initialized to zero.
How many times does "Start" get printed by the following program? [blank_start]_____[blank_end]
- A1
103Assuming all variables are initialized to zero.
How many times does "End" get printed by the following program? [blank_start]____[blank_end]- A18
104Can we use a Mutex for the writing semaphore?
- AYes
- BNo
105In preemptive scheduling, the critical sections of code affected by interrupts must be guarded (e.g., by locks) from simultaneous use.
- ATrue
- BFalse
106Process synchronization and deadlocks have a deep relationship. Choose all correct statements.
- ADeadlocks are sometimes caused by misuse of semaphores
- BA process holding a mutex can be a part of a deadlock
- CA process in a barrier synchronization can be part of a deadlock.
107Can a process that voluntarily suspends itself (e.g., sleeps or requests I/O) be part of a deadlock?
- ATrue
- BFalse
Information
- Description
- Computer Science Quiz on CS1550 Midterm Prep, created by Court Kowaluk on 20/02/2024.
- Author
- Court Kowaluk
- Language
- English
- Views
- 16
- Tags
- Rating
- No ratings yet Rate this quiz