인프런 워밍업 클럽 - CS Day 9
Algorithm참고 : https://visualgo.net/en/sortingBubble Sort인접한 두 원소를 비교하여 두 원소의 위치를 교환한다.과정배열을 처음부터 끝까지 순회하며 인접한 두 원소를 비교한다.왼쪽 원소가 오른쪽 원소보다 크면 두 원소를 교환한다.이 과정을 배열이 정렬될 때까지 반복한다.시간 복잡도O(n^2)장점이해와 구현이 간단한다.단점성능이 좋지 않다.Selection Sort배열에서 최솟값을 찾아 맨 앞으로 이동시킨다.과정정렬되지 않은 부분에서 최솟값을 찾는다.찾은 최솟값을 정렬되지 않은 부분의 첫 번째 원소와 교환한다.정렬된 부분을 한 칸 늘리고, 정렬되지 않은 부분에서 위 과정을 반복한다.시간 복잡도O(n^2)장점이해와 구현이 간단하다.단점성능이 좋지 않다.OSProgramming LanguageCompile Language개발자가 코드를 작성하고 컴파일을 수행하여 0과 1로된 기계어로 실행파일을 만든다.→ 기계어로 되어 있어 실행 속도가 인터프리터 언어에 비해 빠르다.컴파일 과정에서 개발자의 문법오류를 체크한다.ex) C, C++, C#Interpreter Language개발자가 작성한 코드를 미리 기계어로 만들어 놓지 않고 실행시 코드를 한줄씩 해석해 실행하는 언어→ 미리 검사를 하지 않기 때문에 실행할 때 오류가 발생할 수 있고, 컴파일 언어보다 느리다.ex) Javascript, Python, Ruby프로세스의 영역코드 영역실행해야 할 코드가 들어간다.데이터 영역전역 변수나 배열이 들어가는 영역스택 / 힙프로세스가 실행될 때 할당되는 메모리스택 : 지역변수와 함수 관련 값들이 저장힙 : 실행 중에 메모리 공간을 할당할 수 있는 유동적인 공간Compile 언어가 Process가 되는 방법개발자가 코드 작성전처리 단계 실행개발자가 작성한 코드를 확인하고 전처리 구문을 처리한다.C에서는 #이라는 키워드로 선언된다.ex) #include<stdio.h>, #define MY_NUMBER 100코드에 있는 모든 주석은 삭제된다.결과물로 .i 파일이 생성된다.전처리기에서 나온 결과파일을 컴파일러가 처리한다.컴파일러는 .i 파일을 기계어에 가까운 어셈블리어로 변환시킨다.결과물로 .s 파일이 생성된다.어셈블러 작업이 수행된다.오브젝트 파일.o로 변환된다.오브젝트 파일은 0과 1로 구성되어 있다.코드영역과 데이터 영역이 나뉘어져 있다.링커 작업이 수행된다.모든 오브젝트 파일을 하나의 코드 영역과 데이터 영역으로 묶어준다.실제로 실행될 주소를 매핑시켜준다.결과물로 .exe 파일이 생성된다.사용자가 .exe파일을 실행시키면 OS가 프로세스를 생성한다.OS는 파일에 있는 코드 영역과 데이터 영역을 가져와 프로세스의 코드 영역과 데이터 영역에 넣어주고, 빈 상태의 스택과 힙을 할당한다.PCB를 만들어 프로세스를 관리가 가능하게 한다.PC(프로그램 카운터)에 다음 실행할 명령어의 주소를 생성한 프로세스의 코드영역의 첫번째 주소로 설정한다.→ OS의 CPU 스케줄링에 따라서 프로세스가 실행되다가 작업을 마친다.메모리 종류레지스터가장 빠른 기억장소, CPU 내에 존재한다.휘발성 메모리CPU를 나타내는 값에서 32bit, 64bit를 의미하는 것이 레지스터의 크기이다.CPU는 계산을 수행할 때 메인 메모리에 있는 값을 레지스터로 가져와서 계산한다.계산 결과는 메인 메모리에 저장한다.캐시휘발성 메모리속도가 매우 빠른 레지스터와 레지스터에 비해 상대적으로 느린 메인 메모리 사이의 속도 간극을 메우기 위해 필요한 데이터를 미리 가져와 저장하는 저장소성능의 이유로 여러 개가 존재한다.L1, L2, L3→ 숫자가 커질 수록 느린 캐시CPU가 값을 요청해 레지스터로 값을 옮겨야 한다면 빠른 캐시를 순차적으로 확인하고, 캐시에 데이터가 없으면 메인 메모리를 조회한다.ex) L1 → L2 → L3 → 메인 메모리보조 저장장치(HDD, SSD)비휘발성 메모리메인 메모리실제 운영체제와 다른 프로세스들이 올라가는 공간휘발성 메모리데이터를 저장하기 보다는 실행중인 프로그램만 저장한다.OS는 메모리를 관리하기 위해서 1Byte 크기로 구역을 나누고 숫자(주소)를 매긴다.32bit CPU, 64bit CPU32bit CPU레지스터, ALU, Data Bus : 32bit메모리 : 2^32 = 4GB64bit CPU레지스터, ALU, Data Bus : 64bit메모리 : 2^64 = 16384PiB64bit CPU가 32bit CPU 보다 한번에 처리할 수 있는 양이 많기 때문에 속도가 더 빠르다.물리 주소 & 논리 주소물리 주소 공간 : 0x0부터 시작하는 주소 공간논리 주소 : 사용자 관점에서 바라 본 주소 공간사용자는 물리 주소를 몰라도 논리 주소로 물리 주소에 접근할 수 있다.OS를 위한 공간은 따로 확보한다.경계 레지스터H/W적으로 OS 공간과 사용자 공간을 나누는 레지스터CPU 내에 존재하는 레지스터메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났다면 검사하고, 벗어났다면 해당 프로세스를 종료시킨다.절대 주소 & 상대 주소개발자가 프로그램이 실행될 주소를 신경쓰지 않고 개발할 수 있는 이유→ 컴파일러가 컴파일을 할 때 메모리 0번지에서 실행한다고 가정하기 때문절대 주소 : 메모리 관리자가 바라본 프로세스가 올라간 물리 주소상대 주소 : 사용자가 바라보는 논리 주소재배치 레지스터프로그램의 시작 주소가 저장되어 있다.사용자가 요청한 논리 주소의 데이터를 물리 주소로 치환해준다.사용자가 메모리에 접근할 때마다 논리 주소를 물리 주소로 치환해준다.메모리 할당 방식메모리 오버레이메모리보다 용량이 큰 프로그램을 실행시키는 방법큰 프로그램을 메모리에 올릴 수 있을 정도로 분할하여 일부만 실행하고, 실행되지 않은 프로그램은 HDD의 스왑 영역에 저장하는 방식Swap스왑영역에 있는 데이터 일부를 메모리로 가져오고 메모리에 있는 데이터를 스왑영역으로 옮기는 것가변 분할 방식(= Segmentation, 세그멘테이션)프로세스의 크기에 따라 메모리를 나누는 방식하나의 프로세스가 메모리에 연속된 공간에 할당된다.→ 연속 메모리 할당이라고 한다.장점메모리에 연속된 공간에 할당된다.→ 내부 단편화가 없다.단점외부 단편화가 발생한다.고정 분할 방식(= Paging, 페이징)프로세스의 크기와는 상관없이 정해진 크기로 나누 는 방식하나의 프로세스가 메모리에 분산되어 할단된다.→ 비연속 메모리 할당이라고 한다.장점구현이 간단하고 오버헤드가 적다.단점작은 프로세스도 큰 영역에 할당되어 내부 단편화가 발생한다.내부 단편화프로세스에 필요한 메모리보다 더 큰 고정 크기의 메모리 블록이 할당될 때 발생한다.할당된 메모리와 실제 사용된 메모리 사이의 차이로 인해 메모리 공간이 낭비된다.고정 크기 분할 방식에서 주로 발생한다.해결 방법은 딱히 없고, 분할되는 크기를 조절하여 내부 단편화를 최소화한다.외부 단편화메모리 할당과 해제를 반복하면서 작은 빈 공간들이 메모리 곳곳에 흩어져 생기는 현상전체 가용 메모리는 충분하지만, 연속된 큰 블록을 할당할 수 없는 상황을 만든다.가변 분할 방식에서 주로 발생한다.조각모음외부 단편화가 발생한 공간을 합쳐주는 작업현재 메모리에서 실행되고 있는 프로세스들의 작업을 일시 주징하고, 메모리 공간을 이동시켜야 한다.→ 오버헤드가 발생한다.버디 시스템가변 분할 방식 + 고정 분할 방식오늘날의 OS가 채택한 메모리 할당 방식2의 제곱으로 메모리를 분할하여 할당하는 방식→ 근접한 메모리 공간을 합치기 쉽다.→ 조각 모음보다 훨씬 간단하다.장점가변 분할 방식처럼 프로세스 크기에 따라 할당되는 메모리 크기가 달라지고, 외부 단편화를 방지하기 위해 메모리 공간을 확보하는 것이 간단하다.내부 단편화가 발생할 수 있지만 고정 분할 방식에 비해 많은 공간이 낭비되지는 않는다.
