Assignment 2 - Computer Science 314: Operating Systems

Define short-term scheduler and long-term scheduler, and explain the main differences between them. (6 marks)
- long-term scheduler: selects processes from the job pool and loads them into memory for execution
- short-term scheduler: select from among the processes that are ready to execute and allocates the CPU to one of them.
The primary distinction between these two schedulers lies in frequency of execution. The short-term scheduler must select a new process for the CPU frequently. A process may execute for only a few milliseconds before waiting for an I/O request. Often, the short-term scheduler executes at least once every 100 milliseconds. Because of the short time between executions, the short-term scheduler must be fast.

The long term scheduler executes much less frequently; minutes may separate the creation of one new process and the next. The long-term scheduler controls the degree of multiprogramming (the number of processes in memory). If the degree of multiprogramming is stable, then the average rate of process creation must be equal to the average departure rate of processes leaving the system.
Explain the concept of a context switch. (6 marks)

When an interrupt occurs, the system needs to save the current context of the process running on the CPU so that it can restore that context when its processing is done, essentially suspending the process and then resuming it.

Switching the CPU to another process requires performing a state save of the current process and a state restore of a different process. This task is known as a context switch. When a context switch occurs, the kernel saves the context of the old process in its PCB and loads the saved context of the new process scheduled to run. Context-switch time is pure overhead, because the system does no useful work while switching. Its speed varies from machine to machine, depending on the memory speed, the number of registers that must be copied, and the existence of special instructions (such as a single instruction to load or store all registers).
Explain the terms at most once and exactly once, and indicate how these terms relate to remote procedure calls. (6 marks)

The remote procedure call was designed as a way to abstract the procedure-call mechanism for use between systems with network connections. Processes are executing on separate systems. The semantics of RPCs allow a client to invoke a procedure on a remote host as it would invoke a procedure locally. Making an remote procedure call can be an expensive operation. RPCs can fail or be duplicated and executed more than once, as a result of common network errors.
- at most once: The client can send a message one or more times and be assured that it only executes once.
- exactly once: The client must resend each RPC call periodically until it receives the ACK for that call.
Identify and briefly explain each of the four major categories of benefits of multithreaded programming. (6 marks)

Benefits:
- Responsiveness: Multithreading an interactive application may allow a program to continue running even if part of it is blocked or is performing a lengthy operation, thereby increasing responsiveness to the user.
- Resource sharing: Processes may only share resources through techniques such as shared memory or message passing. Such techniques must be explicitly arranged by the programmer. However, thread share the memory and the resources of the process to which they belong by default.
- Economy: Allocating memory and resources for process creation is costly. Because threads share resources of the process to which they belong, it is more economical to create and context-switch threads. In general it is more time consuming to create an manage processes than threads.
- Scalability: The benefits of multithreading can be greatly increased in a multiprocessor architecture, where threads may be running in parallel on different processors.
1. Briefly describe the benefits and challenges for multithreaded programming that are presented by multicore systems. (8 marks)
Challenges:
- Dividing activities: This involves examining applications to find areas that can be divided into separate, concurrent tasks and thus can run in parallel on individual cores.
- Balance: While identifying tasks that can run in parallel, programmers must also ensure that the tasks perform equal work of equal value. In some instances, a certain task may not contribute as much value to the overall process as other tasks; using a separate execution core to run that task may not be worth the cost.
- Data splitting: Just as applications are divided into separate tasks, the data accessed and manipulated by the tasks must be divided to run on separate cores.
- Data dependency: The data accessed by the tasks must be examined for dependencies between two or more tasks. In instances where one task depends on data from another, programmers must ensure that the execution of the tasks is synchronized to accommodate the data dependency.
- Testing and debugging: When a program is running in parallel on multiple cores, there are many different execution paths. Testing and debugging such concurrent programs is inherently more difficult than testing and debugging single-threaded applications.
Define coarse-grained multithreading and fine-grained multithreading, and explain their differences. (6 marks)
- coarse-grained multithreading: a thread executes on a processor until a long-latency event such as a memory stall occurs.
- fine-grained multithreading: switches between threads at a much finer level of granularity - typically at the boundary of an instruction cycle.
Explain process starvation and how aging can be used to prevent it. (6 marks)

A major problem with priority scheduling algorithms is indefinite blocking, or starvation. A process that is ready to run but waiting for the CPU can be considered blocked. A priority scheduling algorithm can leave some low-priority processes waiting indefinitely. In a heavily loaded computer system, a steady stream of higher-priority processes can prevent a low-priority process from ever getting the CPU. Generally one of two things will happen. Either the process will eventually be run or the computer system will eventually crash and lose all unfinished low-priority processes.

A solution to the problem is aging. Aging is a technique of gradually increasing the priority of processes that wait in the system for a long time. For example, if priorities range from 127 (low) to 0 (high), we could increase the priority of a waiting process by 1 every 15 minutes. Eventually, even a process with an initial priority of 127 would have the highest priority in the system and would be executed.
How does the dispatcher determine the order of thread execution in Windows? (6 marks)

Microsoft Windows systems often have no long-term scheduler but simply put every new process in memory for the short-term scheduler. The stability of these systems depends either on a physical limitation or on the self-adjusting nature of human users.
Define critical section, and explain two general approaches for handling critical sections in operating systems. (8 marks)

Each process has a segment of code, called a critical section, in which the process may be changing common variables, updating a table, writing a file, and so on.

The important feature of the system is that, when one process is executing in its critical section, no other process is to be allowed to execute in its critical section. That is, no two processes are executing in their critical sections at the same time.

The critical-section problem is to design a protocol that the processes can use to cooperate. Each process must request permission to enter its critical section. The section of code implementing this request is the entry section. The critical section may be followed by an exit section. The remaining code is the remainder section.

The general structure is:
```
  do {
    lock(something) {
      //critical section
    }
    // remainder section
  } while(1);
```
A solution to the critical-section problem must satisfy the following three requirements:
- Mutual exclusion: if process Pi is executing in its critical section, then no other processes can be executing in their critical sections.
- Progress: If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in deciding which will enter its critical section next, and this selection cannot be postponed indefinitely.
- Bounded waiting: There exists a bound, or limit, on the # of times that other processes are allowed to enter their critical section and before that request is granted.
Describe the dining-philosophers problem, and explain how it relates to operating systems. (6 marks)

Five philosophers spend their lives thinking and eating. The philosophers share a circular table surrounded by five chairs, each belonging to one philosopher. In the center of the table is a bowl of rice, and the table is laid with five single chopsticks. When a philosopher thinks, she does not interact with her colleagues. From time to time, a philosopher gets hungry and tries to pick up the two chopsticks that are closest to her. A philosopher may pick up only one chopstick at a time. Obviously, she cannot pick up a chopstick that is already in the hand of a neighbour. When a hungry philosopher has both her chopsticks at the same time, she eats without releasing her chopsticks. When she is finished eating, she puts down both of her chopsticks and starts thinking again.

This is considered a classic synchronization problem because it is an example of a large class of concurrency-control problems. It is a simple representation of the need to allocate several resources among several processes in a deadlock-free and starvation-free manner.

This relates to operating systems because pick up a chopstick is like entering a critical-section in a process. It is also similar to how the operating system scheduled work to be done and which process gets to execute next. Processes sometimes need to access resources (chopsticks) and they need to be able to do this in a safe way without contention (sharing a chopstick).
Define the two-phase locking protocol. (6 marks)

Locks are applied and removed in two phases:
- Expanding/Growing phase: locks are acquired and no locks are released.
- Shrinking phase: locks are released and no new locks are taken.
Describe how an adaptive mutex functions. (6 marks)

An adaptive mutex protects access to every critical data item. On a multiprocessor system, an adaptive mutex starts as a standard semaphore implemented as a spinlock. If the data are locked and therefore already in use, the adaptive mutex does on of two things. If the lock is held by a thread that is currently running on another CPU, the thread spins while waiting for the lock to become available, because the thread holding the lock is likely to finish soon. If the thread holding the lock is not currently in run state, the thread blocks, going to sleep until it is awakened by the release of the lock. It is put to sleep so that it will not spin while waiting, since the lock will not be freed very soon.
Describe a scenario in which the use of a reader-writer lock is more appropriate than using another synchronization tool, such as a semaphore. (6 marks)

Reader-writer locks are most useful in the following situations:
- In applications where it is easy to identify which processes only read shared data and which processes only write shared data.
- In applications that have more readers than writers. This is because reader-writer locks generally require more overhead to establish than semaphores or mutual-exclusion locks. The increased concurrency of allowing multiple readers compensates for the overhead involved in setting up the reader writer lock.
What is the difference between deadlock prevention and deadlock avoidance? (6 marks)

Deadlock prevention provides a set of methods for ensuring that at least one of the necessary condition cannot hold. These methods provide deadlocks by constraining how requests for resources can be made.
- Mutual exclusion: At least one resource must be held in a nonsharable mode.
- Hold and wait: A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.
- No preemption: Resources cannot be preempted; that is, a resource can be released only voluntarily by the process holding it, after that process has completed its task.
- Circular wait: A set {P0, P1,…,Pn} of waiting processes must exist such that P0 is waiting for resource held by P1, P1 is waiting for a resource held by P2,…,Pn-1 is waiting for a resource held by Pn, and Pn is waiting for ar resource held by P0.
Deadlock avoidance requires the operating system be given in advance additional information concerning which resources a process will request and use during its lifetime. With additional knowledge, it can decide for each request whether or not the process should wait. To decide whether the current request can be satisfied or must be delayed, the system must consider the resources currently available, the resources currently allocated to each process, and the future requests and releases of each process.
Describe a wait-for graph, and explain how it detects deadlock. (6 marks)

A system resource-allocation graph consists of a set of vertices V and a set of edges E. When process Pi requests an instance of resource type Rj, a request edge is inserted in the resource-allocation graph. When this request can be fulfilled, the request edge is instantaneously transformed to an assignment edge. When the process no longer needs access to the resource, it releases the resource; as a result, the assignment edge is deleted.

If the graph contains no cycles, then no process in the system is deadlocked. If the graph does contain a cycle, then a deadlock may exist.
Describe how a safe state ensures that deadlock will be avoided. (6 marks)

A state is safe if the system can allocate resources to each process (up to its maximum) in some order and still avoid a deadlock. A system is in a safe state only if there exists a safe sequence. A sequence of processes is a safe sequence when each resources that each process needs to request can be satisfied by the currently available resources that each process needs. If this cannot be satisfied then the system state is said to be unsafe.

Assignment 2 - Computer Science 314: Operating Systems

Sources