Garbage Collection

java에서는 개발자가 코드로 메모리를 명시적으로 해제하지 않기 때문에 Garbage Collector가 더이상 필요없는 객체를 찾아 지우는 작업을 한다.

stop-the-world

GC를 실행하기 위해 JVM이 애플리케이션 실행을 멈추는것.

stop-the-world가 발생하면 GC를 실행하는 쓰레드를 제외한 나머지 쓰레드는 모두 작업을 멈춘다.

GC작업을 완료한 이후에야 중단했던 장업을 다시 시작한다.

어떤 GC알고리즘을 사용하더라도 stop-the-world는 발생한다.

대개의 경우 GC 튜닝이란 이 stop-the-world시간을 줄이는 것.

GC는 두가지 가정 하에 만들어졌다. : weak generational hypothesis

• 대부분의 객체는 금방 접근 불가능 상태(unreachable)가 된다.
• 오래된 객체에서 젊은 객체로의 참조는 아주 적게 존재한다.

이 가정의 장점을 최대한 살리기 위해 HotSpot VM에서는 크게 2개의 물리적 공간을 나누었다.(Young/Old)

• Young Generation 영역

  새롭게 생성한 객체의 대부분이 여기에 위치한다.

  대부분의 객체가 금방 접근 불가능 상태가 되기 때문에 매우 많은 객체가 Young 영역에 생성되었다가 사라진다. 이 영역에서 객체가 사라질때 Minor GC가 발생한다고 말한다.

• Old Generation 영역

  접근 불가능 상태로 되지 않아 Young영역에서 살아남은 객체가 여기로 복사된다. 대부분 Young 영역보다 크게 할당되며, 크기가 큰 만큼 Young 영역보다 GC는 적게 발생한다. 이 영역에서 객체가 사라질 때 Major GC(또는 Full GC)가 발생한다고 말한다.

   

• Permanent Generation 영역(Method Area)

  객체나 억류(intern)된 문자열 정보를 저장하는 곳.

  Old영역에서 살아남은 객체가 영원히 남아있는 곳은 아니다. 이 영역에서 GC가 발생할 수도 있는데, 여기서 GC가 발생해도 Major GC 횟수에 포함된다.

Old 영역에 있는 개체가 Young 영역의 객체를 참조한다면?

Old 영역에는 512바이트의 덩어리(chunk)로 되어있는 card table이 존재한다.

card table에는 old 영역에 있는 객체가 young 영역의 객체를 참조할 때마다 정보가 표시된다. young영역의 GC를 실행할 때에는 old 영역에 있는 모든 객체의 참조를 확인하지 않고, 이 카드 테이블만 뒤져서 GC대상인지 식별한다.

카드 테이블은 write barrier를 사용하여 관리한다. write barrier은 Minor GC를 빠르게 할 수 있도록 하는 장치이다. wirte barrier 때문에 약간의 오버헤드는 발생하지만 전반적인 GC 시간은 줄어들게 된다.

Young Generation

• Eden 영역
• Survivor 영역 (2개)

1. 새로 생성한 대부분의 객체는 Eden 영역에 위치한다.
2. Eden 영역에서 GC가 한 번 발생한 후 살아남은 객체는 Survivor 영역 중 하나로 이동된다.
3. Eden 영역에서 GC가 발생하면 이미 살아남은 객체가 존재하는 Survivor 영역으로 객체가 계속 쌓인다.
4. 하나의 Survivor 영역이 가득 차게 되면 그 중에서 살아남은 객체를 다른 Survivor 영역으로 이동한다. 그리고 가득 찬 Survivor영역은 아무 데이터도 없는 상태로 된다.
5. 이 과정을 반복하다가 계속해서 살아남아 있는 객체는 Old 영역으로 이동하게 된다.

HotSpot VM에서는 보다 빠른 메모리 할당을 위해 두가지 기술을 사용한다.

• bump-the-point
• TLABs(Thread-Local Allocation Buffers)

bump-the-point

Eden영역에 할당된 마지막 객체를 추적한다. 마지막 객체는 Eden 영역의 맨 위에 있다. 그리고 그 다음에 생성되는 객체가 있으면, 해당 객체의 크기가 Eden영역에 넣기 적당한지만 확인한다.

만약 해당 객체의 크기가 적당하다고 판정되면 Eden 영역에 넣게 되고, 새로 생성된 객체가 맨 위에 있게 된다. 따라서, 새로운 객체를 생성할 때 마지막에 추가된 객체만 점검하면 되므로 빠르게 메모리 할당이 이루어진다.

그러나, 멀티 스레드 환경에서 Thread-Safe하기 위해 만약 여러 스레드에서 사용하는 객체를 Eden영역에 저장하려면 lock이 발생할 수 밖에 없고, lock-contention때문에 성능은 매우 떨어질 것이다. 이를 해결한 것이 TLABs이다.

TLABs 각각의 스레드가 각각의 몫에 해당하는 Eden 영역의 작은 덩어리를 가질수 있도록 하는 것이다. 각 쓰레드에는 자기가 갖고 있는 TLAB에만 접근할 수 있기 때문에, bump-the-point라는 기술을 사용하더라도 아무런 락 없이 메모리 할당이 가능하다.

Old Generation

old 영역은 기본적으로 데이터가 가득 차면 GC를 실행한다.

(JDK 7기준)

• Serial GC
• Parallel GC
• Parallel Old GC
• Concurrent Mask & Sweep GC (CMS)
• G1(Garbage First) GC

Serial GC (-XX:+UseSerialGC)

Old 영역에 살아있는 객체를 식별(Mask)한다. 그 다음에 heap의 앞 부분부터 확인하여 살아 있는 것만 남긴다(Sweep). 마지막 단계에서는 각 객체들이 연속되게 쌓이도록 힙의 가장 앞부분부터 채워서 객체가 존재하는 부분과 객체가 없는 부분으로 나눈다(Compaction).

Serail Gc는 적은 메모리와 CPU 코어 개수가 적을 때 적합한 방식이다.

Serial GC는 운영 서버에서 절대 사용하면 안되는 방식이다. 데스크톱의 CPU 코어가 하나만 있을 때 사용하기 위해 만든 방식으로, 애플리케이션의 성능이 많이 떨어질 수 있다.

Parallel GC (-XX:+UseParallelGC)

Serial GC와 기본적은 알고리즘은 같다. 그러나 Parallel GC는 GC를 처리하는 쓰레드가 여러 개이다. 그렇기 때문에 더 빠르게 객체를 처리할 수 있다. Parallel GC는 메모리가 충분하고 코어의 개수가 많을 때 유리하다.

Parallel Old GC (-XX:+UseParallelOldGC)

앞서 설명한 Parallel GC와 비교하여 Old 영역의 GC 알고리즘만 다르다. 이 방식은 Mark-Summary-Compaction 단계를 거친다. Summary 단계는 앞서 GC를 수행한 영역에 대해서 별도로 살아 있는 객체를 식별한다는 점에서 Mark-Sweep-Compaction 알고리즘의 Sweep 단계와 다르며, 약간 더 복잡한 단계를 거친다.

CMS GC (-XX:+UseConcMarkSweepGC)

초기의 Initial Mark 단계에서는 클래스 로더에서 가장 가까운 객체 중 살아 있는 개체만 찾는 것으로 끝낸다. 따라서, 멈추는 시간은 매우 짧다. 그리고 Concurrent Mark단계에서는 방금 살아있다고 확인한 객체에서 참조하고 있는 개체들을 따라가면서 확인한다. 이 단계의 특징은 다른 스레드가 실행 중인 상태에서 동시에 진행된다는 것이다.

그 다음 Remark 단계에서는 Concurrent Mark 단계에서 새로 추가되거나 참조가 끊긴 객체를 확인한다. 마지막으로 Concurrent Sweep 단계에서는 쓰레기를 정리하는 작업을 실행한다. 이 작업도 다른 스레드가 실행되고 있는 상황에서 진행한다.

이러한 단계로 진행되는 GC방식이기 때문에 stop-the-world 시간이 매우 짧다. 모든 애플리케이션의 응답 속도가 중요할 때, CMS GC를 사용하며, Low Latency GC라고도 부른다.

하지만, 단점도 존재한다.

• 다른 GC방식보다 메모리와 CPU를 많이 사용
• Compaction단계가 기본적으로 제공되지 않는다.

조각난 메모리가 많아 Compaction 작업을 실행하면 다른 GC 방식의 stop-the-world 시간보다 더 길기 때문에 Compaction 작업이 얼마나 자주,오랫동안 수행되는지 확인해야 한다.

G1(Garbage First) GC

G1 GC는 바둑판의 각 영역에 객체를 할당하고 GC를 실행한다. 그러다 해당 영역이 꽉 차면, 다른 영역에서 객체를 할당하고 GC를 실행한다. 즉, 지금까지 영역간 데이터가 이동하는 단계가 사라진 방식이다.

G1 GC의 가장 큰 장점은 성능이다. 지금까지 설명한 방식중 가장 빠르다.

JDK7부터 정식으로 G1 GC를 포함하여 제공하지만, 실 서비스에서 사용하려면 많은 검증기간이 필요할 것으로 보인다.

객체지향 5대 원칙 : SOLID

-      단일 책임 원칙(Single responsibility principle)

-      개방 폐쇄 원칙(Open/closed principle)

-      리스코프 치환 원칙(Liskov substitution principle)

-      인터페이스 분리 원칙(Interface segregation principle)

-      의존관계 역전 원칙(Dependency inversion principle)

* 단일 책임 원칙(Single Responsibility Principle, SRP)

모든 Class는 하나의 책임만 가지며, 그 책임은 완전히 캡슐화되어야 한다. 작성된 class는 하나의 기능만 가지며, 그 Class가 제공하는 모든 서비스는 하나의 책임을 수행하는데 집중되어야 한다. 이는 어떤 변화에 의해 클래스를 변경해야 하는 이유는 오직 하나뿐이어야 한다.

* 개방/폐쇄 원칙(Open/Closed Principle, OCP)

클래스, 모듈 함수 등의 소프트웨어 객체는 확장에 대해 열려있어야 하고, 수정에 대해서는 닫혀 있어야 한다.

수정이 일어나더라도 기존의 구성요소에서는 수정이 일어나지 않아야 하며, 쉽게 확장이 가능하여 재사용을 할 수 있도록 해야한다는 의미이다.

*  리스코프 치환 원칙(Liskov Substitutions Principle, LSP)

리스코프 치환 코드는 상속에 대한 개념이다. 부모 Class가 들어갈 자리에 자식 Class를 넣어도 잘 구동되어야 한다 라는 원칙이다. 서브 타입은 기반 타입이 약속한 규약을 지켜야 한다.

*  인터페이스 분리 원칙(Interface Segregation Principle, ISP)

클라이언트는 자신이 사용하지 않는 메소드에 의존 관계를 맺으면 안된다 라는 원칙이다.

‘하나의 일반적인 인터페이스보다는, 여러 개의 구체적인 인터페이스가 낫다.’

큰 덩어리의 인터페이스들을 구체적으로 작은 단위들로 분리시킴으로써 꼭 필요한 메서드들만 이용할 수 있게 한다. 시스템의 내부 의존성 관계를 느슨하게 하여 리팩토링, 수정, 재배포를 쉽게 할 수 있도록 한다.

*  의존성 역전 원칙(Dependency Inversion Principle, DIP)

1.     상위 모듈은 하위 모듈에 종속되어서는 안된다. 둘 다 추상화에 의존해야 한다.

2.     추상화는 세부사항에 의존하지 않는다. 세부사항은 추상화에 의해 달라져야 한다.

상위 모듈이 하위 모듈에 의존하는 전통적인 의존 관계를 반전시킴으로써, 상위 모듈이 하위 모듈의 구현으로부터 독립되어야 한다.

javascript : Hoisting

Hoist 란?

hoist라는 단어의 사전적 정의는 끌어올리기라는 뜻이다.

자바스크립트에서 끌어올려지는 것은 변수이다.

모든 변수 선언은 호이스트 된다

호이스트란 변수의 정의가 그 범위에 따라 선언과 할당으로 분리되는 것을 의미한다.

변수가 함수 내에서 정의되었을 경우, 선언이 함수의 최상위로,

함수 바깥에서 정의되었을 경우, 전역 컨텍스트의 최상위로 변경이 된다.

선언(Declaration)과 할당(Assignment)

끌어올려지는 것은 선언이다.

//this is inner value
function test(){
    var result = inner();
    console.log("this is "+result);
    function inner(){
        return "inner value";
    }
}

//Syntax error
function test(){
    var result = inner();
    console.log("this is "+result);
    var inner = function(){
        return "inner value";
    }
}

함수 선언이 함수 실행부분보다 뒤에 있더라도 자바스크립트 엔진이 함수 선언을 끌어올린다.

여기서 주의할 점은,

함수 호이스팅은 함수를 끌어올리지만 변수의 값은 끌어올리지 않는다.

Try with resources

JDK1.7 에는 AutoCloseable 인터페이스가 추가됐다.

/**
 * @author Josh Bloch
 * @since 1.7
 */
public interface AutoCloseable {
    void close() throws Exception;
}

인터페이스 추가와 함께 try절에 ()가 들어갈 수 있게 됐다.

public static void main(String[] args) {
    try(FileInputStream fis = new FileInputStream("")){
         
    }catch(IOException e){

    }
}

이런식으로 try(){} 형태로 사용이 가능하며 ()안에 들어올 수 있는건 AutoCloseable 구현체 뿐이다.

이런 문법을 try with resources 라고 부른다.

장점은 다음과 같다.

• try catch 절이 종료되면서 자동으로 close() 메서드를 호출해준다.
• 코드의 길이를 현저히 줄이면서 가독성을 높인다.

try() 구문 안에서 자원을 생성하면, 알아서 close() 를 호출해준다.

해시테이블 HashTable

Concepts

해싱함수(hash function)

• 해싱함수란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길의의 데이터로 매핑하는 함수.
• 매핑 전 데이터 값을 Key, 매핑 후 데이터 값을 해시값(Hash value), 매핑하는 과정을 Hashing이라고 한다.

• 해시함수는 언제나 동일한 해시값을 리턴

• 해당 index만 알면 해시테이블의 크기에 상관없이 데이터에 대단히 빠르게 접근할 수 있다.

• index는 계산이 간단한 함수(상수시간)로 작동한다.

  —> 데이터 엑세스(삽입,삭제,탐색)시 O(1)을 지향한다.

해시테이블(HashTable)

• 해시함수를 사용하며 키를 해시값으로 매핑하고, 이 해시값을 index 혹은 주소 삼아 데이터를 키와 함께 저장하는 자료구조
• 데이터가 저장 되는 곳을 bucket 또는 slot 이라고한다

• 장점

  • 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있다.
  • ex) 하드디스크나 클라우드에 존재하는 무한에 가까운 key들을 유한한 개수의 hash value로 매핑함으로써 작은 크기의 캐쉬 메모리로도 프로세스를 관리할 수 있다.

• Direct-address table : 키의 개수와 동일한 크기의 버킷을 가진 해시테이블

  • 해시 충돌 문제가 발생하지 않는다.
  • 전체 키에 대한 공간을 만들어 놓는다
  • 실제 사용하는 키보다 전체 키가 훨씬 많은 경우 메모리 효율성이 떨어진다.

Problem

• 해시함수는 해쉬값의 개수보다 대게 많은 키 값을 해쉬값으로 변환(many-to-one)하기 때문에,

• 해시 함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 나타내는 해시충돌(collision)이 발생하게 된다.

  

• 현재까지 개발된 거의 모든 해싱함수는 해시충돌을 일으킨다.

• 해시충돌이 해시값 전체에 걸쳐 균등하게 발생하게끔 하는것이 중요하다.

Solve

Chaining

• 하나의 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않는다.
• 해당 버킷에 데이터가 이미 있다면 체인처럼 노드를 추가하여 다음 노드를 가르키는 방식으로 구현(연결리스트)
• 메모리 문제를 야기할 수 있다.

• 시간복잡도

  hashtable size : m , keys : n

  버킷 하나당 n/m = x개의 데이터 이라 가정.

  • 탐색

    매핑 O(1) + 버킷요소 x 탐색 O(x) => O(1+x)

  • 삽입

    매핑 O(1) + 추가 O(1) => O(1)

  • 삭제

    매핑 O(1) + 탐색 O(x) + 삭제 O(1) => O(1+x)

open addessing

• 한 버킷당 들어갈 수 있는 엔트리가 하나쁜인 해시테이블
• 해시함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장할 수 있도록 허용
• 메모리 문제는 발생하지 않지만, 해시충돌이 생길 수 있다.
• 특정 해시값에 키가 몰리게 되면 효율성이 크게 떨어진다.

ex) 해시함수가 '키 값을 8로 나눈 나머지' 10, 18, 26 순으로 해시테이블에 삽입해보자.

세 숫자 중 첫번째 값 10 을 제외한 18, 26인 원래 버킷(2) 말고 각각 다음 (3) , (4)에 저장된다.

[2] 10

[3] 18

[4] 26

—선형탐사

probing

• open address의 효율성 감소 문제를 해결한다.
• 삽입,삭제,탐색을 수행하기 위해 해시테이블 내 새로운 주소를 찾는 과정

• 선형탐사(Linear probing)

  • 최초 해시값에 해당하는 버킷에 다른 데이터가 저장돼있으면 해시값에서 고정폭을 옮겨 다음 해시값에 해당하는 버킷에 액세스한다.
  • 여기에 데이터가 있으면 또 고정폭 만큼 옮긴다.
  • 특정 해시값 주면 버킷이 모두 채워져 있는 primary clustering 문제에 최약하다

  

• 제곱탐사(Quadratic probing)

  • 이동 폭이 제곱수로 늘어난다.
  • 예를들어, 데이터 엑세스할때 충돌이 일어나면 1^2 칸을 옮긴다. 여기서 또 충돌이 일어나면 2^2 만큼, 그다음엔 3^2 만큼 옮긴다.
  • 여러 개의 서로 다른 키들이 동일한 초기 해시값을 갖는 secondary clustering에 취약하다.

  

• 이중 해싱(double hashing)

  • 탐사할 해시값의 규칙성을 없애서 clustering을 방지한다.
  • 2개의 해시함수를 준비해 하나는 최초의 해시값을 얻을 때, 하나는 해시충돌이 일어났을때 탐사 이동폭을 얻기 위해 사용.

가상메모리 요구페이징(demand paging)

지금까지의 메모라 관리 기법 방식은 프로세스 전체가 메모리 내에 올라와야 한다는 것을 전제로 하고 있다.

프로세스 전체가 메모리 내에 올라오지 않더라고 실행히 가능하도록 하는 기법을 가상메모리라고 한다.

가상메모리는 물리 메로리로부터 사용자 관점의 논리 메모리를 분리시켜 주 메모리를 균인한 크기의 저장 공간으로 구성된 엄청나게 큰 배열로 추상화 시켜준다.

따라서 작은 메모리를 가지고도 큰 가상 주소 공간을 제공한다.

• 장점

  • 사용자 프로그램이 물리 메모리보다 커져도 된다. 즉, 메모리 크기의 제약으로부터 자유로워진다.
  • 각 사용자 프로그램이 더 작은 메모리를 차지하므로 더 많은 프로그램을 동시에 수행할 수 있다. 이에 따라 응답시간은 늘어나지 않으면서 CPU 이용률과 처리율이 높아진다.
  • 프로그램을 메모리에 올리고 스왑하는데 필요한 입/출력 횟수가 줄어든다. 따라서 프로그램들이 보다 빨리 실행된다.
  • 가상메모리 파일의 공유를 쉽게 해주고 공유 메모리 구현을 가능하게 한다.
  • 프로세스 생성을 효율적으로 처리할 수 있는 메커니즘도 제공한다.

• 단점

  • 구현이 어렵고, 잘못 사용시 성능이 현저히 저하될 수 있다.

요구페이징

요구페이징은 필요한 프로그램만 메모리에 적재하는 방법으로 가상 메모리 시스템에서 많이 사용된다. 요구 페이징을 사용하는 가상메모리에서는 페이지들이 실행 과정에서 실제로 필요해질 때 적재 된다.

요구페이징은 일부 스와핑 기법과 유사하다. 프로세스를 실행하고 싶으면 메모리로 읽어 들이며 이때 전체 프로세스를 읽어오지 않고 lazy swapper를 사용한다. lazy swapper는 그 페이지가 필요하지 않는 한 메모리에 적재 되지 않는다.

스와퍼는 전체 프로세스를 관리하지만 페이저(pager)는 프로세스 내의 개별 페이지들을 관리한다. 요구 페이징과 관련해서는 스와퍼보다 페이저가 더욱 가깝다.

swap in 시 페이저는 프로세스가 다시 swap out되기 전에 실제로 사용 될 페이지들이 어떤 것인지 추측한다. 페이저는 프로세스 전체를 스왑인 하는 대신에 실제 피룡한 페이지들만 메모리로 읽어온다. 사용되지 않을 페이지를 메모리로 가져오지 않음으로써 시간 낭비와 메모리 공간 낭비를 줄일 수 있다.

페이저는 어느 페이지가 디스크에만 있고 어느 페이지가 메모리에 올라와 있는지 구별할 수 있어야 한다. 이대 유효/무효 비트 기법을 사용하여 비트가 유효하면 메모리에 있는 것을 의미하고 유효하지 않으면 메모리에 없거나(디스크에 있거나) 해당 페이지가 유효하지 않다는 것이다.

프로세스가 메모리에 없는 페이지를 접근하려 할 때 페이지 부재 트랩(page-fault-trap)을 발생시킨다. 페이징 하드웨어는 페이지 테이블을 이용한 주소 변환 과정에 무효 비트를 발견하고 운영체제에 트랩을 건다.

페이지 부재를 처리하는 과정

1. 프로세스에 대한 내부테이블을 검사해서 그 메모리 참조가 유효/무효 인지 알아 낸다.
2. 무효한 페이지에 대한 참조라면 프로세스는 중단된다. 유효한 참조인 경우 메모리에 없으면 디스크로부터 가져와야 한다.
3. 빈 공간, 자유 프레임(free frame)을 찾는다.
4. 디스크에 새로이 할당된 프레임으로 해당 페이지를 읽어 들이도록 요청
5. 디스크 읽기가 끝나면 이 페이지가 메모리에 있다는 것을 알리기 위해 페이지 테이블을 갱신하며 프로세스가 유지되고 있는 내부테이블을 수정한다.
6. 트랩에 의해 중단되었던 명령을 다시 수행하며 프로세스는 그 페이지가 항상 메모리에 있엇던 것처럼 간주하여 해당 페이지를 접근할 수 있다.

페이지가 적재되고 나면 프로세스는 수행을 계속 하는데 프로세스가 사용하는 모든 페이지가 메모리에 올라올 때 까지 필요할 때마다 페이지 부재가 발생 한다. 일단 필요한 모든 페이지가 적재되고 나면 더 이상 부재 오류가 발생하지 않는데 이것이 순수 요구 페이징(pure deman paging)이다.

모든 프로그램은 참조의 지역성(locality of reference)이라는 성질이 있어서 프로그램의 어느 한 특정 작은 부분만 한 동안 집중적으로 참조하는데 이러한 성질 때문에 요구 페이징은 만족할 만한 성능을 보인다.

locality of reference 참조 지역성

동일한 값 또는 해당 값에 관계뗀 스토리지 위치가 자주 액세스 되는 특성.
참조지역성의 3가지 기본형 : 시간, 공간, 순차 지역성

1) 공간(spatial) 지역성 : 특성 클러스터들의 기억 장소들에 대해 참조가 집중적으로 이루어지는 경향으로, 참조된 메모리의 근처의 메모리를 참조.

2) 시간(temporal) 지역성 : 최근 사용되었던 기옥 장소들이 집중적으로 액세스 되는 경향으로, 참조했던 메모리는 빠른 시간에 다시 참조될 확률이 높다.

3) 순차(sequential) 지역성 : 데이터가 순차적ㅇ로 액세스 되는 경향. 프로그램 내의 명령어가 순차적으로 구성되어있다는 것이 대표적인 경우.

요구 페이징의 필수적인 요구 사항은 페이지 부재 오류 처리 후에 명령 처리를 다시 시작할 수 있어야 한다.

만약 페이지 부재가 명령 인출(instruction fetch)시에 발생 했다면 명령을 메모리로 읽어 온 후 다시 수행을 시도하면 된다.

요구 페이징은 컴퓨터 시스템의 성능에 중요한 영향을 미친다. 페이지 부재가 발생하지 않는 한 실질 접근 시간은 메모리 접근 시간과 같다. 그러나 페이지 부재가 발생하면 디스크로부터 관련되는 페이지를 읽어 온 뒤 필요한 워드를 접근해야 한다.

요구 페이징의 또 다른 특성은 스왑 공간의 관리이다. 스왑 공간에서의 디스크 입/출력은 일반적으로 파일 시스템에서의 입/출력보다 빠른데 그 이유는 스왑 공간은 파일 시스템보다 더 큰 블록을 사용하기 때문이고 또 스왑 공간과 입/출력을 할 때는 파일 찾기(lookup)나 간접 할당 방법 등은 사용하지 않기 때문이다.

Operating System

프로세스 동기화

동기화(Synchronization)

• 동기화의 필요성

은행의 1000원의 잔고가 남아있다고 가정하자.

내가 500원을 찾는 순간 동시에 어머니가 500원을 송금해 오셨다면? 우리는 1000원의 잔고를 예상한다.

Process A : incoming
Register1 = Balance
Register1 = Register1 + 500
Balance = Register1

Process B : outgoing
Register2 = Balance
Register2 = Register2 - 500
Balance = Register2

T0: Process A  Register1 = Balance										R1 = 1000
T1: Process A  Register1 = Register1 + 500						R1 = 1500
T2: Process B  Register2 = Balance										R2 = 1000
T3: Process B  Register2 = Register2 - 500						R2 = 500
T4: Process A  Balance = Register1										B = 1500
T5: Process B  Balance = Register2										B = 500

어떠한 데이터에 대해 동시 작업이 일어났을 경우 처리순서에 상관없이 원하는 결과값을 얻기 위해 동기화가 필요하다.

동기화의 목적은 Data Consistency(데이터 일관성)을 보장해주는 것이다.

유저 동기화는 critical section

커널 동기화는 mutex / semaphore

Critical Section

멀티 프로세스 환경에서 둘 이상의 프로세스가 동시에 접근해서는 안되는 공유 자원의 코드 영역.

임계구역은 시간이 지나면 종료되며, 어떤 프로세스가 임계구역에 접근하기 위해서는 지정된 시간만큼 대기해야 한다.

이때 쓰레드나 프로세스가 배타적인 사용권을 보장받기 위해 세마포어 같은 동기화 메커니즘이 사용된다.

한 프로세스 내의 쓰레드 사이에서만 동기화가 가능. 유저 객체(커널에서 제공하는 객체가 아니다.)

임계구역 문제를 해결하기 위한 3가지 조건

1. Mutual Exclusion(상호배제) : 임계구역에는 무조건 하나의 프로세스
2. Progress(진행) : 임계구역이 비었으면 어느 프로세스가 들어갈지 적절히 선택한다
3. Bounded Waiting(한정 대기) : 기아 상태를 방지하기 위해, 한 번 들어갔다 나온 프로세스는 다음에 들어갈때 제한을 준다.

동기화 방법

상호배제 (MUUual EXclusion)  뮤텍스.

공유데이터가 하나의 프로세스에 의해 독점적으로 사용되는 원칙

entry section
		
		critical section
		
exit section

프로세스는 critical section에 들어가기 전에 entry section 단계에서 출입을 허가받아야한다.

critical section 오직 하나의 프로세스만 존재하도록 한다.

동시프로그래밍 환경(멀티 프로세스 및 멀티 쓰레드 같은)에서 공유 불가능한 자원 처리 (critical section과 구분)

DB의 프로그램에서는 자동적인 부가기능으로 지원되지만, OS의 경우는 사용자의 요구에 따라 지원된다.

장점 혼란이없고 간단하다.

단점 read/write 두 처리 모두 대기한다.

write는 대기하는게 맞지만, read는 데이터를 변화시키지 않으므로 상관없다.

하지만 상호배제는 read도 대기해야한다.

→ 해결법

kernel자체가 하나의 커더란 critical section의 역할을 하는 것.

[Spin lock]

0 : critical section가 비어있다. 사용 가능 .

1 : critical section안에 다른 프로세스가 들어와 있는것.

Spin lock이 1일 경우 다음 수행을 기다리는 프로세스는 lock을 계속 돌게된다.

exit section에 의해 프로세스가 처리되었는지를 인식해 spin lock을 조정한다.

장점 : "조금만 기다리면 바로 쓸 수 있는데 굳치 context switching을 해서 부하를 줄 필요가 있나?"

스핀락을 잘 사용하면 context switching을 줄여 효율을 높일 수 있다.

[Sleep lock] — 세마포어

lock이 1일 경우 기다리던 프로세스는 sleep을 하게 되는 것.

critical section내에 프로세스의 작업이 끝나게 되면 sleep중인 프로세스를 깨워 처리하게 된다.

—두개의 차이

프로세스가 exit section에 도착했을때.

spin lock은 lock으로 접근해 1로 바꾼다 : waiting process가 항시 대기하며 값이 바뀌기를 기다리고 있으므로 lock만 바꿔주면 된다.

sleep lock은 sleeping process를 깨운다.

But, 동시에 2개 이상의 프로세스가 접근하면 상호배제 불가.

A와 B가 동시에 접근해서 lock 이 0인걸 확인했다.

A는 0을 1로 바꿨고, B는 read만 수행하고 context switching이 발생했다.

B는 다음 작업이 수행하게 될때 이미 read 했기때문에, 다시 확인하지 않고(A가 1로 바꿔놨는데 0인줄 알고) 데이터에 접근한다.

해결방법 : read/write를 하나의 명령어로 만들어 놓는다.

피터슨의 알고리즘

상호배제를 위한 병렬프로그래밍 알고리즘.

do{
  flag[me] = true; //임계 구역 사용을 원함 
  turn =! me; //me 프로세스의 차례가 아님 
  while(flag[me]&&turn =! me); //me 프로세스가 사용을 원하지만, 턴은 아니면 대기  
  **critical section**
  flag[me]=false; //임계구역 사용이 끝나면 폴스로 바꿔준다. 
  **remainder section**
} while(true);

그러나 프로세스가 많이 몰리면 계속 while문을 대기해야 하는데 이를 busy waiting(바쁜 대기)상태라고 부른다.

세마포어(Semaphore)

critical section, mutex는 동기화에 있어서 동시에 하나의 쓰레드만 실행되게 하지만, 세마포어는 지정된 수만큼의 쓰레드가 동시에 실행되도록 동기화하는 것이 가능.

• 임계구역에 들어가기 전 스위치를 사용중으로 놓고 들어간다.

• 이후에 도착하는 프로세스는 앞의 프로세스가 작업을 마칠때까지 기다린다.

• 프로세스가 작업을 마치면 세마포어는 다음 프로세스에 임계구역을 사용하라는 동기화 신호를 보낸다.

• 임계구역이 잠겼는지 직접 점검하건, 바쁜 대기를 하거나, 다른 프로세스에 동기화 메시지를 보낼 필요가 없다.

• 세마포어에서 잠금이 해제되기를 기다리는 프로세스는 세마포어 큐에 저장되어 있다가 wake_up신호를 받으면 큐에서 나와 임계구여에 진입.

• 함수 P는 임계구역 들어가기전에 수행 / V는 나올때 수행

• 2개의 공유자원을 가지고 3개의 프로세스가 작업할 때 (Rs=2;)

  1. 프로세스 P1은 RS 값을 1 감소시키고 임계구역에 진입한다.
  2. 프로세스 P2도 RS 값을 1 감소시키고 임계구역에 진입한다.
  3. P3은 RS가 0이므로 대기.
  4. P1이 작업을 마치고 V()를 실행하면 RS값은 1이 되고 wake_up신호가 프로세스 P3에게 전달
  5. P3 임계구역 진입

• 문제점

  세마포어를 잘못 사용하면 임계구역을 보호할 수 없다.

  (1) P() - P() : wake_up신호가 발생하지 않아 무한대기에 빠진다.

  (2) V() - P() : 상호배제가 보장되지 않는 경우

   

MUTEX vs Semaphore

세마포어는 뮤텍스가 될 수 있지만 뮤텍스는 세마포어가 될 수 없다. 뮤텍스는 상태가 0,1 뿐인 binary 세마포어

세마포어는 소유할 수 없는 반면 뮤텍스는 소유할 수 있고 소유자가 이에 책임을 진다.

뮤텍스는 1개만 동기화가 되지만 세마포어는 하나 이상의 동기화를 할 수 있다.

ex ) 변기가 3개가 있는 화장실에서

각각의 변기 앞에 3줄로 줄을 선다 —> 뮤텍스

화장실 문 앞에 한줄로 줄을 선다 —> 세마포어

데드락(DeadLock: 교착상태)

프로세스들이 서로 작업을 진행하지 못하고 영원히 대기상태로 빠지는 현상.

프로세스 사이에 할당된 자원의 충돌로 인하여 발생하게 된다.

2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태.

cf) starvation - OS가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제

교착상태 - 자연적으로 일어나는 문제

데드락은 한 시스템 내에서 다음의 네가지 조건이 동시에 성립할 때 발생한다.

아래의 네 가지 조건 중 하나라도 성립하지 않도록 만든다면 교착 상태를 해결할 수 있다.

• 상호배제 (Mutual exclusion)

  한 번에 한 프로세스만 사용 가능

• 점유대기(Hold and wait)

  최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.

• 비선점(No preemption)

  빼앗을 수 없다.

• 순환대기(Circular wait)

  프로세스의 집합 {P0, P1, ,…Pn}에서 P0는 P1이 점유한 자원을 대기하고 P1은 P2가 점유한 자원을 대기하고 P2…Pn-1은 Pn이 점유한 자원을 대기하며 Pn은 P0가 점유한 자원을 요구해야 한다.

데드락 처리

1. 예방

   교착상태 발생조건 중 하나를 제거하면서 해결 -> 자원 낭비가 심하다

2. 회피

   은행원 알고리즘

   • 프로세스가 자원을 요구할 때 , 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피.
   • 안정상태면 자원 할당, 아니면 다른 프로세스들이 자언을 해지할때까지 대기.

식사하는 철학자 문제

철학자가 스테이크를 먹기 위해 양옆의 포크를 동시에 들어야한다.

해결책

• n명이 앉을 수 있는 테이블에서 철학자를 n-1명 앉힌다.
• 한 철학자가 젓가락 두개를 모두 집을 수 있는 상황에서만 젓가락 집도록 허용
• 누군가는 왼쪽 젓가락을 먼저 집지 않고 오른쪽 젓가락을 먼저 집도록 허용

—> Synchronization을 구현하는 것은 사용자의 필요성에 의해 각자에게 맡겨진 것이다.

어떠한 1명이 실수로 잘못 구현하면 심각한 문제 발생. —> 해결방안 : 모니터

모니터

• 시스템 호출과 같은 개념. 인터페이스만 제공한다
• 임계구역으로 지정된 변수나 자원에 접근하고자 하는 프로세스는 직접 P()나 V()를 사용하지 않고 모니터에 작업 요청을 한다.
• 모니터는 요청받은 작업을 모니터 큐에 저장한후 순서대로 처리하고 그 결과만 해당 프로세스에 알려준다.
• 사용자 입장에서는 복잡한 코드를 실행하지 않아서 좋고, 시스템 입장에서는 임계구역을 보호할 수 있어서 좋다.