Os03

OS03

Process Synchronization

---

등장 배경

• 공유된 데이터에 동시에 접근하는 것은 데이터 불일치를 초래할 수 있다.

Critical Section Problem

• 각각의 프로세스는 Critical Section(임계 영역)을 가진다.
• 하나의 프로세스가 임계영역 안에 있을 때 다른 프로세스들은 해당 영역에 진입할 수 없다.
• 모든 프로세스는 entry section에 있는 critical section에 진입하기 위해선 허가를 받아야 한다.

Critical Section Problem 해결책

Mutual Exclusion

• 만약 어떤 프로세스가 임계영역에서 실행된다면 다른 프로세스들은 그들 내부의 임계 영역에서 실행될 수 없다.

Progress

• 만약 어떠한 프로세스도 임계 영역에서 실행되고 있지 않고 임계 영역에 진입하길 원하는 프로세스가 존재할 때 크리티컬에 진입할 수 있는 프로세스를 선택하는 과정은 무한정 연기될 수 없다.

Bounded Waiting

• 프로세스들이 진입 요청을 생성하고 해당 요청이 승인되기 전에 프로세스들이 임계 영역에 진입할 수 있는 횟수의 제한이 반드시 존재해야 한다.

OS에서의 Critical-Section 처리

Preemptive

• kernel mode일 때 프로세스가 선점하도록 허락한다.

Non-Preemptive

• kernel mode가 끝날 때까지 동작한다.

Peterson’s Solution

• turn과 flag 둘 중 하나가 만족하는 프로세스만 임계 영역에 진입하도록 허락해주는 방법

Mutex Locks

• acquire()을 이용하여 임계영역에 진입하고 release()를 이용하여 임계 영역을 해제한다.
• acquire()과 release()는 한 개의 명령으로 수행된다.
• 이 해결 방법은 busy waiting을 얻는다.

Semaphore

• Mutex locks보다 더욱 정교한 방식으로 프로세스의 활동을 동기화한다.
• 2개의 단일 명령(wait(), signal())에 의해서만 접근될 수 있다.
• 같은 세마포어에 있는 두 프로세스 wait()와 signal()을 동시에 실행할 수 없다.
• wait()와 signal()가 동시에 수행될 수 없기 때문에 critical section problem에서 busy waiting문제가 발생한다.
• busy waiting없이 semaphore를 구현하기 위해서는 큐가 필요하다.
• 해당 큐에서 2가지 연산을 수행한다.
  • block - 연산을 수행하는 프로세스를 waiting queue의 적절한 위치에 위치시킨다.
  • wakeup - waiting queue에서 하나의 프로세스를 제거한 후 해당 프로세스를 ready queue에 위치시킨다.

Counting semaphore

• 정수값이 무한정 늘어날 수 있다.

Binary semaphore

• 정수값은 0과 1사이의 값만 될 수 있다.

Deadlock

• 2개 이상의 프로세스들이 하나의 프로세스에서만 실행되는 하나의 이벤트를 실행하길 무한정 기다리는 현상이다.

Starvation

• 세마포어 큐에서 절대 제거될 수 없는 현상이다.

Priority Inversion

• 상위 우선순위의 프로세스들에게 필요한 lock을 우선순위가 낮은 프로세스들이 가지고 있을 때 발생하는 스케쥴링 문제

전통적인 동기화의 문제

Bounded-Buffer Problem

Readers-Writers Problem

• 변종1 : writer가 공유된 자원을 쓸 수 있는 허가권이 없는한 모든 readers가 계속해서 대기상태에 존재하는 것
• 변종2 : writer가 준비된다면 그 즉시 write를 한다.

  Dining Philosophers Problem

함수형 프로그래밍

• 함수형 프로그래밍에서는 절차형 프로그래밍과는 다르게 한 번 변수에 초기화된 값은 절대로 변경될 수 없다.
• erlang과 Scala에서 데이터 경쟁을 처리하는 접근 방식에 대한 관심이 높아지고 있다.

Main memory

• 메인 메모리와 레지스터가 CPU에서 직접적으로 접근할 수 있는 저장장치이다.
• 메인 메모리는 CPU registers와 메인 메모리 사이에서 stall Cache를 발생시키는 사이클을 가질 수 있다.
• 정확한 연산을 보장하기 위해서 메모리의 보호가 필요하다.

Base and Limit Registers

• base와 limit registers 쌍은 논리적 주소 공간을 정의한다.
• CPU는 user mode에서 생성된 모든 메모리 접근이 해당 유저를 위한 base와 limit 사이에 있는지 확인한다.

Address Binding

• 컴파일된 코드의 주소들은 재할당 가능한 주소들에 bind된다.

명령어와 데이터를 메모리에 바인딩하기

명령어와 데이터를 메모리에 바인딩하는 것은 3단계를 거쳐 일어난다.

• 컴파일 시 : 절대적인 코드가 생성되어야 한다.
• 적재 시 : 만약 메모리 위치가 컴파일 시 알려지지 않았다면 재할당 가능한 코드가 반드시 생성되어야 한다.
• 실행 시 : 만약 프로그램 실행 시 메모리 주소가 옮겨질 수 있다면 런타임동안 바인딩이 되어야 한다.

논리적 vs 물리적 주소 공간

• 논리적 주소 : CPU에 의해 생성되고 가상 메모리로서 참조된다.
• 물리적 주소 : 메모리 유닛에 의해 참조되는 주소이다.
• 논리적, 물리적 주소 공간은 각각의 주소들의 집합이다.

Memory-Management Unit(MMU)

• 가상 메모리를 물리적 메모리에 맵핑해주는 하드웨어 장치이다.

Swapping

• 프로세스들은 잠깐 메모리 밖으로 swap될 수 있다. 잠깐 뒤 나머지 작업을 실행하기 위해 다시 불러와진다.
• Backing store - 메모리 이미지들에 직접 접근이 가능한 메모리를 모두 수용할 수 있는 큰 메모리
• Roll out, Roll in - 낮은 우선순위의 프로세스들은 swap out되고 높은 우선순위의 프로세스들은 swap in되는 방식의 스케줄링 방법이다.
• swap out된 프로세스가 같은 물리적 메모리에 맵핑되지 않아도 된다.

동적 저장소 할당 문제

• First-fit : 첫 번째로 맞는 구멍에 할당
• Best-fit : 가장 딱 맞는 구멍에 할당
• Worst-fit : 가장 큰 구멍에 할당

단편화

• External Fragmentation : 요청들을 처리하기 위한 전체 메모리 공간이 존재하지만 인접하진 않다.
• Internal Fragmentation : 요청보다 더 큰 공간을 할당하였을 때 남는 부분이 사용되지 않는다.
• Compaction : 남은 메모리 공간들을 모두 합쳐서 하나의 큰 블록으로 만드는 작업이다. 이를 이용하여 단편화를 해소할 수 있다.

세그멘테이션

• 세그먼트란 논리적 유닛이다.

세그먼트 구조

• <세그먼트 번호, 주소>
• segment table : 2차원 물리적 주소를 맵핑한다.
  • base : 세그먼트가 존재하는 메모리에서 시작 물리적 주소이다.
  • limit : 세그먼트의 길이를 명시한다.
• Segment-table Base Register(STBR)는 메모리에서 segment table의 위치를 가리킨다.
• Segment-table Length Register(STLR)는 프로그램에 의해 사용되어지는 세그먼트의 갯수를 가리킨다.
• 세그먼트 번호 s는 STLR보다 작아야 유효하다.
• 세그먼트 테이블의 validation bit가 0이면 무허가 세그멘트이다.

페이징

• 외부 단편화를 피하거나 메모리 청크의 사이즈가 바뀌는 문제를 피하기 위한 방법이다.
• 물리적 메모리는 frames이라는 고정된 사이즈의 블록으로 나눠진다.
• 논리적 메모리는 pages라는 같은 크기의 블록으로 나눠진다.
• N pages 크기의 프로그램을 실행시키기 위해서 N 크기의 빈 메모리를 찾아야 한다.
• 논리적 메모리를 물리적 메모리로 맵핑시키기 위하여 page table을 작성한다.

주소 맵핑 전략

• CPU에 의해 생성된 주소는 2가지로 나눠진다.
  • Page number(p) : page table의 번호로 사용된다. 물리적 메모리에서 각 페이지들의 시작 주소를 포함하고 있다.
  • Page offset(d) : 물리적 메모리 주소를 정의하기 위해 base address와 합쳐진다.

내부 단편화 계산

• 페이지의 크기 : 2,048 bytes
• Process size : 72,766 bytes
• 35 pages * 1,086 bytes
• Internal fragmentation : 2048 - 1086 = 962 bytes