W2

Question 1

What is parallelism? When it can 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 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:

Increase concurrency level with better performance

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 schedule directly by the operating system kernel

Question 10

What are the four multithreading mapping models?

Answer 10

Many-to-one Model

One-to-one Model

Many-to-many Model

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

Nr 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 bounedd by the size of the pool

Question 20

What are some common processor scheduling algorithms?

Answer 20

First-Come First-Served (FCFS)

Shortest-Job-First (SJF)

Round Robin (RR)

Priority Scheduling - Rate Monotonic (RM), Deadline Monotonic (DM), Earliest Deadline First (EDF)

Multilevel Queue

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. Timers used to determine the necessity of context switches.

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 arbitrartion rule?

Answer 30

Tasks are schedule 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 schedule 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? Arbitrartion 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 executed 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 task with 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? Arbitrartion function?

Answer 34

Processes are often periodic, i.e., activated every period T. RM priorities the processes with the shortest period T. Preemptive Chronological/Random

Question 35

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

Answer 35

Prioritises 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 , e.g.,

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 situtation in which correctness depends on the execution order of concurrenct 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. Abscence 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 sysstem cannot make use of the different processors simultaneously, as it see only a single process.

Question 58

Consider a multiprocessor system and a multithreaded program written using the many-to-many threading model. Let the number of user-level threads in the program be more than the number of processors in the system. 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