왜?
근본적으로 전공자와 비전공자의 차이를 매꾸기 위한 목적이다
자료에서 제공하는 운영체제, 3가지 쉬운 이야기에 대해 볼수있다.
- 가상화(Virtualization)
- 동시성(Concurrency)
- 지속성(Persistence)
이러한 아이디어를 배울있어서 OS의 구조, 즉 CPU에서 어떻게 프로그램을 다음 실행하거나 어떻게 가상 메모리 시스템의 메모리 과부하를 처리하거나 가상 머신 모니터의 작동 방식 디스크에 대한 정보를 관리하는 방법도 약간은 있지만 부품이 고장 났을 때 동작하는 분산 시스템을 구축하는 방법에 대해 설명합니다. 구체적으로 말하면 그러한 같은 것이군요.
일단 2020.09.07까지 읽어왔던것을 정리할 것이다. 책은 기본적으로 virtualization, concurrency까지 읽었고, 100% 이해했다곤 하지못하겠지만, 컴공 친구말로는 이정도면 컴공에서 OS지식수준은 도달했고, 조금더 아는 수준으로 알아도된다고 하여 멈추고 다른 공부로 전환하려고한다.
필자의 이 포스팅은 남을 이해시키기 위함이 아닌 내가 이해하면서 끄적이면서 정리한 글이라고 봐주면 고맙겠다.
제1장 이 책에 관한 대화
제2장 운영체제 개요
프로그램은 매우 단순한일을 한다.
초당 수백만 번 명령어를 반입(fetch)하고 해석(decode)하고 (즉, 무슨 명령어인지 파악하고), 실행(execute)한다.
(즉, 두수를 더하고, 메모리에 접근하고, 조건을 검사하고, 함수로 분기하는 등의 정해진 일을 한다.)
명령어 작업을 완료한 후 프로세서는 다음 명령어로, 또 그 다음 명령어로 프로그램이 완전히 종료될 떄까지 실행한다.
운영체제란
프로그램을 쉽게 실행하고(동시에 여러 개의 프로그램을 실행할수도), 프로그램 간의 메모리 공유를 가능케 하고, 장치와 상호작용을 가능케하고, 다양한 흥미로운 일을 할수있게하는 소프트웨어이다. 시스템을 사용하기 편리하게, 정확하고, 올바르게 동작 시킬 책임이있다.
운영체제는 다양한 물리자원들을 배분하기 위해 가상화를 한다. 그래서 OS를 가상 머신이라고 부른다.
사용자 프로그램의 프로그램 실행, 메모리 할당, 파일 접근과 같은 가상 머신과 관련된 기능들을 운영체제에게 요청할 수 있도록, 운영체제는 사용자에게 API를 제공한다.(시스템콜)
가상화는 많은 프로그램들이 CPU를 공유하여, 동시에 실행될 수 있게한다. 프로그램들이 각자 명령어와 데이터를 접근할수있게한다. OS는 자원 관리자
물리적인 CPU, 메모리, 디스크는 시스템의 자원이다.
효율적으로, 공정하게, 이들 자원을 관리하는 것이 OS의 역할이다.
만약 두개의 쓰레드를 사용하여 각자 같은 변수를 참조하여 100을 더하는 프로그램을 실행시킨다면 결과는 200이 아닌 1xx가 나올것이다.
이뉴는 명령어가 한번에 하나씩만 실행된다는 것과 관련있다.
변수를 메모리에서 레지스터로 탑재하는 명령어1
레지스터를 1증가시키는 명령어 2
레지스터의 값을 다시 메모리에 저장하는 명령어 3
하지만 3개의 명령어가 원자적으로 (한번에 3개 모두) 실행되지 않기 때문에 이상한일이 발생한다.
병행성 과 관련있다
제Ⅰ편 가상화
제3장 가상화에 관한 대화
복숭아(CPU) 나눠먹기
제4장 프로세스의 개념
프로세스= 실행중인 프로그램
프로그램 자체는 생명x, 디스크상에 존재하며, 실행을 위한 명령어와 정적 데이터의 묶음이다.
프로세스들이 생각할때 각자 자신의 CPU가 있다고 착각하게 할수있을까?
Time Sharing기법으로 하나의 프로레스를 실행하고, 얼마 후 중단시키고 다른 프로레스를 실행하는 작업 반복 (context switch의 구현필요)
policy는 어느 프로그램을 실행시킬것인가?에 대한 대답이다
mechanism은 어떻게 다음 실행할 프로그램들로 넘어갈것인가?에 대한 대답이다
프로그램에서 프로세스 생성
OS가 프로그램 코드와 정적데이터를 메모리, 프로레스의 주소 공간(address space)에 탑재(load)하는 것이다.
스택, 힙을 할당한다
(스택은 지역 변수, 함수 인자, 리턴 주소등을 저장,힙은 동적으로 할당된 데이터를 저장위해서 연결 리스트, 해시 테이블, 트리 크기가 가변적인 자료 구조위해서)
OS는 입출력과 관계된 초기화 작업을 수행한다.
OS는 CPU를 새로 생성된 프로세스에 넘기게 되고 프로그램이 실행된다.
프로세스 상태
ready상태에서 스케줄되어야함 그래야 running상태가능
running상태는 현재 실행중인 프로세스임
I/O기다리거나 이벤트 wait를 받았을때 waiting상태로 전환!
자료구조
프로세스 리스트라는 자료 구조를 이용하여 시스템에서 실행 중인 프로그램을 관리한다. 프로세스의 관리를 위한 정보를 저장하는 자료 구조를 프로세스 제어 블럭(PCB)라고 부른다.
레지스터 문맥(register context)자료 구조는 프로세스가 중단되었을 때 해당 프로세스의 레지스터값들을 저장한다. 이 레지스터값들을 복원하여 OS는 프로세스 실행을 재개한다(문맥 교환(context switch))
제5장 막간: 프로세스 API
fork() 시스템콜
PID(프로세스 식별자)
자식 프로세스는 부모 프로세스와 완전히 동일하지는 않다. 자식 프로세스는 자신의 주소 공간, 자신의 레지스터, 자신의 PC값을 갖는다.
CPU스케줄러는 실행할 프로세스를 선택한다. 어느 프로세스가 먼저 실행될지 모름.
wait() 시스템콜
부모가 먼지 실행되면 wait()가 일어나서 자식 프로세스가 일끝낼떄까지 리턴하지않는다.
exec() 시스템콜
자신이 아닌 다른 프로그램을 실행해야 할떄 사용한다. (fork()는 자신의 복사본을 만드는 것과 반대)
fork()와 exec()를 나눠놓은이유는 fork()하고 명령어 (예를들면 입출력바꿈등의 명령)후에 exec()를 하여 외부 프로그램 실행할 수 있기 때문이다
제6장 제한적 직접 실행 원리
CPU시간을 나눠 씀으로써 가상화를 구현한다.(Time sharing)
성능저하, 제어권의 문제가 발생할수있다.
직접 실행 원리로 프로그램을 CPU에서 직접 실행시킴.
제한적! 이라는것은 프로그램 실행에 제한을 둬야 OS는 제어권을 다시 획득해서 제어를 할수있다.
OS에 사용자 모드와 커널 모드가 도입되었다
사용자 모드에서 실행되는 코드는 할수있는 일이 제한된다. 프로세스가 제한된 요청을 할 경우 프로세서가 예외를 발생시키고, OS는 해당 프로세스를 제거한다
커널 모드는 OS의 중용한 코드들이 실행된다. 이 모드에서 실행되는 코드는 모든 특수한 명령어를 포함하여 원하는 모든 작업을 수행할 수 있다.
사용자 프로세스에게 특권 명령을 실행해야할때는 OS가 제공하는 시스템 콜을 이용한다.
trap 특수 명령어를 실행> 커널 안에서 분기하는 동시에 커널 모드로 상향 조정> 커널 모드 진입후 해당 명령 실행> 완료시 return-from-trap 특수 명령어 호출> 사용자 모드로 다시 하향 조정> 호출한 사용자 프로그램으로 리털
trap요청한 프로세스의 레지스터들을 저장해야한다. return-from-trap 명령어 실행 시 사용자 프로세스로 제대로 리턴할 수 있도록 하기 위함이다.
커널은 부팅 시에 trap table만들고 시스템을 통제한다. trap handler는 트랩 발생시 해야하는 행동들이 적혀있다. 즉 하드웨어들이 예외적인 사건이 일어났을때 trap>trap handler>순으로 진행 (???)
프로레스간의 전환중 OS가 제어권획득을 위한 방법은 timer interrupt를 발생시키는것이다. 즉 수행 중인 프로세스가 중단되고 미리 구성된 OS의 interrupt handler가 실행된다. 이 시점에서 OS는 CPU제어권을 다시 얻게 되고 원하는 일가능(현재 프로세스를 중단하고 다른 프로세스를 실행시키는 작업등…)
OS가 현재 실행중인 프로세스를 재개할것인지, 다른 프로세스로 전활할 것인지를 결정해야한다.
이 역할을 OS의 scheduler라는 부분에 의해 내려진다.
다른 프로세스로 전활하기로 결정되면 OS는 context switch한다.(코드를 실행)
현재 실행중인 프로세스의 레지스터 값을 커널 스택 같은 곳에 저장하고 곧 실행될 프로세스의 커널 스택으로부터 레지스터 값을 복원하는 것이 전부다.
시스템 콜을 처리하는 도중 타이머인터럽트가 발생? 등의 질문은 병행성단원에서…
제7장 스케줄링: 개요
(프로세스를 7~9까지 job이라고 부를것임)
스케줄링 평가 항목.
FIFO(First In, First Out)
먼저 온 job 먼저 처리
A job 이 엄청 길고 B, C job이 짧다고 가정
맨 처음 온 job이 너무 많은 시간요구하면 뒤에 다른 job들의 결과처리까지 시간너무 많이소요
SJF(Shortest Job First)
가장 짫은것 처리하기
A가 먼저 도착해버리고 일 처리가 된다면
B,C가 늦게 도착하면 FIFO에서의 문제점과 같아짐
STCF(Shortest Time-to-Completion First)
Preemptive scheduling 선점방식!
can stop a job! 이 필요하며, 즉,context switch를 필요로 한다.
A 도착후 10초후에 B,C가 도착하면
B,C가 먼저 처리가능한 job이므로 A를 중단후 B,C처리후 A로 다시 CPU줌
RR(Round-robin)
job을 시간으로 나눠서 배치함 (time slice)
time quantum 조건에 따라
small일 경우
good responsiveness, high context switch overhead(계속 바꿔야하므로 스위치 비용높다)
Large일 경우
low context switch overhead but bad responsiveness
Incorporating I/O
많은 애플리케이션이 I/O를 한다.
A가 I/O요청하면 잠시 block 하고 B처리하다가 I/O요청 받으면 A로 스위칭
제8장 스케줄링: 멀티 레벨 피드백 큐
MLFQ(Multi-Level Feedback Queue)
SJF, STCF: good for turnaround time, terrible for response time
RR: vice response time
How to optimize the turnaround time while minimizing response time?
MLFQ (Multi-Level Feedback Queue)
Consist of multiple queues
Each queue is assigned a different priority level
A job that is ready to run is on a single queue (running or blocked jobs are out of the queues)
A job with higher priority (a job on a higher queue) is chosen to run next (RR among jobs in the same queue)
MLFQ가 작업의 우선순위를 어떻게 바꿀 것인지 결정해야 한다. 작업의 우선순위를 변경하는 것은 작업이 존재할 큐를 결정하는 것과 마찬가지이다. 이를 위해 워크로드의 특성을 반영해야 한다. 짧은 실행 시간을 갖는 CPU를 자주 양보하는 대화형 작업과 많은 CPU 시간을 요구하지만 응답 시간은 중요하지 않은 긴 실행 시간의 CPU 위주 작업이 혼재되어 있다.
위의 MLFQ의 규칙을 좀 더 추가하면 다음과 같다.
규칙 3 : 작업이 시스템에 진입하면, 가장 높은 우선 순위, 즉 맨 위 큐에 놓여진다.
규칙 4a : 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다. 즉, 한 단계 아래 큐로 이동한다.
규칙 4b : 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선 순위를 유지한다.
다음 예시를 통해서 작업량이 많은 일에 경우 지속적으로 우선순위가 낮은 큐에 배치되며, SJF의 형태를 가진다.
제9장 스케줄링: 비례 배분
제10장 멀티프로세서 스케줄링(고급)
제11장 CPU 가상화에 관한 마무리 대화
Mechanism: Context switch, Timer interrupt, Handler > 어떻게 넘어가고 처리할것인가!!에 대한것 메커니즘
Policy: FIFO, SJF, RR, MLFQ, Lottery, Stride, Multiprocessor > 일 나열에 관한 정책
제12장 메모리 가상화에 관한 대화
사용자 프로그램이 생성하는 모든 주소는 가상주소다.
즉, 당신이 보는 모든 것은 가상 주소
왜 물리 메모리를 가상화해?
OS는 각 프로세스에게 단지 환상을 제공한다. 마치 자기만의 메모리가 있는것처럼!
OS가 하드웨어로부터 약간의 도움을 얻어 가장된 가상 주소를 실제 물리 주소로 변환하고 원하는 정보의 위치를 찾을수있다. 사용하기 쉬운 시스템
고림과 보호!도 중요한 이유중하나
제13장 주소 공간의 개념
멀티프로그래밍과 시분할이 필요해졌다. 시분할을 구현하는 한 가지 방법은 실행 중단 다른 프로세스 실행 중단하는 것이다. 이 중단 시점에 모든 상태를 디스크에 저장..다른 프로세스해당하는거 메모리 올리는것은 매우 느리다
즉, 레지스터 상태를 저장하고 복원하는 것은 빠르지만, 프로세스 전환시 프로세스를 메모리에 그대로 유지하면서, 운영체제가 시분할 시스템을 효율적으로 구현할 수 있게 하는 것이다.
여기서 발생하는 문제점은 여러 프로그램이 메모리에 동시에 존재하려면 보호가 중요한 문제다. 한 프로세스가 다른 프로세스의 메모리를 읽는것을 막아야한다
주소 공간
OS는 사용하기 쉬운 메모리 개념을 만들어야하고, 이 개념이 주소 공간이다.
주소 공간은 실행 프로그램의 모든 메모리 상태를 갖고 있다.
일단 실행중인 프로그램 코드(명령어)는 반드시 메모리에 존재하므로 주소 공간에 존재한다. 스택은 함수 호출 체인 상의 현재 위치, 지역 변수, 함수 인자와 반환 값등을 저장하는 데 사용된다. 힙은 동적으로 할당되는 메모리를 위해 사용된다. 힙과 스택은 각각 반대방향으로 커진다.
주소 공간을 설명할떄, OS가 실행중인 프로그램에게 제공하는 개념을 설명한다. 실제로 프로그램이 물리 주소 0~16KB사이에 존재하는 것이 아니다. 실제로는 임의의 물리 주소에 탑제된다.!!!
OS가 메모리를 가상화하여 다수의 프로세스에게 프로세스전용의 커다랑 주소 공간이라는 개념을 제공한다.
프로세스 A가 가상주소 0부터 load를 수행할때, OS는 하드웨어의 지원을 통해 물리 주소 0이 아니라 물리 주소 320KB(A가 탑재된 메모리 시작주소)를 읽도록 보장한다.
VM(가상 메모리 시스템)의 목표는
- 투명성(실행중인 프로그램이 가상 메모리의 존재를 인지x)
- 효율성(가상화가 시간, 공간 측면에서 효율적이도록)(TLB지원,,)
- 보호(프로세스가 남의 프로세스 메모리에 접근, 영향 x)>>프로세스들 서로 고립
제14장 막간: 메모리 관리 API
어떻게 메모리를 할당하고 관리할 것인가?
C프로그램 실행되면, 두가지 유형의 메모리 공간이 할당된다
스택 메모리는 컴파일러에 의해 암묵적.. 자동 메모리임
함수 리턴 이후에도 유지되어야 하는 정보는 스택에 저장x
힙 메모리는 모든 할당과 반환이 프로그래머에 의해 명시적으로 처리됨
malloc() 힙에 요청할 공간의 크기 넣어줌., 메모리 할당
free() 할당된 메모리 해제.
새로운 언어들이 자동 메모리 관리를 지원(가비지 컬렉터.)
…CS관련아니므로나머지패스
제15장 주소 변환의 원리
CPU가상화 부분에서 제한적 직접 실행이라는 기법을 집중적으로 다뤘다.
즉, 중요한 순간에 OS가 관여하여 하드웨어를 직접 제어한다.
메모리 가상화도 비슷한 전략이다.
하드웨어-기반 주소 변환 >> 주소 변환 으로 부른다
프로그램의 모든 메모리 참조는 가상 주소를 물리 주소로 변환한다.
아주 예전에는 베이스와 바운드라는 간단한 아이디어가 채택되었다. (동적 재배치)
CPU마다 2개의 하드웨어 레지스터가 필요하다. 하나는 베이스 레지스터, 하나는 바운드 레지스터(=리미트 레지스터)이다.
프로그램 시작시 OS가 베이스 레지스터에 프로그램이 탑재될 물리 메모리 위치 시작주소를 저장한다. 프로그램 카운터(PC)는 128이라면 이를 베이스값을 더해서 해당 물리 주소로 변환됫으니 명령어를 가져온다. 또 프로세스에서 가상 주소 15KB의 값을 탑재하라는 명령어를 내리면, 이 주소를 프로세서가 받아 다시 베이스 레지스터 값(32KB라고가정)을 더하고 물리주소는 47KB에서 원하는 내용을 탑재한다.
이를 주소 변환 기술이라고 한다. 하드웨어는 프로세스가 참조하는 가상 주소를 받아들여 데이터가 실제로 존재하는 물리 주소로 변환한다. 동적 재배치! 프로세스가 실행을 시작한 이후에도 주소 공간을 이동가능하기때문에
리미트 레지스터는 합법적인 주소 참조의 범위에 있다는 것을 확인할때 쓰인다
베이스와 리미트 레지스터는 CPU칩 상에 존자하는 하드웨어 구조이다. 주소 변환에 도움을 주는 프로세서의 일부를 MMU라고 부르기도한다
주소 공간의 마지막 물리 주소를 리미트 레지스터에 저장해놓는다면
가상주소+베이스 =< 리미트 를 검사하면 유효한 범위인지 할수있다.
하드웨어는 베이스와 바운드 레지스터를 자체적으로 제공한다.
CPU는 사용자 프로그램이 바운드를 벗어난 주소를 불법적인 메모리 접근을 시도하려고할때 예외를 발생시킬수있다. OS의 “바운드 벗어남”예외 핸들러가 실행되도록 조치.
context switch 가 일어날때 PCB(프로세스 제어 블럭)으로 OS가 실행중인 프로세스를 중단시키면 베이스와 바운드 레지스터의 값을 저장.(메모리에 저장해놓음)
동적 재배치는 비효율적이다.
주소 공간 이미지에서의 free는 즉 내부 단편화를 의미하는 것이므로..
이를 세그멘테이션!으로 줄일수있다.
제16장 세그멘테이션
베이스와 바운드 레지스터를 사용하면 OS가 물리 메모리의 다른 부분으로 쉽게 재배치할수 있다. 하지만 스택과 힙사이에 큰 free공간이 있으므로 그만큼 내부 단편화가 존재하게된다(낭비)
이를 위해 세그멘테이션이라는 아이디어가 탄생했다. MMU안에 오직 하나의 베이스와 바운드 쌍만 존재하는 것이 아니라 __주소 공간의 논리적인 세그멘트(segment) 마다 베이스와 바운드 쌍이 존재한다. __ 세그멘트는 특정 길이를 가지는 연속적인 주소 공간이다. 예시기준으로는 코드, 스택, 힙의 세 종류의 논리적 세그멘트가 있다. OS는 각 세그멘트를 물리 메모리의 각기 다른 위치에 배치가능.
예시기준으로는 3쌍의 베이스와 바운드 레지스터 쌍이 필요하다. 오프셋값+베이스값 이 바운드값을 넘지 않으면 범위내에 있으므로 그 물리 메모리 주소를 읽는다.
가상 주소에서 각 논리에 해당하는 시작값을 뺴고, 오프셋값을 얻어낸후 다시 해당 베이스값을 더해야하는 것에 주의하자
세그멘트 종류의 파악
하드웨어는 가상 주소가 어느 세그멘트를 참조하는지, 그 세그멘트 안에서 오프셋이 얼마인지를 어떻게 알수있을까?
이런식으로 세그먼트를 명시하고, 나머지는 오프셋을 뜻하는것으로 해결한다. 특히 오프셋이 바운드보다 작은지 여부만 검사하면 된다.
시스템이 각 주소 공간 구성 요소(힙, 스택, 코드)를 (베이스, 바운드를 기준으로) 별도로 물리 메모리에 재배치하기 때문에 메모리 절약이가능하다.
문제점들은 다음과 같다
context switch때 세그멘트 레지스터의 저장과 복원이다
미사용중인 물리 메모리 공간의 관리다. 새로운 주소 공간이 생성되면 OS는 이 공간의 세그멘트를 위한 비어있는 물리 메모리 영역을 찾을 수 있어야한다. 각 세그먼트의 크기가 다를수있다.. 특 외부 단편화가 일어날수있다.
물리메모리상태이다
제17장 빈 공간 관리
외부 단편화를 방지하는 방법에 대해 생각해보기
저수준 기법들
분할 - free list를 작성해놓고 할당 요청들어오면 split해서 free list update하고
병합 - 메모리 청크가 반환될때(free()사용시) 해제되는 청크의 주소와 바로 인접한 빈 청크의 주소를 살펴보고, 바로 인접해있다면 더 큰 빈 청크로 병합한다. 아래 그림 5번째
제18장 페이징: 개요
세그멘테이션은 가변 크기의 조각들로 분할하는 것이다. 공간을 다양한 크기의 청크로 분할할 때 공간 자체가 단편화가 될수있다. 할당은 점점더 어려워진다
이를 해결하기 위해 공간을 동일 크기의 조각으로 분할 하는 것을 고려한다
페이징
프로세스의 주소 공간을 몇개의 가변 크기의 논리 세그멘트(코드, 힙, 스택)으로 나누는것이 아니라 고정 크기의 단위로 나눈다. 이 각각의 고정 크기 단위를 페이지(page)라고 부른다. 또한 상응하여 물리 메모리도 페이지 프레임(page frame)이라고 불리는 고정 크기의 슬롯의 배열이라고 생각한다. 이 프레임 각각은 하나의 가상 메모리 페이지를 저장할 수 있다.
주소 공간은 전체0~64KB로 4개의 페이지로 나누면 각 16KB이다. 이를 전체 물리메모리 128KB로 가정하면 페이지 프레임이 8개가 나오므로 OS가 유지하는 빈 공간 리스트에서 가져와 4개의 페이지 프레임에 배치하면된다. 또한 힙 스택이 어느 방향으로 커지는가, 어떻게 사용되는가에 대한 가정을 하지 않아도된다.
주소 공간의 각 가상 페이지에 대한 물리 메모리 위치 기록을 위해서 OS는 프로세스마다 페이지 테이블(page table)이라는 자료 구조를 유지한다. 페이지 테이블의 주요 역할은 주소 공간의 가상 페이지 주소 변환 정보를 저장하는 것이다. VPN(가상주소)>>PFN(물리주소) (즉, 가상페이지0>>물리페이지3)
offset은 놨두고 VPN>PFN으로 전환
Page table은 매우 크므로 MMU안에서 유지하지 않고, 대신 각 프로ㅔ쓰의 페이지 테이블을 메모리에 저장한다.
페이지 테이블은 가상 주소를 물리 주소로 매핑하는데 사용되는 자료구조로, 가장 간단한 형태는 선형 페이지 테이블이다. VPN로 배열의 항목(PTE)에 접근하여 PFN을 얻어낸다. 각 PTE에는 다른 심도있는 비트들도 존재한다.
protection bit, accessed bit, valid bit등등 중요함.
페이징 너무 느림
페이지 테이블로 인해 처리 속도가 매우 저하될수있다.
명령어를 가져오는과정은
메모리 접근에서 VPN을 PFN으로 바꾸기 위해 메모리에 있는 page table에 접근하고 다시 PFN으로 메모리에 접근하여 명령어를 가져온다 (무조건 2번이상의 메모리 처리가 필요…)(느려짐)
메모리 낭비(유용한 응용 데이터 대신 페이지 테이블로 가득참)초래한다.
제19장 페이징: 더 빠른 변환(TLB)
페이징은 상당한 성능 저하를 가져올 수 있다. 하지만 위에처럼 모든 페이징 주소변환에 있어서 모든 로드/스토어 명령어 실행이 추가적인 메모리 읽기를 수반하는 상황(페이지 테이블이 메모리에 잇으므로)을 가정해보자. 정말 느려질수밖에없다.
주소 변환을 빠르게 하기 위해서는 변환-색인 버퍼(TLB)라고 부르는 것을 도입한다. MMU의 일부이다!!. 자주 참조되는 가상 주소-실주소 변환 정보를 저장하는 하드웨어 캐시이다.
하드웨어는 먼저 TLB에 원하는 변환 정보가 있는 지 확인후
>>>>존재하면(hit) 실주소 반환함>>권한 검사>> 원래 오프셋과 합쳐서 메모리 접근
>>>>없다면(miss) 페이지 테이블에 접근하여 변환 정보를 찾아서 TLB로 읽어드린다>>> TLB가 갱신되면 하드웨어는 명령어 재실행>>TLB에 존재하므로 Hit된다.
이제는 히트가 미스보다 훨씬 많다면 이제는 페이징 비용이 부담되지 않는다.
이처럼 a[0]를 처음접근할때는 miss후 해당 페이지에 대한 물리주소를 가져와서 TLB에 도움된다. 그다음 a[1], a[2]는 같은 페이지에 있는 오프셋값이므로 hit, hit가 일어난다. 다음 a[3]은 다른 페이지 이므로 miss가 뜨고 위과정을 반복한다.
그렇다면 TLB가 엄청 크고 모든 페이지테이블 담아 hit가 많아지면 좋은것인가?
아니다. 그럼 결국 메모리와 다를게뭐냐!
지역성을 생각하자
시간지역성, 공간 지역성
시간 지역성: 최근에 접근된 명령어 또는 데이터는 곧 다시 접근될 확률이 높다는 사실에 근거한다! TLB효과높아짐
공간 지역성: 프로그램이 메모리 주소 x를 읽거나 쓰면, x와 인접한 메모리 주소를 접근할 확률이 높다는 사실에 근거한다.
TLB의 구성?
일반적인 TLB는 32,64,128개의 엔트리를 가지며
VPN|PFN|다른 비트들
변환 정보 저장 위치에 제약이 없도록, 각 항목마다 가상 페이지 번호VPN와 물리 페이지 번호 PFN가 있다.
다른 비트들에는 다양한 정보를 표시하고 있다.
TLB의 문맥교환 문제
TLB를 사용하게 되면 프로세스 간 문맥 교환시 새로운 문제가 등장한다.
TLB는 그것을 탑재시킨 프로세스에서만 유효하다. 다른 프로세스들에게는 의미가 없다. 즉, 문맥교환할 때 이전에 실행하던 프로세스의 변환 정보를 사용하지않도록 주의해야한다.
여러가지 해법이 있을 수 있지만 하나만 언급해보자면, ASID정보를 다른 비트들에 추가한다. 문맥 전환시, OS는 새로운 ASID 값을 정해진 레지스터에 탑재한다. (ASID는 PID와역할이 생각하면됨)
제20장 페이징: 더 작은 테이블
나중에 다시보기
제21장 물리 메모리 크기의 극복: 메커니즘
나중에 다시보기
멀티 레이블..등등
즉 세그맨테이션+페이징 개념들이 나오면서 극복
제22장 물리 메모리 크기의 극복: 정책
나중에 다시보기
제23장 VAX/VMS 가상 메모리 시스템
나중에 다시보기
제24장 메모리 가상화를 정리하는 대화
.
제Ⅱ편 병행성
제25장 병행성과 관한 대화
여러사람이 복숭아를 먹고 싶어 한다고해보자
복숭아를 눈으로 확인할 후에 복숭아를 집어 먹도록 하면 발생하는 문제들.
멀티 프로그램 생각해보기
각 쓰레드는 독립된 객체로서 프로그램 내에서 프로그램을 대신하여 일한다.
메모리에 접근하는데, 조정하지 않으면, 예상처럼 동작안할수있다.
제26장 병행성: 개요
이번 장에서는 프로세스를 위한 새로운 개념인 쓰레드를 소개한다.
각 쓰레드가 프로세스와 매우 유사하지만, 차이가 있다면 쓰레드들은 주소 공간을 공유하기 때문에 동일한 값에 접근할 수 있다는 것이다.
하나의 쓰레드의 상태는 프로세스의 상태와 매우 유사하다. 쓰레드는 어디서 명령어들을 불러 들일지 추적하는 프로그램카운터(PC)와 연산을 위한 레지스터들을 가지고있다. 만약 두 개의 쓰레드가 하나의 프로세서에서 실행중이라는 반드시 문맥 교환이 일어나야한다. 쓰레드1이 사용하던 레지스터들을 저장하고 쓰레드2가 사용하던 레지스터 내용을 복원한다는 점에서 프로세스의 문맥 교환가 유사하다. 프로세스의 상태를 PCB에 저장하듯, 쓰레드 제어 블럭(TCB)가 필요하다.
쓰레드는 각자의 레지스터를 가진다.
가장 큰차이는 프로세스와 달리 쓰레드 간의 문맥 교환에서는 주소 공간을 그대로 사용한다는 것이다(사용하고 있던 페이지 테이블을 그대로 사용하면 된다)(명령어 주소공간 공유하기때문에 동일한 값에 접근이가능하다
또 다른 큰 차이는 스택에 있다. 고전적 프로세스 주소 공간과 같은 간단한 모델(단일 쓰레드 프로세스)에서는 스택이 하나만 존재한다. 반면에 멀티 쓰레드 프로세스의 경우에는 각 쓰레드가 독립적으로 실행되며 쓰레드가 실행하기 위해 여러 루틴들을 호출할 수있다. 주소 공간에는 하나의 스택이 아니라 쓰레드마다 스택이 할당되어있다…
쓰레드 생성시 스케줄러의 동작에 따라 다르겟지만, 즉시 실행될수도있고, 준비 상태일수도있다. 따라서 추가 쓰레드의 종료를 예상한다면 메인 쓰레드는 pthread_join()을 호출하여 특정 쓰레드의 동작의 종료를 대기한다.
쓰레드1, 쓰레드2중에 누가 먼저 실행될지 몰라서 문제가 나타날 수 있지만 더 어려운 상황은 공유 데이터에 접근시에 나타난다.
전역 공유 변수를 갱신하는 두개의 쓰레드에서 공유변수인 counter에 1씩을 더해 2만을 기대한다면, 결과는 20000이 되지않는다.
왜?
제어 없는 스케줄링
counter 공유 변수를 증가하는 코드의 순서는 다음과 같다
mov 0x8049, %eax
add $0x1, %eax
mov %eax, 0x8049
이 예제에서 처음 mov 명령어가 명시한 메모리 주소의 값을 읽어드린 후 eax 레지스터에 넣는다. 1을 eax레지스터의 값에 더하는 연산을 한후 마지막으로 eax에 저장되어 이 값을 메모리의 원래의 주소로 다시 저장한다.
쓰레드1에서 마지막 mov 로 메모리에 해당 레지스터 값(51)을 넣기 전에 타임 인터럽트가 일어나면 쓰레드 2는 그냥 메모리에 있는 값(55까지 되었다고가정)부터 시작해서 연산시작하여,,, 정상적으로 쓰레드 문맥 교환이일어나면, 쓰레드1은 이제 레지스터 값을 메모리에 넣는것을 한다.즉, counter변수값이 55에서 다시 51이 된다.
명령어의 실행 순서에 따라 결과가 달라지는 상황을 경쟁조건이라고 부른다. 즉, 결정적 결과가 아니라 비결정적인 결과이다.
멀티 쓰레드가 같은 코드를 실행할때 경쟁 조건이 발생하기 때문에 이러한 코드 부분을 임계 영역이라고부른다. (공유 변수, 자원을 접근하고 하나 이상의 쓰레드에서 동시에 실행되면 안되는 코드를 임계영역이라고부른다.)
이러한 코드에서 필요한 것은 상호 배제이다. 즉, 이 속성은 하나의 쓰레드가 임계 영역 내의 코드를 실행 중일 때는 다른 쓰레드가 실행할 수없도록 보장해준다. 따라서 경쟁을 피할 수 있고 프로그램 실행 결과를 결정론적으로 얻을 수 있게 된다.
원자성!이란 하나의 단위를 뜻하며, 때로는 전부 아니면 전무이다. 원자성을 보장한다는 것은 명령어가 실행이 안되었거나 실행이 종료된 후라는것.
하드웨어 적으로는 동기화 함수 구현에 필요한 기본적인 명령 몇개만 필요하다. 즉 하드웨어와 OS의 지원을 통해 한번에 하나의 쓰레드만 임계 영역에서 실행하도록 구성된, 제대로 잘 동작하는 멀티 쓰레드 프로그램을 작성할 수 있다.
제27장 막간: 쓰레드 API
이번 장은 쓰레드 API에 대해 간략히 설명한다.
쓰레드를 만들때, 종료할때..락, 컨디션 변수에 대해 인터페이스를 설명한다. 이중 락, 컨디션 변수에 대해 설명하겠다
락은 임계 영역에 대한 상호 배제 기법이다.
lock()>>~~~>>unlock()은 ~~~에 실행되는 것에 대해 lock()락을 획득을 시도하고 락을 얻을 때까지 호출에서 리턴하지 않는다. 많은 쓰레드들이 락 획득 함수에서 대기중일수있다. 락을 획득한 쓰레드만이 언락을 호출해야한다.
컨디션 변수
한 쓰레드가 계속 진행하기 전에 다른 쓰레드가 무언가를 해야 쓰레드 간에 일종의 시그널 교환 메커니즘이 필요하다. 이때 쓰는것이 컨디션 변수.
ready를 컨디션 변수로 활용
wait()를 사용하여 호출 쓰레드를 수면상태로 만들고 다른 쓰레드로부터의 시그널을 대기한다. while문에서 ready변수가 0인지 검사하고 0일떄 wait()함수를 넣어서 0인지 계속 검사한다. 이때 wait()는 인자로 락과 시그널을 받는다. 이유는 wait()할때 락을 반납하기때문이다. 다른 쓰레드가 락을 획득 후 할일끝나고 ready=1로 변경하며, signal()로 시그널을 보낸후, 락을 반납한다. 기존 쓰레드가 ready=1이 되는순간 while문 빠져나오고 시그널 받았으므로 wait()상태를 벗어난다.(이때 wait()깨어나서 리턴하기 직전에 락을 다시 획득한다.)
몇가지 유의할 점은 전역 변수 ready를 수정할때 반드시 락을 가진상태에서 수정해야한다. 이를 통해 경쟁 조건이 발생하지 않는다는 것을 보장한다. 나머지 하나는 시그널 대기 함수는 락, 시그널 두개의 인자를 받는다는 것이다. 마지막으로 대기하는 쓰레드가 조건을 검사할때 if 문대신 while문을 사용하는 것이다. 변수를 제대로 갱신하지 않고 대기하던 쓰레드를 깨울수있는데, 이때 재검사를 하지 않는다면 대기하던 쓰레드는 조건이 변경되지 않았더라도 변경되었다고 생각할 것이다. 때문에 시그널의 도착은 변경 사실을 알리는 것이 아니라, 변경된 것 같으니 검사해보라는 정도의 힌트로 간주하는게 더 안전하다.
제28장 락
소스 코드의 임계 영역을 락으로 둘러서 원자 단위 명령어인것처럼 실행되도록 한다. 락은 하나의 변수이므로 락 변수를 먼저 선언한다. 락은 사용가능, 사용중으로 두 가지 상태를 가진다. 사용중이면 다른 쓰레드가 lock()호출해도 리턴하지않는다.
락 평가
락을 만들었을 때 평가는 상호 배제, 공정성, 성능이있다.
초창기 단일 프로세스 시스템에서는 상호 배제 지원을 위해 임계 영역 내에서는 인터럽트 비활성방법씀(Time인터럽트 발생 x) >>결국 마지막까지 처리가능함. 하지만 실제로 중요한 인터럽트가 발생하는데 모두를 무시하는것은 위험하고, OS가 제어권을 가져올 기회가 프로그램에게 주어진다. + 멀티 CPU에대해서는 안통함
Test-And-Set(Atomic Exchange)
플래그 변수로 락을 구현해 보자.
임계 영역에 진입하는 첫 쓰레드가 lock() 을 호출하여 플래그 값이 1인지 검사(test)하고, 플래그값이 1이 아니면 이 쓰레드가 락을 보유(hold)하고 있다고 표시한다. 임계 영역에서 나오면 쓰레드가 unlock()을 호출하여 플래그 값을 초기화하여 락을 더이상 보유하고 있지 않다고 표시한다.
만약 다른 누가 사용중인데 어떤 쓰레드가 lock()호출한다면 flag==1 이므로 spin-wait을 하며 다른 누구의unlock()을 기다린다.
두가지 문제가 있다. 정확성과 성능이다. 시작할 떄는 flag=0이지만 적시에 인터럽트가 발생하면 두 쓰레드 모두 flag를 1로 설정하는 경우가 생길수있다. 성능은 spin-wait라는 방법을 사용하여, 플래그의 값을 무한히 검사하는 것에서 비롯된다. 특히 단일 프로세서에서 특히 손해가 크다. 락을 소유한 쓰레드조차 문맥 교환전까지는 실행할수없기때문이다.
이 TestAndSet이 하는 동작은 다음과같다. ptr이 가리키고 있던 예전의 값을 반환하고 동시에 new에 새로운 값을 저장한다. 핵심은 원자적으로 수행된다는 것이다. 이전값을 검사(test)하고(반환되는값임) 동시에 메모리에 새로운 값을 설정(set)하기 때문이다.
TestAndSet을 이용한 간단한 스핀 락.
즉 TestAndSet이 lock->flag가 0이면 lock()호출한 쓰레드는 TestAndSet에서 0이 반환되므로 while문 탈출한다.(동시에 lock->flag값은 1로 변함)
하지만 lock->flag가 1이였다면 이전값을 반환하는 TestAndSet은 1을 반환하므로 while문안을 돈다.
즉 락의 값을 검사하고 새로운 값으로 설정하는 동작을 원자적 연산으로 만들어서 오직 하나의 쓰레드만 락을 획득할 수 있도록 하였다.
스핀락의 정확성은 완벽하다. 상호 배제가 잘 수행되기 떄문이다. 공정성은 보장하지 못한다. 실제로 while문을 회전 중인 쓰레드는 경쟁에 밀려서 계속 그상태로 남아있을수있다. 성능은 단일 CPU의 경우에 성능 오버헤드는 크다. 스케줄러가 락을 획득하려고 하나씩 깨워야하기때문이다. CPU 사이클을 낭비하면서 락을 획득하기 위해 대기한다. 반면 CPU가 여러 개인 경우 스핀락은 괜찮은 방법이다. 임계 영역이 매우 짧다고하면 쓰레드 A가 락을 획득한 CPU1, B가 락을 기다리는 CPU2가 있다고 하면, 임계 영역 구간이 짧다고 하면 곧 락을 획득 가능한 상태가 될수있으므로 쓰레드 B는 락을 획득하게된다.
Compare-And-Swap
이 기법은 ptr이 가리키고 있는 주소의 값이 expected변수와 일치하는지 검사하는 것이다. 일치한다면 ptr이 가르키는 주소의 값을 새로운 값으로 변경한다. 불일치한다면 아무것도 하지않는다. 원래의 메모리 값을 반환하여 CompareAndSwap를 호출한 코드가 락 획득의 성공 여부를 알수 있도록한다.
락 구현방식은 TestAndSet과 비슷
Load-Linked 그리고 Store-Conditional 넘어긴다
Fetch-And-Add
이런식으로 원자적으로 만든 후, 하나의 쓰레드가 락 획득을 원하면, 티켓 변수에 원자적 동작인 fetch-and-add명령어를 실행한다. 결과 값은 해당 쓰레드 차례를 나타낸다.
myturn은 차례를 나타낸다. 전역 공유 변수인 lock->trun사용하여 어느 쓰레드의 차례인지 판단한다. myturn ==turn이라면 임계 진입, 언락 동작은 lock->turn값 올림.
과도한 스핀
이제까지 소개한 하드웨어 기반의 락은 간단하고, 제대로 동작한다. 하지만 낭비되는 것이있다. 두개의 쓰레드를 프로세서가 하나인 시스템에서 실행했다고하자. 첫번째 쓰레드는 락획득후 실행하다가 타임 인터럽트에 걸리고, 두번째 쓰레드는 락획득을 못하기때문에 타임 인터럽트까지 아무것도 하지않는다. N개의 쓰레드가 하나의 락을 획득하기 위해 경쟁하게 되면 상황은 더욱 심각해진다. N-1개의 쓰레드에 할당된 CPU 시간 동안, 낭비한다. 스핀하면서 락 해제를 기다린다..
이제 하드웨어의 지원으로만 이 문제를 해결할 수가 없다. OS로 부터 추가 지원이 필요하다.
무조건 양보 yield()라는 시스템 콜은 호출 쓰레드 상태를 running에서 ready상태로 변환하여 다른 쓰레드가 running상태로 전이하도록한다. deschedule!
하지만 문맥교환비용이 만만치 않다.
스핀 대신 잠자기!, 어떤 쓰레드가 다음으로 락을 획득할지를 명시적으로 지금까지 제어못했다. 오직 스케줄러에 의해서 뽑혔다. 이번에는 명시적으로 제어해보자. OS로부터 적절한 지원과 큐를 이용한 대기 쓰레드들의 관리가 필요하다. park()는 특정 쓰레드 잠재우는 함수 unpark(threadID)는 특정 쓰레드 깨우는 함수. 이것을 락요청하는 프로세스를 재우고 해당 락이 해제되면 깨우도록 하는 락을 제작하는 데 앞뒤로 사용할 수 있다.
Test-And-Set와 락 대기자 전용 큐와 함께 사용하여 좀더 효율적인 락을 만들것이다. 또 큐를 사용하여 다음으로 락을 획득할 대상을 제어하여 기아 현상을 피할것이다.
일부 하드웨어 지원과 일부 운영체제의 지원(park(), unpark()와 같은 형태)을 받아 락을 구현하였다. 현대적 모델도 관심을 갖자!
제29장 락 기반의 병행 자료 구조
넘김
제30장 컨디션 변수
락 만으로는 병행 프로그램을 제대로 작성 불가하다
부모 쓰레드는 자식 쓰레드가 작업을 끝냈는지 검사하기 원할수있다.(join())
1 | while(done==0): |
위처럼 부모 쓰레드에서 기다리면 부모쓰레드에 CPU가 할당되었을때 낭비된다.
조건이 참이 되 때까지 기다리기 위해 컨디션 변수를 활용할수있다
컨디션 변수는 일종의 큐 자료 구조로서, 어떤 실행의 상태(또는 어떤 조건)가 원하는것과 다를때 조건이 참이 되기를 기다리며 쓰레드가 대기할 수 있는 큐이다. 즉, 다른 쓰레드가 상태를 변경시켰을 때, 대기 중이던 쓰레드(하나 이상의 쓰레드가 깨어날수도있다)를 깨우고 (조건에 따라 시그널을 보내어), 계속 진행할수있도록 한다.
wait()는 락을 해제하고 호출한 쓰레드를 재우는 것이다. 어떤 다른 쓰레드가 시그널을 보내어 쓰레드가 깨어나면, wait()에서 리턴하기 전에 락을 재획득해야한다
두 가지 경우가 있다.
첫번째는 부모 쓰레드가 자식 쓰레드를 생성하고 계속 실행하여 thr_join()을 호출하여 자식 쓰레드가 끝나기를 기다리는 경우이다. 결국 wait()를 호출하여 락해제되고 스스로 잠재운다. 자식 쓰레드는 thr_exit()을 호출하여 부모 쓰레드를 깨울 것이다. 이 코드는 락을 획득한 후에 상태 변수를 done으로 설정하고 부모 쓰레드에 시그널을 보내어 깨어나도록한다. 마지막으로, 호출했던 wait()에서 락을 획득한 채로 리턴하여 부모 쓰레드가 실행될 것이며 락을 해제하며 parent:end 출력된다
두번째는 자식 쓰레드 생성즉시 실행되서 자고 있는 쓰레드를 깨우기 위해 시그널을 보낸다. 하지만 자고있는 쓰레드가 없기 때문에 단순히 리턴한다. 헛 수고!, 그 후에 부모 쓰레드가 실행하고 done=1 화긴하고 대기 없이 바로 리턴된다.
컨디션 변수에서 가장 기본 법칙은 언제나 if 문 아닌 while문을 사용해야한다. 조건을 재확인하는 것이 안전하다.(거짓으로 깨운경우 다시 잠재울수있음.)
그리고 시그널을 보낼때, 대기할때 항상 락을 걸자.
또한 상태 변경되었다는 힌트가 시그널이고 확신은 done이라느 변수사용이 중요하다.
동기화 문제! 해결할수있는 컨디션 변수는 중요하다
두개의 컨디션 변수를 사용하여, 생산자, 소비자를 나눠놓자!
제31장 세마포어
병행성 문제 해결을 위해 락, 조건 변수가 모두 필요하다.
세마포어라는 동기화 기법!
세마포어는 정수 값을 갖는 객체로서 두 개의 루틴으로 조작할 수 있다. sem_wait()와 sem_post()이다. 세마포어는 초기값에 의해 동작이 결정되기 때문에, 사용하기 전”제인 먼지”값을 초기화를 해야한다.
이 루틴들은 다수 쓰레드들에 의해 동시에 호출되는 것을 가정한다.
첫번째로, sem_wait()함수는 세마포어에서 1을 빼고 즉시 리턴하거나(1을 뺀 세마포어의 값이 0이상이면), 아니면 해당 1을 뺀 세마포어 값이 0이상이 될 때까지 호출자를 대기시킨다. 다수의 쓰레드들이 sem_wait()를 호출할 수 있기 때문에, 대기큐에는 다수의 쓰레드가 존재할수있다. 대기하는 법에는 회전과 재우기의 두가지있다는 것을 기억하자
두번째는, sem_wait() 함수와 달리 sem_post()함수는 대기하지 않는다. 세마포어 값을 1을 더하고 대기 중인 쓰레드 중 하나를 깨운다.
세번째로 세마포어가 음수라면 그 값은 현재 대기 중인 쓰레드의 개수와 같다.
이 두개의 함수는 원자적으로 실행된다고 가정한다.
이진 세마포어로 락 만들기
X값에 1로 시작하면된다. 처음락획득이면 1-1=0 이되고 이때 다른 쓰레드가 얻으려고하면 -1이 되고, 처음락쓰레드가 처리다하면 세마포어값은 0이며, post()로 다른 쓰레드 호출하므로, 락획득까지 하고 post()하며 모든 작업완료하면 세마포어값은 1결과적으로된다.
컨디션 변수로서의 세마포어
어떤 조건이 참이 되기를 기다리기 위해 현재 쓰레드를 멈출 때에도 세마포어는 유용하게 사용될 수 있다. 예를 들어, 리스트에서 객체를 삭제하기 위해 리스트에 객체가 추가되기를 대기하는 쓰레드가 있다고 가정한다. 이런 종류의 전형적인 패턴이 하나의 쓰레드가 어떤 사건의 발생을 기다리고, 또 다른 쓰레드는 해당 사건을 발생시킨후, 시그널을 보내어 기다리던 쓰레드를 깨우는 것이다. 대기 중인 쓰레드가 프로그램에서의 어떤 조건이 만족되기를 대기하기 때문ㅇ, 세마포어를 컨디션 변수처럼 사용할수있다.
부모쓰레드가 자식쓰레드를 기다린다하자
부모는 자식 프로세스 생성후 sem_wait()를 호출하여 자식의 종료를 대기한다. 자식은 sem_post()를 호출하여 종료되었음을 알리고 부모가 동작하게한다.
특히 여기에서 x는 0 이되어야한다.
생산자/소비자 유한 버퍼 문제
요약
세마포어는 병행 프로그램 작성을 위한 강력하고 유연한 기법이다.
p.374까지 학습완료