인프런 워밍업 클럽 - CS Day 9

Algorithm

참고 : https://visualgo.net/en/sorting

Bubble Sort

• 인접한 두 원소를 비교하여 두 원소의 위치를 교환한다.

과정

• 배열을 처음부터 끝까지 순회하며 인접한 두 원소를 비교한다.

• 왼쪽 원소가 오른쪽 원소보다 크면 두 원소를 교환한다.

• 이 과정을 배열이 정렬될 때까지 반복한다.

시간 복잡도

• O(n^2)

장점

• 이해와 구현이 간단한다.

단점

• 성능이 좋지 않다.

Selection Sort

• 배열에서 최솟값을 찾아 맨 앞으로 이동시킨다.

과정

• 정렬되지 않은 부분에서 최솟값을 찾는다.

• 찾은 최솟값을 정렬되지 않은 부분의 첫 번째 원소와 교환한다.

• 정렬된 부분을 한 칸 늘리고, 정렬되지 않은 부분에서 위 과정을 반복한다.

시간 복잡도

• O(n^2)

장점

• 이해와 구현이 간단하다.

단점

• 성능이 좋지 않다.

OS

Programming Language

• Compile Language

  • 개발자가 코드를 작성하고 컴파일을 수행하여 0과 1로된 기계어로 실행파일을 만든다.
    → 기계어로 되어 있어 실행 속도가 인터프리터 언어에 비해 빠르다.

  • 컴파일 과정에서 개발자의 문법오류를 체크한다.
    ex) C, C++, C#

• Interpreter Language

  • 개발자가 작성한 코드를 미리 기계어로 만들어 놓지 않고 실행시 코드를 한줄씩 해석해 실행하는 언어
    → 미리 검사를 하지 않기 때문에 실행할 때 오류가 발생할 수 있고, 컴파일 언어보다 느리다.
    ex) Javascript, Python, Ruby

프로세스의 영역

• 코드 영역

  • 실행해야 할 코드가 들어간다.

• 데이터 영역

  • 전역 변수나 배열이 들어가는 영역

• 스택 / 힙

  • 프로세스가 실행될 때 할당되는 메모리

  • 스택 : 지역변수와 함수 관련 값들이 저장

  • 힙 : 실행 중에 메모리 공간을 할당할 수 있는 유동적인 공간

Compile 언어가 Process가 되는 방법

1. 개발자가 코드 작성

2. 전처리 단계 실행

   • 개발자가 작성한 코드를 확인하고 전처리 구문을 처리한다.

   • C에서는 #이라는 키워드로 선언된다.
     ex) #include<stdio.h>, #define MY_NUMBER 100

   • 코드에 있는 모든 주석은 삭제된다.

   • 결과물로 .i 파일이 생성된다.

3. 전처리기에서 나온 결과파일을 컴파일러가 처리한다.

   • 컴파일러는 .i 파일을 기계어에 가까운 어셈블리어로 변환시킨다.

   • 결과물로 .s 파일이 생성된다.

4. 어셈블러 작업이 수행된다.

   • 오브젝트 파일.o로 변환된다.

   • 오브젝트 파일은 0과 1로 구성되어 있다.

   • 코드영역과 데이터 영역이 나뉘어져 있다.

5. 링커 작업이 수행된다.

   • 모든 오브젝트 파일을 하나의 코드 영역과 데이터 영역으로 묶어준다.

   • 실제로 실행될 주소를 매핑시켜준다.

   • 결과물로 .exe 파일이 생성된다.

6. 사용자가 .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 CPU

• 32bit CPU

  • 레지스터, ALU, Data Bus : 32bit

  • 메모리 : 2^32 = 4GB

• 64bit CPU

  • 레지스터, ALU, Data Bus : 64bit

  • 메모리 : 2^64 = 16384PiB

• 64bit CPU가 32bit CPU 보다 한번에 처리할 수 있는 양이 많기 때문에 속도가 더 빠르다.

물리 주소 & 논리 주소

• 물리 주소 공간 : 0x0부터 시작하는 주소 공간

• 논리 주소 : 사용자 관점에서 바라 본 주소 공간

• 사용자는 물리 주소를 몰라도 논리 주소로 물리 주소에 접근할 수 있다.

• OS를 위한 공간은 따로 확보한다.

경계 레지스터

• H/W적으로 OS 공간과 사용자 공간을 나누는 레지스터

• CPU 내에 존재하는 레지스터

• 메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났다면 검사하고, 벗어났다면 해당 프로세스를 종료시킨다.

절대 주소 & 상대 주소

• 개발자가 프로그램이 실행될 주소를 신경쓰지 않고 개발할 수 있는 이유
  → 컴파일러가 컴파일을 할 때 메모리 0번지에서 실행한다고 가정하기 때문

• 절대 주소 : 메모리 관리자가 바라본 프로세스가 올라간 물리 주소

• 상대 주소 : 사용자가 바라보는 논리 주소

재배치 레지스터

• 프로그램의 시작 주소가 저장되어 있다.

• 사용자가 요청한 논리 주소의 데이터를 물리 주소로 치환해준다.

• 사용자가 메모리에 접근할 때마다 논리 주소를 물리 주소로 치환해준다.

메모리 할당 방식

메모리 오버레이

• 메모리보다 용량이 큰 프로그램을 실행시키는 방법

• 큰 프로그램을 메모리에 올릴 수 있을 정도로 분할하여 일부만 실행하고, 실행되지 않은 프로그램은 HDD의 스왑 영역에 저장하는 방식

Swap

• 스왑영역에 있는 데이터 일부를 메모리로 가져오고 메모리에 있는 데이터를 스왑영역으로 옮기는 것

가변 분할 방식(= Segmentation, 세그멘테이션)

• 프로세스의 크기에 따라 메모리를 나누는 방식

• 하나의 프로세스가 메모리에 연속된 공간에 할당된다.
  → 연속 메모리 할당이라고 한다.

장점

• 메모리에 연속된 공간에 할당된다.
  → 내부 단편화가 없다.

단점

• 외부 단편화가 발생한다.

고정 분할 방식(= Paging, 페이징)

• 프로세스의 크기와는 상관없이 정해진 크기로 나누는 방식

• 하나의 프로세스가 메모리에 분산되어 할단된다.
  → 비연속 메모리 할당이라고 한다.

장점

• 구현이 간단하고 오버헤드가 적다.

단점

• 작은 프로세스도 큰 영역에 할당되어 내부 단편화가 발생한다.

내부 단편화

• 프로세스에 필요한 메모리보다 더 큰 고정 크기의 메모리 블록이 할당될 때 발생한다.

• 할당된 메모리와 실제 사용된 메모리 사이의 차이로 인해 메모리 공간이 낭비된다.

• 고정 크기 분할 방식에서 주로 발생한다.

• 해결 방법은 딱히 없고, 분할되는 크기를 조절하여 내부 단편화를 최소화한다.

외부 단편화

• 메모리 할당과 해제를 반복하면서 작은 빈 공간들이 메모리 곳곳에 흩어져 생기는 현상

• 전체 가용 메모리는 충분하지만, 연속된 큰 블록을 할당할 수 없는 상황을 만든다.

• 가변 분할 방식에서 주로 발생한다.

조각모음

• 외부 단편화가 발생한 공간을 합쳐주는 작업

• 현재 메모리에서 실행되고 있는 프로세스들의 작업을 일시 주징하고, 메모리 공간을 이동시켜야 한다.
  → 오버헤드가 발생한다.

버디 시스템

• 가변 분할 방식 + 고정 분할 방식

• 오늘날의 OS가 채택한 메모리 할당 방식

• 2의 제곱으로 메모리를 분할하여 할당하는 방식
  → 근접한 메모리 공간을 합치기 쉽다.
  → 조각 모음보다 훨씬 간단하다.
  

장점

• 가변 분할 방식처럼 프로세스 크기에 따라 할당되는 메모리 크기가 달라지고, 외부 단편화를 방지하기 위해 메모리 공간을 확보하는 것이 간단하다.

• 내부 단편화가 발생할 수 있지만 고정 분할 방식에 비해 많은 공간이 낭비되지는 않는다.