본 글은 책 "혼자 공부하는 컴퓨터 구조+운영체제" 의 Chapter 15. 파일시스템 부분을 읽고 정리한 내용입니다.

파일

• 하드 디스크나 SSD 같은 보조기억장치에 저장된 관련 정보의 집합, 관련있는 정보를 모은 논리적 단위

파일을 이루는 정보

• 이름
• 파일을 실행하기 위한 정보
• 파일 관련 부가 정보 (속성, 메타데이터)
  • 파일 형식, 위치, 크기 등

파일 속성과 유형

* 속성 이름 자체가 의미를 담고 있는 내용인 경우는 생략

파일 유형

• 확장자를 이용해 유형을 나타냄

파일 연산을 위한 시스템 호출

• 파일을 다루는 모든 작업은 운영체제에 의해 이뤄지고 응용프로그램은 파일을 조작할 수 없음

파일 연산을 위한 시스템 호출

• 생성, 삭제, 열기, 닫기, 읽기 ,쓰기

디렉토리

• 파일들을 정리하기 위해 사용되고 윈도우에서는 폴더라고 부름

옛 운영체제에서는 하나의 디렉토리만 존재했음 (single-level directory)

이후, 여러 계층을 가진 tree-structured directory가 생겨남

절대 경로와 상대 경로

• 절대 경로: 루트 디렉토리에서 자기 자신까지 이르는 고유한 경로
  • /home/minchul/a.sh
• 상대 경로: 현재 디렉토리부터 시작하는 경로
  • 현재 디렉토리 경로가 /home이라면 a.sh의 상대 경로는 minchul/a.sh

디렉토리 연산을 위한 시스템 호출

• 디렉토리 생성, 삭제, 열기, 닫기, 읽기

디렉토리 엔트리

• 많은 운영체제에서 디렉토리를 그저 ‘특별한 형태의 파일’로 간주
• 디렉토리는 보조기억장치에 테이블 형태의 정보로 저장되는데 각각의 행을 디렉토리 엔트리라고 함

파일 시스템에 따라 디렉터리 엔트리에 파일 속성을 명시하는 경우도 있음

예시

home 디렉토리는 대략 다음과 같이 구성됨

minchul 디렉토리 엔트리에는 디렉토리에 포함된 파일들의 이름(a.sh, b.c, c.tar)과 이들의 위치를 알 수 있는 정보들이 포함되어있음

파일 시스템

• 파일과 디렉토리를 보조기억장치에 일목요연하게 저장하고 접근할 수 있게 하는 운영체제 내부 프로그램

파티셔닝과 포매팅

• 보조기억장치를 사용하려면 파티션을 나누는 작업과 포맷 작업을 거쳐야 함
• 파티셔닝: 저장 장치의 논리적인 영역을 구획하는 작업 (일종의 칸막이로 영역을 나누는 작업)
  • 파티션: 파티셔닝 작업으로 나눠진 영역 하나하나
• 포매팅: 파일 시스템을 설정하여 어떤 방식으로 파일을 저장하고 관리할 것인지를 결정하고 새로운 데이터를 쓸 준비를 하는 작업

• 포매팅 할 때 파일 시스템이 결정됨
• 파일 시스템은 여러 종류가 있고 파티션마다 다른 파일 시스템을 설정할 수도 있음

파일 할당 방법

• 운영체제는 파일과 디렉토리를 블록(block) 단위로 읽고 씀
  • 하나의 파일이 보조기억장치에 저장될 떄 하나 이상의 블록에 걸쳐 저장됨

• 하드 디스크의 가장 작은 저장단위는 섹터지만 운영체제는 하나 이상의 섹터를 블록이라는 단위로 묶어 관리

• 하드 디스크내에 여러 블록이 있음

파일을 보조기억장치에 할당하는 방법

1. 연속 할당
2. 불연속 할당
   • 연결 할당
   • 색인 할당

연속 할당(contiguous allocation)

• 가장 단순한 방식
• 블록을 3, 2, 5개 차지하는 정도의 크기를 가진 파일 a, b, c가 있다면 아래처럼 할당

• 연속으로 할당된 파일에 접근하기 위해서는 파일의 첫번째 블록 주소와 블록 단위의 길이만 알면됨

• 연속 할당을 사용하는 파일 시스템에서는 디렉토리에 엔트리에 파일 이름과 더불어 첫번째 블록 주소와 블록 단위의 길이를 명시

장점

• 구현이 단순

단점

• 외부 단편화를 야기할 수 있음

단점 예시

위의 사진과 같이 파일이 연속할당방식으로 저장된 상황에서 파일 D, F가 삭제 된다면?

• 블록은 총 11개가 남지만, 크기가 블록 7개 이상을 사용하는 파일은 할당될 수 없음

연결 할당(linked allocation)

• 불연속 할당의 종류
• 파일을 이루는 데이터를 linked list로 관리

• 4개의 블록으로 구성된 a라는 파일이 있다고 할 때
• 10→5→13→2 순으로 블록이 연결되어 있고 2번 블록에는 다음 블록이 없다는 특별한 표시자(-1)를 기록

• 디렉토리 엔트리에는 파일 이름과 함께 첫번째 블록 주소와 블록 단위의 길이를 명시

단점

1. 반드시 첫번째 블록부터 하나씩 차례대로 읽어야 함

• 파일 내 임의의 위치에 접근하는 속도(random access 속도)가 매우 느려 성능면에서 비효율적

2. 하드웨어 고장이나 오류 발생 시 해당 블록 이후 블록은 접근할 수 없음

• 하나의 블록 안에 파일 데이터와 다음 블록 주소가 모두 포함되어 있다보니, 파일을 이루는 블록에 하나라도 문제가 발생하면 이후 블록에 접근할 수 없음

색인 할당(indexed allocation)

• 파일의 모든 블록 주소를 색인 블록(index block)이라는 하나의 블록에 모아 관리하는 방식

• 파일 a의 색인 블록은 4번 블록
• 파일의 데이터는 7, 13, 11 블록이 저장되어 있다고 가정
• 파일 a에 순차적으로 접근하고 싶다면 생인 블록에 저장된 주소로 차례대로 접근하면 됨

• 임의의 위치에 접근하고 싶다면 색인 블록의 i번째 항목이 가리키는 블록에 접근하면 됨
• 디렉토리 엔트리에는 파일 이름과 색인 블록 주소를 명시

색인 할당을 기반으로 만든 파일 시스템이 유닉스 파일 시스템

파일 시스템 살펴보기

대표적인 파일 시스템 2가지

1. FAT 파일 시스템: USB, SD 카드등의 저용량 저장 장치에 사용됨
2. 유닉스 파일 시스템:유닉스 계열 OS에 사용됨

FAT 파일 시스템 (File Allocation Table)

• 연결 할당 기반 파일 시스템의 단점을 보완
  • 단점의 근본적인 원인은 블록 안에 다음 블록의 주소를 저장했기 때문

각 블록에 포함된 다음 블록의 주소들을 한데 모아 테이블 형태로 관리하면? 파일 할당 테이블(FAT)!

• 파일의 첫번째 블록 주소(4번블록)만 알면 4→8→3→5 순으로 파일의 데이터가 담긴 모든 블록에 접근할 수 있음

• 이렇게 FAT을 이용하는 파일 시스템이 바로 FAT 파일 시스템
• MS-DOS에서 사용되었고 최근까지 저용량 저장 장치용 파일 시스템으로 많이 사용됨
• 버전에 따라 FAT12, 16, 32가 있으며 숫자는 블록을 표현하는 비트수를 의미

FAT(FAT12) 파일 시스템을 사용하는 파티션 도식도

• FAT 영역: FAT가 저장되고 파티션의 앞부분에 만들어짐
• 루트 디렉토리 영역: 루트 디렉토리가 저장되는 영역
• 데이터 영역: 서브 디렉토리와 파일들을 위한 영역

FAT가 메모리에 캐시될 경우 느린 임의 접근 속도도 개선 가능

FAT파일 시스템의 디렉토리 엔트리

• 속성은 읽기전용/숨김 파일/시스템 파일/ 일반 파일/ 디렉토리 등을 식별하기 위한 항목

아래 디렉토리 구조를 이루는 FAT 파일 시스템에서 /home/minchul/a.sh 파일을 읽는 과정

/home/minchul/a.sh 에 접근하는 과정

1. 루트 디렉토리에서 home 디렉토리는 몇번 블록에 있는지 살펴봄 → 3번 블록
2. 3번 블록을 읽어 home 디렉토리 내용을 살펴보고 minchul 디렉토리가 몇번 블록에 있는지 살펴봄 → 15번
3. 15번 블록을 읽어 a.sh 파일의 첫번째 블록 주소를 확인 → 9번
4. FAT을 통해 9→8→11→13 블록 순서로 a.sh 파일 내용에 접근 가능

유닉스 파일 시스템

• 색인 할당 기반의 파일 시스템
• 색인 블록 == i-node
  • 파일의 속성 정보와 15개의 블록 주소가 저장될 수 있음

• 파일마다 i-node를 가지고 있고 i-node 마다 고유한 번호가 부여되어있음

• 파티션 내에 i-node 영역에 i-node들이 있고 데이터 영역에 디렉토리와 파일들이 있음

문제: i-node의 크기는 유한한데 블록을 20개, 30개, 그 이상 차지하는 파일은?

첫째, 블록 주소 중 12개에는 직접 블록 주소를 저장

• i-node가 가리킬 수 있는 열다섯 개의 블록 주소 중 처음 12개에는 파일 데이터가 저장된 블록 주소를 직접 명시
  • direct block: 파일 데이터가 저장된 블록

둘째, ‘첫째’ 내용으로 충분하지 않다면 13번째 주소에 단일 간접 블록 주소를 저장

• 단일 간접 블록(single indirect block): 파일 데이터가 저장된 블록 주소가 아닌 파일 데이터를 저장한 블록 주소가 저장된 블록을 의미

셋째, ‘둘째’ 내용으로 충분하지 않다면 14번째 주소에 이중 간접 블록 주소를 저장

• 이중 간접 블록(double indirect block): 데이터 블록 주소를 저장하는 블록 주소가 저장된 블록

넷째, ‘셋째’ 내용으로 충분하지 않다면 열다섯 번째 주소에 삼중 간접 블록 주소를 저장

unix 파일 시스템의 디렉토리 엔트리도 파일 이름과 i-node 번호로 구성됨

예시

• 유닉스 파일 시스템에서 /home/minchul/a.sh 파일을 읽는 과정

• 루트 디렉토리 위치는 루트 디렉토리의 i-node를 통해 확인
  • 유닉스 파일 시스템은 루트 디렉토리의 i-node를 항상 기억하고 있음
  • 2번 i-node가 루트 디렉토리의 i-node라고 가정

1. i-node 2를 통해 루트 디렉토리 위치 파악 → 1번 블록
2. 1번 블록을 읽으면 루트 디렉토리 내용을 알 수 있음 → home 디렉토리의 i-node 번호는 3
3. i-node 3에 접근하여 home의 디렉토리 위치 파악 →210번 블록
4. 210번 블록을 읽으면 home 디렉토리 내용을 알 수 있음 → minchul의 i-node 번호는 8
5. i-node 8에 접근하면 minchul 폴더의 위치 파악 → 121번 블록
6. 121번 블록을 읽으면 minchul 디렉토리 내용을 알 수 있음 → a.sh 파일의 i-node 번호는 9번
7. i-node 9에는 98, 12, 13 블록이 있음

⇒ 결론적으로 a.sh 파일을 읽기 위해 98→12→13 블록에 접근하면 됨, i-node를 통해 위치 정보를 알고, 블록을 통해 내용을 알 수 있음

본 글은 책 "혼자 공부하는 컴퓨터 구조+운영체제" 의 Chapter 14. 가상메모리 부분을 읽고 정리한 내용입니다.

연속 메모리 할당

• 프로세스에 연속적인 메모리 공간을 할당

스와핑

• 현재 사용되지 않는 프로세스들을 보조기억장치의 일부 영역으로 쫓아내고 생긴 빈공간에 새로운 프로세스를 적재

• swap space: 프로세스들이 쫓겨나는 보조기억장치의 일부 영역
• swap-out: 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것
• swap-in: 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨 오는 것

스와핑을 이용하면 실제 메모리 크기보다 프로세스들이 요구하는 메모리 공간 이 더 크더라도 동시에 실행할 수 있음

스왑 영역 크기 확인하기 (mac): sysctl vm.swapusage

$ sysctl vm.swapusage
vm.swapusage: total = 4096.00M  used = 2755.62M  free = 1340.38M  (encrypted)

메모리 할당

• 프로세스는 메모리의 빈 공간에 할당되어야 하는데 여러개라면?
• 최초 적합, 최적 적합, 최악 적합

• 빈공간 A, B, C가 있다면?

최초 적합(first-fit)

• 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식
  • 순서대로 검색한다는 의미는? 어디서부터 검색?
• 검색 최소화, 빠른 할당

최적 적합(best-fit)

• 운영체제가 빈 공간을 모두 검색해본 뒤, 적재 가능한 가장 작은 공간에 배치

최악 적합(worst fit)

• 운영체제가 빈 공간을 모두 검색해본 뒤, 적재 가능한 가장 큰 공간에 프로세스를 배치

외부 단편화(external fragmentation)

• 프로세스들이 실행&종료 되길 반복하며 메모리 사이사이에 빈 공간이 발생해서 메모리가 낭비되는 현상

외부 단편화를 해결할 수 있는 대표적인 방법들

1. 메모리 압축

• 여기저기 흩어져 있는 빈 공간들을 하나로 모으는 방식

단점

1. 작은 빈 공간들을 하나로 모으는 동안 시스템은 하던 일을 중지해야하고, 메모리에 있는 내용들을 옮기는 작업은 많은 오버헤드를 야기
2. 프로세스 이동 방법에 대한 방법을 결정하기 어려움
3. 물리 메모리보다 큰 프로세스 실행 불가

페이징을 통한 가상 메모리 관리

가상 메모리

• 실행하고자 하는 프로그램의 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술

페이징이란?

• 프로세스를 일정 크기로 자르고, 이를 메모리에 불연속적으로 할당하는 메모리 관리 기법

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

페이지 교체와 프레임 할당

요구 페이징(Demand paging)

• 프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법

기본적인 양상

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

* 순수 요구 페이징(pure demand paging)

• 아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행부터 하는 기법
• 프로세스의 첫 명령어를 실행하는 순간부터 페이지 폴트가 계속 발생함
• 실행에 필요한 페이지가 어느 정도 적재된 이후부터는 페이지 폴트 발생 빈도가 떨어짐

요구페이징이 안정적으로 작동하기 위해서는 아래의 2가지가 해결되어야 함

• 페이지 교체
• 프레임 할당

페이지 교체

• 요구 페이징 기법으로 페이지들을 적재하다보면 언젠가 메모리가 가득 차게 됨
• 당장 실행에 필요한 페이지를 적재하려면 페이지를 보조 기억장치로 보내야 하는데 이를 결정하는 방법이 페이지 교체 알고리즘

페이지 교체 알고리즘

• 일반적으로 페이지 폴트가 가장 적제 발생하는 알고리즘을 좋은 알고리즘으로 평가
  • 페이지 폴트가 일어나면 보조기억장치로부터 필요한 페이지를 가져와야하기 때문에 성능 저하발생하기 떄문

페이지 폴트 횟수를 어떻게 알 수 있을까?

⇒ 페이지 참조열 (page reference string) 사용

CPU가 참조하는 페이지들중 연속된 페이지를 생략한 페이지열 (연속된 페이지 참조에서는 페이지 폴트가 발생하지 않기 때문)

예를 들어 아래 숫자들의 페이지 번호들을 CPU가 참조했다면,

2 2 2 3 5 5 5 3 3 7

연속된 페이지를 생략한 페이지 참조열은 아래와 같음

2 3 5 3 7

FIFO 페이지 교체 알고리즘

• First-In, First-Out Page Replacement Algorithm
• 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식

• 페이지가 초기에 적재될 때 발생할 수 있는 페이지 폴트는 고려하지 않음

단점

• 프로그램 실행 내내 사용될 내용을 포함할 수도 있는데 이런 페이지를 메모리 메모리에 먼저 적재되었다고 내쫓을 수 있음

2차 기회(second-chance) 페이지 교체 알고리즘

• 참조 비트 1인 경우: 한번 더 기회를 주기
  • 참조 비트 0으로 초기화 후 적재 시간을 현재 시간으로 설정
• 참조 비트 0인 경우: CPU가 참조한 적이 없는 페이지로 바로 내쫓기

페이지 3의 참조 비트가 1인 경우

페이지 3의 참조비트를 0으로 초기화 후 가장 최근에 적재된 페이지로 간주

최적 페이지 교체 알고리즘(Optimal p age replacement algorithm)

• CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘
• 앞으로 사용빈도가 가장 낮은 페이지를 교체하는 방식

2 3 1 3 5 2 3 4 2 3

• 첫 페이지 폴트: 페이지 1의 경우 한번 사용된 후 이후에 사용되지 않기 때문에 이를 교체함
• 두번째 페이지 폴트: 2,3,5 페이지가 적재된 상황에서 4 페이지를 적재해야 할 때, 그 이후 페이지 2, 3이 사용되므로 5를 교체

특징

• 가장 낮은 페이지 폴트율을 보장하는 알고리즘
• 앞으로 사용되지 않을 페이지 예측관련해 실제 구현이 어려움
• 다른 페이지 교체 알고리즘 성능을 평가하기 위한 하한선으로 간주

LRU 페이지 교체 알고리즘

• Least Recently Used Replacement Algorithm
• 가장 오래 사용되지 않은 페이지 교체

첫 페이지 폴트

• 페이지 2, 3, 1이 적재된 상태
• 페이지 5를 적재하려는 상황에서 최근에 페이지 1, 3, 이 적재되었으므로 페이지 2를 교체

두번째 페이지 폴트

• 페이지 5, 3, 1이 적재된 상태
• 페이지 2를 적재하려는 상황에서 최근에 페이지 5, 3, 이 적재되었으므로 페이지 1을 교체

세번째 페이지 폴트

• 페이지 5, 3, 2가 적재된 상태
• 페이지 4를 적재하려는 상황에서 최근에 페이지 2, 3 이 적재되었으므로 페이지 5를 교체

스래싱과 프레임 할당

페이지폴트가 자주 발생하는 이유

1. 나쁜 페이지 교체 알고리즘
2. 프로세스가 사용할 수 있는 프레임 자체가 적어서

• 새로운 페이지를 참조할 때마다 페이지 폴트가 발생 → 저조한 CPU 이용율

스래싱(Thrashing)

• 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제

• 동시에 실행되는 프로세스의 수를 늘린다고 CPU의 이용률이 높아지는 것은 아님

* 멀티프로그래밍의 정도: 메모리에 동시에 실행되는 프로세스의 수

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

프레임 할당 방식

1. 균등 할당(equal allocation)

• 가장 단순한 할당 방식
• 모든 프로세스들에게 균등하게 프레임을 할당하는 방식
  • 300개의 프레임을 3개의 프로세스에 할당 시 각 프로세스에 100개의 프레임을 할당
• 실행되는 프로세스들의 크기를 고려하지 못한 방식

2. 비례 할당(proportional allocation)

• 프로세스의 크기에 비례하여 프레임 할당

참고) 균등할당과 비례 할당은 프로세스의 실행 과정을 고려하지 않고 단순히 프로세스의 크기와 물리 메모리의 크기만을 고령한 방식이라는 점에서 정적 할당 방식이라고 함

프로세스를 실행하는 과정에서 배분할 프레임을 결정하는 방식의 종류

1. 작업 집합 모델(working set model)

• 작업집합: 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합
• 프로세스가 일정기간동안 참조한 페이지 집합을 기억하여 빈번한 페이지 교체를 방지

1. 페이지 폴트 빈도(PFF: Page-Fault Frequency)

아래 2가지 가정에서 생겨난 아이디어

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

• 상한선, 하한선 범위 안에서만 프레임을 할당하는 방식

참고

1. 책 "혼자 공부하는 컴퓨터 구조+운영체제"
2. 유튜브 "혼자 공부하는 컴퓨터 구조 + 운영체제"

본 글은 책 "혼자 공부하는 컴퓨터 구조+운영체제" 의 Chapter 13. 교착상태 부분을 읽고 정리한 내용입니다.

교착 상태(Deadlock)란?

• 일어나지 않을 사건을 기다리며 진행이 멈춰버리는 현상

게임 프로세스는 자원 A를 점유한 채 웹 브라우저 프로세스가 점유하고 있는 자원 B의 사용이 끝나길 기다리고, 웹 브라우저 프로세스는 자원 B를 점유한 채 게임 프로세스의 자원 A 사용이 끝나길 기다리는 상황

교착 상태는 아주 다양한 상황에서 발생하고 뮤텍스 락에서도 발생할 수 있음

lock1 = true;
while (lock2 == true); # wait
//임계 구역 진입
lock1 = false;

lock2 = true;
while (lock1 == true); # wait
//임계 구역 진입
lock2 = false;

• 위 두 코드 모두 while 문에서 교착 상태가 발생 
• 교착 상태를 해결하기 위해서는
  • 발생한 상황을 정확히 표현하고
  • 일어나는 근본적인 이유에 대해서 알아야 함

자원 할당 그래프(Resource-allocation graph)

• 어떤 프로세스가 어떤 자원을 사용하고 있고, 어떤 프로세스가 어떤 자원을 기다리는지 표현하는 간단한 그래프

1. 프로세스는 원으로, 자원의 종류는 사각형으로 표현

2. 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현

3. 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시

4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스→자원 방향으로 화살표를 표시

교착 상태가 발생한 상황은 자원 할당 그래프가 원의 형태를 띄고 있음

교착 상태 발생 조건

상호 배제

• 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태

점유와 대기

• 자원을 할당 받은 상태에서 다른 자원을 할당받기를 기다리는 상태

비선점

• 프로세스가 자원을 비선점하고 있기 때문

원형 대기

• 프로세스가 요청 및 할당 받은 자원이 원의 형태를 이루었기 때문 (circular wait)

교착 상태 해결 방법

교착 상태 예방

• 교착 상태 발생 필요 조건 4가지 중 하나를 충족하지 못하게 하는 방법
  • 상호 배제
  • 점유와 대기
  • 비선점
  • 원형 대기

자원의 상호 배제 없애기

• 모든 자원을 공유 가능하게 만듦
• 현실가능한 방법은 아님

점유와 대기 없애기

• 특정 프로세스에 자원을 모두 할당하거나 아예 할당하지 않는 방식으로 배분 → 자원의 활용도를 낮출 수 있는 방식임
• 많은 자원을 필요로 하는 프로세스가 무한정 기다리게 되는 기아현상을 야기할 수 있음

비선점 조건 없애기

• 선점이 가능한 자원(ex) CPU)에 한해 효과적이지만 모든 자원이 선점 가능한 것은 아님 (ex) 프린터)

원형 대기 조건 없애기

• 모든 자원에 번호를 붙이고 오름차순으로 자원을 할당

• 하지만 모든 자원에 번호를 붙이고, 어떤 자원에 어떤 번호를 붙이냐에 따라 활용률이 달라짐

교착 상태 회피

• 교착 상태가 발생하지 않을 정도로만 조심히 자원을 할당하는 방식

교착 상태를 회피하는 방법을 학습하기 위해 아래 용어를 알아야 함

안전 순서열(Safe sequence)

• 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 의미

안전 상태(Safe state)

• 안전 순서열대로 프로세스들에 자원을 배분하여 교착 상태가 발생하지 않는 상태

불안전 상태(Unsafe state)

• 안전 순서열이 없는 상황으로 교착 상태가 발생할 수 있는 위험이 있는 상태

예시

• 컴퓨터 시스템에 총 12개의 자원이 존재
• 프로세스 P1, P2, P가 실행중
• 각각 5개, 2개, 2개의 자원을 할당받아 사용중
• 운영체제가 프로세스에 배분할 수 있는 자원은 3개 (12-5-2-2) 가 남은 상황
• P1, P2, P3는 각각 10, 4, 9개의 자원을 요구할 수 있음

• 할당 가능 자원: 12개
• 할당한 자원: 9개
• 남은 자원: 3개

위의 경우 안전 순서열이 존재: P2→P1→P3

Q. 안전 순서열은 어떻게 알 수 있나? → 은행원 알고리즘 참고

안전 순서열이 존재하지 않는 경우

• 위의 예시에서 모든 프로세스가 최대의 자원을 요구하는 상황에 P3에 선뜻 하나의 자원을 내줌

• 할당 가능 자원: 12개
• 할당한 자원: 10개
• 남은 자원: 2개

위의 상황에서 남은 자원을 P2에 모두 주면, 남은 자원은 0개

• 할당 가능 자원: 12개
• 할당한 자원: 12개
• 남은 자원: 0개

위의 예에서 P2가 모든 자원을 반납해도 P1, P3의 요구량을 모두 채울 수 없으므로 서로가 보유하고 있는 자원만을 바라보며 무한정 기다릴 수 밖에 없음 → 불안전 상태로 교착 상태 발생

교착 상태 검출 후 회복

• 교착 상태가 검출되면
  • 선점을 통한 회복
  • 프로세스 강제 종료를 통한 회복

선점을 통한 회복

• 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식

프로세스 강제 종료를 통한 회복

• 교착 상태에 놓인 프로세스가 모두 강제 종료(→ 작업 내용을 잃음)
• 교착 상태가 해결될 때까지 한 프로세스씩 강제 종료(→오버헤드가 있지만 잃는 작업 내용 최소화)

참고

1. 책 "혼자 공부하는 컴퓨터 구조+운영체제"
2. 유튜브 "혼자 공부하는 컴퓨터 구조 + 운영체제"

본 글은 책 "혼자 공부하는 컴퓨터 구조+운영체제" 의 Chapter 12. 프로세스 동기화 부분을 읽고 정리한 내용입니다.

동기화의 의미

• 동시다발적으로 실행되는 많은 프로세스는 서로 데이터를 주고 받으며 협력하며 실행될 수 있고 이 때 데이터의 일관성을 유지해야 함
• 프로세스 동기화란 프로세스 사이의 수행 시기를 맞추는 것을 의미하고 아래 2가지를 위헌 동기화가 있음
  • 실행 순서 제어: 프로세스를 올바른 순서대로 실행하기
  • 상호 배제: 동시에 접근해서는 안되는 자원에 하나의 프로세스만 접근하게 하기

실행 순서 제어를 위한 동기화

• book.txt 파일에 2가지 프로세스가 동시에 실행중이라고 가정해보자
  • Writer process
  • Reader process
• 둘은 무작정 아무 순서대로 실행되어서는 안되고 Writer 실행이 끝난 후 Reader가 실행되어야 함

상호 배제를 위한 동기화

• 공유가 불가능한 자원의 동시 사용을 피하기 위해 사용하는 알고리즘

예시 (Bank account problem)

• 계좌에 10만원이 저축되어 있다고 가정
• 프로세스 A는 2만원 입금
• 프로세스 B는 5만원 입금

프로세스 A 실행되는 과정

1. 계좌의 잔액 읽음
2. 읽어들인 잔액에 2만원 더함
3. 더한 값 저장

프로세스 B 실행되는 과정

1. 계좌의 잔액 읽음
2. 읽어들인 잔액에 5만원 더함
3. 더한 값 저장

이때 두 프로세스가 동시에 실행되었다고 가정했을 때 동기화가 제대로 이루어지지 않은 경우 아래와 같이 전혀 엉뚱한 결과가 나올 수 있음

정상적으로 작동하길 기대되는 예시

생산자와 소비자 문제

• 생산자와 소비자는 ‘총합’이라는 데이터를 공유
• 생산자는 총합에 1을 더하고, 소비자는 총합에 1을 뺌

• 생산자와 소비자를 동시에 실행했을 때 예상되는건 총합의 값은 초기 상태를 유지하는 것
• 하지만 직접 코드를 돌려보면 예상치 못한 결과 발생

#include <iostream>
#include <queue>
#include <thread>

void produce();
void consume();

int sum = 0;

int main() {

    std::cout << "초기 합계: " <<  sum << std::endl;
    std::thread producer(produce);
    std::thread consumer(consume);

    producer.join();
    consumer.join();
    
    std::cout << "producer, consumer 스레드 실행 이후 합계: " <<  sum << std::endl;
    
    return 0;
}

void produce() {
    for(int i = 0; i < 100000; i++) {
        sum++;
    }
}

void consume() {
    for(int i = 0; i < 100000; i++) {
        sum--;
    }
}

초기 합계 : 10
producer, consumer 스레드 실행 이후 합계: -13750

• 이는 생산자 프로세스와 소비자 프로세스가 제대로 동기화되지 않았기 때문
  • ‘총합’ 데이터를 동시에 사용하는데 소비자가 생산자의 작업이 끝나기 전에 총합을 수정했고, 생산자가 소비자의 작업이 끝나기 전에 총합을 수정했기 때문

공유 자원과 임계 구역

• shared resource: 여러 프로세스 혹은 쓰레드가 공유하는 자원
  • 전역 변수, 파일, 입출력 장치, 보조기억장치
• 임계구역: 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역
• 두 개 이상의 프로세스가 임계 구역에 진입하고자 하면 둘 중 하나는 대기해야 함

Race condition

• 임계 구역은 두 개 이상의 프로세스가 동시에 실행되면 안되는 영역이지만 여러 프로세스가 동시에 다발적으로 실행하여 자원의 일관성이 깨지는 경우

Race condition의 근본적인 이유

• 고급언어(C/C++, Python) → 저급언어로 변환되며 코드가 늘어날 수 있음
• 이 때 context switching이 발생하면 예상치 못한 결과를 얻을 수 있음

상호 배제를 위한 동기화는 이런 일이 발생하지 않도록 두 개 이상의 프로세스가 임계 구역에 동시에 접근하지 못하도록 관리하는 것을 의미하며 운영체제는 3가지 원칙하에 해결

1. progress: 임계 구역에 어떤 프로세스도 진입하지 않았다면 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 함
2. Mutual exclusion : 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임게 구역에 들어올 수 없음
3. bounded waiting: 한 프로세스가 임계 구역에 진입하고 싶다면 그 프로세스는 언젠가는 임게 구역에 들어올 수 있어야 함 (무한정 대기 X)

동기화 기법

동기화를 위한 대표적인 도구 3가지

1. 뮤텍스 락
2. 세마포
3. 모니터

뮤텍스 락(Mutex lock)

• Mutual EXclusion lock, 상호 배제를 위한 동기화 도구로 기능을 코드로 구현한 것
• 매우 단순한 형태는 하나의 전역 변수와 두개의 함수
  • 자물쇠 역할: 프로세스들이 공유하는 전역 변수 lock
  • 임계구역을 잠그는 역할: acquire 함수
  • 임계 구역의 잠금을 해제하는 역할: release 함수

acquire 함수

• 프로세스가 임계 구역에 진입하기 전에 호출하는 함수
• 임계 구역이 잠겨있으면 열릴 때까지(lock이 false가 될 때까지) 임계 구역을 반복적으로 확인
• 임계 구역이 열려있으면 임계 구역을 잠그는 함수

release 함수

• 임계 구역에서의 작업이 끝나고 호출하는 함수

acquire(){
    while (lock ==true) # 반복해서 확인하는 대기 방식을 busy wait이라고 함
        ;               # 임계 구역이 잠겨 있는지 반복적으로 확인
    lock = true;        # 만약 임계 구역이 잠겨 있지 않다면 임계 구역 잠금
}

release() {
    lock = false; # 임계 구역 작업이 끝나서 잠금 해제
}

acquire();
// 임계구역 (ex) '총합' 변수 접근)
release();

세마포(Semaphore)

• 사전적 의미: 수기 신호

• 뮤텍스 락과 비슷하지만 좀 더 일반화된 방식의 동기화 도구
• 공유 자원이 여러개 있는 상황에서도 적용이 가능한 동기화 도구

• 단순한 형태로 하나의 변수와 두개의 함수로 구현가능
  • 임계 구역에 진입할 수 있는 프로세스의 개수를 나타내는 전역 변수 S
  • 임계 구역에 들어가도 좋은지 기다려야 할지를 아려주는 wait 함수
  • 이제 가도 좋다는 신호를 주는 signal 함수

wait()
{
    while( S <= 0) # 임계 구역에 진입할 수 있는 프로세스가 0개 이하라면
    ;              # 사용할 수 있는 자원이 있는지 반복적으로 확인하고
    S--;           # 진입할 수 있는 프로세스 개수가 1개 이상이면 S를 1 감소시키고 진입
}

signal()
{
    S++;           # 임계 구역에서의 작업을 마친 뒤 S를 1 증가 시킴
}

wait()
// 임계 구역
signal()

예시

세 개의 프로세스 P1, P2, P3가 2개의 공유 자원(S=2)에 순서대로 접근한다고 가정하면,

1. 프로세스 P1 wait 호출, S는 2→1로 감소
2. 프로세스 P2 wait 호출, S는 1→0으로 감소
3. 프로세스 P3 wait 호출, S는 현재 0이므로 무한히 반복하며 S확인
4. 프로세스 P1 임계 구역 작업 종료, signal 호출, S는 0→1
5. 프로세스 P3에서 S가 1이 됨을 확인하고 S 1→0 만들고 임계 구역 진입

위의 3 과정에서 busy wait 반복하며 확인하며 CPU 사이클이 낭비됨
* busy wait: 쉴새없이 반복하며 확인해보며 기다리는 과정

해결 방법

1. 사용할 수 있는 자원이 없을 경우 대기 상태로 만듦 (해당 프로세스의 PCB를 waiting queue에 삽입)
2. 사용할 수 있는 자원이 생겼을 경우 대기 큐의 프로세스를 준비 상태로 만듦 (해당 프로세스의 PCB를 waiting queue → ready queue 로 이동)

wait()
{
    S--;
    if ( S < 0) {
        add this process to waiting queue;
        sleep();
	}
}

signal()
{
    S++;
    if (S<=0) 
    # remove a process p from waiting Queue;
    wakeup(p); # waiting queue -> ready queue
  }
}

프로세스 4개이고, 공유 자원이 2개라고 가정해보면,

1. 프로세스 P1 wait 호출, S는 2→1로 감소
2. 프로세스 P2 wait 호출, S는 1→0으로 감소
3. 프로세스 P3 wait 호출, S는 0→-1이 되고 waiting queue로 이동
4. 프로세스 P4 wait 호출, S는 -1→-2가 되고 waiting queue로 이동
5. 프로세스 P1 임계 구역 작업 종료, signal 호출, S는 -2→-1이 되고 PCB를 waiting queue → ready queue로 이동
6. 프로세스 P2 임계 구역 작업 종료, signal 호출, S는 -1→0이 되고, PCB를 waiting queue → ready queue로 이동

세마포는 프로세스의 실행순서 동기화도 지원

• 변수 S를 0으로 두고 먼저 실행할 프로세스 뒤에 signal 함수, 다음에 실행할 프로세스 앞에 wait함수를 붙이면 됨

• 위의 경우 프로세스의 실행 순서에 상곤없이 P1→P2 순으로 임계 구역에 진입

모니터(Monitor)

• 세마포는 훌륭한 프로세스 동기화 도구지만 매번 임계 구역 앞뒤로 wait & signal 함수를 명시해야 함
• 모니터는 사용자(개발자)가 다루기에 편한 동기화 도구

상호 배제를 위한 동기화

• 공유자원과 공유 자원에 접근하기 위한 인터페이스를 묶어서 관리
• 프로세스는 반드시 인터페이스를 통해서만 공유 자원에 접근하도록 함

실행 순서 제어를 위한 동기화

• 내부적으로 조건 변수(condition variable)를 이용
• 프로세스나 스레드의 실행 순서를 제어하기 위해 사용하는 특별한 변수

조건 변수별 queue가 있고 이를 통해 실행 순서를 결정할 수 있음

• 조건 변수로 wait과 signal 연산을 수행할 수 있음
  • 조건변수.wait(): 대기 상태로 변경, 조건 변수에 대한 큐에 삽입

• 조건변수.signal(): wait()으로 대기 상태로 접어든 조건 변수를 실행상태로 변경

모니터 안에는 하나의 프로세스만 있을 수 있음

• wait()을 호출했던 프로세스는 signal()을 호출한 프로세스가 모니터를 떠난 뒤에 수행을 재개
• signal()을 호출한 프로세스의 실행을 일시 중단하고 자신이 실행된 뒤 다시 signal()을 호출한 프로세스의 수행을 재개

참고

1. 책 "혼자 공부하는 컴퓨터 구조+운영체제"
2. 유튜브 "혼자 공부하는 컴퓨터 구조 + 운영체제"

본 글은 책 "혼자 공부하는 컴퓨터 구조+운영체제" 의 Chapter 11. CPU 스케쥴링 부분을 읽고 정리한 내용입니다.

CPU 스케쥴링이란?

• 프로세스들에게 공정하게 합리적으로 CPU 자원을 배분하는 것
• 제대로 안되면 반드시 실행되어야 할 프로세스들이 실행되지 못하거나 당장 급하지 않은 프로세스들만 주로 실행되는 등 무질서한 상태가 발생할 수도 있음

프로세스 우선순위

• 아주 단순하게 생각해 봤을 때 CPU를 사용 요청을 먼저 보낸 프로세스들을 순서대로 CPU 이용하게 하는 방법
• 합리적인 방식같지만 좋은 방식은 아님
  • 단순히 FIFO 형태로 CPU를 이용하면 비효율적으로 대기 시간이 길 수 있음
  • 또한 프로세스 마다 우선순위가 다르기 때문

일반적인 프로세스가 실행되는 과정

• 대부분의 프로세스들은 CPU와 입출력장치를 모두 사용하며 실행됨 → 실행/대기 상태 반복
  • 예를들어 워드 프로세서에서 CPU를 이용해 명령어 실행, 사용자로부터 입력받은 내용을 보조기억장치에 저장, CPU를 사용하여 명령어를 실행, 사용자가 입력한 내용을 화면에 출력

• 프로세스 종류마다 입출력장치를 이용하는 시간과 CPU를 이용하는 시간의 양에 차이가 있음
  • I/O bound process: 비디오 재생이나 디스크 백업 작업을 담당하는 프로세스와 같이 입출력 작업이 많은 프로세스 (실행상태보다 입출력을 위한 대기 상태에 더 많이 머무름)
  • CPU bound process: 복잡한 수학 연산, 컴파일, 그래픽 처리 작업을 담당하는 프로세스와 같이 CPU 작업이 많은 프로세스 (대기 상태보다 실행 상태에 더 많이 머무름)

• I/O bound process와 CPU bound process가 동시에 CPU 자원을 요구한 경우
  • I/O bound process를 빨리 실행시켜 입출력 장치를 끊임없이 작동시켜 대기 상태가 되면 CPU bound process에 집중적으로 CPU를 할당하는 것이 더 효율적
    ⇒ 이를 위해 운영체제는 프로세스마다 priority를 부여 (PCB에 명시)

참고) 프로세스의 우선순위를 확인할 수 있는 명령어

$ ps -el
  UID   PID  PPID        F CPU PRI NI       SZ    RSS WCHAN     S             ADDR TTY           TIME CMD
    0     1     0     4004   0  46  0 411466656  19712 -      Rs                  0 ??        12:30.24 /sbin/launchd
    0   146     1     4004   0  31  0 410161104   1776 -      Ss                  0 ??         0:00.01 /usr/libexec/iou
    0   298     1     4004   0  31  0 410536368  41248 -      Ss                  0 ??        10:18.55 /usr/libexec/log
    0   299     1     4004   0   4  0 410397920   2368 -      Ss                  0 ??         0:00.22 /usr/libexec/smd
    0   300     1     4004   0  31  0 410401168   8080 -      Ss                  0 ??         0:53.46 /usr/libexec/Use
    0   302     1     4004   0  20  0 410160192   1024 -      Ss                  0 ??         0:05.09 /System/Library/
    0   303     1  1004004   0  50  0 410516816   7200 -      Ss                  0 ??         7:27.37 /System/Library/

• PRI 컬럼이 process 의 priority 우선순위를 의미

스케쥴링 큐

• PCB에 우선순위가 적혀 있다고 하지만 CPU를 사용할 다음 프로세스를 찾기 위해 운영체제가 모든 프로세스의 PCB를 순회하는건 비효율적
• 또한 새로운 프로세스들이 언제든 생길 수 있음

⇒ 스케쥴링 큐를 구현해 모든 프로세스들을 줄세워 관리
* 자료 구조 관점에서 큐는 FIFO이지만 스케쥴링 큐는 반드시 FIFO일 필요는 없음

크게 Ready queue와 Waiting queue가 있음

• Ready queue: CPU를 이용하고 싶은 프로세스들이 서는 줄
• Waiting queue: 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄
  
  

• 준비 상태에 있는 프로세스들의 PCB는 준비 큐의 마지막에 삽입 되어 CPU를 사용할 차례를 기다림
• 운영체제는 큐에 삽입된 순서대로 프로세스들을 하나씩 꺼내어 실행하되, 그 중 우선순위가 높은 프로세스를 먼저 실행

• 대기 상태에 있는 프로세스도 같은 장치를 요구한 프로세스들은 같은 대기 큐에서 기다림
• 입출력이 완료되어 완료 인터럽트가 발생하면 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾아 준비 상태로 변경한 뒤 waiting queue에서 제거하고 ready queue로 이동

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

• 선점: ‘남보다 앞서서 차지함’을 의미

선점형 스케쥴링(preemptive scheduling)

• 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케쥴링 방식
• 프로세스마다 정해진 시간만큼 CPU를 사용하고 정해진 시간을 모두 소비하여 타이머 인터럽트가 발생하면 운영체제가 해당 프로세스로부터 CPU자원을 뺏은 후 다음 프로세스에 할당하는 방식

장점 & 단점

• 장점: 더 급한 프로세스가 언제든 끼어들어 사용할 수 있고 자원을 골고루 배분할 수 있음
• 단점: context switch 과정에서 오버헤드 발생

비선점형 스케쥴링(Non-preemptive scheduling)

• 하나의 프로세스가 자원을 사용하고 있으면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지 다른 프로세스가 끼어들 수 없는 스케쥴링 방식을 의미 → 하나의 프로세스가 자원 사용을 독점

대부분의 운영체제는 선점형 스케쥴링 방식을 사용

CPU 스케쥴링 알고리즘

스케쥴링 알고리즘의 종류

선입 선처리 스케쥴링 (FCFS 스케쥴링)

• First Come First Served Scheduling 으로 단순히 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케쥴링 방식
• 공정해 보이지만 때때로 프로세스들이 기다리는 시간이 매우 길어질 수 있음

프로세스 A, B, C가 순서대로 준비 큐에 삽입된 상태

• 프로세스 C는 2ms동안 CPU에서 실행되기 위해 22ms라는 긴 시간을 기다려야 함 ⇒ convoy effect (호위효과)

convoy effect를 막기 위해서는 단순히 실행시간이 짧은 프로세스를 먼저 실행하면 됨 ⇒ 최단 작업 우선 스케쥴링

최단 작업 우선 스케쥴링 (Shortest Job First Scheduling)

• 기본적으로 비선점형 스케쥴링 알고리즘으로 분류되지만, 선점형으로 구현될 수도 있음

라운드 로빈 스케쥴링(Round robin scheduling)

• 선입 선처리 스케쥴링에 타임 슬라이스라는 개념이 더해진 스케쥴링 방식

* 타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미

• 큐에 삽입된 순서대로 프로세스들을 실행하되 정해진 시간만큼 사용
• 정해진 시간 내에 프로세스가 완료되지 못하면 다시 큐의 맨 뒤로 삽입됨

예시

• ready queue에 process A, B, C 순서로 삽입되어 있는 경우
• 타임슬라이스: 4ms
  
  

• 타임 슬라이스의 크기가 중요
  • 크면 들어온 순서대로 process를 처리하기 때문에 선입 선처리 스케쥴링과 차이가 없음
  • 작으면 context switch가 자주 발생해 CPU에 부담

최소 잔여 시간 우선 스케쥴링 (Shortest Remaining Time)

• 최단 작업 우선 스케쥴링 + 라운드 로빈 스케쥴링
• 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스는 남은 작업 시간이 가장 적은 프로세스를 선택

우선순위 스케쥴링(Priority scheduling)

• 프로세스들에 우선순위를 부여하고 높은 우선순위를 가진 프로세스부터 실행하는 스케쥴링 알고리즘
  • 우선순위가 같은 프로세스들은 선입 선처리로 스케쥴링

발생할 수 있는 문제

Starvation 현상: 우선순위가 높은 프로세스를 우선하여 처리하는 방식이기에 우선순위가 낮은 프로세스는 ready queue에 먼저 삽입되었음에도 불구하고 계속해서 실행이 연기될 수 있음

⇒ 방지하기 위한 대표적인 기법으로 에이징(aging)이 있음

• 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식

다단계 큐 스케쥴링 (multilevel queue scheduling)

• 우선순위 스케쥴링의 발전된 형태로 우선순위별로 준비 큐를 여러 개 사용하는 스케쥴링 방식
• 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어있으면 그 다음 우선순위 큐에 있는 프로세스들을 처리

• 큐별로 다양한 스케쥴링을 적용해서 효율적으로 처리 가능
• 단점은 기본적으로 프로세스가 큐 간의 이동이 안되서 우선순위가 낮은 큐에 있는 프로세스는 실행되지 않는 starvation 현상이 발생할 수 있음

다단계 피드백 큐 스케쥴링 (multilevel feedback queue scheduling)

• 큐 간의 이동이 가능한 다단계 큐 스케쥴링
• 우선순위가 가장 높은 큐에 삽입되어 프로세스가 실행되다가 타임 슬라이스 동안 실행을 다 못 끝내면

• 다음 우선순위 큐에 삽입되고, 결국 CPU를 오래 사용해야 하는 프로세스는 점차 우선순위가 낮아짐

• 즉 CPU-bound process는 자연스레 우선순위가 낮아지고, I/O Bound process는 자연스레 우선순위가 높은 큐에서 실행이 끝남
• 낮은 우선순위 큐에서 너무 오래 기다리는 프로세스는 에이징 기법을 적용해 starvation 현상을 예방할 수 있음
• 구현이 복잡하지만 CPU 스케쥴링의 가장 일반적인 알고리즘 형태로 알려짐

참고

1. 책 "혼자 공부하는 컴퓨터 구조+운영체제"
2. 유튜브 "혼자 공부하는 컴퓨터 구조 + 운영체제"

본 글은 책 "혼자 공부하는 컴퓨터 구조+운영체제" 의 Chapter 10. 프로세스와 스레드 부분을 읽고 정리한 내용입니다.

10-1. 프로세스 개요

• 실행중인 프로그램
• 실행되기 전까지는 보조기억장치에 있는 데이터 덩어리일 뿐이지만, 메모리에 적재되고 실행되는 순간 프로세스가 됨

ps 명령어로 프로세스 직접 확인하기

• ps: process status

$ ps -ef        
  UID   PID  PPID   C STIME   TTY           TIME CMD
    0     1     0   0 Tue11PM ??         3:49.05 /sbin/launchd
    0   298     1   0 Tue11PM ??         2:45.95 /usr/libexec/logd
    0   299     1   0 Tue11PM ??         0:00.11 /usr/libexec/smd
    0   300     1   0 Tue11PM ??         0:09.75 /usr/libexec/UserEventAgent (System)

• -e: 커널 프로세스를 제외한 모든 프로세스를 출력
• -f: 출력을 풀 포맷으로 표기 (유닉스 스타일) UID, PID , PPID 등이 함께 표시
  • UID: Process owner의 user id

프로세스 종류

• 포그라운드 프로세스(Foreground process): 사용자가 보는 앞에서 실행되는 프로세스
• 백그라운드 프로세스(Background process): 뒷편에서 실행되는 프로세스로 사용자와 직접 상호작용 할 수있는 백그라운드 프로세스도 있지만 묵묵히 정해진 일만 수행하는 백그라운드 프로세스도 있음
  • daemon: 유닉스 체계의 운영체제에서 부르는 백그라운드 프로세스
  • service: windows 에서 부르는 백그라운드 프로세스

프로세스 제어 블록

• 프로세스들은 차례대로 돌아가며 한정된 시간만큼만 CPU를 이용
• 시간이 끝났음을 알리는 인터럽트(타이머 인터럽트)가 발생하면 프로세스 자신의 차례를 양보하고 다음 차례가 올때까지 기다림

프로세스 제어 블록 (Process Control Block, PCB)

• 프로세스와 관련된 정보를 저장하는 자료구조 like 상품에 달린 태그 (커널 영역에 생성됨)
• 운영체제는 빠르게 번갈아 수행되는 프로세스의 실행 순서를 관리하고 CPU등의 자원을 분배하기 위해 이용
• 프로세스 생성 시에 만들어지고 실행이 끝나면 폐기됨

PCB에 담기는 정보

1. Process ID (PID)
   1. 특정 프로세스를 식별하기 위해 부여하는 고유한 번호
2. 레지스터 값
   1. 프로세스는 자신의 실행차례가 돌아오면 이전까지 사용했던 레지스터의 중간값들을 모두 복원해서 이전까지 진행했던 작업들을 그대로 이어 실행. (프로그램 카운터, 스택 포인터)
3. 프로세스 상태
   1. 입출력장치를 사용하기 위해 기다리는 상태인지, CPU 사용을 위해 기다리는 상태인지, CPU 이용중인지 등
4. CPU 스케쥴링 정보
   1. 언제, 어떤 순서로 CPU를 할당받았는지에 대한 정보
5. 메모리 관리 정보
   1. 프로세스가 어느 주소에 저장되어 있는지에 대한 정보
   2. 베이스 레지스터, 한계 레지스터 값, 페이지 테이블 정보(14장)
6. 사용한 파일과 입출력장치 목록

문맥 교환(Context Switch)

• 한 프로세스 → 다른 프로세스로 실행 순서가 넘어가면?

문맥: 하나의 프로세스 수행을 재개하기 위해 기억해야 할 정보로 PCB에 표현되어있음

⇒ 기존의 실행중인 context를 백업하고 새로운 프로세스 실행을 위해 context를 복구하는 과정

• 여러 프로세스가 끊임없이 빠르게 번갈아가며 실행되는 원리

프로세스의 메모리 영역

• 프로세스가 생성되면 커널 영역에 PCB가 생성됨
• 사용자 영역에는?
  • 코드 영역
  • 데이터 영역
  • 힙 영역
  • 스택 영역

코드 영역 (code segment)

• 텍스트 영역이라고도 부르고 기계어로 이루어진 명령어가 저장됨
• 데이터가 아닌 CPU가 실행할 명령어가 담겨 있기 때문에 쓰기가 금지됨 (read-only)

데이터 영역

• 프로그램이 실행되는 동안 유지할 데이터가 저장되는 공간
• EX) 전역 변수 (Global variable)

코드 영역과 데이터 영역은 크기가 고정된 영역이라는 점에서 정적 할당 영역이라고도 부름

• 동적 할당 영역: 힙 & 스택 영역으로 프로세스 실행 과정에서 그 크기가 변할 수 있는 영역

힙 영역 (heap segment)

• 프로그래머가 직접 할당할 수 있는 저장 공간
• 프로그래밍 과정에서 메모리 공간을 할당했다면 언젠가는 반환해야하는 공간
• 반환하지 않으면 메모리 내에 계속 남아 메모리 낭비를 초래 ⇒ memory leak

스택 영역 (Stack segment)

• 데이터를 일시적으로 저장하는 공간
• 데이터 영역에 담기는 값과 달리 잠깐 쓰다가 말 값들이 저장되는 공간 (ex) 매개변수, 지역변수)

힙 영역과 스택 영역은 실시간으로 그 크기가 변할 수 있기 때문에 동적 할당 영역이라고 부름

• 힙: 낮은 주소 → 높은 주소
• 스택: 높은 주소 → 낮은 주소

10-2. 프로세스 상태와 계층 구조

프로세스 상태

• 프로세스는 여러 상태를 거치며 실행됨

생성 상태 (new)

• 프로세스를 생성 중인 상태
• 이제 막 메모리에 적재되어 PCB를 할당받은 상태
• 생성 상태를 거쳐 실행할 준비가 완료된 프로세스는 곧바로 실행되지 않고 준비 상태가 되어 CPU 할당을 기다림

준비 상태 (ready)

• 당장이라도 CPU를 할당받아 실행할 수 있지만, 아직 차례가 아니라 기다리고 있는 상태

실행 상태 (running)

• CPU를 할당받아 실행중인 상태
• 할당된 일정 시간 동안만 CPU를 사용할 수 있음
• 할당된 시간을 모두 사용한다면(타이머 인터럽트 발생) 다시 준비 상태가 되고, 실행 도중 입출력 장치를 사용하여 입출력 장치의 작업이 끝날 때까지 기다려야 한다면 대기 상태가 됨

• 디스패치(dispatch): 준비 상태 → 실행 상태 로 프로세스가 전환되는 것

대기 상태 (blocked)

• 입출력 작업을 요청한 프로세스가 입출력장치의 작업을 기다리는 상태로 완료되면 다시 준비 상태로 CPU 할당을 기다림

종료(terminated)

• 프로세스가 종료된 상태로 운영체제는 PCB와 프로세스가 사용한 메모리를 정리

프로세스 계층 구조

• 프로세스는 실행 도중 시스템 호출을 통해 다른 프로세스를 생성할 수 있음
  • 부모 프로세스(Parent process) : 새 프로세스를 생성한 프로세스
  • 자식 프로세스(child process) : 부모 프로세스에 의해 생성된 프로세스
  • 둘은 각자 다른 PID를 가지고 일부 운영체제에서는 자식 프로세스의 PCB에 부모 프로세스의 PID인 PPID가 기록되기도 함

프로세스 생성 기법

fork: 자기 자신 프로세스의 복사본을 만드는 시스템 호출

• 부모 프로세스는 fork 시스템 호출을 통해 자신의 복사본을 자식 프로세스로 생성
• 부모 프로세스의 자원들 (메모리 내의 내용, 열린 파일 목록) 이 상속됨
  • PID값이나 저장된 메모리 위치는 다름

exec: 새로운 프로그램 내용으로 전환하여 실행하는 시스템 호출

• 메모리 공간을 새로운 프로그램으로 덮어씀
• 코드/데이터 영역의 내용이 실행할 프로그램의 내용으로 바뀌고 나머지 영역은 초기화됨

from multiprocessing import Process
import os

def foo():
    print('child process', os.getpid())
    print('my parent is', os.getppid())
  
if __name__ == '__main__':
    print('parent process', os.getpid())
    child = Process(target=foo).start()

parent process 6488
child process 27724
my parent is 6488

10-3. 스레드(Thread)

프로세스와 스레드

• 전통적인 관점에서 하나의 프로세스는 한번에 하나의 일만 처리 → 단일 스레드 프로세스

• 스레드라는 개념이 도입되면서 하나의 프로세스가 한번에 여러 일을 동시에 처리 → 멀티스레드 프로세스

• 스레드는 프로세스의 자원을 공유함
  • 실행에 필요한 최소한의 정보(프로그램 카운터를 포함한 레지스터, 스택)만을 쓰레드마다 가지며 다른 코드를 실행하고 나머지 힙/데이터 영역은 공유

멀티 프로세스와 멀티 스레드

동일한 작업을 수행하는 단일 스레드 프로세스 여러개 실행 vs 하나의 프로세스를 여러 스레드로 실행하면 어떤 차이가?

• 프로세스끼리는 기본적으로 자원을 공유하지 않음

• 쓰레드끼리는 같은 프로세스 내 자원을 공유 → 협력과 통신에 유리
  • 코드, 데이터, 힙, 파일
  • 때로는 쓰레드가 공유하는 자원에서 문제가 발생해서 다른 쓰레드들에도 영향을 미칠 수 있음쓰레드끼리는 같은 프로세스 내 자원을 공유 → 협력과 통신에 유리

import threading
import os

def foo():
    print('thread id', threading.get_native_id())
    print('process id', os.getpid())

if __name__ == '__main__':
    print('process id', os.getpid())
    thread1 = threading.Thread(target=foo).start()
    thread2 = threading.Thread(target=foo).start()
    thread3 = threading.Thread(target=foo).start()

process id 11912
thread id 20044
process id 11912
thread id 26056
process id 11912
thread id 21764
process id 11912

• thread의 id는 다르지만 모든 pid는 같음

참고

1. 책 "혼자 공부하는 컴퓨터 구조+운영체제"
2. 유튜브 "혼자 공부하는 컴퓨터 구조 + 운영체제"
 

본 글은 책 "혼자 공부하는 컴퓨터 구조+운영체제" 의 "Chapter 9. 운영체제 시작하기"을 읽고 정리한 내용입니다.

09-1 운영체제를 알아야 하는 이유

운영체제란

• 모든 프로그램은 하드웨어가 필요
  • 1+2 계산하는 프로그램은 CPU필요
  • 이미지를 하드 디스크에 저장하는 프로그램은 하드 디스크 필요
• (시스템) 자원: 프로그램 실행에 마땅히 필요한 요소들로 CPU, 메모리, 보조기억 장치 등이 있음
• 운영체제(Operating System): 실행할 프로그램에 필요한 자원을 할당하고 프로그램이 올바르게 실행되도록 돕는 특별한 프로그램
• 운영체제는 매우 특별한 프로그램이기 때문에 항상 컴퓨터가 부팅될 때 메모리 내 커널 영역(kernel space)이라는 공간에 따로 적재되어 실행됨
• 사용자 영역 (user space): 사용자가 이용하는 응용 프로그램이 적재되는 영역

위의 프로그램들은 누가 메모리에 적재했을까? → 운영체제!

응용 프로그램이 실행되려면 CPU가 필요한데 운영체제가 관리함

• 최대한 공정하게 여러 프로그램에 CPU 자원을 할당

⇒ 운영체제는 응용 프로그램과 하드웨어 사이에서 응용 프로그램에 필요한 자원을 할당하고, 응용 프로그램이 올바르게 실행되도록 관리하는 역할

결론적으로 운영체제를 알면 운영체제를 통해 하드웨어의 상태나 코드의 실행 방식을 알 수 있고 결과적으로 하드웨어와 프로그램을 더 깊이 이해할 수 있음

09-2. 운영체제의 큰 그림

운영체제의 심장, 커널

• 운영체제의 핵심 서비스를 담당하는 부분

운영체제에는 속하는데 커널에는 속하지 않는 기능은 User Interface

• GUI
• CLI

이중모드와 시스템 호출

• 사용자가 실행하는 프로그램은 자원에 직접 접근할 수 있을까? NO! 자원에 직접 접근은 위험

• 자원이 무질서하게 관리되고, 응용 프로그램이 조금만 실수해도 컴퓨터 전체에 큰 악영향을 끼칠 수 있음

• 운영체제는 응용 프로그램들이 자원에 접근하려고 할 때 오직 운영체제 자신을 통해서만 접근하도록 하여 자원을 보호

• 응용 프로그램이 자원에 접근하기 위해서 운영체제에 도움을 요청해야 함
  • 도움을 요청한다 → 운영체제 코드를 실행하려고 한다

예를 들어 응용 프로그램이 실행 과정에서 하드 디스크에 접근하여 데이터를 저장하려고 함

• 응용 프로그램이 운영체제에 도움 요청
• 운영체제는 커널 영역 내의 하드 디스크에 데이터를 저장하는 코드를 실행하여 응용 프로그램 대신 작업을 수행

• 이중 모드(Dual model) : CPU가 명령어를 실행하는 모드를 크게 사용자 모드와 커널 모드로 구분하는 방식
  • 사용자모드 : 운영체제 서비스를 제공받을 수 없는 실행 모드 (자원 접근 불가)
  • 커널 모드 : 운영 체제 서비스를 제공받을 수 있는 실행 모드

이중 모드는 플래그 레지스터 내의 슈퍼바이저 플래그에 의해 결정됨

• 응용 프로그램이 운영체제에게 시스템 호출(System call)을 통해 사용자 모드 → 커널 모드로 전환됨
• 일종의 소프트웨어 인터럽트

하드웨어 인터럽트 처리 방식과 유사

1. 시스템 호출을 발생시키는 명령어가 실행되면 CPU는 지금까지의 작업을 백업
2. 커널 영역 내에 시스템 호출을 수행하는 코드(인터럽트 서비스 루틴)을 실행
3. 다시 기존에 실행하던 응용 프로그램으로 복귀하여 실행

일반적으로 응용 프로그램은 실행 과정에서 운영체제 서비스들을 매우 빈번하게 사용

운영체제의 핵심 서비스

크게 3가지

• 프로세스 관리, 자원 접근 및 할당, 파일 시스템 관리

프로세스 관리

• 프로세스 : 실행중인 프로그램
• 일반적으로 하나의 CPU는 한번에 하나의 프로세스만 실행할 수 있기에 CPU는 이 프로세스들을 조금씩 시간을 나눠 번갈아 가며 실행

• 각 프로세스의 상태와 사용하고자 하는 자원도 다양 → 운영체제는 다양한 프로세스를 일목요연하게 관리하고 실행할 수 있어야 함

자원 접근 및 할당

CPU

• 메모리에 여러 프로세스가 적재되고, 하나의 CPU는 한 번에 하나의 프로세스만 실행
• 어떤 프로세스부터 CPU를 이용하게 할지, 얼마나 오래 사용할지 결정해야 함 ⇒ CPU 스케쥴링 (11장)

메모리

• 메모리에 적재된 프로세스들의 크기와 주소도 가지각색이라 운영체제가 어떻게 메모리를 할당하지, 메모리가 부족한 경우에는 어떻게 극복하는지 운영체제가 판단

입출력장치

• 인터럽트 서비스 루틴은 운영체제가 제공하는 기능으로 커널 영역에 있고 하드웨어 인터럽트도 마찬가지
• 입출력장치가 cpu에 하드웨어 인터럽트 요청 신호를 보내면 CPU는 하던 일을 잠시 백업한 뒤 커널 영역에 있는 인터럽트 서비스 루틴을 실행

파일 시스템 관리

• 파일 시스템도 운영체제가 지원하는 핵심 서비스 (15장)

참고

• system call 확인하기위해 linux에서는 strace 명령어 사용

$ strace /bin/ls                                                                                                                                                                                          ok | wschoi@superb-tony | 03:58:16 PM
execve("/bin/ls", ["/bin/ls"], 0x7ffd7c910c40 /* 40 vars */) = 0
brk(NULL)                               = 0x559534620000
arch_prctl(0x3001 /* ARCH_??? */, 0x7ffe470196c0) = -1 EINVAL (Invalid argument)
access("/etc/ld.so.preload", R_OK)      = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=101547, ...}) = 0
mmap(NULL, 101547, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7f8e83bfb000
close(3)                                = 0
openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libselinux.so.1", O_RDONLY|O_CLOEXEC) = 3
read(3, "\\177ELF\\2\\1\\1\\0\\0\\0\\0\\0\\0\\0\\0\\0\\3\\0>\\0\\1\\0\\0\\0@p\\0\\0\\0\\0\\0\\0"..., 832) = 832
fstat(3, {st_mode=S_IFREG|0644, st_size=163200, ...}) = 0
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f8e83bf9000
mmap(NULL, 174600, PROT_READ, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7f8e83bce000
mprotect(0x7f8e83bd4000, 135168, PROT_NONE) = 0
mmap(0x7f8e83bd4000, 102400, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x6000) = 0x7f8e83bd4000
mmap(0x7f8e83bed000, 28672, PROT_READ, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1f000) = 0x7f8e83bed000
mmap(0x7f8e83bf5000, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x26000) = 0x7f8e83bf5000
mmap(0x7f8e83bf7000, 6664, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x7f8e83bf7000
close(3)                                = 0

참고

1. 책 "혼자 공부하는 컴퓨터 구조+운영체제"
2. 유튜브 "혼자 공부하는 컴퓨터 구조 + 운영체제"
 

본 글은 책 "혼자 공부하는 컴퓨터 구조+운영체제" 의 Chapter 6-3. 캐시메모리 부분을 읽고 정리한 내용입니다.

06-3 캐시 메모리

• CPU가 메모리에 접근하는 시간은 CPU의 연산속도보다 느림
• 이를 극복하기 위한 저장 장치로 캐시 메모리가 쓰임

저장 장치 계층 구조(Memory hierarchy)

• ‘CPU에 얼마나 가까운가’를 기준으로 계층적으로 나타낼 수 있음

캐시 메모리(Cache memory)

• CPU와 메모리 사이에 위치
• 레지스터보다 용량이 크고 메모리보다 빠른 S(static)RAM 기반의 저장 장치

캐시 메모리에 CPU가 필요로 하는 데이터가 있다면 데이터로의 접근 시간을 줄일 수 있음

• L(Level)1 캐시: 코어와 가장 가까운 캐시 메모리
• L2 캐시
• L3 캐시

L1과 L2 캐시는 코어 내부에, L3 캐시는 코어 외부에 위치

• CPU가 메모리 내에 데이터가 필요하다고 판단하면 우선 L1 캐시에서 데이터를 검색
• 없다면 L2, L3 를 순차적으로 검색

• 멀티코어 프로세서에서는 L1,L2 캐시는 코어마다 고유한 캐시 메모리로 할당
• L3 캐시는 여러 코어가 공유하는 형태로 사용

참조 지역성 원리

• 캐시 메모리에는 무엇을 저장해야 할까?

⇒ CPU가 사용할 법한 대상을 예측하여 저장

• Cache hit: 자주 사용될 것으로 예측한 데이터가 실제로 들어맞아 캐시 메모리 내 데이터가 CPU에서 활용되는 경우를 뜻함
• Cache miss: 예측이 틀려 메모리에서 필요한 데이터를 직접 가져와야 하는 경우로 자주 발생하는 성능이 떨어짐
• 캐시 적중률(Cache hit ratio) = # Cache hit / (# Cache hit + # Cache miss)
  • 우리가 사용하는 컴퓨터의 캐시 적중률은 대략 85~95% 이상

어떻게 캐시 적중률을 높일 수 있을까?

• 캐시 메모리는 한가지 원칙에 따라 메모리로부터 가져올 데이터를 결정

 
참조 지역성의 원리(locality of reference, principle of locality)

1. CPU는 최근에 접근했던 메모리 공간에 다시 접근하려는 경향이 있다 → 시간 지역성

• 변수는 num, i
• 반복사용되는 변수들을 캐시에 저장하면 효율성 높일 수 있음

2. CPU는 접근한 메모리 공간 근처를 접근하려는 경향이 있다 → 공간 지역성

• 기억장치 내에 서로 인접하여 저장되어 있는 데이터들이 연속적으로 액세스 될 가능성이 높아지는 특성
• 예를 들어 워드 프로세서 프로그램의 자동 저장 기능에 대한 데이터가 사용되었다면, 해당 공간 근처에 있는 기능들에 대한 메모리 공간을 캐시에 저장하면 효율성을 높일 수 있음

참고

1. 책 "혼자 공부하는 컴퓨터 구조+운영체제"
2. 유튜브 "혼자 공부하는 컴퓨터 구조 + 운영체제"
 

본 글은 책 "혼자 공부하는 컴퓨터 구조+운영체제" 의 Chapter 6를 읽고 정리한 내용입니다.

06-1 RAM의 특징과 종류

RAM의 특징

• 실행할 프로그램의 명령어와 데이터가 저장되는 곳
• 전원을 끄면 저장된 명령어와 데이터가 모두 날아감 → 휘발성 저장 장치(volatile memory)

• 비휘발성 저장장치(non-volatile memory): 전원이 꺼져도 저장된 내용이 유지되는 저장 장치로하드디스크, SSD, USB 메모리 등과 같은 보조기억장치가 있음

• 보조기억장치는 전원을 꺼도 내용을 유지하지만 CPU가 직접 접근하지 못함

⇒ 보조기억장치에는 보관할 대상을 저장하고 RAM에는 실행할 대상을 저장

RAM의 용량과 성능

• CPU가 실행하고 싶은 프로그램이 보조기억장치에 있다면 이를 RAM으로 가져와야 함
• RAM의 용량이 적다면 보조기억장치에서 RAM으로 실행할 프로그램을 가져오는 일이 잦아 실행 시간이 길어짐

RAM의 종류

DRAM

• Dynamic RAM
• 저장된 데이터가 동적으로 변하는(사라지는) RAM을 의미
  • 시간이 지나면 저장된 데이터가 점차 사라지는 RAM으로 데이터의 소멸을 막기 위해 일정 주기로 데이터를 재활성화(다시 저장) 해야 함
• 위 단점에도 불구하고 아래 장점들 때문에 가장 많이 쓰임
  • 소비 전력이 비교적 낮음
  • 저렴
  • 집적도가 높아 대용량 설계 용이 (더 작고 빽빽하게 만들 수 있다는 의미)

SRAM

• Static RAM
• 저장된 데이터가 변하지 않는 RAM으로 일반적으로 DRAM보다 빠름
• 대용량으로 만들어질 필요는 없지만 속도가 빨라야하는 곳에 쓰임 (ex) 캐시 메모리)

SDRAM

• Synchronous Dynamic RAM
• 클럭 신호와 동기화된 발전된 형태의 DRAM
  • 클럭에 맞춰 동작하며 클럭마다 CPU와 정보를 주고받을 수 있는 DRAM

DDR SDRAM

• Double Data Rate SDRAM 으로 최근 가장 흔히 사용됨
• 대역폭을 넓혀 속도를 빠르게 만든 SDRAM

* 대역폭(Data rate): 데이터를 주고받는 길의 너비

• DDR2 SDRAM은 DDR SDRAM보다 대역폭이 두 배 넓은 SDRAM (SDR SDRAM 보다 4배 넓음)
• DDR3 SDRAM : DDR2 SDRAM보다 대역폭이 2배 넓음 (SDR SDRAM보다 8배)
• DDR4 SDRAM : DDR3 SDRAM보다 대역폭이 2배 넓음 (SDR SDRAM보다 16배)

06-2 메모리의 주소 공간

메모리에 저장된 정보의 위치를 나타내는 주소는 두 종류가 있음

• 물리주소: 메모리 하드웨어가 사용하는 주소
• 논리주소: CPU와 실행중인 프로그램이 사용하는 주소

물리주소와 논리주소

• CPU가 이해하는 주소가 논리 주소라고는 해도 CPU가 메모리와 상호작용하려면 논리주소와 물리주소 간의 변환의 이루어져야 함
  • 아래 그림에서 인터넷 브라우저의 0번지와 게임의 0번지는 CPU가 이해하기는 다르지만 실제 물리주소로 변환되지 않으면 메모리가 이해할 수 없음

⇒ CPU와 주소 버스 사이에 위치한 메모리 관리 장치(MMU, Memory Management Unit)라는 하드웨어에 의해 논리주소 ↔ 물리주소 변환이 수행됨

MMU는 CPU가 발생시킨 논리 주소에 베이스 레지스터(프로그램의 기준 주소) 값을 더하여 논리주소→물리주소로 변환

• 베이스 레지스터: 프로그램의 가장 작은 물리 주소로 프로그램의 첫 물리 주소를 저장하는 셈

• CPU가 "프로그램 A의 100번지 데이터"를 삭제하라고 명령하면, MMU를 통해 베이스 레지스터 값을 찾고 논리주소 값을 더해 실제 물리 주소 값을 얻은 다음 메모리에 접근하여 데이터 삭제

• CPU가 "프로그램 C의 100번지 데이터"를 삭제하라고 명령하면, MMU를 통해 해당 프로그램의 베이스 레지스터 값을 찾고 논리 주소 값을 더해 실제 물리주소 값을 얻은 다음, 메모리에 접근하여 데이터 삭제

메모리 보호 기법

• 아래 CPU의 명령어는 안전할까?

• 안전하지 않고 실행되어서는 안됨
• 프로그램의 논리 주소 영역을 벗어났기 때문
• 위 명령어가 실행된다면 메모장 프로그램은 애꿏은 인터넷 브라우저 프로그램에 숫자 100을 저장

• 인터넷 브라우저 프로그램의 명령어가 자신과 전혀 관련없는 게임 프로그램 정보를 삭제하게 됨
• 다른 프로그램의 영역을 침범할 수 있는 명령어는 위험하기 때문에 논리 주소 범위를 벗어나는 명령어 실행을 방지하고 실행중인 프로그램이 다른 프로그램에 영향을 받지 않도록 보호할 방법이 필요

⇒ 한계 레지스터 (limit register)

• 베이스 레지스터가 실행중인 프로그램의 가장 작은 물리 주소를 저장한다면, 한계 레지스터는 논리 주소의 최대 크기를 저장
  • 베이스 레지스터 값 ≤ 프로그램의 물리 주소 범위 < 베이스 레지스터 값 + 한계 레지스터 값

CPU가 접근하려는 논리 주소는 한계 레지스터가 저장한 값보다 커서는 안됨

• 프로그램 A의 크기, 즉 한계 레지스터가 150인 상황
• CPU가 200번지를 삭제하라는 명령어를 보내면 논리 주소가 한계 레지스터 값보다 커 실행될 수 없음

⇒ CPU는 메모리에 접근하기 전에 접근하고자 하는 논리 주소가 한계 레지스터보다 작은지를 항상 검사

참고

1. 책 "혼자 공부하는 컴퓨터 구조+운영체제"
2. 유튜브 "혼자 공부하는 컴퓨터 구조 + 운영체제"

본 글은 책 "혼자 공부하는 컴퓨터 구조+운영체제" 의 Chapter 5를 읽고 정리한 내용입니다.

05-1 빠른 CPU를 위한 설계 기법

클럭(Clock)

• 컴퓨터 부품들은 ‘클럭 신호’에 맞춰 움직이는데 실제로 클럭 속도가 높은 CPU는 일반적으로 성능이 좋음
• 단위: Hz 로 초당 반복되는 클럭 수
  • 실제 CPU 클럭 속도 표현 예시: Base 2.5GHz, Max 4.9GHz 등으로 표시되어있음
  • 의미: 초당 25억번, 순간적으로 최대 49억번 반복된다는 의미

오버클럭킹(Overclocking) : 최대 클럭 속도를 강제로 끌어올리는 기법

Q. 클럭 속도를 무지막지하게 높이면 무조건 CPU가 빨라질까?
A. 발열 문제가 심해지고,클럭 속도만으로 cpu의 성능을 올리는 것에는 한계가 있음

코어와 멀티코어

코어란?

• 명령어를 실행하는 부품으로, CPU가 기술적으로 많은 발전을 거듭하면서 단순히 “명령어를 실행하는 부품” → “명령어를 실행하는 부품을 여러 개 포함하는 부품”으로 확장됨

• 코어를 여러개 포함하고 있는 CPU를 멀티코어 CPU 또는 멀티코어 프로세서라고 부름
• 코어의 개수가 연산 처리 속도와 연관이 있지만 코어마다 처리할 명령어들을 얼마나 적절하게 분배하느냐에 따라 연산 속도가 크게 달라짐

스레드와 멀티스레드

• 스레드: “실행 흐름의 단위”라는 사전적 의미를 가지고 2가지로 나뉨
  • 하드웨어적 스레드
  • 소프트웨어적 스레드

하드웨어적 스레드

• 하나의 코어가 동시에 처리하는 명령어 단위
• 여러 스레드를 지원하는 CPU는 하나의 코어로도 여러 개의 명령어를 동시에 실행할 수 있음
  • 2코어 4스레드 CPU: 아래 그림처럼 명령어를 실행하는 부품 2개, 한번에 4개의 명령어를 처리할 수 있는 CPU를 의미 (멀티스레드 프로세서, 멀티스레드 CPU)

*하이퍼스레딩: 인텔의 멀티스레드 기술을 의미

소프트웨어적 스레드

• 하나의 프로그램에서 독립적으로 실행하는 단위
• 아래의 기능들을 동시에 수행되길 원할 때 각각의 스레드로 만들어 동시 실행할 수 있음

멀티스레드 프로세서

• 하나의 코어로 여러 명령어를 동시에 처리하도록 만들려면 프로그램 카운터, 스택 포인터, 메모리 버퍼 레지스터, 메모리 주소 레지스터와 같이 하나의 명령어를 처리하기 위해 꼭 필요한 레지스터를 여러개 가지고 있으면 됨

• 레지스터세트: 하나의 명령어를 실행하기 위해 꼭 필요한 레지스터들을 편의상 부르기 위한 세트
• 레지스터 세트가 2개인 CPU는 두 개의 명령어를 처리하기 위한 정보들을 기억할 수 있음

• 하드웨어 스레드를 이용해 하나의 코어로도 여러 명령어를 동시에 처리할 수 있다고 했음
• 그러나 메모리 속 프로그램 입장에서는 하드웨어 스레드는 마치 ‘한번에 하나의 명령어를 처리하는 CPU’나 다름 없음 ⇒ 하드웨어 스레드를 논리 프로세서(logical processor)라고 부르기도 함

05-2 명령어 병렬처리 기법

• 빠른 CPU를 만들려면 높은 클럭 속도, 멀티코어, 멀티 쓰레드를 지원하는 CPU를 만드는 것도 중요하지만 CPU가 놀지 않고 시간을 알뜰하게 쓰며 작동하게 만드는 것도 중요

명령어 병렬 처리 기법(ILP: Instruction-Level Parallelism)

• 명령어를 동시에 처리하여 CPU를 한시도 쉬지 않고 작동시키는 기법
  • 명령어 파이프 라이닝
  • 슈퍼스칼라
  • 비순차적 명령어 처리

명령어 파이프라인

하나의 명령어가 처리되는 전체 과정을 클럭 단위로 나누면

1. 명령어 인출 (Instruction Fetch)
2. 명령어 해석 (Instruction Decode)
3. 명령어 실행 (Execute Instruction)
4. 결과 저장 (Write Back)

같은 단계가 겹치지만 않는다면 CPU는 ‘각 단계를 동시에 실행할 수 있다’
⇒ 명령어 파이프라인에 넣고 동시에 처리하는 기법을 명령어 파이프라이닝이라고 함

명령어 파이프라인을 사용하지 않고 모든 명령어를 순차적으로만 처리하면 아래와 같이 비효율적으로 처리됨

파이프라이닝이 높은 성능을 가져오기는 하지만, 성능 향상에 실패하는 경우도 있음 → 파이프라인 위험

파이프라인 위험 3가지 종류

• 데이터 위험 (Data hazard)
• 제어 위험 (Control hazard)
• 구조적 위험

데이터 위험

• 명령어 간의 의존성때문에 발생하는 위험
• 모든 명령어를 동시에 처리할 수 없는 경우도 있기 때문

명령어 1: R1 <- R2 + R3
명령어 2: R4 <- R1 + R5 

명령어 1을 실행 후에 명령어 2에서 명령어 1의 결과를 인출해야 하기때문에 병렬적으로 처리할 수 없음

제어 위험

• 기본적으로 프로그램 카운터는 ‘현재 실행 중인 명령어의 다음 주소’로 갱신됨
• 분기 등으로 인한 프로그램 카운터의 갑작스러운 변화가 생기면 명령어 파이프라인에 가지고 와서 처리 중(ex) 인출, 해석)이던 명령어들이 쓸모 없어짐

⇒ 분기 예측을 통해 프로그램이 어디로 분기할지 미리 예측한 후 그 주소를 인출하는 기술을 사용

구조적 위험

• 명령어들을 겹쳐 실행하는 과정에서 서로 다른 명령어가 동시에 ALU, 레지스터 등과 같은 CPU 부품을 사용하려고 할 때 발생 ⇒ 자원 위험이라고도 부름

슈퍼스칼라

• 여러개의 파이프라인을 이용해서 한번에 두가지의 명령어를 인출/해석/실행/저장

• 이론적으로는 파이프라인 개수에 비례하여 처리속도 증가, but 파이프라인 위험도 증가하기 때문에 고도로 설계 되어야 함

비순차적 명령어 처리

• OoOE: Out-of-order execution

• M(N): N 번지의 메모리
• M(N) ← 100: N 번지에 100을 저장

3번째 명령어 (M(102) <- M(100) + M(101)) 에서 1, 2번째 명령어의 결과가 필요하기 때문에 이상적인 성능 향상을 이끌 수 없음

여기서 의존성이 없는 명령어의 순서를 바꿔본다면?

• 순차적으로 명령어를 처리할 때 보다 더 효율적으로 처리될 수 있고 이렇게 명령어 파이프라인을 멈추는 것을 방지하는 기법을 비순차적 명령어 처리 기법이라고 함

* 물론 아무 명령어나 순서를 바꿔서 수행할 수는 없고 최적화 필요

05-3 CISC 와 RISC

• CPU 성능을 향상시키기 위해서 명령어 파이프라이닝, 슈퍼 스칼라 기법등을 적용하기 위해서는 명령어가 파이프라이닝 하기 쉽게 생겨야 함

CPU는 명령어를 실행한다 ⇒ 모든 CPU가 똑같이 생긴 명령어를 실행할까? NO!

명령어의 세세한 생김새, 연산, 주소 지정 방식은 CPU마다 다름

명령어 집합 (Instruction set, Instruction set architecture, ISA)

• CPU가 이해할 수 있는 명령어들의 모음
• 인텔의 CPU가 이해할 수 있는 명령어 집합과 아이폰의 CPU가 이해할 수 있는 명령어 집합은 다름

명령어 병렬 처리 기법들을 도입하기 유리한 ISA는 크게 2가지가 있음

• CISC
• RISC

CISC

• Complex Instruction Set Computer
• 복잡한 명령어 집합을 활용하는 컴퓨터(CPU)
• Intel, AMD 기반 cpu (x64, x86-64)

• 복잡하고 다양한 명령어 활용
• 명령어의 형태와 크기가 다양한 가변 길이 명령어 활용

• 상대적으로 적은 수의 명령어로도 프로그램을 실행할 수 있음 ⇒메모리를 최대한 아끼며 개발해야했던 시절에 인기가 높았음
• 명령어 파이프라이닝이 불리하다는 치명적인 단점이 있음
  • 명령어가 워낙 복잡하고 다양한 기능을 제공해 명령어의 크기와 실행되기까지의 시간이 일정하지 않음
  • 명령어 실행하는데 여러 클럭 주기 필요

⇒ CISC 명령어 집합은 복잡하고 다양한 기능을 제공하기에 적은 수의 명령어로 프로그램을 동작시키고 메모리를 절약할 수 있지만, 명령어의 규격화가 어려워 파이프라이닝이 어려움

RISC

• Reduced Instruction Set Computer
• 명령어의 종류가 적고, 짧고 규격화된 명령어 사용 (되도록 1클럭 내외로 실행되는 명령어를 지향) ⇒ 고정 길이 명령어 사용
• 메모리에 직접 접근 명령어를 load, store 두개로 제한할 만큼 메모리 접근을 단순화 및 최소화
  • 레지스터를 십분 활용 → 범용 레지스터 수가 더 많음
• 다만 명령어 종류가 CISC 보다 적기에 더 많은 명령어로 프로그램을 동작시킴

참고

1. 책 "혼자 공부하는 컴퓨터 구조+운영체제"
2. 유튜브 "혼자 공부하는 컴퓨터 구조 + 운영체제"