기억장치 배치 전략

• 최초 적합(First Fit) : 가능한 영역 중에서 첫 번째 분할 영역에 배치시키는 방법
• 최적 적합(Best Fit) : 가능한 영역 중에서 단편화를 가장 작게 남기는 분할 영역에 배치하는 방법
• 최악 적합(Worst Fit) : 가능한 영역 중에서 단편화를 가장 많이 남기는 분할 영역에 배치하는 방법

배치 전략 중 10K 프로그램이 할당 받는 영역의 번호는 다음과 같다.

• 최초 적합(First Fit) : 10K 프로그램이 들어갈 수 있는 첫 번째 영역은 2번이다.
• 최적 적합(Best Fit) : 10K 프로그램이 들어가고 단편화를 가장 작게 남기는 영역은 4번이다.
• 최악 적합(Worst Fit) : 10K 프로그램이 들어가고 단편화를 가장 많이 남기는 영역은 5번이다.

가상기억장치 구현

• 보조기억장치(하드디스크)의 일부를 주기억장치처럼 사용하는 것으로 가상기억장치에 저장된 프로그램을 실행하려면 가상기억장치의 주소를 주기억장치의 주소로 바꾸눈 주소 변환 작업(매핑)이 필요하다.
• 페이징 기법 : 프로그램을 동일한 크기로 나눈 단위를 페이지라 하며 이 페이지를 블록으로 활용하는 기법

• 세그먼테이션 기법 : 프로그램을 가변적인 크기로 나눈 단위를 세그먼트라 하며, 이 세그먼트를 블록으로 사용하는 기법

• 내부 단변화 : 프로그램이 할당된 후 남는 빈 공간, 영역 크기 16K > 프로그램 크기 14K 인 경우 내부 단편화 2K 발생
• 외부 단편화 : 영역 크기보다 프로그램 크기가 커서 할당되지 않아 남는 빈 공간, 영억 크기 12K < 프로그램 크기 14K 인 경우 외부 단편화 12K 발생

페이징 기법

• 페이지 : 프로그램을 일정한 크기로 나눈 단위(일반적으로 1~4KB)
• 프레임 : 페이지 크기로 일정하게 나누어진 주기억장치 단위
• 주소 변환을 위해서 페이지의 위치 정보를 가지고 있는 페이지 맵 테이블이 필요하다.
• 외부 단편화는 발생하지 않지만 내부 단편화는 발생할 수 있다.
• 장점 : 여러 개의 프로그램을 동시 실행할 수 있어 다중 프로그래밍 정도가 향상된다.
• 단점 : 주소 변환 과정에서 CPU 사용시간이 낭비되고 내부 단편화 문제가 발생한다.

세그먼테이션 기법

• 세그먼트 : 사용자 주소 공간을 논리적인 단위로 나눈 것, 각 세그먼트는 고유한 이름과 크기를 가진다.
• 주소 변환을 위해 세그먼트가 존재하는 위치 정보를 가지고 있는 세그먼트 맵 테이블이 필요하다.
• 장점 : 외부단편화에 의한 기억장치 낭비를 줄일 수 있다.
• 단점 : 세그먼트 크기가 가변적이기 때문에 세그먼트 영역이 다른 세그먼트 영역을 침범하지 않는 기억장치 보호키가 필요하다.

페이지 교체 알고리즘

• 페이지 부재가 발생했을 때 가상기억장치의 필요한 페이지를 주기억장치에 적재하는 데 어떤 프레임을 선택해 교체할 지 결정하는 기법

FIFO(First In First Out)

• 가장 오래 있었던 페이지를 고체하는 기법이다.
• 벨레이디의 모순 현상이 발생한다.(프레임 수가 늘어나면 페이지 부재 수가 줄어들지 않는 현상)

• 위 경우 페이지 부재가 총 9번 발생한다.
• 하지만, Frame 개수가 4개로 늘어나도 페이지 부재는 10번으로 증가한다. => 벨레이디 모순 현상

LRU(Least Recently Used)

• 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법
• 계수기나 스택같은 별로 하드웨어가 필요하며 시간적인 오버헤드가 발생하고, 실제로 구현하기 어렵다.

LFU(Least Frequently Used)

• 사용 빈도가 가장 적은 페이지를 교체하는 기법
• 활발하게 사용되는 페이지는 사용 횟수가 많아 교체되지 않고 사용된다.
• 초기에 많이 사용된 페이지가 그 후루도 사용되지 않을 경우 프레임을 계속 차지할 수 있다.

가상기억창치 관리

1. 페이지 크기
   • 페이지 크기가 작을 경우
     • 페이지 단편화가 가모되고 볼필요한 내용이 주기억장치에 적재될 확률이 적다.
     • 페이지 정보를 가지는 페이지 맵 테이블 크기가 커지고 매핑 속도가 늦어진다.
     • 디스크 접근 횟수가 많아져 전체적인 입출력 시간이 증가한다.
   • 페이지 크기가 클 경우
     • 페이지 정보를 갖는 맵 테이블의 크기가 작아지고, 매핑 속도가 빨라진다.
     • 디스크 접근 횟수가 줄어들어 전체적인 입출력 시간이 감소한다.
     • 페이지 단편화가 증가되고, 한 개의 페이지를 주기억장치로 이동하는 시간이 늘어난다.
2. 구역성(Locality)
   • 어느 순간 특정 페이지만 집중적으로 참조하는 것
   • 시간 구역성
     • 하나의 페이지를 일정 시간 동안 집중적으로 엑세스하는 현상
     • 한번 참조한 페이지는 가까운 시간 내에 계속 참조할 가능성이 높다.
   • 공간 구역성
     • 어느 하나의 페이지를 참조하면 그 근처의 페이지를 참조할 가능성이 높다.
     • 프로세스 실행 시 일정 위치의 페이지를 집중적으로 액세스하는 현상
3. 워킹 셋(Working Set)
   • 프로세스가 일정 시간 동안 자주 참조하는 페이지들의 집합
   • 자주 참조되는 워킹 셋을 주기억장치에 상주시킴으로써 페이지 부재 및 교체 현상이 줄어들어 사용이 안정화된다.
4. 스레싱(Thrashing)
   • 프로세스 처리 시간보다 페이지 교체에 소요되는 시간이 더 많아지는 현상
   • 어떤 프로세스가 실제로 사용하는 프레임 수만큼의 프레임을 갖지 못한 경우 발생
   • 방지 방법 : 다중 프로그래밍 정도 완화, Working Set 이용
   • cf) 다중 프로그래밍 정도 : 얼마나 많은 프로그램을 동시에 수행하는 정도

디스크 스케줄링

• 사용할 데이터가 디스크 상의 여러 곳에 저장되어 있을 경우 디스크 헤드가 움직으는 경로를 결정하는 기법
• 목적 : 처리량 최대화, 응답 시간 최소화, 응답 시간 편차의 최소화

FCFS(First Come First Service)

• 디스크 대기 큐에 가장 먼저 들어온 트랙에 대한 요청을 먼저 서비스하는 기법
• 더 높은 우선순위의 요청이 입력되어도 순사가 바뀌지 않아 공평성이 보장된다.
• 디스크 오버헤드가 적을 때 효율적이며, 오버헤드가 커지면 응답 시간이 길어진다.
• 디스크 대기 큐 : 53,98,183,37,122,14,124,65,67
• 이동 순서 : 53 -> 98 -> 183 -> 37 -> 122 -> 14 -> 124 -> 65 -> 67

SSTF(Shortest Seek Time First)

• 탐색 거리가 가장 짧은 트랙에 대한 요청을 먼저 서비스하는 기법
• 현재 헤드 위치에서 가장 가까운 거리에 있는 트랙으로 헤드를 이동한다.
• 현재 헤드 위치에 가장 가까운 트랙에 대한 요청이 계속 발생하는 경우 먼 거리의 서비스는 무한정 기다리는 기아 상태가 발생할 수 있다.
• 디스크 대기 큐 : 53,98,183,37,122,14,124,65,67
• 이동 순서 : 53 -> 65 -> 67 -> 37 -> 14 -> 98 -> 122 -> 124 -> 183

SCAN

• SSTF가 갖는 탐색 시간의 편차를 해소하기 위한 기법
• 현재 헤드 위치에서 진행 방향이 결정되면 탐색 거리가 짧은 순서에 따라 그 방향의 모든 요청을 서비스 후 역방향의 요청 사항을 서비스한다.
• 오버헤드가 적을 경우 가장 효율적인 기법이다.
• 디스크 대기 큐 : 53,98,183,37,122,14,124,65,67
• 이동 순서 : 53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199 -> 37 -> 14

C-SCAN(Circular SCAN)

• 항상 바깥쪽에서 안쪽으로 한 방향으로만 움직이며 가장 짧은 탐색 거리를 갖는 요청을 서비스하는 기법
• 처음가 마지막을 인접시킨 것과 같은 원형 형태로 디스크를 처리한다.
• 디스크 대기 큐 : 53,98,183,37,122,14,124,65,67
• 이동 순서 : 53 -> 37 -> 14 -> 0 -> 199 -> 183 -> 124 -> 122 -> 98 -> 67 -> 65

프로세스 동기화 배경

• 프로세스가 병행 또는 병렬로 실행될 때 여러 프로세스가 공유하는 데이터의 무결성이 유지되어야 한다.
• 병행 프로세스는 다중 처리 시스템이나 분산 처리 시스템에서 중요 개념으로 사용

임계 구역

• 임계구역 안에서는 공유 변수를 변경, 테이블 갱신, 파일 쓰기 등의 작업을 수행한다.
• 임계구역에는 하나의 프로세스만 접근할 수 있으며, 해당 프로세스가 자원을 반납해야 다른 프로세스가 자원 및 데이터를 사용할 수 있다.
• 한 프로세스가 자신의 임계구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계구역에 들어갈 수 없다.

임계구역 문제 해결 방법

1. 상호 배제 기법
   • 특정 프로세스가 공유 자원을 사용하고 있을 경우 다른 프로세스가 해당 공유 자원을 사용하지 못하게 제어하는 기법
   • 두 개의 프로세스 기준 : 피터슨 알고리즘(두 프로세스가 두 개의 데이터 항목을 공유하여 자원을 사용하는 방법)
   • 여러 개의 프로세스 기준 : Lamport의 빵집 알고리즘(각 프로세스에 번호를 부여하여 자원을 사용하도록 하는 방볍)
2. 진행
   • 자신의 임계구역에서 실행되는 프로세스가 없고 자신의 임계구역으로 진입하려는 프로세스가 있다면 잔류 구역에서 실행 중이지 않은 프로세스들만 임계영역에 진입 대상이 되고, 이 선택은 무한정 연기되지 않음!
3. 한계 대기
   • 프로세스가 자기의 임계구역에 진입하려는 요청을 한 후로부터 요청이 허용될 때까지 다른 프로세스들이 임계영역에 그들 자신의 임계구역에 진입을 허용하는 횟수의 한계가 필요하다.

Mutex Lock(상호 배재)

• Mutex가 지켜주는 덕에 화장실을 한명만 사용할 수 있다.
• 즉, Mutex는 임계구역을 보호하고 프로세스간 경쟁을 방지하기 위해 사용
• boolean available 변수를 사용 => 락의 가용 여부 표시

1
2
3
4
5
6

do {
    //Lock 획득
    임계구역
    //Lock 반환
    나머지 구역
} while(true);

세마포어(Semaphore)

• Mutex와 유사하게 동작하지만 프로세스들이 자신들의 행동을 더 정교하게 동기화 할 수 있는 방법 제공
• 각 프로세스에 제어신호를 전달하여 순차적으로 진행하기 위한 동기화 구현
• 세마포 S = 정수 변수, wait(s)와 signal(s)로만 접근이 가능하다. S = 0인 경우 모든 자원이 사용 중을 의미

1
2
3
4
5
6

//wait(S) => 상호배재 보장
//임계구역에 진입하기 전에 확인
if (S <= 0) //누군가 사용하고 있다면
    S가 양수가 될 때까지 현재 프로세스를 list에서 기다림
else    //임계 구역에 진입이 가능하다면
    S = S - 1;

1
2
3
4
5
6

//Signal(S) => 진행 보장
//임계구역을 떠날 때 실행
if (자원 반환전에 list에서 기다리는 프로세스가 있다면)
    그 중 한개 프로세스를 임계 구역 진입
else     //list에서 기다리는 프로세스가 없다면
    S = S + 1;

Mutex와 세마포어의 차이

Mutex(상호 배재)

• Critical Section을 가진 쓰레드들의 Running time이 서로 겹치지 않게 각각 단독으로 실행되게 하는 기술
• Mutex 객체를 두 쓰레드가 동시에 사용할 수 없다. (1개의 쓰레드만 Critical Section에 접근 가능하도록 하는 기술)
• cf) Critical Section : 각 프로세스에서 공유데이터를 엑세스하는 프로그램 코드부분

세마포어(Semaphore)

• 공유된 자원의 데이터를 여러 프로세스가 접근하는 것을 막는 것
• 만약, 화장실 칸이 4개라면 4개의 프로세스는 사용 가능하고, 나머지 프로세스는 대기해야 한다.

고전적인 동기화 문제

1. 생산자-소비자 문제
   • 생산자가 데이터를 생산하여 입력된 경우에만 접근하도록 구성하는 방식
   • 생산자는 꽉찬 버퍼를 생산하고 소비자는 비어있는 버퍼를 생산한다.
2. 읽기-쓰기 문제
   • 두 Reader가 동시에 공유 데이터를 접근하는 것은 허용하나, 동시에 Writer를 허용하지 않는 방식
   • Writer보다 Reader 요청이 많은 경우 병행성을 높일 수 있다.
3. 식사하는 철학자 문제
   • 5명의 철학자들은 생각하고 먹는 일을 수행(철학자 : 프로세스, 젓가락 : 자원)
   1. 철학자는 양쪽의 젓가락을 사용하여 식사를 하고, 식사를 마친 철학자는 젓가락을 내려놓고 다시 생각한다.
   2. 철학자는 2개의 젓가락을 손에 쥐어야 식사를 할 수 있고, 한 번에 하나씩 잡을 수 있다.
   3. 옆 사람이 식사중이면 젓가락 잡는 것을 대기한다.

5명의 철학자가 동시에 식사를 하게 되면 모두 왼쪽 포크만을 가지게 되고 오른쪽 포크를 대기하는 교착 상태(Deadlock)이 발생한다.

이를 방지하기 위한 방법은 대표적으로 3가지이다.

1. 최대 4명의 철학자들만이 테이블에 앉을 수 있도록 한다. => 젓가락이 하나 남기 때문에 어떤 철학자는 식사가 가능하다.
2. 한 철학자가 동시에 두개의 젓가락을 모두 집을 수 있을 때만 젓가락을 집도록 허용한다.(즉, 임계구역 안에서만 젓가락을 집어야 한다)
3. 비대칭 해결안을 사용한다.(홀수 번 철학자는 왼쪽, 짝수 번 철학자는 오른쪽 젓가락부터 집는다)

교착상태(DeadLock)

• 상호 배제에 의해 나타나는 문제점으로 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상

예방 기법

• 상호 배재 부정 : 한 번에 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다.
• 점유 및 대기 부정 : 프로세스가 실행되기 전 필요한 모든 자원을 할당해 프로세스 대기를 없애거나 자원이 점유되지 않은 상태에서만 자원을 요구하도록 한다.
• 비선점 부정 : 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구 자원을 사용하기 위해 기다리게 한다.
• 환형 대기 부정 : 자원을 선형 순서로 분류해 고유 번호를 할당하고, 각 프로세스는 현재 점유한 고유 번호보다 앞이나 뒤 한쪽 방향으로만 자원을 요구하도록 한다.

회피 기법(Dijkstra 제안한 은행원 알고리즘)

• 안정 상태 : 모든 프로세스가 교착상태를 일으키지 않으면서 각 프로세스가 요구한 최대 요구량만큼 필요한 자원을 할당해 줄 수 있는 상태
• 불안정 상태 : 교착상태의 필수 조건으로 교착상태가 발생할 수 있는 상태

은행원 알고리즘 : 안전상태를 유지할 수 있는 요구만을 수락하고 불안전 상태를 초래할 사용자의 요구는 나중에 만족될 수 있을 때까지 계속 거절하는 알고리즘

1. 각 프로세스마다 할당할 수 있는 최대 자원을 계산한다.
2. 각 프로세스마다 자원을 할당한 후에도 안전 상태를 유지할 수 있는지 확인하고 자원을 할당한다.
3. 추가적인 자원을 할당해도 안전 상태를 유지할 수 있다면 자원을 할당할 수 있다. 하지만 불안전상태가 된다면 교착상태가 되므로 거절한다.

• Available : 각 종류별로 가용한 자원의 개수, Available[i] = k 라면 R[i] 를 K개 사용할 수 있다는 뜻
• Max : 각 프로세스가 최대로 필요로 하는 자원의 개수, Max[i,j] = k 라면 Process[i]가 R[j]를 K개까지 요청할 수 있다는 뜻
• Allocation : 각 프로세스에게 현재 나가있는 자원의 개수, Allocation[i,j] = k 라면 현재 Process[i]가 R[j]를 K개 사용 중이라는 뜻
• Need : 각 프로세스가 향후 요청할 수 있는 자원의 개수, Need[i,j] = k라면 Process[i]가 향후 R[j]를 K개 요청할 수 있다는 뜻
  • Need = Max - Allocation

자원 요청 알고리즘

1. 만약 Request[i] <= Need[i] 이면 2단계로 이동, 아니면 시스템에 있는 개수보다 더 많이 요청했기 때문에 오류로 처리
2. 만약 Request[i] <= Available[i] 이면 3단꼐로 이동, 아니면 요청한 자원이 지금 없으므로 Process[i]는 기다려야 한다.
3. Process[i]에게 할당한 것처럼 시스템 상태정보를 바꿔 본다.
   • Available = Available - Request[i]
   • Allocation[i] = Allocation[i] + Request[i]
   • Need[i] = Need[i] - Request[i]
4. 만약, 이렇게 바뀐 상태가 안전하다면 Process[i]에게 자원을 할당한다. 그렇지 않다면 상태를 원상태로 되돌리고 Request[i]가 만족될 때까지 기다린다.

예를 통해 알아보자. 프로세스 P와 A 자원 10개, B 자원 5개, C 자원 7개가 있을 때 다음과 같은 예시가 있다고 가정하자.

Need 값은 Max - Allocation 으로 구할 수 있으며 이 경우 남은 자원 수는 다음과 같다.

여기서 P[1]이 A 자원 1개와 C 자원 2개를 추가로 요청한다고 가정해보자. 이 때의 Request[1] = (1,0,2) 가 된다.

1. Request[i] <= Need[i]를 검사한다. (1,0,2) <= (1,2,2)이므로 조건을 만족한다.
2. Request[i] <= Available[i]를 검사한다. (1,0,2) <= (3,3,2) 이므로 조건을 만족한다.
3. Process[i]에게 할당한 것처럼 시스템 상태정보를 바꿔 본다.
   • Available[1] = Available[1] (3,3,2) - Request[1] (1,0,2) = (2,3,0)
   • Allocation[1] = Allocation[1] (2,0,0) + Request[1] (1,0,2) = (3,0,2)
   • Need[1] = Need[1] (1,2,2) - Request[1] (1,0,2) = (0,2,0)
4. 위 상태는 안정 상태이므로 Process[1] 의 요청을 즉시 들어줄 수 있다.

위 예시에서는 <P[1], P[3], P[4], P[2], P[0]> 순서로 진행하면 안정 순서열이 된다.

운영체제란?

• 제한된 컴퓨터 각종 자원을 효율적으로 관리하여 사용자에게 편리한 환경을 제공하는 소프트웨어

운영체제 목적

• 처리 능력 : 일정 시간 내에 시스템이 처리하는 일의 양
• 반환 시간 : 시스템에 작업을 의뢰한 시간부터 처리가 완료될 때까지 소요되는 시간
• 사용 가능도 : 시스템 사용할 필요가 있을 때 즉시 가용 가능한 정도
• 신뢰도 : 시스템이 주어진 문제를 정확하게 해결하는 정도

운영체제 기능

• 프로세서 관리
• 기억장치 관리
• 프로세스 관리
• 주변장치 관리
• 파일 및 데이터 관리

프로세스

• 현재 실행중이거나 곧 실행 가능한 PCB를 가진 프로그램
• PCB(Process Control Block) : OS가 프로세스의 대한 중요한 정보를 저장하는 곳으로 각 프로세스가 생성될 때 고유 PCB가 생성되고, 프로세스가 완료되면 PCB는 제거된다.

스레드(Thread)

• 프로세스 내에서의 작업 단위로서 시스템의 여러 자원을 할당받아 실행하는 프로그램 단위
• 스레드 기반 시스템에서 스레드는 독립적인 스케줄링의 최소 단위로서 프로세스 역할 담당
• 하나의 프로세스를 여러 개의 스레드로 생성하여 병행성을 증진시킬 수 있다.
• 공통적으로 접근 가능한 기억장치를 통해 효율적으로 통신한다.

CPU 스케줄링

• 프로세스가 생성되어 실행될 때 필요한 시스템의 자원을 해당 프로세스에 할당하는 것
  • cf) 문맥 교환(Context Switching) : 하나의 프로세스에서 다른 프로세스로 전환할 때 실행하던 프로세스의 상태를 보관하고 새로운 프로세스 정보를 적재하여 실행을 준비하는 것
  • cf) 준비상태 큐(Ready Queue) : 주기억장치에 적재되어 있으면서 CPU에 의해 실행되기를 준비하는 프로세스들로 구성된 리스트

비선점 스케쥴링

• 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케쥴링 기법
• 프로세스가 CPU를 할당받으면 해당 프로세스가 완료될 때까지 CPU를 사용한다.
• 프로세스의 요구를 공정하게 처리할 수 있지만 중요한 작업이 중요하지 않은 작업을 기다리는 경우가 발생한다.

FCFS(First Come First Service)

• 준비상태 큐에 먼저 도착한 순서대로 CPU에 할당하는 기법
• 공평성은 유지되지만 중요한 작업이 중요하지 않은 작업을 기다리게 된다.

SJF(Short Job First)

• 준비상태 큐에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법
• 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에 할당 순위가 밀려 무한 연기(기아) 상태가 발생할 수 있다.

HRN(Hightest Response-ratio Next)

• SJF 기법을 보완한 것으로 대기 중인 프로세스들의 대기시간과 실행시간을 고려하여 우선순위를 결정한다.
• 우선순위 계산식 : (대기시간 + 수행시간) / 수행시간

선점 스케쥴링

• 하나의 프로세스가 CPU를 할당받아 실행중일 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케쥴링 기법
• 우선순위가 높은 프로세스를 빠르게 처리할 수 있지만 많은 Overhead를 초래한다.

Round Robin

• 각 프로세스느 시간 할당량(Time Slice)만큼 CPU를 점유하고 실행이 완료되지 않으면 CPU를 반환하고 준비상태 큐의 가장 뒤로 배치
• 문맥 교환(Context Switching) 효과를 고려하여 시간 할당량을 정한다.
• 시간 할당량이 클수록 FCFS와 같아지고, 시간 할당량이 작을 수록 문맥 교환 및 오버헤드가 자주발생

SRT(Shortest Remaining Time)

• SJF 기법을 선점 형태로 변경한 기법으로 프로세스들 중 남아있는 실행시간이 가장 짧은 프로세스를 다음 프로세스로 선택

다단계 큐 스케쥴링

• 준비완료 큐를 다수의 별도의 큐로 분리하여 각 큐의 독자적인 스케쥴링에 따라 CPU를 할당받는 기법
• 각각의 서로 다른 작업들이 다른 묶음으로 분리될 수 있을 때 사용한다.
• 이전 작업이 실행 중이더라도 우선 순위가 높은 큐에 작업이 들어오면 CPU를 반환해야 한다.
  • cf) 우선순위 : 시스템 프로세스 > 대화형 프로세스 > 일괄처리 프로세스

다단계 피드백 큐 스케쥴링

• 프로세스가 큐들 사이를 이동하는 것을 허용하는 기법이다.
• 프로세스를 CPU 성격에 따라 구분하고 어떤 프로세스가 CPU 시간을 너무 많이 사용하면 한 단계 낮은 우선순위 준비큐로 강등된다.
• 즉, 짧은 프로세스의 경우 FCFS 방식으로 신속하게 실행되고, 긴 프로세스는 낮은 단계의 준비단계 큐로 밀린다.
• 낮은 우선순위 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위 큐로 이동한다. (Aging 기법) -> 기아 상태 예방

* 프로세스 동기화 배경

프로세스가 병행 또는 병렬로 실행될 때 여러 프로세스가 공유하는 데이터의 무결성이 유지되어야 한다.

병행 프로세스는 다중 처리 시스템이나 분산 처리 시스템에서 중요 개념으로 사용

* 임계 구역

한 프로세스가 자신의 임계구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계구역에 들어갈 수 없다

임계구역 안에서는 공유 변수를 변경, 테이블 갱신, 파일 쓰기 등의 작업을 수행한다.

임계구역에는 하나의 프로세스만 접근할 수 있으며, 해당 프로세스가 자원을 반납해야 다른 프로세스가 자원 및 데이터를 사용할 수 있다

* 임계구역 문제 해결 방법

1. 상호 배제 기법

특정 프로세스가 공유 자원을 사용하고 있을 경우 다른 프로세스가 해당 공유 자원을 사용하지 못하게 제어하는 기법

두 개의 프로세스 기준 : 피터슨 알고리즘(두 프로세스가 두 개의 데이터 항목을 공유하여 자원을 사용하는 방법)

여러 개의 프로세스 기준 : Lamport의 빵집 알고리즘(각 프로세스에 번호를 부여하여 자원을 사용하도록 하는 방볍)

2. 진행

자신의 임계구역에서 실행되는 프로세스가 없고 자신의 임계구역으로 진입하려는 프로세스가 있다면, 

잔류 구역에서 실행 중이지 않은 프로세스들만 임계영역에 진입 대상이 되고, 이 선택은 무한정 연기되지 않음!

3. 한계 대기

프로세스가 자기의 임계구역에 진입하려는 요청을 한 후로부터 요청이 허용될 때까지 다른 프로세스들이 임계영역에 그들 자신의 임계구역에 진입을 허용하는 횟수의 한계가 필요

* Mutex Lock

>> Mutex가 지켜주는 덕에 화장실을 한명만 사용할 수 있다.

즉, Mutex는 임계구역을 보호하고 프로세스간 경쟁을 방지하기 위해 사용

boolean available 변수를 사용 => 락의 가용 여부 표시

* 세마포어(Semaphore)

Mutex와 유사하게 동작하지만 프로세스들이 자신들의 행동을 더 정교하게 동기화 할 수 있는 방법 제공

각 프로세스에 제어신호를 전달하여 순차적으로 진행하기 위한 동기화 구현

세마포 S = 정수 변수, wait(s)와 signal(s)로만 접근이 가능하다. S = 0인 경우 모든 자원이 사용 중을 의미

=> 진행 보장

* 고전적인 동기화 문제

1. 생산자-소비자 문제

생산자가 데이터를 생산하여 입력된 경우에만 접근하도록 구성하는 방식

생산자는 꽉찬 버퍼를 생산하고 소비자는 비어있는 버퍼를 생산한다.

2. 읽기-쓰기 문제

두 Reader가 동시에 공유 데이터를 접근하는 것은 허용하나, 동시에 Writer를 허용하지 않는 방식

Writer보다 Reader 요청이 많은 경우 병행성을 높일 수 있다.

3. 식사하는 철학자 문제

5명의 철학자들은 생각하고 먹는 일을 수행(철학자 : 프로세스, 젓가락 : 자원)

1. 철학자는 양쪽의 젓가락을 사용하여 식사를 하고, 식사를 마친 철학자는 젓가락을 내려놓고 다시 생각한다.
2. 철학자는 2개의 젓가락을 손에 쥐어야 식사를 할 수 있고, 한 번에 하나씩 잡을 수 있다.
3. 옆 사람이 식사중이면 젓가락 잡는 것을 대기한다.

5명의 철학자가 동시에 식사를 하게 되면 모두 왼쪽 포크만을 가지게 되고 오른쪽 포크를 대기하는 교착 상태(Deadlock)이 발생한다.

이를 방자힉 위한 방법은 대표적으로 3가지이다.

1. 최대 4명의 철학자들만이 테이블에 앉을 수 있도록 한다. => 젓가락이 하나 남기 때문에 어떤 철학자는 식사가 가능하다.
2. 한 철학자가 동시에 두개의 젓가락을 모두 집을 수 있을 때만 젓가락을 집도록 허용한다.(즉, 임계구역 안에서만 젓가락을 집어야 한다)
3. 비대칭 해결안을 사용한다.(홀수 번 철학자는 왼쪽, 짝수 번 철학자는 오른쪽 젓가락부터 집는다)

* 운영체제란?

제한된 컴퓨터 각종 자원을 효율적으로 관리하여 사용자에게 편리한 환경을 제공하는 소프트웨어

* 운영체제 목적 

• 처리 능력 : 일정 시간 내에 시스템이 처리하는 일의 양
• 반환 시간 : 시스템에 작업을 의뢰한 시간부터 처리가 완료될 때까지 소요되는 시간
• 사용 가능도 : 시스템 사용할 필요가 있을 때 즉시 가용 가능한 정도
• 신뢰도 : 시스템이 주어진 문제를 정확하게 해결하는 정도

* 운영체제 기능

• 프로세서 관리
• 기억장치 관리
• 프로세스 관리
• 주변장치 관리
• 파일 및 데이터 관리

* 프로세스

현재 실행중이거나 곧 실행 가능한 PCB를 가진 프로그램

cf) PCB(Process Control Block) : OS가 프로세스의 대한 중요한 정보를 저장하는 곳으로 각 프로세스가 생성될 때 고유 PCB가 생성되고, 프로세스가 완료되면 PCB는 제거된다.

* 스레드(Thread)

• 프로세스 내에서의 작업 단위로서 시스템의 여러 자원을 할당받아 실행하는 프로그램 단위 
• 스레드 기반 시스템에서 스레드는 독립적인 스케줄링의 최소 단위로서 프로세스 역할 담당 
• 하나의 프로세스를 여러 개의 스레드로 생성하여 병행성을 증진시킬 수 있다. 
• 공통적으로 접근 가능한 기억장치를 통해 효율적으로 통신한다.

CPU 스케줄링

* 개념

프로세스가 생성되어 실행될 때 필요한 시스템의 자원을 해당 프로세스에 할당하는 것

cf) 문맥 교환(Context Switching) : 하나의 프로세스에서 다른 프로세스로 전환할 때 실행하던 프로세스의 상태를 보관하고 새로운 프로세스 정보를 적재하여 실행을 준비하는 것

cf) 준비상태 큐(Ready Queue) : 주기억장치에 적재되어 있으면서 CPU에 의해 실행되기를 준비하는 프로세스들로 구성된 리스트

* 비선점 스케쥴링

이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케쥴링 기법

프로세스가 CPU를 할당받으면 해당 프로세스가 완료될 때까지 CPU를 사용한다.

프로세스의 요구를 공정하게 처리할 수 있지만 중요한 작업이 중요하지 않은 작업을 기다리는 경우가 발생한다.

# FCFS(First Come First Service)

• 준비상태 큐에 먼저 도착한 순서대로 CPU에 할당하는 기법
• 공평성은 유지되지만 중요한 작업이 중요하지 않은 작업을 기다리게 된다.

# SJF(Short Job First)

• 준비상태 큐에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법
• 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에 할당 순위가 밀려 무한 연기(기아) 상태가 발생할 수 있다.

# HRN(Hightest Response-ratio Next)

• SJF 기법을 보완한 것으로 대기 중인 프로세스들의 대기시간과 실행시간을 고려하여 우선순위를 결정한다.
• 우선순위 계산식 : (대기시간 + 수행시간) / 수행시간

* 선점 스케쥴링

하나의 프로세스가 CPU를 할당받아 실행중일 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케쥴링 기법

우선순위가 높은 프로세스를 빠르게 처리할 수 있지만 많은 Overhead를 초래한다.

# Round  Robin

• 각 프로세스느 시간 할당량(Time Slice)만큼 CPU를 점유하고 실행이 완료되지 않으면 CPU를 반환하고 준비상태 큐의 가장 뒤로 배치
• 문맥 교환(Context Switching) 효과를 고려하여 시간 할당량을 정한다.
• 시간 할당량이 클수록 FCFS와 같아지고, 시간 할당량이 작을 수록 문맥 교환 및 오버헤드가 자주발생

# SRT(Shortest Remaining Time)

• SJF 기법을 선점 형태로 변경한 기법으로 프로세스들 중 남아있는 실행시간이 가장 짧은 프로세스를 다음 프로세스로 선택

# 다단계 큐 스케쥴링

• 준비완료 큐를 다수의 별도의 큐로 분리하여 각 큐의 독자적인 스케쥴링에 따라 CPU를 할당받는 기법
• 각각의 서로 다른 작업들이 다른 묶음으로 분리될 수 있을 때 사용한다.
• 이전 작업이 실행 중이더라도 우선 순위가 높은 큐에 작업이 들어오면 CPU를 반환해야 한다.
• cf) 우선순위 : 시스템 프로세스 > 대화형 프로세스 > 일괄처리 프로세스

# 다단계 피드백 큐 스케쥴링

• 프로세스가 큐들 사이를 이동하는 것을 허용하는 기법이다.
• 프로세스를 CPU 성격에 따라 구분하고 어떤 프로세스가 CPU 시간을 너무 많이 사용하면 한 단계 낮은 우선순위 준비큐로 강등된다.
• 즉, 짧은 프로세스의 경우 FCFS 방식으로 신속하게 실행되고, 긴 프로세스는 낮은 단계의 준비단계 큐로 밀린다.
• 낮은 우선순위 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위 큐로 이동한다. (Aging 기법) -> 기아 상태 예방