midterm

Question 1

What are the key roles of an operating system?

Answer 1

Hides hardware complexity
manages resources
provides isolation & protection between applications running on the OS

Question 2

Can you make distinction between OS abstractions, mechanisms, policies?

Answer 2

Abstractions:
complicated interactions between the OS and hardware that the OS makes simpler for applications running on a system.
Examples include: process, thread, file, socket, memory page.

Mechanisms:
“verbs’ that describe actions an operating system can do on abstractions, like “create”, “schedule”, “open”, “write”, “allocate”.

Policies:
concepts implemented by Operating systems to efficiently deal with the nature of computer hardware and software interaction.
For example the operating system can have a policy about how long content can stay in memory instead of just being on disk. Others include Least Recently Used (LRU) and Earliest Deadline First (EDF)”

Question 3

What does the principle of separation of mechanism and policy mean?

Answer 3

Mechanisms in the operating system can support multiple policies. The mechanisms are flexible. The memory management mechanism might use different policies depending on the situation (LRU, LFU, random, etc.)

Question 4

What does the principle optimize for the common case mean?

Answer 4

designing the OS based on how it will be used, what the user will be executing, what are the workload requirements of the user.

important because it allows the OS to be as effective as possible.

entails the OS choosing specific mechanisms and policies that match its most common usage.

Question 5

What happens during a user-kernel mode crossing?

Answer 5

When a user application/process tries to execute a function that requires kernel level permissions the call (system call) is sent across the user-kernel boundary.

The kernel performs the system call and then returns to the user process. During the time when in privileged mode a bit is set on the CPU which allows privileged calls to be performed, this bit is not set when in user mode.

A trap can also occur when a user-level process attempts to perform a privileged function, the operating system will then check if the calling process should be allowed to do that action or not.
Crossings are slow, every time a system call is made it (crossing) affects hardware cache by switching locality. App loses part of the data from cache in favor of whatever the OS needs to bring in to perform its system call.

in user-kernel mode crossing the mode bit is set in CPU, and control is passed to kernel)”

Question 6

What are some of the reasons why user-kernel mode crossing happens?

Answer 6

when a user-level thread/process/applications attempts to do a privileged action while the OS is not operating in privileged mode causing a trap
OR
when a user-level thread/process makes use of the OS level provided system calls which have the operating system perform said privileged actions.
OR
hardware interrupts; for example, the timer interrupt is what lets the kernel regain control to do scheduling.
OR
“(I also think that signals are user-kernel mode crossing but in the other direction: from kernel to user)” -

Question 7

What is a kernel trap? Why does it happen? What are the steps that take place during a kernel trap?

Answer 7

alert to the operating system that an unprivileged user process has attempted to perform a privileged task or access privileged memory addresses. When this occurs the OS determines the source of this trap, determines if it should be allowed or not and then after returning execution to the interrupted user process.

Question 8

What is a system call? How does it happen? What are the steps that take place during a system call?

Answer 8

an operation (belonging to a set) that the OS makes available to applications which can explicitly invoke a privileged mechanism.

happens when a user-level application makes a system call telling the OS it would like it to perform said privileged action.
step

1. User Process makes a system call
2. Control is passed to the operating system which sets the kernel mode bit to 0 (privileged access only). It jumps to the place in memory for the OS function to take place (along with the optional arguments from the user process.
3. The system call completes execution and returns the result to the original user process which requires an execution context switch back to user-level privilege.

There are both synchronous and asynchronous versions of system calls.”

Question 9

Monolithic OS

Answer 9

design is large and can be hard to manage and may not be very portable, but it can be optimized at compile time since it includes everything a system will need.

downside of it is customization, portability and manageability due to large codebase, which can be hard to code, debug and maintain. Also the memory footprint can be huge and it can impact performance.

Question 10

Modular os

Answer 10

design can be smaller than monolithic because it is interface implemented oriented - meaning modules that are required based on the usage and workload of the operating system can be loaded in if they are necessary and excluded if not.

less resource intensive and is easier to maintain; however, performance is impacted because of interfaces and modules are often sources of bugs which are not directly the fault of the operating system implementing said modules. Given that modules can come from non-kernel authors this approach can be buggy.

Question 11

Microkernal OS

Answer 11

design has a very small footprint and only supports very basic roles.
Memory management,
address space,
location for execution of user processes.

The user-level runs the typical operating system components like file systems, disk drivers, etc. This requires much moreless inter-process communication interactions.

very small and test (useful for embedded devices).

often less portable (very specific for said devices) and could be slow because of number of user-kernel boundary crossings that are required.

Question 12

Process vs. thread, describe the distinctions.

Answer 12

“A process is any user application that is running on the operating system.
has it’s own memory space allocated to it. Both heap and stack allocations in virtual memory
The process consists of its address space - this includes: the code (text), the data that’s available when the process is initialized, the heap, and the stack. As the process executes dynamic data is added to the heap. The stack is a LIFO (last in first out) data structure that is useful for process execution when an applications needs to jump to another location to execute something and later return to a prior position.

A thread is similar to a process except in the case of multiple instances it has it’s own program counter, stack pointer, stack and thread-specific registers. But it shares the same virtual address space with other threads..”

Question 13

What happens on a process vs. thread context switch.

Answer 13

“During a process context switch all information about the process that is being preempted that is tracking by the CPU will be updated in the process control block for that process. The CPU will then have the information loaded for a different process, and then switched back when the context switch happens in reverse. It may also require data be removed from the processor cache to make room for the other process.

When a context switch occurs, the running thread stores its execution context (its program counter, stack pointer, and register values) in memory, and the new thread’s execution context is loaded from memory onto the processor. This is faster than a context switch between processes, because threads don’t need the costly virtual to physical address mappings to be swapped out or recreated. This also leads to hotter caches during switches which is a performance optimization.”

Question 14

Describe the states in a lifetime of a process?

Answer 14

New - First state when a process is created
Ready - Once OS admits process it will get a PCB and some initial resources, a running process is interrupted (context switch)
Running - OS Scheduler gives CPU to a process
Waiting - I/O event (or some other long running event/operation), causes a Ready state after I/O or event completes
Terminated - Process finishes all operations or encounters error

Question 15

Describe the lifetime of a thread?

Answer 15

created when a parent process/thread calls a thread creation mechanism.

then run asynchronously (unless blocked/waiting).

can be signalled or broadcasted to in order to check if they need to continue blocking or continue executing. The parent process/thread can call a join mechanism to block itself until a child completes after which it’s result can be returned to said parent.

Question 16

Describe all the steps which take place for a process to transition from a waiting (blocked) state to a running (executing on the CPU) state.

Answer 16

A waiting process will wait until it’s current event or operation that caused the WAITING state to finish. It will then transition to a READY state. Once in the READY state the process can be scheduled by the scheduler to have a CPU in which case it will enter the RUNNING state.

Question 17

What are the pros-and-cons of message-based vs. shared-memory-based IPC.

Answer 17

“Message-based uses a OS provided communication channel to allow processes to send messages to each other.
good - the operating system maintains this communication channel for the processes so the API is more universally implemented.
bad - requires a lot of overhead. The processes have to copy information into the communication channel into kernel memory through the OS (i.e. system call).

Shared-memory-based IPC is implemented when the OS maps a shared memory space for processes to share.
Good - Both/all processes can access this shared memory space as if it were their own. This gets the OS out of the way which is good for performance,
Bad- OS no longer manages that address space it’s up to the processes which can be bug prone and processes must know how to handle said shared memory space.”

Question 18

What are benefits of multithreading?

Answer 18

allows parallelization to occur which helps achieve overall performance/speed increases and/or execution time decreases.
Multiple threads of an application can be at different points in execution handling more input at the same time (especially on multi-core systems).
Threads can also be assigned long execution and block tasks so the main application or other threads can continue processing information/input while other threads wait for slower devices like I/O.
requires less memory because threads can share address space. This means the application requires less memory which could result in less memory swaps.

Question 19

When is it useful to add more threads, when does adding threads lead to pure overhead?

Answer 19

Depending on the input and tasks of an application it could be beneficial to add more threads.
For example in a pipeline pattern it could make sense to match the number of threads to the number of steps in the pipeline or perhaps several threads per step (for the longer/more involved steps). In boss-worker patterns it might be detrimental to add more threads dynamically if there isn’t enough work for those threads to do. (I think it’s useful to add more threads as long as there is idle CPU time. So instead of letting CPU stay idle, another thread can be context-switched and start doing useful work. But once there is no idle CPU time to utilize, then adding more threads just adds overhead and slow down processing)

Question 20

What are the possible sources of overhead associated with multithreading?

Answer 20

context switching & synchronization between threads

when a boss thread has to manage a pool of worker threads. It may not know exactly what each thread is doing or what it did last so it is difficult to know during execution time which threads may be more/less efficient at certain tasks.

overhead of keeping the shared buffer synchronized.

Question 21

Describe the boss-worker multithreading pattern

Answer 21

one boss/main thread which creates one or more children/worker threads to complete tasks.

assumes each worker thread fully complete the task, in that, each worker will fully handle all portions/subtasks of a task.
boss thread will then call joins and wait for worker thread executions before finishing execution or moving on to another portion of the application logic.

Question 22

If you need to improve a performance metric like throughput or response time, what could you do in a boss-worker model?

Answer 22

add work to a queue which the worker threads can then work on. This gives the boss less one-on-one work with each thread and it can focus on creating a queue. The queue can be created fully before the worker threads are created, or the threads could be created and then the boss can start adding work to the queue for even more efficiency in response time/throughput.

Another way to improve the performance is to exploit ‘locality’. This can be done by the boss assigning smaller specialized sub-tasks to threads. If the thread is continually working on that specific task, it’ll more likely utilize the ‘hot cache’ for faster performance)

Question 23

.What are the limiting factors in improving performance with boss/worker pattern?

Answer 23

overhead associated with the synchronization requirements of shared buffer resources,

in addition this pattern ignores locality (meaning the boss doesn’t try to positively affect hot cache performance opportunities).

Question 24

Describe the pipelined multithreading pattern.

Answer 24

n number of threads that each handle one subtask in a series of tasks to accomplish the overall purpose of the application.

The first thread(s) pass on the tasks to the second thread(s) to perform a separate task that relies on the first task being complete, so on, until the end of the overall process.

Question 25

If you need to improve a performance metric like throughput or response time, what could you do in a pipelined model?

Answer 25

more information is gathered about how long each subtask will take, or at the very least how much time each subtask takes relative to each other. For example if subtask_1 takes 10 ms and subtask_2 takes 30 ms then it makes sense to have 3 times as many subtask_2 threads than subtask_1 threads.

Question 26

What are the limiting factors in improving performance with pipelining pattern?

Answer 26

overhead involved with synchronizing threads as well as balancing (accurately determining the number of threads that should be performing each subtask).

Question 27

mutexes

Answer 27

Mutexes is a mechanism employed in multithreading program to enable mutual exclusion within the execution of concurrent threads.

mutexes protect shared information from being updated simultaneously from different areas at the same time. Mutexes are used like locks to ensure access to share information happens exclusively.

Question 28

Condition Variables

Answer 28

supplemental mechanisms to mutexes that allow a more fine grained control over the behaviour of multiple executing threads.

keeps track of which threads are waiting on a certain set of criteria to be true.

used in a multithreading library API via wait() commands. Threads can then signal or broadcast to condition variables to wake other threads that are waiting on the same condition(s).

Question 29

What are spurious wake-ups, how do you avoid them, and can you always avoid them?

Answer 29

Spurious wake-ups occur when a thread completes a task and then before unlocking a mutex begins to signal/broadcast to other threads that will need to acquire that same mutex lock to continue processing. Since the initial thread still has the lock the other threads won’t be able to make any progress.

avoid this problem by letting the mutex be unlocked in the initial thread and then making signal/broadcast calls. This isn’t always possible however if you need a priority in which threads should be notified first as you will probably need to access (read) shared variables to determine which other threads should be notified via the conditional variable(s).

Question 30

need for using a while() look for the predicate check in the critical section entry code examples in the lessons?

Answer 30

while() loops in the critical_section_enter of a thread task are required because even if a thread can acquire the mutex lock it doesn’t mean the proxy variable (shared) between threads didn’t change just before the lock was acquired. Another thread could have already acquired the lock and was signalled to continue, if it was first the while loop ensures mutual exclusion.

Question 31

What’s a simple way to prevent deadlocks? Why?

Answer 31

A simple way (if the application intention will allow it) is to use only one lock/mutex. This works because as long as the mutex is used correctly with lock/unlock it will have exclusivity in any given executing thread. This is problematic in that it’s quite restrictive and limits parallelism.

A more difficult approach would be to maintain a lock order. Example: you must lock mutex A before you can lock mutex B.

Question 32

explain the relationship among kernel vs. user-level threads? Think though a general mxn scenario (as described in the Solaris papers), and in the current Linux model. What happens during scheduling, synchronization and signaling in these cases?

Answer 32

Kernel and user-level threads are essentially abstractions (via data structures). In a general many-to-many scenario kernel threads are assigned light-weight processes which are associated with one or more user-level threads. When a user-level thread is created it returns a thread ID which is not a pointer but instead an index in a table that points to the user-level thread data structure. The thread size is known at compile time which means it can be allocated in contiguous memory which helps improve locality and memory access. The OS/kernel does not know about the existence or properties of each user-level thread.

The kernel-level data structures have several data structures:

Process which tracks a list of the kernel threads, signal handlers, virtual address space, and user credentials.

Light-Weight Process (LWP) is close to a user-level thread but is visible to the kernel. It’s not needed when the specific process it is associated with is not running. keeps track of information regarding one or more more user-level threads in the process it’s associated with at any given time.

Kernel-level Thread

CPU

Special signals and system calls allow the user and kernel level threads to coordinate. Even in many-to-many scenarios user-level threads can be bound to kernel-level threads (called a “bound” thread). This is similar to the idea that a kernel may “pin” a kernel-thread to a specific CPU.

In Linux user-level threads are always bound to kernel level threads. This makes handling signals and scheduling much simpler since each thread is bound to each other.”

Question 33

Can you explain why some of the mechanisms described in the Solaris papers (for configuring the degree concurrency, for signaling, the use of LWP…) are not used or necessary in the current threads model in Linux?

Answer 33

“Linux uses 1-to-1 user to kernel threading so the extra functionality/mechanisms provided by LWP aren’t necessary. Signaling is more straightforward as well in this design in that you don’t need the additional flag described by the Solaris paper because the kernel thread that is going to send a signal to the process thread is matches 1-to-1 and might have the ability to see it’s in a critical section meaning it will wait to avoid potential deadlocks?

At the time of the Solaris paper memory was very constrained, and only a few kernel threads could be stored in physical memory at a time

“Nowadays it’s possible to store a large number of kernel-level thread data structures in physical memory without running out of space. That’s why most modern operating systems opt for a 1:1 threading model. The advantages (the kernel knows about all user-level threads and can make smarter scheduling decisions) outweigh the disadvantages (more memory usage).

Question 34

Interrupt

Answer 34

an event from some external device (external to the CPU that retrieves the interrupt) notifying the CPU that something has occurred.

could be a timer notifying that a timeout has occurred, an I/O device announcing the arrival of a network packet. Interrupts happen asynchronously

When a device interrupts the CPU it sends a unique message to the CPU. The hardware defined message is looked up in a interrupt handler table and the handler is called. The PC is moved to the address of the handler code and executed from that point. Interrupts are asynchronous.

Question 35

Signal

Answer 35

A signal is an event that comes from the software running on the OS or by the CPU hardware itself. Signals can appear both asynchronously and synchronously.

Similarly to interrupts when a signal event happens the OS signals a process (instead of the device interrupting the CPU). The process then has signal specific handlers in the signal handler table based on the OS defined signals there can also be default OS handlers for signals if they aren’t specified by the individual process.
Similarly to interrupts when a signal event happens the OS signals a process (instead of the device interrupting the CPU). The process then has signal specific handlers in the signal handler table based on the OS defined signals there can also be default OS handlers for signals if they aren’t specified by the individual process.”

Question 36

Can each process configure their own signal handler? Can each thread have their own signal handler?

Answer 36

Each process can handle their own signal as the signal handler table is process specific. Threads cannot set their own signal handler, only their signal mask.

A KLT can call a wrapper routine that has access to all threads running in the process. It can find a ULT that can handle the signal handler even if the KLT signal it originated from is running a ULT that doesn’t handle that signal.

Question 37

What’s the potential issue if an interrupt or signal handler needs to lock a mutex? What’s the workaround described in the Solaris papers?

Answer 37

it will cause a deadlock.

threads library sets/clears a special flag in the threads structure whenever it enters/exists a critical section. This flag indicates all signals should be masked while the thread is in a critical section. (Implementing Lightweight Threads, D. Stein, D. Shah, “Signal Safe Critical Sections” on Page 8).

Alternatively, the OS can detect that the handler contains a lock request and run it in a separate thread to prevent the risk of deadlock.”

Question 38

Contrast the pros-and-cons of a multithreaded (MT) and multiprocess (MP) implementation of a webserver, as described in the Flash paper.

Answer 38

“A MP implementation of a simple webserver has one main benefit and that is it’s simplicity.
downsides :
requires a lot of context switching (as certain parts of the process require longer tasks like I/O),
each process has it’s own address space which can be good because synchronization is less important, but it requires a larger memory footprint the more requests you want to be able to handle. T
he separate address spaces also prevent the processes from sharing a cache.

A MT implementation requires that the operating system supports kernel threads.
Pros:
Shared address space for a smaller memory footprint and cheaper context switches.
Cons:
This implementation is not as simple though and requires more complicated programming. It also requires synchronization with HTTP requests coming in to the server.”

Question 39

What are the benefits of the event-based model described in the Flash paper over MT and MP? What are the limitations?

Answer 39

An event-based model is essentially a state machine. It’s a looping Event Dispatcher which based on incoming notifications/events calls specific event handlers to handle each process of an HTTP request. The dispatcher allows handlers to execute to completion, if handlers need to block the dispatcher will initiate the blocking operating and continue looping for additional events from HTTP requests.

The largest benefit of an event-based model:
no context-switches and the entire process happens in the same address space with no synchronization required.
no risk of context switches being needed to hide latency (t_idle > 2 * t_ctx_switch). In the case when there is more than one CPU the event-based model still works because multiple event-based processes can be running on each CPU each handling multiple requests.

limitations:
cache pollution (each event handler may require certain things to be loaded but not others)/loss of localities. blocking I/O events can cause the entire model to block."

Question 40

Describe AMPED MODEL

Answer 40

An AMPED model is an improvement on the SPED model.

makes use of helpers that directly deal with the blocking I/O operations which allows the main dispatcher to continue to pick up requests and serve them to handlers.
helpers communicate directly with the dispatcher via pipes.
helpers are processes themselves which handle the blocking operations.

Question 41

How do you think an AMTED version of Flash would compare to the AMPED version of Flash?

Answer 41

“The AMTED model is similar to the AMPED model with the added benefit that the helpers can be threads instead of processes. This can be useful if you have a kernel that supports threading as well;

however, it is necessarily more complicated to program than an AMPED implementation for the same reason threads are more complicated than processes.

AMTED model would probably be more efficient than an AMPED model because switching between threads is less costly than switching between processes.

Question 42

There are several sets of experimental results from the Flash paper discussed in the lesson. Do you understand the purpose of each set of experiments (what was the question they wanted to answer)? Do you understand why the experiment was structured in a particular why (why they chose the variables to be varied, the workload parameters, the measured metric…).

Answer 42

reread

Question 43

If you ran your server from the class project for two different traces: (i) many requests for a single file, and (ii) many random requests across a very large pool of very large files, what do you think would happen as you add more threads to your server? Can you sketch a hypothetical graph?

Answer 43

“Many requests for single file

If all the requests are for a single file you won’t see a lot of improvement from multithreading. The file will be stored in memory, so each thread will have almost zero idle time, hence there’s no benefit to preempting one thread to schedule another. The only reason you would multithread in this case would be if you had multiple processors to work with, and then you would only need as many threads as there are processors.

Remember that stopping one thread’s execution to run another only makes sense if the first thread has to wait - i.e. if t_idle > 2 * t_context_switch

Many random requests across a very pool of very large files

“This is where you would see dramatic benefits from multithreading, compared to a single-threaded implementation. If the cache is cold, threads will sit idle while waiting to retrieve a file from disk. During this time another thread can execute, effectively ““hiding”” the latency of the file I/O.

Question 44

How is a new process created?

Answer 44

Via fork
If we want to create a process that is an exact replica of the calling process

Via fork followed by exec
If we want to create a process that is not an exact replica of the calling process

Via fork or fork followed by exec
Either of the above two options

Question 45

benefit of multithreading on 1 CPU

Answer 45

hide the latency associated with code that blocks processing (such as a disk I/O request).

Question 46

“A shared calendar supports three types of operations for reservations:
read
cancel
enter

Requests for cancellations should have priority above reads, who in turn have priority over new updates. In pseudocode, write the critical section enter/exit code for the read operation.”

Answer 46

int curr_reader
int curr_canceller
int curr_writer
int waiting_canceller
int waiting_reader
int waiting_writer
condition cancel_cond
condition read_cond
condition write_cond
mutex c_lock

lock(c_lock)
waiting_reader += 1
while (waiting_canceller > 0 || curr_canceller > 0 || curr_writer > 0) {
    wait(c_lock, read_cond)
}
waiting_reader -= 1
curr_reader += 1
unlock(c_lock)

read(calendar)

lock(c_lock)
curr_reader -=1
if (waiting_canceller > 0) {
   signal(cancel_cond)
} else if (waiting_reader > 0) {
    broadcast(read_cond)
} else if (waiting_writer > 0) {
    signal(write_cond)
}
unlock(c_lock)

Question 47

If the kernel cannot see user-level signal masks, then how is a signal delivered to a user-level thread (where the signal can be handled)?

Answer 47

all signals are intercepted by a user-level threading library handler, and the user-level threading library installs a handler. This handler determines which user-level thread, if any, the signal be delivered to, and then it takes the appropriate steps to deliver the signal.

If all user-level threads have the signal mask disabled and the kernel-level signal mask is updated, then and the signal remains pending to the process.

Question 48

Process elements

Answer 48

list of kernal level threads
virtual address space
user credentials
signal handlers

Question 49

LWP elements

Answer 49

User level registers
system call args
resource usage info
signal mask
similar to ULT but visible to kernal , not needed when process not running

Question 50

Kernel-threads - elements

Answer 50

kernal level registers
stack pointer
scheduling info
pointers to associated LWP process
information needed even when process not running, not swappable

Question 51

CPU - data strucute elements

Answer 51

current thread
list of kernal -level threads
dispatching and interrupt handling information
on SPARC dedicated register == current thread

Question 52

An image web server has three stages with average execution times as follows:

Stage 1: read and parse request (10ms)
Stage 2: read and process image (30ms)
Stage 3: send image (20ms)

You have been asked to build a multi-threaded implementation of this server using the pipeline model. Using a pipeline model, answer the following questions:

How many threads will you allocate to each pipeline stage?
What is the expected execution time for 100 requests (in sec)?
What is the average throughput of this system (in req/sec)? Assume there are infinite processing resources (CPU’s, memory, etc.).”

Answer 52

“Threads should be allocated as follows:
Stage 1 should have 1 thread
This 1 thread will parse a new request every 10ms
Stage 2 should have 3 threads
The requests parsed by Stage 1 get passed to the threads in Stage 2. Each thread picks up a request and needs 30ms to process the image. Hence, we need 3 threads in order to pick up a new request as soon as Stage 1 passes it.
Stage 3 should have 2 threads.
This is because Stage 2 will process an image and pass a request every 10ms (once the pipeline is filled). In this way, each Stage 3 thread will pick up a request and send an image in 20ms. Once the pipeline is filled, Stage 3 will be able to pick up a request and send the image every 10ms.
The first request will take 60ms. The last stage will continue delivering the remaining 99 requests at 10ms intervals. So, the total is 60 + (99 * 10ms) = 1050ms = 1.05s
100 req / 1.05 sec = 95.2 req/s
Relevant Sections
P2L2: Threads and Concurrency
Pipeline Pattern
Multithreading Patterns Quiz”