deck_17769120

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?

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.

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 processes?

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.

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

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.

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.

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.

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.

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.

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.

In event-based scheduling, decisions are made in response to specific events rather than fixed time intervals.

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 and when the system first produces a response.

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.

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. ## Footnote 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. ## Footnote 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'. ## Footnote If a process completes within its quantum, it releases the CPU voluntarily.

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. ## Footnote 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 priorities the processes with the shortest period T. ## Footnote 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. ## Footnote 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. ## Footnote 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. ## Footnote Each queue has its own scheduling algorithm.

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. ## Footnote 1. Number of queues. 2. Scheduling algos for each queue.

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. ## Footnote 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. ## Footnote 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. ## Footnote 2. Minimal waiting - waiting only when correctness is in danger.

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. ## Footnote 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. ## Footnote Busy-wait, which wastes CPU Cycles.

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. ## Footnote lock(m): await(m>0) + m=m-1; unlock(m): m=m+1.

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. ## Footnote 2. Priority Inversion: occurs when a lower-priority task holds a resource that is needed by a higher-priority task.

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. ## Footnote 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. ## Footnote 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.

Answer 58

When the number of kernel threads is less than the number of processors, then some of the processors would remain idle. ## Footnote 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.

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.