메모리 관리

1. 메모리 관리의 개념

메인메모리는 운영체제를 위한 영역과 실행중인 프로그램 영역으로 구분됨

• 다중프로그래밍 시스템에서 운영체제에 의해 동적으로 메모리의 사용자 영역을 여러 프로세스가 상주할 수 있도록 세분화 하는 과정

반입정책

• 메인 메모리에 적재할 다음 프로세스의 반입시기를 결정하는 방법

1. 요구 반입 기법
   • 운영체제나 시스템 프로그램, 사용자 프로그램 등의 참조요구에 따라 메인메모리에 적재하는 방법으로 오랫동안 사용됨
2. 예상 반입 기법
   • 시스템의 요구를 예측하여 메모리에 미리 적재하는 방법으로 최근 사용되기 시작함
   • 요구되는 페이지 외의 다른 페이지도 함께 불러들이며, 탐색시간과 회전지연시간을 갖는 보조기억장치의 특성을 참조한 정책

배치정책

• 디스크에서 반입한 프로세스를 메인메모리에 어느 위치에 저장할 것인가를 결정하는 방법

대치정책

• 재배치 기법으로 메인메모리에 있는 어떤 프로세스를 제거할 것인가를 결정하는 방법

2. 메모리 해석에 대한 두 가지 관점

절대 주소와 상대 주소

1) 절대 주소(물리적 주소)

• 실제 물리 주소를 가리키는 주소

• 실제 데이터나 프로그램이 저장되는 공간(RAM, 레지스터 등)

2) 상대 주소(논리적 주소)

• 사용자 영역이 시작되는 번지를 0번지로 변경하여 사용하는 주소
• 사용자 프로세스 입장에서 바라본 주소
• 절대 주소와 관계없이 항상 0번지 부터 시작

메모리 매핑(주소 바인딩)

• 프로세스의 상대 주소를 메모리의 절대 주소로 변환하는 과정

• 메모리관리자(MMU)인 하드웨어에서 실행

MMU(Memory Management Unit)

• 상대 주소를 절대 주소로 매핑해주는 하드웨어 장치

• 재배치 레지스터(Relocation Register)와 한계 레지스터(Limit Register)를 사용하여 매핑한다

  • 재배치 레지스터: 주소변환의 기본이 되는 주소값을 가진 레지스터로, 메모리에서 사용자 영역의 시작 주소값이 저장.
  • 한계 레지스터: 해당 프로세스의 크기를 저장, 만약 요청한 상대 주소가 이 값을 벗어나는지 확인할 수 있음.

3. 메모리 낭비 방지 방법

동적 적재(Dynamic Loding)

• 프로세스가 시작될 때 프로세스 전체를 메모리에 적재시키는 것이 아니라 메모리를 좀더 효율적으로 사용하기 위해 필요한 루틴이 호출될 때 해당 루틴을 메모리에 적재하는 방식
• 프로그램 실행에 반드시 필요한 루틴/데이터만을 적재하는 것

장점/특징

• 사용하지 않는 루틴을 적재하지 않음
• 코드 양이 많이 필요한 경우 유용함
• 프로그램 전체 양은 많으나 실제로 사용된 구역은 작으며, 운영체제로부터 특별한 지원을 필요치 않음(동적 연결적재기는 제공되어야 함)
• 이용하기 위해서는 사용자 자신이 프로그램 설계를 책임져야 함.

동적 연결(Dynamic Linking)

• 프로그램을 메모리에 적재할 때, 프로세스에서 공통으로 사용되는 라이브러리 루틴을 메모리에 중복으로 올리는 것은 낭비로 Linking(Object File과 Library File을 묶어 실행 파일 생성)을 실행 시점에서 하는 방식

• 여러 프로그램에 공통 사용되는 라이브러리를 관리하는 방법

• 라이브러리 루틴 연결을 실행 시까지 미루고 오직 하나의 라이브러리 루틴만 메모리에 적재해서 이 루틴과 연결을 하도록 하는 방법

중첩(Overlay)

• 프로그램의 크기 > 실제 메모리의 크키인 경우에 전체 프로그램을 메모리에 가져오는 대신 적당한 크기로 잘라서 가져오는 방식

장점/특징

• 한정된 메모리에서 메모리보다 큰 프로그램 실행 가능
• 프로그램 전체가 아니라 일부만 메모리에 올라와도 실행 가능
• 프로그램이 실행되면 필요한 모듈만 메모리에 올라와 실행됨

프로세스 교체(Swaping)

• 주기억장치에 적재한 하나의 프로세스와 보조기억장치에 적재한 다른 프로세스의 메모리를 교체
• 현재 사용되지 않고 있는 프로세스를 관리
• 다중프로그래밍 환경에서 프로그램 수를 조절하여 성능 이슈를 해결하기 위함

• swap in: 메인 메모리로 데이터를 가져오는 작업, 새로 시갖하는 프로세스를 메모리에 적재
• swap out: 메인 메모리에서 데이터를 내보내는 작업, 수행이 완료 된 프로세스를 보조기억장치로 보냄

4. 메모리 관리 방식

연속 메모리 할당 방식

• 프로그램(프로세스)를 적재하는 과정에서 연속적인 공간에 적재되도록 하는 방식
  1. 고정 분할 방식
  2. 가변 분할 방식
  3. 버디 시스템

분산 메모리(비연속 메모리) 할당 방식

• 하나의 프로세스가 메모리의 여러 영역에 분산되어 적재되는 방식
  1. 페이징
  2. 세그먼테이션

1) 고정 분할 방식

• 고정된 경계를 갖는 메모리 영역으로 구분하여 영구적인 파티션 으로 미리 나누어 각 분할에 하나의 프로세스를 적재하여 실행하도록 하는 방식

1. 균등 분할
   • 사용 가능한 파티션이 있기만 하면 적재
   • 빈 공간이 없으면 준비상태가 아닌 기존 프로세스 스왑 아웃
2. 비균등 분할
   • 최적 파티션에 할당(내부 단편화 최소화)
   • 할당 방법으로 단일큐 방식과 파티션당 독립된 프로세스 큐 할당 방식이 있음.

장점

• 구현이 간단하며 운영체제의 오버헤드가 거의 없다

약점

• 최대 활성 프로세스의 수 고정: 시스템 생성시간에 미리 정해진 파티션의 수에 의해 시스템 내에서 활성화된 프로세스의 수가 제한을 받는다.

• 내부 단편화 발생: 시스템 생성시간에 파티션의 크기가 미리 정해지기 때문에, 크기작 작은 작업의 경우 파티션의 공간을 효율적으로 사용할 수 없다.

내부 단편화

• 빈 파티션이지만 프로세스보다 크기가 작아 이용될 수 없음
• 내부 공간의 낭비 발생

2) 가변 분할 방식

• 프로그램의 크기를 고려하여 파티션의 크기 및 개수를 동적으로 바꾸는 방식
• 어떤 프로그램이 종료되었을 때, 그 빈 파티션에서 외부 단편화가 발생할 수 있음

장점

• 내부단편화가 없고 주기억장치를 보다 효율적으로 사용할 수있다.

약점

• 외부단편화를 해결하기 위한 메모리집약이 요구된다.
  • 이로 인한 CPU의 효율이 나빠짐

외부 단편화

• 메모리가 할당되고 해제되는 작업 이 반복되며 중간중간에 생긴 사용하지 않은 메모리가 많이 존재하여 총 메모리 공간은 충분하지만 할당 할 수 없는 상황

배치 알고리즘

메모리 집약은 많은 시간이 소모되는 작업이기 때문에 운영체제는 프로세스를 할당할때 어떤 위치에 할당할것인지를 결정해야 한다.

1. 최적 적합(Best Fit)

• 메모리의 빈 공간을 모두 확인 한 후 요청된 크기와 가장 근접한 크기의 메모리를 선택

2. 최초 적합(First Fit)

• 메모리의 처음부터 검사해서 크기가 충분한 첫번째 사용 가능한 메모리 블록을 선택

3. 순환 적합(Next Fit)

• 가장 최근에 배치되었던 메모리의 위치에서부터 검사를 시작해 크기가 충분한 다음 위치의 사용가능한 메모리 블록을 선택

4. 최악 적합(Worst Fit)

• 메모리의 빈 공간을 모두 확인 한 후 크기가 가장 큰 파티션에 적재

3) 버디 시스템

• 고정 분할과 가변 분할 결점을 보안한 절충안
• 큰 버퍼들을 반복적으로 이등분하여 작은 버퍼들을 만들며, 가능할 때마다 인접한 빈 버퍼들을 합치는 과정 반복, 버퍼를 나눌 때 각각을 서로의 버디라고 함

특징

• 가변 분할 방식처럼 메모리가 프로세스 크기대로 나뉨
• 고정 분할 방식처럼 하나의 구역에 다른 프로세스가 들어갈 수 없고, 메모리 한 구역 내부에 조각이 생겨 내부 단편화 발생
• 비슷한 크기의 조각이 서로 모여 조각을 통합하여 큰 조각(메모리집약)을 만들기 쉬움

4) 페이징

• 작업의 크기가 동일한 페이지로 나눠 처리하는 방법

페이지(page)

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

프레임(frame)

• 페이지와 크기가 같은 주기억장치 메모리 조각

페이지 테이블

• 프로세스의 각 페이지에 해당하는 프레임 위치 관리

특징

• 빈 프레임에 어떤 페이지든 적재할 수 있어 메모리를 효율적으로 사용
  • 프레임 간 외부 단편화가 발생하지 않음
• 한 프로세스의 페이지를 메인 메모리의 여러 위치에 분산 적재됨
  • 운영체제의 페이지 관리 부담이 큼
• 프레임 단위로 할당되므로 내부 단편화는 발생
  • 어떤 프로세스의 메모리 요구가 페이지 범위 내에 맞지 않으면, 할당된 마지막 프레임은 완전히 가득 차지 않을

5) 세그먼테이션

COMMING SOON

Reference

『IT CookBook, 운영체제』, 구현회 집필, 한빛아카데미

『IT CookBook, 쉽게 배우는 운영체제』, 조성호 집필, 한빛아카데미

『운영체제 : 내부구조 및 설계원리 (6판)』, WILLIAM STALLINGS 저, PEARSON HALL

CPU 스케줄링 알고리즘

프로세스 스케줄러는 프로세스 스케줄링 알고리즘에 따라 프로세서를 할당하고 작업을 완료한다.

스케줄링 알고리즘의 선택기준

CPU 사용률

• 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법

• 가장 이상적인 수치는 100%이지만 실제로는 여러가지 이유로 90%에도 못 미침

처리량

• 단위 시간당 작업을 마친 프로세스의 수
• 이 수치가 클수록 좋은 알고리즘임

대기시간

• 프로세스가 생성된 후 실행되기 전까지 대기하는 시간

응답시간

• 첫 작업을 시작한 후 첫 번째 출력(반응)이 나오기까지의 시간

실행시간

• 프로세스 작업이 시작된후 종료되기 까지의 시간

반환시간

• 대기시간을 포함하여 실행이 종료될 때까지의 시간

평균 대기시간

• 모든 프로세스의 대기시간을 합한 뒤 프로세스의 수로 나눈 값

FCFS 스케줄링

선입 선처리(FCFS, First Come First Served) 스케줄링은 비선점 기법으로 프로세서 스케줄링 알고리즘 중 가장 간단하다. 프로세서를 요구하는 순서로 프로세서를 할당하는 방법으로 선입선출(FIFO, First In First Out) 큐로 구현한다. 일괄 처리 시스템에서는 매우 효율적이나 대화식 시스템에서는 사용자가 빠른 응답을 요구하기 때문에 적합하지 않다

프로세스가 준비 큐에 들어오면, 즉 새로운 작업이 시스템에 들어오면 프로세스의 프로세스 제어블록(PCB)은 준비 큐의 마지막에 연결된다. 차례가 되면 준비 큐의 앞부분에 잇는 프로세스는 프로세서를 할당 받고 준비 큐에서 삭제된다. 선입 선처리 성능은 좋지 않은 경우가 많으며 평균 대기시간이 긴 경우도 가끔 있다.

동작 방식

• 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식
• 한 번 실행되면 그 프로세스가 끝나야만 다음 프로세스를 실행할 수 있음
• 큐가 하나로 모든 프로세스의 우선순위는 동일함

성능

프로세스 도착 순서와 작업의 시간

FCFS 스케줄링의 평균 대기시간

※ 평균 대시 시간은 $(0+27+41)\div3=23$

평가

• 처리량이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려 시스템의 효율성이 떨어지는 문제가 있는데 이를 콘보이 효과(Convory effect) 또는 호위 효과라고 함
• 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율이 떨어짐

SJF 스케줄링

최소작업 우선(SJF, Shortest Job First) 스케줄링은 프로세서 버스트 시간이 짧은 작업에 프로세스를 할당하는 기법이다. 이때 두 프로세스가 다음 순서로 동일한 프로세서 버스트를 가진다면 선입 선처리 스케줄링을 적용한다.

동작 방식

• 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식
• 콘보이 효과를 완화하여 시스템의 효율성을 높임

성능

SJF 스케줄링의 평균 대기시간

※ 평균 대기시간은 $(0+24+36)\div3=20$

평가

• 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어려움
• 작업시간이 길다는 이유만으로 계속 뒤로 밀려 공평성이 현저히 떨어짐 >> 아사(starvation) 현상이 발생할수 있음

에이징

• 아사현상의 완화방법
• 프로세스가 양보할 수 있는 상한선을 정하는 방식
• 프로세스가 자신의 순서를 양보할 때마다 나이를 한 살씩 먹어 최대 몇 살까지 양보하도록 규정하는 것

HRN 스케줄링

최고 응답률 우선 (HRN, Highest Response-Rate Next) 스케줄링은SJF 스케줄링 알고리즘의 약점이었던 긴 작업과 짧은 작업간의 지나친 불평등을 어느정도 보완한 알고리즘이다.

동작방식

• SJF 스케줄링에서 발생할 수 있는 아사현상을 해결하기 위해 만들어진 비선점형 알고리즘
• 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링을 하는 방식
• 프로세스의 우선순위를 결정하는 기준

$$
우선순위= \frac{대기한\ 시간+CPU\ 사용\ 시간}{CPU\ 사용\ 시간}
$$

CPU 사용 시간이 분모에 있으므로 CPU 사용 시간이 짧은 작업이 우선순위가 높다. 그리고 대기한 시간이 분자에 있으므로 CPU 사용 시간이 긴 작업에도 대기한 시간이 큰경우에는 우선순위가 높아진다.

성능

HRN 스케줄링의 평균 대기시간

※ 평균 대기시간은 $(0+24+36)\div3=20$

평가

• 실행 시간이 짧은 프로세스의 우선순위를 높게 설정하면서도 대기 시간을 고려하여 아사현상을 완화
• 대기 시간이 긴 프로세스의 우선순위를 높임으로써 CPU를 할당받을 확률을 높임
• 여전이 공평성이 위배되어 많이 사용되지 않음

라운드 로빈 스케줄링

순환 할당(Round Robin) 스케줄링은 시분할 시스템을 위해 특별히 설계되었다. 이 순환 알고리즘은 규정 시간량(Time Quantum) 또는 시간 할당량(Time Slice)라고 하는 작은 단위의 사간을 정의한다. 준비 큐는 순환 큐로 설계하여 프로세서 스케줄러가 준비 큐를 돌아가면서 한 번에 한 프로세스에 정의된 규정 시간량 만큼의 프로세서를 제공한다.

동작방식

• 한 프로세스가 할당받은 시간(타임 슬라이스)동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식
• 선점형 알고리즘 중 가장 단순하고 대표적인 방식
• 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행

성능

라운드 로빈 스케줄링의 평균 대기 시간

※ 총 대기 시간은 $0(P_1)+7(P_2)+14(P_3)+19(P_1)+19(P_2)+8(P_1)=67$

※ 평균 대기 시간은 $67\div3=22.33$

타임 슬라이스의 크기와 문맥교환

• 라운드 로빈 스케줄링이 효과적으로 작동하려면 문맥 교환에 따른 추가 시간을 고려하여 타임 슬라이스를 적절히 설정해야 함
• 타임 슬라이스는 되도록 작게 설정하되 문맥 교환에 걸리는 시간을 고려하여 적당한 크기로 하는 것이 중요

타임 슬라이스가 큰 경우

• 하나의 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보여 FCFS 스케줄링과 다를게 없음

타임 슬라이스가 작은 경우

• 문맥 교환이 너무 자주 일어나 문맥 교환에 걸리는 시간이 실제 작업 시간보다 상대적으로 커지며, 문맥 교환에 많은 시간을 낭비하여 실제 작업을 못하는 문제가 발생

※ 유닉스 운영체제에서는 타임 슬라이스가 대략 100 ms

SRT 우선 스케줄링

최소 잔여 시간 우선 (SRT, Shortest Remaining Time) 스케줄링은 SJF 스케줄링과 라운드 로빈 스케줄링을 혼합반 방식이다. 쉽게 말해 SJF의 선점형 버전이라 할 수 있다. SRT 스케줄링은 기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당 받을 프로세스를 선택할 때 남야 있는 작업 시간이 가장 적은 프로세스를 선택한다. 라운드 로빈 스케줄링이 큐에 있는 순서대로 CPU를 할당한다면, SRT 스케줄링은 남은 시간이 적은 프로세스에 CPU를 먼저 할당한다.

동작방식

• 기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당받을 프로세스를 선택 할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택

성능

SRT 스케줄링의 평균 대기시간

※ 총 대기 시간은 $0(P_1)+4(P_3)+16(P_2)+27(P_1)=47$

※ 평균 대기 시간은 $47\div3=15.66$

평가

• 현재 실행 중인 프로세와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세와 문맥 교환을 해야 하므로 SJF 스케줄링에는 없는 작업이 추가됨
• 운영체제가 프로세의 종료 시간을 예측하기 어렵고 아사 현상이 일어나기 때문에 잘 사용하지 않음

우선순위 스케줄링

프로세스는 중요도에 따라 우선순위(Priority)를 갖는데 이러한 우선순위를 반영한 스케줄링 알고리즘이 우선순위 스케줄링이다. 우선순위 스케줄링은 어떤 기준으로 우선순위를 정하느냐에 따라 다양하게 구현할 수 있다.

동작 방식 예

FCFS 스케줄링에 우선순위를 적용한 결과

우선순위 적용

• 우선순위는 비선점형 방식과 선점형 방식에 모두 적용할 수 있음

SJF 스케줄링

• 작업시간이 짧은 프로세스에 높은 우선순위를 부여

HRN 스케줄링

• 작업 시간이 짧거나 대기 시간이 긴 프로세스에 높은 우선순위를 부여

SRT 스케줄링

• 남은 시간이 짧은 프로세스에 높은 우선순위를 부여

고정우선순위 vs 변동우선순위

고정우선순위

• 한 번 우선순위를 부여받으면 종료될 때 까지 우선순위가 고정
• 단순하게 구현할 수 있지만 시시각각 변하는 시스템의 상황을 반영하지 못해 효율성이 떨어짐

변동우선순위

• 일정 시간마다 우선순위가 변하며 일정 시간마다 우선순위를 새로 계산하고 이를 반영
• 복잡하지만 시스템의 상황을 반영하여 효율적인 운영 가능.

우선순위 스케줄링의 평가

• 준비 큐에 있는 프로세스의 순서를 무시하고 우선순위가 높은 프로세스에 먼저 CPU를 할당하므로 공평성을 위배하고 아사 현상을 일으김
• 준비 큐에 있는 프로세스의 순서를 무시하고 프로세스의 우선순위를 매번 바꿔야 하기 때문에 오버헤드가 발생하여 시스템의 효율성을 떨어뜨림

다단계 큐 스케줄링

다단계 큐(Multi-Level Queue) 스케줄링은 각 작업들을 서로 다른 묶음으로 분류할 수있을 때 사용하는 알고리즘이다. 준비상채의 큐를 종류별로 여러 단계로 분할하고 작업을 기억장치의 크기나 프로세스의 형태에 따라 어느 한 큐에 지정한다. 각 큐는 자신만의 독자적인 스케줄링 알고리즘을 갖고 있다. 또한 각 큐는 순서대로 절대적인 우선순위를 갖는다.

• 각 작업들을 서로 다른 묶음으로 분류할 수 있을 때 사용
• 준비 상태 큐를 종류별로 여러단계로 분할, 그리고 작업을 메모리의 크기나 프로세스의 형태에 따라 특정 큐에 지정, 각 큐는 자신만의 독자적인 스케줄링 알고리즘을 갖는다.

동작방식

• 우선순위에 따라 준비 큐를 여러 개 사용하는 방식
• 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입
• 우선순위는 고정형 우선순위를 사용
• 상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작됨

장점

• 응답이 빠르다

단점

• 여러 준비 큐와 스케줄링 알고리즘 때문에 추가 오버헤드가 발생한다.
• 우선순위가 낮은 큐의 프로세스는 무한정 대기하는 기아상태가 발생할 수 있다.

다단계 피드백 큐 스케줄링

다단계 큐 스케줄링은 작업이 시스템에 들어가면 한 큐에서만 고정되어 실행된다. 즉, 작업은 다른 큐로 옮겨지지 않는다. 이러한 방식은 스케줄링 부담이 적다는 장점이 있으나 융통성이 떨어진다는 단점도 있다.

다단계 피드백 큐(Multi-Level Feedback Queue) 스케줄링은 작업이 큐 사이를 이동할 수 있다. 이 기법은 프로세서 버스트의 특성에 따라 분리하여 구분한다.

그러나 높은 우선순위의 큐가 완전히 비어야 낮은 우선순위의 준비 큐에 있는 작업이 실행될 수 있기 때문에 낮은 우선순위의 큐에 입력된 작업이 무한정 기다리게 되는 하사현상에 빠질 수 있다는 문제점이 있다. 물론 특정 큐에서 오래 기다린 프로세스를 우선순위가 높은 큐로 이동시키거나, 프로세서 점유 시간이 긴 작업을 우선순위가 낮은 큐로 이동시켜서 기아상태를예방하는 에이징 기법을 활용한다.

프로세서 버스트의 특성에 따라 분리/구분하며, 작업이 큐 사이를 이동 가능함

• 어떤 작업이 요구하는 프로세서 시간이 너무 길면 작업을 낮은 단계 큐로 옮김
• 입출력 중심 작업과 전면작업(대화형 작업)을 높은 우선순위 큐에 놓고 프로세서 중심 프로세스는 낮은 우선순위 큐에 놓음.

알고리즘 구현시 고려사항

• 큐의 수
• 각 큐에 대한 스케줄링 알고리즘
• 작업을 좀 더 높은 우선순위의 큐로 격상시키는 시기를 결정하는 방법
• 작업을 좀 더 낮은 우선순위의 큐로 격하시키는 시기를 결정하는 방법
• 프로세스들이 어느 큐에 들어갈 것인가를 결정하는 방법
• 프로세스가 서비스를 받는 시기를 결정하는 방법

Reference

『IT CookBook, 운영체제』, 구현회 집필, 한빛아카데미

『IT CookBook, 쉽게 배우는 운영체제』, 조성호 집필, 한빛아카데미

『운영체제 : 내부구조 및 설계원리 (6판)』, WILLIAM STALLINGS 저, PEARSON HALLㅈ

CPU 스케줄링 개요

모든 프로세스들은 실행을 시작하면서부터 자신이 필요로 하는 자원을 경쟁적으로 운영체제에 요구하게 된다. 운영체제는 이들이 요청한 자원을 할당해주어야만 할 것이다.

CPU 입장에서의 자원은 실행시간을 의미하며, 운영체제는 스케줄링이라는 수단을 통해 각 프로세스에 실행시간을 할당한다.

1. CPU 스케줄링

• CPU 스케줄러는 프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정하는 일을 하며 CPU 스케줄링은 CPU 스케줄러가 하는 모든 작업을 가리킨다.
• 컴퓨터 시스템의 효율성은 어떤 프로세스에 CPU를 먼저 배정하느냐에 따라 달라지므로 CPU 스케줄링 작업의 형평성과 효율성을 결정하는 중요한 일이다.

2. 스케줄링의 단계

1) 작업 스케줄링(작업 선택) - 승인 스케줄링

• 고수준 스케줄링(장기 스케줄링)이라 부름
• 전체 시스템의 부하를 고려하여 작업을 시작할지 말지를 결정하여 시스템 내의 전체 프로세스 수를 조절하는 것
  • 다중 프로그래밍의 정도를 결정함.

2) 작업 승인과 프로세서 결정 스케줄링(사용권한)

• 중간수준 스케줄링(중기 스케줄링)이라 부름
• 전체 시스템의 활성화된 프로세스 수를 조절하여 과부화를 막는 것
  • 전체 프로세스 수를 조절해야 한다면 이미 활성화된 프로세스 중 일부를 보류 상태로 보내고 보류된 프로세스는 처리 능력에 여유가 생기면 다시 활성화 된다.

3) 프로세서 할당 스케줄링(디스패칭)

• 저수준 스케줄링(단기 스케줄링)이라 부름

  • 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정하는 것

3. CPU 스케줄링의 목적

CPU의 스케줄링의 목적은 응답시간이나 처리량, 효율성을 증대시키기 위해 CPU가 다음에 실행할 프로세스를 선택하는 것이라 할 수 있다.

1) 공평성

• 모든 프로세스가 자원을 공평하게 배정받아야 하며, 자원 배정 과정에서 특정 프로세스가 배제되어서는 안된다.

2) 효율성

• 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링을 하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 주어야 한다.

3) 안정성

• 우선순의를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야 한다.

4) 확장성

• 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야 한다
• 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되게 해야한다.

5) 반응 시간 보장

• 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 한다.

6. 무한 연기 방지

• 특정 프로세스의 작업이 무한히 연기되어서는 안된다.

4. 스케줄링 시 고려 사항

선점형 스케줄링과 비선점형 스케줄링

중요도

• 비선점형과 선점형 프로세스가 혼재하는 경우에는 비선점형 프로세스의 중요도를 매우 낮게 설정하여 선점형 프로세스에 영향을 덜 미치도록 한다.

프로세스 우선순위

대부분의 CPU 스케줄러는 우선순위를 사용한다. 우선순위가 있다는 것은 프로세스의 중요도가 다르다는 의미이다.

• 프로세스는 크게 커널프로세스와 일반 프로세스로 나뉜다.

• 커널 프로세스의 우선순위가 일반 프로세스보다 높다

• 시스템에는 다양한 우선순위 프로세스가 공존하며 우선순위가 높은 프로세스가 CPU를 먼저, 더 오래 차지한다.

• 일반 프로세스의 우선순위는 사용자가 조절할 수 있으며 시스템에 따라 높은 숫자가 높은 우선순위를 나타내기도 하고 낮은 숫자가 높은 우선순위를 나타내기도 한다.

CPU 집중 프로세스와 입출력 집중 프로세스

프로세스의 특징

프로세스는 생성된 후 준비, 실행, 대기 상태를 거쳐 완료된다. 준비 상태는 CPU를 할당받기 위해 기다리는 상태이므로 실제 작업이 일어나는 것은 실행 상태와 대기 상태이다. 프로세스는 CPU를 사용하여 작업을 하는 실행 상태또는 입출력을 요청하여 완료되기까지 기다리는 대기 상태가 있다.

프로세스의 실행은 CPU의 실행과 I/O 대기 사이클로 반복된다

이때 CPU를 할당 받아 실행하는 작업을 CPU burst, 입출력 작업을 I/O burst라 부른다.

CPU Burst

• 프로그램의 수행중에 연속적으로 CPU를 사용하는 단절된 구간
• 스케쥴링의 단위가 된다.

I/O Burst

• 프로그램의 수행중에 I/O작업이 끝날때까지 block되는 구간

프로세스 버스트 지속시간 빈도 그래프

• 이러한 분포는 적절한 프로세서 스케줄링 알고리즘을 선택하는 데 매우 중요한 기준이 됨.

CPU-bound process(CPU 집중 프로세스)

실행하는 동안 입출력은 자주 수행하지 않으면서 대부분의 시간을 어떤 계산을 하기 위해 CPU를 사용하는 프로세스를 의미한다

• CPU 버스트가 큰 프로세스
• 계산 위주의 작업 수행(CPU 중심 작업)
• 긴 CPU 버스트를 가진다.

I/O-bound process(입출력 집중 프로세스)

실생시간의 대부분을 CPU보다는 입출력을 위한 시간으로 사용하는 프로세스를 일컽는다.

• CPU를 사용하여 계산하는 시간보다 I/O에 많은 시간이 필요함
• 대부분의 대화형 프로세스(입출력 중심 작업)
• 짧은 CPU 버스트를 가진다.

전면 프로세스와 후면 프로세스

전면 프로세스

• GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스

• 현재 입력과 출력을 사용하는 프로세스

• 사용자와 상호작용이 가능하여 상호작용 프로세스라고도 함

후면 프로세스

• 사용자와 상호작용이 없는 프로세스

• 사용자의 입력 없이 작동하기 때문에 일괄 작업 프로세스라고도 함

• 전면 프로세스의 우선순위가 후면 프로세스보다 높음

5. 다중 큐

프로세스는 저마다 중요도가 다르며 프로세스의 중요도는 프로세스 제어블록에 표시된다. CPU 스케줄러는 모든 프로세스 제어 블록을 뒤저셔 가장 높은 우선순위의 프로세스에 CPU를 할당한다. 그러나 매번 모든 프로세스 제어블록을 검색하는 것은 번거로운 일이다.

준비 상태의 다중 큐

• 프로세스는 준비 상태에 들어올 때마다 자신의 우선순위에 해당하는 큐의 마지막에 삽입
• CPU 스케줄러는 우선순위가 가장높은 큐의 맨 앞에 있는 프로세스에 CPU 할당

프로세스의 우선순위를 배정하는 방식

1) 고정 우선순위 방식(static priority)

• 운영체제가 프로세스에 우선순위를 부여하면 프로세스는 끝날 때까지 바뀌지 않는 방식
• 프로세스가 작업하는 동안 우선순위가 변하지 않기 때문에 구현이 쉽다
• 시스템의 상황이 시시각각 변하는데 우선순위를 고정하면 시스템의 변화에 대응하기 어려워 작업의 효율이 떨어진다.

2) 변동 우선순위 방식(dunamic priority)

• 프로세스 생성 시 부여받은 우선순위가 프로세스 작업 중간에 변하는 방식
• 구현하기 어렵지만 시스템의 효율성을 높일 수 있다.

대기 상태의 다중 큐

• 시스템의 효율을 높이기 위해 대기 상태에서는 같은 입출력을 요구한 프로세스끼리 모아 놓음.
  • 시스템 내에는 다양한 종류의 입출력장치가 있기 때문에 한곳에 모아두는 것이 관리하기 더 불편함.

다중 큐 비교

준비 큐

• 한 번에 하나의 프로세스를 꺼내어 CPU를 할당(디스패치)

대기 큐

• 여러 개의 프로세스 제어블록을 동시에 꺼내어 준비 상태로 옮김
• 대기 큐에서 동시에 끝나는 인터럽트를 처리하기 위해 인터럽트 벡터라는 자료 구조를 사용함

Reference

『IT CookBook, 운영체제』, 구현회 집필, 한빛아카데미

『IT CookBook, 쉽게 배우는 운영체제』, 조성호 집필, 한빛아카데미

『운영체제 : 내부구조 및 설계원리 (6판)』, WILLIAM STALLINGS 저, PEARSON HALL

교착상태

교착상태 개념

• 둘 이상의 프로세스가 서로가 가진 한정된 자원을 요청하는 경우 발생하는 것으로, 프로세스가 진전되지 못하고 모든 프로세스가 대기 상태가 된다.
  • 영구적으로 블록되어 있는 상태

교착상태 조건

1. 상호배제(Mutual exclusion)

• 한 번에 한 프로세스만 해당 자원을 사용할 수 있어야 함(자원의 비공유)
  • 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 대기해야 함.

2. 점유와 대기(Hold and wait)

• 최소한 자원 하나를 보유하고 다른 프로세스에 할당된 자원을 얻기 위해 기다리는 프로세스가 있어야 함.

3. 비선점(No preemption)

• 자원은 선점될 수 없음. 즉 자원을 강제로 뺏을 수 없으며 자원을 점유하고 있는 프로세스가 끝나야 해제됨.

4. 환형대기(Circular wait)

• 프로세스 간에 닫힌 연결이 존재함
  • 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있음.

• 교착상태가 발생하기 위해서는 조건1 ~ 조건3이 기본적으로 필요하다.
• 이러한 세 가지 조건이 만족되면, 교착상태가 발생할 수 있다. (교착상태가 발생할 수 있는 필요조건)
  • 위의 세 조건만으로 교착상태가 실제로 발생하는 것은 아니다.
• 조건4까지 만족되면 교착상태가 발생할 수 있는 필요충분조건이 된다.
  • 조건4는 조건1 ~ 조건3의 결과에 의해 발생한다.

운영체제 교제에 따라 교착상태의 조건으로 조건1 ~ 4를 동일하게 다루고 있다.

하지만 교착상태 예방과 교착상태 회피의 명확한 구분을 위해 조건1 ~ 3과 조건4는 다르게 다루어야 한다.

조건1 ~ 3은 정책이며, 조건4는 이러한 정책에 의해 발생한 상태이기 때문이다.

조건1 ~ 4를 동일하게 다루면 이후 논의할 교착상태 예방과 교착상태 회피의 명확한 구분이 어려워 진다.

교착상태의 관리

교착상태를 해결하기 위한 다양한 접근 방법들이 제안 되었다.

1. 교착상태 예방
   • 교착상태의 발생 조건 1~4 중 하나를 시스템에서 허용하지 않는 것
2. 교착상태 회피
   • 현재 자원 할당의 상태에 따라 안전하게 자원 할당을 결정하는 것
3. 교착상태 회복
   • 교착상태가 발생하면 그것을 발견하고 회복하는 것

교착상태 예방

• 운영체제를 설계할 때 교착상태가 발생할 가능성을 없애는 것
  • 교착상태가 발생하기 위한 네 가지 필요충분조건 중 하나를 설계 단계에서 배재하는 것
• 교착상태 예방 방법은 크게 간접적인 방법과 직접적인 방법으로 구분
  • 간접적인 방법
    • 조건 1~3 중 하나를 허용하지 않는 것
  • 직접적인 방법
    • 조건4를 허용하지 않는 것

상호배제

• 시스템 내에 있는 상호 배타적인 모든 자원, 즉 독점적으로 사용할 수 있는 자원을 없애버리는 방법
• 현실적으로는 모든 자원을 공유할 수 없으며 상호 배제를 적용하여 보호해야 하는 자원이 있음
• 상호 배제를 무력화하는 것은 사실상 어려움

점유와 대기

• 최대 자원 할당
  • 프로세스가 작업을 수행하기 전에 필요한 모든 자원을 요청하고 획득해야 함.
  • 단점
    1. 모든 자원을 할당받기 위해 오랜 기간 기다릴 수 있다. (기아상태 발생 가능)
    2. 한꺼번에 할당 받은 자원 중 일부는 실제 수행이 끝날때쯤 사용될 도 있다.
    3. 프로세스가 미래에 사용될 모든 자원을 미리 알기는 어렵다.

비선점

1. 프로세스가 어떤 자원을 요청할 때, 요청한 자원이 사용 가능한지 검사.
   • 사용 가능하다면 자원 할당, 사용 불가능한 자신이 점유한 자원을 반납한 후 원래 자원과 새로 원하는 자원을 요청
2. 두 프로세스에 우선순위를 부여하여, 높은 우선순위의 프로세스가 그보다 낮은 순위의 프로세스가 점유한자원을 선점하여 해결.

환형대기

• 자원의 할당 순서를 정하여 교착상태를 예방
  • 모든 자원에 일련의 순서를 부여, 각 프로세스는 오름차순으로만 자원을 요청할 수 있게 함

예

두 자원 $R_i$ 와 $R_j$ 가 있으며, 운영체제가 $i<j$ 인 할당 순서를 정했다고 하자.

$i<j$ 는 $R_i$ 가 먼저 할당되어야 하며 그 이후에 $R_j$ 가 할당될수 있다는 것을 의미한다.

프로세스 $P$ 가 자원 $R_i$ 를 할당하고 $R_j$ 를 요청했다고 하자.

이 상황에서 교착상태가 발생하려면 다른 프로세스 $Q$ 는 $R_j$ 를 할당하고 $R_i$ 를 요청해야 한다.

하지만, 이것은 운영체제의 자원 할당 순서에 위배개기 때문에 나타날수 없다.

결국, 자원들의 할당 순서를 정하면 교착상태가 발생하지 않는 것이다.

교착상태 회피

• 교착 상태의 모든 발생 가능성을 미리 제거하는 것이 아닌 교착 상태 발생할 가능성 인정하고(세 가지 필요조건 1~3 허용), 교착 상태가 발생하려고 할 때 적절히 회피하는 것
• 예방 방법에 비해 더 많은 병행성을 제공(자원의 효율성이 높음)

• 교착상태 회피를 위한 두가지 방법

  1. 프로세스의 시작중단
     • 프로세스의 요구가 교책상태가 발생할 수 있다면 프로세스를 시작을 중지함
  2. 자원 할당 거부(은행원 알고리즘)
     • 프로세스가 요청한 자원을 할당했을때, 교착상태가 발생할 수 있다면 요청한 자원을 할당하지 않음

• 어떤 프로세스가 요청을 할 때 미래에 대한 분석을 통해 교착상태를 회피
  • 교착상태를 회피하기 위한 알고리즘을 위해서는 프로세스가 현재 사용 가능한 자원, 다른 프로세스에 할당된 자원 등 각 프로세스에 대한 요구와 해제 정보가 필요

안정상태와 불안정상태

교착상태 회피를 위해 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정상태와 불안정한 상태로 나누고 시스템이 안정상태를 유지하도록 자원을 할당

안정상태

• 시스템이 교착상태를 일으키지 않으면서 각 프로세스가 요구한 최대 요구량만큼 필요한 자원을 할당해 줄 수 있는 상태

불안정상태

• 안정 상태와 달리 프로세스의 자원 할당 및 해제의 순서가 불명확하여 교착상태의 발생가능성이 존재

교착상태

• 교착 상태는 불안정 상태의 일부분이며, 불안정 상태가 커질수록 교착 상태가 발생할 가능성이 높아짐

은행원 알고리즘

COMMING SOON

교착상태 회복

자원의 접근에 대한 제한이나 프로세스의 행위에 제한을 두지않기 때문에 교착상태가 발생할수 있다.

따라서

1. 교착상태가 발생했는지를 파악하기위해 시스템 상태를 주기적으로 검사
2. 교착상태로부터 회복

의 기능을 지원해야한다.

교착상태 탐지

COMMING SOON

교착상태로부터 회복

• 교착상태를 회복한다는 것은 환형대기에서 탈피한다는 것인데 이를 위한 방법으로 2가지 방법을 사용할 수 있음

1. 프로세스 종료

1) 교착상태 프로세스를 모두 중지

• 교착상태의 순환대기를 확실히 해결하지만 자원 사용과 시간 면에서 비용이 많이 듬.
• 오랫동안 연산했을 가능성이 있는 프로세스의 부분 결과를 폐기하여 나중에 다시 연산해야 함.

2) 한 프로세스씩 중지

• 한 프로세스가 중지될 때마다 교착상태 탐지 알고리즘을 호출하여 프로세스가 교착상태에 있는지 확인.
• 교착상태 탐지 알고리즘 호출에 대한 부담이 큼.

2. 자원 선점

• 프로세스의 자원을 선점하여 교착상태가 해결될 때까지 선점한 자원을 다른 프로세스에 할당하여 이용
• 다음의 세가지 사항을 해결해야 함.

1) 희생자 선택(selection of a victim)

자원 선점에 앞서 어떤 자원과 어느 프로세스가 선점될 것인가?

• 프로세스를 종료할 때, 비용을 최소화하기 위해 적절한 선점 순서를 결정해야 함.
• 비용 요인은 교착상태 프로세스가 점유하고 있는 자원 수, 교착상태 프로세스가 지금까지 실행하는 데 소용한 시간과 같은 매개변수가 포함됨.

2) 롤백(rollback)

만약 특정 프로세스을 자원을 강제로 방출하고 선점시켰다면, 그 프로세스를 어떻게 처리 할 것인가?

• 필요한 자원을 읽은 프로세스는 정상적으로 실행할 수 없으므로, 프로세스를 안정상태로 복귀시키고 다시 시작해야 함.

  • 단순한 방법은 완전히 복귀시키고(프로세스를 중지) 재시작하는 것이며, 프로세스를 교착상태에서 벗어날 정도로만 복귀시킬 수 있다면 더 효과적임.
  • 시스템이 실행하는 모든 프로세스의 상태 정보를 유지해야 하는 부담이 존재함.

3) 기아 상태(starvation)

자원 선점을 통해 기아상태가 발생하지 않을까?

• 동일한 프로세스가 자원들을 항상 선점하지 않도록 보장할 때, 비용에 근거한 시스템은 동일한 프로세스가 희생자로 선택되기 쉬움.

  • 이는 프로세스가 자신의 작업을 완료하지 못하는 기아상태가 되어 시스템 조치를 요구함.

• 프로세스가 짧은 시간 동안만 희생자로 지정됨을 보장해야 함.

• 일반적인 해결 방법은 비용 요소에 복귀 횟수를 포함시키는 것.

Reference

『IT CookBook, 운영체제』, 구현회 집필, 한빛아카데미

『IT CookBook, 쉽게 배우는 운영체제』, 조성호 집필, 한빛아카데미

『운영체제 : 내부구조 및 설계원리 (6판)』, WILLIAM STALLINGS 저, PEARSON HALL

상호배제 방법

데커 알고리즘

• 하드웨어의 도움 없이 프로세스 두 개의 상호배제 문제를 해결.

특징

• 특별한 하드웨어 명령문을 필요로 하지 않는다.
• 임계 영역 바깥에서 수행 중인 프로세스가 다른 프로세스들이 임계 영역 진입 막지 않는다.
• 임계영역에 들어가기를 원하는 프로세서로 하여금 무한정 기다리게 하지 않는다.

01     program dekkersalgorithm;
02     var fprocess: (first, second);                                  // 공유 변수
03         P1_enter, P2_enter : boolean;
04     procedure P1;                                                   // 프로세스 P1의 임계영역 진입 절차
05         begin
06             while true do
07                 begin
08                     P1_enter := true;                               // P1이 임계영역 진입 시도
09                     while P2_enter do;                              // P2의 임계영역 진입 여부 확인
10                         if fprocess = second then                   // P2의 진입 차례(기회)라면
11                         begin
12                             P1_enter := false;                      // P2에게 진입 순서 양보
13                             while fprocess = second do;             // 순서 기다림(P2 완료)
14                                 P1_enter := true                    // P1이 임계영역 재진입 시도
15                             end;
16                     criticalsectionone;                             // 임계영역
17                     fprocess := second;                             // P2에게 진입 순서 양보
18                     P1_enter := false;                              // P1의 임계영역 사용 완료 지정
19                     otherstuffone                                   // P1의 잔류영역 수행
20                 end;
21         end;
22     procedure P2;
23         begin
24             while true do
25                 begin
26                     P2_enter := true;
27                     while P1_enter do;
28                         if fprocess = first then
29                             begin
30                                 P2_enter := false;
31                                 while fprocess = first do;
32                                 P2_enter := true;
33                             end;
34                     criticalsectiontwo;
35                     fprocess := first;
36                     P2_enter := false;
37                     otherstufftwo
38                 end;
39         end;
40     begin
41         P1_enter := false;
42         P2_enter := false;
43         fprocess := first;
44         parbegin
45             P1;
46             P2;
47         parend;
48     end.

기타 유용한 상호배제 알고리즘

다익스트라 알고리즘

• 최초로 프로세스 n개의 상호배제 문제를 소프트웨어적으로 해결.
• 실행 시간이 가 장 짧은 프로세스에 프로세서 할당하는 세마포 방법.
• 가장 짧은 평균 대기시간 제공

크누스 알고리즘

• 이전 알고리즘 관계 분석 후 일치하는 패턴을 찾아 패턴의 반복을 줄여서 프로세스에 프로세서 할당.
• 무한정 연기할 가능성을 배제하는 해결책을 제시했으나, 프로세스들이 아주 오래 기다려야 함

램포트 알고리즘

• 사람들로 붐비는 빵집에서 번호표 뽑아 빵 사려고 기다리는 사람들에 비유해서 만든 알고리즘
• 준비 상태 큐에서 기다리는 프로세스마다 우선순위를 부여하여 그중 우선순위가 가장 높은 프로세스에 먼저 프로세서를 할당
• ‘램포트의 베이커리(빵집) 알고리즘’이라고 함.

핸슨 알고리즘

• 실행 시간이 긴 프로세스에 불리한 부분을 보완하는 것.
• 대기시간과 실행 시간을 이용하는 모니터 방법.
• 분산 처리 프로세서 간의 병행성 제어 많이 발표

TestAndSet

• 공유 변수 수정하는 동안 인터럽트 발생 억제하여 임계 영역 문제 간단 해결
• 항상 적용할 수 없고 실행 효율 현저히 떨어짐
• 소프트웨어적인 해결책은 더 복잡하고 프로세스가 2개 이상일 때는 더 많은 대기 가능성
• 메모리 영역의 값에 대해 검사와 수정을 원자적으로 수행할 수 있는 하드웨어 명령어
• 알고리즘이 간단, 하나의 메모리 사이클에서 수행하여 경쟁 상황 해결
• 기계명령어 2개(원자적연산 명령어 TestAndSet, TestAndSet에 지역변수 lock 설정명령어)
• 일부 시스템에서 원자 명령어의 하나로, 읽기와 쓰기 모두 제공
• 해당 주소의 값을 읽고 새 값으로 교체하면서 해당 메모리 위치의 이전 값 반환

TAS 명령어의 원자적 연산 수행

// target을 검사하고, target 값을 true로 설정
boolean TestAndSet(boolean *target){
   boolean temp = *target;    // 이전 값 기록
   *target = true;            // true로 설정
   return temp;                    // 값 반환
}

부울 변수 lock을 사용한 상호배제

do{
   while(TestAndSet(&lock))    // lock을 검사하여 true이면 대기, false이면 임계 영역 진입
      ;                                // 아무것도 하지 않음
   lock = false;                    // 다른 프로세스의 진입 허용 의미로 lock을 false로
}while(true);

TestAndSet 명령어를 사용한 상호배제

do{                                            // 프로세스 Pi의 진입 영역
   waiting[i] = true;
   key = true;
   while(waiting[i] && key)
      key = TestAndSet(&lock);
   waiting[i] = false;
       //임계 영역
       //탈출 영역
   j = (i + 1) % n;
   while((j != i) && !waiting[j])    // 대기 중인 프로세스를 찾음
      j = (j + 1) % n;                    
   if(j == i)                                // 대기 중인 프로세스가 없으면
      lock = false;                        // 다른 프로세스의 진입 허용
   else                                        // 대기 프로세스가 있으면 다음 순서로 임계 영역에 진입
      waiting[j] = false;                // Pj가 임계영역에 진입할 수 있도록
       //나머지 영역
}while(true);

TestAndSet 명령어의 장점과 단점

장점

• 사용자 수준에서 가능하다
  • 메인 메모리를 공유하는 다중 프로세서나 단일 프로세서에서 프로세스 수에 관계없이 적용할 수 있다.
  • lock 변수 수에 상관없이 구현할 수 있다.
  • 구현이 단순하고 확인이 용이하다
  • 다중 임계 영역을 지원한다.

단점

• 바쁜 대기 발생
  • 프로세서 시간 소모가 크다
  • 대기 프로세스는 비생산적, 자원이 소모되는 대기 루프에 남는다.
• 기아 상태 발생
  • 프로세스가 임계 영역을 떠날 때 프로세스 하나 이상을 대기하는 경우 가능하다.
• 교착 상태 발생
  • 플래그는 우선순위가 낮은 프로세스가 재설정할 수 있지만, 우선순위가 높은 프로세스가 선점한다
  • 우선순위가 낮은 프로세스는 lock을 가지고, 우선순위가 높은 프로세스가 이것을 얻어려고 시도할 때 높은 우선순위 프로세스는 무한정 바쁜 대기가 될 것이다.

세마포어 (Semaphore)

세마포어 정의

• S : 세마포어를 나타내며 표준 단위연산 P와 V에 의해서반 접근 되는 음이 아닌 정수값을 갖는 플래그 변수

두 가지 연산(P, V)

P 연산

• 프로세스를 대기시키는 wait 동작으로 임계 영역에 진입하기 위한 연산

  P(S) : wait(S)
  while S <= 0
  ;                // 바쁜 대기, S > 0 이 될때까지 대기
  S--;
  }

V 연산

• 대기 중인 프로세스를 깨우는 신호를 보내는 signal 동작으로 임계 영역에서 나오기 위한 연산.

  V(S) : signal(S){
  S++;            // 다른 프로세스의 접근 허용
  }

세마포어 사용

세마포어는 프로세스 n개의 임계 영역 문제를 다루는 데 사용.

• 세마포어 S에 적용된 두 연산 P, V는 동시에 두 가지 동작이 실행되는 것을 예방하는 상호 배제를 의미함.

• n개의 프로세스는 1로 초기화된 공통 세마포어인 mutex(Mutual Exclusion)를 공유.

  do{
     wait(mutex);
         //임계영역
     signal(mutex);
         //나머지 영역
  }while(true);

세마포어는 여러 가지 동기화 문제를 다루는 데 사용.

예 : 수행 중인 두 개의 프로세스, 문장 S1을 가진 P1과 문장 S2를 가진 P2의 경우

• 조건 : S2는 S1이 끝난 후에만 수행되도록 구현함.

  프로세스P1

  S1;
  signal(synch);
  

  프로세스 P2

  wait(synch);
  S2;
  

세마포어의 종류

이진 세마포어

• 세마포어 S를 상호배제에 사용, 1 또는 0으로 초기화, P와 V의 연산 교대 실행

계수 세마포어

• 유한한 자원에 접근 제어 가능, 여러 번 획득, 해제할 수 있도록 count 자원의 사용 허가 값으로 사용

• 사용 가능한 자원 수로 초기화하므로, count를 초기의 세마포 수로 초기화

  • 각 프로세스가 자원 사용하려면 P 연산 수행

    • S(count) 감소 (S--)

  • 프로세스가 자원 해제할 때 V 연산 수행

    • S(count) 증가 (S++)

세마포어의 구현

• 세마포어는 제어된 변수로, P와 V의 초기 작업 때만 값이 변할 수 있음.

• 이진 세마포어는 0, 1 값만 가짐.

• 한 프로세스가 임계 영역에 있을 때, 임계영역에 들어가기를 원하는 다른 프로세스가 진입코드를 계속 순환하여 프로세스 시간 낭비함.

  • 이를 극복하기 위해 세마포어의 wait, signal 동작을 수정
    • 프로세스가 wait 동작을 실행하고 세마포어의 값이 양수가 아닐 경우 프로세스는 대기함.
    • 다음 제어는 프로세서 스케줄러에 넘기고 프로세서는 준비 큐에서 다른 프로세스를 선택.
    • 세마포어 S에 의해 블록/대기 중인 프로세스는 다른 프로세스가 signal 동작을 실행해야 재시작 가능.
    • 프로세스는 wakeup 동작에 의해 재시작되고, 대기상태에서 준비 상태로 변경, 준비 큐에 놓임.
  • 세마포어는 block/wakeup 동기화를 구현하는 메커니즘으로도 사용됨.
    • 하나의 프로세스가 자신을 보류시켜 사건이 발생할 때까지 기다리면 다른 프로세스가 사건 발생 때보류된 프로세서를 깨움.

세마포어의 구조

struct semaphore{
   int count;
   queueType queue;
}
semaphore S;

세마포어의 wait와 signal 연산

wait 연산

wait(S){
   S -> count--;
   if(S->count < 0){
      add this process to S -> queue;    // 프로레스를 준비 큐에 추가
      block();                                    // 프로세스 중단(일시정지)
   }
}

signal 연산

signal(S){
   S->count++;
   if(S->count <= 0){
      remove a process P from S -> queue;    // 준비 큐에서 P 프로세스를 제거
      wakeup(P);                                    // 신호를 보내 프로세스를 실행
   }
}

• 프로세스 리스트는 각 프로세스 제어 블록(PCB)의 링크 필드(Link Field)의 정보를 이용해 구현 가능
  • 각 세마포어는 정수값과 PCB 리스트의 포인터를 포함.
  • 리스트에서 LIFO(Stack)을 이용하여 프로세스를 추가, 제거 가능하나 기아상태를 발생시킬 수 있음.

두 프로세스의 동기화 문제 해결 방법

단일 프로세서

• P와 V 연산을 수행하는 중에 인터럽트를 금지함

  • 인터럽트를 금지하면 다른 프로세서의 명령어 실행이 중간에 끼어들지 않음.

다중 프로세서

• 인터럽트 금지할 수 없어, 다른 프로세스의 명령어가 임의의 방법으로 끼어들 수 있음.

  • 모든 프로세서에서 인터럽트 비활성화 곤란, 이는 심각한 성능 저하로 이어질 수 있음.

• 하드웨어가 특별한 명령을 제공하지 않으면, 소프트웨어적 해결 방법을 사용해야 함.

  • wait와 signal 연산으로는 바쁜 대기를 완전히 제거 할 수 없음.

• 응용 프로그램의 진입 영역에서 임계 영역까지 바쁜 대기 제거 해야 함.

  • 결국 바쁜 대기의 시기를 이동해야 하는 것.
  • wait와 signal 연산이 임계 영역의 바쁜 대기 제한할 수 있으므로 임계 영역은 항상 비어 있고 바쁜 대기가 거의 일어나지 않는 것처럼 보임.

• 바쁜 대기는 아주 짧은 기간 동안만 일어나지만, 어떤 응용 프로그램에서는 임계 영역 이 아주 길거나 항상 점유되어 있는 상황이 발생할 수 있음.

  • 이때는 바쁜 대기가 매우 비효율적임

모니터 (Monitor)

• 세마포어의 P, V 연산이 프로그램 전체에 퍼져 있으며, 이들 연산이 미치는 영향을 전체적으로 파악하기 쉽지 않아 프로그램 작성이 어려운 단점을 극복하기 위함.
  • 세마포어와 동일한 기능을 제공하지만 세마포어보다 제어가 손쉬운 고수준의 동기화구문이다.
• 다수의 병행 프로그래밍 언어에서 구현되어 있다.
  • Concurrent-Pascal, Pascal-Plus, Module-2/3, Java 등에서 지원

모니터의 구조

• 하나 이상의 프로시저와 초기화 코드, 공유 데이터로 구성된 소프트웨어 모듈로 이루어진 객체.

모니터의 특징

1. 지역(공유) Data는 모니터의 프로시저를 통해 접근이 가능하다.
   • 즉, 외부에서 변수에 대한 직접 접근은 허용되지 않는다.
2. 프로세스는 모니터의 프로시저 중 하나를 호출함으로써 모니터로 들어간다.
3. 한 순간에 오직 하나의 프로세스만이 모니터 내에 존재할 수 있다.
   • 즉, 모니터가 이미 사용 중일 경우 다른 프로세스들은 모니터가 이용가능해질 때까지 대기한다.

모니터는 3번째 특징에 의해 상호배제기능을 제공하게 된다.

모니터의 조건 변수

• 동기화를 위해 사용된다.
• 모니터 내부에 포함되며, 모니터 내부에서만 접근이 가능함
• 다음의 두 인터페이스에 의해서만 접근이 가능하다.
  • wait 연산
    • 어떤 프로세스가 signal을 호출할 때까지 wait를 호출한 프로세스는 연기/중단된다는 의미.
  • signal 연산
    • 중단된 프로세스 중에서 한 개만 재개하며, 호출 시 해당 조건 변수와 연관된 큐에서 대기 중인 프로세스 하나를 큐에서 꺼내 모니터로 진입할 수 있도록 함.
    • 중단된 프로세스가 없으면 효과가 없으며 연산이 전혀 실행되지 않는 것과 같음.

유한 버퍼에서 모니터를 이용한 생산자/소비자 문제 해결방법

/* 생산자/소비자 프로그램 */
monitor boundedbuffer; 
char buffer [N];                    /* N개의 문자가 저장될 수 있는 버퍼 */
int nextin, nextout;                /* 버퍼 포인터 */
int count;                          /* 버퍼 내부에 추가된 문자수 */
cond notfull, notempty;             /* 동기화를 위한 조건 변수 */

void append(char x)
{
   if (count == N)                  /* 버퍼에 문자가 가득 찬 경우, 오버플로 방지 */
     cwait(notfull);
   buffer[nextin] = x;
   nextin = (nextin + 1) % N;
   count++;                         /* 버퍼에 문자 하나를 추가 */
   csignal(notempty);               /* not empty 조건 변수에서 대기하고 있는 프로세스를 꺠움 */
}
void take(char x)
{
   if (count == 0)                  /* 버퍼가 빈 경우, 언더플로 방지 */
      cwait(notempty);
   x = buffer[nextout];
   nextout = (nextout + 1) % N;
   count--;                         /* 버퍼에서 문자 하나를 삭제 */
   csignal(notfull);                /* not full 조건 변수에서 대기하고 있는 프로세스를 깨움 */
}
{                                   /* 모니터 몸체(body) */
   nextin = 0;                      /* 버퍼 변수 초기화 */
   nextout = 0;
   count = 0;
}
void producer()
{
   char x;
   while(true)
   {
      produce(x);
      append(x);
   }
{
void consumer()
{
   char x;
   while (true)
   {
     take(x);
     consume(x);
   }
}
void main()
{
   parbegin(producer, consumer);
}

Reference

『IT CookBook, 운영체제』, 구현회 집필, 한빛아카데미

『IT CookBook, 쉽게 배우는 운영체제』, 조성호 집필, 한빛아카데미

『운영체제 : 내부구조 및 설계원리 (6판)』, WILLIAM STALLINGS 저, PEARSON HALL

상호배제와 동기화

상호배제의 개념

• 병행 프로세스에서 프로세스 하나가 공유 자원 사용 시 다른 프로세스들이 동일한 일을 할 수 없도록 하는 방법

• 읽기 연산은 공유 데이터에 동시에 접근해도 문제 발생하지 않음.

동기화

• 변수나 파일은 프로세스별로 하나씩 차례로 읽거나 쓰도록 해야 하는데, 공유 자원을 동시에 사용하지 못하게 실행을 제어하는 기법
  • 동기화는 순차적으로 재사용 가능한 자원을 공유하려고 상호작용하는 프로세스 사이에서 나타남
  • 동기화로 상호배제 보장할 수 있지만, 이 과정에서 교착 상태와 기아 상태가 발생할 수 있음

병행 프로세스 간 상호작용

프로세스는 아래 세 가지 형태로 상호작용 함.

• 프로세스들이 서로 인식하지 못하는 경쟁관계 유지.
  • 다중 프로그래밍 환경에서 운영체제는 자원에 대한 경쟁을 고려, 동일한 디스크나 프린터로의 접근 조절.
  • 프로세스들은 입출력 버스를 비롯한 개체를 공유하는 단계에서 간접적으로 서로의 관계를 인식함.
    • 프로세스들은 공동 개체를 공유하는데 따른 협력이 필요함.
  • 프로세스들은 서로를 인식하고 프로세스끼리 통신할 수 있는 기본 함수를 가짐.
    • 프로세스들이 협력관계일 때, 프로세스 간 직접 통신이 가능, 병행해서 함께 동작할 수 있음.

상호배제의 조건

1. 두 프로세스는 동시에 공유 자원에 진입 불가
2. 프포세스의 속도나 프로세서 수에 영향을 받지 않음
3. 공유 자원을 사용하는 프로세스만 다른 프로세스 차단 가능
4. 프로세스가 공유 자원을 사용하려고 너무 오래 기다려서는 안 됨

생산자/소비자 프로세스

• 생산자/소비자, 판독자/기록자(입력기/출력기) 문제
  • 여러 프로세스가 공통 작업 수행을 위해 서로 협동하고, 병행 처리되는 대표적인 예.
  • 상호배제와 동기화가 필요하며 세마포어를 이용해 구현.
  • 운영체제에서 비동기적으로 수행하는 모델로 생산자 프로세스는 소비자 프로세스가 소비하는 정보를 생산.

생산자와 소비자의 공유 버퍼

• 생산자와 소비자 프로세서들을 병행 실행하기 위해 공유 버퍼가 필요함
  • 생산자의 데이터 생산 속도와 소비자의 데이터 소비 속도는 서로 독립적이므로 버퍼가 필요함
    • 생산자와 소비자는 같은 버퍼에 접근하므로 동시에 사용할 수 없음.
• 생산자는 버퍼가 꽉 차면 더 이상 생산 불가, 소비자는 버퍼가 비면 데이터 소비 불가 >> 문제 발생
• 생산자와 소비자의 공유 버퍼의 상태
  

  

무한 버퍼 생산자/소비자 문제

• 버퍼의 크기에 제한을 두지 않으며 항상 버퍼에 빈자리가 존재함

유한 버퍼 생산자/소비자 문제

• 크기가 고정된 버퍼를 사용
  • 버퍼가 비었을 시 소비자가 대기
  • 버퍼가 가득 차면 생산자가 대기
• 공유 버퍼의 저장소를 두개의 논리적 포인터 in과 out을 사용한 순한 배열을 사용하여 해결 가능
  • in과 out은 0으로 초기화.
  • 변수 in은 비어있는 다음 버퍼를 가리킴.
  • 변수 out은 채워진 버퍼의 맨 처음을 가리킴.
  • 소비자는 버퍼에서 데이터를 읽기 전 생산자가 앞서 가는 지, 즉 in > out 인지 확인함.

유한 버퍼를 공유하는 생산자/소비자 프로세스 간 변형 프로그램

1. 공유 데이터의 선언

   #define BUFFER_SIZE 10 //버퍼 크기
   typedef struct{
      DATA data;
   } item;
   item buffer[BUFFER_SIZE];
   int in = 0;
   int out = 0;
   int counter = 0;

2. 생산자와 소비자 프로세스

   생산자 프로세스는 생산하는 새로운 원소를 지역변수 nextProduced에 저장, 소비자 프로세스는 소비하는 원소를 지역변수 nextConsumed에 저장 각 프로세스 구현

   생산자 프로세스

   item nextProduced;
   
   while(true){
       //버퍼가 가득 차 아무 일도 하지 않음
       while(counter == BUFFER_SIZE);
       buffer[in] = nextProduced;
       in = (in + 1) % BUFFER_SIZE;
       counter++;
   }
   

   소비자 프로세스

   item nextConsumed;
   
   while(true){
       //버퍼가 가득 차 아무 일도 하지 않음
       while(counter == 0);
       nextConsumed = buffer[out];
       out = (out + 1) % BUFFER_SIZE;
       counter--;
   }
   

3. counter++와 counter-- 기계어

   두 코드의 동시 수행시 counter 값이 맞는기 기계어로 작성 확인

   count++ 기계어

   rigister1 = counter;
   register1 = register1 + 1;
   counter = register1;
   

   count-- 기계어

   rigister2 = counter;
   register2 = register1 - 1;
   counter = register2;
   

   실행 예

   T1 : 생산자가 register1 := counter를 수행 (register1 = 5)
   T2 : 생산자가 register1 := counter1 + 1을 수행 (register2 = 6)
   T3 : 소비자가 register2 := counter를 수행 (register2 = 5)
   T4 : 소비자가 register2 := register2 – 1을 수행 (register2 = 4)
   T5 : 생산자가 counter := register1을 수행 (counter = 6)
   T6 : 소비자가 counter := register2를 수행 (counter = 4)

경쟁 상태(Race Condition)

• 공유 데이터에 최종적으로 남는 데이터의 결과를 보장할 수 없는 상황을 의미
• 여러 프로세스가 공유 데이터를 동시에(병행적으로) 접근(읽기나 쓰기)할 때 공유 데이터에 대한 접근 순서에 따라 실행 결과가 달라지는 상황
• 장치나 시스템이 둘 이상의 연산을 동시에 수행하려 할 때, 어느 프로세서가 제일 마지막에 수행된 후 결과를 저장했느냐에 따라 발생하는 오류 발생하므로 적절한 순서에 따라 수행 해야 함
  • 접근 순서화가 필요
  • 병행 프로세서들은 반드시 동기화되어 실행되어야 함.

경쟁 상태의 예방(동기화 실행 방법)

임계 구역

• 공유 변수를 어느 한 순간에 한 프로세스만 조작할 수 있도록 함.

상호 배제

• 위의 예에서 counter를 조작하는 부분을 임계구역으로 설정, 상호 배제 함.

임계 영역(Critical Section)

둘 이상의 프로세스가 공유할 수 없는 자원을 임계자원이라 하며, 프로그램에서 이를 이용하는 부분.

• 공유 메모리가 참조되는 프로그램의 부분(데이터나 데이터 구조)으로 다수의 프로세스가 접근 가능한 영역이면서 한 순간에 하나의 프로세스만 사용할 수 있는 영역(공유 자원의 독점을 보장하는 코드 영역)을 의미.
• 프로세스들이 공유 데이터를 통해 협력 시, 한 프로세스가 임계영역에 들어가면 다른 모든 프로세스는 임계영역으로의 진입 금지.
• 다중 처리 시스템과 단일 처리 시스템(시분할)환경에 적용되는 하나의 실행단위, 실행 구간을 의미.
  • 임계영역 내에서 빠른 속도로 작업을 수행, 한 프로세스가 오랫동안 머무르면 안됨.
  • 프로세스가 무한 루프 등에 빠지지 않도록 관리.

진입 상호 배제

• 프로세스 하나가 임계 영역에 있으면 다른 프로세스가 임계 영역에 들어가지 못하게 하는 것.

• 임계 영역에 들어가기를 원하는 프로세스는 진입 상호배제를 수행해야 함.

  • 프로세스가 접근하지 않은 임계 영역은 잠금 상태.
  • 프로세스는 임계 영역에서 작업을 수행하기 전에 키를 얻어 임계 영역의 잠금 상태를 해제해야 함.
  • 프로세스가 키를 반환할 때까지 다른 모든 프로세스에 대해 잠김 상태 유지.

• 임계 영역을 떠나는 프로세스는 출구 상호배제를 수행함으로써 다른 프로세스가 임계 영역에 들어갈 수 있도록 함.

Reference

『IT CookBook, 운영체제』, 구현회 집필, 한빛아카데미

『IT CookBook, 쉽게 배우는 운영체제』, 조성호 집필, 한빛아카데미

『운영체제 : 내부구조 및 설계원리 (6판)』, WILLIAM STALLINGS 저, PEARSON HALL

병행 프로세스

병행 프로세스 개념

• 프로세스 여러 개가 동시에 실행되는 것.

  • 독립적으로 작업을 수행, 다른 프로세스와 협력하며 특정 기능 수행.
  • 프로세스 간 교신이 필요.

• 비동기적 병행 프로세스

  • 프로세스 간 교신 시 동기화되어야 하는 프로세스.

• 상호 작용

  • 제한된 자원을 공유하기 위함이며, 상호 작용하는 프로세스는 순서에 맞게 실행되도록 동기화되어야 함.

병행 프로세스의 과제

병행성

다수의 프로세서를 이용하여 작업을 수행하며, 다중 프로세싱 시스템, 분산 처리 환경, 다중 프로그래밍 운영체제에서 매우 중요함.
시스템의 신뢰도 향상과 처리 속도 개선을 통한 처리 능력 증대에 매우 중요함.

• 다중 프로세싱 시스템
  • 각 프로세서가 갖는 오버헤드를 감소시키면서 프로세서의 유효성을 증대시킴.
  • 여러 개의 명령어를 세분화하여 동시에 처리하기 위해 프로세서들을 연결, 상호작용을 제어.

다중 프로세싱 시스템의 성공적인 구현을 위한 해결 문제

• 공유 자원을 상호 배타적으로 사용해야 함.
  • 프린터, 통신망 등은 한 순간에 한 프로세스만 사용해야 함.
• 병행 프로세서들 사이는 협력 또는 동기화되어야 함.
  • 상호 배제도 동기화의 형태임.
• 두 프로세스 사이에 데이터 교환을 위한 통신이 이루어져야 함.
• 프로세서는 결정성(Determinacy)을 확보해야 함.
  • 동시에 수행되는 다른 프로세스들의 실행 속도와 관계 없이 항상 일정한 실행 결과 보장.
  • 교착 상태를 해결하고 병행 프로세스들의 병렬 처리 능력 극대화.
  • 실행 검증 문제 해결
  • 병행 프로세스 수행 과정에서 발생하는 상호 배제를 보장해야 함.
    • 어떤 프로세스가 작업을 실행 중일 때 나머지 프로세스들이 그 작업에 관련된 작업을 수행할 수 없음.

다중 프로세싱 시스템은 프로세스 동기화 알고리즘이 필요.

• 프로세서들이 모든 입출력 장치와 메모리를 참조 가능.
• 동시에 동일한 자원에 접근할 경우 충돌이 발생하므로 이를 해결.

선형 그래프

프로세스는 프로세스 집합과 이들의 선행 제약(Precedence Constraint)의 두 가지 요소로 정의

선형 제약

• 프로세스를 순서대로 다른 상태로 옮기는 것
  • 두 프로세스에 선행 제약이 없으면 이 둘은 독립적이므로 병행 실행 가능

선형 그래프

• 선행 제약의 논리적 표현
• 각 문장에 대응되는 노드가 비순환 그래프를 이룸
• 선행 그래프에서 노드는 소프트웨어 작업이거나 동시에 실행할 수 있는 프로그램 명령

예

간단한 산술 연산을 수행하는 알고리즘

• 병행 수행을 하기 위해 프로세서 안의 기능 단위(가산기 등)를 여러 개 두거나 프로세서를 여러 개 사용해야 함
• 프로세서를 여러 개 사용 시 여러 문장이 동시에 수행되어 총 수행시간을 줄일 수 있음

a := x + y; → S1
b := z + 1; → S2
c := a - b; → S3
w := c + 1; → S4

• S1과 S2연산은 동시에 수행이 가능 한 연산
• S3연산은 a와 b가 값을 할당 받기 전에 수행하면 안된다.
• S4연산은 c 값을 계산하기 전에 수행할 수 없다.

병행 프로세스를 표현하는 방법

프로그램의 여러 문장의 선행 관계 명시를 위해 두 가지 언어구조 제시

fork와 join 구조

• 선행 그래프는 연산 부분의 선행 제약을 정의하는데 유용하나, 2차원이므로 프로그래밍 언어에서 사용하기에 어려움.

• 병행을 최초로 언어적 표현으로 명시.

fork L 명령

• 프로그램에서 두 개의 병행 수행을 만듦
• 단일 연산을 두 개의 독립적인 연산으로 분할
• 다음 문장으로 이어지는 흐름과 라벨L 위치에서 시작하는 흐름으로 나뉨.

join n 명령

• 여러 개의 병행 연산을 하나로 결합하는 방법을 제공
  • 단위적으로 수행해야 함
• 합칠 연산의 수를 명시하는 매개변수를 가짐

    count := 2;
    fork L1;
    a := x + y;
    go to L2;
L1 : b := z + 1;
L2 : join count;
    c := a – b;
    w := c + 1;

병행 문장

• 하나의 프로세스가 여러 병렬 프로세스로 퍼졌다가 다시 하나로 뭉쳐지는 것을 나타내는 구조

다익스트라가 제안한 ‘parbegin/parend’

• 일반적인 형태

  parbegin S1; S2; ......; Sn; parend;

  • 각 Si는 단일 문장(명령어), parbegin과 parend 사이의 모든 문장은 병행 수행 가능.

• 보다 효과적인 병행 문장은 S0과 Sn+1 문장을 추가하여 아래와 같이 정의 가능.

  S0; parbegin S1; S2; ......; Sn; parend; Sn+1;

  • Sn+1 은 모든 S(i=1, 2,…, n)가 끝난 후에만 실행 가능.

• 위의 간단한 산술연산의 예를 parbegin/parend로 표현하면 아래와 같다.

  parbegin
      a := x + y;
      b := z + 1;
  parend;
      c := a – b;
      w := c + 1;

Reference

『IT CookBook, 운영체제(개정3판)』, 구현회 집필, 한빛아카데미

『IT CookBook, 쉽게 배우는 운영체제』, 조성호 집필, 한빛아카데미

『운영체제 : 내부구조 및 설계원리 (6판)』, WILLIAM STALLINGS 저, PEARSON HALL

스레드(Thread)

스레드의 개념

프로세스의 작업 과정

1. 프로세스의 생성: OS는 코드와 데이터를 메모리에 가져오고, PCB를 생성하고 작업에 필요한 메모리를 확보
2. CPU 스케줄러가 프로세스가 해야하는 일을 CPU에 전달하고 실제 작업을 수행한다.
   • 이때, CPU에 전달 하는 일 하나를 스레드라고 한다.

• 프로세스의 특성인 자원과 제어에서 제어만 분리한 실행 단위
• 프로세스 하나는 스레드 한 개 이상으로 나눌 수 있음
• 프로세스의 직접 실행 정보를 제외한 나머지 프로세스 관리 정보 공유
• 다른 프로시저 호출, 다른 실행 기록(별도 스택 필요)
• 관련 자원과 함께 메모리 공유 가능하므로 손상된 데이터나 스레드의 이상 동작 고려
• 같은 프로세스의 스레드들은 동일한 주소 공간 공유

스레드의 정의

• 프로세스의 코드에 정의된 절차에 따라 CPU에 작업 요청을 하는 실행 단위
• CPU 스케줄러가 CPU에 전달하는 일 하나
• CPU가 처리하는 작업의 단위는 프로세스로부터 전달받은 스레드
  • OS입장에서의 작업단위는 프로세스
  • CPU입장에서의 작업단위는 스레드

프로세스와 스레드의 차이

프로세스

• 실행중인 프로그램이 디스크로부터 메모리에 적재되어 CPU의 할당을 받은 것을 말함

스레드

• 스레드는 프로세스의 실행 단위라고 할 수 있습니다.

• 한 프로세스 내에서 동작되는 여러 실행 흐름으로프로세스 내의 주소 공안이나 자원을 공유할 수 있습니다.

• 스레드는 스레드 ID, 프로그램 카운터, 레지스터 집합, 그리고 스택으로 구성됩니다.

• 같은 프로세스에 속한 다른 스레드와 코드, 데이터 섹션, 그리고 열린 파일이나 신호와 같은 운영체제 자원들을 공유합니다.

스레드 병렬 수행

• 프로세스 하나에 포함된 스레드들은 공동의 목적 달성을 위해 병렬 수행
• 프로세스가 하나인 서로 다른 프로세서에서 프로그램의 다른 부분 동시 실행

스레드 병렬 수행의 이점

스레드별로 실행 환경 정보가 따로 있지만 서로 많이 공유하므로, 프로세스보다 동일한 프로세스의 스레드에 프로세서를 할당하거나 스레드 간의 문맥 교환이 훨씬 경제적

• 사용자 응답성 증가
• 프로세스의 자원과 메모리 공유 가능
• 경제성 좋음
• 다중 처리(멀티 프로세싱)로 성능과 효율 향상

스레드 관련 용어

멀티 스레드

• 하나의 프로세스를 다수의 실행 단위로 구분하여 자원을 공유하고 자원의 생성과 관리의 중복성을 최소화하여 수행 능력을 향상시키는 것

• 프로세스 내 작업을 여러 개의 스레드로 분할함으로써 작업의 부담을 줄이는 프로세스 운영 기법

• 운영체제가 소프트웨어적으로 프로세스를 작은 단위의 스레드로 분할하여 운영하는 기법

멀티 태스킹

• 운영체제가 CPU에 작업을 줄 때 시간을 잘게 나누어 배정하는 기법

멀티 프로세싱

• 운영체제가 CPU에 작업을 줄 때 시간을 잘게 나누어 배분하는 기법

• CPU를 여러 개 사용하여 여러 개의 스레드를 동시에 처리하는 작업 환경으로 이는 병렬 처리에서 슈퍼 스칼라 기법과 같다.

• 멀티 프로세싱은 하나의 컴퓨터에 여러 개의 CPU 혹은 하나의 CPU 내 여러 개의 코어(core)에 스레드를 배정하여 동시에 작동시키는 것

• 네트워크로 연결된 서로 다른 컴퓨터에 여러 개의 스레드가 나누어져 협업하는 분산 시스템도 멀티 프로세싱이라 부른다.

CPU 멀티 스레드

• 한 번에 하나씩 처리해야 하는 스레드를 파이프라인 기법을 이용해 동시에 여러 스레드를 처리할 수 있도록 만든 병렬 처리 기법
• 하드웨어적인 방법으로 하나의 CPU에서 여러 스레드를 동시에 처리하는 병렬 처리 기법

스레드 제어 블록TCB, Thread Control Block

• 정보 저장
• 프로세스 제어 블록은 스레드 제어 블록의 리스트
• 스레드 간에 보호 하지 않음

TCB의 내용

• 실행 상태
  • 프로세서 레지스터, 프로그램 카운터, 스택 포인터
• 스케줄링 정보
  • 상태(실행, 준비, 대기), 우선순위, 프로세서 시간
• 계정 정보
  • 스케줄링 큐용 다양한 포인터
  • 프로세스 제어 블록PCB을 포함하는 포인터

멀티스레드 구조

스레드는 멀티태스킹의 낭비 요소를 제거하기 위해 사용된다. 비슷한 일을 하는 2개의 프로세스를 만드는 대신, 코드, 데이터 등을 공유하면서 여러 개의 일을 하나의 프로세스 내에서 하는 것이다.

프로세서는 크게 정적인 영역과 동적인 영역으로 구분된다.

정적인 영역은 코드 전역 데이터 파일등 프로세스가 실행되는 동안 바뀌지 않는 영역

동적인 영역은 스레드가 작업을 하면서 값이 바뀌거나 새로 만들어지거나 사라지는 영역

• 레지스터 값, 스택, 힙 등이 있다

장점

• 응답성 향상
• 자원 공유
• 효율성 향상
• 다중 CPU 지원

단점

• 모든 스레드가 자원을 공유하기 때문에 하나의 스레드에 문제가 생기면 전체 프로세스에 영향을 미침

멀티스레드 모델

커널 스레드: 커널이 직접 생성하고 관리하는 스레드

사용자 스레드: 라이브러리에 의해 구현된 일반적인 스레드

사용자 레벨 스레드(N to 1 모델)

• 사용자 프로세스 내에 여러 개의 스레드가 커널의 스레드 하나와 연결
• 스레드 라이브러리를 이용하여 작동
  • 라이브러리가 직접 스케줄링을 하고 작업에 필요한 정보를 처리하기 때문에 문맥 교환이 필요 없음
• 커널 스레드가 입출력 작업을 위해 대기 상태에 들어가면 모든 사용자 스레드가 같이 대기하게 됨
• 한 프로세스의 타임 슬라이스를 여러 스레드가 공유하기 때문에 여러 개의 CPU를 동시에 사용할 수 없음

장점

• 이식성 높음
  • 커널에 독립적 스케줄링을 할 수 있어 모든 운영체제에 적용
• 오버헤드 적음
  • 스케줄링, 동기화 위해 커널 호출 않으므로 커널 영역 전환 오버헤드 감소
• 유연한 스케줄링 가능
  • 커널이 아닌 스레드 라이브러리에서 스레드 스케줄링 제어하므로 응용 프로그램에 맞게 스케줄링 가능

단점

• 시스템의 동시성 지원하지 않음
  • 스레드가 아닌 프로세스 단위로 프로세서 할당하여 다중 처리 환경을 갖춰도 스레드 단위로 다중 처리 불가능 동일한 프로세스의 스레드 한 개 가 대기 상태가 되면 이 중 어떤 스레드도 실행 불가
• 확장 제약이 따름
  • 커널이 한 프로세스에 속한 여러 스레드에 프로세서를 동시에 할당 할 수 없어 다중 처리 시스템에서 규모 확장 곤란
• 스레드 간 보호 불가능
  • 스레드 간 보호에 커널의 보호 방법 사용 불가
  • 스레드 라이브러리에서 스레드 간 보호를 제공해야 프로세스 수준에서 보호 가능

커널 레벨 스레드(1 to 1 모델)

• 하나의 사용자 스레드가 하나의 커널 스레드와 연결
• 독립적으로 스케줄링이 되므로 특정 스레드가 대기 상태에 들어가도 다른 스레드는 작업을 계속할 수 있음
• 커널 레벨에서 모든 작업을 지원하기 때문에 멀티 CPU를 사용할 수 있음
• 하나의 스레드가 대기 상태에 있어도 다른 스레드는 작업을 계속 할 수 있음

멀티 레벨 스레드(M to N 모델)

• 사용자 레벨 스레드와 커널 레벨 스레드를 혼합한 방식
• 커널 스레드가 대기 상태에 들어가면 다른 커널 스레드가 대신 작업을 하여 사용자 레벨 스레드보다 유연하게 작업을 처리할 수 있음
• 커널 레벨 스레드를 같이 사용하기 때문에 여전히 문맥 교환 시 오버헤드가 있어 사용자 레벨 스레드만큼 빠르지 않음
• 빠르게 움직여야 하는 스레드는 사용자 레벨 스레드로 작동하고, 안정적으로 움직여야 하는 스레드는 커널 레벨 스레드로 작동

Reference

『IT CookBook, 운영체제(개정3판)』, 구현회 집필, 한빛아카데미

『IT CookBook, 쉽게 배우는 운영체제』, 조성호 집필, 한빛아카데미

『운영체제 : 내부구조 및 설계원리 (6판)』, WILLIAM STALLINGS 저, PEARSON HALL