Processes and Threads

Question 1

Explain the difference between a program and a process.

Answer 1

A program is a sequence of instructions that accomplish a given task.
A process is an instance of a running program.

Question 2

Consider an operating system, which supports the four process states “ready”, “running”, “blocked”, and “zombie”. Depict the possible state transitions and label each edge with an event causing the transition.

Answer 2

ready - (dispatch) -> running
running - (interrupt) -> ready
running - (I/O wait) -> blocked
running - (terminate, exception) -> zombie
blocked - (I/O complete) -> ready

Question 3

Explain the purpose of the PCB and the TCB. For each structure, give two pieces of
information that is stored in it.

Answer 3

Process Control Block: The PCB is the kernel data structure to represent a process. Two typical fields are: list of open files, structure to describe the
address space.

Thread Control Block: The TCB is used by the kernel to represent a thread. Two typical fields are: pointers to stacks, thread execution state.

Question 4

What is a User-Level Thread (ULT)? Which thread models presented in the lecture employ ULTs?

Answer 4

A user-level thread is a thread that is entirely implemented (i.e., control structures, scheduling, dispatching, etc.) in user level. Depending on the thread model, the kernel is not aware of user-level threads.
ULTs are used in the many-to-one and the M-to-N thread models.

Question 5

A web server uses a fixed pool of processes to handle connections from multiple clients in parallel. Give an advantage and a disadvantage of this scheme compared to using the same number of threads.

Answer 5

+Using multiple processes, each worker has her own address space. As a result, a segmentation fault in one worker does not affect the others. When using multiple threads in the same address space, a segmentation fault in one thread crashes the entire server. In case of a security vulnerability, a separate process for each connection also prevents leaking data from different clients.
-communication and coordination between worker processes is more complex than doing the same between threads in the same address space

Question 6

Besides the preemptive MLFQ-based scheduler, the Linux kernel also contains a non preemptive FCFS scheduler. Threads scheduled by the FCFS scheduler always have priority over threads under the MLFQ scheduler. Processes with administrator privileges can choose which scheduler their threads use. Processes without administrator privileges always use the MLFQ scheduler.
For which type of application is the FCFS scheduler beneficial?

Answer 6

> The non-preemptive FCFS scheduler is suited for applications that execute mostly in short bursts and that must be handled with high urgency. These are
typically real-time applications.

> Short Bursts: If the application does not execute in short bursts, there is a danger of these applications starving the system.

> Urgency: Since applications under the FCFS scheduler are always preferred, the application should be time-critical.

Question 7

Why are only applications with administrator privileges allowed to use the FCFS scheduler?

Answer 7

It is easy for applications to abuse the non-preemptive FCFS scheduler: Since FCFS processes are never preempted, an application can easily hog the CPU by putting a CPU-bound thread into the FCFS scheduler. Therefore, untrustworthy users
should not be allowed to use the FCFS scheduler without approval from an administrator.

Question 8

Consider an operating system, which assigns a 16-bit process ID (PID) to each process. On process creation, the system determines a unique PID by atomically incrementing a global counter and using the new counter value as PID. Explain why this system would cause problems in practice.

Answer 8

With a PID of 16 bits, a maximum of 65536 processes can be created before the counter overflows. Once this happens, the system will start to reuse previously used PIDs, possibly even those of existing processes.

Question 9

How could the PID allocation be adjusted?

Answer 9

The system must find the next unused PID instead of simply incrementing the counter, for example by incrementing the counter repeatedly until reaching a PID that is not currently assigned to a process.

Question 10

Which one of the thread models presented in the lecture would you choose for an I/O-intensive application?

Answer 10

The one-to-one model, because I/O-intensive applications can be expected to block frequently. Since all threads are known to the kernel in the one-to-one model, it is possible to block only those threads actually performing I/O operations.
In the many-to-one model, all user-level threads would be blocked as soon as one of them performs I/O, because the I/O operation would block the underlying kernel-level thread.

Question 11

Explain the term long-term scheduling.

Answer 11

Long-term scheduling is used to decide at what time processes are started in a system. In other words, the long-term scheduler decides which (and how many) processes are visible to the short-term scheduler.

Question 12

Explain the difference between a scheduler and a dispatcher.

Answer 12

A dispatcher implements the mechanism to switch threads. It is given a thread to switch to, and then performs the tasks necessary to make that thread run on the CPU, such as saving the old thread’s context to memory and restoring the new thread’s context.
A scheduler implements the scheduling policy. It is thus responsible for selecting the next thread to run after the previous thread has exhausted its time slice or blocked for I/O. After making a selection, the scheduler typically calls into the dispatcher, passing an identifier for the selected thread.

Question 13

Discuss the advantages and disadvantages of short over long time slices in preemptive round-robin scheduling (not virtual round-robin). Use the criteria presented in the lecture for assessing scheduling policies.

Answer 13

+improved interactivity
+shorter response time
+Improved fairness for I/O-bound jobs

-increased turnaround time
-increased scheduling and dispatching overhead
-decreased throughput

Question 14

Explain the concept of priority inheritance.

Answer 14

Priority inheritance (or priority donation) can be useful if a high-priority task A depends on the completion of a low-priority task B, in which case A donates its priority to B so B completes faster. Otherwise, A effectively gets a lower priority than B, because A cannot run, until B has finished (i.e., the scheduler selected the low-priority task).

Question 15

Name one data structure that is allocated in the user address space and one that is allocated in the kernel address space during the creation of a kernel-level thread.

Answer 15

User space: (User-)Stack
Kernel space: Thread control block (TCB)

Question 16

Name three reasons for terminating a process.

Answer 16

> Voluntary termination: The process has finished the task it was started for.

> Fatal error: The process has encountered an error or the OS kills the process because of an exception (e.g., a segmentation fault).

> External termination: The process is killed by a signal from another process.

Question 17

Explain the term preemption. Which feature must the hardware provide for preemption to be possible?

Answer 17

Preemption means that the OS can interrupt running threads, storing their state so their execution can be seamlessly resumed later.
For preemption to work, the hardware must provide a timer interrupt.

Question 18

Do daemon processes in interactive systems typically have a high or low scheduling priority?

Answer 18

A low priority. Daemons are background processes that are not directly visible to the user. The user is less likely to notice slow-running daemons, which is
why resources should preferably be allocated to foreground processes that the user interacts with.

Question 19

Can priority inversion occur in the many-to-one thread model?

Answer 19

Yes. Priority inversion is a scheduling problem and therefore unrelated to the type of thread used. If a high-priority thread A waits on a spinlock held by
low-priority thread B, A cannot continue if the scheduler constantly selects threads with a higher priority than B for execution. Whether that scheduler executes in user or kernel space makes no difference.

Question 20

Which data about a zombie process must a POSIX-compatible operating system at least store until that process is terminated for good?

Answer 20

> Exit status: This is what is collected by waitpid()

> Process ID (PID): Since the parent process can wait for a specific child, the OS must know which exit status belongs to which process

> Parent process: Since processes can only wait for their own children, the operating system must store parent-child relations for zombies to allow for permission checking. This relationship can be stored either in the child (as a link to the parent process) or the parent (as a list of children)

Question 21

Does it make sense to free all virtual memory in the user mode address space of a process when that process becomes a zombie?

Answer 21

Yes. A process can only become a zombie after it exits. This implies that no activity can take place in the address space of a zombie process, which is why the contents of the address space are not needed anymore.

Question 22

Consider an OS using a round-robin scheduler with a fixed timeslice length. This OS attempts to give more CPU time to important threads by adding these threads to the scheduler’s queue multiple times. However, the system often crashes as soon as such a thread blocks. Which problem probably caused the crash? Suggest a solution for this problem that otherwise preserves the properties of the scheduler.

Answer 22

The problem with this scheme is that if one thread blocks for I/O, there will be more entries for this thread in the scheduler’s queue. The scheduler may thus select a thread to run that is not ready to run.
Possible solutions include:
* Whenever a thread blocks, scan the scheduler’s queue and remove all entries for this thread.
* Store a timeslice length in each thread’s TCB, and run each thread for its stored timeslice length once selected. This way, some threads can be granted more time without the need for multiple entries per thread in the scheduler’s queue.
* Have the scheduler check the thread’s state before actually scheduling it, and advance to the next queue entry if the current entry refers to a blocked thread.

Question 23

Parallel execution can be implemented both with processes as well as threads. List and explain two advantages of threads compared to parallel processes.

Answer 23

+All threads of a process share the same address space which facilitates communication and coordination between the threads
+Switching between threads causes less overhead than switching between processes because the address space does not need to be switched.

Question 24

Give one advantage and one disadvantage of user-level threads compared to kernel-level threads.

Answer 24

+User-level threads can be implemented on OS that don’t support kernel-level-threads.
+Switching between user-level threads causes less overhead than switching between kernel-level threads. As a consequence user-level-threads tend to be faster and more efficient.

-If one user-level thread invokes a blocking system call all other threads of the process are blocked as well.
-The process scheduler implemented as part of the kernel lacks knowledge about the number of threads per process which might lead to poor scheduling decisions.

Question 25

Does each thread of a process have its own stack?

Answer 25

Yes, every thread needs its own stack to allow independent function calls.

Question 26

Explain the “convoy effect” which can occur when a first come first serve (FCFS) scheduler is used.

Answer 26

If one long job arrives first, the other jobs have to wait for the first job to finish even if they are very short.
The convoy effect leads to a bad utilization of I/O devices and a poor average turnaround time.

Question 27

Consider a scheduling policy which selects for execution the process with the shortest next CPU burst, in order to minimize average waiting time. Why does this policy, however, not necessarily result in the minimal average turnaround time?

Answer 27

If a long I/O intensive job with many short CPU bursts is executed, it is given priority over shorter jobs with longer CPU bursts. Due to their lower priority, those shorter jobs have to wait, which might increase the average turnaround time.

Question 28

Explain the difference between kernel-level threads and kernel-mode threads?

Answer 28

Kernel-mode threads perform background tasks such as garbage collection, freeing page frames and swapping them out to disk, calculating checksums, mirroring disks in a software RAID, or distributing load to other processors. As the name suggests, kernel-mode threads are completely running in kernel-mode, meaning that privileged instructions can be executed without an additional system call.

Kernel level threads are threads running in user-mode and kernel-mode, which are managed and scheduled by the kernel – as opposed to user-level threads which are managed in user-mode.

Question 29

Explain the term upcall?

Answer 29

An upcall is a call from a lower-level subsystem, such as a kernel to a higher-level subsystem, such as user code. Note: A system call is not an upcall but a downcall from user code to the kernel

Question 30

Explain the importance of upcalls when using a M-to-N threading model?

Answer 30

In the many-to-many model there must be some way for the kernel to communicate with the user-level thread manager to maintain an appropriate number of kernellevel threads allocated to the process. This mechanism is called scheduler activations. The kernel notifies the user-level thread manager of important kernel events using upcalls from the kernel to the user-level thread manager. Examples of such events include a thread making a blocking system call and the kernel allocating a
new kernel-level thread to the process.

Question 31

A figure shows the performance of a computing system in dependence on the number of concurrently executed processes. Explain why the system performance rises in the left part of the figure when the number of processes is increased.

Answer 31

Multiprogramming lets processes use the CPU when it would otherwise become idle. Suppose the CPU phases of a process are as long as the I/O phases. In a single-programming system, there would be no overlapping on the CPU. So, the CPU
would be idle up to 50 % of the time while accessing the I/O device. As the number of processes is increased, the probability that at least one process wants to use the CPU rises.
Note: Processes are executed concurrently (not in parallel).

Question 32

A figure shows the performance of a computing system in dependence on the number of concurrently executed processes. Why does the system performance collapse in the right part of the figure?

Answer 32

When the number of processes is too high, thrashing occurs. The system doesn’t have enough physical memory to keep the working sets of all running processes in memory. This causes constant swapping of pages and severely inhibits progress.

Question 33

How can the collapse of the system performance be prevented by the operating system?

Answer 33

If the working sets of all running processes do not fit into memory, the long-term scheduler may select some processes and temporally suspend them, so that other processes can make progress.

Question 34

Assume that two processes A and B are executed alongside other processes on a system with a round-robin scheduler in a concurrent way. For the following experiments, the length of the timeslice of the round-robin scheduler is changed and the
turnaround times of process A and process B are measured for each experiment.
If the length of the time slice is reduced from T0 to T1 = 0.1 · T0, the turnaround times of process A and process B are considerably increased. Explain the cause.

Answer 34

The number of context switches is increased by a factor of 10 which leads to additional computational overhead due to kernel invocation, storing and loading of the process control blocks, flushing of caches etc.

Question 35

If the length of the time slice is raised from T0 to T2 = 2 · T0, the turnaround time of process A is slightly reduced whereas the turnaround time of process B is considerably increased. Explain this behavior

Answer 35

As the time slice is increased, the computational overhead for context switches is reduced which is beneficial for CPU-bound processes like process A. Process B, however, is IO-bound and isn‘t able to use its full time quantum if the time slice is doubled due to frequent waiting for I/O. Whenever process B invokes the kernel to access IO, the scheduler selects the next process for execution regardless of whether its time quantum is fully used or not.

Question 36

Explain the functional principle of a multilevel feedback queue. How do the levels of a multilevel feedback queue differ from each other?

Answer 36

When using a multilevel feedback queue, the OS tries to achieve a good trade-off between interactivity and computational overhead caused by context switches. A Multi-Level Feedback Queue consists of multiple scheduling queues
with different priorities. Processes that do not use up their quantum repeatedly are promoted into a higher priority queue while CPU-bound processes are demoted. IO-bound processes end up in a high priority queue and are scheduled more frequently
but with a shorter time slice, thereby improving their interactivity. CPU-bound processes are given a lower priority but run for longer at a time, which reduces the computational overhead due to context switches. Apart from priorities, the queues can differ in their time quantum and in the scheduling algorithm (e.g. Round Robin or FCFS).

Question 37

Explain how priority inversion can be prevented.

Answer 37

Priority donation (also known as priority inheritance) prevents the problem of priority inversion. A process that is blocking a resource needed by a higher-priority process inherits the higher priority until it releases the resource.

Question 38

A scheduling policy selects among all runnable processes the one with the highest priority. Assume, there are three processes L, M, and H with priorities p(L) < p(M) < p(H). Explain how priority inversion can occur.

Answer 38

If process H requires a resource, which is currently held by process L, process H has to wait for process L to release the resource. Process L cannot release
the resource as long as process M is runnable, since process M is scheduled prior to process L. Indirectly, process M affects how long process H has to wait for the resource, although process M has a lower priority than process H. This effect is called priority inversion.

Question 39

Explain how a selfish process can maximize its amount of CPU time when multi-level feedback queue scheduling is used.

Answer 39

A selfish process can maximize its CPU time by relinquishing the CPU right before its time quantum is fully used up, thus keeping or increasing its priority.

Question 40

Explain how the shortest job first strategy can be approximated in practice.

Answer 40

The shortest job first strategy can be approximated by selecting the next process based on the length of its next CPU burst rather than its total execution time. The length of the next CPU burst can be predicted as an exponential average of previous CPU bursts.

Question 41

The shortest job first scheduling policy selects the process for execution which has the smallest total execution time. Explain why the policy cannot be implemented for arbitrary processes.

Answer 41

The total execution time of a process must be known before execution.

Question 42

How do zombie processes arise? Which purpose do they serve?

Answer 42

A zombie process is a process that has completed execution (via the exit system call) but still has an entry in the process table. The entry in the process table is still needed to allow the parent process to read its child’s exit status via wait().

Question 43

Which thread model does not allow processes to utilize the full performance of multicore system

Answer 43

The Many-to-One Model (User Level Threads)

Question 44

Give two reasons why the operating system should isolate the address spaces of different processes.

Answer 44

> Buggy program could trash other programs.
Malicious user could steal other users sensitive data like passwords.
Selfish user could use up all (virtual) memory for himself.

Question 45

How many child processes are created in the code shown below when executing
main()?
1 void main() {
2 fork();
3 fork();
4 }

Answer 45

Three child processes are created. After the initial process forks in line 2, there are two processes running, a parent and a child. Each of them then forks in line 3, creating two additional processes. Then all the processes exit.

Question 46

What is cooperative scheduling?

Answer 46

Cooperative scheduling means that the OS does not forcibly preempt running threads. Instead, threads must relinquish the CPU voluntarily, for
example by blocking for I/O or calling yield() explicitly.

Question 47

In which thread model is cooperative scheduling usually used?

Answer 47

With the many-to-one thread model (ULT)

Question 48

In contrast to the combination of fork() and exec(), CreateProcess() on Windows creates a new process in a single system call. What advantage besides the
reduced number of system calls does this offer?

Answer 48

• fork() has to copy the full address space of the calling process, which is slow for big address spaces. A combined call does not need to copy the address space.
• fork() duplicates lots of process state that is thrown away immediately upon calling exec(). A combined call can initialize the new processes with the correct state directly.

Question 49

On multi-core processors, the Linux scheduler uses a queue for each core. Name an advantage (+) and a disadvantage (-) of this approach.

Answer 49

(+) No cross-core synchronization is necessary in the normal case, as the scheduler works on local data structures.
(-) The scheduler needs to do periodic load balancing across cores.

Question 50

Name four typical goals of a scheduling algorithm.

Answer 50

Fairness, balance, low response time, high throughput, low scheduling overhead,
high CPU utilization

Question 51

Assume that the scheduler moves all processes to the highest-priority queue every 500 ms. Which problem does this strategy solve? Describe a scenario where this problem might occur.

Answer 51

Starvation would occur if a CPU-bound process runs at the same time as lots of I/O-bound processes. The I/O-bound processes would always stay in the high-priority queues, preventing the CPU-bound process in the low-priority queue from running.

Question 52

What is the advantage of lazy dynamic binding?

Answer 52

Lazy dynamic binding reduces the program’s startup time because the individual functions in the dynamically-linked libraries are only resolved in PLT and GOT when they are first called.

Question 53

When a process calls fork(), the system creates a nearly exact copy of the parent process. Why is the copy only “nearly exact” and not an “exact” copy?

Answer 53

The process id of the child needs to be unique and thus cannot be copied. To distinguish parent and child in the code, the fork() call returns 0 in the child and the child’s pid in the parent.

Question 54

Which thread model uses scheduler activations?

Answer 54

Hybrid Threads / M-to-N

Question 55

A core functionality of the operating system is process isolation. What does that mean and how does the OS implement isolation?

Answer 55

The OS puts each process in its own address space and multiplexes hardware between all processes (limited direct execution). Consequently, processes can’t see each other and thus cannot read or modify other process’s data.

Question 56

Name two operating system functionalities that weaken the isolation between processes.

Answer 56

> IPC mechanisms such as shared memory, message passing, signals
(shared) file system access
shared resources after fork() such as file descriptors
debuggers
the /proc file system

Question 57

What is a daemon? Give an example.

Answer 57

A daemon is a process designed to run in the background, without direct control from the user.
Examples:
* networking software such as web servers
* hardware control software such as sound servers or network configuration agents
* long-term schedulers in user space such as the init process or cron

Question 58

What is the init process? Which role does it play with regard to daemons?

Answer 58

The init process is the initial user space process started by the kernel.
The init process is responsible for launching most daemons.
OR
In the process hierarchy, daemons are usually placed directly below the init process. This can be accomplished by having the daemon’s parent process exit.

Question 59

When starting a new thread, memory needs to be allocated. Which structures need this memory? In the one-to-one model, in which address space are these structures located?

Answer 59

A thread needs memory for:
* the stack, allocated in the user address space
* the thread control block (TCB), allocated in kernel space.

Question 60

Which problem does Virtual Round Robin solve in comparison with normal round robin? Explain the problem and the solution.

Answer 60

RR is unfair to I/O bound jobs because they block before using up their time slice. When a process blocks, Virtual RR stores the remaining time slice and gives those processes priority over CPU-bound processes until the stored time slice is used up.

Question 61

Name a scheduling algorithm which only makes sense on pure batch systems.

Answer 61

• First Come First Serve
• Shortest Job First

Question 62

Where are the process control blocks (PCB) located in the address space?

Answer 62

The PCBs are stored in the kernel’s memory range.

Question 63

Is it possible for a debugger in a multiprocessor system to observe the execution of another process running in parallel by reading its PCB and TCB?

Answer 63

No, although the PCB and TCB contain the execution state of a process, most information is only valid while the process is not running.

Question 64

Give two voluntary events that might trigger a thread switch in the One-to-One model.

Answer 64

• calling yield()
• executing a blocking system call
• waiting on a mutex or semaphore
• thread exit

Question 65

What does a long-term scheduler do?

Answer 65

The long-term scheduler selects which processes to put into the ready queue.

Question 66

Which issue commonly occurs in systems with strict priority scheduling?

Answer 66

Systems with strict priority scheduling often suffer from starvation: Low priority processes will never run if there is a runnable higher-priority process for an extended period of time. (priority inversion)

Question 67

Give an alternate name for the hybrid threading model.

Answer 67

M:N model

Question 68

A process can be in different states at a given time. In the ** state, a process is executing instructions on a processor. When a process initiates **, it becomes ** for a while so that it does not unnecessarily waste processing time. Finally, after a process calls exit, it sticks around in the ** state until its parent process reads its **.

Answer 68

Running
An I/O request
blocked/waiting
zombie / terminted
exit status

Question 69

Name four elements of a Process Control Block.

Answer 69

• process state
• process id
• program counter
• CPU registers
• scheduling information
• memory management information
• list of open files

Question 70

Explain why a FCFS-scheduler is a bad choice for desktop systems

Answer 70

FCFS does not preempt running processes and therefore does not provide good interactivity, which is important for desktop systems. If, for example, a single process runs on the CPU for an extended period of time, other processes, including the desktop environment, are never dispatched.

Question 71

t_turnaround

Answer 71

t_finish − t_arrival

Question 72

t_wait

Answer 72

t_finish - t_arrival - t_length

Question 73

t_response

Answer 73

t_firstdispatch - t_arrival

Question 74

On SMP systems, current schedulers use one ready queue per CPU to avoid synchronization overhead when accessing the queues. Describe a problem of this approach compared to a single ready queue shared by all CPUs, and suggest a solution for the
problem.

Answer 74

If multiple ready queues are used, it is possible for one queue to run empty while others still contain threads ready to run. This results in poor system utilization since the empty queue causes one CPU to idle even though there is plenty of work to be done.
A possible solution to this problem is for the idle CPU to check if the ready queues of other CPUs contain waiting threads and if so, to pull some of these waiting threads into its own ready queue. This scheme is also known as work stealing.

Question 75

Describe an advantage and a disadvantage of cooperative Round-Robin-Scheduling compared to non-cooperative Round-Robin-Scheduling. Assume that all tasks perform I/O after a finite amount of computation.

Answer 75

The main advantage of non-cooperative Round-Robin over cooperative Round-Robin is that the former distributes the available CPU time fairly: Each task receives the same number of time slices on average, with each time slice having the same length.
On the other hand, a non-cooperative Round-Robin scheduler frequently preempts all running tasks, possibly at inconvenient times. In contrast, a cooperative RoundRobin scheduler switches away from a running task only when it is convenient for
that task to do so (e.g., when that task must wait for I/O anyway). Therefore, the main advantage of a cooperative Round-Robin scheduler is a much lower scheduler overhead.