CS TIL (20180810)
.
study program : https://www.fastcampus.co.kr/dev_school_css
-
참고로 파이썬 같은 인터프리터 언어는 힙영역으로 들어간다. 스텍 프레임을 사용할 수 없다. 예를 들어 a =10 을 정의하고 del a를 통해 원하는 시점에 바로 지울 수 있는 이유는 이 언어들이 힙영역에 저장되어 있기 때문이다. 파이썬은 코드를 작성하고 그 프로세스를 실행하면 1.5기가의 협영역을 통째로 할당받아서 자기들이 설계한 구조로 내부 저장공간을 구성하여 활용한다. 어제 배웠던 기존의 가상공간과는 조금 다를 수 있다.
-
heap의 단점
1) 메모리 단편화현상
최악의 단점이다. 스텍은 생성과 삭제가 논리적으로도 그렇고 깔끔하다. 반면에 힙은 malloc이라는 함수가 할당될때마다 스텍처럼 차곡차곡 쌓이게 되기는 한다(스텍처럼 위아래로 쌓이는게 아니라 힙은 좌우로 쌓인다고 생각하자). 아직까지는 문제가 없다. 이제 원하는 공간 중간중간을 지우게 되면 조각조각 예를 들어 2바이트 2바이트씩 지우고 4바이트짜리를 할당하려고 하면 넣을 수없는 경우가 발생한다. 다시말해 빈공간 빈공간을 합치면 할당이 가능하지만 그게 안되기때문에 메모리 단편현상이 발생한다. 쉽게 비유를 하자면 버스에 커플이 자리를 앉으려고 하는데 한자리만 점유한 사람들이 많아서 커플이 동시에 앉을 수 없는 경우 그래서 나온게 다이나믹 힙이다. 프로그래밍으로 다이나믹 힙을 구현해야하고 대략적인 원리는 일정공간의 힙을 할당받아서 힙영역의 데이터들만 집중적으로 모아놓는다. 결론적으로 다이나믹 힙을 사용하면 속도나 효율성이 증대된다.
2) 메모리 누수 특히 c언어에서
3) 느리다. 특히 malloc을 쓸때
- 프로그램과 프로세스
1) 프로그램 : 하드웨어에 저장되어 있는 이미지, 프로그램의 이미지는 하나지만 프로세스는 여러개인 경우가 있다. 예를 들어 메모장을 두개 켜서 작업할때.. 이 두놈의 구분은 프로세스 아이디(PID)로 구분한다.
2) 프로세스 : 프로그램을 더블클릭해서 실행 시킨 것
즉 프로그램을 실행하면
하드디스크에 있는 프로그램이 램으로 넘어가며 프로세스로 바뀌게 된다.
- 가상주소공간의 활용취지
내가쓰는 컴퓨터의 램을 12기가라고 가정하자. 만약에 프로세스가 있으면 OS가 실제 메모리 4기가 씩 할당해주면 프로세스 3개 띄우면 아무것도 못하게 된다. 당연히 상식적으로.. 이런 경우는 오에스가 프로세스에 4기가를 주기는 하는데 실제 램의 4기가를 주는게 아니라 가상주소공간을 활용한다.
- 가상메모리
가상메모리의 아이디어는 램이 모자란 상황에서 데이터 저장기능은 하드디스크도 할 수 있으니까 하드디스크를 이용해보자
pysical memory = 메인메모리(실제 램) + page file(하드디스크의 일부) 인데 피지컬 메모리를 하드디스크를 이용해서 확장해보자
특히 프로세스가 페이지 파일을 메인메모리처럼 인식하도록 트릭을 구현함
즉 가상메모리는 메인메모리 + 하드디스크의 일부 이렇게 정의할 수 있다.
- MMU(메모리 메니지먼트 유닛)
프로세스에 주어지는 메모리 공간을 가상 주소 공간이라고 한다.
가상 주소 공간의 메모리 주소를 논리 주소(logical address)라고 하고 메인 메모리의 메모리 주소를 물리 주소(physical address)라고 한다. 프로세스를 실행하려면 실제로 데이터와 코드를 올릴 물리 메모리가 필요하다. 이를 위해 논리 주소를 물리 주소로 변환해 메인 메모리를 사용해야 하는데 이때 필요한 하드웨어가 MMU이다.
MMU(Memory Management Unit)는 논리 주소를 물리 주소로 런타임에 대응시키는 하드웨어로 과거에는 따로 존재했지만 지금은 CPU 내부에 있다.
-
가상메모리의 알고리즘
가상주소공간(VAS) : 총4기가를 4키로바이트로 잘개잘개 쪼개서 구분한다. 그 잘개 쪼개진 공간 하나를 page라고 말한다. page의 수는 총 2의 20승개이다. (4기가를 4키로바이트로 나눔)
<가상주소공간 구조> 총 4기가
page 4키로바이트
page 4키로바이트
page 4키로바이트
...... ......
page 4키로바이트
page 4키로바이트
page 4키로바이트
이 공간을 20비트로 표현할 수 있고 32비트 컴퓨터에서는 총 32비트 공간에서 20비트는 page number로 구성된다. 그리고 나머지 12비트는 offset이 구성된다. offset은 가상주소공간의 페이지 시작지점에서 특정 page가 저장되어 있는 주소까지 떨어져 있는 만큼을 offset이라고 한다.
가상주소공간에서 논리주소 표현 32비트 컴퓨터 기준 -------------------------------------------------- | page number 20비트 | offset 12비트 | -------------------------------------------------- -
실제 램에서 공간
1) 실제 램에서의 주소가 실제 공간이다.
2) 메인 메모리도 가상 주소 공간과 같은 크기로 쪼개진다. 쪼개진 부분 하나를 페이지 프레임이라고 부른다. 메인 메모리의 프레임이 가상 주소 공간의 페이지와 크기가 같은 이유는 실제로 존재하지 않는 페이지를 실제로 존재하는 프레임에 할당하기 위해서이다.
<실제 램공간> 총 4기가
--------------------------------------------------
page frame 4키로바이트
--------------------------------------------------
--------------------------------------------------
page frame 4키로바이트
--------------------------------------------------
--------------------------------------------------
page frame 4키로바이트
--------------------------------------------------
...... ......
--------------------------------------------------
page frame 4키로바이트
--------------------------------------------------
--------------------------------------------------
page frame 4키로바이트
--------------------------------------------------
--------------------------------------------------
page frame 4키로바이트
--------------------------------------------------
이놈도 2의 20승 만큼의 프레임이 존재한다.
실제 램공간에서 특정 프레임의 주소를 프레임넘버라고 한다.
실제램에서 물리주소 표현 32비트 컴퓨터 기준
--------------------------------------------------
| frame number 20비트 | offset 12비트 |
--------------------------------------------------
만약에 CPU가 프로그램을 실행하면 CPU의 PC가 해당되는 page를 가리키게 된다(즉 논리주소를 가리킨다). 그리고 램에 저장되어 있는 page table이라는 공간이 있는데 거기에는 page number와 frame number , valid bit로 구분하는 매핑 맵이있다. 그 page table에서 PC가 가리킨 논리주소를 조회해서 해당 실제 물리주소(page frame)을 알아낸다음 이 물리 주소를 또 다른 레지스터인 MAR(Memory Address Register)에 저장하고, CPU는 이 레지스터의 주소 값을 읽어와 메인 메모리에서 인스트럭션을 가져오고(fetch) 실행(execute)한다.
페이지 테이블은 프로그램이 실행되면서 생기고 동시에 실질적으로 논리주소 4기가를 부여해준것과 같다.
프로세스가 여러개가 있으면 각각의 프로세스는 각각의 페이지 테이블 하나씩 같고 있다.
- 요구 페이징
가상 메모리는 요구 페이징으로 구현한다. 요구 페이징이란 프로세스를 실행할 때 모든 페이지를 프레임에 매핑하는 것이 아니라, 필요한 페이지만 메인 메모리에 올려 실행하는 것을 말한다. 프로세스가 처음 실행될 때 운영체제는 페이지 테이블을 메인 메모리에 만들고 실행에 필요할 것 같은 페이지만 먼저 프레임에 매핑한다. 이러한 방식을 preparing이라고 부른다.
페이지 테이블에서 페이지와 프레임을 매핑할 때는 메인 메모리에 올라와야 하는 페이지의 코드를 하드디스크에서 가져와 프레임을 생성하고 페이지와 매핑한다. 매핑한 페이지는 페이지 테이블의 유효 비트를 1로 바꾼다. 아직 필요하지 않아 프레임에 매핑하지 않은 페이지는 하드디스크에 있는 페이지의 위치로 초기화하고 유효 비트를 0으로 만든다. 이후 CPU가 페이지를 요청했을 때 프레임으로 매핑한 상태가 아니라면 빈 프레임에 페이지를 매핑한다.
- 페이지 폴트
CPU가 요청한 페이지가 메인 메모리에 없을 때 발생한다. 이는 유효 비트를 확인하면 알 수 있는데, 유효 비트가 0이면 메인 메모리에 존재하지 않는 것이다. 페이지 폴트가 발생하면 해당 페이지를 하드디스크에서 가져와 빈 프레임에 할당하면 된다.
이때 메인 메모리에 빈 프레임이 없다면 페이지 교체 알고리즘에 의해 메인 메모리에 있는 페이지를 하드디스크로 내리고 요청된 페이지를 메인 메모리로 올린다. 이때 페이지 교체 알고리즘에 의해 메인 메모리에서 하드디스크로 내려지는 페이지를 희생 페이지, 페이지를 메인 메모리에서 하드디스크로 내리는 것을 page-out, 하드디스크에서 메인 메모리로 올리는 것을 page-in이라고 한다.
중요한 점은 페이지 폴트가 자주 일어나면 프로그램 성능이 상당히 떨어진다는 점이다. 데이터를 읽어오는 속도 때문이다. 앞서 말한 것처럼 메모리에서 데이터를 읽어올 때는 20~100사이클이 걸리지만 하드디스크에서 읽어올 때는 엄청나게 많은 사이클이 걸린다.
페이지 폴트가 일어날 확률을 줄이려면 지역성을 고려하면서 프로그래밍해야 한다. 예를 들어 프로그램에서 데이터를 저장할 때 연결 리스트 자료 구조를 사용했더니 메모리 단편화가 심하게 발생해 관련 데이터가 멀리 흩어지면서 페이지 폴트가 빈번하게 발생해 성능이 떨어질 수 있다.
- TLB(Translation Lookaside Buffer)
매번 cpu가 요청할때마다 logical 주소를 pysical주소로 바꾸게 되면 이것도 매번 매핑하면 시간이 걸리기 때문에 이 시간을 절약하고자 cpu와 page table 사이에 캐시를 둔다 이놈을 TLB 라고 한다. cpu가 page table로 접근하기 전에 TLB한테 물어본다. TLB는 page table의 일부 정보를 임시저장하고 있기때문에 그게 가능하다. CPU가 TLB에게 물어봤는데 요구하는 정보가 있다. 그럴때는 TLB hit라고 한다. 요구하는 정보가 없을때는 TLB miss라고 한다. TLB가 page table의 일부정보를 임시저장하는 원리는 CPU가 TLB에게 물어봤는데 TLB miss가 일어나면 page table의 데이터를 가져와 바로 cpu로 가는게 아니라 TLB에 해당 정보를 임시저장하고 CPU로 보내주게 된다.
-
CPU에서 PC 와 MAR 의 구분 PC = 가상주소공간에서 주소를 가리킴 MAR = 실제주소공간에서 주소를 가리킴
-
가상메모리의 구현
1) paging
2) segmentation
3) 최신 OS는 segmentation with paging을 쓴다.
- CPU에서 프로세스가 실행될때 상태
오늘날의 운영체제는 대부분 멀티프로세스 기반이다. 프로세스 여러 개를 동시에 실행할 수 있다. 프로세스를 실행하려면 독자적인 메모리 공간과 CPU가 필요합니다. 메모리는 이전 장에서 다룬 가상 메모리를 사용해서 해결했다. CPU는 한 번에 하나의 프로세스에만 할당할 수 있습니다. 여러 프로세스가 완벽하게 ‘동시에’ 실행되는 건 불가능하다. 우리 눈에만 그렇게 보일 뿐이고 프로세스는 프로그램을 더블클릭하는 순간부터 창을 닫을 때까지 계속해서 실행 상태로 있는 것이 아니다. 프로세스 상태는 상황에 따라 변합니다.
1) created : 프로그램을 더블클릭했을 때 프로세스가 생성되면서 실행 가능 상태가 된다. 곧바로 실행 상태가 되는 것이 아니라, 우선 실행 가능 상태가 되어 실행 중인 프로세스와 우선순위를 비교한 다음 우선순위가 높으면 실행하고 아니면 실행 가능 상태에서 순서를 기다리는 방식이다.
2) running : 프로세스가 운영체제로부터 CPU를 할당받아 실행되고 있는 상태
3) waiting : 실행 가능 상태의 프로세스는 언제든지 실행될 준비가 되어 있다. 운영체제는 인터럽트가 발생했을 때 실행 가능 상태의 프로세스 중 다음으로 CPU를 할당받아 실행될 프로세스를 결정한 후 실행 중인 프로세스와 교체한다. 이때 다음으로 실행될 프로세스에 CPU를 할당하는 것을 디스패치(dispatch)라고 하고, 실행 중이던 프로세스에서 CPU를 해제하는 것을 프리엠션(preemption)이라고 한다.
4) blocked : 프로세스가 I/O(입출력) 작업을 하면 CPU를 해제하고 보류 상태로 변경된다. 이때 실행 가능 상태의 프로세스 중 하나가 CPU를 할당받는다. 보류 상태에 들어간 프로세스는 I/O 작업이 모두 끝나면 실행 가능 상태로 변경된다. 중요한 점은 I/O 작업이 완료된 다음 바로 실행 상태로 변경되는 것이 아니라, 실행 가능 상태가 되어 실행되기를 기다린다는 점이다. 또한 실행 대기 상태(Waiting)와 보류(Blocked) 상태를 구분할 수 있어야 한다. 실행 대기 상태는 언제든지 다시 실행될 수 있는 상태를 말하지만 보류 상태는 I/O 작업이 끝나기 전에는 실행이 불가능한 상태다.
5) terminated : 프로세스 실행이 완료되어 메인 메모리에서 사라진다.
-
어떤 프로세스가 CPU를 확보할 것인가 언제 확보할 것인가 결정하는 것은 OS의 스케쥴러가 수행한다.
- 스케쥴링을 할때
- 새로운 프로세스가 실행 또는 종료될때
- CPU를 확보하고 실행중이던 프로세스가 I/O 작업으로 돌입했을때
- time slice
- 스케쥴링 알고리즘
엄청 많지만 두가지만 알자
1) 우선순위 알고리즘
프로세스에 우선순위를 매겨 우선순위가 높은 프로세스를 먼저 실행합니다. 어떤 프로세스가 CPU를 할당받고 실행되는 도중에 우선순위가 높은 프로세스가 생성되면 스케줄러는 실행 중인 프로세스를 실행 가능 상태로 만들고 우선순위가 높은 프로세스를 실행합니다. 계속해서 우선순위가 높은 프로세스가 생성되면 우선순위가 낮은 프로세스는 계속 CPU를 할당받지 못하는 현상이 발생하는데 이를 기아 상태(starvation)라고 합니다. 이를 해결하기 위해 우선순위가 낮은 프로세스가 일정 시간 CPU를 할당받지 못하면 우선순위를 높여 실행될 수 있도록 만드는데 이러한 방법을 에이징(aging)이라고 합니다.
2) 라운드 로빈
우선순위가 완벽하게 동일한 경우에는 이때 라운드 로빈을 쓰게 된다. 줄선대로 작업을 수행하는 …
각각의 프로세스에는 동일한 time slice를 부여하여 작업중에 time slice가 완료되면 짤없이 다시 맨 뒤로 줄서야 한다. 그리고 자기차례가 오면 마저 작업을하고 이런식으로..
실행 가능 상태에 있는 프로세스들을 순서대로 가져와 일정 시간 동안 CPU를 할당하는 방식이다. 모든 프로세스에 같은 시간이 부여됩니다. 이때 프로세스에 부여된 일정 시간을 time slice 혹은 quantum이라고 한다. 라운드 로빈을 이용하면 모든 프로세스가 동시에 실행되는 것처럼 보인다. 대표적인 선점형 스케줄링이다. 라운드 로빈 스케줄링에서 가장 중요한 것은 타임 슬라이스를 얼마로 정하느냐이다. 너무 짧으면 컨텍스트 스위칭이 너무 자주 일어나 시스템에 부담이 되고 너무 길면 멀티태스킹을 구현하는 데 문제가 발생한다.
-
OS의 중에는 선점형 스케쥴링을 하는놈(pre-emptive OS)과 비선점형 스케쥴링 하는 놈으로 구분할 수 있다. 현재 지금 시중에 있는 거의 모든 OS는 선점형 스케쥴링 방식을 쓰고 있다. 작업중인 프로세스를 끌어내리고 우선순위가 높은 프로세스를 작업시킬 수 있다. 이 말은 멀티테스킹이 가능하다라는 말과 동일하다. 비선점형은 강제적으로 양보를 수행하는 것이 아니라 명시적으로 양보하고 , I/O 작업할때만 양보한다.
-
컨텍스트 스위칭
프로세스 두 개가 같은 프로그램에서 만들어졌을 때 두 프로세스는 어떤 차이가 있냐면 우선 두 프로세스는 독립된 메모리 공간을 가진다. 현재 실행 중인 인스트럭션이나 스택 프레임이 다를 것이다. 실행 중인 인스트럭션이 다르므로 프로그램 카운터 값도 다르고 스택 프레임도 다르니 스택 포인터와 프레임 포인터와 범용 레지스터의 값도 모두 다르게 된다. 프로세스가 실행되려면 다양한 CPU 레지스터 값과 프로세스 상태 정보 등이 필요하다. 그러므로 프로세스가 실행 상태에서 실행 가능 상태로 변경될 때 이러한 정보를 메모리 어딘가에 저장해야 한다. 프로세스의 CPU 상태와 프로세스의 상태를 저장해 둔 메모리 블록을 프로세스 제어 블록이라고 한다.
PCB 데이터는 프로세스가 실행 가능 상태에서 실행 상태로 바뀔 때도 필요하다. 프로그램 카운터를 예로 들면 PCB에 저장된 프로그램 카운터 값을 CPU로 가져와야 이전에 실행한 마지막 인스트럭션의 다음 인스트럭션을 가져와 실행할 수 있다.
스케줄러가 실행 중인 프로세스에서 CPU를 해제하고 실행 가능 상태의 프로세스에 CPU를 할당할 때, 실행 중인 프로세스의 CPU 상태 정보를 그 프로세스의 PCB에 저장하고 곧 실행될 프로세스의 PCB에서 이전 CPU 상태 정보를 CPU로 가져오는 것을 컨텍스트 스위칭이라고 한다. CPU 상태를 컨텍스트라고 부르는데 말 그대로 현재 CPU의 레지스터 값들을 ‘전환(switching)’하는 것이다.
- 쓰레드
1) 프로세스 안의 실행 흐름의 단위로 스케줄러에 의해 CPU를 할당받을 수 있는 인스트럭션의 나열
2) process에 있는 실행흐름
3) 프로세스가 껍질, 쓰레는 그 안에 알맹이 (인스트럭션을 실행하는 흐름)
4) 단일 쓰레드 vs 멀티쓰레드
5) 단일쓰레드(싱글코어) : 인스트럭션을 한땀한땀 한줄로 시행 / 싱글코어 싱글쓰레드
6) 멀티쓰레드(멀티코어) : 그 한줄을 쓰레드 개수 만큼 쪼개서 동시에 시행함 즉 4개의 쓰레드라면 4개의 쓰레드가 동시에 하나의 일을 쪼개서 시행함, 위의 싱글코어 싱글쓰레드 보다 1/4만큼 시간이 절약된다. / 멀티코어 멀티쓰레드
7) 스레드는 각자 독립적인 스택 세그먼트를 갖지만, 코드, 데이터, 힙은 다른 스레드와 공유한다. 데이터 세그먼트나 힙 세그먼트에 공유 데이터를 두면 모든 스레드가 이용할 수 있다.
- 프로세스와 쓰레드의 차이 :
멀티프로세스(multi-process)는 프로세스 여러 개를 동시에 실행하는 것을 말하고, 멀티스레드(multi-thread)는 스레드를 여러 개 만들어 동시에 실행하는 것을 말한다.
- 멀티쓰레드를 이용한 코딩 시
1) 레이스 컨디션(경쟁조건)과 데드락(교착상태)를 가장조심해야 한다.
2) 레이스 컨디션은 공유자원(전역변수, 힙 등)의 여러 쓰레드가 한번에 접근하여 값을 수정하려고 할때 문제가 발생하는 경우
3) 쓰레드 세이프 여러 쓰레드가 한번에 공유자원에 접근하더라도 문제가 발생하지 않을때
4) 레이스 컨디션은 상호배제라는 것으로 해결한다.
예를들어 쓰레드 하나가 g_count 함수(공유자원)에 접근하여 값을 수정하는 순간 다른 쓰레드는 락이 걸려서 접근하지 못한다. 그리고 접근한 쓰레드가 작업이 끊나고 lock.release를 하는 순간 다른 쓰레드가 와서 사용하고 이런식으로 진행된다.