9. 경쟁 상태(Race Condition)

공유 자원에 대해 여러 프로세스가 동시에 접근할 때, 결과 값에 영향을 줄 수 있는 상태
➡️ 동시 접근 시

"경쟁상태가 발생하는 경우"

1. 커널 작업을 수행하는 중에 인터럽트 발생
   • 문제점 : 커널 모드에서 데이터를 로드하여 작업을 수행하다 인터럽트가 발생하여 같은 데이터를 조작하는 경우
   • 해결법 : 커널 모드에서 작업을 수행하는 동안, 인터럽트를 disable 시켜 CPU 제어권을 가져가지 못하도록 한다.
2. 프로세스가 System Call을 하여 커널 모드로 진입하여 작업을 수행하는 도중에 문맥 교환(Context Switching)이 발생할 때.
   • 문제점 : 프로세스 A가 커널 모드에서 데이터 조작 중, 시간이 초과되어 CPU 제어권이 프로세스 B로 넘어가 같은 데이터를 조작하는 경우.(프로세스 B가 작업에 반영되지 않음)
   • 해결법 : 프로세스가 커널모드에서 작업을 하는 경우 시간이 초과되어도 CPU 제어권이 다른 프로세스에게 넘어가지 않도록 함.
3. 멀티 프로세서 환경에서 공유 메모리 내의 커널 데이터가 접근할 때.
   • 문제점 : 멀티 프로세서 환경에서 여러 CPU(멀티 코어)가 동시에 커널 내부의 공유 데이터에 접근하여 조작하는 경우
   • 해결법 : 커널 내부에 있는 각 공유 데이터에 접근할 때마다, 그 데이터에 대한 lock/unlock을 하는 방법

---

10. 세마포어 & 뮤텍스

공유된 자원에 여러 프로세스가 동시에 접근하면서 문제 발생할 수 있다.
이때 공유된 자원의 데이터는 한 번에 하나의 프로세스만 접근할 수 있도록 제한을 두어야 한다.

이를 위해 나온 것이 세마포어

1. 세마포어

멀티 프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법

동기화 대상이 여러 개일 경우 접근할 수 있는 최대 허용치만큼 접근을 허용하게 한다.

✔️ 임계 구역(Critical Section)

• 여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분

  공유 데이터를 여러 프로세스가 동시에 접근할 때 잘못된 결과를 만들 수 있기 때문에, 한 프로세스 임계 구역을 수행할 때는 다른 프로세스가 접근하지 못하도록 한다.

세마포어 P, V 연산

P : 임계 구역 들어가기 전에 수행 (ㅍ로세스 진입 여부를 자원의 개수(S)를 통해 결정)

V : 입계 구역에서 나올 때 수행 (자원 반납 알림, 대기 중인 프로세스를 깨우는 신호)

🎨 구현 방법

P(S);

// -- 임계 구역 --

V(S)

procedure P(S)   //--> 최초 S값은 1임
    while S=0 do wait  //--> S가 0면 1이 될때까지 기다려야 함
    S := S-1   //--> S를 0로 만들어 다른 프로세스가 들어 오지 못하도록 함
end P

--- 임계 구역 ---

procedure V(S) //--> 현재상태는 S가 0임
    S := S+1   //--> S를 1로 원위치시켜 해제하는 과정
end V

이를 통해, 한 프로세스가 P 혹은 V를 수행하고 있는 동안 프로세스가 인터럽트 당하지 않게 된다. P와 V를 사용하여 임계구역에 대하 상호배제 구현이 가능하게 되었다.

2. 뮤텍스

임계 구역을 가진 스레드들의 실행시간이 서로 겹치지 않고 각각 단독으로 실행되게 하는 기술
"상호배제의 약자이다."

해당 접근을 조율하기 위해 lock과 unlock을 사용한다.

• lock : 현재 임계 구역에 들어갈 권한을 얻어옴 (다른 프로세스가 임계 구역 수행 중이면(lock상태) 종료할 때까지 대기
• unlock : 현재 임계 구역을 모두 사용했음을 알림. (대기 중인 다른 프로세스/스레드가 임계 구역에 진입할 수 있음)

뮤텍스 알고리즘

1. 데커 알고리즘
   flag와 turn 변수를 통해 임계 구역에 들어갈 프로세스/스레드를 결정하는 방식
   • flag[n] : 프로세스 n이 임계구역에 진입할때 0과 1로 나타내는 함수.
   • turn : 누가 임계구역에 들어갈 차례인지 나타내는 변수

while(true) {
    flag[i] = true; // 프로세스 i가 임계 구역 진입 시도
    while(flag[j]) { // 프로세스 j가 현재 임계 구역에 있는지 확인
        if(turn == j) { // j가 임계 구역 사용 중이면
            flag[i] = false; // 프로세스 i 진입 취소
            while(turn == j); // turn이 j에서 변경될 때까지 대기
            flag[i] = true; // j turn이 끝나면 다시 진입 시도
        }
    }
}

// ------- 임계 구역 ---------

turn = j; // 임계 구역 사용 끝나면 turn을 넘김
flag[i] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림

2. 피터슨 알고리즘
   데커와 유사하지만, 상대방 프로세스/스레드에게 진입 기회를 양보하는 것의 차이

while(true) {
    flag[i] = true; // 프로세스 i가 임계 구역 진입 시도
    turn = j; // 다른 프로세스에게 진입 기회 양보
    while(flag[j] && turn == j) { // 다른 프로세스가 진입 시도하면 대기
    }
}

// ------- 임계 구역 ---------

flag[i] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림

3. 제과점 알고리즘
   여러 프로세스/스레드에 대한 처리가 가능한 알고리즘. 가장 작은 수의 번호표를 가지고 있는 프로세스가 임계 구역에 진입한다.

while(true) {
    
    isReady[i] = true; // 번호표 받을 준비
    number[i] = max(number[0~n-1]) + 1; // 현재 실행 중인 프로세스 중에 가장 큰 번호 배정 
    isReady[i] = false; // 번호표 수령 완료
    
    for(j = 0; j < n; j++) { // 모든 프로세스 번호표 비교
        while(isReady[j]); // 비교 프로세스가 번호표 받을 때까지 대기
        while(number[j] && number[j] < number[i] && j < i);
        
        // 프로세스 j가 번호표 가지고 있어야 함
        // 프로세스 j의 번호표 < 프로세스 i의 번호표
    }
}

// ------- 임계 구역 ---------

number[i] = 0; // 임계 구역 사용 종료

세마포어와 뮤텍스 쓰임

세마포어는 여러 스레드가 일정 자원을 사용할 때 사용된다.
뮤텍스는 단일 스레드가 자원을 독점할 때 사용된다.

---

11. 페이징과 세그먼테이션

기법을 쓰는 이유
다중 프로그래밍 시스템에서 여러 프로세스를 수용하기 위해 주기억장치를 동적 분할하는 메모리 관리 작업이 필요하기 때문

메모리 관리 기법

1. 연속 메모리 관리
   "프로그램 전체가 하나의 커다란 공간에 연속적으로 할당되어야 함"

   • 고정 분할 기법 : 주기억장치가 고정된 파티션으로 분할 (내부 단편화 발생)

   • 동적 분할 기법 : 파티션들이 동적 생성되며 자신의 크기와 같은 파티션에 적재 (외부 단편화 발생)

     내부 단편화
     메모리가 고정된 크기의 파티션으로 나뉠 시 프로그램이 파티션에 할당 될 때 파티션의 크기가 프로그램의 필요한 크기보다 클 경우 남는 공간이 발생. 이 남는 공간은 해당 파티션 내에서는 다른 프로세스에 의해 사용될 수 없으므로 낭비되는 메모리가 생긴다

     외부 단편화
     프로그램의 크기에 맞게 메모리 파티션이 동저으로 생성된다. 프로세스가 메모리를 할당받고 해제하는 과정에서 다양한 크기의 메모리 블록이 생기고 사라짐. 시간이 지날수록 이 블록이 흩어져 있어 다른 프로세스가 할당받지 못하는 상황이 발생됨.

2. 불연속 메모리 관리
   "프로그램의 일부가 서로 다른 주소 공간에 할당될 수 있는 기법"

   • 페이지 : 고정 사이즈의 작은 프로세스 조각

   • 프레임 : 페이지 크기와 같은 주기억장치 메모리 조각

   • 단편화 : 기억 장치의 빈 공간 or 자료가 여러 조각으로 나뉘는 현상

   • 세그먼트 : 서로 다른 크기를 가진 논리적인 블록이 연속적 공간에 배치되는 것

     고정 크기 : 페이징
     가변 크기 : 세그먼트

   • 단순 페이징

     • 각 프로세스는 프레임들과 같은 길이를 가진 균등 페이지로 나뉨
     • 물리 메모리의 남는 프레임에 적절히 배치된다
     • 외부 단편화 X
     • 소량의 내부 단편화만 존재

   • 단순 세그먼테이션

     • 각 프로세스는 여러 세그먼트로 나뉨
     • 내부 단편화X, 메모리 사용 효율 개선, 동적 분할을 통한 오버헤드 감소
     • 오버헤드만 발생

   • 가상 메모리 페이징

     • 단순 페이징과 비교해 프로세스 전부를 로드시킬 필요 없음
     • 필요한 페이지가 있으면 나중에 자동으로 불어 들어짐
     • 외부 단편화 없다
     • 복잡한 메모리 관리로 오버헤드 발생

   • 단순 세그먼테이션

---

12. 페이지 교체 알고리즘

페이지 부재 발생 -> 새로운 페이지를 할당해야 함 -> 현재 할당된 페이지 중 어떤 것을 교체할지 정하는 방법

😒 ..좀더 생각해보면

가상 메모리는 요구 페이지 기법을 통해 필요한 페이지만 메모리에 적재하고 사용하지 않는 부분은 그대로 둔다

하지만 결국 메모리는 가득 차게되고, 기존 페이지가 사용된 후에도 자리만 차지할 수 있다.

따라서, 메모리가 가득 차면 추가로 페이지를 가져오기 위해 안쓰는 페이지를 빼고 새로운 페이지를 넣어야 한다.

여기서 어떤 페이지를 뺄지 정해야 한다.

이왕이면 수정되지 않는 페이지를 선택해야 좋다.

• 수정되지 않는 페이지를 교체하는 것이 일반적으로 더 빠르고 효율적이기 때문.
• 수정된 페이지는 메모리에서 변경이 되었기 때문에, 페이지 교체 전에 변경 내용을 디스크에 반영해야 한다.
• 이는 추가적인 I/O 작업을 필요로 한다.

---

Page Reference String

CPU는 논리 주소를 통해 즉정 주소를 요구함

메인 메모리에 올라와 있는 주소들은 페이지 단위로 가져오기 때문에 페이지 번호가 연속적으로 나타나게 되면 페이지 결함이 없다.

따라서 CPU의 주소 요구에 따라 페이지 결함이 일어나지 않는 부분은 생략하여 표시하는 방법이 바로
Page Reference String

1. FIFO 알고리즘

   first-In First-Out. 메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리즘

   victim page : out이 되는 페이지는, 가장 먼저 메모리에 올라온 페이지

   가장 간단한 방법으로, 특히 초기화 코드에서 적절한 방법

   초기화 코드 : 처음 프로세스 실행될 때 최초 초기화를 시키는 역할만 진행하고, 다른 역할은 수행하지 않으므로 메인 메모리에서 빼도 괜찮음.
   

2. OPT(최적 페이지 교체) 알고리즘

   Optimal 알고리즘, 앞으로 가장 사용하지 않을 페이지를 가장 우선적으로 내보냄

   FIFO에 비해 페이지 결함의 횟수를 많이 감소시킬 수 있음

   하지만, 실질적으로 페이지가 앞으로 잘 사용되지 않을 것이라는 보장이 없기 때무에 수행하기 어려운 알고리즘.

3. LRU 알고리즘

   Least-Recently-Used, 최근에 사용하지 않은 페이지를 가정 먼저 내려보내는 알고리즘

   최근에 사용하지 않았으면, 나중에 사용되지 않을 것이라는 아이디에서 나옴.

   OPT의 경우 미래 예측이지만, LRU의 경우 과거를 보고 판단하므로 실질적으로 사용이 가능한 알고리즘.

   OPT 보다는 페이지 결함이 더 일어날 수 있지만, 그나마 최적의 알고리즘 효율을 보여주어
   실제로 사용할 수 있는 페이지 교체 알고리즘에서는 가장 좋은 방법임