exams

Question 1

Name an advantage of indirect message passing compared to direct message passing

Answer 1

+ allows the communication partners to be replaced
+ allows a message to be received by any process of a group of processes

Question 2

For which combinations of asynchronous or synchronous send and receive is buffered
message passing fundamentally required

Answer 2

Buffers are necessary whenever sending is asynchronous. Asyn send-operations return immediately and potentially continues to overwrite the message, so the message has to be placed in a buffer. Synchronous send requires the sender to wait for the receiver, rendezvous-style message passing can be implemented and the message can be copied directly to the receiver.

Question 3

Describe the producer-consumer problem. Name the cases in which one of the communication partners has to block.

Answer 3

The producer-consumer problem consists of senders (producer) and receivers (consumer) communicating via a shared bounded buffer. Producers put messages into the buffer and receivers remove messages from the buffer. A producer has to block while the buffer is full, and a sender has to block while the buffer is empty.

Question 4

Name a synchronization primitive which is suitable to notify other threads and which
does not have this problem (the first thread might block forever)

Answer 4

Semaphore or condition variable.
While a condition variable is the best way to solve any such problem, counting semaphores can be used as well in some situations. Non-counting primitives such as mutexes or spinlocks are not suitable for notification problems in general as they can only be used once at a time, and subsequent attempts to wait for a condition either result in race conditions or excessive blocking.

Question 5

Explain the difference between deadlock prevention and deadlock avoidance.

Answer 5

Deadlock prevention means that the system is restructured at design time so that arbitrary execution orders cant lead to deadlocks.
Deadlock avoidance, instead, restricts the allowed resource at runtime so that the system stays in a safe state, on the basis of knowledge about potential future resource requests by all involved processes.

Question 6

Describe a method to detect deadlocks.

Answer 6

By creating the wait-for-graph of all resource acquisitions and by searching for cycles in that graph. If a resource allocation graph is used, the OS needs to check whether the cycle can be resolved by continuing processes outside of the cycle.

Question 7

Assume a single processor system with non-interruptible interrupt service routines.
A resource that is protected by a spinlock is used in an interrupt service routine as
well as in interruptible kernel code.
In which situation does a deadlock occur? Identify the two resources involved in
cyclic waiting.

Answer 7

Deadlocks occur if the spinlock is held by the interruptible kernel code, that code is interrupted and the interrupt handler tries to acquire the spinlock. The interrupt handler prevents the previous code from proceeding but can’t proceed itself as the spinlock is locked. The second resource is the CPU (which is locked by the interrupt handler whereas the interruptible kernel code tries to acquire it)

Question 8

external fragmentation and internal fragmentation

Answer 8

Internal fragmentation:
If a memory manager only offers memory blocks of fixed sizes, the difference between the requested size and block size cant be used.
External fragmentation:
The free space in physical memory may be too scattered to allow the allocation of a segment of a certain length, even though the total free space is available.

Question 9

one way to reduce internal fragmentation when using paging and give two
disadvantages which are caused by this measure

Answer 9

by choosing a smaller page size
-increased page table size
-the TLB reach is reduced
-overhead

Question 10

How can external fragmentation occur when using a buddy allocator

Answer 10

External fragmentation can happen for example if multiple blocks of a certain level
have been freed but cannot be merged (1 P) because their respective buddies still
contain valid allocations – you can only merge blocks that are buddies. In that case
the total free memory might suffice to fulfill a memory request, but the memory is not
contiguous

Question 11

Explain, why the operating system cannot choose an arbitrary format for TLB entries
on a system with a software-managed TLB

Answer 11

The TLB entry format is specified in the instruction set architecture (ISA) of the respective CPU. Even with a software-managed TLB, the TLB is a hardware component, which is specified by the cpu manufacturer (1 P). The format of the page table
entries, however, can be chosen by the operating system.

Question 12

Name and explain one advantage and one disadvantage of physical tagging compared to virtual tagging

Answer 12

Correct answers for advantages include ((1 P) for a valid advantage):
* No ambiguity (homonym problem): A virtual address might point to different
physical addresses at different points in time. When using physical tags, homonyms
can be detected which means that the cache does not have to be flushed at each
context switch.
* Synonyms (multiple virtual addresses point to the same physical address) can
be detected by checking all entries of the cache
* Easy write-back. If the cache entry needs to be written back to main memory,
no additional TLB lookup is required.
Disadvantage ((1 P) for a valid disadvantage):
Modern systems use virtual memory abstraction. A TLB look-up is required to translate the virtual address to the physical address which is used for tagging. The virtual
to physical translation takes some time and might increase the latency of the cache.

Question 13

In order to reduce the latency of the L1 cache, a virtually indexed cache can be used.
Which coherence problem arises when using a virtually indexed, physically tagged
cache?

Answer 13

Aliasing (0.5 P) (coherence problem with synonyms). Virtual addresses that point to
the same physical address might be mapped to different cache sets.

Question 14

Name some information that is stored in the “flags” field in

Answer 14

It stores the file access mode (read or write) as well as file creation flags passed to open().

Question 15

The two processes pictured in the figure above share an entry in 2. How can this happen on a Unix system?

Answer 15

A call to fork() copies the local open file table, but not the entries in the global open file table. Consequently, two processes share an open file.

Question 16

In the system pictured above is it possible to get the filename of an opened file
starting from an entry in 1? Explain.

Answer 16

No, because there is no association from an inode to a directory entry/file name, but only the other way around. Even with the association, there might be multiple hard links or the opened file might have been renamed or deleted.

Question 17

What does the abbreviation “DMA” stand for

Answer 17

Direct Memory Access

Question 18

An operating system programs DMA devices so that they write to the memory of
user processes. Explain why it is still possible to switch the address space during a
blocking I/O operation

Answer 18

Changing the address space with a pending DMA operation is possible because the DMA device is programmed with physical addresses that stay valid even if they are not mapped in the virtual address space.

Question 19

A process invokes the kernel by a system call. Name two ways of passing the parameters to the kernel.

Answer 19

*parameters can be passed in registers
*parameters can be pushed on the stack by a program and popped off by the kernel
*when there are more parameters than registers, parameters can be stored in a block in memory and the address of the block can be passed as a parameter in a register.

Question 20

Why does a system call not necessarily require a context switch?

Answer 20

Since the kernel is mapped into the address space of all processes, system calls that do not block can be executed without changing address spaces.

Question 21

Besides potential performance advantages, give a reason why at least a part of
interrupt service routines is typically written in assembly language.

Answer 21

High-level languages usually do not allow the kind of low-level access to CPU hardware that is required in interrupt service routines (ISR). For instance, an ISR may be required to (de-)activate the interrupt servicing of a particular device or directly access certain registers.

Question 22

Name one exception triggered by the processor for which the process is usually continued after exception handling and one for which the process is usually terminated.

Answer 22

The process is usually resumed after a page fault.
The process is usually terminated after a division by zero or an invalid opcode.

Question 23

Name five segments typically present in the user address space.

Answer 23

.data, .rodata, .bss, .text, stack, heap

Question 24

Name one of these segments whose memory is usually shared between multiple
processes. Why is it shared?

Give a reason for one of the segments why it cannot be shared.

Answer 24

.text, .rodata
sharing saves memory (and load time).

heap
it can’t be shared because then allocations and modifications from one process would be visible in other processes, breaking the isolation.

Question 25

Name four operations the operating system offers for working with files

Answer 25

write
read
create
seek
delete
open
close

Question 26

Which two ways can the kernel use to access device registers?

Answer 26

port-mapped IO
memory-mapped IO

Question 27

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

Answer 27

many to one model (user level)

Question 28

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

Answer 28

*buggy program could trash other programs
*malicious users could steal other users’ sensitive data
*selfish user could use up all (virtual) memory for himself

Question 29

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

Answer 29

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 30

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 30

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 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 31

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 31

fork has to copy full address space of the calling process
fork duplicates lots of process state that is thrown away immediately upon calling exec()
forking is problematic in multithreaded applications

Question 32

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

Answer 32

+ 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 33

How is a futex (fast user-space mutex) different from a classic mutex? Which advantage does the futex have?

Answer 33

A futex first tries to spinlock the userspace to enter the critical section and only executes a mutex-like syscal to put the thread to sleep if the spinlock is busy.
As a result, futexes cause significantly less syscall overhead if congestion is low.

Question 34

The following code implements a simple barrier synchronization for N threads, which
causes the threads to leave the function barrier() only when all N threads have called
the function. Each thread executes barrier() only once in total.
Which erroneous behavior can be observed? Describe how the code has to be changed
to prevent this error.

int counter = 0;
void barrier() {
counter = counter + 1;
while (counter != N) {
/* wait until all N threads have called the function*/ }

Answer 34

The threads might never leave the barrier because an update to the counter is lost. The addition in line after counter+= counter has to be made atomic and by using an atomic instruction or a mutex.

Question 35

Describe how barrier synchronization can be implemented with direct asynchronous message passing. You can assume that every involved
process knows which other processes participate in the barrier synchronization and
that each process can be addressed by a unique known number (process ID)

Answer 35

Example implementation:
All processes send a message to all other processes
Each process then waits until N-1 messages were received before it continues.