# All
###### tags: `OS`

## ch6.

### Critical section
#### Solution
1. **Mutual Exclusion**
2. **Progress**
3. **Bounded-Waiting**

#### Handling
* **Preemptive**
* **Non-preemptive**

#### Synchronization Hardware
* **Atomic** = **non-interruptible**

#### Mutex Locks
* **Busy waiting**
* this lock can call **spinlock**

### Semaphore Usage
* **Counting Semaphore**
* **Binary Semaphore**
* same as **mutex lock**

### if Semaphore no Busy Waiting
* Two operations
* **block**
* **wakeup**

### Deadlock & Starvation
* **Deadlock**
* two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes
* **Starvation**
* A process may never be removed from the semaphore queue in which it is suspended
* **Priority Inversion**
* Scheduling problem when lower-priority process holds a lock needed by higher-priority process
* via **priority-inheritance** protocol to solve

### Conditions Variables
* **Signal and wait**
* **Signal and continue**

## ch7.

### Readers & Writers Problem
* two variations
* **First variations**
* **Second variations**

* System
* **Solaris**
* **Windows**
* **Linux**
* **Pthreads**

#### **Solaris**
* importance
* adaptive mutexes
* condition variations
* readers-writers
* turnstiles

#### **Windows**
* importance
* spinlocks
* dispatcher objects
* signaled-state
* non-signaled state

#### **Linux**
* importance
* Semaphores
* atomic integers
* spinlocks
* reader-writer versions of both
* reader
* writer

#### **Pthreads**
* importance
* Pthreads API is OS-independent
* mutex locks
* condition variable
* Non-portable
* read-write locks
* spinlocks

### Alternative Approaches
* **Transactional Memory**
* **OpenMP**
* **Functional Programming Languages**

## ch8.

### System Model
* **Request**
* **Use**
* **Release**

### Deadlock

#### Solution
* **Mutual exclusion**
* **Hold and wait**
* **No preemption**
* **Circular wait**

#### Deadlock with Mutex Locks
* occur via
* **System calls**
* **locking**

### Resource-Allocation Graph


* **Request edge**

* **Assignment edge**

* **Process**

* **Resource**

### Wait-for Graph

### Basic Facts

* if system in safe state -> no deadlock
* if system in unsafe state -> possibility of deadlock

#### Handling Deadlocks
* Deadlock Prevention
* **Mutual Exclusion**
* **Hold and Wait**
* **No Preemption**
* **Circular Wait**

* Deadlock Avoidence
* algorithm
* Single
* resource-allocation graph
* Multiple
* Banker's algorithm

* resource-allocation graph

* unsafe in resource-allocation graph

#### Banker's algorithm
* **Available**
* **Max**
* **Allocation**
* **Need**

#### Safety algorithm
(1)
Work = Available;
Finish[i] = false;
(2)
Finish[i] = false;
if Need <= Work, go step (3)
else if i no exist, go step (4)
(3)
Work = Work + Allocation~i~
if Finish[i] == true, go step (2)
(4)
if Finish裡的陣列狀態都等於true的時候, then System is Safe state(= Answer)

#### Example(Banker's algorithm)
> P~n~ Need = Max[P~n~] - Allocation[P~n~]
> so,
> P~1~ Need = (7,5,3) - (0,1,0) = (7,4,3)
> P~2~ Need = (3,2,2) - (2,0,0) = (1,2,2)
>以此類推



> if Available >= Need[P~n~]
> Available = Available + Allocation[P~n~]
> else next
> so,
> (3,3,2) < (7,4,3) next
> (3,3,2) >= (1,2,2) Available = (3,3,2) + (2,0,0) = (5,3,2)
> (5,3,2) < (6,0,0) next
> (5,3,2) >= (0,1,1) Available = (5,3,2) + (2,1,1) = (7,4,3)
> (7,4,3) >= (4,3,1) Available = (7,4,3) + (0,0,2) = (7,4,5)
> because P~0~ and P~2~ no excute, so we back to deal again
> (7,4,5) >= (7,4,3) Available = (7,4,5) + (0,1,0) = (7,5,5)
> (7,5,5) >= (6,0,0) Available = (7,5,5) + (3,0,2) = (10,5,7)
> ### Ans : P~2~-->P~4~-->P~5~-->P~1~-->P~3~

#### Detection algorithm
(1)
Work = Available;
Finish[i] = Allocation
if Finish == 0, then Finish[i] = true;
(2)
if Finish[i] == false;
Request <= Work
if i no exist, go step (4)
(3)
Work = Work + Allocation~i~
if Finish[i] == true,then go step (2)
(4)
if Finish裡的陣列狀態都等於false的時候, then System is deadlock

#### Resource Request algorithm
(1)
Request <= Need, then go (2)
(2)
Request <= Available, then go (3)
(3)
Available = Available - Request
Allocation = Allocation + Request
Need = Need - Request
### Recovery from Deadlock: Resource Preemption
* Selecting a victim
* Rollback
* Starvation

## ch9.

### Address Binding
* Compile time
* Load time
* Excution time

### Logical vs. Physical Address Space
* Logical address
* generated by the CPU
* also referred to as virtual address
* Execution-time binding occurs when reference is made to location in memory
* Logical address bound to physical addresses
* each logical address must be less than the limit register
* MMU maps logical address dynamically
* <segment-number, offset>
* Physical
* address seen by the memory unit
* Hardware device that at run time maps virtual to physical address
* Base register contains value of smallest physical address

* hit time = access memory + search time
* miss time = access memory + access memory + search time
* EAT(effective access time) = hit time + miss time;

## ch10.
* Copy-on-Write

* Thrashing

* Belady's Anomaly

* Buddy System Allocator

## Program

while (true) {/* produce an item in next produced */ 
    while (counter == BUFFER_SIZE) ; 
        /* do nothing */       
    buffer[in] = next_produced;
    in = (in + 1) % BUFFER_SIZE; 
    counter++; 
}

while (true) {
    while (counter == 0) ; 
        /* do nothing */ 
    next_consumed = buffer[out]; 
    out = (out + 1) % BUFFER_SIZE; 
    counter--; /* consume the item in next consumed */ 
} 

do { 
    flag[i] = true; 
    turn = j; 
    while (flag[j] && turn = = j); 
        critical section 
    flag[i] = false; 
        remainder section 
    } while (true);

do {   
    waiting[i] = true;   
    key = true;   
    while (waiting[i] && key) 
        key = test_and_set(&lock); 
    waiting[i] = false; 
    /* critical section */ 
    j = (i + 1) % n; 
    while ((j != i) && !waiting[j]) 
        j = (j + 1) % n; 
    if (j == i) 
        lock = false; 
    else 
        waiting[j] = false; 
    /* remainder section */ 
} while (true);

do { 
    ...        
    /* produce an item in next_produced */ 
    ... 
    wait(empty); 
    wait(mutex); 
    ...        
    /* add next produced to the buffer */ 
    ... 
    signal(mutex); 
    signal(full); 
} while (true);

Do { 
    wait(full); 
    wait(mutex); 
    ...        
    /* remove an item from buffer to next_consumed */ 
    ...
    signal(mutex); 
    signal(empty); 
    ...        
    /* consume the item in next consumed */ ...     
} while (true);

do {          
    wait(rw_mutex); 
    ...          
    /* writing is performed */ 
    ... 
    signal(rw_mutex); 
} while (true);

do {           
    wait(mutex);           
    read_count++;           
    if (read_count == 1) 
        wait(rw_mutex); 
    signal(mutex); 
    ...           
    /* reading is performed */ 
    ... 
    wait(mutex);           
    read count--;           
    if (read_count == 0) 
        signal(rw_mutex); 
    signal(mutex); 
} while (true);

monitor DiningPhilosophers{ 
    
    enum { THINKING; HUNGRY, EATING) state [5] ;
          condition self [5];
          void pickup (int i) { 
              state[i] = HUNGRY;
              test(i);
              if (state[i] != EATING) 
                  self[i].wait;
          }
          void putdown (int i) { 
              state[i] = THINKING;
              // test left and right neighborstest(
              test((i + 4) % 5);
              test((i + 1) % 5);
          }
          void test (int i) { 
            if ((state[(i + 4) % 5] != EATING) &&(state[i] == HUNGRY) &&(state[(i + 1) % 5] != EATING) ) { 
                state[i] = EATING ;
                self[i].signal () ;
            }
        }
      initialization_code() { 
          for (int i = 0; i < 5; i++)
              state[i] = THINKING;
      }
}