Week 2 Flashcards
Process creation
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.
Process Termination
Process asks OS to system exit or parent terminates child process. The processes resources are then removed.
Cooperating processes
Dependent upon other processes and have to communicate accordingly
Producer - Consumer
Producer generates information that will be consumed by the consumer. Process can have a bounded or unbounded buffer.
Interprocess Communication
Mechanism for processes to communicate and synchronize (direct and indirect)
Direct Communication
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
Mailboxes
Processes share a mailbox (port), which is where messages will be sent. Disadvantages: Sharing mailbox isn’t efficient.
Blocking synchronization
Synchronous message sender. Both processes must wait until the exchange is made.
Rendez-vous
Both sender and receiver are blocking. Blocker is zero capacity.
Non-Blocking synchronization
Sender can drop into buffer until receiver is ready and vice versa.
Bounded vs unbounded buffer
Bounded buffer may need to wait or abandon messages. Unbounded is very resource heavy.
Thread
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.
Benefits of threads
Less overhead on context switching. Can run on multiple CPUs. Helps responsiveness, resource sharing, faster thread creation.
What happen when a thread terminates
Rejoins main thread
Examples of threads
Games (NPCs), Web browser (tabs)
User Threads
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.
User Thread advantages
Fast, don’t require system calls to switch, simple scheduling
User thread Disadvantages
No multi-processor support. When a thread is blocked, all threads are blocked.
Setup of user kernel
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.
Kernel thread
Os aware thread. Os does scheduling for this thread. System calls are required to create new threads.
Kernel thread advantages
Can run a process on multiple cores. OS will block only singular threads.
Kernel thread disadvantages
Not as fast, more resource intensive
Kernel thread implementation
OS assigns stack to unallocated space automatically. Thread control blocks stored in memory.
Many-to-one implementation
User level thread. OS sees one process but programmer sees multiple threads.
One-to-One
Kernel threads. OS sees every thread that exists.
Thread pool
Pool of threads OS is aware of. At the user level, there are more threads than supported. Library will manage which threads are mapped.
Thread Pool Pattern
Taking blocks like loops and putting each independent iteration into a thread.
Creating kernel threads
Fork and Clone
Fork
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.
Clone
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.
Java threads
Part of the language. Extends the thread class and implements the runnable interface.
Race condition
Final value of a shared resource depending on the order in which code executes.
Critical section
Block of code where a shared resource is changed or manipulated.
Breakdown of critical section
Entry: Acquire access to the shared resource. Critical Section: Modify shared variable. Exit: exit the critical section. Remainder: Code post critical section.
Criteria for critical section
Mutual exclusion, progress, bounded wait
Mutual exclusion
One process in a critical section at a time
Progress
- 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
Bounded wait
Equitable sharing between processes
Peterson’s model
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.
CS criteria and Peterson’s model
Satisfies mutual exclusion and bounded wait. Doesn’t satisfy progress as P0 hitting an infinite loop in the remainder will halt progress.
Peterson’s model 2
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.
Issue with Peterson’s model 2
If an interrupt occurs during entry section both sections can be set to true and no one can enter cs, failing progress.
Petersons complete algorithm
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.
Test and Set
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.
Atomic instruction
Cannot be interrupted
Test and set cs constraints
Satisfies progress and mutual exclusion. Doesn’t satisfy bounded wait because the same process can get the lock over and over.
Test and set with bounded wait
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.
Problems with test and set bounded wait
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.
Busy waiting
Cycles of processes on wait
Semaphore solution
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.
Semaphore with bounded wait
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.
