GOSE_KOSE

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 스케줄링에 대해서 정리하는 시간을 가지도록 하겠습니다.!

1. 처리기 스케줄링 유형

처리기의 스케줄링은 응답 시간이나 처리량 효율성을 증대시키기 위해 처리기가 다음에 실행할 프로세스를 선택하는 것으로 일반적으로 스케줄링은 3단계로 이루어져 있습니다.

장기 스케줄링

프로세스가 CPU에 의해 실행될 수 있는 자격을 부여할지 여부를 결정하는 역할을 수행합니다. 장기 스케줄링은 프로세스를 시스템으로 진입시키는 여부를 판단하므로 멀티프로그래밍을 제어하는 역할을 한다고 볼 수 있습니다. 장기 스케줄링은 일괄 처리 큐에서 소정의 규정에 따라 작업들을 골라 프로세스로 만들어줍니다.

일괄 처리 큐

• 일괄 처리 큐(Batch Queue)는 여러 작업들이 한 번에 처리되도록 대기열에 모아두는 방식
• 일괄 처리 큐의 주요 역할은 시스템의 효율성을 높이고 자원을 최적화하기 위해 관련 작업을 그룹화하고 순차적으로 처리
• 주로 백그라운드에서 실행되는 작업에 사용될 수 있으며, 작업들을 우선순위에 따라 정렬하여 작업을 처리할 수 있고 유사한 작업을 그룹화하여 한 번에 처리하는 기능을 수행

장기 스케줄러가 프로세스를 선택하는 알고리즘

• FCFS(First com first Service)
• 우선순위 기반
• 예상되는 실행 시간의 길이
• 입출력 우대

중기 스케줄링

중기 스케줄링은 스와핑 기능의 일부라고 할 수 있습니다. 장기 스케줄링에서 프로세스를 생성했을 때, 주메모리에 프로세스를 스왑인 해야하는 상황이 생길 수 있습니다. (반대로 스왑 아웃 상황) 이 경우 중기 스케줄링은 이러한 스와핑 과정을 수행하는 것을 의미할 수 있습니다. 

단기 스케줄링

단기 스케줄링은 CPU 스케줄러라고 불리며 프로세스들 사이에서 CPU를 할당하는 역할을 수행합니다. 단기 스케줄러는 프로세스들 사이에서 CPU를 우선순위 혹은 요구사항을 고려하여 실행 순서를 결정하고, 컨텍스트 스위칭을 관리합니다. 이때, 디스패쳐와 함께 작동하여 컨텍스트 스위칭을 수행합니다. 

디스패쳐란

프로세스 간의 컨텍스트 스위칭을 수행하는 역할을 담당하며 단기 스케줄러와 함께 작동합니다. 디스패처는 단기 스케줄러가 선택한 프로세스를 실행하기 위해 현재 실행 중인 프로세스의 상태를 저장하고 새로 선택된 프로세스의 상태를 불러오는 작업을 수행합니다. 

단기 스케줄링 호출

• 새로운 프로세스가 생성되어 실행 대기 상태에 들어감
• 실행 중인 프로세스가 입출력을 요청, 시스템 호출 등을 인해 대기 상태로 전환
• 실행 중인 프로세스가 종료되거나 시간 할당량이 만료되어 다른 프로세스에게 CPU를 넘겨줌

2. 스케줄링  평가 척도

사용자 중심의 성능 관련 평가척도

• 반환시간: 프로세스가 시스템으로 진입한 후로부터 종료할 때까지 걸린 시간을 의미하며, 실제 실행 시간뿐만 아니라, CPU나 다른 자원들을 사용하기 위해 대기한 시간 모두 포함합니다.
• 응답시간: 대화형 프로세스가 시스템에 요구를 한 후, 이에 대한 시스템으로부터 첫 번째 응답이 올 때까지의 시간을 의미합니다. 프로세스는 사용자에게 실행 결과를 출력해 주는 사이에 시스템에 또 다른 요청을 하는 경우가 종종 있습니다. 따라서, 사용자의 입장에서 보면 시스템의 반응 속도를 가늠하기에는 반환 시간보다 응답 시간이 더 적합합니다.
• 완료 기한: 프로세스가 완료되어야 하는 시점에 기한이 있다면, 스케줄러는 다른 평가 척도가 희생당하더라도 완료 기한을 만족시킬 수 있는 프로세스의 수를 최대화하는 방향으로 설계해야 합니다.

사용자 중심의 기타 평가척도

• 예측 가능성: 같은 작업이라면 실행될 때마다 동일한 기간 동안 실행되어야 하고, 시스템의 부하 정도에 상관없이 동일한 비용으로 실행되어야 합니다. 만약 실행할 때마다 응답 시간이나 반환 시간이 많이 차이 난다면 사용자들은 시스템을 신뢰하지 못하게 됩니다.

시스템 중심의 성능 관련 평가 척도

• 처리량: 처리량을 중시하는 스케줄러는 단위 시간 내에 완료될 수 있는 프로세스의 수를 최대화하는 정책을 사용합니다. 이는 처리해야 할 작업의 양에 관련된 척도로써 각 프로세스 실행 시간의 길고 짧음에 따라 크게 좌우될 수  있습니다. 
• 처리기 이용률: 처리기 이용률이란 전체 시간 중에 처리기가 바쁘게 실행을 한 시간의 비율을 의미합니다. 여러 사용자들이 공유하여 사용하는 고가의 시스템에서 처리기 이용률은 시스템을 효율적으로 사용하고 있느냐 아니냐가 매우 중요한 성능 척도입니다. 

시스템 중심의 기타 평가 척도

• 공정성: 시스템이 어떤 특정 목적을 위해 공표하지 않은 이상 어떤 프로세스도 스케줄러로부터 차별을 받아서는 안됩니다. 즉 프로세스가 처리기를 할당받지 못하는 기아 상태 발생을 줄여야 합니다.
• 우선순위: 프로세스들에게 우선순위가 부여되면, 스케줄러는 높은 우선순위의 프로세스를 우대해야 합니다.
• 균형 있는 자원: 활용 스케줄러는 시스템 내의 자원들이 가능한 최대로 활용되도록 해야 합니다.

3. 스케줄링 정책

준비 큐에서 대기 중인 프로세스 중 하나를 선택하는 알고리즘을 함수 형태로 표현한 것은 선택 함수라고 부릅니다. 스케줄링이 선택함수를 적용하는 과정에 사용하는 용어는 다음과 같습니다.

• w: 대기한 시간과 실행한 시간을 모두 합쳐 시스템이 들어온 후 지금까지 경과한 시간
• e: 지금까지 실행하는 데에만 걸린 시간
• s: 프로세스가 시작해서 종료하기까지 걸릴 총 서비스 시간(e를 포함). 이 값은 시스템에 의해 미리 계산되거나 프로세스가 이 정보를 미리 시스템에게 알려주어야 함. 

결정 모드는 선택 함수가 호출되는 시점이 언제인가 하는 것을 나타냅니다. 

• Nonpreemptive(비선점) 모드: 프로세스가 일단 실행 상태에 진입하면 종료되거나 자발적으로 CPU를 놓을 때까지는 CPU를 빼앗기지 않습니다. 자발적으로 CPU를 놓는다는 것은 자기가 스스로 블록 시키거나 입출력 요구 및 시스템 서비스 호출 등으로 인해 스스로 준비 큐에서 빠지는 상황을 의미합니다.
• Preemptive(선점) 모드: 현재 실행 중인 프로세스라 할지라도 운영체제에 의해 인터럽트가 걸려 비자발적으로 준비 큐로 이동될 수 있습니다. 현재 실행 중인 프로세스를 선점시킬 수 있는 시점으로는 새로운 프로세스가 진입, 하드웨어로부터 인터럽트가 걸려 이를 대기 중이던 선점된 프로세스가 다시 준비 큐로 들어오는 것, 또는 클록 인터럽트에 의해 주기적으로 스케줄러가 호출되는 시점 등을 들 수 있습니다. 

Preemptive 모드는 NonPreemptive 모드 스케줄링에 비해 프로세스 간 문맥 교환이 자주 발생하기 때문에 이로 인한 오버헤드가 크다고 할 수 있습니다. 하지만 최근 처리기는 문맥 교환에 드는 비용을 최소화하기 위해 하드웨어 수준에서 문맥 교환 연산을 제공하므로 오버헤드 문제가 해결되고 있습니다. 따라서, 기아 상태를 방지할 수 있는 Preemptive 모드가 나은 서비스를 제공합니다. 

스케줄링 정책의 특징

4. FCFS(First-Come-First-Served)

FCFS는 가장 단순한 형태의 스케줄링 정책으로 FIFO라고도 합니다. 큐잉 체계를 엄격하게 지키고 있으므로 다음의 절차에 따라 진행됩니다.

이 표를 토대로 확인할 수 있는 부분은 긴 프로세스의 경우 상대적으로 짧은 프로세스보다 서비스 시간 자체가 길기 때문에 정규화된 반환시간이 적습니다. 하지만 Y 프로세스는 서비스 시간이 매우 짧지만 앞의 X 프로세스의 긴 시간으로 인해 반환시간이 늦어져 비효율적인 것을 확인할 수 있습니다. 

이를 처리기 중심 프로세스와 입출력 중심 프로세스로 대입하여 생각해 보면 다음과 같습니다.

•  입출력 중심 프로세스는 무거운 작업이지만 실제 네트워크 및 디스크 처리 대기 시간이 긴 것이고 CPU의 실행 시간으로 보면 프로그램 카운터로부터 명령어를 입출력 컨트롤러에게 전달하고 제어하는 역할이므로 CPU 버스트는 짧습니다.
• 반면 처리기 중심 프로세스는 실제 CPU가 연산해야 하는 작업이 많으므로 많은 시간이 소요됩니다.
• 따라서, 빠른 시간 내 CPU 버스트를 마칠 수 있는 작업인 입출력 중심의 프로세스임에도 오랜 시간을 대기해야 하므로 비효율적이라고 볼 수 있습니다.

5. Round Robin

라운드 로빈 방식은 어떤 긴 프로세스가 일정 시간을 넘어가는 순간 실행을 강제로 선점(preemption)시키는 것을 의미합니다. 이때 클록 인터럽트가 주기적으로 발생하게 되는데 이 인터럽트 루틴으로 인해 현재 실행 중이던 프로세스는 준비 큐로 이동시키고 준비 큐에서 FCFS 방법으로 다음 프로세스를 골라 실행시킵니다.

여기서 사용되는 개념이 시간 할당량으로 모든 프로세스는 정해진 시간 조각만큼만 실행한 후 강제적으로 CPU를 빼앗습니다.

• 시간할당량이 짧은 경우: 시간할당량이 짧은 경우, 짧은 프로세스에게 유리하지만, 짧은 할당 시간으로 인해 컨텍스트 스위칭이 빈번하게 발생하므로 오버헤드가 발생할 수 있습니다.
• 시간할당량이 긴 경우: 긴 프로세스의 경우 끝날 때까지 다른 프로세스가 대기해야 하므로 정규화된 반환 시간이 매우 길었습니다. 만약 시간할당량이 긴 프로세스의 프로세스 시간과 비슷하거나 더 큰 경우 결국 짧은 프로세스는 긴 프로세스의 시간을 전부 기다려야 하게 되므로 FCFS의 문제점을 해결할 수 없습니다.

라운드 로빈 방식은 공평한 시간 할당량으로 프로세스를 처리하기 때문에 시분할 시스템이나 트랜잭션 처리 시스템에 매우 효과적일 수 있습니다. 하지만 라운드 로빈 방식에도 입출력 중심 프로세스를 처리하는데 한계가 있습니다. 이 절차를 정리하면 다음과 같습니다.

(공부한 내용이 명확하게 이해가 되지 않아서 제가 이해한 바를 바탕으로 정리하였습니다. 따라서, 사실과 다를 수 있습니다.)

• 입출력 중심 프로세스는 처리기 중심 프로세스보다 상대적으로 짧은 CPU 버스트를 가집니다. 따라서 할당된 시간보다 빠르게 1번 요청을 수행하면 입출력 큐로 이동하여 입출력 완료까지 대기합니다. 입출력이 완료되면 준비 큐로 이동합니다.
• 이 과정에서 만약 시간 할당량이 5초라면 2초만 사용하게 되고 3초는 사용하지 못하고 반납하게 됩니다.
• 이어서 만약 처리기 중심 프로세스가 실행이 된다면 이 프로세스는 주어진 시간을 모두 활용한 후 다시 준비큐로 이동하게 됩니다.
• 이 과정을 정리하면, 실제 CPU는 짧은 버스트를 가짐에도 불구하고 입출력 요청을 수행하게 되면 입출력 큐로 이동하고 다시 준비큐로 가게 되므로 실제 시간 할당량을 전부 채우지 못하게 되는 문제가 발생할 수 있습니다.

이를 해결하기 위한 방법이 개선된 라운드 가상 라운드 로빈(Virtual Round Robin)입니다. 수행 절차는 다음과 같습니다.

• 입출력 중심 프로세스가 입출력 요청을 수행하면 입출력 큐로 가서 입출력 완료까지 대기합니다.
• 이후, 다시 준비 큐로 이동하는 것이 아니라 보조 큐로 이동하여 현재 수행 중인 프로세스가 CPU를 반납하면 준비 큐보다 먼저 보조 큐에 있는 입출력 중심 프로세스를 스케줄링합니다.
• 이때 만약 앞서 시간 할당량 5초를 기준으로 2초를 소모했다면 3초만 부여하여 다른 프로세스와 동일하게 5초만 수행될 수 있도록 합니다.

6. SPN(Shortest Process Next)

FCFS가 긴 프로세스에 효율적인 점을 극복하기 위해 짧은 프로세스에 우선순위를 두는 방식을 비선점 방식을 SPN이라고 합니다.

이 경우, 각 프로세스의 총 실행 시간을 미리 알아야 한다는 단점이 있는데, 이를 극복하기 위해 단순 평균 혹은 지수적 평균 방법을 적용합니다.

Sn+1 = aTn + (1 - a)Sn

여기서 알파는 0 < a < 1 사이의 가중치로 과거 측정치에 비해 상대적으로 최근 측정치에 어느 정도의 비중을 둘 것인가를 설정할 수 있는 파라미터입니다.

이를 적용하면, 일반적으로 반복되는 특정 프로세스에 대한 총 실행 시간을 예측하여 적용할 수 있습니다. 만약 짧을 프로세스가 있다면 우선순위를 얻게 되어 CPU를 할당받아 처리할 수 있습니다. 이 경우 긴 프로세스는 계속 대기하여 결국 CPU를 할당받지 못하게 되는 기아 상태에 빠질 수 있습니다.

7. SRT (Shortest Remaining Time)

SPN가 프로세스의 총 실행 시간에 따라 프로세스를 선택하는 스케줄링 방법이었다면, SRT는 프로세스가 남아있는 시간을 기준으로 선점 방식으로 프로세스를 선택하는 스케줄링입니다. 즉, 현재 실행 중인 프로세스가 남은 시간이 10초인데, 새로 들어온 프로세스의 남은 시간이 2초라면 선점 방식에 의해 프로세스 CPU를 빼앗고 준비 큐에 있는 프로세스를 선택할 수 있는 방법입니다.

이 역시, 긴 프로세스에 대해서는 기아 상태에 빠질 수 있다는 단점이 존재합니다.

8.HRRN(Hightest Response Ratio Next)

앞 서 정규화된 반환 시간이라는 평가 척도가 존재했었는데, 이러한 정규화된 반환 시간의 평균이 최소화시키는 방향으로 스케줄러를 최적화하는 방법을 HRRN이라고 합니다.

R = (w + s) / s
R = 응답 비율
w = 처리기를 기다리며 대기한 시간
s = 예상되는 서비스 시간

HRRN은 SPN, SRT처럼 프로세스들의 예상 실행시간에 대한 예측을 해야 한다는 점에서 단점이 있지만, HRRN의 장점은 대기 시간이 긴 프로세스에게도 우선권을 줄 수 있다는 점입니다.

해당 수식을 살펴보면, 짧은 프로세스의 경우 s가 매우 짧기 때문에 R의 값이 크게 나와 높은 우선권을 가질 수 있습니다. 하지만 s가 크더라도 만약 이를 상쇄시킬 정도로 w가 더 크다면 대기 시간이 그만큼 커져서 R이 커지게 됩니다. 따라서, 프로세스의 대기 시간을 고려할 수 있다는 점에서 장점을 가집니다.

9. FeedBack

FeedBack은 SPN, SRT, HRRN이 필요로 하는 프로세스의 총 실행시간을 예측할 수 없는 상황에 적용할 수 있습니다. FeedBack 방식은 현재 수행된 수행시간이 길어질수록 낮은 우선순위를 부여하는 방법으로 총 실행 시간을 예측할 수 없더라도 실행 시간이 길어진다면 곧 긴 프로세스임을 의미하므로 비슷한 효과를 얻을 수 있다는 개념입니다. 이를 구현하기 위해서는 우선순위 큐가 여러 개 구성되게 됩니다.(다단계 피드백)

수행 절차는 다음과 같습니다.

• 프로세스 A가 시간 할당량을 채우지 못하고 5초의 누적된 수행시간을 기록합니다.
• 프로세스 A는 우선순위 큐 RQ1에 입력이 되고 준비 큐에 있는 다른 프로세스들이 실행됩니다.
• 프로세스 B는 시간 할당량 이내에 처리되어 CPU가 반납되었고(누적시간 2초) 프로세스 C는 RQ0에서 나와 시간 할당량을 채우지 못하고 5초의 누적된 수행시간을 기록합니다.
• 이때,  프로세스 B가 입출력 요청을 완료하여 다시 RQ1으로 오게 되면 누적 시간이 적으므로 프로세스 B가 먼저 실행됩니다.
• 우선순위 큐 RQ1에서 프로세스 A를 빼서 실행했는데 시간 할당량을 채우지 못하여 10초의 누적된 수행시간을 기록합니다.

이러한 절차대로 수행될 경우, 짧은 프로세스의 경우 우선권을 얻을 수 있습니다. 하지만, 긴 프로세스의 경우 계속 우선권에서 밀려 기아 상태에 돌입할 수 있게 됩니다.

따라서, 우선순위 큐 RQn에 시간 할당량 p를 다르게 부여하는 방법이 있습니다. 예를 들어 RQ1은 p = 1, RQ2는 p = 2 등으로,
우선순위가 계속 밀린 긴 프로세스가 선택되면 긴 시간 할당량이 적용될 수 있도록 하는 방법도 있습니다.

(하지만, 실제 우선순위를 보장하지는 않으므로 계속 기아상태에 머물 수 있다는 점도 있습니다.)

이상으로 단일 처리기 스케줄링에 대한 정리를 마치도록 하겠습니다.

감사합니다!!!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 가상메모리에 대해서 정리하도록 하겠습니다.

1. 하드웨어와 제어구조

• 프로세스의 모든 메모리 참조는 논리주소이고, 이 주소는 프로세스 수행 시간에 동적으로 물리주소로 변환됩니다. 
• 프로세스는 스와핑으로 다시 주기억장치에 적재될 때, 이전 위치가 아닌 다른 위치에 저장될 수 있습니다.
• 프로세스의 주소공간은 여러 블록으로 분할될 수 있고, 프로세스가 수행 중 이 블록들은 주기억장치의 연속된 영역에 위치할 필요가 없습니다.

2. 가상메모리 용어 정리

3. 주기억장치에 프로세스의 일부 블록(페이지, 세그먼트) 적재의 효과

수행 프로세스 과정

• 프로세스의 적재집합은 프로세스의 코드나 데이터 중 임의 시점에 주기억장치에 적재되어 있는 부분을 의미합니다.
• 처리기는 세그먼트테이블이나 페이지테이블을 이용하여 프로세스의 참조 주소가 적재집합에 포함되어 있는지를 파악합니다.
• 주기억장치에 적재되지 않은 논리주소가 참조될 경우, 처리기는 메모리 접근 오류 인터럽트를 발생시킵니다.
• 인터럽트 된 프로세스를 블록 상태로 둔 후, 디스크로부터 입출력 처리를 마친 후 블록된 상태를 재개합니다.

이러한 과정은, 보다 많은 프로세스를 주기억장치에 유지하고, 주기억장치보다 큰 프로세스를 수행할 수 있도록 합니다.

4. 페이징

가상 메모리는 전통적으로 프로세스별 페이지테이블이 설정됩니다. 페이지테이블 항목에는 해당 페이지가 메모리에 적재되어 있는지 구분할 수 있도록 비트(존재비트 P)가 존재해야 합니다. 페이지테이블 항목은  변경비트 M을 가지는데 해당 페이지가 메모리에 적재된 후 그 내용이 변경되었는지 여부를 나타냅니다.

페이지테이블 구조 

• 프로세스가 수행될 때, 프로세스를 위한 페이지테이블의 시작 주소가 특정 레지스터에 저장
• 가상주소의 페이지 번호를 테이블의 인덱스로 사용하여 페이지테이블의 항목 선정
• 페이지가 적재된 프레임 번호를 얻음
• 프레임번호 + 가상주소의 오프셋과 결합되어 물리주소 구성

전통적인 페이지 테이블 구조

32비트 주소 체계에 적용 가능한 2단계 구조의 페이지 처리 방식은 다음과 같습니다.

여기서, 4KB(2^10 * 2^2) * 4MB(2^20 * 2^2) = 4GB(2^32 * 2^2) 이므로 다음과 같은 2단계 구조를 만들 수 있으며 

전체 가상 주소 공간 2^32 / 페이지 크기 2^12를 하면 2^20의 페이지 수를 구할 수 있습니다.

2^20의 2^10(10 비트)은 루트 페이지 테이블 역할을 수행하고 나머지 2^10은 루트 페이지의 하위 페이지로 가상메모리 상에 유지됩니다.(프로세스가 적재되면 주기억장치로 루트 페이지 혹은 일부가 적재될 수 있습니다. -> 요구 페이징) 가상 페이지의 처음 10비트는 루트 페이지에 대한 인덱스로 쓰여 사용자 페이지테이블이 저장된 페이지를 위한 PTE를 찾아주며 (2^10), 여기서 찾은 값이 인덱스로 쓰여 가상주소에 참조될 실제 페이지를 위한 PTE를 찾게 합니다. 여기서 프레임 번호를 얻을 수 있으며 12비트의 오프셋과 합쳐져 주기억장치의 페이지프레임을 구할 수 있습니다.

역페이지 테이블 구조

앞서 정의한 전통적인 페이지테이블 구조에서는 가상 페이지수에 비례하여 PTE가 증가하게 되는데, 이를 주메모리에 적재해야 된다는 점에서 주기억장치에 많은 무리를 줄 수 있습니다. 이를 해결하기 위한 방법이 역페이지 테이블 구조입니다. 역페이지 테이블 구조의 저장 방식은 다음과 같습니다.

• 가상주소 중 페이지번호 부분은 간단한 해시 함수를 통해 특정 해시 값으로 사상됩니다.
• 해시값은 역페이지 테이블에 대한 인덱스로 쓰이고, 역페이지테이블은 페이지테이블의 항목들로 구성됩니다.
• 페이지테이블 항목이 가상메모리의 페이지 당 하나씩이 아니라 실기억장치의 페이지프레임당 하나씩 설정되므로 프로세스의 수나 지원되는 가상 페이지 수와 상관없이 주기억장치의 일정 부분만이 테이블 설정에 쓰입니다.
• 하나 이상의 가상주소들이 동일한 해시테이블 항목으로 사상될 수 있으므로 연결 기법을 통해 체인 기법을 활용합니다.

저는 역페이지 테이블 구조 2가지가 이해가 되지 않았습니다.ㅜㅜ
(하단에 게시되는 글을 제가 이해한 바를 정리한 내용이므로 사실과 다를 수 있습니다.)

먼저 실주소를 찾는 과정을 이해하는데 어려움을 겪었습니다.

예를 들어 운영체제가 프로세스A에 대한 가상 주소를 실주소로 매핑하길 원할 때, 단순히 페이지 번호로 어떻게 실주소를 매핑할 수 있는가입니다. 즉, 페이지 번호는 많은 프로세스에서 겹칠 수 있는데 역페이지테이블에서 프로세스 ID를 제공하더라도 여러 개의 체인으로 연결된 매핑값을 모두 실주소로 변환한 후 실주소에 접근하여 해당 프로세스가 운영체제가 요구하는 프로세스 A와 같은지 파악해야 하지 않는가입니다

이 문제에 대한 답변은 여러 블로그와 GPT를 통해 찾을 수 있었고 해당 절차는 다음과 같습니다.

운영체제는 현재 실행 중인 프로세스 A에 PID를 얻습니다. 가상 주소를 통해 페이지 번호를 획득한 후 해시함수에 프로세스 A의 PID와 가상 주소를 적용합니다. 만약 찾았다면 리턴하고, 해당 PID가 일치하지 않는 경우 체인을 활용하여 주소를 찾습니다. 역페이지테이블에서 해당 해시값을 바탕으로 실주소의 프레임 번호를 찾아 가상 주소의 오프셋과 결합하여 실주소를 얻습니다.

두번 째는 페이지테이블 항목이 가상메모리의 페이지 당 하나씩이 아니라 실기억장치의 페이지프레임당 하나씩 설정된다는 의미가 이해가 되지 않았습니다. 이에 대한 자료를 찾아본 후 제가 이해한 바는 다음과 같습니다.

페이징 작업을 수행할 때 주기억장치도 페이지 프레임을 적용합니다. 이때 가상 페이지 블록과 동일한 크기로 주기억장치도 물리 메모리를 분할하게 되는데, 분할된 각 페이지프레임에 대해 페이지테이블을 적용합니다. 이를 통해 다시 페이지테이블과 역페이지테이블을 이해하면, 페이지테이블의 경우 가상 주소 공간을 페이지 범위로 나누고 각 페이지에 대해 테이블 엔트리를 설정하기에 프로세스별로 PTE가 생성되게 됩니다.

역페이지테이블은 프로세스가 실행될 때, 필요한 가상 메모리 페이지들은 디스크 스왑 영역에 위치하고 프로세스가 해당 페이지에 액세스 하는 경우 페이지폴트가 발생하여 주기억장치에 스왑인 됩니다. 이 과정에서 역페이지 테이블에 페이지에 대한 정보, 프로세스 ID 등의 정보를 입력하게 됩니다. 따라서,  페이지 번호와 오프셋을 통해 가상 주소를 실주소로 매핑할 수 있게 됩니다. 즉, 프로세스 별 PTE를 적재하는 것이 아니라, 주메모리에 있는 페이지프레임에 역페이지테이블을 구성하여 적재하는 것입니다.

5. TLB(Translation Lookaside Buffer)

원칙적으로 모든 가상메모리 참조는 두번의 물리 메모리 참조를 수반하므로 두 배의 메모리 접근 시간을 갖게 합니다.

가상메모리 방식은 페이지테이블 항목들에 대한 특수 고속 캐시를 사용하는데, 이를 TLB라고 부릅니다. TLB는 가장 최근에 참조된 페이지테이블의 항목을 유지합니다.

TLB의 작동 구조

• 시작
• CPU가 TLB를 검사
• TLB에 페이지 테이블 항목이 있다면 CPU가 물리 주소를 생성
• 없다면, 페이지 테이블에 접근하여 주기억 장치에 페이지 테이블 확인 (존재비트 1 or 0)
• 있다면(존재비트 1), TLB를 갱신한 후 CPU 물리 주소를 생성
• 만약 주기억 장치에 페이지가 없다면 '페이지 폴트'가 발생하여 운영체제가 CPU에게 디스크로부터 페이지를 반입하도록 명령
• CPU가 입출력 하드웨어를 활성화하고 드스크로부터 주기억장치로 페이지를 스왑인

이 부분에서 혼란이 왔던 부분은 실제 페이지테이블에서 페이지 번호를 조회하는 것과 TLB에서 페이지 번호를 조회하는 것이 결국 같은 메커니즘으로 적용되는 것이 아닌가라는 의문이었습니다.

하지만 실제 메커니즘은 많이 달랐습니다. 앞 서 페이지테이블은 일부가 주기억장치에 저장된다고 설명하였습니다. 만약 페이지폴트가 발생하지 않는 상황하에서 가상메모리의 실주소를 찾는 과정은 주기억장치에 접근해야 하므로 속도가 더딜 수 있습니다.

TLB는 CPU 하드웨어에 접근하여 만약 TLB 페이지테이블에 항목이 있다면 이미 주기억장치에 스왑인 하면서 TLB를 갱신한 것을 의미하기 때문에 물리주소를 바로 얻어올 수 있습니다.

만약, 페이지폴트가 발생한다면 디스크로부터 주기억장치로 필요한 페이지를 전송하여 적재하고 TLB를 갱신합니다. 이러한 과정을 통해 최근 참조된 페이지테이블에 값은 TLB에 적재되어 주기억장치를 매번 들려서 물리주소를 찾지 않더라도 빠른 고속 처리를 가능하도록 합니다.

6. 페이지 크기

페이지 크기는 그 양에 따라 페이지 폴트 발생률이 달라질 수 있습니다.

페이지 크기가 작은 경우

일반적으로 페이지 크기가 작다면 페이지폴트의 경우 지역성의 원리에 따라 한 프로세스가 활용할 수 있는 페이지들이 상대적으로 많아집니다. 이는 곧 페이지폴트 수를 줄이는 효과를 얻을 수 있습니다. 페이지 폴트의 수를 줄이는 이유는 다음과 같습니다.

• 공간 지역성: 프로세스는 일반적으로 코드와 데이터의 일부 영역에 집중되어 실행됩니다. 페이지 크기가 작으면 주기억장치에 적재된 페이지가 필요한 데이터와 코드만 포함하게 되므로 더 좋은 공간 지역성을 달성합니다.
• 메모리 사용의 효율성: 작은 페이지 크기를 사용하면 페이지 내부의 미사용 메모리 공간이 줄어들고 메모리 사용 효율성이 향상됩니다. (내부 단편화 감소)

< 페이지 크기가 작으면 주기억장치에 적재된 페이지가 필요한 데이터와 코드만 포함?>

페이지 크기가 작아지면, 각 페이지에 포함된 데이터와 코드가 더 밀집되어 있습니다. 이렇게 되면 주기억장치에 적재된 페이지가 프로세스가 필요로 하는 데이터와 코드만 포함하게 됩니다. 앞 서, 페이지 크기가 작으면 주기억장치에 적재된 페이지가 필요한 데이터와 코드만 포함하게 된다는 의미는 실제 프로세스가 주기억장치에 적재될 때 페이지 크기가 클 경우 불필요한 데이터도 함께 적재될 수 있지만, 페이지 크기가 작을 경우 반드시 필요한 소스만 적재될 수 있기 때문에 효율적으로 사용할 수 있다는 의미입니다.

하지만, 반드시 페이지폴트가 감소하는 것은 아닙니다.

페이지 크기가 작을 때는 페이지 수가 증가하게 됩니다. (32비트 가상 주소 공간을 고려하면, 2^12의 페이지 크기가 있다면 32 - 12 = 20 즉 2^20만큼의 페이지 수가 필요합니다)

이는 곧 페이지 테이블이 증가하는 문제를 발생시키고, 멀티프로그래밍 환경에서 큰 프로그램을 수행하는 활성 프로세스의 페이지테이블 중 일부가 주기억장치에 적재되지 못하고 가상메모리 상에 있어야 합니다. 즉 이 경우는 반대로 페이지 폴트 발생률을 높일 수 있습니다.

페이지 크기가 클 경우 

페이지 크기가 큰 경우 페이지 폴트 발생률은 증가할 수 있습니다. 페이지 크기에 따라 비례하여 페이지 수는 작아지므로 개별 페이지들은 최근 잠조로부터 멀리 떨어진 위치를 포함하게 됩니다. 이는 지역성의 원리에 따르면 공간 밀집도가 낮아지게 되므로 페이지 폴트 발생 확률을 높입니다.

페이지 크기가 프로세스 전체 크기와 근접해 갈 경우

이 경우 하나의 페이지에 프로세스 전체를 적재할 수 있으므로 페이지 폴트 발생 빈도가 감소하게 됩니다. 

7. 정리하며

가상 메모리를 사용할 경우 모든 주소 참조는 실행 중에 실주소로 변환되는 논리적 띄게 됩니다. 가상 메모리의 도입으로 주기억장치에 가해지는 부담을 효과적으로 줄일 수 있습니다. 이러한 가상 메모리의 용어, 페이지를 정리하며 정말 많은 점을 배울 수 있었고 단순히 논리적 참조로만 알고 있었던 과거에 저를 반성할 수 있게 되었습니다.

이해가 되지 않는 부분이 너무 많았고 하나씩 이해하는 과정에서 정말 많은 시간이 흘렀지만 가상 메모리가 어떠한 수행 절차로 실주소로 변환되는지 배울 수 있었고, TLB로 최근 참조한 페이지테이블에 대한 고속 캐시 효과를 얻을 수 있는 점도 정리할 수 있었습니다.

사실과 무관한 정보도 있을 수 있습니다. 이 부분은 계속 반복 학습하여 수정해 나가겠습니다.! 피드백 주시면 바로 배우겠습니다.

감사합니다.!

자료 출처: 운영체제 제 8판 내부구조 및 설계원리

그림 출처: https://velog.io/@gndan4/OS-%EA%B0%80%EC%83%81-%EB%A9%94%EB%AA%A8%EB%A6%AC

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 운영체제의 메모리 관리에 대한 글을 작성하고자 합니다. 먼저 가상 메모리의 경우 분량이 방대하기 때문에 다음 포스팅에 작성하고, 기본적인 메모리 방식을 위주로 정리하도록 하겠습니다.

멀티프로그래밍 시스템에서 효과적인 메모리 관리는 필수적입니다. 적은 수의 프로세스만이 주기억장치에 있을 때, 대부분의 시간 동안 입출력 작업 종료를 기다리게 되고 처리기는 아무 일도 하지 않게 됩니다. 따라서,  메모리는 사용 가능한 처리기 시간을 소비하기에 충분한 수의 프로세스들이 준비 상태에 있도록 할당되어야 합니다.

1. 메모리 관리 요구조건

• 재배치 - 프로세스가 디스크로 스왑아웃이 되면, 스왑인이 될 때, 다른 공간으로 프로세스를 재배치해야 합니다. 이 과정에서 메모리 참조 부분을 실제 물리주소로 변환할 수 있어야 합니다.
• 보호 - 다른 프로세스에 속한 프로그램들은 허가 없이 읽기나 쓰기를 위해 임의의 프로세스의 메모리를 참조하면 안 됩니다.
• 공유 - 필수적인 보호 기능을 침해하지 않는 범위에서 제한된 접근을 통하여 메모리의 일부분을 공유할 수 있도록 허용해야 합니다.

2. 메모리 관리 기법

메모리 관리의 주된 작업은 처리기에 의해 실행될 프로세스를 주기억 장치로 가져오는 것입니다. 주로 '세그먼테이션'과 '페이징'을 활용하는 가상 메모리가 사용되고 있습니다. 

3. 고정 분할

주기억장치를 관리하는 가장 단순한 기법은 고정된 경계를 가지는 메모리 영역으로 구분합니다.

• 분할크기: 각 분할이 고정된 경계를 가지는 메모리 영역으로 구분되며 균등 분할과 비균등 분할로 나뉩니다.
• 프로그램이 파티션보다 클 수 있다는 단점이 있습니다 또한, 매우 적은 메모리를 필요로 하더라도 고정된 파티션의 일부에 적재되어야 하기 때문에 내부 공간의 낭비가 발생하는 내부 단편화가 발생합니다.
• 배치 알고리즘은 균등 분할의 경우 모두 동일한 크기의 파티션으로 균등 분할 되어 있으므로 적재 가능한 파티션이 하나라도 존재하면 프로세스는 배치가 가능합니다.
• 비균등 분할의 경우 각 프로세스의 용량에 맞는 가장 작은 파티션을 할당하기 위해 스왑아웃된 프로세스들을 유지하는 스케줄링 큐가 필요합니다. 

4. 동적 분할

고정 분할의 기법에서 발생하는 몇 가지 문제점을 해결하기 위해 동적 분할 기법이 개발되었지만 이 기술 역시 현재는 잘 쓰이지 않습니다.

• 동적 분할에서 파티션의 크기와 개수는 가변적입니다. 한 프로세스가 주기억장치로 적재될 때, 정확히 요구된 크기만큼의 메모리만 할당받습니다.
• 서로 다룬 프로세스가 스왑인 스왑아웃 하는 과정에서 주기억장치에 사용할 수 없는 단편화된 구멍이 생기게 되는데, 이러한 조각화된 메모리를 외부 단편화라 부릅니다. 이는 메모리 효율성을 저하시킵니다.
• 메모리 집약을 사용할 경우 파티션을 연속적이게 인접하도록 만들 수 있지만 불필요한 재배치 시간이 소모됩니다.

• 배치 알고리즘으로 최적적합, 최초적합, 순환적합 종류가 있으며 최초적합은 가장 간단하며 대부분 가장 최적입니다. 순환 적합은 메모리 마지막 부분에 있는 사용 가능한 블록에서 자주 일어나고, 최적적합은 이름과 다르게 가장 성능이 나쁜 방법으로 가장 작은 블록을 찾아 배정하므로 가장 작은 외부 단편화를 생성합니다.

5. 버디 시스템

버디 시스템은 2^k로 블록 단위로 할당 가능한 메모리에 따라 블록을 나눌 수 있습니다. 그림과 같이 만약 56K의 메모리가 필요할 경우 256K -> [128K, 128K] -> [128K, [64K, 64K]]로 나누며 가장 작은 단위에 프로세스를 적재하는 방식입니다.

6. 재배치

프로세스가 스왑인 스왑아웃되는 과정에서 데이터 위치가 변경될 수 있습니다. 이 문제를 해결하기 위해 주소 유형을 정의하여 적절한 조치 및 변환이 이루어져야 합니다.

• 논리주소: 현재 데이터가 적재된 메모리와는 독립적인 메모리 위치에 대한 참조입니다. 반드시 물리주소로 변환되어야 합니다.
• 상대주소: 어떤 알려진 시점, 주로 처리기의 한 레지스터 값으로부터 상대적인 위치를 의미합니다.
• 물리주소: 절대주소란 주기억장치 안에서의 실제 위치를 의미합니다.

재배치를 지원하는 하드웨어의 경우 프로세스가 실행 상태가 될 때, '베이스 레지스터'에 프로세스의 주기억장치의 시작주소가 적재됩니다. 프로세스를 실행하는 동안은 상대주소가 사용되며, 베이스 레지스터로 상대주소에 베이스 레지스터에 적재된 값이 더해져 절대주소로 변환되어 사용됩니다. 

7. 페이징

주기억장치를 비교적 작은 고정 사이즈 파티션으로 나누고(프레임) 각 프로세스 또한 같은 크기의 고정 조각(페이지)으로 나눌 수 있습니다. 따라서, 외부 단편화에 대한 낭비를 없애고, 내부 단편화의 경우 마지막 페이지에서만 발생하도록 처리할 수 있습니다. 

이 경우, 만약 각 프로세스들이 스왑인 스왑아웃 되는 과정에서 비연속적인 공간이 발생할 수 있습니다.  하지만 논리주소와 '페이지 테이블'을 통해  프로세스의 각 페이지들에 해당하는 프레임의 위치를 관리하여 비연속적인 공간에 단편화된 프레임을 점유하도록 함으로써 내부 단편화를 없앨 수 있습니다.

• 페이지 테이블은 프로세스의 각 페이지들에 해당하는 프레임의 위치를 관리합니다.
• 각 논리주소는 페이지 번호와 페이지 내의 오프셋으로 구성됩니다.
• 논리주소(페이지 번호, 오프셋)가 주어지면 처리기는 페이지 테이블을 이용하여 물리주소(프레임 숫자, 오프셋)를 생성합니다.

페이징과 오프셋은 시스템 아키텍처와 메모리 관리 전략에 따라 다를 수 있습니다.

만약 가상 주소 공간이 32비트이고 페이지당 4KB라면,  페이지 번호와 오프셋으로 나뉘게 됩니다.

• 20비트: 페이지 번호 (1024byte * 4 = 4096KB)
• 12비트: 오프셋 (2^12 = 4096) 
• 총 오프셋 개수 : 2^20 * 2^12 = 2^32

8. 세그먼테이션

세그먼테이션은 페이지 번호와 오프셋을 사용하는 것은 동일하지만, 페이징과 달리, 메모리 관리가 가변적입니다. 세그멘테이션은 논리적인 메모리 구조를 지원하므로 프로그램의 모듈화가 용이하지만, 외부 단편화 문제가 발생할 수 있습니다.

>> 외부 단편화가 발생하는 이유는 메모리 공간이 가변적이기 때문에 스왑아웃되어 다른 프로세스가 메모리 공간을 점유하려고 할 때 그 공간이 메모리 요구조건을 만족시키지 않을 가능성이 높기 때문입니다.

이상으로 메모리 관리에 대한 글을 마치도록 하겠습니다.

감사합니다.!

자료 출처(그림 1) : https://m.blog.naver.com/PostView.naverisHttpsRedirect=true&blogId=qkreorb0321&logNo=110178025041 

자료 출처 (그림 2): https://www.crocus.co.kr/1376

출처: 운영체제 8판 내부구조 및 설계원리

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 상호 배제의 방법으로 Hoare(토니 호어)의 모니터 방식과 Lampson/Redell의 모니터 방식을 정리하도록 하겠습니다.

이전 포스팅은 운영체제에서 공유 자원의 상호 배제 방법으로 세미포어를 활용하는 것을 정리하였습니다. 세미포어는 상호 배제 보장과 프로세스 간 협력을 위해 사용되는 강력하고 유연한 프리미티브이지만, 구현하기가 어렵고 모듈화가 되지 않는다는 단점이 있습니다. 이러한 문제를 해결하기 위한 방법으로 '토니 호어'가 '모니터'를 제안하였습니다.

1. 모니터

모니터는 프로그래밍 언어 수준에서 제공되는 구성체로 세마포어와 동일한 기능을 제공합니다. 모니터에 대한 개념은 Concurrent Pascal, Java 등 다양한 언어로 구현되어 있습니다. 

Hoare가 제안한 시그널 기반 모니터

• 지역 변수는 모니터의 프로시저를 통해 접근 가능합니다. 즉, 외부에서 변수에 대한 직접 접근은 허용되지 않습니다.
• 프로세스는 모니터의 프로시저 중에 하나를 호출함으로써 모니터로 들어갑니다.
• 한 순간에 오직 하나의 프로세스만이 모니터 내에 존재할 수 있습니다. 즉, 모니터가 이미 사용 중인 경우 다른 프로세스들은 모니터가 이용 가능해질 때까지 대기해야 합니다. (상호 배제)
• 모니터는 동기화를 위해 조건 변수(condition variabls)를 제공합니다. 조건 변수는 모니터 내부에 포함되며, 모니터 내부에서만 접근할 수 있습니다.
• cwait(c): 호출한 프로세스를 조건 c에서 일시 중지합니다. 모니터는 이제 다른 프로세스에서 사용될 수 있습니다.
• csignal(c): cwait(c)에 의해 중지되었던 프로세스의 수행을 다시 재개시킵니다. 만일 중지된 프로세스가 여러 개일 경우 그 중하나를 선택합니다. 만약 중지된 프로세스가 없다면 시그널은 아무 일도 일어나지 않습니다.

2. 모니터 수행 과정

• A 프로세스 지역 변수 x와 관련된 프로시저 호출
• B 프로세스가 모니터 진입점에서 진입 시도
• 모니터를 프로세스 A가 이미 사용 중이므로 대기 큐[x]에 블록
• 프로세스가 지역 변수 x 관련 프로시저를 마친 경우 cSignal(x) 호출
• 이전에 중단된 프로세스C가 있다면 프로세스 블록 큐에서 호출하여 진행 

3. 기존 모니터 모델의 단점

• cSignal을 호출한 프로세스가 호출 이후 여전히 해야 할 작업이 남아 있다면, 두 번의 추가적인 프로세스 문맥 교환이 필요합니다. 한 번은 호출한 프로세스를 일시중지 시키고, 모니터가 다시 사용하게 되었을 때, 재개시키기 위해 필요합니다.
• 스케줄러는 cSignal 호출로 인해 cWait() 중인 프로세스가 블록 큐에서 나와 실행되어 다른 프로세스가 모니터에 들어가지 않도록 해야 합니다. 만약 계속 새로운 프로세스가 모니터에 입장할 경우 블록 큐에 있는 프로세스는 계속 대기상태에 있을 수 있습니다.

저는 처음에 스케줄러는 cSignal 호출로 인해 cWait() 중인 프로세스가 블록 큐에서 나와 실행되어 다른 프로세스가 모니터에 들어가지 않도록 해야 하는 부분이 자세히 이해가 되지 않았습니다. 

하지만 위에서 정리한 수행 과정에 하나의 예시를 더 추가해보고 생각해 보았더니 이해할 수 있었습니다.

• 자원 소비를 담당하는 프로세스 A 모니터 진입 -> 조건 a에 대해 cWait(a)로 모니터에서 나와 블록 큐로 이동
• 자원 소비를 담당하는 프로세스 C가 대기 큐에 모니터 진입 -> 조건 a에 대해 cWait(a)로 모니터에서 나와 블록 큐로 이동
• 현재 블록 큐 (A, C) 순서
• 자원 추가를 담당하는 프로세스 D가 대기 큐에서 모니터 진입 -> 조건 a를 만족하여 cSignal(a) 호출
• 대기 큐에 프로세스E가 있더라도 블록 큐에 있는 A를 모니터에 진입하여 cWait() 이후 과정을 수행할 수 있도록 수행

4. Lampson과 Redell의 모니터 모델

토니 호어의 모니터 모델의 단점을 극복하기 위해 Lampson과 Redell이 다른 모니터 모델을 개발하였습니다.

• csignal() -> cnotify()로의 도입으로 각 조건 변수에 대한 최대 대기 시간을 설정할 수 있습니다.
• 주요 변경 로직은 if 로 설정된 조건을 while로 대체하는 소스입니다. while( count == N) cwait(notfull);
• 조건 변수에 감시 타이머를 설정하여 최대 대기 시간을 기다린 프로세스는 다시 준비 상태로 전이시킬 수 있습니다.
• cbroadcast의 추가로 대기하고 있는 모든 프로세스를 전부 깨울 수 있습니다. 이 효과는 메모리 10이 확보되었을 때, 메모리에 충족하는 특정 프로세스만 실행시켜야 할 때, 전부 프로세스를 깨움으로써 가용한 프로세스를 수행시킬 수 있습니다.

이 부분에서 while()에 대한 이해되지 않는 부분이 생겼습니다. while 루프를 활용한다면 무한 루프에 빠지지 않을까라는 궁금증입니다. 하지만, 이 부분은 너무나 명쾌하게 해결할 수 있는 문제였습니다. 실제 블록 큐로 이동하게 된다면 큐에서 빠져나오지 않는 한 cpu에서 실행되지 않습니다. cnotify나 cbroadcast를 호출할 때 비로소 큐에서 빠져나와 할당받을 수 있으며 다시 while 루프에서 자원에 대한 조건을 처리하므로 안정적으로 자원에 대한 상호배제와 동기화를 처리할 수 있습니다.

이상으로 상호 배제의 모니터에 대한 글을 마치도록 하겠습니다.

읽어주셔서 감사드립니다.!!!

출처 (사진 1) : http://blog.skby.net/%EC%83%81%ED%98%B8-%EB%B0%B0%EC%A0%9C-%EA%B8%B0%EB%B2%95-%EB%AA%A8%EB%8B%88%ED%84%B0-monitor/

자료 출처: 운영체제 8판 내부구조 및 설계원리

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 운영체제의 세마포어에 대한 개념을 정리하고자 합니다.

1. 세마포어란

• 프로세스 간에 시그널을 주고받기 위해 사용되는 정수 값으로, 세마포어는 3가지 원자적인 연산을 지원합니다.
  initialize, decrement, increment
• decrement 연산은 프로세스를 블록 시킬 수 있습니다. 반면 increment 연산은 블록되었던 프로세스를 깨울 수 있습니다.
• 복잡한 프로세스 간 상호작용 속에서 세마포어 s를 통해 시그널을 전송하기 위해 프로세스는 semSignal(s)라는 프리미티브를 수행합니다.
• 반면, 세마포어 s를 통해 시그널을 수신하기 위해 프로세스는 semWait(s)라는 프리미티브를 수행합니다.
• 종류는 범용 세마포어, 이진 세마포어 등이 있습니다.

2. 세마포어 연산

• 세마포어 초기화: 세마포어는 음이 아닌값으로 초기화됩니다.
• semWait 연산: 세마포어 값을 감소시킵니다. 만일 값이 음수가 되면, semWait를 호출한 프로세스는 블록됩니다. 음수가 아니면 프로세스는 계속 수행됩니다.
• semSignal 연산: 세마포어 값을 증가시킵니다. 만약 값이 양수가 아니면 semWait 연산에 의해 블록된 프로세스를 깨웁니다.

3. 세마포어의 사용 예

세마포어는 여러 프로세스 또는 스레드가 공유 리소스에 동시 접근하는 것을 제어하는데 사용됩니다. 

• 공유 메모리 : 여러 프로세스가 동시에 메모리에 접근할 때, 서로 읽기 쓰기 작업이 충돌하지 않도록 보장하기 위해 사용됩니다.
• 파일 시스템: 여러 프로세스가 동시에 파일이나 디렉토리에 접근할 때, 데이터 일관성을 유지하기 위해 사용됩니다.
• 프로세스간 통신: 여러 프로세스가 메세지를 전달하거나 데이터를 주고받을 때, 동기화를 위해 사용됩니다.
• 데이터베이스 시스템: 여러 사용자나 애플리케이션에서 동시에 데이터베이스에 접근할 때, 트랜잭션의 원자성과 일관성을 보장하기 위해 사용됩니다.

4. 세마포어 프리미티브

< 범용 세마포어 프리미티브 >

public class OsExample {

    class GeneralSemaphore {
        int count;
        Queue<Pid> queue;
    }

    class Pid {
        public Pid() {}
    }


    void semWait(GeneralSemaphore s) {
        s.count--;
        if (s.count < 0) {
            /* 요청한 프로세스를 s.queue에 연결 */
            /* 요청한 프로세스를 블록 상태로 전이시킴 */
        }
    }

    void semSignal(GeneralSemaphore s) {
        s.count++;

        if (s.count <= 0) {
            /* s.queue에 연결되어 있는 프로세스를 큐에서 제거 */
            /* 프로세스 상태를 실행 가능으로 전이시키고 redy list에 연결 */
        }
    }
}

< 이진 세마포어 프리미티브 >

public class BinarySemaphoreEx {

    class BinarySemaphore {
        Value value;
        Queue<Pid> queue;
    }

    class Pid {
        public Pid() {}
    }

    void semWaitB(BinarySemaphore s) {
        if (s.value == ONE) s.value = ZERO;
        else {
            /* 요청한 프로세스를 s.queue에 연결  */
            /* 요청한 프로세스를 블록 상태로 전이 */
        }
    }

    void semSignalB(BinarySemaphore s) {
        if (s.queue.isEmpty()) s.value = ONE;
        else {
            /* s.queue에서 프로세스 p를 제거  */
            /* 프로세스의 p의 상태를 실행 가능으로 전이, ready list에 연결 */
        }
    }
}

5. 세마포어 정책

범용 세마포어와 이진 세마포어 모두 세마포어에서 블록된 프로세스들을 관리하기 위해 큐를 사용합니다.

세마포어는 큐를 적용하는 정책에 따라 두 가지로 분리할 수 있습니다

강성 세마포어

프로세스들이 세마포어를 사용할 때, 먼저 semWait를 호출한 프로세스가 먼저 semSignal을 호출할 수 있는 순서로 실행됩니다. 

즉, 강력한 선입선출을 유지하여 많은 OS에서 강성 세마포어를 주로 사용하고 있습니다.

<강성 세마포어 실행 순서>

• 프로세스 D 실행 s = 1 (S는 D가 실행되면 +1 )
• D는 준비 큐 대기
• A프로세스, B프로세스, D 준비 상태
• A 프로세스가 스케줄링 -> A가 semWait() 호출 -> s 소비 -> s = 0 -> A 실행
• B 프로세스 semWait() 호출 -> s <= 0 이므로 s = -1한 후, B 블록 큐 이동
• A 프로세스 타임아웃으로 준비 큐 대기
• D 프로세스 semSignal() 호출로 s++, 이어서 블록 큐에서 프로세스 B 호출
• B가 실행 후, 종료
• C가 준비 큐에서 스케줄링 -> semWait()를 호출 -> s = 0이므로  s--, C는 블록
• A가 준비 큐에서 스케줄링 -> semWait()를 호출 -> s = -1이므로 s--. A는 블록
• D가 준비 큐에서 스케줄링 -> semSignal()를 호출 -> s++, s-= -1, 블록된 'C' 실행

약성 세마포어

약성 세마포어는 큐를 사용하거나 혹은 다른 매커니즘을 사용할 수 있습니다. 만약 적용되는 프로세스가 실행 순서에 대한 요구사항이 없다면 다른 동기화 매커니즘을 사용하여 실행 순서를 관리할 수 있습니다. 따라서, 약성 세마포어는 '기아' 상태가 발생할 수 있습니다.

6. 상호 배제

세마포어를 사용할 경우, 공유 자원에 접근하려는 n개의 프로세스를 상호 배제할 수 있습니다.

프로세스가 공유 자원을 접근하려는 코드 부분이 임계영역으로 정의되고, 긱 프로세스는 임계영역에 들어가기 전 semWait를 호출합니다. s의 값의 범위에 따라 해당 프로세스의 블록이 결정됩니다.

만약 s가 양수라면 임계영역 내부로 입장하고, 임계 영역에서 나오며 s를 다시 증가킵니다.

따라서, s.count는 다음과 같이 정리할 수 있습니다.

• s.count >= 0 : s.count는 현재 임계영역에 블록됨이 없이 진입할 수 있는 프로세스의 수를 나타냅니다.
• s.count < 0: s.count의 절대값은 s.queue에 블록되어 있는 프로세스의 수를 나타냅니다.

운영체제는 공부해도 시간이 지나면 헷갈리고 잊어버리게 되는 것 같습니다.

꾸준히 정리하며, 공부를 이어나가도록 하겠습니다.

감사합니다!

- 자료 출처 : 운영체제 8판 내부구조 및 설게원리