Winwoo's Story

Semaphore and Monitor

• Semaphore의 문제점 보완
  - 함수명으로 Semaphore의 사용을 구분한다.
  

  

  
  

• Mutex (Mutual exclusion)
  - Mutual exclusion을 구현하기 위해 사용하는 Sleeping Lock
  - 동일한 Mutex를 사용할 때 Mutex_lock()을 호출한 Process와 Mutex_unlock()을 호출한 Process가 일치해야 된다.
  
  

• Semaphore의 구현
  - 기본적으로 C 구조체 이다.
  

  

  
  

• P함수 / V함수 구현
  - Interrupt disable을 사용해야 안전성이 보장된다.
  - 짧은 시간이기 때문에 Interrupt disable을 사용해도 문제가 없다.
  - Cnt = Semaphore
  - Cnt가 0이상일 경우 : 남아있는 열쇠(자원)의 개수
  - Cnt가 0이하일 경우 : 절대값이 Queue에서 대기중인 Process의 개수
  - 기본적으로 Single Processor용 Mechanism
  

  

  
  

• Multi Processor Semaphore Mechanism
  - Atomic OS 필요 : 글로벌 자원를 읽고, 쓰는 등 전체의 과정을 쪼갤 수 없는 기본 단위로 만듦
  - Bus를 장악하여 한 Processor가 자원을 사용하고 있을 경우 다른 Processor의 Bus Transaction을 차단
  
  

• TAS (Test And Set) Instruction
  - 대표적인 Multi Processor Semaphore Mechanism
  - 메모리의 Boolean 변수를 읽어서 확인 후 값을 1로 쓰는 작업을 Atomic하게 수행
  - Busy waiting이란 단점이 있다.
      *Busy Waiting(Spining) : 특정 조건의 만족 여보를 루프를 돌면서 반복하여 확인하는 기법
  
  

• Monitor
  - P나 V를 빼먹어서 생기는 오류를 최대한 줄이기 위해 사용
  - Java에서 Synchronized Class가 예
  

  

  
  

• Monitor API
  - condition 변수 : 어떤 조건이 충족되기를 기다리고 있는 Process들의 Waiting Queue
  - Monitor는 한번에 하나의 Process만 내부의 Method를 수행할 수 있도록 허용하기 때문에 Monitor 내부의 변수들을 따로 보호하지 않는다.
  

  

  
  
  

• Hoare Style Monitor(Signal-and-Urgent-wait monitor)
  - waitQueue에서 깨어난 Process가 바로 monitor내부로 진입하는 방식의 Monitor
      *Signaler Queue : Signal을 보낸 Process가 Monitor밖에서 대기하기 위한 Queue
  
  

• Brinch-Hansen Style Monitor
  - Wait Queue에 Signal을 보낸 Process가 수행을 계속하는 방식의 Monitor
  
  

• Monitor Implementation
  

  

  
  

Process Synchronization

• Synchronization
  - Proecess간에 Interrupt -> Resource Share
  
  

• Reentrant code(재진입가능 코드)
  - 여러 Process들에 의해 동시에 호출되거나, 이전 호출이 완료되기 전에 반복 호출되어도 올바르게 수행 되는 코드
  
  

• Race Condition(경합 조건)
  - Synchronization의 문제로 여러 Process들이 동기화 절차를 거치지 않고 동시에 자원을 사용하기 위해 경쟁하므로써 그 수행결과를 예측할 수 없게 되는 상황
  
  

• Critical Section
  - 하나의 Process가 자원을 독차지 하고 모든 작업을 수행시키는 공간
  - Mutual exclusion : 한 Process 외의 다른 Process는 배제 시킨다.
  - 여러개 Process가 진입 요청시 그중 하나의 Process만 허용한다.
  
  

• Semaphore (중요)
  

  

  
  - Synchronization을 제공해 주는 정수형 변수
  - 초기값은 1로 초기화 한다.
  - Mutual exclusion 제공
  - Scheduling 제공된다.
  

  

  (semaphore Scheduling)
  
  

• Binary Semaphore
  - 0 또는 1의 2가지 상황만 있는 경우
  
  

• Counting Semaphore
  - 0과 1외 또다른 2가지 이상의 상황이 있는 경우
  
  

• Producer / consumer
  - Producer : Data 생성 -> 버퍼에 넣는 행위
  - consumer : Data 사용 -> 버퍼에서 읽는 행위

  

  
  
  

• Producer / Consumer에 Semaphore적용
  - Producer가 Consumer보다 빠를 경우 Producer는 대기현상이 발생
  - Consumer가 Producer보다 빠를 경우 Consumer행위는 대기현상이 발생
  -> 두 현상 모드 Semaphore를 사용하여 해결
  

  

  
  

• Interrupt Disable을 사용한 Synchronization의 문제
  - Interrupt Disable은 시스템 전체에 영향을 미치기 때문에 상관없는 Process의 수행도 방해하게 됨
  
  

• Semaphore의 단점
  - Unstructured Programming construct이기 떄문에 컴파일러등의 도구를 사용한 디버깅이 어렵다.

CPU Scheduling

• Preemptible Resource
  - 한 Process가 점유한 상태에서 다른 Process에게 양보할 수 있는 자원
      (ex)CPU, Memory
  
  

• Non-Preemptible Resource
  - 한 Process가 점유하면 사용을 마칠때 까지 다른 Process에게 양보할 수 없는 자원
      (ex)Printer
  
  

• CPU Brust
  - 프로그램의 수행중에 연속적으로 CPU를 사용하는 단절구간
  

  
  

• I/O Brust
  - 프로그램의 수행중에 I/O의 완료를 기다리며 블록 되는 구간
  
  

• Scheduling Policies
  - 다음에 어떤 Process에게 CPU자원을 할당 할지
  - 얼마만큼에 시간동안 자원 할당 할지
  
  
• Scheduling Policies 설계 목표
  - Resource의 실질적인 작업시간 계산
  - 오버헤드의 최소화
  - Scheduling 최소화 ( Context Switching 최소화)
  - CPU Time을 여러 Process에게 골고루 할당
  
  
• Aging
  - Task가 CPU를 기다리는 시간에 비례하여 우선순위를 점차적으로 높이는 기법
  
  
• Process의 특징
  - CPU Bound Process : 대부분의 시간을 CPU연산에 사용
      성능적 요구 : 높은 CPU Utilization과 Throughput을 요구
  - I/O Bound Process : 대부분의 시간을 I/O를 보내고 wait에 사용하고 CPU연산을 짧게 한다.
     성능적 요구 : 짧은 Response Time을 요구한다.
  
  
• Scheduling의 종류
  1. First in First out ( FIFO )
      - 먼저 들어온 job을 먼저 처리한다.
      - CPU Brust기준으로 실행한다
      장점 : 단순하고 직관적
      단점 : 하나의 job이 무한Loop를 통해 CPU를 계속해서 점유하고 있을 수 있다. -> 이 경우 OS가 Timer를 통해 관리
      - CPU Brust가 짧은 순서대로 실행시키는게 효율적
          -> 문제점 : 운영체제가 Task의 남은 CPU Brust size를 예측할 수 없음
  
  2. Round Robin ( RR )
      - 기본적으로 FIFO 구조로 설계
      - Timeout 시간을 정해 일정시간 동안만 Job을 실행시키고 시간이 초과 하면 Ready Queue의 맨뒤로 간다.
      - 문제점
          (1) *<Timeout 시간>을 얼마나 잡을 것 인가?
              *Timeout 시간 : Time Slice 또는 TimeQuantum 
                  -> Task에게 CPU가 할당된 후 다음 스케쥴링을 위한 Timer Interrupt가 발생할 때 까지의 시간
          (2) 평균적으로 FIFO보다 좋은 성능을 보이지만 몇몇 상황에선 FIFO보다 안좋은 성능을 보인다.
          (3) CPU Brust의 차이가 미미하다면 FIFO가 효율적이다.
          (4) CPU Brust의 차이가 클수록 Round Robin이 효율적이다.
  
  3. Adeptive Scheduling
      - workload의 특성에 따라 Time Slice의 크기를 동적으로 바꿔주는 스케쥴링 기법
      - Multi Level Feedback Queue가 대표적 (MLFQ)
  
      
  
  4. Priority-based Scheduling
      - Process들에게 선호도를 매기고, 선호도가 높은 Process를 먼저 수행하는 스케쥴링 기법
      - 문제점 : Stavation -> 수행할 준비를 마치고 CPU를 할당 받기를 기다리는 Process가 선호도가 낮아 무기한 연기되는 현상 발생
  
  5. Fair Share Scheduling(Bandwidth Scheduling, Proportional Share Scheduling)
      - 대기중인 Process들에게 정해진 비율에 따라 CPU의 Bandwidth를 분배하는 스케쥴링 기법
  
  
• Evolution of Scheduling Policies
  
  

MultiThreading

• Server Architecture
  - iterative server : 서버가 깨어나서 Message Queue의 내용을 처리하고 처리가 완료되면 다시 Queue의 내용을 확인하여 처리
      *장점 : 단순하고 관리가 쉽다.
      *단점 : 하나의 Process를 사용하기 떄문에 처리속도가 느리다.
  - Concurrent server : Message Queue에서 Request의 처리를 서버가 직접하는것이 아니라 별도의 Worker Process를 두어 처리하게 하는 방식
      *장점 : 다수의 Process를 이용해 처리속도가 빠르다.
      *단점 : 여러 Process를 생산 및 관리해야 되기 때문에 복잡하고 시스템에 부담이 된다.
  

  

  
  

• MultiThreading의 목적

- Concurrency(동시 처리)는 높이면서 Execution Unit을 생성하거나 수행시키는데 드는 부담을 줄임
- Massively Parallel Scientific Programming ( 대용량 병렬 프로그래밍 )을 할 때 발생하는 오버헤드를 줄이기 위해

• Process와 Thread의 관계
  - Process는 Context와 Thread of Control로 이루어져있다.
  - 이때 Process안에 Thread가 여러개 있는 것이 MultiThread이다.
  
  
• MultiThread구현에 필요한 것들
  - 하나의 Process가 여러개의 Thread를 갖게 되므로 Process는 여러개의 Stack을 갖게된다.
  - 여러개의 Thread를 관리하기 위해 Thread ID를 할당 한다.
  - Thread 마다의 정보를 갖고있을 Thread control Block(TCB)을 생성한다.
  
  

• Task
  - Design Time Process
  - Process에게 부여된 자원(Resource)
  
  
• MultiThread의 구현
  1. User-Level 구현
      1. Stack 구현
      2. TCB를 Thread 마다 생성 (User Level에 위치)
      3. Thread 간의 Switching을 위해 Scheduler 구현
          - user Level에 Scheduler 함수 생성
          - 여러 Scheduler함수를 모아 Thread Library로 묶음
          *Thread Library : Thread의 생성 및 소멸, Thread Context저장, Thread간 접근 가능
     

- 문제점 -
    1. 한 Thread가 Blocking System call을 호출하는 경우 해당 process의 모든 Thread가 Block된다.
    2. OS가 Thread에게 직접 Interrupt를 전달할 수 없기 때문에 Preemptive Schedling을 할 수 없다.

2. Kernel-Level구현
    - Kernel의 System call을 이용하여 모든 처리를 한다.
    -장점 : User-Level의 단점을 모드 보완한다.
    - 단점 : Kernel단의 수행시간이 증가되면서 추가적인 오버헤드가 발생한다.

3. Combined User-Level / KernelLevel 구현
    - 대부분 User-Level에서 처리
    - Interrupt가 왔을 시 Interrupt를 User-Level Scheduler에게 전달
    - Blocking System call 발생 시 해당 Thread를 중지시키고 새로운 Kernel Stack을 할당하여 User Process에 붙여 Return시킨다.

• POSIX Pthread API
  - 다양한 unix계열 운영체제들의 API를 표준화 하기위해 IEEE가 정의한 인터페이스
  

  

  
  

• Thread life Cycle
  

  

  
  

Abstraction and Decomposition

• Complexity 문제 해결
  - Abstraction + Decomposition = Layered Architecture
  
  

  

   - API (Application Programming Interface) : Layer(계층)와 Layer 사이의 통신을 위해 정의 된 호출 규약 (system call 등)
  
  

• Layering Principle
  - 위의 계층은 아래 계층이 제공하는 기능(API)만을 사용할 수 있으며 반대의 경우는 발생하지 않아야 한다.
  

Process Creation and Termination

• 일반적인 Process 생성 순서
  1. OS는 Code를 Code Segment에 저장
  2. OS는 전역 변수를 Data 영역에 저장
  3. 초기화된 Stack과 Heap 생성
      ( http://winwoo.tistory.com/18 ' Process 초기화 '참고 )
  4. Process의 정보를 담은 PCB를 malloc 시킴
  5. 만들어진 PCB를 Ready Queue에 Add
  
  

• 유닉스(Unix)계열의 경우 Process 생성 방법
  1. System Boot 시 0번(첫번째) Process만 일반적인 process 생성 방식으로 생성
  2. 이후 모든 Process는 'Cloning'방법으로 생성
      -ex) system Call : fork();
  
  

• Cloning Process 생성 방법
  - Parent Process : Process Cloning을 초래하는 기존의(첫번째) Process
  - child Process : Parent Process로 부터 만들어지는 새로운 Process
  - fork() : Parent Process가 Child Process를 생성하기 위해 System call 함수
  - fork() logic
      1. OS가 현재 fork()를 호출한 Parent Process 수행 중단
      2. Parent Process의 Context 스냅샷 저장
      3. 저장한 스냅샷 그대로 Copy
      4. Child Process 생성 완료
          -> 단, PID(Process Id) 는 다름
  -fork()의 단점 : Parent Process와 다른 형태의 Process는 생성할 수 없다.
  -fork() 보완 : fork() 이후 exec() 호출
  -exec() : fork()를 이용해 copy한 process에 File System에 있는 Process Data를 Override 시킴
      -> 이미 생성된 Copy Process의 내용을 무시하기 때문에 좋지 않은         logic
  -wait() : 생성한 Child Process의 Id를 받아 Child Process가 종료 될 때 까지 Parent Process를 기다리게 함
  -exit() : Process를 종료한다. 종료 시 Code, resource, data structure등 모두 날라가지만, exit Status라는 자료구조는 가지고 있다.
  (이후 Process는 zombi State가 된다.)

  

  
  
  

• Zombi State
  -exit() 이후에 Parent Process가 자신의 exit status를 읽어가기를 기다리는 Process의 상태
  

  
  

• Shell 또는 CLI(Command Line Interrupt)
  -사용자가 입력한 명령어를 입력으로 받아들여 새로운 Process를 수행시키는 프로그램
  

• COW(Copy on Write)
  - fork()시 바로 Override 되는 단점 보완
  - Process context를 fork()시점에 복사하지 않고, Data Segment에 새 값이 쓰여질 때 복사하는 기법

Context Switching

• Context Switching이란?
  - 현재 수행중인 Process의 Context state를 저장하고 다음 수행 될 Process의 Context state를 불러오는 작업
  
  

• Context Saving
  - Context Swithcing이 일어날 경우 현재 Process의 Context를 저장하는 작업
  
  

• Context 종류 및 Saving유무
  (Context별 설명은 http://winwoo.tistory.com/16 'Program State' 참고)
  - Memory Context : 필요한 Data만 Saving
  - CPU Register Context : 반드시 모든 Data Saving
      -> saving 장소 : 일반적으로 한단계 아래의 저장장치로 데이터를
                        대피시키기 때문에 CPU Register는 Main Memory로 대피
  - Kernel Context : Saving 필요 없음
  
  

• Interrupt Service Routine이 발생 했을 때
   ( Context Switching 발생 -> HW가 실행)
  다음과 같은 순서로 Stack에 저장
  1. Interrupt가 발생하기 전 PSW 저장
  2. Interrupt가 끝나고 돌아올 주소 저장
      - 돌아올 주소는 HW가 PC(Program Count)에서 가져옴

• 초기 Process 생성 시 Stack 초기화
  

- Context Switching Mechanism이 동작하기 위해선 한번이라도 Context Switching이 일어나야 된다. 하지만 Process가 처음 생성될 경우 임의의 Stack을 만들어 준다.

Process Scheduling

• Process Scheduling 이란
  - OS가 여러 Process중 CPU에 할당 할 Process를 정하는 방법
  
  

• Scheduling 구성 요소
  - Policy : 다음에 수행될 Process를 선택하는 기준
  - Mechanism : CPU를 한 Process에서 다른 Process로 넘겨주는 방법                     (Dispather)
  
  

• Dispatcher
  1. Dispatcher Loop
      {
          1.주어진 Process 가동
          2.가동 중 중단 요청시 안전한공간으로 해당 Process 저장
          3.다른 Process Load
      }
      - 무한 Loop
  2. 호출 방법
      - Non Preemptive Scheduling ( SW Interrupt 사용 -> Trap )
          Process가 자발적으로 CPU를 양보하여 다른 Process를 수행하는         Scheduling (ex) I/O에서 Block할 경우
      - Preemtive Scheduling ( HW Interrupt 사용 -> Timer사용 )
          OS가 강제로 Process로부터 CPU를 빼앗아 다른 Process를
          수행하는 Scheduling
  
  

• Process Status Word(PSW)
  -OS란 Kernel mode에서 사용되는 *<함수 library>라고 할 수 있다.
  *함수 library 종류
      - System Call : OS의 Kernel이 제공하는 서비스를
                                   응용프로그램에요청하기 위한 인터페이스
      - Interrupt Service Routine
  - PSW Register 안의 특정 bit를 mode bit로 사용하여
   'Kernel Mode'와 'User Mode' 구분

  
  

*본 자료는 서울대학교 홍성수 교수님의 '운영체제' 수업을 바탕으로 개인적으로 정리하여 올립니다. 관련 이미지 자료는 홍성수 교수님 수업 PPT자료가 출처임을 알립니다. 문제 시 말씀해주시면 삭제 조치 하겠습니다. 감사합니다.

Process Concept

• Process : OS에서 프로그램을 수행시키는 기본 주체
  

- Runtime System의 수행 주체

- CPU나 다른 자원을 할당 받는 주체

- Process는 OS에서 가장 중요한 단위

• Decomposition
  

- 복잡한 문제를 단순한 여러 개의 문제로 나누어 처리하는 방법론

• Program과 Process의 차이

- Program : 저장매체에 저장된 수동적인 Code Sequence ( 수동적 )

- Process : Program을 실행할 때 일어나는 일 ( 능동적 )

(실행 시 메모리 할당 및 CPU할당 등 다양한 일을 포함)

• Program State
  - 무언가 Program이 실행될 때 모든 Data를 말한다.
      1. Memory ( Memory Context 
          - Code : 기계어
          - Data : Program 전역 변수
          - Stack : Program 지역 변수
          - Heap : Program 동적 메모리 공간
      2. CPU ( H/W Context )
          - Register value
      3. Per - Process Kernel Info ( System Context )
  
  

• Execution Stream
  - Process가 지금까지 수행한 모든 명령어들의 순서
  
  

• Process 정리
  - 수행중인 Program -> State 필요 -> State 위에 Thread of Control
  또는 excution Stream 존재
  
  

• Multi Programming
  - 여러개의 Active한 Process가 Memory에 올라가 있는 경우
  
  

• Swapping ( Main Memory의 공간이 작을 때 사용 )
  - 메모리 부족문제를 해결하기 위해 CPU를 사용하지 않는 일부 Process의 데이터를 Memory에서 다른 저장 장치로 옮기고 CPU를 사용할 Process의 데이터를 Memory에 Load 한다.
  
  

• Process Control Block (PCB)
  - OS가 가지고 있는 Process의 정보
  
  

• Process Table
  - 여러개의 PCB를 Array로 관리
  
  

• State Transition
  - Process Life Cycle : Process가 생성되었을 때 부터 종료될 때 까지 발생하는 일련의 상태 변화
  
  

- Ready State : Active한 Process가 CPU할당을 받지 못한 상태 

(Queue를 통해 관리한다)
*Ready Queue : Ready 상태의 Process들을 관리하기 위한 Queue형태의 자료구조 -> 일반적으로 PCB들을 Linked List로 구현

- Waiting State : 여러개의 Process가 Waiting 상태일 수 있다. 단, Process마다 Waiting 이유가 다를 수 있기 때문에 OS는 Waiting 이유에 따라 별도의 Queue를 통해  Process들을 관리 한다.

*본 자료는 서울대학교 홍성수 교수님의 '운영체제' 수업을 바탕으로 개인적으로 정리하여 올립니다. 관련 이미지 자료는 홍성수 교수님 수업 PPT자료가 출처임을 알립니다. 문제 시 말씀해주시면 삭제 조치 하겠습니다. 감사합니다.