Page Replace Algorithm이란?

Virtual memory system에서 페이지 부재(page fault)가 발생했을때 주기억장치(메모리)의 모든 페이지 프레임이 사용중이라면 어느 페이지 프레임을 교체할 지 결정하는 알고리즘

FIFO(First In First Out)

페이지 교체 시, 메모리에 올라온지 가장 오래된 페이지를 내쫓는다.

장 점: 

•  가장 간단한 페이지 교체 알고리즘

 단 점:

• 가장 오래된 페이지가 초기화 모듈이라면 성능이 저하될 수 있음
• Belady의 모순(Belady's anomaly)
  • 프로세스에게 프레임을 더 주었는데 오히려 페이지 부재율이 더 증가하는 현상

OPT(Optimal)

앞으로 가장 오랜 동안 사용되지 않을 페이지를 찾아 교체한다

 장 점: 

•  모든 알고리즘보다 낮은 페이지 부재율
•  Belady의 모순 발생하지 않음

단 점: 

•  구현이 어려움. (프로세스가 앞으로 메모리를 어떻게 참조할 것인지 미리 알아내기 힘들기 때문)

LRU(Least Recently Used)

페이지 교체 시에 가장 오래 사용되지 않은 페이지를 교체 
최적 페이지 교체 알고리즘에 근사한 알고리즘으로 각 페이지마다 마지막 사용 시간을 유지 (미래시간 대신 과거 시간에 대해 적용한 최적 교체 알고리즘)

구현방식

• 카운트 방식 : Counting에서 이 방식을 쓴다.
• 스택 방식 : 그 많은 페이지를 관리하기 위해, doubly-linked-list를 차용한 스택을 쓰기엔 메모리, 연산량이 너무 아깝다

Least-recently-used Approximation

reference bit을 사용

• reference bit: 하드웨어 지원없이 시스템은 LRU에 대한 도움을 제공하기 위해 reference bit의 형태를 지원.

이 방식은 페이지가 변하는 순서는 알 수 없지만 페이지가 교체 되는지 아닌지는 알 수 있는 방식

Counting-Based Page

참조 횟수를 가지고 교체될 페이지를 선정

Least Frequently Used

참조 횟수가 가장 적은 페이지를 교체

Most Frequently Used

참조 횟수가 가장 많은 페이지를 교체

 가장 작은 참조 횟수를 가진 페이지가 가장 최근에 참조됐기 때문에 가장 적게 참조됐고, 앞으로 사용될 것이라는 판단에 근거한 알고리즘이다.

대개 LFU, MFU 알고리즘을 잘 쓰지 않는다.

• 현 시 비용이 많이 들고, 최적(OPT) 페이지 교체 정책에 제대로 근사하지 않기 때문

프로세스와 가상 메모리

모든 프로세스는 자신만의 가상 주소 공간을 가지고 있다. 32비트/64비트 프로세스는 각 비트수에 맞게 최대 4GB/16GB의 주소 공간을 가진다.

모든 프로세스들은 자신만의 주소 공간을 가지기 때문에, 특정 프로세스 내에서 쓰레드가 수행될 때 해당 쓰레드는 프로세스가 소유하고 있는 메모리에 대해서만 접근이 가능하다. 다른 프로세스에 의해 소유된 메모리는 숨겨져 있으며, 접근이 불가능하다.

따라서, A 프로세스가 0x12345678 주소에 무엇인가를 저장하였지만, B 프로세스 역시 0x12345678 주소에 무엇인가를 저장할 수 있으며, 이 주소들은 완전히 독립되어 있는 것이다.

즉, 가상 메모리는 프로세스의 logical memory와 physical memory를 분리하기 위해 생겨난 것

따라서 logical memory가 physical memory보다 커지는 것을 가능케 할 수 있다.

하나의 프로세스 logical memory가 physical memory보다 커지는 것도 가능하며, 여러 프로세스의 logical memory 총합이 physical memory보다 커지는 것도 가능한 것이다.

램이 꼴랑 1기가인 PC를 생각해 보면 이 PC에서 포토샵도 띄우고, 게임도 띄우고, 웹페이지도 띄운다. 하드가 버벅대지만, PC는 멈추지 않고 실행한다.

이처럼, 프로세스가 실제 필요로 하는 부분만 메모리로 올리는 Demand-Paging 기법을 사용한다.

이미 메모리가 소진된 상태에서 위에서 띄운 프로그램의 작업 내용을 기억하기 위해 디스크 공간을 메모리처럼 활용할 수 있는 기능을 가지고 있다.

디스크 상에 존재하는 이러한 파일을 paging file (또는 swap file)이라고 하며,  모든 프로세스가 사용할 수 있는 가상 메모리로 사용된다.

즉 용량이 큰 게임을 실행하면 하드가 돌면서 실행된다. 하드 스왑이라는 페이징 파일에서 실제 물리 메모리로 올리고 내리고 하는 일련의 작업을 이야기하는 것이다.

애플리케이션 관점에서 보면, 페이징 파일을 사용하면 애플리케이션이 사용할 수 있는 램의 크기가 증가한 것과 같은 효과를 가져온다.

만일 PC에 4GB의 램이 있고, 디스크 상에 4GB의 페이징 파일이 있디면, 수행 중인 애플리케이션은 PC에 8GB의 램이 있는 것과 동일한 효과를 누릴 수 있는 것이다 (물론, 8GB 램보다는 4GB 램+ 4GB 페이징 파일이 더 느리다.)

가상메모리란 한정된 물리 메모리의 한계를 극복하고자 디스크와 같은 느린 저장장치를 활용해, 애플리케이션들이 더 많은 메모리를 활용할 수 있게 해 주는 것이 가상 메모리이다.

Page

Page란, 가상 메모리를 사용하는 최소 크기 단위

만약, 페이징 파일에서 물리 메모리로 데이터를 로드할 때, 아무 위치에나 필요한 크기 만큼(무작위) 로드한다고 가정을 해 보자.

이런 경우, 로드하고 언로드하는 데이터의 크기가 모두 제각각이므로, 이를 반복하다 보면 메모리 공간에 fragmentation이 발생하게 된다.

결국 메모리는 남아 있지만, 정작 원하는 크기의 데이터를 물리 메모리로 로드하지 못하게 되는 상황이 생길 수 있는 것이다. 이를 막기 위해, 운영체제가 만든 것이 page라는 최소 크기 단위이다.

Demanding Page

데드락이란?

프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태

예를 들어 P1과 P2가 리소스 A,B 둘 다를 얻어야 한다고 가정한다. t1(첫 번째 시간)에 P1이 리소스 A를 얻고 P2가 리소스 B를 얻었다면 t2(다음 시간)때 P1은 리소스 B를, P2는 리소스 A를 기다리게 된다. 하지만 서로 원하는 리소스가 상대방에게 할당되어 있기 때문에 이 두 프로세스는 무한정 기다리게 되는데 이러한 상태을 DeadLock상태라고 한다.

데드락 발생 조건

데드락은 아래 네 가지 조건이 동시에 성립 할 때 발생한다. 즉, 아래의 네 가지 조건 중 하나라도 성립하지 않도록 만든다면 데드락을 해결할 수 있다.

데드락 처리

예방

• 교착 상태 발생 조건 중 하나를 제거함으로써 해결하는 방법
• 자원의 낭비가 심하다.

회피

• 교착 상태가 발생하면 피해나가는 방법
• 은행원 알고리즘 (Banker’s Algorithm)
  • 자원할당 요청 -> 자원이 안전한지 체크 -> (안전하다면) 자원할당
                                                            -> (안전하지 않으면) 할당거부

탐지

• 자원 할당 그래프를 통해 교착 상태 탐지
• 자원을 요청할때마다 자원 할당 알고리즘을 실행하면 오버헤드 발생

회복

• 교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제함으로써 회복
  

프로세스를 종료하는 방법

• 교착 상태의 프로세스를 모두 중지
  
• 교착 상태가 제거될 때까지 한 프로세스씩 중지

자원을 선점하는 방법

• 교착 상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하며, 해당 프로세스를 일시 정지 시키는 방법
  
• 우선 순위가 낮은 프로세스, 수행된 횟수가 적은 프로세스 등을 위주로 프로세스의 자원을 선점한다.

스핀 락

Spin Lock 은 이름이 뜻하는대로, 만약 다른 스레드가 lock을 소유하고 있다면 그 lock이 반환될 때까지 계속 확인하며 기다리는 것이다. "조금만 기다리면 바로 쓸 수 있는데 굳이 컨텍스트 스위칭으로 부하를 줄 필요가 있나?" 라는 컨셉으로 개발된 것으로 크리티컬 섹션에 진입이 불가능할때 컨텍스트 스위칭을 하지 않고 잠시 루프를 돌면서 재시도 하는 것을 말합니다. Lock-Unlcok 과정이 아주 짧아서 락하는 경우가 드문 경우(즉; 적절하게 크리티컬 섹션을 사용한 경우) 유용하다. Spin Lock 은 다음과 같은 특성을 갖는다.

1. Lock을 얻을 수 없다면, 계속해서 Lock을 확인하며 얻을 때까지 기다린다. 이른바 바쁘게 기다리는 busy wating이다.
2. 바쁘게 기다린다는 것은 무한 루프를 돌면서 최대한 다른 스레드에게 CPU를 양보하지 않는 것이다.
3. Lock이 곧 사용가능해질 경우 컨택스트 스위치를 줄여 CPU의 부담을 덜어준다. 하지만, 만약 어떤 스레드가 Lock을 오랫동안 유지한다면 오히려 CPU 시간을 많이 소모할 가능성이 있다.
4.  하나의 CPU나 하나의 코어만 있는 경우에는 유용하지 않다. 그 이유는 만약 다른 스레드가 Lock을 가지고 있고 그 스레드가 Lock을 풀어 주려면 싱글 CPU 시스템에서는 어차피 컨택스트 스위치가 일어나야 하기 때문이다. 주의할 점 스핀락을 잘못 사용하면 CPU 사용률 100%를 만드는 상황이 발생하므로 주의 해야 한다. 스핀락은 기본적으로 무한 for 루프를 돌면서 lock을 기다리므로 하나의 쓰레드가 lock을 오랫동안 가지고 있다면, 다른 blocking된 쓰레드는 busy waiting을 하므로 CPU를 쓸데없이 낭비하게 된다.

장점은 스핀락을 잘 사용하면 context switch를 줄여 효율을 높일 수 있습니다. 무한 루프를 돌기 보다는 일정 시간 lock을 얻을 수 없다면 잠시 sleep하는 back off 알고리즘을 사용하는 것이 훨씬 좋습니다.

크리티컬 섹션

유저 객체. (커널에서 제공 객체X)

커널 객체가 아니므로 가볍고 빠름

그러나 한 프로세스 내의 쓰레드 사이에서만 동기화가 가능. 보통의 경우 가볍고 쉽게 쓸 수 있는 동기화 객체

뮤텍스

커널 객체. 

크리티컬 섹션보다 무거움.

크리티컬 섹션이 한 프로세스 내의 쓰레드 사이에서만 동기화가 가능한 반면, 뮤텍스는 여러 프로세스의 스레드 사이에서 동기화가 가능.

뮤텍스를 가장 흔히 사용하는 예가 프로세스 다중 실행을 막을 때. 이런 기능은 크리티컬 섹션으로는 불가능.

cs(크리티컬 섹션)를 가진 스레드들끼리 실행이 겹치지 않게 단독으로 실행하는 기술

세마포어

커널 객체

위의 크리티컬 섹션, 뮤텍스는 동기화 함에 있어서 동시에 하나의 쓰레드만 실행되게 하지만 이에 반해, 세마포어는 지정된 수만큼의 쓰레드가 동시에 실행되도록 동기화하는 것이 가능.

지정된 수보다 작거나, 같을 때까지 쓰레드의 실행을 허용하고, 지정된 수를 넘어서 쓰레드가 실행되려 하면 실행을 막음.

뮤텍스와 세마포어 차이점

세마포어는 뮤텍스가 될 수 있지만 뮤텍스는 세마포어가 될 수 없음.

세마포어는 소유할 수 없는 반면 뮤텍스는 소유할 수 있고 소유자가 이에 책임을 짐

뮤텍스는 1개만 동기화가 되지만 세마포어는 하나 이상을 동기화 할 수 있음

• 예) 변기가 하나뿐인 화장실에서는 앞의 사람이 볼일을 마치고 나가야 다음 사람이 들어갈 수 있다. 이렇게 한번에 오직 하나만 처리할 수 있는 대상에 사용하는 것이 뮤텍스, 변기가 세개인 화장실에서는 동시에 세 사람이 볼일을 볼 수 있고 이 세 사람 중 아무나 한명이 나오면 다음 사람이 볼일을 볼 수 있다. 이렇게 동시에 제한된 수의 여러 처리가 가능하면 세마포어이다. 만약 변기 세개짜리 화장실의 각 변기에 대해 뮤텍스를 사용한다면 대기중인 사람은 각 변기 앞에 줄을 서는 것이고 이렇게 되면 옆 칸이 비어도 들어가지 못하게 된다. 이에 비해, 변기 세개에 대해 세마포어를 적용하는 것은 화장실 앞에서 줄을 서서 대기하다가 아무나 한명 나오면 대기중이던 한명이 들어가는 것이다. 만약 변기 세개를 묶어서 뮤텍스를 사용한다면 변기 수에 관계없이 무조건 한명만 사용할 수 있게 된다. 이 예에서 변기는 동기화 대상, 사람은 그 동기화 대상에 접근하는 쓰레드를 나타낸다. 뮤텍스와 세마포어의 목적은 특정 동기화 대상이 이미 특정 쓰레드에 의해 사용중일 경우 다른 쓰레드가 해당 동기화 대상에 접근하는 것을 제한하는 것으로 동일하지만 관리하는 동기화 대상이 몇개인가에 따라 차이가 생기게 되는 것이다.

OS란?

컴퓨터의 하드웨어와 소프트웨어를 제어하며, 사용자가 컴퓨터를 쓸 수 있게 만들어주는 프로그램

OS의 목표

• 어플리케이션을 위한 기본 실행 환경을 제공해 사용자의 프로그램을 정확하게 실행
• 컴퓨터 시스템을 편리하고 효율적이고 안전하게 사용할 수 있게 만듬

OS의 관점

• resouce allocator - 컴퓨터 시스템의 자원(소프트웨어, 하드웨어)를 할당해주고 이것들을 효율적으로 관리
• control program - 사용자 프로그램 실행과 I/o 장치 실행을 통제한다.
• kernel - 컴퓨터 운영체계의 가장 중요한 핵심으로서 운영체계의 다른 모든 부분에 여러 가지 기본적인 서비스를 제공한다.
• 멀티 프로세스/ 멀티 테스킹 : 여러 작업은 동 시간에 메인메모리 안에서 유지되고 이러한 프로세스들은 cpu time, I/o 장치, 다른 자원들을 공유한다.

컴퓨터 시스템의 구성요소

• 하드웨어 - CPU, Memory 등 기본 컴퓨팅 리소스
• 유저
• 어플리케이션
• OS

Interrupt

CPU는 데이터를 메인메모리 ↔로컬 버퍼 로 데이터를 이동시킨다.

I/o 디바이스

각 디바이스 컨트롤러는 로컬 버퍼를 가진다.

cpu와 I/o디바이스는 동시에, 독립적으로 실행된다.

 cpu와 I/o디바이스 사이에 정보를 전달하는 의사소통이 필요하다.

디바이스 컨트롤러는 cpu에게 자신의 처리가 끝났다는 것을 알려야 한다.

 -> Interrupt로 알려줌.

cpu, 다양한 device controller들이 공유하는 메모리에 접근하기 위해 공용버스를 통해 연결됨

cpu가 다른 일을 하고 있다가 interrupt가 걸리면 저장한 다음 멈추고 interrupt를 건 I/o디바이스를 처리한다.

 인터럽트엔 h/w, s/w 가 있음.

하드웨어는 우리가 알고 있는 I/o 디바이스의 신호

소프트웨어에는 cpu 내부에서 0으로 나눴을 때와 같은 오류 인터럽트 (trap)

인터럽트 걸렸을 때, 과정

하던일 멈춤-> 고정 위치에 하던일 저장 -> 인터룹트 서비스 루틴 실행 -> 서비스 루틴 완료한 다음 다시 하던 일 시작

interrupt : 키보드에서 인터룹트 발생

exception: 0을 나눌 때,

듀얼모드

유저모드와 커널모드로 나눔 유저모드에 어플리케이션이 있고 커널모드에서 처리 이 두 사이에 통신을 위해 시스템 콜이 일어남.

function call : caller와 callee는 같은 프로세스 안에 있음

system call : 다른 프로세스에 있음

- 같은 액티비티를 수행하기 위해 os에게 요청 - 매우 비쌈

운영체제가 지원하는 서비스에 대한 프로그래밍 인터페이스

프로세스 관리

 fork() : 부모에서 동일한 차일드 프로세스 생성

c에서 printf를 하는 행동은 유저모드에서 발생. prinf를 하면 c library call이 일어남. 다음 커널 모드에서 write()를 호출하고 write() system call이 불린 후 결과를 역순으로 전달.

system call의 종류 

프로세스 컨트롤, 파일 관리, 디바이스 관리, 정보 유지,

ms-dos - simple structure 듀얼모드 없음

unix - layered 커널에서 모든 것을 관리, 기능이 확장됨에 따라 커널이 넘 커짐

텍스트 : PC(피시 카운터 - 다음번에 실행 될 명령어의 주소를 가지고 있는 레지스터), 프로그램 코드 저장

데이터: 글로벌 변수, 스태틱 변수 저장

힙 :메모리관리, 동적 메모리 할당(시스템 콜로 관리)

스택: 임시 데이터 저장- 로컬 변수, 리턴 어드레스

한 프로그램은 동시에 여러번 실행할 수 있다.

-> 비록 두 프로세스는 같은 프로그램이라도, 두 개의 분리된 실행 시퀀스로 간주됨

이것은 Text section (텍스트영역)은 공유할 수있지만, Data, Heap, Stack 영역은별도로갖음.

쓰레드는 스택을 제외하고 전부 공유

하나의 프로세스는 CPU에서 한번만 실행된다. 나머지는 준비상태나 대기상태의 큐에 존재한다.

각 프로세스는 등록되고 커널(OS)에 의해 관리된다.

 각 프로세스는 PCB에 정보를 저장하고 표현된다.(프로세스 상태, CPU 레지스터, 정보 등)

Context switch

현재 cpu를 사용중인 프로세스의 상태를 저장하고 새로운 프로세스의 상태를 이전에 cpu를 쓰던 상태로 복귀 다음 context 정보들을 pcb에 저장되고 불려짐. 

멀티쓰레드

이전 웹서버는 많은 사용자의 요청이 들어올 경우, 사용자의 요청 당 프로세스 1개씩 생성했다. 문제로 프로세스간 데이터를 공유하기 위해 IPC가 필요했다.

이 문제를 멀티쓰레드로 가능하게 했다. 멀티 쓰레드는 스택영역을 제외하고 텍스트, 데이터, 힙을 공유해 한 프로세스안의 쓰레드 간 공유를 쉽게 할 수 있다.

쓰레드 VS 프로세스

새로운 프로세스를 생성해 fork()를 사용하는 것은 비싸다.(시간 & 메모리)

왜? 

fork는 글로벌 변수, 코드, 스택 부분을 전부 복사해서 새로운 프로세스를 만든다.

thread는 stack만 따로 만든다.(나머지 공유)

멀티쓰레드 모델

many to one : 1개의 커널 쓰래드에 여러개의 유저쓰레드 연결

one to one : 유저 쓰레드 1개당 커널쓰레드 (각기 분리되어있음)

many to many : 여러 커널 쓰레드와 유저 쓰레드를 연결. 통로는 1개로 스케쥴링에 의해 커널 쓰레드를 결정함

스케쥴링

OS의 역할

시간 공유를 위한 자원

Preemptive: 현재 실행중인 프로세스에 인터룹트가 걸리면 레디상태로 이동한다.

non-Preemptive: cpu가 프로세스 하나에 전부 할당되어 일처리가 완료 될 때까지 자원을 놓지 않는다.

스케쥴링 알고리즘 

FCFS

도착한 순서대로 실행, 논 프림티브에 적당, 다 끝나거나 I/O요구하기 전까지 자원을 놓지않음

SJF(shortest-job-first)

두가지 버전이 있다.

non-preemptive - 맨 처음은 들어온 순서대로 수행 후 맨 처음 프로세스가 수행 중 도착한 프로세스 중 burst time(수행시간)이 가장 짧은 순서대로 수행.

preemptive - 맨 처음 도착한 프로세스를 수행 중에 도착한 프로세스들과 burst time을 계속 비교해 가장 짧은 것을 수행한다.

장점 : 평균 waiting time이 가장 짧음, 반응이 빠름

단점 : starvation - burst time이 가장 긴 프로세스가 먼저 들어왔을 경우에 실행이 되지 않을 수도 있음. -> aging으로 해결가능 (시간에 따라 priority를 높힌다.)

Priority 

우선순위에 따라 실행 순서를 결정. 

문제점: 

RR (round robin)

프림티브

time quantum을 사용자가 지정해 프로세스에 할당 시간을 준다.

(예, time quantum 시간을 10이라 잡으면 각 프로세스마다 10이란 시간을 사용하고 다시 큐에 들어가 대기)

(time quantum; 이하 g라 부름] g가 매우길면 fcfs가 되고 매우 짧으면 빈번하게 context switching이 벌어져  오버헤드가 매우 높아진다.)

Syncronize

Race Condition

일반적으로 Race Condition 이란 두 개 이상의 프로세스가 공통 자원을 병행적으로(concurrently) 읽거나 쓸 때, 공용 데이터에 대한 접근이 어떤 순서에 따라 이루어졌는지에 따라 그 실행 결과가 달라지는 상황을 말한다. Race condition이 발생하게 되면 모든 프로세스에 원하는 결과가 발생하는 것을 보장할 수 없으므로 이러한 상황은 반드시 피해야 한다. 이를 피하는 방법은 크게 mutual exclusion과 critical section으로 나누어 볼 수 있다.
예를 들어 A와 B라는 사람이 같은 계좌에 0원이 들어있는 계좌에서 돈을 각각 입금, 출금을 동시에 한다고 했을 때, 이를 처리하는 순서에 따라서 B는 출금을 할 수도 있고 없을 수도 있다.

Mutual Exclusion 

Race condition을 해결하기 위해서는 두개 이상의 프로세스가 공용 데이터에 동시에 접근하는 것을 막아야 한다. 즉 한 프로세스가 공용 데이터를 사용하고 있으면 다른 프로세스가 그 자원을 사용하지 못하도록 막거나, 다른 프로세스가 이미 공용 자원을 사용하고 있으면 이 프로세스가 그 자원을 사용하지 못하도록 막으면 race condition을 피할 수 있다. 각각이 서로 공용자원의 사용을 막는다는 의미에서 이런 접근을 상호 배제(mutual exclusion)이라고 부른다. 

 Critical Section

프로세스의 입장에서 보면 프로세스의 어떤 부분은 자신만의 데이터를 가지고 열심히 계산만 하는 부분이 있고 공용데이터에 값을 저장하거나 읽어오는 부분이 있다. 공용 데이터에 접근하는 부분을 특별히 critical region 또는 critial section이라고 부른다. 따라서 프로세스란 측면에서 보았을 때 어떤 두 프로세스가 동시에 critical section에 들어가지 않도록 할 수 있다면 race condition을 피할 수 있다.

Syncronize 문제점

read와 write는 동시에 나올 수 없다.

read는 동시에 여러개가 가능하지만 write는 무조건 1개만 실행되어야 한다.