CIT595 Flashcards

1
Q

Which of the following are pushed onto the stack during a function call to remember the execution context of a process?
Program counter
Compute registers
File descriptor table

A

Program Counter
Compute registers
Because we are jumping to run another function, we need to remember the execution context of where we left off previously in the main function. The program counter and compute registers are necessary for this, the file descriptor table can be accessed throughout the program.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Is the following statement true or false? Select the best response. A process can jump to any location in the kernel via a system call.
True
False

A

False
For security reasons, it is not advisable for user processes to call into any arbitrary functions in the kernel. Otherwise, one process may arbitrarily jump to the kernel and read data that it is not authorized to read or call functions that results in security attacks that require root access. Instead, all system calls go through a limited number of entry points to kernel code, which are available as a limited number of system call functions to the user.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Is the following statement true or false? Select the best response.
In a function call, there is no need to transition to kernel mode.
True
False

A

True
Function code is part of the user’s application, and is thus accessible within user mode.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Which of the following statements about system calls are true? Select all that apply.
System calls are more expensive in terms of CPU resources compared to function calls.
System calls require context switching but function calls do not.
After a system call, the original system caller may not get to run immediately.

A

System calls require context switches, because they involve privileged instructions. Functions written by users do not require context switching. Context switching is expensive because the CPU must save the old process state and load in a new process. Because a new process gets a chance to run, the original system caller may need to wait to continue executing after the call is complete.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Which of these examples can cause a hardware interrupt? Select all that apply.
Clock tick or pulse
Completion of disk operation
Network message has arrived
Illegal memory access by user level process

A

All of these external events generate hardware interrupts that cause the operating system to react.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Is the following statement true or false? Select the best answer. Custom handlers are code in user space written to process signals sent to a process.
True
False

A

True
Every signal results in a default processing behavior, unless the user registers a custom handler in their code in user space

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Every signal results in a default processing behavior, unless the user registers a custom handler in their code in user space
True
False

A

True
The operating system has a software component for doing signal relaying, because the operating system does not want to allow a process to send arbitrary signals to another process. The operating system essentially serves as a gatekeeper for all signals.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Which of the following correctly contrasts interrupt handlers and system calls? Select all that apply.
System calls have return values while interrupt handlers do not.
Context switch happens for system calls but not interrupt handlers.
Both interrupt handlers and system calls require context switching.

A

System calls have return values while interrupt handlers do not.
Interrupt handlers have parameters used by the OS, but no return values that are relevant to the user. Both system calls and interrupts are handled in kernel mode.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Which of the following signals cannot be caught or ignored by a process? Select all that apply.
SIGKILL
SIGINT
SIGSTOP

A

SIGKILL and SIGSTOP cannot be caught or ignored

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Is the following statement true or false? Select the best answer.
Signals that are blocked by the operating system are lost forever.
True
False

A

False
If a signal reaches this filter and it’s slated to be blocked, then the signal will be buffered within the operating system. When there is an explicit command to unblock the signal, it will be relayed to the process.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Interrupts are only initiated by currently running processes.
True
False

A

False
Interrupts can be initiated by hardware, e.g. clock ticks, completion of I/O requests.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

During a system call, a TRAP instruction occurs and executing the correct system call requires a jump to a specific address in OS address space, as indexed by the system call number.
True
False

A

True
Since a system call requires user mode to kernel mode transition, a TRAP has to occur. To avoid the TRAP jumping into any arbitrary location in the OS, it has to go through a dispatcher that figures out the right function call based on the system call number.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

When executing a TRAP instruction during a system call, the CPU mode bit changes from supervisor to user.
True
False

A

False
It goes from user to supervisor mode.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

A regular function call requires fewer CPU cycles than a system call (assuming both have the same code).
True
False

A

True
A system call requires trapping to kernel, context switching and updating some data structures in the kernel. Hence it requires additional CPU cycles.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Consider the following piece of code where a parent creates a child, a child creates a grandchild, and a grandchild creates a great-grandchild process Assume that parent, child (child_pid), grandchild (grandchild_pid), and great-grandchild (greatgrandchild_pid) have PIDs 100, 200, 300, and 400, respectively.

child_pid = fork()
if(child_pid != 0){
/execute parent code/
} else{
/execute child code/
grandchild_pid = fork();
if(child_pid != 0){
/execute parent code/
} else{
great_ grandchild_pid = fork();
}
Enter the value of the child_pid variable in the parent’s address space.

A

200
child_pid is equal to the return value of the parent’s fork() call which is 200.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Consider the following piece of code where a parent creates a child, a child creates a grandchild, and a grandchild creates a great-grandchild process Assume that parent, child (child_pid), grandchild (grandchild_pid), and great-grandchild (greatgrandchild_pid) have PIDs 100, 200, 300, and 400, respectively.

child_pid = fork()
if(child_pid != 0){
/execute parent code/
} else{
/execute child code/
grandchild_pid = fork();
if(child_pid != 0){
/execute parent code/
} else{
great_ grandchild_pid = fork();
}
Enter the value of the greatgrandchild_pid variable in the grandchild’s address space.

A

400
greatgrandchild_pid is equal to the return value of the grandparent’s fork() call which is 400.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Consider the following piece of code where a parent creates a child, a child creates a grandchild, and a grandchild creates a great-grandchild process Assume that parent, child (child_pid), grandchild (grandchild_pid), and great-grandchild (greatgrandchild_pid) have PIDs 100, 200, 300, and 400, respectively.

child_pid = fork()
if(child_pid != 0){
/execute parent code/
} else{
/execute child code/
grandchild_pid = fork();
if(child_pid != 0){
/execute parent code/
} else{
great_ grandchild_pid = fork();
}
Enter the value of the greatgrandchild_pid variable in the greatgrandchild’s address space.

A

0
When the grandchild calls fork(), a new process (greatgrandchild) is created. The return value in the greatgrandchild is 0.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Consider the following piece of code where a parent creates a child, a child creates a grandchild, and a grandchild creates a great-grandchild process Assume that parent, child (child_pid), grandchild (grandchild_pid), and great-grandchild (greatgrandchild_pid) have PIDs 100, 200, 300, and 400, respectively.

child_pid = fork()
if(child_pid != 0){
/execute parent code/
} else{
/execute child code/
grandchild_pid = fork();
if(child_pid != 0){
/execute parent code/
} else{
great_ grandchild_pid = fork();
}
Enter the value of the grandchild_pid variable in the grandchild’s address space. (Numeric answer question)

A

0
This has similar reasoning as in question 8. When a fork() call creates a new process, that within the new process, the return value of fork() is 0.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Which of the following is not an example signal that originates from a hardware interrupt?
Input from keyboard, network, or disk
SIGINT signal from one process to another
Clock pulse for updating system time
Illegal memory access

A

SIGINT signal from one process to another

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Is the following statement true or false? Select the best answer.
STDIN and STDOUT are file descriptors made available to a process
True
False

A

STDIN and STDOUT are reserved as file descriptors which by default read from keyboard and output to the terminal. However, they can be overwritten.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Consider a command out > pwd where out is a valid text file, and pwd prints the current path. When you type it in a shell, what is the expected output? Select the best answer.
Prints the contents of out
Invalid command
The shell ignores out and just prints the current path

A

out > pwd is an invalid command since it starts with ‘out’ which the shell cannot interpret as an executable command.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Consider a command pwd < out, where out is a valid text file, and pwd prints the current path. When you type it in a shell, what is the expected output? Select the best answer.
Prints the contents of out
Invalid command
The shell ignores out and just prints the current path

A

The shell ignores out and just prints the current path
Since pwd is not expecting a STDIN, the ‘< out’ is ignored by shell.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Suppose you have a command that takes in an argument (e.g.sleep()) and you run “sleep 10 < file.txt”. When you type it in a shell, what is the expected output if the contents of file.txt is “100” and nothing else?
Sleeps for 10 seconds
Invalid command
Sleeps for 100 seconds

A

Sleeps for 10 seconds
The system call for sleep is not expecting another input argument, so the redirection is irrelevant and gets ignored.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is the behavior of ls | more > out? Select the best answer.
ls runs to list all the directories. If more than fit into a page, the user has to press space to continue until all the files are listed. The output is stored in the file out.
ls runs to list all directories. Even if more than a page is needed, the user does not press any keys, and all the listed files are stored in the file out.
Throw an error

A

ls runs to list all directories. Even if more than a page is needed, the user does not press any keys, and all the listed files are stored in the file out.
This is somewhat surprising. Since the output of ls goes to a file, there is no real definition of a screenful of display, hence no user keys are needed.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What is the output of ls | pwd? Select the best answer.
We list all files in the current directory, and pwd is ignored.
Throws an error
The current path is printed out

A

The current path is printed out
The two commands run concurrently, but since the output of ls is used as input to pwd, it is not displayed. However, since pwd does not read from standard in, the output of ls is ignored and only the pwd command is executed.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Is the following statement true or false? Select the best answer.
A ctrl-C signal will be sent to an entire process group.
true
false

A

true
By definition, the option of grouping processes together allow us to send a signal to all.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Is the following statement true or false? Select the best answer.
A pipelines of processes A | B | C are in the same process group.
true
false

A

true
Whenever a pipeline of processes is implemented, the OS will always group the processes together so that they can receive common signals at the same time.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Which of the following commands are illegal or will cause the process to be stopped?
Select the best answer.
Is > out
Is > out &
cat &
Is | pwd &

A

‘cat &’ is illegal since a process cannot take in standard input in the background. Interesting, most OS will allow ‘Is > out &’ to happen. It just becomes distracting to have background processes generating output in the background.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Is the following statement true or false? Select the best answer.
When a process is stopped, a SIGCHLD signal is sent to the parent.
true
false

A

true
Whenever a process is stopped or exited, a SIGCHLD signal is sent to the parent.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Which of the following is a difference between processes and threads? Select all that apply.
Process creation is cheaper and faster than threads.
There can be many threads within a process.
Threads in the same process can communicate directly with each other by writing to the same memory location but processes communication involves the kernel.
Processes has better isolation than threads and one process is less likely to corrupt another process compared to two threads.

A

There can be many threads within a process.
Threads in the same process can communicate directly with each other by writing to the same memory location but processes communication involves the kernel.
Processes has better isolation than threads and one process is less likely to corrupt another process compared to two threads.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Is the following statement true or false? Select the best answer.
In a web server, creating a thread for each new request from a client and then destroying the thread after the request has been serviced requires less overhead than maintaining a thread pool.

A

False
Creating threads can be expensive so creating a new thread for each request will add a lot of overhead to the web server. It is more efficient to maintain a thread pool and to use a thread from the pool to service each request, returning the thread to the pool after the request has been serviced.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

Which of the following are good uses of threads? Select all that apply.
A. Two different applications belonging to two different users, each running in a separate thread.
B. Web browser has several threads, each supporting a different task (e.g. image rendering, receiving requests from users, sending back HTML responses, etc.}.
C. An application that breaks up large amounts of data into small chunks for processing in parallel.

A

B. Web browser has several threads, each supporting a different task (e.g. image rendering, receiving requests from users, sending back HTML responses, etc.}.
C. An application that breaks up large amounts of data into small chunks for processing in parallel.

A is not a good way to use threads since processes provide better isolation. It is more desirable to have each user application run in its own separate process. B and C are good uses of threads as they both require running multiple tasks in parallel but yet isolation is not essential in either.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Is the following statement true or false? Select the best answer.
Context switching between user level threads is very fast, requiring only a few instructions in user space.

A

True
Context switching between user level threads is indeed very fast, requiring only a few instructions in user space. This is one of the advantages of user level threads.

34
Q

Which of the following correctly reflects the differences between kernel and user level threads? Select the best answer.
Kernel level threads are all maintained by the kernel, while user level threads are maintained in user space.
Kernel level threads that make system calls will block other kernel level threads in the same process.
The scheduling of both kernel level threads and user level threads can be customized by the user application.
Kernel level thread creation is faster and cheaper than user level thread creation.

A

Kernel level threads are all maintained by the kernel, while user level threads are maintained in user space.

35
Q

Is the following statement true or false? Select the best answer.
If multiple processes or threads are reading from an array, but they are all manipulating different entries in the array, a race condition is possible.
True
False

A

False
A race condition requires concurrent updates to the same state. Since different entries of an array live in different memory addresses, updating different entries of an array at the same time does not result in a race condition.

36
Q

Are the following statements true or false? Select all the true statement(s)
Mutual Exclusion is to prevent simultaneous accesses to a critical section.
Disabling interrupts achieves mutual exclusion by preventing CPU from context switching.
Disabling interrupts prevents clock interrupts.
Only the process trying to get into the critical session will be stopped by disable interrupts.

A

Mutual Exclusion is to prevent simultaneous accesses to a critical section.
Disabling interrupts achieves mutual exclusion by preventing CPU from context switching.
Disabling interrupts prevents clock interrupts.

Disabling interrupts avoids race conditions by disabling context switching when a process is in a critical section. The clock interrupt is turned off, which means the scheduler will not be invoked. Therefore, no context switch for all process, whether it entering critical section or not.

37
Q

(1) int condition = false;
(2) while (!condition) {
(3) disable_interrupt();
(4) CS();
(5) condition = true;
(6) enable_interrupt();
(7) }

The code above implements a disable interrupt. Would the solution guarantee mutual exclusion if lines (4) and (5) were swapped? Select the best answer. True or False

A

True
The mutual exclusion would still hold if lines (4) and (5) are swapped since the disable_interrupt function prevents context switching. In other words, it ensures the critical section will be executed by only one process at a time. The condition variable serves to make sure this critical section is executed only one time within this process, and this reordering does not affect mutual exclusion.

38
Q

Is the following statement true or false? Select the best answer.
An example of busy waiting is when a process, P0, repeatedly checks the value of a turn variable in a while loop, only breaking out of the while loop when the turn value becomes 0, indicating that it is P0’s turn to execute its critical section.

A

True
This is a very common description of busy waiting that is used throughout synchronization and mutual exclusion solutions.

39
Q

Is the following statement true or false? Select the best answer.
Busy waiting is not ideal because a process that is busy waiting continuously consumes the CPU’s resources.

A

True
A process that is busy waiting must continuously check the value of some condition or variable in a while loop; this requires CPU cycles and consumes the CPU’s resources.

40
Q

Is the following statement true or false? Select the best answer.
One drawback of Peterson’s solution is that it is difficult to generalize beyond two threads or processes. However, one benefit of Peterson’s solution is that it does not require busy waiting.

A

False
Unfortunately, both are drawbacks to the solution. Peterson’s solution both is difficult to generalize beyond two threads or processes and requires busy waiting.

41
Q

When a process makes a system call, after the call completes, it may not get to run immediately.

A

True
The scheduler may pick another process to run instead of the process that made the call.

42
Q

During a system call, the system call number corresponding to the system call function is pushed onto the stack initially.

A

True
The stack is a convenient place for storing the system call number. This number will be popped off the stack when the kernel takes control, to figure out which system call to invoke.

43
Q

During a system call, the system call function caller’s current register values are first stored in the heap and then copied to the PCB.

A

False
The current register values are stored in the stack, not heap.

44
Q

Is the following statement true or false?

System calls are more expensive (i.e. require more instructions to run) than regular function calls.

A

True
System calls are more expensive because a context switch is required.

45
Q

A SIGKILL signal can be caught or ignored.

A

False
SIGKILL is a special signal that unconditionally kills a process, and is the last resort the OS uses to kill a process. Hence, the OS does not allow this signal to be caught or ignored by a process.

46
Q

One can overwrite a SIGINT default handler with a custom handler.

A

True
Unlike a SIGKILL, a SIGINT signal is a gentler way to terminate a process. The process is allowed to change its handling behavior.

47
Q

Is the following statement true or false?

Blocked signals are lost because the kernel drops these signals.

A

False
When signals of a given type are blocked, the kernel will buffer them for delivery when the signals are unblocked.

48
Q

Is the following statement true or false?

The more advanced sigaction() function provides the means to query for the most recent action associated with the signal, prior to any new actions being taken.

A

True
Based on the function signature of sigaction, the last parameter returns a reference to the current action associated with the signal prior to invoking its function.

49
Q

Consider a scenario where we have the following function that returns the round trip time to a server.

ping google.com

Suppose we run the above program in the background, which of the following methods allows us to terminate the ping process right after starting this process? Select all that apply.

Send a SIGKILL to the ping process based on its process ID
Press ctrl-C
kill %1

A

Send a SIGKILL to the ping

Pressing ctrl-C will not work since the process is running in the background.

50
Q

Consider the pipelined process

sleep 10 | sleep 15

What is the number of seconds for which the above process group will block? Enter your answer as a number in the space provided below. Do not enter any spaces or punctuation.

A

15
Since the two processes are running concurrently, it will block for the longer of two processes.

51
Q

Which of the following statements about the TSL instruction is correct? Select the best answer.
A. It is a hardware component in CPU for concurrency control.
B. It gets the content of a memory at the first CPU cycle and then immediately set the memory value to 1 at the beginning of the following cycle.
C. It needs only one hardware instruction to achieve both getting and setting a memory value.

A

TSL instruction is a special hardware instruction, instead of a hardware component, so A is incorrect. TSL instruction can guarantee both getting and setting a memory value within one CPU cycle, so B is incorrect. TSL instruction can use one hardware instruction to achieve both getting and setting a memory value with the help of hardware, so C is correct.

52
Q

What could happen if the two instructions, reading shared variable and setting the lock, in TSL are not atomic when controlling the concurrency of process T1 and T2? Suppose the shared variable lock is initialized to be 0. Select the best answer.
Both T1 and T2 could read the shared variable before it is updated.
check
There will be no race condition in the critical session since the two processes will block each other from the beginning.
One of the processes will have starvation if it always reads the shared variable in between of the two instructions of the other process.

A

T1 and T2 read the shared variable before updating it, so A is correct. Then both of them will get into the critical section concurrently. It causes a race condition on the resource in the critical section, so B is incorrect. There is no starvation since all the processes are able to get into the critical section, so C is incorrect.

53
Q

Which of the following statements is false? Select the best answer.
A. The producer will fall asleep if the counter is N after it produces an item.
B. The producer will wake up the consumer if the counter is larger than zero after increased by the producer.
C. The consumer will fall asleep if the counter is zero before it producer any item.
D. The consumer will wake up the producer if the counter is N - 1 after decreased by the consumer

A

B is the false statement. The producer will wake up the consumer if the counter is one after increased by the producer.

54
Q

Suppose the buffer is now full of N items. Below are four steps (not in a particular order) on the producer side. Re-order the steps to trigger the lost wakeup problem on the producer.

Enter the correct sequence, in numbers, in which the steps occur. Do NOT use any letters, spaces, or punctuation. For example, you may enter the sequence 1234.

  1. The producer checks whether there are N items in the buffer and the answer is yes.
  2. The producer goes to sleep.
  3. The consumer removes an item from the buffer and decreases the counter from N to N - 1.
  4. The consumer wakes the producer up since there are N - 1 items in the buffer.
A

1342
The main cause of the lost wakeup problem is that a process wakes up another process before it actually falls into sleep.

55
Q

Which of the following details about the semaphore values used in the implementation you just learned is correct? Select all that apply.
The semaphore value can be interpreted as the number of available resources.
The initial value of the semaphore value should be 1.
If the semaphore value is negative, the absolute value of it can be interpreted as the number of blocked processes/threads.

A

The semaphore value can be interpreted as the number of available resources.
If the semaphore value is negative, the absolute value of it can be interpreted as the number of blocked processes/threads.

sem_wait is called before a process accesses the critical session and it subtracts the semaphore value by 1. sem_post is called after a process leaves the critical session and increase the semaphore value by 1. Also, sem_wait blocks the process unless the semaphore value is positive. So we can see the semaphore value as the number of the available resource. Therefore, the option, The semaphore value can be interpreted as the number of available resources, is correct.

The initial value of the semaphore should be the maximum number of processes you would allow to have concurrency. So, the initial value of the semaphore value does not have to be 1.

A process is blocked only when the semaphore value is negative after decreased by 1 in sem_wait. So, the absolute of the negative semaphore value represents the blocked processes.

56
Q

Given the multi-thread version of “Hello World” that you have learned, which of the following details about the semaphore value in this implementation are correct? Select all that apply.
The minimum of the semaphore value is -2.
The maximum of the semaphore value is 2.
The first sem_wait is used for preventing the main thread creating thread 2.
The second sem_wait is used for preventing the main thread exiting.

A

If we use the semaphore implementation provided in lecture, the minimum value of the semaphore is -1 and the maximum value is 1.

The first sem_wait is used for preventing the main thread creating thread 2.
The second sem_wait is used for preventing the main thread exiting.

57
Q

Given two processes, A and B, and two resources R1 and R2, there will be a deadlock if A holds R1 and needs R2 to progress, and B holds R2 and needs R1 to progress.

A

True
A deadlock is a situation where there is a set of blocked processes waiting for resources such that there is no way to satisfy any of their requests.

58
Q

Which other strategies would work to break the circular wait in the Dining Philosophers problem?
Assign each chopstick a distinct number [0 to N] in counterclockwise order. Each philosopher “i” first grabs the right chopstick and then the left chopstick.
Each philosopher “i” grabs chopstick “i” and then chopstick “i+1 mod N”
Assign each chopstick the numbers 1 and 2 in alternate order. Each philosopher “i” grabs the adjacent chopstick of lower number and then the resource of a higher number.

A

Assign each chopstick the numbers 1 and 2 in alternate order. Each philosopher “i” grabs the adjacent chopstick of lower number and then the resource of a higher number.
The correct approach causes a philosopher to request chopsticks in the opposite order of the others. In the incorrect solutions, each philosopher “i” would grab the same side chopstick first and then wait indefinitely for the other side chopstick, which is being held by philosopher “i+1”.

59
Q

Recall that if a program is sound, it means that the program is guaranteed to produce correct results at all stages without race conditions and synchronization issues. Which of the following statements is correct?
A sound program is always deadlock-free because it avoids all the race conditions.
A sound program is not necessarily to be deadlock-free because the processes can still wait for each other to release some resource.

A

Consider the following counterexample - sound but not deadlock free. Each philosopher “i” in the Dining Philosophers’ problem still chopstick “i” and then instead of immediately attempting to grab “i+1 mod N”, the philosopher executes the following code:

// For philosopher i
(1) GRAB(i)
(2) CHECK if (i+1) mod N is available
____(a) If Yes: GRAB ((i+1) mod N)
____(b) If No: RELEASE (i)

A deadlock, or rather “anti-deadlock” is possible because there is a state where no philosopher eats. Starvation is possible because some philosopher “i” may never pass the check.

60
Q

Is the following statement true or false?
Deadlock is possible if the mutual exclusion, hold & wait, and circular wait conditions exist, but there is resource preemption.
True
False

A

False
If any condition for deadlock is removed, then deadlock cannot happen.

61
Q

Is the following statement true or false?
Deadlock is possible if we run processes one by one, and complete each process before beginning the subsequent process.
True
False

A

False

his means that there is never a cyclical wait so a precondition of deadlock is broken.

62
Q

Given any resource allocation graph, if there is a cycle, there is a deadlock in the program it represents.
Is the reverse (that if there is a deadlock in the program, there must be a cycle in its resource allocation graph) also true?

A

Yes, it is an if-and-only-if relationship.

63
Q

Which of the following are components of the resource allocation graph but not the wait-for graph?
Nodes representing resources
Edges representing resources
Directed edges from a process P to a resource R if P is waiting for R
Directed edges from a resource R to a process P if R is allocated to P

A

The wait-for graph only removes the nodes representing resources and only focuses on the waiting relationships between processes.

64
Q

Which of the following is the more conservative resource allocation approach?
Picking one process at a time and always making sure there are sufficient resources for the process to finish before running the process.
Starting as many as processes to run in parallel to use most of the available resources.

A

Being conservative in resource allocating approach means sacrificing the concurrence for deadlocks avoidance.

65
Q

Which of the following statements about allocation safe states is correct?
An allocation state is safe if there is a sequential ordering of processes such that all the processes will be able to finish executing without entering a deadlock state.
If an allocation state is a safe state, we can only use sequential execution to finish all the processes.
An allocation state is safe means it can never meet deadlock no matter how to allocate the resources.

A

The first option is the definition of a safe state. However, an allocation state is safe does not mean it has to be sequentially executed to avoiding deadlock. It also does not mean that you can assign execution in any order.

66
Q

Consider a system that comprises of a total of 3 processes (A, B, and C) and 16 resources. Now the system has allocated 10 resources and there are 6 unallocated resources to be used. The table below lists the system’s current allocation and the maximum needs for each process:

Process Holding Max Claims
A 2 15
B 3 10
C 5 11

What is the sequence of processes that will make the current state safe? Enter the sequence of processes as a sequence of uppercase letters in the space provided below. Do not enter any spaces, punctuation, or symbols. For example, if you think the correct sequence of processes is B, followed by A, followed by C, then enter BAC as your answer.

A

An allocation state is safe if there is a sequential ordering of processes such that all the processes will be able to finish executing without entering a deadlock state.

In the current state, process A need 13 more resource, B 7 resource, and C 6 resource.

There are 6 unallocated resources, therefore, we should execute process C first.

After C finishes, there are 11 unallocated resources. So we should execute process B.

After B finished, there are 14 unallocated resources.

Finally, the process A is ready to be executed. In conclusion, the sequential ordering is C->B->A.

67
Q

Which of the following statement(s) about the second solution for the dining philosopher’s problem is (are) not true? Select the best answer.
This solution breaks the symmetry of the problem.
close
This solution can make sure half of the philosophers get to eat at any time.
This solution not only avoids deadlock but also has no race conditions.

A

This solution not only avoids deadlock but also has no race conditions.
There are race conditions between any pair of odd and even number philosophers when they are picking up their first chopsticks.

68
Q

Recall that there are three semaphores used in the Bounded-buffer problem. Which of the following statements about the three semaphores are correct? Select all that apply.
A. Semaphore “mutex” is used to make sure only one process can update the buffer.
B. Semaphore “full” is initialized to 0 and represent the available resource in the buffer.
C. Semaphore “empty” is initialized to N and represent the available empty space in the buffer.

A

Semaphore “mutex” is placed before and after updating the buffer in both producer and consumer, so A is correct.
Semaphore “full” will increase after the producer update the buffer and will block the consumer when there is no resource in the buffer, so B is correct.
Semaphore “empty” will increase after the consumer updates the buffer and will block the producer when there is no resource in the buffer, so C is correct.

69
Q

In the reader-writer problem, write semaphore is used in both the writer process and the reader process. Please select options to fill in the two blanks to complete the statement about the usage of write in different processes.

Which of the following phrases correctly completes the sentence about write semaphores below?

The write semaphore is used in writer processes to…

avoid any writers updating the data during the reading.

avoid writers getting into the critical section concurrently.

A

avoid writers getting into the critical section concurrently

The write is used at the beginning of the writer process to make sure no one is using the file before updating it. In the reader process, the write is used by the first reader to make sure the file is updated and no writer can change it during the reading.

70
Q

In the reader-writer problem, write semaphore is used in both the writer process and the reader process.

Which of the following correctly completes the sentence about write semaphores below?

The write semaphore is used in reader processes to…

avoid any writers updating the data during the reading.

avoid writers getting into the critical section concurrently.

A

The write is used at the beginning of the writer process to make sure no one is using the file before updating it. In the reader process, the write is used by the first reader to make sure the file is updated and no writer can change it during the reading.

71
Q

Which of the following statements about the monitor is true? Select the best answer.
A. The monitor is a convenient abstraction that allows us to support synchronization.
B. There can be more than one thread in a monitor at any time.

A

The monitor is a convenient abstraction that allows us to support synchronization either at a process or a thread level without having to deal with low-level semaphores. So A is correct. The basic idea of a monitor is that at any point in time, only one process or thread can enter the monitor and the rest have to be queued up. So B is incorrect.

72
Q

Which of the following statements about the monitor with condition variables is true? Select the best answer.
A condition variable has both wait and signal functions.
The blocked threads in a monitor can be signaled by any condition variables.

A

A condition variable has both wait and signal functions. A condition variable’s signal function can wake up one of the threads blocked on it.

73
Q

Let’s have an example about how processes claim resources. Intuitively and not necessarily, resources can be equivalent to memory resources. Consider an application that uses memory as follows.:

  1. 10 MB of memory in first 5 minutes
  2. 30 MB of memory in next 5 minutes (that includes the original 10MB)
  3. 5 MB of memory in final 5 minutes (where 25MB has been released)

Which of the following will be the amount of resource (memory) that the application declares in the Banker’s Algorithm?
30 MB, because this is the maximum number of resources the application needs at once.
45 MB, because this is the number of resources the application needs in total.
10 MB, because this is the number of resources the application needs to execute the first step.

A

30 MB, because this is the maximum number of resources the application needs at once.

74
Q

Is the following statement true or false? Select the best answer.

Conditional variables and semaphores are functionally equivalent.

A

False. They are not functionally equivalent, e.g. semaphores maintain counters, while conditional variables are mostly used with monitors.

75
Q

Is the following statement true or false? Select the best answer.

A binary semaphore can only have a value of either 0 or 1.

A

True. A binary semaphore saturates at a value of 1 and is used as a mutex.

76
Q

Is the following statement true or false? Select the best answer.

TSL (Test-and-Set) is a software-based solution for mutual exclusion.

A

False. TSL is a hardware solution.

77
Q

Is the following statement true or false? Select the best answer.

The Test-and-Set (TSL) is superior to the Peterson’s solution because it does not result in busy waiting.

A

False. TSL also suffers from the busy wait problem.

78
Q

Is the following statement true or false? Select the best answer.

Two threads within the same process can write to the same memory.

A

True. Two threads in the same process share the same virtual memory and hence can write to the same memory.

79
Q

Is the following statement true or false? Select the best answer.

“Starvation freedom” means that if a thread/process wants to enter a critical section, it will eventually be granted permission to enter.

A

True. A thread/process is not “starved” if after asking to enter a critical section, it enters eventually. In contrast, a starved process/thread will not get a chance to enter (forever, or at least it has to wait a long time)

80
Q

Is the following statement true or false? Select the best answer.

In the context of semaphore implementations, “P” and “V” calls have to be atomic actions.

A

True. The P and V calls have to be atomic, if not, the increase and decrease of the counter value will cause problems.

81
Q

Is the following statement true or false? Select the best answer.

The Peterson’s solution does not require simple assignments and tests since the shared variables do not have to be atomic.

A

False. The whole basis of the Peterson’s solution is its reliance on certain atomic statements (simple assignments and tests). This means no context can happen for these statements.