Operating Systems Final Exam

COP 4610 - Operating Systems Concepts

What statements are true about the functions wait() and signal() for condition variables?

1. By calling wait () we decrease the semaphore by one, and signal increases the semaphore by 1

2. The thread calling wait() goes to the ready state, while the thread calling signal() sends a signal to wake up anyone sleeping in the queue of the condition variable

3. The thread calling wait() goes to the waiting state, while the thread calling signal() sends a signal to wake up any thread sleeping in the queue of the condition variable

4. The thread calling wait() needs to held the lock, while the thread calling signal() automatically acquires the lock

5. When a thread wake up (from a wait()) and start running automatically re-take the lock, and a thread before calling signal () needs to already have the lock

3 & 5

Which of the following is a necessary condition to call the function wait() in the context of condition variables?

1. The semaphore has to be initialized to one

2. Assumes the lock is held when wait() is called by a thread

3. The thread has to be in the scope of parent

4. The thread has to be registered by the thread condition variable

2

Assume multiple CPUs. The following piece of code corresponds to a lock based on disable and enable interruptions. Disable interruptions guarantees that at least 1 thread will be in the critical section. Is this lock able to guarantee mutual exclusion?

No, but if there is one CPU then yes.

Parent and children threads share the stack. True or False?

False

Assume 1 CPU and a set 10 threads running following a round-robin scheduling policy. The time slice is 5 ms, and the amount of time needed to update a shared variable in the critical section is 6 ms. Let’s assume that thread one was able to get into the critical section. Also assume that thread one gives up the CPU as soon as leaves the critical section.

How long does it take for thread 2 to get into the critical section? (counting from the very beginning)

1. Thread 1 starts and runs for the first 5 ms → does not finish (needs 1 more ms)

2. Thread 1 rescheduled after other 9 threads → 9 × 5 = 45 ms later

3. Thread 1 runs for 1 ms to finish in critical section → 5 + 45 + 1 = 51 ms

4. Thread 2 enters critical section at 51 ms

Assume 1 CPU and a set 10 threads running following a round-robin scheduling policy. The time slice is 5 ms, and the amount of time needed to update a shared variable in the critical section is 6 ms. Let’s assume that thread one was able to get into the critical section. Also assume that thread one gives up the CPU as soon as leaves the critical section.

Also, assume that the program uses the function YIELD() (instead of the traditional while-loop for spinning - send it to the ready state) which takes 1 ms in give up the CPU if found that the lock is close.

How long does it take for thread 2 to get into the critical section? (counting from the very beginning)

1. Thread 1 starts and runs for the first 5 ms → does not finish (needs 1 more ms)

2. Threads 2-10 run for 1 ms to execute YIELD → 9 × 1 = 9 ms

3. Thread 1 runs for 1 ms to finish in critical section → 5 + 9 + 1 = 15 ms

4. Thread 2 enters critical section at 15 ms

Assume 1 CPU and a set 10 threads running following a round-robin scheduling policy. The time slice is 5 ms, and the amount of time needed to update a shared variable in the critical section is 4 ms. Let’s assume that thread one was able to get into the critical section. Also assume that thread one gives up the CPU as soon as leaves the critical section.

How long does it take for thread 2 to get into the critical section? (counting from the very beginning)

1. Thread 1 starts and runs for 4 ms. It gives up CPU.

2. Thread 2 starts and runs for 4 ms in the critical section.

Assume 10 CPUs and a set 10 threads running following a round-robin scheduling approach. The time slice is 5 ms, and the amount of time needed to update a shared variable in the critical section is 6 ms. Let’s assume that thread one was able to get into the critical section. Also, assume that thread one gives up the CPU as soon as leaves the critical section.

How long is going to take for the next thread (no necessary thread 2) to get into the critical section? (counting from the very beginning)

1. Thread 1 starts and runs for the first 5 ms → does not finish (needs 1 more ms)

2. 10 threads are running simultaneously on 10 CPUs.

3. Thread 1 rescheduled and runs for 1 ms (5 + 1 = 6 ms)

Assume 1 CPU. Assume this attempted implementation of a lock. Assume 5 threads are competing for this lock. How many threads can possibly acquire the lock, and get into the critical section at the same time?

1. We can possibly have 1, 2, 3, 4 or 5 at the same time in the critical section.

2. It is not possible to have more than one thread at the time in the critical section.

3. None of the above.

1

Assume 1 CPU. Assume this attempted implementation of a lock. Assume 5 threads are competing for this lock. Assume disable interruptions by default (every thread runs until completion). How many threads can possibly acquire the lock, and get into the critical section at the same time?

1. We can possibly have 2 threads

2. It is not possible to have more than one thread at the time in the critical section.

3. We can possibly have 3 threads

4. We can possibly have 4 threads

5. We can possibly have 1, 2, 3, 4 or 5 threads

2

Assuming a maximum of 5 threads in the system, and further assuming the ticket lock is used “properly” (i.e., threads acquire and release it as expected), what values of lock->ticket and lock->turn are NOT possible?

1. ticket=0 and turn=0

2. ticket=0 and turn=1

3. ticket=1 and turn=0

4. ticket=1000 and turn=999

2 → turn cannot be greater than ticket

The following program creates and uses two threads to update the value of the global variable counter. Assuming the functions pthread_create() and pthread_join() all work as expected. Which outputs are possible?

1. 0

2. 995

3. 998

4. 999

5. 1000

6. None of the above

3 → if both threads read the counter before decrement

4 → if one thread decrements before the other

The following program creates and uses two threads to update the value of the global variable counter. Assuming the functions pthread_create() and pthread_join() all work as expected. Assume a proper lock of the variable counter (Although it is not possible to see that in the code, assume the variable counter is in between locks()). Which outputs are possible?

1. 0

2. 995

3. 998

4. 999

5. 1000

6. None of the above

3 → no interference between threads

A semaphore is synchronization primitive, is an object with an integer value that we can manipulate with two routines sem_wait() and sem_post(). In the following piece of code, the semaphore is initialized to what?

1 (the 0 means the semaphore is shared between threads in the same process.)

What happens in a binary semaphore? What should the semaphore be initialized to?

The semaphore should be initialized to 1, if it is negative, the thread will go to sleep.

1. sem_wait() → thread checks lock

2. thread goes to critical section

3. sem_post() → wake any thread sleeping

What happens when semaphores are used as condition variables?

In this scenario, the semaphore should be initalized to 0.

The parent calls sem_wait() and the child sem_post() to wait for the condition of the child finishing its execution to become true.

There are two possible outcomes:

1. parent waits, child signals, parent proceeds

2. child signals first before parent waits

What happens when thread call the function wait()?

pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m);

1. The thread goes to sleep in the condition variable (waiting state)

2. The thread automatically releases the lock

3. All of the above

3

What happens when thread call the function signal()?

pthread_cond_signal(pthread_cond_t *c);

1. The calling thread wake up

2. Send a signal to and wake up to all the threads sleeping in the condition variable c.

3. Send a signal to and wake up to one thread sleeping in the condition variable c.

4. None of the above

3

When a thread call the function signal()

pthread_cond_signal(pthread_cond_t *c);

we say that another thread sleeping in condition variable c wake up. Here, the meaning of waking up is what?

1. The thread was in the ready state, and start running

2. The thread was in the wait state, and transition to the ready state

3. The thread was in the wait state and transition to the running state

4. None of the above

2

Given the following multi-thread program. After executing line 13, the next line to be executed is what?

1. Line 6 to continue executing the next iteration of the for-loop.

2. Line 16 because the producer already produces and now the consumer has to consume.

3. Line 21 where a consumer is sleeping and now wake up.

4. The next line to be executed is up to the scheduler.

4

Select mechanisms for thread synchronization from the below.

1. Thread Merging

2. Mutex

3. Condition Variable

4. Stack

2 & 3

Match the statements to the right term.

A) TestAndSet

B) Race Condition

C) Mutual Exclusion

D) Address Space

1. It guarantees that if one thread is executing within the critical section, the others will be prevented from doing so.

2. Arises if multiple threads of execution enter the critical section at roughly the same time

3. Within a multi-threaded program, what aspect is shared between the threads?

4. This hardware instruction is used to build a mutual exclusion primitive like a lock.

1 → C

2 → B

3 → D

4 → A

What happen if thread one calls the function signal() on condition variable A and there are two threads sleeping in condition variable B?

1. Nothing, thread 1 just return from the call and continue running, there is no one to wake up

2. Wake up the first thread sleeping in condition variable B

3. Wake up the second thread getting sleep in condition variable B

4. Increase the value of the condition variable A by 1

1

Thread

• single point of execution (for single-thread)

• has a program counter (PC) where instructions are being fetched and executed

• share the same address space and the same data unlike a process

Threads in Context Switching

• Thread Control Block (TCB) → save the state of a thread, which include PC and a private set of register

• does not switch page tables since they share the same address space

Difference between single-thread and multi-thread

Multi-thread:

• more than one point of execution

• several stacks

Single-thread:

• one point of execution

• one stack

Why use threads?

• Parallelism: taking advantage of multiple CPUs or cores

• To avoid blocking program progress due to slow I/O

How to create and compile thread?

gcc -o t2 t2.c -pthread

Each time when the code is run, we get a different result, why?

• Race condition (or, more specifically, a data race) → the results depend on the timing of the code’s execution

• Because multiple threads executing this code can result in a race condition, we call this code a critical section.

• Critical section → a piece of code that accesses a shared variable and must not be concurrently executed by more than one thread (mutual exclusion!!)

States of the lock

• available (or unlocked or free) → no thread holds the lock

• acquired (or locked or held) → exactly one thread holds the lock and presumably is in a critical section

Semantics of lock()

• A thread P1 want to enter in the critical section by calling lock, if no other thread holds the lock (i.e., it is free), P1 will acquire the lock and enter the critical section.

• If other thread held the lock, P1 has to wait for the other thread to release the lock (P1 is not allow to enter in the critical section).

• P2 will release the lock, then P1 will get the lock, and will enter in the critical section.

How to develop a lock that doesn’t needlessly waste time spinning on the CPU?

Yield() → give up CPU and let another (moves caller from running state to ready state)

Condition variables

• used to wait until some variable meets some conditions

• more like channels than variables

  • B waits for a signal on channel before running

  • A sends signal when it is time for B to run

• explicit queue of waiting threads

Producer/Consumer (Bounded Buffer) problem

Producers generate data items and place them in a buffer. Consumers grab said items from the buffer and consume then in some way.

They both kill the program if buffer full. → if parameter for assert() is not true, program is killed

**Any time, this program can DIE EASILY. It won’t die if the producer runs first then the consumer, but that is not guaranteed → depends on scheduler → we need CV