Week 2

Question 1

Process creation

Answer 1

A parent will create a child process and will then have control over child. E.g. Unix kernel finds init process, starts system boot, daemon processes, and terminal login processes.

Question 2

Process Termination

Answer 2

Process asks OS to system exit or parent terminates child process. The processes resources are then removed.

Question 3

Cooperating processes

Answer 3

Dependent upon other processes and have to communicate accordingly

Question 4

Producer - Consumer

Answer 4

Producer generates information that will be consumed by the consumer. Process can have a bounded or unbounded buffer.

Question 5

Interprocess Communication

Answer 5

Mechanism for processes to communicate and synchronize (direct and indirect)

Question 6

Direct Communication

Answer 6

Processes explicitly identifies who is sending and where it is being sent. Addressing can be asymmetric, meaning they can receive from anyone by must specify who they send to

Question 7

Mailboxes

Answer 7

Processes share a mailbox (port), which is where messages will be sent. Disadvantages: Sharing mailbox isn’t efficient.

Question 8

Blocking synchronization

Answer 8

Synchronous message sender. Both processes must wait until the exchange is made.

Question 9

Rendez-vous

Answer 9

Both sender and receiver are blocking. Blocker is zero capacity.

Question 10

Non-Blocking synchronization

Answer 10

Sender can drop into buffer until receiver is ready and vice versa.

Question 11

Bounded vs unbounded buffer

Answer 11

Bounded buffer may need to wait or abandon messages. Unbounded is very resource heavy.

Question 12

Thread

Answer 12

Lightweight process, essentially one part of an existing process. Contains a unique stack, thread ID, and registers but shares code, memory, files, and other resources with other threads.

Question 13

Benefits of threads

Answer 13

Less overhead on context switching. Can run on multiple CPUs. Helps responsiveness, resource sharing, faster thread creation.

Question 14

What happen when a thread terminates

Answer 14

Rejoins main thread

Question 15

Examples of threads

Answer 15

Games (NPCs), Web browser (tabs)

Question 16

User Threads

Answer 16

Threads are implemented by a library. OS is not thread aware. Cooperative multitasking means there’s no interrupt when switching threads. Earliest version of threads. Process schedules threads on CPU.

Question 17

User Thread advantages

Answer 17

Fast, don’t require system calls to switch, simple scheduling

Question 17

User thread Disadvantages

Answer 17

No multi-processor support. When a thread is blocked, all threads are blocked.

Question 17

Setup of user kernel

Answer 17

File and devices are manage by OS. Thread control blocks are put in data segment because OS isn’t aware of them. Stack pointers are allocated in heap or in unallocated space.

Question 17

Kernel thread

Answer 17

Os aware thread. Os does scheduling for this thread. System calls are required to create new threads.

Question 17

Kernel thread advantages

Answer 17

Can run a process on multiple cores. OS will block only singular threads.

Question 18

Kernel thread disadvantages

Answer 18

Not as fast, more resource intensive

Question 19

Kernel thread implementation

Answer 19

OS assigns stack to unallocated space automatically. Thread control blocks stored in memory.

Question 20

Many-to-one implementation

Answer 20

User level thread. OS sees one process but programmer sees multiple threads.

Question 21

One-to-One

Answer 21

Kernel threads. OS sees every thread that exists.

Question 22

Thread pool

Answer 22

Pool of threads OS is aware of. At the user level, there are more threads than supported. Library will manage which threads are mapped.

Question 23

Thread Pool Pattern

Answer 23

Taking blocks like loops and putting each independent iteration into a thread.

Question 24

Creating kernel threads

Answer 24

Fork and Clone

Question 25

Fork

Answer 25

System call to start another process. Returns the Child PID to the parent and 0 to the child. Makes a deep copy of the PCB and returns a separate copy. Two independent shells are now running.

Question 26

Clone

Answer 26

System to start another process. Makes a shallow copy of the current running thread. New PCB but both point to same data, file information, etc.

Question 27

Java threads

Answer 27

Part of the language. Extends the thread class and implements the runnable interface.

Question 28

Race condition

Answer 28

Final value of a shared resource depending on the order in which code executes.

Question 29

Critical section

Answer 29

Block of code where a shared resource is changed or manipulated.

Question 30

Breakdown of critical section

Answer 30

Entry: Acquire access to the shared resource. Critical Section: Modify shared variable. Exit: exit the critical section. Remainder: Code post critical section.

Question 31

Criteria for critical section

Answer 31

Mutual exclusion, progress, bounded wait

Question 32

Mutual exclusion

Answer 32

One process in a critical section at a time

Question 33

Progress

Answer 33

- If there is no process in cs, a waiting process is let in. Essential that you can't just lock out and have no one in the critical section

Question 34

Bounded wait

Answer 34

Equitable sharing between processes

Question 35

Peterson's model

Answer 35

Model only works for two processes and contains a shared variable initialized at zero. While loop until turn becomes the appropriate number, enters the cs, then makes turn the second number and exits.

Question 36

CS criteria and Peterson's model

Answer 36

Satisfies mutual exclusion and bounded wait. Doesn't satisfy progress as P0 hitting an infinite loop in the remainder will halt progress.

Question 37

Peterson's model 2

Answer 37

Model still works for 2 processes and contains a shared variable Boolean array called flag. Set your flag to true when entering code. Infinite while loop while the other program's flag is true. Enter cs once its false. Set appropriate flag to false and enter remainder section.

Question 38

Issue with Peterson's model 2

Answer 38

If an interrupt occurs during entry section both sections can be set to true and no one can enter cs, failing progress.

Question 39

Petersons complete algorithm

Answer 39

Model works with 2 processes and contains a shared integer set to zero and a Boolean array set to false. Infinite wait while other processes flag is true and turn is set to other process. Turn will break the tie if both flags are true.

Question 40

Test and Set

Answer 40

Guaranteed by hardware to be atomic. Lock set to false. Processes will swap their true value with the lock value until they receive false in their register. At this time they have the key and can be let into the critical section. Once done, they will set the lock back to false.

Question 41

Atomic instruction

Answer 41

Cannot be interrupted

Question 42

Test and set cs constraints

Answer 42

Satisfies progress and mutual exclusion. Doesn't satisfy bounded wait because the same process can get the lock over and over.

Question 43

Test and set with bounded wait

Answer 43

Same concept as test and set. When exiting critical section, we look to the next process in the queues and give them the key. If there's no one in line, set lock back to false.

Question 44

Problems with test and set bounded wait

Answer 44

If an interrupt occurs when checking wait queue and process that was already checked goes to wait queue. Sol: Keep going until a waiting process is found or get to yourself and release the lock.

Question 45

Busy waiting

Answer 45

Cycles of processes on wait

Question 46

Semaphore solution

Answer 46

Integer value and two atomic operations: wait and signal. If semaphore is greater than 1, you can enter the critical section. Once semaphore hits zero, the process gets put to sleep. When the process leaves the critical section, it increments the semaphore.

Question 47

Semaphore with bounded wait

Answer 47

semaphore is contained within struct that has a queue. During wait and signal, the program will put or remove processes from the wait queue in the order they were added.