---
# System prepended metadata

title: All
tags: [OS]

---

# 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

![](https://i.imgur.com/K5Yk0iX.png)

* **Request edge**
![](https://i.imgur.com/vgUM9MB.png)

* **Assignment edge**
![](https://i.imgur.com/6XtVjhO.png)

* **Process**
![](https://i.imgur.com/pjKPI14.png)

* **Resource**
![](https://i.imgur.com/445lCYQ.png)

### Wait-for Graph
![](https://i.imgur.com/difd2sS.png)

### Basic Facts

* if system in safe state -> no deadlock
* if system in unsafe state -> possibility of deadlock
![](https://i.imgur.com/hHWKEUP.png)



#### 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
![](https://i.imgur.com/Dtekcmj.png)

* unsafe in resource-allocation graph
![](https://i.imgur.com/t5GAkFD.png)


#### 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)
![](https://i.imgur.com/IQo49If.png)
> 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)
>以此類推

![](https://i.imgur.com/OVaZIHh.png)

![](https://i.imgur.com/GPpWgCJ.png)

> 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
![](https://i.imgur.com/lL23Osq.png)

* Thrashing
![](https://i.imgur.com/rBRQ7BO.png)

* Belady's Anomaly
![](https://i.imgur.com/tfchkVN.png)

* Buddy System Allocator
![](https://i.imgur.com/oJaKjyI.png)









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

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

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

```cpp=
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);
```

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

```cpp=
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);
```

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

```cpp=
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);
```

```cpp=
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;
      }
}
```