part2

Question 1

What is parallelism? When can it take place?

Answer 1

The simultaneous execution of multiple processes or threads.

When there exist multiple processors or cores.

Question 2

What is concurrency? How does it differ from parallelism? Can concurrency take place on a single-core processor?

Answer 2

The ability of an operating system to manage multiple processes at the same time, allowing them to make progress independently.

Processes are not executed simultaneously, but rather multiple tasks are dealt with at once. Yes, as only one process is actually being executed at any one time.

Question 3

What are three disadvantages of processes?

Answer 3

1. Creation overhead, e.g., in terms of memory space.
2. Complex inter-process communication.
3. Process-switching overhead (mode + context switch, including save/restore contexts of execution).

Question 4

What is the difference between processes and threads? Definition, Ownership, Address Space, Info.

Answer 4

Process is an independent program in execution with its own memory space. Thread is the smallest unit of execution within a process.

Processes define ownership on resources, while threads may share access to the same variables, code, or files. All threads operate in their process’ address space, while different processes have different address spaces. Processes have their context of execution saved in a PCB, while threads have an associated executed state which is the PCB extended with thread info.

Question 5

What additional info does a thread’s associated executed state have in addition to the PCB?

Answer 5

Program counter, stack counter, return addresses of function calls, values of processor registers.

Question 6

Why do threads operate faster than processors?

Answer 6

Thread creation and termination is much faster as no memory address space copy is needed.

Context switching between threads of same process is much faster, as no need to switch whole address space, only swap CPU registers content. Communication between threads is faster and more at programmer’s hand than between processes.

Question 7

What are some reasons to introduce threads? What is their primary downside?

Answer 7

Reasons:

1. Increase concurrency level with better performance.
2. Use natural concurrency within a program.

Downside: No protection against other threads in the same process (risk of faults, memory sharing).

Question 8

What are user threads?

Answer 8

Threads managed by a user-level library without kernel intervention, with the OS unaware of these threads.

Question 9

What are kernel threads?

Answer 9

Threads managed and scheduled directly by the operating system kernel.

Question 10

What are the four multithreading mapping models?

Answer 10

1. Many-to-one Model.
2. One-to-one Model.
3. Many-to-many Model.
4. Two-level Model.

Question 11

What is the many-to-one multithreading mapping model?

Answer 11

Multiple user threads are created and managed by a user-level thread library.

All these threads are mapped to a single kernel thread. Kernel treats the entire process as a single thread, regardless of the amount of user threads. Implemented entirely in user space.

Question 12

Advantages of many-to-one multithreading mapping model? Disadvantages?

Answer 12

Adv: No need for kernel involvement, fast and easy to deploy.

Disadv: Only one user accesses kernel at a given time; thus, multiple threads cannot run in parallel on multiple processors; blocking system call from one user thread blocks all user threads of the process.

Question 13

What is the one-to-one multithreading model?

Answer 13

Each user-level thread maps to a kernel thread.

Kernel fully aware of all threads in process. Threads managed and scheduled by OS.

Question 14

Advantages of one-to-one multithreading model? Disadvantages?

Answer 14

Adv: Allows for concurrency between all threads.

Disadv: All threads managed by kernel, with negative impacts on performance in case of many user threads.

Question 15

What is the many-to-many model?

Answer 15

Limited number of kernel threads.

Multiple user threads mapped to a pool of kernel threads. User-level thread library schedules user threads onto available kernel threads, and kernel schedules kernel threads on the CPU.

Question 16

Advantages of many-to-many multithreading model? Disadvantages? What is the concurrency level limited by in this model?

Answer 16

Advantages: Concurrency, bounded performance cost for kernel.

Disadvantage: More complex to implement. Number of kernel threads.

Question 17

What is the two-level multithreading model?

Answer 17

Maps multiple user threads to a smaller number of kernel threads (like in many-to-many model).

Certain user threads can also be bound directly to kernel threads (like in one-to-one model).

Question 18

How does thread switching as a kernel activity? How about as handled by user-level thread libraries?

Answer 18

1. Kernel maintains execution state of thread, works similar to process switching.

2. Library maintains execution state of threads, must obtain control in order to switch threads; responsibility of programmer to call library to yield execution.

Question 19

What are thread pools? What are their advantages?

Answer 19

A collection of pre-initialised threads that can be reused to execute tasks, avoiding the overhead of creating and destroying threads repeatedly.

Adv: Slightly faster to service a request with an existing thread than creating a new one; allows number of user threads in an application to be bounded by the size of the pool.

Question 20

What are some common processor scheduling algorithms?

Answer 20

1. First-Come First-Served (FCFS).
2. Shortest-Job-First (SJF).
3. Round Robin (RR).
4. Priority Scheduling - Rate Monotonic (RM), Deadline Monotonic (DM), Earliest Deadline First (EDF).
5. Multilevel Queue.
6. Multilevel Feedback Queue.

Question 21

What does the decision mode define?

Answer 21

When scheduling decisions are taken.

Question 22

Preemptive vs Non-Preemptive Scheduling:

Answer 22

In preemptive scheduling, the OS can interrupt a running process to allocate CPU time to another process.

In non-preemptive scheduling, once a process starts executing, it runs until it completes or voluntarily relinquishes control of the CPU.

Question 23

Time-Based vs Event-Based Scheduling:

Answer 23

In time-based scheduling, scheduling decisions are made based on a regular time slice or a clock interrupt.

In event-based scheduling, decisions are made in response to specific events rather than fixed time intervals, such as the arrival of new processes, completion of I/O operations, etc.

Question 24

What is the priority function?

Answer 24

The function defining which ready tasks are chosen for execution next.

Question 25

What is the arbitration rule?

Answer 25

Breaks ties between tasks.

Question 26

How is the waiting time defined?

Answer 26

Total amount of time a process spends in the ready queue, waiting for CPU time to be allocated, excluding the time the process is actively executing.

Question 27

How is the response time defined?

Answer 27

The amount of time that elapses between when a user initiates a request (or a process is submitted) and when the system first produces a response or starts delivering output, i.e., when the process starts being executed.

Question 28

How is the turnaround time defined?

Answer 28

The total time taken to execute a particular process, from the time it is submitted to the time it completes execution, including all waiting time, execution time, and time spent in the ready queue.

Question 29

What is throughput?

Answer 29

The number of jobs or processes that are completed per unit of time.

Question 30

What is the priority function of FCFS? Is it preemptive or non-preemptive? What is its arbitration rule?

Answer 30

Tasks are scheduled in order of their arrival.

Non-preemptive. Random choice among processes that arrive at the same time.

Question 31

What is the priority function of SJF scheduling? What is its decision mode? What is its arbitrary rule? What is it optimal with relation to? What is its preemptive version called?

Answer 31

Tasks are scheduled in terms of shortest execution time.

Non-preemptive. Chronological or random ordering. Average waiting time. Shortest-Remaining-Time-First.

Question 32

How does Round Robin Scheduling work? Arbitration Rule?

Answer 32

Each process in the ready queue is allocated a fixed time slice, i.e., a ‘quantum’.

If a process completes within its quantum, it releases the CPU voluntarily. If it does not, it is preempted, and the next process in the queue is given a turn to execute. Random arbitration.

Question 33

What is priority scheduling? What is an issue with it?

Answer 33

A priority number is associated with each task that is either assigned by the programmer or computed through a function that depends on task properties. CPU is allocated to the task with the highest priority.

Starvation, i.e., low priority processes never executing.

Question 34

What is Rate Monotonic (RM) Priority Scheduling? Is it preemptive or non-preemptive? Arbitration function?

Answer 34

Processes are often periodic, i.e., activated every period T. RM prioritizes the processes with the shortest period T.

Preemptive. Chronological/Random.

Question 35

What is Deadline Monotonic (DM) scheduling? Preemptive? Arbitration function?

Answer 35

Prioritizes the processes with the shortest relative deadline D.

Preemptive. Chronological/Random ordering.

Question 36

What is Earliest Deadline First (EDF)? Decision mode? Arbitration rule?

Answer 36

Highest priority assigned to process with shortest remaining time until its deadline.

Preemptive. Chronological/Random.

Question 37

What is multilevel queue scheduling? How is scheduling between the queues done?

Answer 37

Partitions the ready queue into various sub-queues, such as: system processes, interactive processes, interactive editing processes, batch processes, student processes.

Each queue has its own scheduling algorithm. Scheduling between queues can be done with: 1. fixed priority scheduling (where high priority queues are served first, and low priority queues last) 2. time slice, where each queue gets a certain amount of CPU time which it can schedule amongst its processes.

Question 38

What is a multilevel feedback queue? What is a multilevel feedback queue scheduler defined in terms of?

Answer 38

Instead of processes being assigned to one, fixed sub-queue, tasks can be moved across sub-queues.

1. Number of queues. 2. Scheduling algos for each queue. 3. Method used to determine when to upgrade/demote a task. 4. Method used to determine which queue a task will enter when that task needs service.

Question 39

What is a sequential task? What takes the place between the states?

Answer 39

A discrete sequence of tasks, e.g., observable in program code.

Indivisible, atomic steps/actions.

Question 40

What is the single reference rule?

Answer 40

A statement in a programming language may be regarded as atomic if at most one reference to a shared variable occurs.

Question 41

How to regard a non-atomic statement as atomic, e.g., S?

Answer 41

You write it as <S>, e.g., <x:=x+1>.</S>

Question 42

What is a trace? Does it maintain the internal execution of the individual tasks? What do the actions refer to?

Answer 42

A sequence of atomic actions, obtained by interleaving the execution of concurrent tasks.

Yes. Assignments or tests.

Question 43

What is a ‘possible trace’?

Answer 43

A trace in which all tests yield true.

Question 44

What are shared variables?

Answer 44

Variables accessible to several tasks (processes/threads).

Question 45

What is a private variable?

Answer 45

Variable accessible only to a single task.

Question 46

What is interference?

Answer 46

Disturbing others’ assumptions about the state.

Question 47

What is meant by race condition?

Answer 47

A situation in which correctness depends on the execution order of concurrent activities.

Question 48

What is synchronisation?

Answer 48

Ordering the execution, i.e., forbidding certain traces.

Question 49

What are the five requirements on synchronisation solutions? Explain each shortly.

Answer 49

1. Functional correctness - satisfying the given specification.
2. Minimal waiting - waiting only when correctness is in danger.
3. Absence of deadlocks - don’t manoeuvre the system into a state such that progress is no longer possible.
4. Absence of livelocks - livelocks occurs when two or more processes continuously change their state in response to each other without making any progress.
5. Fairness in competition: weakly, each contender should eventually be admitted to proceed; strongly, a bound on the waiting time for each contender can be placed.

Question 50

How does Peterson’s Algorithm work? Write out the structure of the algorithm.

Answer 50

Uses a shared variable t to denote the turn. Uses two booleans bY and bX to ensure minimal waiting.

void Px { while (true) { bX = true; t = Y; while(bY=true AND t!=X) { skip; } x = x+1; bX = false; }}

Question 51

What are the limitations of Peterson’s Algorithm?

Answer 51

Can synchronise only two tasks, with extensions for more tasks existing but being more complex.

Busy-wait, which wastes CPU Cycles. Does not work for single core due to busy-wait, as the process on the core that is busy waiting will never give the CPU to the other process which is required to stop the busy wait.

Question 52

What is a mutex?

Answer 52

A synchronisation primitive used to ensure that only one thread or process can access a shared resource at a time.

Question 53

What is a mutex initialised to? What are its two operations?

Answer 53

1.

lock(m): await(m>0) + m=m-1; checks if mutex is available, which is the case if m>0; m=m-1 process acquires the lock by decrementing m. unlock(m): m=m+1; releases the mutex by incrementing m, signalling that the mutex is now available for other processes to acquire.

Question 54

What are some challenges with priority scheduling when protecting shared resource access?

Answer 54

1. Blocking: a low priority task obtaining a resource, and a high priority task then waiting on it.

2. Priority Inversion: occurs when a lower-priority task holds a resource that is needed by a higher-priority task - involves the medium task, which preempts the lowest task, which means that the highest task has to wait for both to complete.

Question 55

What is a solution to priority inversion that prevents a middle-priority task to preempt the lowest priority task that has the resource? What is the name of this protocol?

Answer 55

Adjusting the priority of the task T holding the resource to the maximum of the priority of any other task that is blocked on the allocated resources of P and its own priority.

Priority Inheritance Protocol.

Question 56

Which of the following components of program state are shared across threads in a multithreaded process: register values, heap memory, global variables, stack memory?

Answer 56

Share heap memory and global variables.

Do NOT share register values and stack memory.

Question 57

Can a multithreaded solution using multiple user-level threads achieve better performance on a multiprocessor system than on a single processor system?

Answer 57

No, since the multithreaded system cannot make use of the different processors simultaneously, as it sees only a single process.

Question 58

Consider a multiprocessor system and a multithreaded program written using the many-to-many threading model. Discuss the performance implications of the following scenarios: a. The number of kernel threads allocated to the program is less than the number of processors. b. The number of kernel threads allocated to the program is equal to the number of processors. c. The number of kernel threads allocated to the program is greater than the number of processors but less than the number of user-level threads.

Answer 58

When the number of kernel threads is less than the number of processors, then some of the processors would remain idle since the scheduler maps only kernel threads to processors and not user-level threads to processors.

When the number of kernel threads is exactly equal to the number of processors, then it is possible that all of the processors might be utilized simultaneously. However, when a kernel thread blocks inside the kernel (due to a page fault or while invoking system calls), the corresponding processor would remain idle. When there are more kernel threads than processors, a blocked kernel thread could be swapped out in favor of another kernel thread that is ready to execute, thereby increasing the utilization of the multiprocessor system.

Question 59

Do processes share global variables?

Answer 59

No, they do not.

Question 60

Which is the most general scheduling algorithm?

Answer 60

Multilevel Feedback-Queue Algorithm.