1. True or False. Explain briefly if false:
a) In CPU scheduling, process starvation is possible in the FCFS technique.
b) In Round-Robin CPU scheduling, the average turnaround time increases with the increase of time quantum.
a) false. Unless processes take infinite amount of time to execute (which isn’t true), a process will eventually be executed.
b) false. The average turnaround time differ (sometime increases, sometimes decreases) as the value of time quantum increases
2. Briefly answer the following questions:
a) Please list the multithreading models to map from user threads to kernel threads.
b) What is spinlock? Briefly explain why spinlocks are not appropriate for single-processor systems yet are often used in multi-processor systems.
c) In priority scheduling of processes, aging can be used to prevent process starvation. How?
a) There are four models: one-to-one (each user thread maps to one kernel thread); many-to-one (many user threads map to one kernel thread); many-to-many (usually many user threads map to smaller number of kernel threads); and two-level approach.
b) Spinlock: when a process keeps running when it is blocked. In single processor systems, the spinlock process occupies the only processor while the condition it waits never changes. On the other hand, in multiple process systems, the spinlock process can wait in one processor while other processors work on other processes.
c) In order to avoid starvation, the aging technique can be used. Using this technique, the priority of low priority process will be gradually increased as the time that it waits in queue increases. Therefore, the (originally) low priority process will eventually have high priority and be executed.
3. There are two methods for Interprocess Communication (IPC): message passing and shared memory. (20 points, 10 points each)
a) Please briefly explain both.
b) In message passing, there are either blocking or non-blocking passing. Please briefly explain each of the four combinations.
a) Message passing: two or more processes are allowed to access a shared mailbox controlled by the kernel. A process sends message to other process(es) by putting the message into the mailbox.
Shared memory: two or more processes share the access to a newly allocated memory. A process writes to the shared memory to be read by others.
b) blocking send and non-blocking receive: the sender sends the message and wait until the message is picked up by the receiver. The receiver can check message any time. If there is no message, a NULL will be returned.
Blocking send and blocking receive: similar to above, but the receiver will wait until a message appears.
Non-blocking send and non-blocking receive: the sender sends the message and moves on with other tasks. The receiver can check message any time. If there is no message, a NULL will be returned.
Non-blocking send and blocking receive: similar to above, but the receiver will wait until a message appears.
4. In the following simple program, how many processes will have been created altogether (including the parent process)? Please explain.
#include <stdio.h>
#include <unistd.h>
main() {
fork();
fork();
sleep(100);
return 0;
}
One fork() will generate one new child process. The first fork() will result in two processes (parent and child). The second fork() executed by them will create two new child processes. Altogether there are 4 processes.
5. Explain how semaphore can be used to ensure ordered execution of a line L1 in process P1 and L2 in process P2. Therefore, L2 will always be run after L1 no matter how P1 and P2 are run. (15 points)
P1: …
L1
…
P2: …
L2
…
In order to ensure the execution sequence, a semaphore s can be defined and initialized to 0. We add s.signal() after L1 in P1 and add s.wait() before L2 in P2.
So it looks like
P1: …
L1
s.signal()
…
P2: …
s.wait()
L2
…
