Welcome to shouzo's blog!

移動的覺察 / 詮釋者，致力於用技術重現所有天賦

20170525 [學習筆記] Linux 系統程式 (12)

2017-05-25

Linux 作業系統程式設計

Linux 作業系統程式設計
- 一、作業系統
一、作業系統
- 課堂講義
  - Chapter 8: Memory-Management Strategies
(一) Contiguous Allocation
- Main memory must support both OS and user processes
- Limited resource, must allocate efficiently
- Contiguous allocation is one early method
- Main memory usually into two partitions
  - Resident operating system, usually held in low memory with interrupt vector
  - User processes then held in high memory
  - Each process contained in single contiguous section of memory
- Relocation registers used to protect user processes from each other, and from changing operating-system code and data
  - Base register contains value of smallest physical address
  - Limit register contains range of logical addresses – each logical address must be less than the limit register
  - MMU maps logical address dynamically
  - Can then allow actions such as kernel code being transient and kernel changing size
- Multiple-partition allocation
  - Degree of multiprogramming limited by number of partitions
  - Variable-partition sizes for efficiency (sized to a given process’ needs)
  - Hole – block of available memory; holes of various size are scattered throughout memory
  - When a process arrives, it is allocated memory from a hole large enough to accommodate it
  - Process exiting frees its partition, adjacent free partitions combined
  - Operating system maintains information about
    - (a) allocated partitions
    - (b) free partitions (hole)
(二) Dynamic Storage-Allocation Problem
- First-fit：Allocate the first hole that is big enough
- Best-fit：Allocate the smallest hole that is big enough; must search entire list, unless ordered by size
  - Produces the smallest leftover hole
- Worst-fit：Allocate the largest hole; must also search entire list
  - Produces the largest leftover hole
- First-fit and best-fit better than worst-fit in terms of speed and storage utilization
(三) Fragmentation
- External Fragmentation – total memory space exists to satisfy a request, but it is not contiguous
- Internal Fragmentation – allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but not being used
- First fit analysis reveals that given N blocks allocated, 0.5 N blocks lost to fragmentation
  - 1/3 may be unusable -> 50-percent rule
- Reduce external fragmentation by compaction
  - Shuffle memory contents to place all free memory together in one large block
  - Compaction is possible only if relocation is dynamic, and is done at execution time
  - I/O problem
    - Latch job in memory while it is involved in I/O
    - Do I/O only into OS buffers
- Now consider that backing store has same fragmentation problems
(四) Segmentation
- Memory-management scheme that supports user view of memory
- A program is a collection of segments
  - A segment is a logical unit such as：main program、procedure、function、method、object、local variables、global variables、common block、stack、symbol table、arrays
Segmentation Architecture
- Logical address consists of a two tuple：<segment-number, offset>
- Segment table – maps two-dimensional physical addresses; each table entry has
  - base – contains the starting physical address where the segments reside in memory
  - limit – specifies the length of the segment
- Segment-table base register (STBR) points to the segment table’s location in memory
- Segment-table length register (STLR) indicates number of segments used by a program：segment number s is legal if s < STLR
- Protection
  - With each entry in segment table associate
    - validation bit = 0 » illegal segment
    - read/write/execute privileges
- Protection bits associated with segments; code sharing occurs at segment level
- Since segments vary in length, memory allocation is a dynamic storage-allocation problem
- A segmentation example is shown in the following diagram
Read All
20170519 [學習筆記] Linux 系統程式 (11)

2017-05-19

Linux 作業系統程式設計

Linux 作業系統程式設計
- 一、作業系統
一、作業系統
- 課堂講義
  - Chapter 7: Deadlocks
  - Chapter 8: Memory-Management Strategies
- 參考資料
  - Static Linking VS. Dynamic Linking
(一) Deadlock Detection
- Allow system to enter deadlock state
- Detection algorithm
- Recovery scheme
(二) Detection Algorithm
- Example
- Usage
  - When, and how often, to invoke depends on
    - How often a deadlock is likely to occur?
    - How many processes will need to be rolled back?
      
      one for each disjoint cycle
  - If detection algorithm is invoked arbitrarily, there may be many cycles in the resource graph and so we would not be able to tell which of the many deadlocked processes “caused” the deadlock.
(三) Recovery from Deadlock

1. Process Termination
- Abort all deadlocked processes
- Abort one process at a time until the deadlock cycle is eliminated
- In which order should we choose to abort?
  1. Priority of the process
  2. How long process has computed, and how much longer to completion
  3. Resources the process has used
  4. Resources process needs to complete
  5. How many processes will need to be terminated
  6. Is process interactive or batch?
2. Resource Preemption
- Selecting a victim - minimize cost
- Rollback - return to some safe state, restart process for that state
- Starvation - same process may always be picked as victim, include number of rollback in cost factor
(四) Memory-Management
- Program must be brought (from disk) into memory and placed within a process for it to be run
- Main memory and registers are only storage CPU can access directly
- Memory unit only sees a stream of addresses + read requests, or address + data and write requests
- Register access in one CPU clock (or less)
- Main memory can take many cycles, causing a stall
- Cache sits between main memory and CPU registers
- Protection of memory required to ensure correct operation
1. Base and Limit Registers
  - A pair of base and limit registers define the logical address space
  - CPU must check every memory access generated in user mode to be sure it is between base and limit for that user
  - Hardware Address Protection with Base and Limit Registers
2. Address Binding
  - Programs on disk, ready to be brought into memory to execute form an input queue
    - Without support, must be loaded into address 0000
  - Inconvenient to have first user process physical address always at 0000
    - How can it not be?
  - Further, addresses represented in different ways at different stages of a program’s life
    - Source code addresses usually symbolic
    - Compiled code addresses bind to relocatable addresses
      
      i.e. “14 bytes from beginning of this module”
    - Linker or loader will bind relocatable addresses to absolute addresses
      
      i.e. 74014
    - Each binding maps one address space to another
1. Logical vs. Physical Address Space
2. Memory-Management Unit (MMU)
  - Hardware device that at run time maps virtual to physical address
  - Many methods possible, covered in the rest of this chapter
  - To start, consider simple scheme where the value in the relocation register is added to every address generated by a user process at the time it is sent to memory
    - Base register now called relocation register
    - MS-DOS on Intel 80x86 used 4 relocation registers
  - The user program deals with logical addresses; it never sees the real physical addresses
    - Execution-time binding occurs when reference is made to location in memory
    - Logical address bound to physical addresses
3. Dynamic relocation
  - Using a relocation register
4. Dynamic Linking
  - Static linking - system libraries and program code combined by the loader into the binary program image
  - Dynamic linking – linking postponed until execution time
  - Small piece of code, stub, used to locate the appropriate memory-resident library routine
  - Stub replaces itself with the address of the routine, and executes the routine
  - Operating system checks if routine is in processes’ memory address
    - If not in address space, add to address space
  - Dynamic linking is particularly useful for libraries
  - System also known as shared libraries
  - Consider applicability to patching system libraries
    - Versioning may be needed
5. Swapping
  - A process can be swapped temporarily out of memory to a backing store, and then brought back into memory for continued execution
    - Total physical memory space of processes can exceed physical memory
  - Backing store – fast disk large enough to accommodate copies of all memory images for all users; must provide direct access to these memory images
  - Roll out, roll in – swapping variant used for priority-based scheduling algorithms; lower-priority process is swapped out so higher-priority process can be loaded and executed
  - Major part of swap time is transfer time; total transfer time is directly proportional to the amount of memory swapped
  - System maintains a ready queue of ready-to-run processes which have memory images on disk
  - Does the swapped out process need to swap back in to same physical addresses?
    - Depends on address binding method
      
      Plus consider pending I/O to / from process memory space
  - Modified versions of swapping are found on many systems (i.e., UNIX, Linux, and Windows)
    - Swapping normally disabled
    - Started if more than threshold amount of memory allocated
    - Disabled again once memory demand reduced below threshold
Read All
20170512 [學習筆記] Linux 系統程式 (10)

2017-05-12

Linux 作業系統程式設計

Linux 作業系統程式設計
- 一、作業系統
一、作業系統
- 課堂講義
  - Chapter 7: Deadlocks
(一) Deadlock Characterization
- Mutual exclusion：only one process at a time can use a resource.
- Hold and wait：a process holding at least one resource is waiting to acquire additional resources held by other processes.
- No preemption：a resource can be released only voluntarily by the process holding it, after that process has completed its task.
- Circular wait：there exists a set {P0, P1, …, Pn } of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2 , …, Pn–1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held by P0.
- Deadlocks can occur via system calls, locking, etc
(二) Resource-Allocation Graph

1. Example
- Resource Allocation Graph
- Resource Allocation Graph With A Deadlock
- Graph With A Cycle But No Deadlock
2. Basic Facts
- If graph contains no cycles » no deadlock
- If graph contains a cycle
  - if only one instance per resource type, then deadlock
  - if several instances per resource type, possibility of deadlock
3. Methods for Handling Deadlocks
- Ensure that the system will never enter a deadlock state
- Allow the system to enter a deadlock state and then recover
- Ignore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNIX
(三) Deadlock Prevention
- Mutual Exclusion：not required for sharable resources; must hold for nonsharable resources
- Hold and Wait：must guarantee that whenever a process requests a resource, it does not hold any other resources
  - Require process to request and be allocated all its resources before it begins execution, or allow process to request resources only when the process has none
  - Low resource utilization; starvation possible
- No Preemption：
  - If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released
  - Preempted resources are added to the list of resources for which the process is waiting
  - Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting
- Circular Wait：impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration
1. Example
- Deadlock Example
```
/* thread one runs in this function */
void *do work one(void *param)
{
    pthread mutex lock(&first mutex);
    pthread mutex lock(&second mutex);
    /** * Do some work */
    pthread mutex unlock(&second mutex);
    pthread mutex unlock(&first mutex);
    pthread exit(0);
}

/* thread two runs in this function */
void *do work two(void *param)
{
    pthread mutex lock(&second mutex);
    pthread mutex lock(&first mutex);
    /** * Do some work */
    pthread mutex unlock(&first mutex);
    pthread mutex unlock(&second mutex);
    pthread exit(0);
}
```
- Deadlock Example with Lock Ordering
```
void transaction(Account from, Account to, double amount)
{
    mutex lock1, lock2;
    lock1 = get lock(from);
    lock2 = get lock(to);
    acquire(lock1);
    acquire(lock2);
    withdraw(from, amount);
    deposit(to, amount);
    release(lock2);
    release(lock1);
}
```
2. Deadlock Avoidance
- Requires that the system has some additional a priori information available
  - Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need
  - The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition
  - Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes
3. Safe State

4. Basic Facts
- If a system is in safe state » no deadlocks
- If a system is in unsafe state » possibility of deadlock
- Avoidance » ensure that a system will never enter an unsafe state
5. Safe, Unsafe, Deadlock State

6. Avoidance algorithms
- Single instance of a resource type
  - Use a resource-allocation graph
- Multiple instances of a resource type
  - Use the banker’s algorithm
7. Resource-Allocation Graph

8. Algorithm

(1) Data Structures for the Banker’s Algorithm
- Example
(2) Safety Algorithm
Read All
20170505 [學習筆記] Linux 系統程式 (9)

2017-05-05

Linux 作業系統程式設計

Linux 作業系統程式設計
- 一、作業系統
一、作業系統
- 課程簡報
  - Chapter 6: Process Scheduling
(一) Semaphore
- Synchronization tool that does not require busy waiting.
- Semaphore S – integer variable
- Two standard operations modify S: wait() and signal()
- Less complicated
- Can only be accessed via two indivisible (atomic) operations
```
wait(S)
    while (S <= 0)
        ; //busy wait
    S--;
}
signal(S) {
    S++;
}
```
1. Usage
- Counting semaphore – integer value can range over an unrestricted domain
- Binary semaphore – integer value can range only between 0 and 1
  - Then a mutex lock
- Can implement a counting semaphore S as a binary semaphore
- Can solve various synchronization problems
- Consider P1 and P2 that require S1 to happen before S2
```
P1:
    S1;
    signal(synch);
P2:
    wait(synch);
    S2;
```
2. Implementation

(1) Busy waiting
- Must guarantee that no two processes can execute wait() and signal() on the same semaphore at the same time
- Thus, implementation becomes the critical section problem where the wait and signal code are placed in the critical section
- Could now have busy waiting in critical section implementation
  - But implementation code is short
  - Little busy waiting if critical section rarely occupied
- Note that applications may spend lots of time in critical sections and therefore this is not a good solution
(2) with no Busy waiting
- With each semaphore there is an associated waiting queue
- Each entry in a waiting queue has two data items:
  - value (of type integer)
  - pointer to next record in the list
- Two operations:
  - block – place the process invoking the operation on the appropriate waiting queue
  - wakeup – remove one of processes in the waiting queue and place it in the ready queue
```
typedef struct{
    int value;
    struct process *list;
} semaphore;

wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        // add this process to S->list;
        block();
    }
}

signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        // remove a process P from S->list;
        wakeup(P);
    }
}
```
(二) Deadlock and Starvation
- Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes
- Let S and Q be two semaphores initialized to 1
- Starvation – indefinite blocking
  - 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
  - Solved via priority-inheritance protocol
(三) Classical Problems of Synchronization

1. Bounded-Buffer Problem
- n buffers, each can hold one item
  - Semaphore mutex initialized to the value 1
  - Semaphore full initialized to the value 0
  - Semaphore empty initialized to the value n
(1) The structure of the producer process
```
do {
    ...
    /* produce an item in next_produced */
    ...
    
    wait(empty);
    wait(mutex);
    
    ...
    /* add next produced to the buffer */
    ...

    signal(mutex);
    signal(full);
} while (true);
```
(2) The structure of the consumer process
```
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);
```
2. Readers-Writers Problem
- A data set is shared among a number of concurrent processes
  - Readers - only read the data set; they do not perform any updates
  - Writers - can both read and write
- Problem - allow multiple readers to read at the same time
- Several variations of how readers and writers are treated – all involve priorities
- Shared Data
  - Data set
  - Semaphore rw_mutex initialized to 1
  - Semaphore mutex initialized to 1
  - Integer read_count initialized to 0
(1) The structure of a writer process
```
do {
    wait(rw_mutex);
    
    ...
    /* writing is performed */
    ...
    
    signal(rw_mutex);
} while (true);
```
(2) The structure of a reader process
```
do {
    wait(mutex);
    read_count++;
    
    
    if (read_count == 1)    // only for the first reader entering
        wait(rw_mutex);
        
    signal(mutex);    // if the first reader wait for rw_mutex, other readers will be blocked on wait(mutex)
        
    ...
    /* reading is performed */
    ...
        
    wait(mutex);
    read_count--;
        
    if (read_count == 0)    // only for the last reader leaving
        signal(rw_mutex);
    
    signal(mutex);
} while (true)
```
(3) Problem
- First variation – no reader kept waiting unless writer has permission to use shared object
- Second variation – once writer is ready, it performs write asap
- Both may have starvation leading to even more variations
- Problem is solved on some systems by kernel providing reader-writer locks
3. Dining-Philosophers Problem
- Philosophers spend their lives thinking and eating
- Don’t interact with their neighbors, occasionally try to pick up 2 chopsticks (one at a time) to eat from bowl
  - Need both to eat, then release both when done
(1) In the case of 5 philosophers
- Shared data
  - Bowl of rice (data set)
  - Semaphore chopstick [5] initialized to 1
- The structure of Philosopher i:
```
do {
    wait ( chopstick[i] );
    wait ( chopStick[ (i+1) % 5] );
    
    // eat

    signal ( chopstick[i] );
    signal (chopstick[ (i+1) % 5] );
    
    // think
    
} while (TRUE);
```
- Incorrect use of semaphore operations:
  - signal (mutex) …. wait (mutex)
  - wait (mutex) … wait (mutex)
  - Omitting of wait (mutex) or signal (mutex) (or both)
- Deadlock and starvation
(2) Monitors
- A high-level abstraction that provides a convenient and effective mechanism for process synchronization
- Abstract data type, internal variables only accessible by code within the procedure
- Only one process may be active within the monitor at a time
- But not powerful enough to model some synchronization schemes
Monitors Implementation

1. Using Semaphores
- Variables
```
semaphore mutex; // (initially = 1)
semaphore next; // (initially = 0)
int next_count = 0;
```
- Each procedure F will be replaced by
```
wait(mutex);

...
body of F;
...

if (next_count > 0)
    signal(next)
else
    signal(mutex);
```
- Mutual exclusion within a monitor is ensured
2. Condition Variables
- For each condition variable x, we have:
```
semaphore x_sem; // (initially = 0)
int x_count = 0;
```
- The operation x.wait can be implemented as:
```
x-count++;
if (next_count > 0)
    signal(next);
else
    signal(mutex);
wait(x_sem);
x-count--;
```
Resuming Processes
- If several processes queued on condition x, and x.signal() executed, which should be resumed?
- FCFS frequently not adequate
- conditional-wait construct of the form x.wait(c)
  - Where c is priority number
  - Process with lowest number (highest priority) is scheduled next
Allocate Single Resource
```
monitor ResourceAllocator
{
    boolean busy;
    condition x;
    
    void acquire(int time) {
        if (busy)
            x.wait(time);
        busy = TRUE;
    }
    
    void release() {
        busy = FALSE;
        x.signal();
    }
    
    initialization code() {
        busy = FALSE;
    }
}
```
(3) Solution
- Each philosopher i invokes the operations pickup() and putdown() in the following sequence:
  - No deadlock, but starvation is possible.
```
DiningPhilosophers.pickup(i);
    EAT
DiningPhilosophers.putdown(i);
```
```
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 neighbors */
        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;
    }
}
```
Read All
20170504 [個人紀錄] Vim 慣用設定

2017-05-04

程式設計

Vim
- 前言
- 一、vimrc 慣用設定
前言

最近剛重灌 Ubuntu，在此紀錄個人安裝 Vim 時常用的設定與外掛。

一、vimrc 慣用設定
- 系統環境
  
  ubuntu 17.04
- 參考資料
- 個人常用的 Prompt 顏色格式
  
  PS1=’[\e[1;33m]\u@\h[\e[m]:[\e[1;34m]\W[\e[1;32m]$[\e[m] ‘
Read All