Introduction to OS Flashcards

Question

What do we do or get when a cache is hot?

Answer 1

1. Most process data is in the cache so the process performance will be at its best 2. Sometimes, we must context switch when there is another prioritised process or there is a policy to timeshare the CPU.

Answer 2

When a process is created, it's in the *new* state. At this point, the operating system initializes the PCB for the process, and it moves to the *ready* state. In this state it is able to be executed, but it is not being executed. Once the process is scheduled and moved on to the CPU it is in the *running* state. If the process is then interrupted by the scheduler, it moves back the the *ready* state. If the process is running, and then makes an I/O request, it will move onto the wait queue for that I/O device and be in the *waiting* state. After the request is serviced, the process will move back to the *ready* state. If a running process exits, it moves to the *terminated* state.

Answer 3

*Running* and *ready* states

Answer 4

When a process is in a blocked state, this means that process is currently waiting for an I/O request to be fulfilled. Usually this means that the process is sitting on an I/O queue within the kernel that is associated with the device it's making the request to. Once the request is fulfilled, the process moves back to a ready state, where it can be executed, although it is not yet scheduled. The currently executing process must be preempted, and the ready process must be switched in. At this point, the process is executing on the CPU.

Answer 5

1. fork - the OS will create a new PCB for the child process. It will copy the exact same values from the parent PCB into the child PCB. Both the parent and the child will continue their execution at the instruction that's immediately after the fork. 2. exec - It will take a PCB structure created via fork, but it will not leave its values to match the parent's values. Instead, the OS will replace the child's image and load a new program. The child's PCB will point to values or describe values that describe this new program. Note that the program counter of the child will now point to the first instruction of the new program.

Answer 6

These are called root processes. Examples are sched(), init(), and pageout.

Answer 7

ZYGOTE - a daemon process which has the single purpose of launching app processes.

Answer 8

The CPU scheduler is an OS component that determines which one of the currently ready processes will be dispatched to the CPU to start running, & how long should it run for. To manage the CPU, the OS must be able to: * preempt - interrupt the executing process and save its current context * schedule - run the scheduling algorithm in order to choose on the ready processes that should be run next * dispatch - dispatch the chosen process onto the CPU and switch into its context so that the process can finally start executing

Answer 9

Useful CPU work = total processing time / total time total processing time = 2 * Tp where Tp is the amount of time to run a process total time = 2*Tp + 2*tsched Note that the longer the CPU runs a process, the less frequent it runs the scheduler

Answer 10

Consider a process had made an I/O request. - OS delivered the request and placed the process on an I/O queue that's associated with the particular device - Process is now waiting in the I/O queue. It will remain in the queue until the device completes the operations that the I/O event is complete and responds to the request. - Once the I/O request is dismissed, the process is ready to run again. Process can be placed in the ready queue or can be scheduled on the CPU.

Answer 11

1. A process which is waiting on an I/O event 2. A process which is running on the CPU but its time slice expired 3. When a new process is created via the fork call 4. A process which is waiting for an interrupt

Answer 12

1. Maintaining the ready queue 2. Deciding on when to context switch

Answer 13

1. They help transfer data and information from one address space to another. 2. They maintain the protection and isolation that operating systems are trying to enforce. 3. They provide flexibility and performance.

Answer 14

Message-passing IPC - The OS establishes a communication channel, e.g., shared buffer. Processes interact with it by writing or sending a message into that buffer, or reading or receiving a message from that shared communication channel. * Pros: OS will manage the message passing channel; has system calls in place for operations like read/write and recv/send; user doesn't need to worry about any of the details. * Cons: overhead; every piece of data that is sent between processes must first be copied from the sending process's address space into memory associated with the kernel and then into the receiving process's address space; here is user/kernel crossing for every message. Shared-memory IPC - The OS establishes a shared memory channel and then it maps it into the address space of both processes. Processes are allowed to directly read and write from this memory. * Pros: The kernel is completely uninvolved. The processes can read from and write to this memory as they would with any other memory in their address space * Cons: Without the kernel, a lot of the APIs that were taken for granted with message passing IPC may have to be re-implemented. For example, the user now has to manage all of the synchronization themselves.

Answer 15

Threads represent multiple independent execution contexts. They are part of the same virtual address space, which means they share all of the virtual to physical address mappings, as well as the code, data, and files. However, they potentially execute different instructions, access different portions of the address space, operate on different portions of the input. Each thread has a different program counter, stack pointer, stack, thread-specific registers. The PCB is more complicated as it contains all information that is shared among all the threads, as well as separate information about every single one of the execution contexts that are part of the process.

Answer 16

There are two main benefits of multithreading, namely parallelization and concurrency. Parallelization comes into effect on multi CPU systems in which separate threads can be executing at the same time on different processors. Parallelizing work allows for the work to be accomplished more quickly. Concurrency refers to the idea that the CPU can do a little bit of work on one thread, and then switch and do a little bit of work on another thread. Succinctly, concurrency refers to the idea that the execution of tasks can be interwoven with one another. The primary benefit of concurrency without parallelization - that is, concurrency on single CPU platforms - is the hiding of I/O latency. When a thread is waiting in an I/O queue, that thread is blocked: its execution cannot proceed. In a multithreaded environment, a thread scheduler can detect a blocked thread, and switch in a thread that can accomplish some work. This way, it looks as if progress is always being made (CPU utilization is high) even though one or more threads may be waiting idle for I/O to complete at any given time. Adding threads make sense if you have fewer threads than you have cores or if you are performing many I/O requests. Adding threads can lead to pure overhead otherwise. While new threads require less memory than new processes, they still do require memory. This means that threads cannot be made for free, and in fact thread creation is often quite expensive. In addition, thread synchronization can add more overhead to the system, in terms of the CPU cycles and memory that must be consumed to represent and operate synchronously.

Answer 17

1. Can share a virtual address space (T) 2. Take longer to context switch (P) 3. Have an execution context (B) 4. Usually result in hotter caches when multiple exist (T) 5. Make use of some communication mechanism (B)

Answer 18

A thread can be created (a new execution context can be created and initialized). To create a thread, we need to specify what procedure it will run, and what arguments to pass to that procedure. Once the thread has been created, it will be a separate entity from the thread that created it, and we will say at this point that the process overall is multithreaded. During the lifetime of a thread, the thread may be executing on the CPU - similar to how processes may be executing on the CPU at any point in time - or it may be waiting. Threads may wait for several different reasons. They may be waiting to be scheduled on the CPU (just like processes). They may be waiting to acquire some synchronization construct - like a mutex - or they may be waiting on some condition to become true or some signal to be received - like a condition variable. Different queues may be maintained depending on the context of the waiting. Finally, at the end of their life, threads can be joined back in to their parents. Through this join, threads can convey the result of the work they have done back to their parents. Alternatively, detachable threads cannot be joined back into their parent, so this step does not apply to them. Threads can also be zombies! A zombie thread is a thread that has completed its work, but whose data has not yet been reclaimed. A zombie thread is doing nothing but taking up space. Zombies live on death row. Every once in a while, a special reaper thread comes and cleans up these zombie threads. If a new thread is requested before a zombie thread is reaped, the allocated data structures for the zombie will be reused for the new thread.

Answer 19

- thread data structure: to distinguish a thread from a process. It should allow us to identify threads and keep track of their resource usage. - mechanisms to create and manage threads - mechanisms to allow threads to safely coordinate among each other, especially when there are certain dependencies between their execution, when these threads are executing concurrently.

Answer 20

A data race problem is when multiple threads are accessing the same data at the same time and modify it at the same time.

Answer 21

1. Mutual exclusion - only one thread at a time is allowed to perform an operation; uses mutexes 2. Waiting on other threads - specific condition before proceeding; uses condition variable

Answer 22

It is a data structure that contains all information that is specific to a thread and that can describe a thread. This inclues the thread ID, register values, program counter, stack pointer, and othe attributes.

Answer 23

Birrel proposes a fork call with two parameters, a procedure (proc argument) and args which are the arguments for the procedure. fork (proc, args)

Answer 24

join(thread) - terminate a thread. When the parent thread calls join, with the thread ID of the child thread, it will be blocked until the child completes. Join will return to the parent the result of the child's computation.

Answer 25

Mutexes are synchronization constructs that enforce the principle of mutual exclusion. Mutual exclusion is the requirement that one thread of execution never enter its critical section at the same time that another concurrent thread of execution enters its own critical section.

Answer 26

Condition variables are constructs used in conjunction with mutexes to control concurrent execution. While mutexes and mutual exclusion represent binary states - either the thread can access a shared resource or it cannot - condition variables allow for more complex states. Threads can wait on condition variables until a condition is met, and threads can signal/broadcast on condition variables when a condition is met.

Answer 27

free: resource_counter = 0 reading: resource_counter > 0 writing: resource_counter = -1 ///////////////////////////////// Multiple Readers: mutex_lock(&m); while(resource_counter== -1) wait(&cond_reader, &m); resource_counter++; mutex_unlock(&m); // read data.... mutex_lock(&m); resource_counter--; if(resource_counter== 0) signal(&cond_writer); mutex_unlock(&m); ////////////////////////////////////////// Single Writer: mutex_lock(&m); while(resource_counter != 0) wait(&cond_writer, &m); resource_counter = -1; mutex_unlock(&m); // write data.... mutex_lock(&m); resource_counter = 0; mutex_unlock(&m); signal(&cond_writer); broadcast(&cond_reader);

Answer 28

Spurious wake ups occur when a thread is woken up when the application is in a state during which it's impossible for that thread to make progress. This often occurs when one thread tries to signal/broadcast while holding a mutex. Threads associated with condition variable being signaled on will be woken up from the wait queue associated with the condition variable, but since the signaling thread holds the mutex, they will immediately be placed on the wait queue associated with acquiring the mutex. CPU cycles will be wasted. Spurious wake ups can often be avoided by placing signal/broadcast calls outside of the mutex. Note that, this cannot always happen: if a signaling call depends on some configuration of shared state, this must be checked while holding the mutex, as with any other shared state access.

Answer 29

When a condition variable is signaled on, and a thread is to be "woken up", two things occur: - The thread is removed from the wait queue - The thread reacquires the mutex The two steps are logically independent. What this means is that another thread may be given CPU time (and potentially the mutex) in between these two steps. As a result, the shared state may be updated before the waking up thread reacquires the mutex. Therefore, the thread must do another check when it actually acquires the mutex to ensure the condition it needs to proceed is still true.

Answer 30

The simplest way to prevent deadlocks is to maintain a lock order. This will prevent a cycle in the wait graph, which is necessary and sufficient for a deadlock to occur. Two threads can deadlock if they are each trying to acquire mutexes the other holds. A thread can also deadlock with itself if it tries to acquire a mutex it already holds. Enforcing a lock order can ensure that neither of these scenarios occurs.

Answer 31

In the boss-workers problem, you have one boss thread and n worker threads. For each task that enters the system, the boss dispatches the tasks that the workers consume. This is often, though not necessarily, done through a shared request queue/buffer. In this case, the boss will add items to the queue, and the workers will consume items from the queue. If you wanted to improve throughput or response time in this model, there are mainly two things you could do. First, increase the number of threads. The more you leverage concurrency, the more potential you have to increase the efficiency of your processing. That being said, dynamic thread creation is expensive, so it makes sense to just have a pool of workers up front instead of creating new threads on the fly. Increasing the size of the pool may help performance. Second, decrease the amount of work the boss has to do. Since the boss has to do some processing on every request, the throughput of the system is correlated to this processing time (throughput = 1 / boss_time_per_order). Make sure to make this is low as possible. This approach is still limited by the amount of processing power you have. After a certain number of threads, the work will become CPU-bound. Some threads will end up just having to wait their turn for computing resources. In addition, this approach lacks locality. The boss doesn't keep track of what any of the workers were doing last. It is possible that a thread is just finishing a task that is very similar to an incoming task, and therefore may be best suited to complete that task. The boss has no insight into this fact.

Answer 32

In the pipeline pattern, the execution of the task is broken down into stages. Threads are assigned to continually complete the work at once stage, receiving requests from the stage before it and passing work on to the stage after it. One of the benefits of this process is locality. Since each thread performs the same (small) task over and over again, it is more likely that the hardware cache will be hot, increasing performance. On a larger level, this pattern will be bottle necked by the stage that takes the longest to complete. One way to overcome the difference in processing needed for each stage is to allocate a different number of threads to each stage. For example, a stage that takes three times as long as another stage should have three times the amount of threads. A downside of this approach is that it is difficult to keep the pipeline balanced over time. When the input rate changes, or the resources at a given stage are exhausted, rebalancing may be required.

Answer 33

Boss/worker formula: execution time = time_to_finish_1_order * ceiling (num_orders / num_concurrent_threads) Pipeline formula: execution time = time_to_finish_first_order + (remaining_orders * time_to_finish_last_stage)

Answer 34

User level threads are associated with a user level library (like pthreads), while kernel level threads are associated with the kernel threading implementation (like NPTL). For a user thread to run, it must be associated with a kernel thread, which in turn must be scheduled on the CPU. In the one-to-one model, there is one kernel thread for every user thread. That means that when a user thread is created, a kernel thread is also created. This 1:1 model is the current situation in Linux and is supported at the kernel level by the task struct. The benefit of the approach is that the kernel understands that the process is multithreaded, and it also understands what those threads need. Since the operating system already supports threading mechanisms to manage its thread, the user libraries can benefit directly from the multithreading support available in the kernel. One downside of this approach is that is it expensive: for every operation we must go to the kernel and pay the cost of a system call. Another downside is that since we are relying on the mechanisms and policies supported by the kernel, we are limited to only those policies and mechanisms. As well, execution of our applications on different operating systems may give different results. In a so-called many-to-many scenario, there can be one or more user threads scheduled on one or more kernel threads. The kernel is aware that the process is multithreaded since it has assigned multiple kernel level threads to the process. This means that if one kernel level thread blocks on an operation, we can context switch to another, and the process as a whole can proceed. One of the downsides of this model is that is requires extra coordination between the user- and kernel-level thread managers. Signaling in a many to many scenario comes with complexities. If the kernel thread has a signal enabled but the user thread does not, the user threading library may have to send directed signals back down into the kernel to get the right user level thread to respond to the signal.

Answer 35

After splitting the PCB (kernel's PCB - virtual address mapping; kernel-level threads - stack and register pointers needed to represent execution state), the kernel's PCB is further split into: - Hard process state: includes the virtual address mapping which is relevant to all user-level threads that execute within the process - Light process state: includes the signal masks and system call arguments which is only relevant to a subset of user-level threads that are associated with a particular kernel-level thread

Answer 36

Multiple data structures have the following advantages over a single PCB structure to represent all aspects of the execution state of a process: 1. Scalability: multiple but smaller data structures versus large continuous data structure 2. Overheads: easier to share versus private for each entity 3. Performance: on context switch - save and restore what needs to change versus saving and restoring everything 4. Flexibility: update all versus user-level library only needs to update portion/subset of the state

Answer 37

1. kthread_worker 2. task_struct

Answer 38

Process - list of kernel-level threads - virtual address space - user credentials - signal handlers Light-Weight Process (LWP) - similar to user-level threads but visible to the kernel; not needed when process is not running - user level registers - system call arguments - resource usage info - signal mask Kernel-level threads - kernel-level registers - stack pointer - scheduling information - pointers to associated LWP, process, CPU structure CPU - current thread - list of kernel-level threads - dispatching and interrupt handling information

Answer 39

The mechanisms described in the Solaris paper were all mechanisms for rationing the number of threads that are created at any given point in time. Configuring the degree of concurrency implied that you couldn't just be automatically given as much as you needed. Having LWPs multiplex over kernel threads indicated that kernel threads needed to be shared. The rationing was based on real concerns about the available memory in a system at any given time. The native implementation of threads in Linux is the Native POSIX Threads Library (NPTL). This is a 1:1 model, meaning that there is a kernel level task for each user level thread. In NPTL, the kernel sees every user level thread. This is acceptable because kernel trapping has become much cheaper, so user/kernel crossings are much more affordable. Also, modern platforms have more memory - removing the constraints to keep the number of kernel threads as small as possible.

Answer 40

- pthread_setconcurrency() - 0

Answer 41

Mutexes that sometimes result in the thread to spin and other times it results in the thread to block, depending on the length of the critical sections. If the critical section is short, the thread spin on the CPU and burn a few cycles until the other thread releases the mutex. For long critical sections, the thread is properly blocked. Note that we only use adaptive mutexes on multiple CPU systems.

Answer 42

- 20 threads - max_threads

Answer 43

Interrupts are events generated externally by components other than the CPU, e.g., I/O devices, timers, other CPUs. Type of interrupt depends on the specific configuration of the physical platform and the types of devices that it has. They also appear asynchronously.

Answer 44

Signals are events triggered by the CPU and software running on it. Type of signal depends on the operating system. They appear synchronously or asynchronously.

Answer 45

- Have a unique ID depending on the hardware or operating system - Both can be masked and disabled/suspended via corresponding mask; per CPU interrupt mask, per process signal mask - If enabled, both trigger their corresponding handler. The interrupt handler is set for the entire system by the operating system; signal handlers are set on per process basis by process

Answer 46

When a user-level application tries to perform a illegal task using the hardware, the kernel is notified via an interrupt. An interrupt is handled on a per-CPU basis, and the operating system maintains an interrupt handler table, which maps interrupts by the interrupt number (INT) to handling procedures. When the interrupt occurs, the kernel jumps to the associated interrupt handler and executes that code. Which interrupts occur is a function of the platform on which you are running. How those interrupts are handled is a function of the OS on top of the physical system.

Answer 47

Each process maintains its own signal handling table, which is very similar to kernel-level interrupt handling table. Each entry contains a reference to the signal and a reference to the handling code. When a signal comes in, the process jumps to the handling code. Threads cannot have their own handler, although they can set their own signal masks to ensure that they can disable signals they don't want to receive.

Answer 48

Since handlers are executed within a thread's stack, there is the potential for a thread to deadlock with itself if it tries to lock a mutex it has already acquired. This is because the current stack frame needs the mutex that was acquired in a lower stack frame to be released. The handling routine was trying to lock a mutex that was already held by the thread that was interrupted by the handling routine. The solution is to have signal handlers execute in another thread. This way, the signal handling code can contend for a mutex like any other thread, which removes the possibility of deadlock. Since dynamic thread creation is expensive: - if the handler routine does not include locks, then execute it on the stack of the interrupted thread - if the handler routine include locks (and therefore will block), then turn it into real thread Another solution is to have threads alter their signal masks before entering and after exiting their critical sections. While this solution requires fewer SPARC instructions than creating a new thread to handle signals, mutex acquisition happens much more frequently than signals. This is another example of optimizing for the common case!

Answer 49

1. One-shot signals - If there are multiple instances of the same signal that will occur, they will be handled at least once. The handling routine must be re-enabled every single time. This demonstrates an overriding behavior. 2. Real time signals - If a signal is raised n times, then the handler is guaranteed to be called n times as well. This demonstrates a queuing behavior.

Answer 50

- terminal interrupt signal: SIGINT - high bandwidth data is available on a socket: SIGURG - background process attempting to write: SIGTTOU - file size limit exceeded: SIGXFSZ

Answer 51

Boss-worker model: Execution time = 120 * ceiling (11/5) = 120 * 3 = 360 ms Average time per order = (5*120 + 5*240 + 1*360) / 11 = 196 ms Pipeline stage model: Execution time = 120 + (10*20) = 320 ms Average time = (120 + 140 + ... 320) / 11 = 220 ms

Answer 52

The main benefits of the MP model are its simplicity. Each request is handled in a new process with its own address space: there is no need for any (explicit) synchronization code. However, this benefit comes at the cost of performance. First, the memory foot print of the MP implementation is large. Processes have discrete address spaces, which means that memory usage grows steeply with request count. As a result, there is less memory available for caching, which means that computation becomes disk-bound more quickly. As well, context switching slows down the performance of the MP implementation. Context switching between processes consumes CPU cycles, which could otherwise be spent handling requests.

Answer 53

The main benefits of the MT model, compared to the MP model are that it is more efficient. MT applications share the address space of the process they are contained in, so they are more memory efficient than MP applications. As well, this sharing allows for smaller context switches (and often leaves hotter hardware caches), which can help performance. Unfortunately, this benefit comes at the cost of complexity. MT applications require explicit synchronization code to be written (mutexes, condition variables, etc). In addition, MT applications require kernel MT support.

Answer 54

The event-based model operated primarily in one thread, which makes its memory footprint smaller than both the MT and MP model. As well, the cost of context switching was not (as) present. That being said, helper processes were involved, but their utilization was as needed: they weren't created blindly for every new request entering the system. The benefit of the smaller memory footprint was that more memory was available for the various types of caching done in the system. This meant that Flash could delay becoming disk-bound longer than the MT/MP models. Summary: - single address space - single flow of control - smaller memory requirement; compact address - no context switching (low overheads) - no synchronization Limitations of the main approach behind Flash was that not every kernel supported asynchronous I/O. As a result, Flash had to fake it in a sense, utilizing helper processes to make I/O look async. I think that the AMTED model would perform better than the AMPED model, as the MT model uses less memory than the MP model, which again allows for a bigger cache. I think the main reason for choosing process-based helpers was that kernel support for multithreading was spotty at the time of the writing of the paper; thus, a process based approach was the most portable. That being said, I think the performance differential would be on par with that between the standard MP/MT models, which is to say, not that much.

Answer 55

Event-driven model. Extra memory is only required for helper processes/threads for concurrent blocking I/O operations

Answer 56

1. Single File Test - This test was a test of "best case": to show what performance would look like across the servers when the request pattern was optimal. To achieve this, requests were made for a single file which varied in size. SPED performed better than AMPED - which performs the extra check to see if the file is in memory (not an issue here because its one file and is always going to be in memory). Both performed better than MT/MP, which were slowed by context switching overhead. (SPED > AMPED/Flash > MT/MP > Apache) 2. Owlnet Trace - This tests workloads that can primarily be served from cache, but not completely. AMPED performs slightly better than SPED here. Since some of the work is disk-bound SPED blocks where AMPED context switches. Both of these approaches are better than MT/MP models, which have more memory allocated to them (less for cache size), and still incur the overhead of context switching. 3. CS Trace - This tests workloads that become disk-bound very quickly. In this case, AMPED, and MT/MP smoke SPED. Since SPED is single-threaded, with not helpers, SPED blocks a lot when the workload is disk-bound. AMPED only has enough helper processes to keep the disk busy, so it has a smaller memory footprint and few context switching overheads than MP/MT Summary: - When data is in cache: SPED >> AMPED Flash; unnecessary test for memory presence - SPED and AMPED Flash >> MT/MP; sync & context switching overhead - When workload is disk-bound: AMPED Flash >> SPED; blocks because no async I/O - AMPED Flash >> MT/MP; more memory efficient, less context switching

Answer 57

1. Execution time 2. Throughput, e.g., bytes per second (amount of data in a given amount of time) 3. Request rate 4. CPU utilization - % of time a CPU is working to complete tasks 5. Wait time 6. Platform efficiency 7. Performance/$ 8. Performance/W 9. Percentage of SLA violations

Answer 58

Single file: Adding more threads would likely increase the throughput of the GETFILE server. Files need to be read from disk into memory before they can be served. Once a file is read into memory, it can stay in memory until its contents need to be replaced. More threads would be able to serve more concurrent requests. Random requests across a large pool of large files: Adding more threads may not have a huge impact on throughput in this scenario. Any given new request is not likely to be able to read from main memory, since the range of inputs is so wide. This means that this application would likely be disk-bound from the get-go. Increasing the number of threads allows for more concurrent requests to be processed, but each thread will likely have to pull content from disk. I would say that the graph for throughput vs threads in both cases would be logarithmically increasing, with the graph for the single file example rising much more sharply than the graph for the large pool.