CS : 운영체제(3)

6. 교착 상태

위와 같이 두 개 이상의 프로세스가 서로 대기 중인 상황에서는 어떤 프로세스도 자원을 이용할 수 없게된다.

어떤 프로세스가 어떤 자원을 할당 받았는지 혹은 기다리고 있는지 아래와 같은 자원 할당 그래프로 파악할 수 있다. 

• 프로세스는 원, 자원은 사각형
• 사용할 수 있는 자원의 개수는 자원 사격형 내 점으로 표현
• 할당받았으면 자원에서 프로세스 쪽으로 화살표로 표시
• 기다리고 있으면 프로세스에서 자원으로 화살표

교착 상태가 발생할 조건

1. 상호 배제
   한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
2. 점유와 대기
   자원을 할당받은 상태에서 다른 자원을 할당 받기를 기다리는 상태
3. 비선점
   어떤 프로세스도 다른 프로세의 자원을 강제로 빼앗지 못하는 상태
   CPU 스케줄링할 때 비선점, 선점했을 때랑 같은 느낌의 비선점
4. 원형 대기
   프로세스들이 원의 형태로 자원을 대기하는 상태

하나라도 만족하지 않으면 교착 상태는 발생하지 않는다.

교착 상태 예방

애초에 교착 상태가 발생하지 않도록 네 가지 교착 상태 중에 하나를 없애버리는 방식

• 상호 배제를 없애는 건 현실적으로는 가능한 일이 아니다 (모든 자원을 공유 가능하게)
• 점유와 대기를 없애기 위해 특정 프로세스에 자원을 모두 할당하거나 아예 할당하지 않는 방식으로 배분 (자원을 할당받은 상태에서 대기) (철학자 문제에서 오른쪽 포크 기다릴거면 왼쪽 포크 내려놓으라고 하는 것) -> 자원의 활용률을 낮출 수 있는 방식
• 비선점 조건을 없애기 위해 한 프로세스가 다른 프로세스 자원을 뺏을 수 있도록 함 -> 선점이 가능한 자원(CPU-선점형 스케줄링, 타임아웃 인터럽트로)에 한해 효과적이다 -> 모든 자원이 선점 가능한 것은 아니기 때문이다 (프린트)
• 원형 대기 조건을 없애기 위해 (원의 형태로 서로를 기다림) 모든 자원에 번호를 붙이고 오름차순으로 할당하면 원형 대기는 발생하지 않음 -> 모든 자원에 번호 붙이는 것은 어려운 작업 -> 어떤 자원에 어떤 번호를 붙이느냐에 따라 활용률이 달라진다

교착 상태가 발생하지 않음을 보장할 수 있으나 부작용이 따르는 방식이다.

교착 상태 회피

교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주한다. 교착 상태가 발생하지 않을 만큼 조심 조심 할당을 해야한다.

• 안전 순서열 : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
  A, B, C가 동시에 실행 중일 때 자원을 C, B, A 순서로 할당하니까 안전하게 할당되는 안전 순서열로 제공
• 안전 상태 : 교착 상태 없이 모든 프로세스가 자원을 할당 받고 종료될 수 있는 상태
  안전 순서열이 있는 상태
• 불안전 상태 : 교착 상태가 발생할 수도 있는 상태
  안전 순서열이 없는 상태

컴퓨터 시스템에 총 12개의 자원이 있고 프로세스 P1, P2, P3가 각각 5개, 2개, 2개 자원을 할당받아 실행 중이라고 하자. 그럼 운영체제가 배분할 수 있는 자원의 수는 3개가 된다. 그리고 프로세스 P1, P2, P3는 각각 최대 10개, 4개, 9개를 요구할 수 있다. 

이러한 상황은 안전 순서열이 존재한다. P1, P2, P3가 각각 5개, 2개, 7개로 최대를 요구한 상황이라면 P2한테 2개를 제공받고 종료되어 반환이 되면 1+4=5개 남는다. 남은 5개 중를 P1한테 할당하고 종료가 되면 10개가 남게 된다. 그럼 P3한테 7개를 제공하면 안전하게 모든 프로세스가 실행가능하다

P2 -> P1 -> P3가 안전 순서열이 된다.

이는 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하는 방식이다. 

교착 상태 검출 후 회복

• 선점을 통한 회복
  교착 상태가 해결될 떄까지 한 프로세스씩 자원을 몰아주는 방식
• 프로세스 강제 종료를 통한 회복
  교착상태에 놓인 프로세스 모두 강제 종료 (-> 작업 내역 잃을 위험)
  교착 상태가 해결될 때까지 한 프로세스씩 강제 종료 (-> 계속 해결됐나 확인해야해서 오버헤드)

교착 상태 무시

그냥 문제가 발생해도 무시한다. 문제 발생의 빈도수가 낮으면 문제 발생 시 무시한다

 

 

7. 연속 메모리 할당

프로세스에 연속적인 메모리 공간을 할당하는 것을 연속 메모리 할당이라고 한다.

 

현재 사용되지 않는 프로세스들을 보조기억장치의 일부 영역(스왑 영역)으로 쫓아내고 그렇게 생긴 빈 공간에 새 프로세스를 적재한다. 당장 사용되지 않는 프로세스를 보조기억장치를 쫓아내고 지금 당장 필요한 프로세스를 메모리를 적재한다면 메모리 관리가 효율적이다. 

스왑 영역에 있던 프로세스가 다시 메모리가 적재되는 것을 스왑인, 메모리에서 스왑 영역으로 쫓아내는 것을 스왑 아웃이라고 한다.

프로세스들이 요구하는 메모리 공간 크기가 실제 메모리의 크기보다 큰 경우에 도움이 된다. A, B, C, D의 크기의 합이 물리 메모리보다 크다면 프로세스 D가 당장 실행되어야 하고 프로세스 B가 당장 사용되지 않으면 둘디 바꿀 수 있다.

 

 

 메모리 할당

프로세스는 메모리의 빈 공간에 할당되어야 하는데 빈공간이 여러 개 있다면 어디에 적재를 시켜야할까?

• 최초 적합 (first-fit)
  운영체제가 메모리 내의 빈 공간을 순서대로 검색하다 적재할 수 있는 공간 발견하면 그 공간에 프로세스를 배치하는 방식
  빈공간 검색을 최소화하고 빠르게 할당을 할 수 있다
  빈 공간 A에 적재를 하게 된다
• 최적 적합 (best-fit)
  운영체제가 빈 공간을 모두 검색해본 뒤, 적재 가능한 가장 작은 공간에 할당을 한다
  빈 공간 C에 적재를 하게 된다
• 최악 적합 (worst-fit)
  운영체제가 빈 공간을 모두 검색해본 뒤, 적재 가능한 가장 큰 공간에 할당한다
  빈 공간 B에 적재를 하게 된다

이 세가지 모두 연속 메모리 할당 방식이다. (프로세스를 메모리에 연속적으로 할당하는 방식) 하지만 프로세스를 연속적으로 메모리에 할당하는 방식 은 메모리를 효율적으로 사용하는 방법이 아니다.

 

외부 단편화

메모리에 50MB가 남아있지만 50MB짜리 프로세스를 할당할 수는 없다. 이를 외부 단편화라고 한다. 프로세스가 실행되고 종료되길 반복하면서 메모리 사이사이에 빈 공간이 발생하는 것을 뜻한다. 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상이다. 

 

외부 단편화 해결 - 1 : 메모리 압축

여기저기 흩어져 있는 빈 공간들을 하나로 모으는 방식이다. 프로세스를 적당히 재배치시켜 흩어져 있는 작은 빈공간들을 하나의 큰 빈 공간으로 만드는 방법이다.

이러한 재배치 과정에서 많은 오버헤드를 야기하고 프로세스는 자기 할 일을 제대로 하진 못한다. 

외부 단편화 해결 - 2 : 페이징

외부 단편화를 최소화하기 위한 가장 대표적인 메모리 관리 기법이다. 뒤에서 자세히 설명할 예정이다!

 

연속 메모리 할당에는 외부 단편화 문제와 물리 메모리보다 큰 프로세스를 실행할 수 없다는 문제점이 존재한다. 이를 페이징을 통해서 해결할 수 있다.

 

가상 메모리란 실행하고자 하는 프로그램의 일부만 메모리에 적재해서 실제 물리 메모리보다 큰 프로세스를 실행할 수 있게 하는 기법이다. 

 

 

8. 페이징

가상 메모리란 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술로 가상 메모리 관리 기법에는  페이징, 세그멘테이션이 있다.

앞에서 외부 단편화를 배웠는데, 메모리에 적재되는 대상이 전부 일정한 크기를 가지고 있다면 외부 단편화가 발생하지 않는다. (스왑 아웃되어도 적재되는 크기랑 같으니까 외부 단편화 X)

이에 페이징은 프로세스를 일정 크기로 자르고, 이를 메모리에 불연속적으로 할당하는 방식이다. 

프로세스의 논리 주소 공간을 페이지(page)라는 일정 단위로 자르고, 메모리의 물리 주소 공간을 프레임(frame)이라는 페이지와 동일한 일정한 단위로 자른 뒤 페이지를 프레임에 할당하는 가상 메모리 관리 기법이다.

 

프로세스 단위인 스왑 인, 스왑 아웃이 아닌 페이지 단위의 스왑 인(페이지 인), 스왑 아웃(페이지 아웃)이 일어난다. 메모리에 적재될 필요가 없는 페이지들은 보조 기억 장치로 스왑 아웃되고 실행에 필요한 페이지들은 메모리로 스왑 인 된다.

어떤 프로세스를 실행하기 위해서는 모든 페이지가 메모리에 저장되어 있을 필요는 없다. 프로세스 A 실행 중이면 프로세스 A를 이루는 모든 페이지가 메모리에 적재될 필요는 없다. 즉 물리 메모리보다 큰 프로세스도 실행될 수 있다.

 

프로세스를 일정 크기로 자르고 불연속적으로 할당되어 있다면 CPU 입장에서는 어떤 프로세스가 어디에 어떻게 있는지 알기 어려워진다. 프로세스를 이루는 페이지가 어느 프레임에 적재되어있는지 CPU가 일일이 알기가 어렵고 프로셋가 메모리에 불연속적으로 배치되어 있다면 CPU 입장에서 이를 순차적으로 실행할 수 없다. CPU 입장에서 다음에 실행할 명령어 위치를 찾기가 어려워 진다.

 

=> 이러한 문제를 해결 하기 위한 페이지 테이블이 존재한다

 

 

페이지 테이블

실제 메모리 내의 주소인 물리 주소에 불연속적으로 배치되더라도 CPU가 바라보는 주소인 논리 주소에는 연속적으로 배치되도록 하는 방법이다. 페이지 번호와 프레임 번호를 짝지어주는 일종의 이정표이다.

 

물리적으로는 분산되어 저장되어 있더라도 CPU 입장에서 바라본 논리 주소는 연속적으로 보이게 된다. 

 

 

내부 단편화

하지만 페이징은 외부 단편화를 해결할 수 있지만 내부 단편화를 일으킬 수가 있다. 어떤 프로세스 크기가 페이지 크기의 배수가 되지 않을 수도 있다. 예를 들어 페이지 크기가 10KB이고 프로세스 크키가 108KB라면 2KB만큼의 내부 단편화가 발생하게 된다. 

 

 

PTBR

프로세스마다 페이지 테이블이 있고, 각 페이지 테이블은 CPU 내의 프로세스 테이블 베이스 레지스터 (PTBR)가 가리킨다.

메모리에 페이지 테이블에 다 저장되어 있게 된다면 메모리 접근 시간이 두 배로 늘어난다. 페이지 테이블을 참조하기 위해 한 번, 페이지 참조하기 위한 한 번 접근해야 한다. 메모리에 접근하는 건 캐시 메모리, 레지스터에 접근하는 것보다 늦게 된다.

 

이를 해결하기 위해 TLB라는 캐시 메모리를 이용하게 된다.

 

TLB

TLB는 CPU 곁에 페이지 테이블의 캐시메모리다. 페이지 테이블의 일부를 가져와 저장하게 된다. 불필요한 메모리 접근을 줄일 수 있다.

CPU가 접근하려는 논리 주소가 TLB에 있다면 TLB 히트로 불필요한 메모리 접근이 필요가 없다. CPU가 접근하려는 논리 주소가 TLB에 없다면 TLB 미스로 메모리 접근이 두번 이루어진다.

 

 

페이징에서의 주소 변환

어떤 페이지, 어떤 프레임에 접근하고 싶은지, 접근하려는 주소가 그 페이지에서 얼마나 떨어져 있는지를 알아야 한다.

 

페이징 시스템에서의 논리 주소는 페이지 번호(page number)와 변위(offset)으로 이루어져 있다. (접근하고자 하는 페이지 번호와 얼마나 떨어져 있는지의 정보)

페이지 번호, 변위로 이루어진 논리 주소는 페이지 테이블을 통해 프레임 번호, 변위로 변환이 된다. 변위는 같다. (페이지 크기 = 프레임 크기)

CPU가 <5, 2>에 접근하고 싶다면 5번 페이지는 1번 프레임에 할당되어 있고 10번지에 접근을 하게 된다.

 

 

페이지 테이블 엔트리

페이지 테이블의 각각 행을 페이지 테이블의 엔트리라고 한다. 앞서 말한 페이지 번호, 프에임 번호도 페이지 테이블의 엔트리이다. 페이지 테이블에서는 페이지 번호, 프레임 번호 말고도 다양한 정보가 담기게 된다.

 

• 유효 비트 : 현재 해당 페이지에 접근 가능한지 여부 (스왑영역으로 쫓겨났는지 아닌지)
  유효 비트가 0인 페이지에 접근하려고 하면 페이지 폴트(page fault)라는 인터럽트가 발생한다.
  CPU가 기존 작업 백업하고, 페이지 폴트 처리 루틴을 실행하게 된다. 여기서 페잊이 처리 루틴은 원하는 페이지를 메모리로 가져온 뒤 유효 비트를 1로 변경해주게 된다. 페이지 폴트를 처리했기 때문에 CPU가 페에지게 접근할 수 있게 된다. 
• 보호 비트 : 페이지 보호 기능을 위해 존재하는 비트
  읽기 전용 페이지 (코드 영역), 쓰기도 가능한 페이지를 구분한다. 읽기, 쓰기, 실행 권한을 나누어서 보호 비트를 저장하기도 한다. (3 bit)
• 참조 비트 : CPU가 이 페이지에 접근한 적이 있는지 여부
• 수정 비트 (더티 비트, dirty bit) : CPU가 이 페이지에 데이터를 쓴 적이 있는지 여부
  CPU가 페이지의 내용을 변경한 적이 있다면, 스왑 아웃될 때 보조기억장치에도 쓰기 작업을 거쳐야 한다. 

 

 

요구 페이징

처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법이다.

1. CPU가 특정 페이지에 접근하는 명령어를 실행한다
2. 해당 페이지가 현재 메모리에 있을 경우 (유효 비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근한다
3. 해당 페이지가 현재 메모리에 없을 경우 (유효 비트가 0일 경우) 페이지 폴트가 발생한다
4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다
5. 다시 1번을 수행한다
6. 페이지가 존재하는 그 프레임에 접근한다

이러한 요구 페이징 시스템이 안정적으로 작동하려면 페이지 교체와 프레임 할당 문제가 해결되어야 한다

 

 

페이지 교체 알고리즘

요구 페이징 기법으로 페이지를 적재하다보면 언젠가 메모리가 가득 차게 된다

당장 실행에 필요한 페이지를 적재하려면 적재된 페이지를 보조기억장치로 내보내야 하는데 이때 어떤 페이지를 내보내야 할까? 이를 결정하는 것이 페이지 교체 알고리즘이다.

 

페이지 폴트가 적은 알고리즘이 좋은 알고리즘이다. 페이지 폴트가 발생해서 보조 기억 장치에서 가져오면 시간이 오래 걸린다. (성능 저하)

 

 

CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열을 페이지 참조열이라고 하는데 이를 통해 페이지 폴트 횟수를 알 수 있다. (연속된 페이지는 당연히 페이지 폴트가 발생하지 않으니까 생략) ex - 2 3 3 3 4 5 5 6 -> 2 3 4 5 6

 

FIFO 페이지 교체 알고리즘

가장 단순한 방식으로 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식이다

프로세스가 사용할 수 있는 프레임이 3개라고 가정하였다. 여기서 페이지 초기 접근의 페이지 폴트는 고려하지 않는다.

프로그램 실행 초기에 적재되었는데 실행 내내 사용될 페이지가 있을 수도 있으니까 이러한 경우에 성능이 나빠진다.

 

2차 기회 페이지 교체 알고리즘

FIFO 페이지 교체 알고리즘의 보완책이다. 가장 오래 있던 페이지를 쫓아내긴 하는데 CPU가 한번 참조한 적이 있다면 (참조 비트가 1이라면) 적재된 시간을 지금으로 설정하고 맨 뒤로 보내게 된다. 참조 비트를 0으로 초기화 하고 적재 시간을 현재 시간을 설정한다. 참조 비트가 0이면 내쫓는다.

이와 같이 페이지 3이 아니라 페이지 1을 내쫓게 된다.

 

최적 페이지 교체 알고리즘

CPU에 의해 참조되는 횟수를 고려한다. 메모리에 오래 남아야할 페이지는 자주 사용될 페이지이다. 앞으로의 사용 빈도가 가장 낮은 페이지를 교체한다.

가장 낮은 페이지 폴트율을 보장하지만 실제 구현이 어렵다. 앞으로 오랫동안 사용되지 않을 페이지를 어떻게 예측할 수 있을까? 보통 다른 페이지 교체 알고리즘의 성능을 평가하기 위한 하한선으로 간주한다.

 

LRU (Least-Recently-Used) 페이지 교체 알고리즘

가장 오래 사용되지 않을 페이지 교체가 아니라 가장 오래 사용되지 않은 페이지 교체하는 방식이다.

 

스래싱

페이지 폴트가 자주 발생하는 이유에는 나쁜 페이지 교체 알고리즘을 사용해서 뿐 아니라 프로세스가 사용할 수 있는 프레임 자체가 적어서의 이유도 있다.

 

스레싱이란 프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능(CPU 이용률)이 저해되는 문제를 말한다. (빈번한 페이지 교체로 인해서 발생)

 

각 프로세스가 필요로 하는 최소한 프레임 수가 보장되지 않았기 때문에 발생한다. 각 프로세스가 필요로 하는 최소한 프레임 수를 파악하고 프로세스들에게 적절한 프레임을 할당해주어야 한다

 

프레임 할당

균등 할당 (equal allocation)

모든 프로세스들에게 균등하게 프레임을 할당한다.

실행되는 프로세스의 크기는 다양하기 때문에 모두 같은 프로임을 할당하는 것은 비합리적이다.

프로세스의 실행 과정을 고려하지 않는다. 물리적인 크기만 고려한다. (정적할당 방식이다.)

 

비례 할당 (proportional allocation)

프로세스 크기에 비례하여 프레임을 할당한다.

프로세스의 실행 과정을 고려하지 않는다. 물리적인 크기만 고려한다. (정적할당 방식이다.)

크기가 작은 프로세스인데 막상 실행해보니 많은 프레임을 필요로 하는 경우도 있기 때문에 프로세스가 필요로하는 프레임 수를 실행해야 봐야할 수 있다

 

작업 집합 모델

CPU가 특정 시간동안 주로 참조한 페이지 개수만큼 프레임을 할당한다. (작업 집합만큼 할당을 한다.)

 프로세스가 일정기간동안 참조한 페이지 집합인 작업집합을 기억하여 빈번한 페이지 교체를 방지한다. 

 

작업 집합을 구하기 위해서는 프로세스가 참조한 페이지와 시간간격이 필요하다.

실행하는 과정을 통해 프레임 할당을 하므로 동적할당 방식이다.

 

페이지 폴트 빈도 기반의 프레임 할당

1. 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 가지고 있다.

2. 페이지 폴트율이 너무 낮으면 그 프로세스는 너무 많은 프레임을 가지고 있다.

상한선과 하한선을 정하고 그 내부 범위 안에서만 프레임을 할당하는 방식이다

실행하는 과정을 통해 프레임 할당을 하므로 동적할당 방식이다.

 

 

페이지의 이점

프로세스는 기본적으로 자원을 공유하지 않는다. 부모 프로세스가 적재된 별도의 공간에 자식 프로세스가 통째로 복제되어 적재된다. 

쓰기 시 복사

부모 프로세스와 동일한 프로세스가 복제되어 생성되면 자식 프로세스는 부모 프로세스와 동일한 프레임을 가리킨다. 부모나 자식에서 쓰기 작업이 없다면 이 상태를 유지한다. 하지만 프로세스는 자원을 공유하지 않기 때문에 둘 중 하나라도 쓰기 작업을 수행하면 해당 페이지는 별도의 공간으로 복제가 된다. 

프로세스 생성 시간을 절약하고 메모리를 절약한다.

 

계층적 페이징

프로세스 테이블의 크기는 생각보다 작지 않다. 프로세스를 이루는 모든 테이블 엔트리를 메모리에 두는 것은 낭비이다. 프로세스를 이루는 모든 페이지 테이블 엔트리를 항상 메모리에 유지하지 않은 방법이 계층적 페이징이다. 

페이지 테이블을 자체를 페이징하여 여러 단계의 페이지를 두는 방식이다. 

페이지 테이블을 여러 페이지로 쪼개고 이 페이지를 가리키는 페이지 테이블 (Outer 페이지 테이블)을 두는 방식이다. 

모든 페이지 테이블을 항상 메모리에 필요가 없어지고 CPU와 가장 가까이 위치한 페이지 테이블(Outer 페이지 테이블)은 항상 메모리에 유지한다.

논리 주소가 위와 같이 바뀌게 된다.

그림은 2단계이다. 단계가 더 많아질 수도 있긴한데 페이지 폴트가 발생할 때 참조 횟수가 늘어나니까 마냥 좋은 것은 아니다.

 

 

9. 파일 시스템

데이터 관점에서는 보조기억장치에 저장된 데이터 덩어리인데 운영체제가 파일과 디렉터리로서 관리를 해주는 것이다.

파일 : 보조기억장치에 저장된 관련 정보의 집합파일을 실행하기 위한 정보 + 부가 정보 (=속성, 메타 데이터)

메타데이터, 속성

 

.많은 운영체제에서는 디렉터리를 그저 특별한 형태의 파일로 간주한다. 파일 내부에는 파일과 관련된 정보가 있다면 디렉터리에는 해당 디렉터리에 담겨있는 대상과 관련된 정보들이 담겨있다. 이 정보는 표의 형태로 저장된다. 

디렉터리 엔트리에는 디렉터리에 포함된 대상의 이름과 그 대상이 보조 기억장치 내에 저장된 위치를 유추할 수 있는 정보가 저장된다.

 

 

파티셔닝

저장장치의 논리적인 영역을 구획하는 작업이다

 

포매팅

어떤 방식으로 파일을 관리할지 결정하고 새로운 데이터를 쓸 준비하는 작업이다. 

 

파일 할당 방법

포맷팅까지 끝난 하드 디스크에 파일을 저장한다. 운영체제는 파일/디렉터리를 블록 단위로 읽고 쓴다.