PROCESS SYNCHRONIZATION

PREEMPTIVE KERNEL

allows a process to be preempted while it is running in kernel mode.

SYNCHRONIZATION HARDWARE

- in a uniprocesor environment
- disables interrupts
- shared variable

- multiprocessor systems

- disabling interrupts may cause delay entry to the critical section and can decrease efficiency (ex: system clock)

- message passing
- modern machines provide special atomic or non-interruptible
hardware instructions

- use of TestAndSet() and Swap() *both are executed atomically

MUTEX LOCKS VS. SEMAPHORES

- locking mechanisms | signaling mechanisms

- object | integer

- modified by processes that requests or releases a source | modified by wait and signal

- if locked, process waits, queued and can be accessed when mutex is unlocked | if resource is not free, process requires a resource with wait, semaphore count is 0

- can have multiple threads but not simultaneously | can have multiple threads

- only lock() can release | any process can obtain and release

- lock & unlock | wait & signal

CRITICAL SECTION

- is a part of program that tries to access shared resources
- needs to be executed immediately

ex: CPU, memory, data structure, IO device

- Processes should not be inside their critical sections at the same time
- Processes executing outside its critical sections should not block other processes
- Processes should not be waiting for a long time to enter its critical section

conditions for critical section

NON-PREEMPTIVE KERNEL

does not allow a process to be preempted while running in kernel mode

PETERSON'S ALGORITHM

- algorithm for mutual exclusion

- assumes that the load and store machine-language instructions are atomic; that is, cannot be interrupted
- allows 2 processes that alternate between their critical sections
and remainder sections

- requires 2 processes to share data items

* if turn == 1, process is allowed to enter critical section
* if flag[i] is true, means that Pi is ready to enter critical section

MUTEX LOCKS

- kernel resource
- OS "locking mechanism"
- software solution for critical section problem
- locks the resources in the entry section of the code
- unlocks the resources at the exit section

SEMAPHORES

- "signaling" mechanism
- OS service for synchronization
- uses an integer variable
- uses Wait() and Signal()

COUNTING SEMAPHORES

- no mutual exclusion, integer value, more than one slot, provide a set of processes

BINARY SEMAPHORES

- mutual exclusion, binary value, only one slot, implements mutual exclusion mechanism

BOUNDED BUFFER PROBLEM

- multi-process synchronization
- producer and consumer share the same buffer
- producer generates data and places it in a buffer
- consumer consumes the data from the buffer
- producer should not produce data if buffer is full
- consumer should not consume data if buffer is empty
- producer and consumer should not access the buffer at the same time

*use semaphores to solve where:

• semaphore S: the produce or consumer will be allowed to access the buffer at a particular time

• semaphore E: variable that defines the empty space in a buffer

• semaphore F: variable that defines the filled-up space in the

READERS WRITERS PROBLEM

- data set is shared among a number of concurrent processes
- only 1 writer can write at a time
- if a process is writing, other processes cannot read or write to it

problem:
- allow several readers to read
- allow only one writer to modify the data

* to solve use semaphores

READERS

only read the data set; they do not perform any updates

WRITERS

can both read and write

DINING PHILOSOPHERS PROBLEM

solution:

uses semaphore to represent a chopstick

• Wait() - chopstick is picked
• Signal() - releases a chopstick

MONITOR SYNCHRONIZATION

- one solution in process synchronization

- high-level abstraction for process synchronization

- only one process is active within the monitor at a time

- overcomes timing errors

- abstract data types and contain shared data variables and procedures

CONDITION VARIABLE

a container of threads that wait for a certain condition. it cannot be shared with other processes.

SIGNAL()

a blocked process is given a chance to execute when another process performs a signal operation on a condition
variable

WAIT()

suspends the process that are waiting for any condition variable. the suspended process is placed in a block queue of that particular condition variable.

TRANSACTIONAL MEMORY

- concurrency control mechanism
- uses load and store atomically
- provide high-level programming abstraction
- coordinates between concurrent reads and writes

TRANSACTION

set of operations that can execute and commit changes as long as there is no conflict

SOFTWARE TRANSACTIONAL MEMORY

code is inserted by a compiler and manages each transaction by examining
where statements may run concurrently and where specific low-level locking is
required

HARDWARE TRANSACTIONAL MEMORY

uses hardware cache hierarchies and cache coherency protocols to manage and resolve conflicts involving shared data residing in separate processors' caches

* no code instrumentation

OPENMP (OPEN MULTI PROCESSING)

- supports multiplatform shared-memory multiprocessing
- master threads create slave threads

FUNCTIONAL PROGRAMMING LANGUAGES

- offer a different paradigm than procedural languages in that they do not maintain state
- variables are immutable
- based on mathematical functions

CLOSURE

inner function that c access the parent
function's variables even after the parent function has executed

FUNCTIONAL PROGRAMMING

easier to maintain because it is not possible for accidental changes outside the given function. no side effects.

MODULARITY

makes use of small modules and can be
tested separately. can easily be reused.

REFERENTIAL TRANSPARENCY

variables in functions do not change its value

IMMUTABLE DATA

to easily create data structures instead of modifying existing ones