24.03.22 운영체제, KEYWORD

운영체제

24 세마포어

24.1 세마포어 : 정의

• 세마포어는 정수 값을 갖는 객체로서 두 개의 루틴으로 조작할 수 있다. POSIX 표준에서 이 두 개의 루틴은 sem_wait()와 sem_post()이다. 세마는 초기 값에 의해 동작이 결정되기 때문에, 사용하기 전 제일 먼저 값을 초기화 해야한다.
• 같은 프로세스 내의 쓰레드 간에 세마포어를 공유한다. 두 루틴들은 동시에 다수 쓰레드들에 의해 호출될 수 있다. 임계영역이 적절히 보호되어야 한다. 임계영역 보호를 위해 사용할 함수내에서 임계영역 보호문제가 존재한다.
• sem_wait() 함수는 세마포어 값이 1 이상이면 즉시 리턴하거나, 해당 세마포어 값이 1 이상이 될 때까지 호출자를 대기시킨다. 다수의 쓰레드들이 sem_wait()을 호출 할 수 있기 때문에, 대기 큐에는 다수의 쓰레드가 존재할 수 있다. 대기하는 법에는 회전과 재우기 두 가지가 있다는 것을 상기하자
• sema_post()함수는 대기하지 않는다. 세마포어 값을 증가시키고 대기 중인 쓰레드 중 하나를 깨운다.
• 세마포어가 음수라면 그 값은 현재 대기중인 쓰레드의 개수와 같다. 일반적으로 사용자는 이 값을 알 수 없다.

24.2 이진 세마포어(락)

• 락은 두 개의 상태(사용 가능, 사용 중)만 존재하므로 이진 세마포어 라고도 불린다.

24.3 순서보장을 위한 세마포어

• 세마포어는 병행 프로그램에서 일어나는 사건들의 순서를 정하는 데에도 유용하다. 예를 들어, 리스트에서 객체를 삭제하기 위해 리스트에 객체가 추가되기를 대기하는 쓰레드가 있을 수 있다. 이러한 사용 패턴을 보면 하나의 쓰레드가 사건의 발생을 기다리고, 또 다른 쓰레드는 해당 사건을 발생시킨 후, 시그널을 보내어 기다리는 쓰레드를 깨운다.

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

• empty와 full이라는 두 개의 세마포어를 사용한다. 쓰레드는 empty를 사용하여 가용 버퍼 공간이 있는지, full을 사용하여 읽은 내용이 있는지 여부를 표시한다.
• 생산자와 소비자 쓰레드가 각 하나씩 있고 CPU도 하나인 상황에 대해 살펴보자. 소비자 쓰레드가 먼저 실행되었다 가정하자. 소비자 쓰레드가 변수 값은 0으로 초기화 되었기 때문에 해당 명령으로 인해 full의 값은 -1로 감소되고, 소비자 쓰레드는 대기 모드가 된다. 누군가가 full값을 증가시키기를 기다려야 한다.

24.5 Reader - Writer 락

• 다수의 쓰레드가 연결 리스트에 노드를 삽입하고 검색을 하는 상황을 가정해보자. 삽입 연산은 리스트를 변경한다. 검색은 리스트를 변경하지 않고 단순히 읽기만 한다. 삽입 연산이 없다는 보장만 된다면 다수의 검색 작업을 동시에 수행할 수 있다. 이와 같은 경우를 위해 만들어진 락이 Reader - Writer락이다.
• 자료구조를 갱신하려면 배타적 접근 권한을 갖는 락을 사용한다. 내부적으로는 write lock 세마포어를 사용하여 하나의 쓰기 쓰레드만이 락을 획득 할 수 있도록 하여, 임계영역 진입 후에 자료 구조를 갱신한다.
• 읽기 락(reader lock)은 동시에 여러 쓰레드가 락을 보유 할 수 있다. 읽기 락을 획득시 읽기 쓰레드가 먼저 락을 획득하고 읽기 중인 쓰레드 수를 표현하는 reader의 값을 증가시킨다. 첫 번째 읽기 쓰레드가 읽기 락을 획득할 때 중요한 과정이 있다. 읽기 락 획득시 write lock 세마포어에 대해 sem_wait()을 호출하여 쓰기 락을 함께 획득한다. 획득한 쓰기 락은 읽기 락을 해제할 때, sem_post()로 다시 해제한다.
• 이 과정을 통해서 읽기 락을 획득하고 난 후, 다른 읽기 쓰레드들이 읽기 락을 획득할 수 있도록 한다. 다만, 쓰기 락을 획득하려는 쓰기 쓰레드들은 모든 읽기 쓰레드가 끝날 때까지 대기해야 한다.
• 이 방식은 공정성에 문제가 있다. 상대적으로 쓰기 쓰레드가 불리하다. 쓰기 쓰레드에게 기아 현상이 발생하기 쉽다.

24.6 쓰레드 제어

• 과도하게 많은 쓰레드가 동시에 수행되면 시스템 효율이 매우 나빠진다. 이런경우 프로그래머는 과도하게 많은에 대한 임계값을 정하고, 세마포어를 사용하여 문제가 되는 코드를 동시에 실행하는 쓰레드 개수를 제한한다. 우리는 이 접근법을 제어(throttling)라고 부르며 수락제어의 한 형태로 간주한다.

KEYWORD

Virtual Memory

• 운영체제는 메모리가 실제 메모리보다 많아 보이게 하는 기술인 가상 메모리를 제공한다.
• 가상 메모리는 시스템이 프로그램을 실행시키는데 최소한 얼마만큼의 메모리가 필요한가에 대한 접근 방식으로, 실행에 필요한 일부분만 메모리에 로드하고 나머지는 디스크에 두고서 필요할 때마다 교체하면서 쓰는 방식으로 구현된다.

Demand Paging

• 현재 필요한(요구되어지는) 페이지만 메모리에 올리는 것을 Demanding Paging(요구 페이징)이라고 한다.
• CPU 이용률과 처리율이 높아지고, 더 많은 사용자를 수요할 수 있다.
• Page table에서 해당 page가 메모리에 있는지를 나타내는 valid-invalid bit를 사용한다. bit가 invalid인 경우 페이지가 물리적 메모리에 없다는 것이다.
• 따라서 처음에는 모든 page entry가 invalid로 초기화되어있고, 주소 변환 시 bit가 invalid로 되어있다면 page fault라는 오류가 발생한다.

Page Table

Paging

• address space를 연속적으로 할당하지 말고, 페이지라는 단위로 쪼개서 사용하는 것이다.
• 먼저, 프로세스의 메모리를 page 단위로 자르고, 실제 physical 메모리도 page 단위로 쪼갠다. 이 때 쪼개진 physical memory를 page나 page frame이라고 부른다. 그리고 이 virtual address의 page를 physical memory의 frame으로 mapping하는 방법이다.

Page Table

• VPN(Virtual Page Number)를 PFN(Physical Frame Number)로 매핑해주는 table
• 각각의 프로세스는 자신만의 page table을 독립적으로 가지고 있으며, 각 프로세스의 page table이 저장되어 있는 주소를 page table register가 저장하고 있다.
• page table은 OS로부터 관리되고, MMU가 접근해서 읽는다. 이 때, 각 page table의 원소 하나하나를 page table entry(pte)라고 한다.
• page table은 메인 메모리에 존재해서 메인 메모리에 최소 2번은 접근해야 원하는 데이터를 얻을 수 있다.
  1. 페이지 테이블에 접근
  2. 페이지 테이블을 기반으로 실제 메모리에 접근
  • 이를 줄이기 위해서 TLB를 사용한다.

TLB(Translation Lookaside Buffer)

• 가상 메모리 주소를 물리적인 주소로 변환하는 속도를 높이기 위해 사용되는 캐시이다.
• 최근에 일어난 가상 메모리 주소와 물리 주소의 변환 테이블을 저장한다.
• CPU가 가상 주소로 메모리에 접근하려고 할 대, 우선 TLB에 접근하여 가상 주소에 해당되는 물리 주소를 찾고 TLB에 매핑이 존재하지 않으면 MMU가 페이지 테이블에서 해당되는 물리 주소로 변환한 후 메모리에 접근한다.
• 프로세스가 바뀔 경우, TLB를 모두 flush 해줘야 한다는 문제가 있다.

Page Fault

• CPU가 접근하려는 페이지가 메모리에 없는 경우이다. 즉, 페이지 테이블의 valid bit 값이 0인 경우이다.
• 페이지 폴트가 발생하면 운영체제는 그 데이터를 메모리로 가져와서 마치 페이지 폴트가 전혀 발생하지 않은것처럼 프로그램이 계속적으로 작동하게 해준다.

동작

1. page table을 통해 필요한 page가 없다면 (invalid) 즉, page fault
2. 운영체제에 page fault trap을 발생시킨다.
   1. 동작하고 있던 프로세스의 PCB를 메모리에 저장한다.
3. 운영체제는 다른 page table을 확인한다. 그리고 뭔가 이상하다면 프로세스를 중지시키고 그냥 메모리에 없는 것이라면 backing store에서 찾는다.
4. 필요한 페이지를 찾아서 물리 메모리에서 빈 frame을 찾는다. 빈 frame이 없다면 교체 알고리즘으로 page in, page out을 수행한다. 이때 프로그램은 wait queue에 들어가서 대기한다.
   1. free frame을 찾고 있을 때 CPU는 다른 프로그램에게 할당된다.
   2. 찾았다면 CPU를 사용하고 있던 프로그램의 PCB를 저장하고 page fault를 발생시킨 프로그램의 PCB를 가져온다.
5. 그리고 물리 메모리에 올리면, page table을 update한다. 즉, valid bit를 수정한다.
6. page fault를 발생시킨 코드를 다시 시작한다.

Lazy Loading

• 프로그램이 실제로 해당 데이터를 필요로 할 때까지 데이터의 로딩을 지연시키는 기법이다. 이는 주로 메모리 관리에 사용되며, 프로그램이 시작할 때 필요한 모든 데이터를 메모리에 즉시 로드하지 않고, 필요한 순간에만 해당 부분을 로드한다.
• 메모리 사용의 효율성을 높이고 시스템의 전반적인 성능을 개선한다. 메모리는 한정된 자원이므로, 모든 데이터를 미리 로드하면 불필요한 메모리 사용으로 이어질 수 있다.

Lazy Loading의 작동 방식

1. Demand Paging : 프로세스가 페이지에 접근하려 할 때마다 해당 페이지가 메모리에 없으면 페이지 폴트가 발생한다. 이후 운영체제는 필요한 페이지를 디스크에서 메모리로 로드한다.
2. 리소스 사용 최적화 : 프로세스가 실제로 사용하지 않는 페이지는 메모리에 로드되지 않는다, 이는 시스템 리소스의 낭비를 줄이고, 사용 가능한 메모리를 효율적으로 사용할 수 있게 한다.

장점

• 메모리 사용 최적화
• 초기 로딩 시간 감소
• 시스템 자원의 효율적 사용

단점

• 페이지 폴트 발생 시 성능 저하 가능성
• 관리가 복잡해 질 수 있다.

Page Replacement Policy

• evict할 페이지를 고르는 여러가지 알고리즘

OPT(Belady’s Algorithm)

• 앞으로 가장 오랫동안 사용되지 않을 페이지를 빼는 알고리즘
• page fault가 나면, 가장 나중에 참조될 페이지를 빼는 방식이다. 대신 이 방식은 어느 페이지가 참조될 지 알아야 한다는 단점이 있다. 대부분의 현실 컴퓨팅의 경우 미래에 어느 페이지가 참조될 지 아는 것은 불가능하다. 따라서 belady’s algorithm은 다른 알고리즘의 효율성을 따지는 평가기준으로 많이 쓰인다.

FIFO

• 가장 먼저 들어온 페이지를 가장 먼저 빼는 알고리즘
• 가장 직관적이고 일반적인 방법이다. 하지만 이 알고리즘에는 치명적인 문제점이 있는데, 이를 belady’s anomaly라고 부른다.
• belady’s anomaly란, page frame이 커졌지만, page fault rate가 증가하는 문제이다. 즉, 메모리를 하나 더 쓰느라 돈을 쓰고도 컴퓨터 성능이 떨어지는 것을 의미한다.

LRU(Least Recenty Used)

• 가장 과거에 참조된 페이지를 빼는 알고리즘
• OPT 방식에서 변형된 것으로, 우리가 미래를 보고 판단할 수 없으니, 과거를 보고 미래를 예측하는 것이다.
• 만약, n개의 page frame을 가지고 있을 때, page frame이 1,2,3,4, …n 라는 페이지를 포함한다고 하자. 이 때, n+1개의 page frame으로 늘어나도 page frame이 1,2,3,4,…n을 무조건 포함하고 있는 경우를 stack algorithm이라고 한다.
• LRU Algorithm은 stack algorithm의 한 예시이다. 따라서 LRU는 belady’s anomaly를 겪지 않는다.
• LRU를 구현하는 방식은 크게 두 가지가 있다.
  • doubly linked list
    • 페이지들을 linked list 형식으로 구현하여 관리하는 방식이다.
    • 이 방식은 evict 할 때, tail을 자르면 되므로, evict 하기 빠르다는 장점이 있지만, linked lsit를 매번 업데이트 해줘야 하므로, 페이즈를 참조할때는 느리다는 단점이 있다.
  • clock or counters
    • 각 page frame마다 시간을 기록할 수 있는 변수를 두고, 페이지가 참조될 때마다 clock을 업데이트 해주는 방식이다.
    • 이 방식은 참조될 때마다 clock을 업데이트해주기만 하면 되므로 페이지를 참조할 때 빠르다는 장점이 있지만, evict 페이지를 찾으려면 전체를 다 살펴봐야 하므로, evict하기 느리다는 단점이 있다.

LRU Approximation Algorithm

• 근사적으로 늦게 참조된 페이지를 찾는 방식을 사용하는데, 이를 LRU Approximation Algorithm이라고 한다.
• 크게 reference bit을 사용하는 방법과 second chance algorithm이라는 방식이 있다.
  • reference bit
    • 각 page를 나타내는 pte의 reference bit은 참조될 때마다 1로 세팅된다.
    • 특정 시간 간격을 두고 reference bit를 모아서, 모인 값이 가장 작은 페이지를 evict하는 방식이다.
  • second chance algorithm(clock algorithm)
    • 페이지들이 시계 모양의 ring buffer형식으로 구현되어 있는 상태에서 특정 페이지가 참조되면 reference bit을 1으로 바꿔준다. 그리고 특정 페이지를 evict해야 한다면, 시계바늘이 가리키고 있는 페이지를 evict 하려고 한다. 다만 이 때, 시계바닐이 가리키는 페이지의 reference bit가 0이면 그냥 evict하고, 1이면 0으로 만들고 시계바늘을 한칸 옮긴다.

Page의 종류

1. Anonymous page(익명 페이지)
   • 파일으로부터 매핑되지 않은, 커널로부터 할당된 페이지
2. File-backed page(파일 기반 페이지)
   • 파일으로부터 매핑된 페이지

Anonymous Page

• 커널로부터 프로세스에게 할당된 일반적인 메모리 페이지이다. 즉, 익명 페이지는 힙을 거치지 않고 할당받은 메모리 공간이다.(힙도 익명 페이지이다. malloc, new같은 메모리 할당자는 익명 페이지에서 일부 메모리를 잘라 할당 받는것이다.) 익명이라는 뜻은 파일에 기반하고 있지 않은 페이지라는 뜻이다.
• 페이지가 파일에 매핑되어 있다면, 그 메모리는 파일 내용을 담고 있을 것이다. 하지만 익명 페이지는 파일에 매핑되어 있지 않았기 때문에 0으로 초기화된 값을 담고 있다.
• 프로세스가 mmap()으로 커널에게 익명 페이지를 할당 요청하게 되면, 커널은 프로세스에게 가상 메모리 주소 공간을 부여하게 된다. 부여된 가상 메모리 공간은 아직까지는 실제 물리 메모리 페이지로 할당되지 않은 공간이다. 부여된 가상 메모리에 읽기, 쓰기시 다음과 같은 커널의 도움을 받아 zero페이지로 에뮬레이션 되거나, 실제 물리 페이지로 매핑된다.
  1. 프로세스가 그 메모리 공간에 읽기 작업 시, 커널은 zero로 초기화된 메모리 페이지를 제공한다.
  2. 프로세스가 그 메모리 공간에 쓰기 작업 시, 커널은 실제 물리 메모리를 할당하고 write된 데이터를 보관한다.
• 익명 페이지는 private 또는 shared로 할당받을 수 있다.
  • 프로세스의 힙과 스택이 private로 할당된 anonymous page이다.
  • shared는 프로세스간 통신을 위해 사용되는 anonymous page이다.

File-Backed Page

• 파일의 내용을 메모리에 직접 반영하는 메모리 페이지다. 이는 파일 내용을 프로세스의 주소 공간으로 매핑하여, 파일 데이터에 대한 빠른 접근과 수정을 가능하게 한다.
• 프로그램이 mmap과 같은 시스템 호출을 사용하여 파일을 메모리에 매핑하면, 운영체제는 해당 파일의 내용을 메모리 페이지로 매핑한다.

작동 원리

1. 메모리 매핑 : 프로세스가 파일을 메모리에 매핑하면, 운영체제는 파일의 내용을 메모리 페이지에 매핑한다. 이 페이지들은 파일의 실제 데이터를 반영한다.
2. 페이지 폴트 처리 : 프로세스가 처음으로 파일-백업 페이지에 접근하면 페이지 폴트가 발생할 수 있다. 이 경우, 운영체제는 해당 파일의 적절한 부분을 읽어 메모리에 로드한다.
3. 데이터 동기화 : 프로세스가 이 페이지들을 변경하면, 변경사항은 나중에 파일 시스템에 다시 쓰여질 수 있다. 이를 통해 파일과 메모리 간의 데이터 동기화가 이루어진다.

특징

• 지속성 : 디스크에 저장된 파일과 직접 연결되어 있으므로, 데이터는 지속성을 가진다.
• 효율적인 파일 접근 : 파일 입출력을 위한 시스템 호출의 오버헤드없이 파일 데이터에 접근하고 수정할 수 있다.
• 동기화 옵션 : 자동 또는 수동으로 파일과 메모리 간의 동기화를 관리할 수 있다.

Swap Disk

• RAM이 모두 찼을 때 RAM에서 잘 사용하지 않는 page들을 옮겨 두는 disk 공간이다.
• Swap disk는 물리적 메모리가 부족할 때 사용되는 디스크 기반의 저장 공간이다. 이 공간은 일부 페이지를 임시로 저장하는 데 사용되며, 이를 스와핑 이라고 한다.
• 스왑 디스크의 목적은 시스템의 물리적 메모리가 부족할 때 추가적인 가상 메모리 공간을 제공하는 것이다. 시스템은 더 많은 프로세스와 데이터를 동시에 처리할 수 있다.

작동방식

1. 스와핑 : 메모리가 가득 차면, 운영체제는 가장 적게 사용되는 메모리 페이지들을 스왑 디스크로 이동시킨다. 이를 통해 메모리에서는 더 중요한 데이터를 처리할 수 있게 된다.
2. 페이지 교체 : 스왑 디스크에 저장된 페이지가 다시 필요하게 되면, 운영체제는 해당 페이지를 메모리로 다시 로드한다. 이 과정에서 다른 페이지가 스왑 디스크로 이동될 수도 있다.
3. 스왑 공간 관리 : 운영체제는 스왑 공간을 효율적으로 관리하기 위해 복잡한 알고리즘을 사용한다.

장점

• 메모리 부족 문제를 완화한다.
• 동시에 실행되는 프로세스의 수를 증가시킬 수 있다.
• 시스템의 전반적인 유연성을 향상 시킨다.

단점

• 디스크 기반의 스왑은 메모리에 비해 상대적으로 느리다.
• 과도한 스와핑(thrashing)은 시스템 성능 저하를 일으킬 수 있다.

DMA(Direct Memory Access)

• CPU를 거치지 않고 주변장치가 시스템 메모리에 직접 접근할 수 있도록 해주는 기술이다.
• CPU가 데이터 전송을 관리하는 대신, DMA 컨트롤러가 이 역할을 담당하여 CPU를 다른 작업에 할당할 수 있다.

작동 방식

1. DMA 컨트롤러 : DMA 연산은 DMA 컨트롤러라는 특수한 하드웨어에 의해 수행된다. 이 컨트롤러는 주변장치와 메모리 간의 데이터 전송을 관리한다.
2. 메모리 접근 : 주변장치가 데이터를 전송할 준비가 되면, DMA 컨트롤러는 메모리 주소를 지정하고 데이터 전송을 시작한다. 이 과정에서 CPU는 관여하지 않는다.
3. 인터럽트와 완료 신호 : 데이터 전송이 완료되면, DMA 컨트롤러는 CPU에 인터럽트를 보내 전송이 완료되었음을 알린다. 이를 통해 CPU는 전송된 데이터를 처리할 수 있다.

장점

• 효율성 : 대용량 데이터를 처리할 때 CPU부담을 줄어준다.
• 성능 향상 : CPU는 다른 중요한 작업에 집중할 수 있어 전체 시스템 성능이 향상된다.
• 저지연 : 입출력 장치와 메모리 간의 빠른 데이터 전송을 가능하게 한다.

단점

• 복잡성 : DMA컨트롤러의 관리와 구성이 복잡할 수 있다.
• 자원 충돌 : 메모리 버스의 점유로 인해 다른 장치들의 메모리 접근이 지연될 수 있다.