map함수

먼저 map 함수는 map(function, iterable) 형태로 이루어져 있습니다. map 함수의 동작은 두 번째 들어온 반복 가능한 인자를 첫 번째 들어온 함수 인자에 하나씩 집어 넣어 실행시킵니다. 코딩 테스트에서 여러 개의 입력 값을 한 번에 받고 싶을 때나 배열에 있는 값들을 하나의 문자열로 출력하고 싶을 때 사용합니다. 또한 map 함수의 반환 값은 map 객체 형이기 때문에 list나 tuple 등으로 형변환을 시켜주어야 합니다.

join 함수

join 함수는 매개 변수로 들어온 list에 있는 요소 하나씩을 모두 합쳐서 하나의 문자열로 변환하는 함수입니다. ''.join(리스트)의 형태로 주로 사용하며 '_'.join(리스트)와 같이 구분자를 넣어주면 요소와 요소 사이에 구분자를 추가하여 문자열을 만들 수 있습니다.

예제

위의 map 함수와 join 함수를 이용하여 다음과 같이 사용할 수 있습니다. 만약 arr = [1, 2, 3, 4, 5]와 같이 정수 배열이 있을 때 문자열 "12345"를 출력하고 싶으면 다음과 같이 map과 join을 이용하면 됩니다.

arr = [1, 2, 3, 4, 5]
str_arr = ''.join(map(str, arr))

이 경우 arr에 있는 요소 하나 하나에 str함수를 적용하여 문자열로 형 변환을 시켜준 상태에서 모든 요소를 합친 상황입니다.

배열에서 특정 원소 삭제하기

배열에서 특정 원소를 삭제해야 하는 경우가 있습니다. 이 때 del 함수나 remove 함수를 이용해 삭제 가능합니다. 먼저 del 함수는 배열의 인덱스를 활용하여 배열의 원소를 삭제합니다.

arr = [1, 2, 3, 4, 5]
del arr[3]

del arr[3]이므로 3번 인덱스에 존재하는 4가 삭제되어 arr = [1, 2, 3, 5]가 됩니다. 한 번에 여러 개의 원소를 삭제하고 싶을 때에는 del arr[1:3]과 같이 범위를 지정하는 :를 활용하면 됩니다. 이 때 시작 인덱스는 1번이고 마지막 인덱스는 3이 아닌 2임에 유의해야 합니다. 따라서 1, 2번 인덱스의 값인 2, 3이 사라지고 arr = [1, 4, 5]가 됩니다.

remove를 이용하면 원소의 값을 이용해 원소를 삭제할 수 있습니다.

arr = [1, 2, 3, 4, 5]
arr.remove(4)

위의 예시와 같이 remove안에 삭제하고자 하는 원소를 적으면 배열에서 4가 삭제되어 arr = [1, 2, 3, 5]가 남습니다.

배열의 모든 원소를 삭제하고 싶으면 다음과 같이 clear()를 사용하면 됩니다.

arr = [1, 2, 3, 4, 5]
arr.clear()

문자열 안에서 문자 찾기

문자열.find(찾고자 하는 문자)를 이용하면 찾고자 하는 문자의 인덱스 값을 반환합니다. 만약 찾고자 하는 문자가 문자열에 존재하지 않으면 -1을 반환합니다.

s = 'ABCDEFG'
s.find('A')

위의 예시의 경우 A가 0번 인덱스에 위치하므로 0을 반환합니다. 문자열.startswith(문자, 찾기 시작할 지점)와 문자열.endswith(문자, 찾기 시작할 지점, 끝날 지점)을 통해 시작하려는 문자와 끝을 내는 문자가 인자에 있는 문자와 일치하는지 확인할 수 있습니다. 만약 일치한다면 True를 반환하고 그렇지 않으면 False를 반환합니다.

s = 'ABCDEFG'
s.startswith('D')
s.startswith('C', s.find('C'))
s.endswith('G')
s.endswith('G', 0, 2)

딕셔너리

딕셔너리를 다른 배열과 같은 자료구조에 비해 적게 사용해서 그런지 항상 헷갈립니다.

• 딕셔너리에 새로운 key와 value를 추가하고 싶을 때 dict에 key가 있는지 확인 후 없으면 dict[key] = value 형태로 추가합니다.

• 딕셔너리에 있는 키 값들만 추출하고 싶을 때 dict.keys()를 사용하면 딕셔너리 안의 키 값들만 반환됩니다.

• 딕셔너리에 있는 value 값들만 추출하고 싶을 때 dict.values()를 사용하면 딕셔너리 안의 value 값들만 반환됩니다.

• 딕셔너리를 정렬하기 위해서는 dict.items()를 이용하면 됩니다.

  # 키 값 기준으로 오름차순으로 정렬합니다.
  d = sorted(dict.items())
  # 키 값 기준으로 내림차순으로 정렬합니다.
  d = sorted(dict.items(), reverse = True)
  # value 값 기준으로 정렬합니다.
  d = sorted(dict.items(), key = lambda x : x[1]) 

먼저 주어진 수들을 합칠 수 있는 방법을 모두 나열한 뒤 가장 큰 값을 찾는 것은 안됩니다. 제한 사항에 "numbers의 길이는 1 이상 100,000 이하입니다."가 있기 때문에 최악의 경우 100000!만큼 연산을 해야 하고 이는 시간 초과를 발생시킬 수 있는 너무나 큰 숫자 입니다.

STEP 1

가장 큰 수가 나오기 위해서는 각 numbers의 원소들의 가장 맨 앞자리 수가 큰 순서로 정렬을 하면 됩니다. [3, 30, 34, 5, 9] 문제의 예시처럼 이 경우 맨 앞자리 수가 9가 제일 크므로 9를 먼저 놓고 그 다음 5를 놓습니다. 이 부분은 정수 배열을 문자열 배열로 바꾼 뒤 정렬하면 해결됩니다. 왜냐하면 문자열은 맨 첫 글자의 아스키코드 값을 기준으로 정렬하기 때문입니다.

STEP 2

문제는 3과 30, 34 입니다. 3개의 숫자 모두 앞자리가 3으로 동일하지만 3과 30중에는 3이 앞에 와야합니다. 왜냐하면 303일 경우와 330과 같은 경우가 만들어지기 때문입니다. 즉 3은 33이하의 숫자보다는 우선순위를 크게 가져야 합니다. [3, 32], [3, 31], [3, 30]의 경우 등을 생각해보면 됩니다. 이러한 경우 어떻게 해결해야 할까요?

바로 원소를 3번 이어붙이는 것 입니다. "numbers의 원소는 0 이상 1,000 이하입니다." 해당 조건에서 우리는 모든 원소가 0~1000 에 속한다는 것을 알 수 있습니다. 따라서 3과 30을 비교할 때 3을 3번 이어 붙이면 333이 되고 30을 3번 이어 붙이면 303030이 됩니다. 이를 비교해보면 333문자열이 더 큰 것을 알 수 있고 이를 통해 333, 303030, 343434의 순서가 343434, 333, 303030이 되는 것을 알 수 있습니다.

lambda를 이용한 sort

위의 step2를 구현하기 위해서는 문자열을 3번 이어붙인 상태를 기준으로 정렬을 수행해야 합니다. 물론 3개를 이어붙인 배열을 하나 만들어 그 상태로 정렬을 수행해도 되지만 sort에서 lambda를 이용하면 사용자가 원하는 기준으로 정렬이 수행됩니다.

사용법은 다음과 같습니다. key 인자에 함수를 넘겨주면 해당 key 인자가 기준이 됩니다. 밑의 예시에서는 x[1]이 정렬의 기준이 됩니다. 또한 sort 함수는 기본적으로 오름차순으로 정렬되며 이는 reverse 인자에 의해 결정됩니다. reverse 인자는 기본적으로 False이므로 True로 바꾸어주면 내림차순으로 정렬을 수행합니다.

arr.sort(key = lambda x: x[1], reverse = True)

소스코드

def solution(numbers):
    str_numbers = []

    # 정수 배열을 문자열 배열로 바꾸어줌
    for num in numbers:
        str_numbers.append(str(num))

    # 문자열 배열을 원하는 기준으로 정렬
    str_numbers.sort(key = lambda x: x*3,reverse=True)

    # 모두 이어 붙임
    return str(int(''.join(str_numbers)))

C언어 특징

• C언어는 문자열 비교시 == 연산자를 사용할 수 없고 string.h를 include하여 strcmp를 통해 문자열을 비교할 수 있습니다.
• C언어는 main에서 사용자 정의 함수를 사용하기 위해서는 사용자 정의 함수의 정의를 main함수 위에 쓰거나 proto type을 맨 위에 적어주어야 사용 가능합니다.

컴파일링(소스 코드 -> 오브젝트 코드)

C언어의 컴파일링 과정은 다음과 같이 4단계를 거칩니다.

• 전처리(Precompile) 전처리기에 의해 수행되는 것으로 #으로 시작되는 C언어 소스 코드는 전처리기에게 실질적인 컴파일이 이루어지기 전에 무언가를 실행하라고 알려줍니다. 예를 들어 #include는 전처리기에게 다른 파일의 내용을 포함시키라고 알려줍니다.

• 컴파일(Compile) 전처리기가 전처리한 소스 코드를 생성하고 나면 컴파일을 합니다. 컴파일러라고 불리는 프로그램은 C 코드를 어셈블리어로 컴파일합니다. 어셈블리어로 코드를 변환시켜줌으로써 컴파일러는 컴퓨터가 이해할 수 있는 언어와 최대한 가까운 프로그램으로 만들어 줍니다.

• 어셈블(Assemble) 소스 코드가 어셈블리 코드로 변환되면 어셈블러가 어셈블리 코드를 오브젝트 코드로 변환시킵니다. 컴퓨터의 중앙처리장치가 프로그램을 어떻게 수행해야 하는지 알 수 있는 명령어 형태인 연속된 0과 1들로 바꿔주는 작업입니다. 소스 코드에서 오브젝트 코드로 컴파일 되어야 하는 파일이 1개라면 컴파일 작업은 여기서 끝이 나지만 그렇지 않으면 링크라는 단계가 추가됩니다.

• 링크(Link) 만약 프로그램이 여러 개의 파일로 이루어져 있어 하나의 오브젝트 파일로 합쳐야 한다면 링크라는 단계가 필요합니다. 링커는 여러 개의 다른 오브젝트 코드 파일을 실행 가능한 하나의 오브젝트 코드 파일로 합쳐줍니다.

정렬

버블 정렬의 하한 시간복잡도는 Ω(n^2)입니다. 이미 정렬이 된 값이 들어온 상태여도 정렬 상태를 확인하지 않고 n-1번씩 n-1번 순회를 하며 정렬 작업을 수행하기 때문입니다. 하지만 버블 정렬에서 조건문을 추가하여 더 이상의 swap이 없으면 정렬이 된 상태로 간주하여 정렬을 종료하는 코드를 추가하면 Ω(n)이 됩니다. 선택 정렬 또한 마찬가지입니다. 선택 정렬은 배열을 순회하면서 가장 작은 값을 찾아 맨 앞으로 옮기는 작업이 필요한데 최선의 결과로 배열을 입력 받아도 가장 작은 값을 찾기 위해서는 모든 배열을 순회하며 확인해야 하기 때문에 하한 시간복잡도는 Ω(n^2)입니다. 병합 정렬도 정렬 도중에 현재 배열이 정렬되었는지 알 방법이 없기 때문에 Ο(nlogn)과 Ω(nlogn)을 가집니다.

메모리 구역

그림과 같이 메모리 안에는 데이터가 저장되는 구역이 나누어져 있습니다. machine code 영역에는 프로그램의 컴파일된 바이너리가 저장됩니다. globals 에는 전역 변수들이 저장됩니다. heap에는 malloc으로 할당된 메모리의 데이터가 저장됩니다. stack에는 프로그램의 함수와 관련된 내용이 저장됩니다.

메모리 할당

정수는 4byte의 메모리를 차지합니다. 만약 정수의 배열 arr[3]이 있다면 arr[0]는 정수 배열의 첫 번째 메모리 주소를 가리키게 됩니다. arr[1]은 arr[0]의 바로 다음 메모리 주소가 아닌 4byte 뒤의 메모리 주소를 가리키게 됩니다.

앞에서 가상 메모리의 기초에 대해서 공부했습니다. 이번에는 가상 메모리를 어떻게 효율적으로 관리하는지에 대해 자세히 공부해보겠습니다. 먼저 요구페이징에 대해서 알아보겠습니다.

프로세스의 일부만 메모리에 가져오는 이유는 무엇일까요?

바로 메모리를 효율적으로 관리하기 위해서 입니다. 메모리가 가득차면 관리하기 어렵기 때문에 적은 양의 프로세스만 유지하는 것 입니다. 응답속도 향상을 위해 용량이 큰 프로세스를 전부 메모리로 가져와 실행하면 응답이 늦어져 필요한 모듈만 올려 실행합니다. 이 때 사용자가 요구할 때 해당 페이지를 메모리로 가져오는 것을 요구페이징이라고 합니다. 페이지를 미리 가져오는 경우 가져온 페이지를 쓰지 않을 경우 메모리 낭비를 하기 때문에 현재 운영체제에서는 요구페이징을 기본으로 사용합니다.

페이지 테이블 엔트리(PTE)의 구조

페이지가 스왑 영역에 있는 경우는 크게 두 가지입니다. 먼저 요구페이징으로 인해 처음부터 물리 메모리에 올라가지 못한 경우(현재 필요하지 않은 경우)와 메모리가 가득차서 스왑 영역으로 옮겨온 경우(가상 메모리 기초에서 살펴본 경우) 입니다.

앞에서 PTE는 페이지 번호와 프레임 번호로 구성된다고 했는데 정확히 페이지 번호, 플래그비트, 프레임 번호로 구성됩니다. 프레임 번호를 주소 필드(address field)라고도 합니다. 그렇다면 플래그비트는 무엇일까요?

• 접근비트(access bit) : 페이지가 메모리에 올라온 후 사용한 적이 있는지 알려주는 비트입니다. 해당 메모리에 읽거나 실행작업을 했다면 접근비트가 1이 됩니다.

• 변경비트(modified bit) : 페이지가 메모리에 올라온 후 데이터의 변경이 있었는지 알려주는 비트입니다. 해당 메모리에 쓰기나 추가 작업을 했다면 변경비트가 1이 됩니다.
• 유효비트(valid bit) : 페이지가 실제 메모리에 있는지 나타내는 비트입니다. 실제 메모리에 있으면 0, 없으면 1로 표시합니다.(가장 중요하지만 헷갈리는 부분입니다.)
• 읽기, 쓰기, 실행비트 : 페이지에 대한 권한을 나타내는 비트입니다. 읽기 권한이 없는 프로세스를 읽으려고 하거나 쓰기 권한이 없는 프로세스가 쓰려고 할 때 접근을 차단하는데 사용됩니다.
• 접근 비트와 변경 비트는 페이지가 메모리에 올라온 후 어떤 작업이 있었는지 알려주는 역할을 합니다.

유효비트를 통해 해당 페이지의 위치를 알 수 있기 때문에 유효비트는 굉장히 중요합니다. 따라서 유효비트에 대해 더 알아봅시다.

유효비트

• 유효비트 0 : 페이지가 메모리에 있으므로 주소 필드에 물리 메모리의 프레임 번호가 저장됩니다.
• 유효비트 1 : 페이지가 스왑 영역에 있으므로 주소 필드에 스왑 영역 내 페이지의 주소가 저장됩니다.

페이지 부재(Page fault)

프로세스가 페이지를 요청했을 때 해당 페이지가 물리 메모리에 없는 상황을 말합니다. 세그멘테이션 오류(segmentation fault)의 경우 사용자의 프로세스가 주어진 메모리 공간을 벗어나거나 접근 권한이 없는 곳에 접근할 때 발생하며 해당 프로세스를 강제 종료하며 해결하는 심각한 오류입니다. 하지만 페이지 부재(page fault)의 경우 해당 페이지가 물리 메모리에 없을 때 발생하는 자연스러운 오류로 스왑 영역에서 해당 페이지를 물리 메모리로 옮기면 해결됩니다.

페이지 부재가 발생하면 프로세스가 해당 페이지를 사용할 수 있도록 스왑 영역에서 물리 메모리로 옮겨야 합니다. 만약 메모리에 빈 프레임이 없을 때는 메모리에 있는 프레임 중 하나를 스왑 영역으로 보낸 후 해당 페이지를 가져올 수 있습니다. 어떤 페이지를 스왑 영역으로 보낼지 결정하는 알고리즘을 페이지 교체 알고리즘(page replacement algorithm)이라고 하며 페이지 교체 알고리즘에 의해 스왑 영역으로 보낼 페이지를 대상 페이지(victim page)라고 합니다. 그렇다면 대상 페이지는 어떻게 정해지고 페이지 교체 알고리즘에는 어떠한 것들이 있을까요?

지역성

대상 페이지와 페이지 교체 알고리즘의 선정 기준에 대해 이야기하기 전에 지역성에 대한 개념을 공부해야합니다.

지역성(locality)

• 메모리의 빈 공간이 없어 어떤 페이지를 스왑 영역으로 보낼 때는 자주 사용될 페이지를 보내면 시스템의 성능이 저하되므로 앞으로 사용하지 않을 페이지를 보내는 것이 좋습니다.
• 지역성은 기억 장치에 접근하는 패턴이 메모리 전체에 고루 분포되는 것이 아니라 특정 영역에 집중되는 성질을 말합니다.
• 페이지 교체 알고리즘이 내보낼 페이지를 찾을 때 지역성을 바탕으로 합니다.

지역성의 종류에는 공간의 지역성, 시간의 지역성, 순차적 지역성이 있습니다. 기준점에 가까울수록 사용 가능성이 높기 때문에 기준점에 먼 페이지가 스왑 아웃될 가능성이 높습니다.

페이지 교체 알고리즘

페이지 교체 알고리즘은 스왑 영역으로 보낼 페이지를 결정하는 알고리즘입니다. 메모리에서 앞으로 사용할 가능성이 적은 페이지를 대상 페이지로 선정하여 페이지 부재를 줄이고 시스템의 성능을 향상시킵니다. 페이지 교체 알고리즘의 종류는 다음과 같습니다.

페이지 교체 알고리즘의 성능은 같은 메모리 접근 패턴을 사용하여 페이지 부재 횟수와 페이지 성공 횟수를 비교하여 측정합니다.

무작위 페이지 교체 알고리즘(random page replacement algorithm)

• 페이지 교체 알고리즘 중 가장 간단하게 구현할 수 있습니다.
• 특별한 로직 없이 무작위로 대상페이지를 선정합니다.
• 지역성을 전혀 고려하지 않기 때문에 성능이 좋지 않습니다.

FIFO 페이지 교체 알고리즘(first in, first out page replacement algorithm)

• 시간상으로 메모리에 가장 먼저 올라온 페이지를 대상 페이지로 지정하여 스왑 영역으로 보냅니다.
• 페이지의 부재는 F, 메모리에 있는 경우는 S로 표시합니다.
• 알고리즘은 큐로 구현하고 메모리 가장 위쪽에는 가장 오래된 페이지, 새로운 페이지는 맨 아래에 삽입합니다.
• 메모리가 가득 차면 맨 위의 페이지가 스왑 영역으로 가고 나머지 페이지들은 위쪽으로 이동합니다.
• 시간적 지역성을 고려했지만 무조건 오래된 페이지를 대상 페이지로 지정하기 때문에 성능이 떨어집니다.

최적 페이지 교체 알고리즘(optimal page replacement algorithm)

• 앞으로 사용하지 않을 페이지를 스왑 영역으로 옮깁니다.
• 메모리가 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 사용 시점까지 가장 멀리 있는 페이지를 대상 페이지로 지정합니다.
• 이상적이지만 미래를 예측해야 하기 때문에 실현 불가능합니다.

LRU(least recently used) 페이지 교체 알고리즘

• 페이지에 접근한 시간을 기준으로 대상 페이지를 선정합니다.
• 최근 최소 사용 페이지 교체 알고리즘이라고도 합니다.
• 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 영역으로 옮깁니다.
• 최근에 사용된 페이지는 놔두고 오래 전에 사용된 페이지를 대상 페이지로 선정합니다.
• 알고리즘은 시간을 기준으로 구현할 수 있으며 카운터나 참조 비트를 이용할 수도 있습니다.
• 참조 비트 시프트 방식의 경우 참조 비트의 초기 값은 0이며 페이지에 접근할 때마다 1로 바뀝니다. 참조 비트는 주기적으로 오른쪽으로 한 칸씩 이동하며 대상 페이지는 참조 비트 중 가장 작은 값을 선정합니다.
• 참조 비트 방식은 LFU 페이지 교체 알고리즘과 비슷합니다.

LFU(least frequently used) 페이지 교체 알고리즘

• 페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정합니다.
• 현재 프레임에 있는 페이지마다 그 동안 사용된 횟수를 세어 횟수가 가장 적은 페이지를 스왑 영역으로 옮깁니다. 사용 횟수가 같으면 가장 위에 있는 페이지를 대상 페이지로 지정합니다.

NUR(not used recently) 페이지 교체 알고리즘

• LRU, LFU 페이지 교체 알고리즘은 성능이 좋으나 페이지 접근을 표시해야 하기 때문에 추가적인 오버헤드가 큽니다.
• 이를 개선한 것이 NUR 알고리즘으로 두 개의 비트만으로 구현이 가능합니다.
• 최근 미사용 페이지 교체 알고리즘이라고도 부릅니다.
• 페이지마다 참조 비트와 변경 비트를 가집니다.
• 참조 비트는 페이지에 접근(read/execute)하면 1이 됩니다.
• 변경 비트는 페이지가 변경(write/append)되면 1이 됩니다.
• 모든 페이지의 초기 상태는 (0,0), 모든 값이 (1,1)이면 초기화 합니다.
• 대상 페이지를 찾을 때 참조 비트가 0인 페이지를 먼저 찾고 없으면 변경 비트가 0인 페이지를 찾습니다.
• 모든 페이지의 비트가 (1, 1)일 때는 어떤 페이지를 더 자주 사용했는지 알 수 없어 NUR을 적용할 수 없습니다. 따라서 모든 페이지가 (1, 1)이 되면 모든 페이지 비트를 초기화 합니다.

2차 기회 페이지 교체 알고리즘

• 큐를 사용하며 특이점은 특정 페이지에 접근해 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 대상 페이지 후보에서 제외하는 것 입니다.
• LRU, LFU, NUR보다 성능이 약간 낮고 FIFO 보다는 우수하다고 알려져 있습니다.
• 큐의 유지비용 및 중간에 있는 값을 이동하는 작업이 추가되는 단점이 있습니다.

시계 알고리즘

• 2차 기회 페이지 교체 알고리즘은 큐를 사용하지만 시계 알고리즘은 원형 큐를 사용합니다.
• 스왑 영역으로 옮길 대상 페이지를 가리키는 포인터를 사용합니다. 이 때 참조 비트가 1인 페이지는 0으로 만든 후에 건너뜁니다.(2차 기회를 줍니다.)
• 포인터가 큐의 맨 바닥으로 내려가면 다음 번에는 다시 큐의 처음을 가리키게 됩니다.
• 포인터가 시계처럼 한 방향으로 돌기 때문에 시계 알고리즘이라고 부릅니다.
• 참조 비트 1개가 추가되고 메모리에 있는 페이지를 성공적으로 참조하면 0에서 1로 변경됩니다.

스레싱

하드디스크의 입출력이 너무 많아져서 잦은 페이지 부재로 작업이 멈춘 것 같은 상태를 스레싱이라고 합니다. CPU가 작업하는 시간보다 스왑 영역으로 페이지를 보내고 새로운 페이지를 메모리에 가져오는 작업이 빈번해져서 CPU가 작업할 수 없는 상태에 이르게 되는 시점을 스레싱 발생 시점(threshing point)이라고 합니다. 물리 메모리의 크기를 늘리면 스레싱 발생 시점이 늦춰져서 프로세스를 원만하게 실행할 수 있습니다.

정적 할당과 동적 할당

프로세스에 프레임을 할당하는 방식은 크게 정적 할당과 동적 할당으로 구분합니다. 정적 할당에는 균등 할당(equal allocation)과 비례 할당(proportional allocation)이 존재합니다. 균등 할당은 프로세스의 크기와 상관없이 사용 가능한 프레임을 모든 프로세스에 동일하게 할당하는 것 입니다. 비례 할당은 프로세스의 크기에 비례하여 프레임을 할당하는 것 입니다.

동적 할당에는 작업집합 모델(working set model)이 있습니다. 이는 지역성 이론에 근거하며 가장 최근에 접근한 프레임이 이후에도 다시 참조될 가능성이 높다는 가정하에 만들어집니다. 최근 일정 시간 동안 참조된 페이지들을 집합으로 만들고 이 집합에 있는 페이지들을 물리 메모리에 유지합니다. 작업집합 크기(working set size)는 작업집합 모델에서 물리 메모리에 유지할 페이지 크기입니다. 작업집합 윈도우는 작업집합에 포함되는 페이지 범위, 현재시점에서 최대 어느 범위까지 페이지를 살펴볼 것인가를 결정하는 것이 작업집합 윈도우입니다. 이 때 작업집합 윈도우를 너무 크게 잡으면 필요 없는 페이지가 메모리에 남아서 다른 프로세스에 영향을 미치고 너무 작게 잡으면 필요한 페이지가 스왑 영역으로 옮겨져서 프로세스의 성능이 떨어집니다 적정크기의 작업집합을 유지함으로써 메모리를 효율적으로 관리할 수 있습니다.

현재 메모리 관리의 가장 큰 특징은 물리적 메모리 크기와 프로세스가 올라갈 위치를 신경 쓰지 않고 프로그래밍 하도록 지원합니다. 이러한 메모리 시스템을 가상 메모리라고 합니다.

• 가상 메모리 시스템의 모든 프로세스는 실제 메모리와 별개로 자신이 메모리의 어느 위치에 있는지 상관없이 0번지부터 시작하는 연속된 메모리 공간을 가집니다.

• 가상 메모리는 크게 프로세스가 바라보는 메모리 영역과 메모리 관리자가 바라보는 메모리 영역으로 나뉩니다.
• 가상 메모리의 최대 크기는 컴퓨터 시스템이 가진 물리 메모리의 크기로 한정되며 CPU 비트에 따라 결정됩니다.
• 가상 메모리 시스템에서는 물리 메모리의 내용 중 일부를 스왑 영역으로 옮깁니다. 따라서 가상 메모리의 크기는 물리 메모리와 스왑 영역을 합한 크기입니다.

그렇다면 가상 메모리는 어떤 방식으로 분할할까요?

가변 분할 방식을 이용한 세그멘테이션과 고정 분할 방식을 이용한 페이징 기법이 있습니다. 기본적으로 페이징 기법을 사용하나 페이지 테이블 관리가 어렵다는 단점이 있습니다. 세그멘테이션은 외부 단편화 등의 문제가 있습니다. 가상 메모리 시스템에서는 두 기법의 단점을 보완한 세그멘테이션 - 페이징 혼용 기법을 주로 사용합니다.

매핑 테이블

가상 메모리 시스템에서 가상 주소는 실제로 물리 주소나 스왑 영역 중 한 곳에 위치하며 메모리 관리자는 가상 주소와 물리 주소를 일대일 매핑 테이블로 관리합니다.

페이징 기법 구현

페이징 기법은 고정 분할 방식을 이용한 가상 메모리 관리 기법으로 물리 주소 공간을 같은 크기로 나누어 사용합니다. 가상 주소는 프로세스 입장에서 바라본 메모리 공간으로 항상 0번지부터 시작합니다. 페이징 기법의 특징에 대해서 공부해봅시다.

• 가상 주소의 분할된 각 영역을 페이지라고 하며 번호를 매겨 관리합니다.

• 물리 메모리의 각 영역은 가상 주소의 페이지와 구분하기 위해 프레임이라고 합니다. 프레임 또한 페이지처럼 번호를 매겨 관리합니다.
• 페이지와 프레임의 크기는 같기 때문에 페이지는 어떠한 프레임에도 배치될 수 있습니다.
• 어떤 페이지가 어떤 프레임에 있는 지에 대한 연결(매핑) 정보는 페이지 테이블에 담겨있습니다.
• 페이지 테이블에 invalid는 해당 페이지가 스왑 영역에 있다는 뜻 입니다.

페이지 기법에서 주소를 변환하는 방법에 대해 알아봅시다.

페이지 기법에서는 가상 주소를 VA = <P, D>로 표현합니다. VA는 Virtual Address, P는 페이지, D는 Distance로 거리 혹은 오프셋을 의미합니다. 페이징 기법에서의 주소 변환은 가상 주소 VA = <P, D>를 물리 주소 PA = <F, D>로 변환하는 것입니다. PA는 Physical Address이고 F는 Frame 입니다. 페이징 기법에서 VA가 PA로 변형될 때에 D의 값은 가상 메모리와 물리 메모리를 같은 크기로 분할했기 때문에 변하지 않습니다.

페이지의 크기가 다양할 경우 가상 주소를 <P, D>로 변환하는 공식은 다음과 같습니다.

P = 나눗셈(가상 주소/한 페이지의 크기)의 몫 D = 나눗셈(가상 주소/한 페이지의 크기)의 나머지

예를 들어 한 페이지의 크기가 512B인 시스템에서 가상 주소 2049번지는 2049/512는 몫이 4, 나머지가 1이기 때문에 P = 4, D = 1이 됩니다.

16bit CPU의 컴퓨터에서 한 페이지의 크기가 2^10B일 때 페이징 시스템에 대해 알아봅시다. 한 프로세스가 사용할 수 있는 가상 메모리의 크기는 2^16B입니다. 따라서 사용자는 0번지부터 2^16-1번지까지 가상 주소 공간을 사용 가능합니다. 또한 가상 주소로 사용할 수 있는 16bit 중 6bit는 페이지 번호로 10bit는 페이지의 처음 위치에서 해당 주소까지의 거리를 저장합니다. 이것은 시스템의 페이지가 063번지까지, 페이지 하나가 01023번 까지 구성되어 있다는 것을 의미합니다. 이러한 상황에서 가상 주소 980번지의 페이지와 거리를 구하려고 하면 페이지 하나의 크기가 1024이므로 980/1024를 하여 몫은 0, 나머지는 980으로 하여 VA = <0, 980>과 같은 결과를 얻어 낼 수 있습니다.

페이지 테이블 관리

그렇다면 다수의 프로세스가 있는 경우 페이징 시스템은 어떻게 될까요? 페이지 테이블 관리가 복잡한 이유는 시스템에 여러 개의 프로세스가 존재하고 프로세스마다 페이지 테이블이 하나씩 존재하기 때문입니다. 프로세스의 수가 많아지면 페이지 테이블의 크기가 커지고 이에 따라 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어듭니다. 따라서 페이지 테이블의 크기를 적정하게 유지하는 것은 페이지 테이블 관리의 핵심이고 페이지 테이블은 메모리 관리자가 자주 사용하는 자료구조이므로 물리 메모리 영역 중 운영체제 영역의 일부분에 모아 놓습니다.

이렇게 페이지 테이블을 운영체제 영역의 일부분에 모아 놓으면 운영체제의 영역이 커지는 만큼 사용자 영역이 작아집니다. 따라서 물리 메모리의 크기가 작을 때는 프로세스만 스왑 영역으로 옮겨지는 것이 아니라 페이지 테이블의 일부도 스왑 영역으로 옮겨집니다. 각 페이지 테이블의 시작 주소는 페이지 테이블 기준 레지스터(Page Table Base Register, PTBR)에 보관하여 각 프로세스가 메모리에 접근하려고 할 때 메모리 관리자는 페이지 테이블의 위치를 신속하게 파악할 수 있습니다. PTBR은 각 프로세스의 PCB에 저장되는 데이터로 물리 메모리 내에 페이지 테이블의 시작 주소를 가지고 있습니다.

페이지 테이블 매핑 방식

위의 페이지 테이블의 관리에서 기본적으로 페이지 테이블은 운영체제 영역에 존재하며 때에 따라 스왑 영역에 존재하기도 합니다. 페이지 테이블 전체를 메모리에서 관리하느냐 일부를 스왑 영역에서 관리하느냐에 따라 가상 주소를 물리 주소로 변환하는 방법이 달라집니다. 페이지 테이블이 위치하는 곳에 따라 다양한 페이지 테이블 매핑 방식이 존재합니다.

직접 매핑(direct mapping)

• 페이지 테이블 전체가 물리 메모리의 운영체제 영역에 존재하는 방식입니다.
• 별다른 부가 작업 없이 바로 주소 변환이 가능하기 때문에 직접 매핑이라고 부릅니다.

연관 매핑(associative mapping)

• 페이지 테이블 전체를 스왑 영역에서 관리하는 방식입니다.
• 물리 메모리의 여유 공간이 작을 때 사용하는 방식입니다.(따라서 최근에는 사용하지 않습니다.)
• 모든 페이지 테이블을 저장 장치의 스왑 영역에 저장하고 그 중 일부만 물리 메모리에 가져옵니다.
• 일부 내용만 무작위로 가져오기 때문에 페이지 번호와 프레임 번호를 모두 표시합니다.
• 주소 변환 시 물리 메모리 내의 페이지 테이블을 다 검색해야 하며 만약 원하는 프레임 번호를 얻지 못하면 스왑 영역에 있는 페이지 테이블을 검색합니다.
• 검색 실패 시 스왑 영역에서 다시 찾아야 하므로 시간을 낭비하여 속도가 느려지게 됩니다.

집합-연관 매핑(set-associative mapping)

• 디렉토리 매핑이라고도 부릅니다.
• 페이지 테이블을 일정한 집합으로 나누고 나눈 단위로 물리 메모리에 가져옵니다.
• 페이지 테이블을 n개씩 나누고 이를 관리하는 페이지 테이블을 하나 더 생성합니다.
• 새로 생성한 집합 테이블에는 일정하게 나눈 페이지 테이블이 물리 메모리에 있는지, 스왑 영역에 있는지에 대한 위치 정보를 표시합니다. I는 스왑 영역에 있다는 표시입니다.
• 연관 매핑과 비교했을 때 집합 테이블을 통해 원하는 페이지 테이블 엔트리가 스왑 영역에 있는지 물리 메모리 영역에 있는지 간단하게 파악할 수 있습니다.
• 연관 매핑과 집합-연관 매핑은 캐시에서 사용하는 방식입니다.
• 페이지 테이블이 일정 크기의 묶음으로 나뉘기 때문에 가상 주소를 VA = <P, D>가 아니라 VA = <P1(디렉터리 테이블 번호), P2(묶음 테이블 번호), D>로 바꾸어 표시합니다.

역매핑(invert mapping)

• 물리 메모리의 프레임 번호를 기준으로 테이블을 구성합니다.
• 물리 메모리의 프레임에 어떤 프로세스의 어떤 페이지가 올라와 있는지 표시합니다.
• 프로세스 수와 상관없이 테이블이 하나만 존재하므로 테이블의 크기가 매우 작다는 장점이 있습니다.
• 프로세스가 가상 메모리에 접근할 때 PID와 페이지 번호를 모두 찾아야 하기 때문에 속도가 매우 느리다는 단점이 있습니다.

세그멘테이션 기법의 구현

지금까지는 페이징 기법의 구현에 대해 살펴보았습니다. 이제 가변 분할방식인 세그멘테이션 기법의 구현에 대해 공부해봅시다.

• 세그멘테이션 테이블에는 세그먼트의 크기를 나타내는 limit와 물리 메모리 상의 시작 주소를 나타내는 address가 있습니다.

• 프로세스 크기에 따라 메모리를 분할하기 때문에 매핑 테이블에 크기 정보를 포함합니다.
• 각 세그먼트가 자신에게 주어진 메모리 영역을 넘어가면 안되기 때문에 세그먼트의 크기 정보에는 크기를 뜻하는 size 대신 제한을 뜻하는 limit를 사용합니다.
• 스왑 영역에 존재하는 프로세스는 세그멘테이션 테이블의 address에 I(Invalid)라고 표시합니다.
• 메모리를 프로세스 단위로 관리하기 때문에 페이지 테이블이 작고 단순하다는 장점이 있습니다.
• 물리 메모리의 외부 단편화로 인해 관리가 복잡합니다.
• 만약 가상 주소의 거리가 세그먼트의 크기보다 크다면 메모리 결함(fault)를 출력하고 해당 프로세스를 강제 종료합니다.
• 자신의 영역을 벗어나는 주소에 접근하거나 숫자를 0으로 나누는 것과 같이 의도치 않은 인터럽트를 트랩이라고 하며 트랩이 발생하면 운영체제는 사용자에게 세그멘테이션 오류(segmentation fault) 메시지를 보냅니다.

세그멘테이션-페이징 혼용기법

페이징 기법은 물리 메모리를 동일한 크기로 나누어 관리하기 때문에 메모리 관리가 단순한 반면 페이지 테이블의 크기가 컸습니다. 세그멘테이션 기법은 맵핑 테이블의 크기가 작지만 물리 메모리의 단편화로 추가적인 관리가 필요했습니다. 이러한 두 가지 방법의 장점을 활용한 것이 세그멘테이션-페이징 혼용 기법입니다. 이 기법을 이해하기 위해서는 먼저 프로세스의 영역별 메모리 접근 권한에 대해 알아야 합니다.

프로세스는 몸체에 해당하는 코드 영역, 프로세스가 사용한느 데이터를 저장하는 데이터 영역, 프로세스를 실행하는데 필요한 스택 영역, 프로세스 제어블록(PCB)로 구성됩니다.

• 코드 영역 : 자기 자신을 수정하는 프로그램은 없기 때문에 읽기 및 실행 권한을 가집니다.

• 데이터 영역 : 데이터는 크게 읽거나 쓸 수 있는 데이터와 읽기만 가능한 데이터로 나눌 수 있습니다. 일반적인 변수는 읽거나 쓸 수 있으므로 읽기 및 쓰기 권한을 가지고 상수로 선언한 변수는 읽기 권한만 가집니다.

메모리 접근 권한 검사는 가상주소에서 물리주소로 변환이 생기면 시행됩니다. 이 부분이 핵심인데 이렇게 가상주소에서 물리주소로 변환하는 과정에서 페이징 기법을 사용할 경우 페이지 테이블의 모든 행에 메모리 접근 권한과 관련된 권한 비트(right bit)를 추가해야 합니다. 페이지 테이블에 권한 비트가 추가되면 페이지 테이블의 크기가 커지는 문제가 생깁니다. 이러한 문제를 해결하기 위해 세그멘테이션 기법을 혼용하는 것 입니다. 위의 그림과 같이 페이징 기법에 세그멘테이션 테이블을 추가하고 권한 비트와 같은 중복 데이터를 세그멘테이션 테이블로 옮겨 테이블의 크기를 줄입니다. 오늘날 대부분의 운영체제는 이와 같은 방식을 사용하고 있습니다. 사용자 입장에서는 기본적으로 세그멘테이션 기법을 사용하고 메모리 관리자 입장에서는 페이징 기법을 사용합니다. 가상주소 VA는 <S, P, D>로 표현하여 S는 세그먼트 번호, P는 페이지 번호, D는 거리를 의미합니다.

1. 사용자가 어떤 주소에 있는 데이터를 요청하면 해당 주소가 몇 번째 세그먼트의 몇 번째 페이지로부터 얼마나 떨어져 있는지 계산하여 가상 주소 VA = <S, P, D>를 구합니다.
2. 세그멘테이션 테이블의 해당 세그먼트 번호로 가서 자신의 영역을 벗어나는 접근인지 등을 확인합니다.
3. 페이지 테이블에서 해당 페이지가 어느 프레임에 저장되었는지 찾습니다. 만약 없다면 스왑 영역에 가서 해당 페이지를 물리 메모리로 가져옵니다.
4. 물리 메모리에 있는 프레임의 처음 위치에서 D만큼 떨어진 곳에 접근하여 데이터를 읽거나 씁니다.

동일한 조건일 때 메모리 용량이 크면 작업속도가 빨라집니다. 하지만 이는 로그 그래프의 형태로 기울기가 바뀌기 때문에 메모리의 크기가 어느 수준 이상이 되면 속도의 차이가 작아집니다. 따라서 한정된 크기의 메모리를 관리하는 것은 굉장히 중요한 일입니다.

메모리 관리의 이중성

프로세스 입장에서는 메모리를 독차지하려 하고 메모리 관리자 입장에서는 되도록 관리를 효율적으로 하고 싶어합니다. 프로세스가 작업하는 도중에 할당된 공간이 부족하면 메모리 관리자는 새로운 공간을 확보하기 위해 옆의 프로세스를 밀어내거나 더 큰 공간으로 해당 프로세스를 옮깁니다. 작업을 마친 후 빈 공간이 생기면 다음 작업을 위해 빈 공간을 어떻게 처리해야 할지 결정해야 합니다. 빈 공간이 여러 개 생기면 합쳐서 하나의 공간을 만들고 이렇게 하기 위해 현재 작업 중인 공간을 옆으로 밀고 작은 공간을 합칩니다. 이렇듯 메모리 관리는 굉장히 복잡하게 이루어집니다. 그렇다면 이러한 관리는 누가 하는 것일까요?

메모리 관리자의 역할

바로 메모리 관리자가 메모리를 관리합니다. 메모리 관리자는 Memory Manage Unit이라고 하며 메모리 관리를 담당하는 하드웨어입니다. 위의 3가지 작업에 대해 자세히 알아보겠습니다.

가져오기(Fetch) : 프로세스와 데이터를 메모리로 가져옵니다.

• 메모리 관리자는 사용자가 요청하면 프로세스와 데이터를 모두 메모리로 가져옵니다.
• 대용량 동영상과 같은 상황에서는 데이터의 일부만 가져와 실행합니다.
• 사용자의 요청이 없어도 앞으로 필요할 것이라고 예상되는 데이터를 미리 가져옵니다. 이를 Prefetch라고 합니다.

배치(Placement) : 가져온 프로세스와 데이터를 메모리의 어떤 부분에 올려놓을지 결정합니다.

• 배치 작업 전에 메모리를 어떤 크기로 나눌 것인지가 매우 중요합니다.
• 같은 크기로 자르느냐(페이징 혹은 고정분할), 실행되는 프로세스 크기에 맞게 자르느냐(세그멘테이션 혹은 가변분할)에 따라 메모리 관리 복잡성이 달라집니다.

재배치(Replacement) : 꽉 차 있는 메모리에 새로운 프로세스를 가져오기 위해 오래된 프로세스를 내보냅니다. 가까운 미래에 사용하지 않을 프로세스를 찾아서 내보내는 알고리즘을 교체 알고리즘이라고 합니다.

메모리 주소

32bit CPU와 64bit CPU의 차이는 CPU의 bit차이입니다. CPU의 bit는 한 번에 다룰 수 있는 데이터의 최대 크기를 의미하고 이를 워드(word)라고 부릅니다. 32bit CPU 내의 레지스터 크기는 전부 32bit, 산술 논리 연산장치와 대역폭도 32bit로 설계되어 있습니다. 그렇다면 메모리 크기는 어떨까요?

32bit CPU의 메모리 크기는 표현할 수 있는 메모리 주소의 범위가 02^32-1, 총 개수가 2^32개 입니다. 16진수로 나타내면 00000000FFFFFFFF이고 총 크기가 2^32B로 약 4GB입니다.

64bit CPU의 메모리 크기는 0~2^64-1번지의 주소 공간을 제공하기 때문에 총 크기가 2^64B로 약 16777216TB로 무한대에 가까운 메모리 사용이 가능합니다.

주소 공간에는 물리 주소 공간과 논리 주소 공간이 있습니다. 물리 주소 공간은 하드웨어 입장에서 바라본 주소 공간으로 컴퓨터마다 크기가 다릅니다. 논리 주소 공간은 사용자 입장에서 바라본 주소 공간입니다.

절대주소 및 상대주소

위의 사진은 한 번에 한 가지 일만 처리하는 일괄 처리 시스템에서 볼 수 있는 단순 메모리 구조로 메모리를 운영체제 영역과 사용자 영역으로 나누어 관리합니다. 사용자 프로세스는 운영체제 영역을 피하여 메모리에 적재합니다. 사용자 프로세스가 운영체제의 크기에 따라 매번 적재되는 주소가 달라지는 것은 번거롭기 때문에 이를 개선하여 사용자 프로세스를 메모리의 최상위부터 사용합니다. 여기서 최상위는 그림상 999번 주소를 위치를 말합니다. 그러나 이러한 방법도 메모리를 거꾸로 사용하기 위해 주소를 변경하는 일이 복잡하기 때문에 잘 쓰이지 않고 경계 레지스터를 이용하는 방법을 사용합니다.

경계 레지스터는 운영체제 영역과 사용자 영역 경계 지점의 주소를 가진 레지스터입니다. CPU내에 있는 경계 레지스터가 사용자 영역이 운영체제 영역으로 침범하는 것을 방지합니다. 메모리 관리자는 사용자가 작업을 요청할 때마다 경계 레지스터의 값을 벗어나는지 검사하고 만약 경계 레지스터를 벗어나는 작업을 요창하는 프로세스가 있으면 해당 프로세스를 종료합니다. 이제 절대주소와 상대주소의 개념에 대해서 알아봅시다.

절대주소(absolute address)

• 실제 물리 주소(physical address)를 가리키는 주소입니다.
• 메모리 주소 레지스터가 사용하는 주소입니다.
• 컴퓨터에 장착된 램 메모리의 실제 주소입니다.

상대주소(relative address)

• 사용자 영역이 시작되는 번지를 0번지로 변경하여 사용하는 주소입니다.
• 사용자 프로세스 입장에서 바라본 주소입니다.
• 절대 주소와 관계없이 항상 0번지 부터 시작입니다.
• 프로세스 입장에서 상대 주소가 사용할 수 없는 영역의 위치를 알 필요가 없고 주소가 항상 0번지부터 시작하기 때문에 편리합니다.

위에서 설명한 논리 주소 공간은 상대 주소를 사용하는 주소 공간이고 물리 주소 공간은 절대 주소를 사용하는 주소 공간 입니다.

다음은 상대 주소를 절대 주소로 변환하는 과정에 대해 알아보겠습니다. 메모리 접근 시 상대 주소를 사용하면 절대 주소로 변환해야 합니다. 메모리 관리자는 사용자 프로세스가 상대 주소를 사용하여 메모리에 접근할 때마다 상대 주소 값에 재배치 레지스터 값을 더하여 절대 주소를 구합니다. 재배치 레지스터는 주소 변환의 기본이 되는 주소 값을 가진 레지스터로 메모리에서 사용자 영역의 시작 주소 값이 저장됩니다. 위의 그림에서는 360번 주소부터 사용자 영역이 시작되므로 재배치 레지스터에는 360이 저장되어 있을 것 입니다.

메모리 중첩

메모리 중첩(오버레이)는 단일 프로그래밍 환경에서의 메모리 할당을 의미합니다. 정의가 살짝 어려운데 프로그램의 크기가 실제 메모리보다 클 때 전체 프로그램을 메모리에 가져오는 대신 적당한 크기로 잘라서 가져오는 기법입니다. 따라서 메모리 오버레이를 사용하면 물리 메모리보다 더 큰 프로그램도 실행이 가능합니다. 예를 들어 워드 프로그램을 실행하고 워드 프로그램의 크기가 실제 메모리의 크기보다 클 때 현재 사용하고 있는 기능인 모듈만을 적당한 크기로 잘라 메모리에 올리는 것 입니다.

메모리 오버레이는 한정된 메모리에서 메모리보다 큰 프로그램이 실행 가능하다는 가상 메모리의 기본 개념이라는 의미가 있습니다. 또한 메모리를 여러 조각으로 나누어 여러 프로세스에 할당할 수 있다는 의미도 있습니다.

스왑(Swap)

스왑은 단일 프로그래밍 환경에서 메모리 할당을 의미합니다. 메모리 오버레이에서 메모리에 프로그램의 모듈 A를 올려 사용하고 있다고 가정해봅시다. 만약 모듈 B를 가져다가 쓰고 싶으면 모듈 A를 꺼내어 어딘가에 보관해야 합니다. 이를 하드디스크 위치에 옮겨 보관할 수도 있지만 언제 모듈 A를 다시 사용할지도 모르고 아직 작업이 끝났는지도 모르기 때문에 별도의 공간에 보관해야 합니다. 이렇듯 메모리가 부족해서 교체된 프로세스는 저장장치의 특별한 공간에 모아두는데 이 영역을 스왑 영역(swap area)라고 합니다. 메모리에서 교체되었다가 다시 돌아가는 데이터가 머무는 곳이기 때문에 저장장치는 장소만 빌려주고 메모리 관리자가 관리합니다. 사용자는 실제 메모리의 크기와 스왑 영역의 크기를 합쳐서 전체 메모리로 인식하고 사용합니다.

스왑인 : 스왑 영역에서 메모리로 데이터를 가져오는 작업을 의미합니다. 스왑아웃 : 메모리에서 스왑 영역으로 데이터를 내보내느 작업을 의미합니다.

메모리 분할 방식

이번 포스팅의 가장 중요한 부분이라고 생각합니다. 다중 프로그래밍 환경에서 메모리를 어떤 방법으로 분할하여 프로세스들을 올릴 수 있는지에 대해 공부해보도록 하겠습니다.

가변 분할 방식(세그멘테이션) : 프로세스의 크기에 따라 메모리를 나누는 것입니다. 따라서 메모리의 영역이 크기가 각각 다릅니다. 한 프로세스가 연속된 공간에 배치되기 때문에 연속 메모리 할당이 가능합니다. 이러한 연속 메모리 할당이 가변 분할 방식의 장점이지만 비어 있는 공간을 하나로 합쳐야 하며 이 과정에서 다른 프로세스의 자리도 옮겨야 하므로 메모리 관리가 복잡해진다는 단점이 있습니다. 위의 그림에서 프로세스 B와 D의 작업이 종료되고 19KB의 프로세스가 올라오려고 한다면 빈 공간이 분리되어 있기 때문에 올라올 수 없을 것 입니다. 따라서 빈 공간을 하나로 합쳐야 하며 이 과정에서 프로세스 C의 이동이 필연적으로 발생합니다. 이렇게 가변 분할 방식에서 발생하는 작은 빈 공간을 외부 단편화(external fragmentation)이라고 합니다.

고정 분할 방식(페이징) : 프로세스의 크기와 상관없이 메모리를 동일한 크기로 나누는 것입니다. 고정 분할 방식은 큰 프로세스가 메모리에 올라오면 여러 조각으로 나누어 배치하고 한 프로세스가 분산되어 배치되기 때문에 비연속 메모리 할당입니다. 메모리를 일정한 크기로 나누어 관리하기 때문에 메모리 관리가 수월하다(메모리 통합 같은 부가적인 작업을 할 필요가 없기때문에)는 장점이 있지만 쓸모없는 공간으로 인해 메모리 낭비가 발생할 수 있다는 단점이 있습니다. 위의 그림에서 프로세스 B는 18KB, D는 17KB이기 때문에 메모리의 한 조각인 20KB에 배치하면 각각 2KB, 3KB씩 공간이 남습니다. 이러한 현상을 내부 단편화(internal fragmentation)라고 합니다.

가변 분할 방식의 메모리 관리

그렇다면 가변 분할 방식에서는 어떻게 메모리를 관리해야 할까요? 먼저 외부 단편화를 해결해야 합니다. 작은 조각이 발생하지 않도록 프로세스를 배치해야 하고 조각이 발생했을 때 작은 조각들을 모아서 하나의 큰 덩어리로 만드는 조각 모음 작업을 수행하면 됩니다.

작은 조각이 발생하지 않도록 프로세스를 배치하는 방식에는 3가지가 있습니다.

최초 배치(first fit) : 프로세스를 메모리의 빈 공간에 배치할 때 메모리에서 적재 가능한 공간을 순서대로 찾다가 첫 번째로 발견한 공간에 프로세스를 배치하는 방법입니다. 빈 공간을 찾아다닐 필요가 없습니다.

최적 배치(best fit) : 메모리의 빈 공간을 모두 확인한 후 적당한 크기 가운데 가장 작은 공간에 프로세스를 배치하는 방법입니다. 빈 공간을 모두 확인하는 부가 작업이 있지만 딱 맞는 공간을 찾는 경우 단편화가 일어나지 않습니다. 하지만 딱 맞는 공간이 없는 경우 아주 작은 조각을 만들어내는 단점이 있습니다.

최악 배치(worst fit) : 빈 공간을 모두 확인한 후 가장 큰 공간에 프로세스를 배치하는 방법입니다. 주로 큰 빈 공간이 있을 때 사용하면 좋습니다. 최적 배치와 반대로 접근하는 개념이며 프로세스를 배치하고 남는 공간이 크기 때문에 다른 프로세스가 와도 됩니다. 빈 공간의 크기가 클때는 효율적이지만 빈 공간의 크기가 점점 줄어들면 최적 배치처럼 작은 조각을 만들어내는 단점이 있습니다.

하지만 위의 3가지 방법을 이용해 프로세스를 배치해도 여전히 단편화 현상이 발생합니다. 이에 따라 조각 모음을 실행해야 합니다.

조각 모음 : 이미 배치된 프로세스를 옆으로 옮겨 빈 공간들을 하나의 큰 덩어리로 만드는 작업입니다. 조각 모음을 하기 위해서는 이동할 프로세스의 동작을 멈추고 프로세스를 적당한 위치로 옮깁니다.(프로세스가 이동하기 때문에 프로세스의 상대 주소 값을 바꿉니다.) 작업을 다 마친 후에는 프로세스를 다시 시작합니다.

고정 분할 방식의 메모리 관리

고정 분할 방식은 가변 분할 방식보다 공간을 효율적으로 관리합니다. 고정 분할 방식은 조각모음을 할 필요가 없어 관리가 원활하며 메모리 관리 시스템의 기본 방식으로 사용됩니다. 만약 메모리를 20KB씩 분할한다고 가정했을 때 프로세스 C의 크기가 30KB이면 C는 20KB인 C1과 10KB인 C2로 나뉜뒤 C2는 메모리에 남는 공간이 없을 경우 스왑 영역으로 옮겨지게 됩니다. 고정 분할 방식은 내부 단편화를 줄이기 위해 신중하게 메모리의 크기를 결정해서 나눠야 하지만 사용하는 프로세스의 크기가 제각각이기 때문에 메모리를 얼마로 나누느냐에 대한 정답은 없습니다.

버디 시스템

가변 분할 방식과 고정 분할 방식 외에 새로 등장한 메모리 분할 방법입니다. 버디 시스템의 작동 방식은 다음과 같습니다.

1. 프로세스의 크기에 맞게 메모리를 1/2로 자르고 프로세스를 메모리에 배치합니다.
2. 나뉜 메모리의 각 구역에는 프로세스가 1개만 배치 됩니다.
3. 프로세스가 종료되면 주변의 빈 조각과 합쳐서 하나의 큰 덩어리를 만듭니다.

버디 시스템은 다음과 같은 특징을 가집니다.

• 가변 분할 방식처럼 메모리가 프로세스 크기대로 나뉩니다.

• 고정 분할 방식처럼 하나의 구역에 다른 프로세스가 들어갈 수 없고 메모리의 한 구역 내부에 작은 조각이 생겨 내부 단편화가 발생합니다.
• 비슷한 크기의 조각이 서로 모여 작은 조각을 통합하여 큰 조각을 만들기 쉽습니다.
• 효율적인 공간 관리 측면에서 보면 고정 분할 방식과 버디 시스템은 비슷합니다. 그러나 공간을 1/2로 나누어 가면서 메모리를 배분하는 버디 시스템보다 모든 공간을 동일한 크기로 나누는 고정 분할 방식이 메모리 관리 측면에서 단순하기 때문에 고정분할 방법이 많이 사용됩니다.

지난번에는 교착상태의 정의까지 공부했습니다. 그렇다면 언제 교착상태가 발생하는지에 대해서 알아보겠습니다. 다음 4가지 조건이 모두 발생할 때 교착상태는 발생합니다.

• 상호 배제(mutual exclusion) : 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 합니다.

• 비선점(non-preemptive) : 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 합니다.
• 점유와 대기(hold and wait) : 프로세스가 어떤 자원을 할당 받은 상태에서 다른 자원을 기다리는 상태여야 합니다.
• 원형 대기(circular wait) : 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 합니다.

위 4가지 조건 중 상호 배제와 비선점 조건은 자원이 어떤 특징을 가지고 있는지 나타냅니다. 사용하는 자원을 동시에 공유할 수 없고 중간에 빼앗을 수도 없다면 자원을 가진 프로세스가 자원을 내놓을 때까지 무작정 기다리는 교착상태가 발생합니다. 점유와 대기, 원형 대기 조건은 _프로세스가 어떤 행위를 하고 있는지_를 나타냅니다. 프로세스가 자원을 점유 및 대기하고 있는 상태에서 다른 프로세스를 방해하는 방향이 원을 이루면 서로 양보하지 않기 때문에 교착상태가 발생합니다.

그렇다면 이러한 교착상태는 어떤 방식으로 해결할 수 있을까요?

교착상태 해결 방법

교착상태를 해결하기 위해서 사람들은 크게 3가지 방법을 생각해냈습니다.

• 교착상태 예방 : 교착상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방법이지만 이 방법은 실효성이 적습니다.

• 교착상태 회피 : 자원 할당량을 조절하여 교착 상태를 해결하는 방식입니다. 자원을 할당하다가 교착상태를 유발할 가능성이 있다고 판단되면 자원 할당을 중단하고 지켜보는 것 입니다. 그러나 자원을 얼마나 할당해야 교착상태가 발생하지 않는다는 보장이 없기 때문에 실효성이 적습니다.
• 교착상태 검출과 회복 : 교착상태 검출은 어떤 제약을 가하지 않고 자원 할당 그래프를 모니터링하면서 교착상태가 발생하는지 살펴보는 방법입니다. 만약 교착상태가 발생하면 교착상태 회복 단계가 진행이 됩니다. 가장 현실적인 교착상태 해결 방법입니다.

이제 각 방법에 대해 자세히 공부해보겠습니다.

교착상태 예방

위에서 교착상태 예방은 교착상태를 유발하는 네 가지 조건이 발생하지 않도록 하는 것이라고 했습니다.

상호배제 예방 : 시스템 내에 있는 상호 배타적인 모든 자원을 없애버리는 방법입니다. 시스템 내의 모든 자원을 공유할 수 있다면 교착상태는 발생하지 않습니다. 하지면 현실적으로 모든 자원을 공유할 수 없으며 상호배제를 적용하여 보호해야 하는 자원이 있습니다. 자원을 공유하게 되면 임계 구역이 보호받지 못하는 문제가 발생하기도 합니다.

비선점 예방 : 모든 자원을 빼앗을 수 있도록 만드는 방법입니다. 하지만 임계 구역을 보호하기 위해 잠금을 사용하면 자원을 빼앗지 못할 뿐더러 어떤 기준으로 자원을 빼앗을지, 빼앗은 시간 중 얼마나 사용할지 등을 결정하기 어렵고 이로 인해 우선 순위가 낮은 프로세스는 아사(starvation) 현상이 발생할 수 있습니다. 에이징을 사용해도 특정 조건 이상일 때 한 프로세스가 계속 자원을 사용할 수 있기 때문에 비선점 효과를 일으켜 교착상태를 일으킬 수 있습니다.

점유와 대기 예방 : 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법입니다. 전부 할당하거나 아예 할당하지 않는(all or nothing) 방식을 적용합니다. 프로세스는 시작 초기에 자신이 사용하려는 모든 자원을 한꺼번에 점유하거나 그렇지 못할 경우 자원을 모두 반납해야 합니다. 앞에서 살펴본 상호 배제 예방과 비선점 예방은 자원에 대한 제약을 풀어버리는 것인데 임계구역으로 보호 받는 자원에 대한 제약을 풀기는 어렵습니다. 점유와 대기 예방은 자원이 아닌 프로세스의 자원 사용 방식을 변화시켜 교착상태를 처리한다는 점에서 의미가 있습니다.
하지만 점유와 대기 예방은 프로세스가 자신이 사용하는 모든 자원은 자세히 알기 어렵다는 점과 자원의 활용성이 떨어진다는 점, 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 자원 선점에 불리한 점, 결국 일괄 작업 방식으로 진행된다는 단점이 있습니다.

원형대기 예방 : 점유와 대기를 하는 프로세스들이 원형을 만들지 못하도록 막는 방법입니다. 자원을 한 방향으로만 사용하도록 설정함으로써 원형대기를 예방할 수 있습니다. 즉 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당하는 것 입니다. 원형 테이블에서 식사하던 것을 일렬로 줄세워 식사하는 것과 같습니다. 숫자가 작은 자원을 잡은 상태에서 큰 숫자를 잡는 것은 허용하지만 숫자가 큰 자원을 잡은 상태에서 작은 숫자를 잡는 것은 허용하지 않습니다. 이렇게 하면 원형대기는 사라지지만 프로세스 작업진행의 유연성이 사라지고 큰 번호 자원을 사용한 후 작은 번호의 자원을 사용할 수 없기 때문에 자원에 번호를 부여하는데 매우 신중해야 한다는 단점이 있습니다.

교착상태 회피

교착상태 회피는 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어 주면 교착상태가 발생하는지 파악해 그 수준 이하로 자원을 나누어 주는 방법입니다. 교착상태가 발생하지 않는 범위 내에서만 자원을 할당하고 교착상태가 발생하는 범위에 있으면 프로세스를 대기시킵니다. 교착상태 회피는 시스템의 운영방식에 변경을 가하지 않기 때문에 교착상태 예방보다 유연합니다. 교착상태 회피는 자원의 총 개수와 할당된 자원의 개수를 기준으로 시스템을 안정상태와 불안정상태로 나누고 시스템이 안정상태를 유지하도록 자원을 할당합니다. 아래의 그림과 같이 할당된 자원이 적으면 안정상태가 크고 할당된 자원이 커질수록 불안정상태도 커집니다. 교착상태도 불안정상태의 일부이며 불안정상태가 커질수록 교착상태의 발생가능성이 증가합니다. 이렇게 교착상태 회피는 안정상태를 유지할 수 있는 범위 내에서 자원을 할당함으로써 교착상태를 회피합니다. 교착상태 회피에는 다익스트라가 제안한 은행원 알고리즘 방식이 대표적으로 쓰입니다. 예를 들어 어떤 음식점에 우동 10인분과 스파게티 20인분을 만들 수 있는 재료가 준비되어 있다고 가정해봅시다. 은행원 알고리즘에서는 30명을 기준으로 예약을 받지 않고 10명 이내로 예약을 받습니다. 왜냐하면 10명이 넘어갔을 때 손님 모두가 우동을 시키는 경우 우동의 재료는 10인분 밖에 없기 때문에 우동의 재료가 소진되기 때문입니다. 이처럼 은행원 알고리즘은 최악의 경우를 기준으로 함으로써 문제상황을 철저히 회피하여 교착상태를 막습니다. 은행원 알고리즘은 다음과 같은 변수를 가집니다.

은행원 알고리즘에서는 각 프로세스의 기대자원과 비교하여 가용자원이 크거나 같으면 자원을 할당합니다. 가용자원이 기대자원보다 크다는 것은 그 자원을 사용해 작업을 종료할 프로세스가 있다는 의미이므로 안정상태입니다. 이러한 교착상태 회피에도 여러 문제점이 존재합니다. 먼저 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 합니다. 또한 미리 선언한 자원이 정확하지 않으면 교착상태 회피에서도 교착상태가 발생할 수 있습니다. 안정상태나 불안정상태를 파악하려면 시스템 자원의 수가 고정적이어야 합니다. 그러나 일시적인 고장이나 새로운 자원이 추가되는 경우가 자주 발생해 매우 유동적이기 때문에 이를 알기 어렵습니다. 위의 음식점에서 음식은 총 30인분이 준비되어 있지만 은행원 알고리즘에 의하면 10명만 받기 때문에 20인분의 음식은 버려지게 됩니다. 즉 자원이 낭비됩니다.

교착상태 검출

교착상태 예방은 실제로 구현하기 어렵고 교착상태 회피는 구현할 수는 있지만 자원을 낭비하는 등의 여러가지 문제점이 있습니다. 이에 따라 교착상태 검출이라는 가장 현실적인 해결방법이 등장했습니다. 교착상태 검출은 운영체제가 프로세스의 작업을 관찰하면서 교착상태 발생여부를 계속 주시하는 방법입니다. 만약 교착상태가 발견되면 이를 해결하기 위해 교착상태 회복 단계를 밟습니다. 그렇다면 운영체제는 어떤 방식으로 교착상태 발생여부를 판단할 수 있을까요?

가장 간단한 방법이 타임아웃을 통한 방식입니다. 일정시간동안 작업이 진행되지 않는 프로세스를 교착상태가 발생한 것으로 처리하는 방법입니다. 쉽게 구현이 가능하지만 교착상태로 인한 타임아웃이 아닌데도 프로세스가 강제 종료가 될 수 있고 하나의 운영체제 내에서 동작하는 프로세스들은 그 상태를 운영체제가 감시하기 때문에 타임아웃 방법을 적용할 수 있지만 분산 DB와 같이 데이터가 여러 시스템에 나뉘어 있고 각 시스템이 네트워크로 연결되어 있는 경우에는 원격지에 있는 프로세스의 응답이 없는 것이 교착상태 때문인지 네트워크 때문인지와 같이 원인을 정확히 파악할 수 없습니다. 이러한 문제에도 불구하고 타임아웃은 대부분의 데이터베이스와 운영체제에서 많이 선호합니다. 왜 그럴까요?

데이터베이스는 일관성이 깨지면 안되기 때문에 교착상태 처리가 운영체제보다 복잡합니다. 데이터를 조작할 때는 반드시 잠금을 얻은 후 작업을 시작해야 하고 만약 여러 개의 잠금을 얻어 작업을 진행하다가 타임아웃으로 프로세스가 종료되면 일부 데이터에 문제가 발생할 수 있습니다. 이러한 문제를 해결하기 위해 DB에서는 체크포인트(check point)와 롤백(roll back)을 사용합니다.

체크포인트는 작업을 하다가 문제가 발생하면 저장된 상태로 되돌아오기 위한 표시이고 체크포인트를 설정하면 현재 시스템 상태가 하드디스크에 저장되는데 이러한 데이터를 스냅숏이라고 합니다. 롤백은 작업을 하다가 문제가 발생하여 과거의 체크포인트로 되돌아가는 것을 말합니다. 롤백이 일어나면 저장된 스냅숏을 복원하여 시스템을 체크포인트 시점으로 되돌립니다.

타임아웃이 아닌 또다른 방법으로는 자원할당 그래프를 이용하여 교착상태를 검출하는 방법이 있습니다. 운영체제는 자원을 요청하거나 할당할 때마다 자원할당 그래프를 갱신하는데 이때 사이클이 발생하면 교착상태가 검출된 것으로 판단합니다. 위의 (a)그래프의 경우 사이클이 존재하지 않지만 (b)그래프의 경우 사이클이 존재하므로 (b)그래프는 교착상태가 있는 자원할당 그래프입니다.

교착상태 회복

위의 방법을 통해 교착상태가 검출되었다면 어떻게 이를 해결할까요? 교착상태 회복단계에서는 교착상태를 일으킨 프로세스를 강제로 종료합니다. 이 때 두 가지 방식으로 종료를 할 수 있는데 첫 번째는 교착상태를 유발한 모든 프로세스를 동시에 종료하는 것이고 두 번째는 교착상태를 일으킨 프로세스 중 하나를 선택해 순서대로 종료하는 것입니다. 교착상태를 유발한 모든 프로세스를 종료하는 경우 종료된 프로세스들이 동시에 작업을 다시 시작하면 교착상태를 다시 일으킬 가능성이 큽니다. 따라서 다시 실행할 때는 순차적으로 실행해야 하며 실행 순서를 정하는 기준이 필요합니다. 교착상태를 일으킨 프로세스 중 하나를 선택해 순서대로 종료를 할 때에는 어떤 프로세스부터 종료할 것인지 기준이 필요합니다. 우선순위가 낮은 프로세스를 먼저 종료하거나 우선순위가 같은 경우 작업시간이 짧은 프로세스를 먼저 종료하거나 위의 두 조건이 같을 경우 자원을 많이 사용하는 프로세스를 먼저 종료하는 것과 같은 기준이 있을 수 있습니다.

공유 자원(shared resource)는 여러 프로세스가 공동으로 이용하는 변수, 메모리, 파일 등을 말합니다. 그리고 다수의 프로세스가 이러한 한정된 공유 자원을 가지고 공동으로 작업할 때 문제가 발생할 수 있습니다. 이렇게 공유 자원 접근 순서에 따라 실행 결과가 달라지는 프로그램의 영역을 임계 구역이라고 합니다. 그렇다면 임계 구역에서 문제가 발생하지 않기 위해서는 어떠한 조건을 만족해야 할까요?

임계 구역 해결 조건

3가지 조건이 존재합니다. 상호 배제(mutual exclusion), 한정 대기(bounded waiting), 진행의 융통성(progress flexibility) 입니다.

• 상호배제(mutual exclusion) 한 프로세스가 임계 구역에 들어가면 다른 프로세스는 임계 구역에 들어갈 수 없는 것

• 한정 대기(bounded waiting) 어떤 프로세스도 무한 대기하지 않아야 함
• 진행의 융통성(progress flexibility) 한 프로세스가 다른 프로세스의 진행을 방해해서는 안 된다는 것

위 3가지 조건을 만족하는 코드를 설계하기 위해 다양한 방식이 나왔습니다. 다음 방식은 임계 구역 문제의 하드웨어적인 해결 방법입니다. 검사와 지정(test-and-set) 코드로 하드웨어의 지원을 받아 while(lock==true); 문과 lock=true; 문을 한꺼번에 실행하며 실행 중간에 타임아웃이 걸려 임계 구역을 보호하지 못하는 문제가 발생하지 않습니다. 주로 방산과 같은 중요한 프로그램에 사용되는 기술입니다.

while(testandset(&lock) == true);
//
임계구역
//
lock = false;

피터슨 알고리즘

피터슨 알고리즘은 변수 turn을 이용하여 두 프로세스가 동시에 lock을 설정하여 임계 구역에 진입불가 상황을 대비하는 알고리즘입니다. 만약 프로세스 P2의 잠금을 설정하지 않았거나 잠금을 설정했어도 turn이 1로 바뀌면 프로세스 P1은 임계 구역에 진입하여 작업을 완료한 후 잠금을 해제하고 임계 구역에서 벗어날 수 있습니다. 따라서 프로세스 P1이 임계 구역에 진입하기 위해서는 lock2가 false이거나 turn이 1이어야 합니다. 피터슨 알고리즘은 임계 구역 해결의 3가지 조건을 만족하지만 2개의 프로세스만 사용 가능하다는 단점이 존재합니다.

데커 알고리즘

데커 알고리즘의 동작 방식은 피터슨 알고리즘에 비해서는 조금 복잡합니다. 우선 공유 변수에서 lock1과 lock2가 false이고 turn값이 1인 상태에서 시작하며 프로세스 P1의 입장에서 본다고 가정합니다. 프로세스 P1에 잠금을 겁니다. 그리고 프로세스 P2에 잠금이 걸렸는지 확인합니다. 현재 lock2의 값이 false이므로 임계 구역으로 넘어가 작업을 하고 turn의 값을 2로 lock1의 값을 false로 지정합니다. 만약 프로세스 P2도 잠금이 걸렸다면 즉 lock2의 값이 true라면 turn 변수의 값을 통해서 우선 순위가 높은 프로세스를 확인합니다. 만약 P1이 높으면 임계 구역으로 진입하고 P2가 높으면 lock1을 false로 만들고 프로세스 P2의 작업이 끝날 때까지 기다립니다.

데커 알고리즘은 하드웨어의 도움 없이 임계 구역의 문제 해결이 가능하다는 장점이 있습니다.

세마포어(semaphore)

또 다른 임계 구역 문제 해결 방식으로는 세마포어가 있습니다. 세마포어는 다익스트라가 제안한 이론으로 프로세스가 임계 구역에 진입하기 전에 스위치를 사용 중으로 놓고 임계 구역으로 들어가는 것 입니다. 이후에 도착한 프로세스는 스위치의 상태를 확인하고 앞의 프로세스가 작업을 마칠 때까지 기다립니다. 프로세스가 작업을 마치면 다음 프로세스에게 임계 구역을 사용하라는 동기화 신호를 보냅니다. 세마포어는 사용 전에 Semaphore(n);을 이용하여 사용 가능한 자원의 개수 n개를 나타냅니다. 임계 구역 진입 전에 P();을 이용하여 사용 중이라고 표시합니다. 이는 마치 스위치를 눌러 사용 중인 상태를 나타내는 것과 같습니다. 임계 구역을 나오면 V();를 통해 스위치를 내리며 사용을 끝났음을 나타냅니다. P(); 과정에서 사용 가능한 자원의 개수 n이 n-1로 줄어들고 V();를 통해 사용이 끝났으므로 사용 가능한 자원이 n-1개에서 다시 n개로 되돌아 옵니다. 위의 그림에서 RS는 사용 가능한 자원의 수를 저장하는 변수입니다.

모니터(monitor)

하지만 세마포어를 위 그림과 같이 잘못 사용하는 경우 임계 구역을 보호하지 못하게 됩니다. 각각의 경우는 세마포어를 사용하지 않은 경우, P();를 2번 사용한 경우, V();와 P();의 순서를 바꾸어 사용한 경우에 해당합니다.

이러한 실수를 없애기 위해 생긴 방법이 모니터입니다. 모니터는 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만을 제공함으로서 자원을 보호하고 프로세스 간에 동기화를 시킵니다. 임계 구역으로 지정된 변수나 자원에 접근하고자 하는 프로세스는 직접 P()나 V()를 사용하지 않고 모니터에 작업을 요청하면 모니터는 요청받은 작업을 모니터 큐에 저장한 후 순서대로 처리하고 그 결과만 해당 프로세스에 알려줍니다.

교착상태(dead lock)

시스템 내에 임계 구역이 존재하면 프로세스 간 상호배제를 보장해야 합니다. 운영체제가 상호배제를 보장하기 위해 잠금을 사용하다 보면 2개 이상의 프로세스가 다른 프로세스의 작업 종료를 기다리며 작업이 더이상 진행되지 않는 교착상태에 빠지게 됩니다.

교착상태와 아사현상은 비슷해보이지만 다른 점이 있습니다. 아사현상은 운영체제가 잘못된 정책을 사용하여 특정 프로세스가 작업이 지연되는 문제를 말하고 교착상태는 여러 프로세스가 작업 중 자연적으로 발생하는 문제입니다. 따라서 운영체제는 감시를 하다가 교착상태를 감지하면 강제적으로 이를 해결해야 합니다.

위 그림의 경우 프로세스 P1은 프린터를 할당 받았지만 CD 레코더를 기다리고 있고 프로세스 P2는 CD 레코더를 할당 받았지만 프린터를 기다리고 있습니다. 이러한 무한 대기 상태를 교착상태라고 합니다. 데이터베이스 같은 응용프로그램에서도 일관성을 유지하기 위해 잠금을 사용하다가 교착 상태가 발생할 수 있으며 이러한 교착 상태로 인해 일관성이 깨지고 무결성 또한 깨질 수 있습니다.

위 그림에서 사용된 실선, 점선, 화살표가 자원할당 그래프(resource allocation graph)입니다. 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것입니다. 프로세스는 원으로, 자원은 사각형으로 표현하며 자원을 사용하고 있는 경우에는 자원으로부터 프로세스로 향하는 화살표 실선으로 표시하고 프로세스가 자원을 기다리는 경우는 프로세스로부터 자원으로 화살표 점선으로 표시합니다.

안드로이드 공부를 시작하면 자바와 코틀린이라는 두 가지 언어의 선택지를 만나게 된다. 나는 동아리에서 코틀린을 이용했기 때문에 자연스레 코틀린을 먼저 접하게 되었는데 딱히 이유는 알지 못했다. 코틀린이 대세다, 편하다 라는 얘기만 듣고 정작 왜 코틀린이 대세인지는 알지 못했다.

간결성(Concise)

• getter, setter 등을 따로 선언해주지 않아도 된다.

• 람다식이 간결하다.
• filter를 이용해 배열을 반복문 없이 확인할 수 있다.
• object class를 통해 싱글톤 패턴을 쉽게 구현할 수 있다.

안전성(Safety)

• 변수에 null 처리를 못하기 때문에 null point exception이 발생하지 않는다.

• null을 허용하려면 ? 키워드가 필요하다.
• auto-cast를 지원한다.

auto-cast 지원 예시를 살펴보자.

fun calculateTotal(obj: Any){
    if(obj is Invoice)
        obj.calculate()
}

위의 코드에서 obj에는 어떠한 형식이든 들어갈 수 있다.(코틀린에서 Any는 자바에서 최상위 클래스인 Object와 같은 개념이다) if문 안의 is는 타입을 확인하는 것으로 자바에서의 instanceOf 연산자와 같은 역할을 한다. 여기서 코틀린의 auto-cast가 일어난다. 코틀린은 타입이 맞는지 확인하는 순간 해당 타입이 맞으면 obj를 Any에서 Invoice타입으로 변형한다. 따라서 별도의 타입 변환 없이 obj.calculate()코드가 실행된다.

자바와의 상호호환(Interoperable)

• 코틀린은 자바와 100% 상호호환이 된다. 자바 코드를 코틀린으로 변환할 수 있고 코틀린 코드를 자바로 변환할 수 있다. 실제로 안드로이드 스튜디오에서 자바 코드를 복붙하면 코틀린으로 변환시켜준다.

친화적이다(Tool-Friendly)

• 자바에서 제공하는 툴을 모두 사용할 수 있고 더불어 코틀린만의 추가적인 툴들을 사용할 수 있다.

앱 구성 요소에는 4가지 유형이 있습니다. 각 유형은 뚜렷한 목적을 가지고 있으며 나름의 수명 주기가 있어 생성 및 소멸의 방식을 정의합니다.

1. 액티비티(Activity)

액티비티는 사용자와 상호작용하기 위한 진입점입니다. 액티비티는 사용자 인터페이스를 포함한 화면 하나를 나타냅니다. 여러 액티비티가 함께 작동하여 하나의 앱에서 짜임새 있는 사용자 환경을 구성하지만 각 액티비티는 서로 독립되어 있습니다. 따라서 인텐트(Intent)를 통해 하나의 앱에서 다른 앱의 액티비티를 시작할 수도 있습니다. 액티비티는 다음과 같이 시스템과 앱의 주요 상호 작용을 돕습니다.

• 사용자가 현재 관심을 가지고 있는 사항을 추적하여 액티비티를 호스팅하는 프로세스를 시스템에서 계속 실행하도록 합니다.

• 이전에 사용한 프로세스에 사용자가 다시 찾을 만한 액티비티(중단된 액티비티)가 있다는 것을 알고, 해당 프로세스를 유지하는 데 더 높은 우선순위를 부여합니다.
• 앱이 프로세스를 종료하도록 도와서 이전 상태가 복원되는 동시에 사용자가 액티비티로 돌아갈 수 있게 합니다.
• 앱이 서로 사용자 플로우를 구현하고 시스템이 이러한 플로우를 조정하기 위한 수단을 제공합니다.

또한 액티비티는 다음과 같은 특징을 갖습니다.

• 2개 이상의 액티비티를 동시에 보여줄 수 없습니다.

• 1개 이상의 View 혹은 ViewGroup을 포함합니다.
• 어플리케이션에는 반드시 하나 이상의 액티비티가 있어야 합니다.
• 액티비티 내에 프레그먼트를 추가하여 화면을 분할시킬 수 있습니다.

2. 서비스(Service)

서비스는 여러 가지 이유로 백그라운드에서 앱을 계속 실행하기 위한 다목적 진입점입니다. 이는 백그라운드에서 실행되는 구성 요소로, 오랫동안 실행되는 작업을 수행하거나 원격 프로세스를 위한 작업을 수행합니다. 서비스는 사용자 인터페이스를 제공하지 않습니다. 예를 들어 다른 앱을 실행했을 때에도 백그라운드에서 음악을 재생하거나 사용자와 액티비티 간의 상호작용을 차단하지 않고 네트워크를 통해 데이터를 가져올 수도 있습니다. 서비스는 다음과 같은 특징을 갖습니다.

• 네트워크와 연동이 가능합니다.

• 액티비티와 서비스 모두 UI 스레드라고 불리는 동일한 어플리케이션 스레드로 실행되기 때문에 서비스 내에서 별도의 스레드를 생성하여 작업을 처리해야 합니다.
• 어플리케이션이 종료되어도 이미 시작한 서비스는 백그라운드에서 계속 동작합니다.

3. Broadcast Receiver

Broadcast Receiver는 시스템(안드로이드 os)이 정기적인 사용자 플로우 밖에서 이벤트를 앱에 전달하도록 지원하는 구성 요소로, 앱이 시스템 전체의 브로드캐스트 알림에 응답할 수 있게 합니다. Broadcast Receiver도 앱으로 들어갈 수 있는 또 다른 명확한 진입점이기 때문에 현재 실행되지 않은 앱에도 시스템이 브로드캐스트로 전달할 수 있습니다. 대다수의 브로드캐스트는 시스템에서 발생합니다. 예를 들어 배터리가 부족하거나 사진을 캡쳐했다고 알리는 등의 경우에 자주 쓰이며 예정된 이벤트에 대한 알림과 같이 앱에서도 브로드캐스트를 시작할 수 있습니다. Broadcast Receiver는 사용자 인터페이스를 표시하지 않지만 상태 표시줄 알림을 생성하여 사용자에게 브로드캐스트 이벤트가 발생했다고 알릴 수 있습니다.

4. 콘텐츠 제공자

콘텐츠 제공자는 파일 시스템, SQLite 데이터베이스, 웹상이나 앱이 액세스할 수 있는 다른 모든 영구 저장 위치에 저장 가능한 데이터를 관리하고 다른 어플리케이션의 데이터를 제공하는 데 사용되는 컴포넌트입니다. 특정 어플리케이션이 사용하고 있는 데이터베이스를 공유하기 위해 사용하며 어플리케이션 간의 데이터 공유를 위해 표준화된 인터페이스를 제공합니다. 다음은 콘텐츠 제공자의 특징입니다.

• 외부 어플리케이션이 현재 실행 중인 어플리케이션 내에 있는 데이터베이스(DB)에 함부로 접근하지 못하게 할 수 있으면서 나 자산이 공개한 데이터만 공유할 수 있도록 도와줍니다.

• 작은 데이터들은 인텐트로 어플리케이션끼리 데이터를 공유하고 음악 또는 사진 파일과 같은 큰 데이터들은 콘텐츠 프로바이더를 사용하는 것이 적합합니다.
• 프로바이더는 데이터의 Read, Write에 대한 퍼미션이 있어야 어플리케이션에 접근이 가능합니다.
• 데이터베이스의 CRUD 원칙을 준수합니다.

인텐트(Intent)

액티비티, 서비스, Broadcast Receiver는 인텐트라는 비동기식 메시지로 활성화됩니다. 인텐트는 런타임에서 각 구성 요소를 서로 바인딩합니다. 컴포넌트에 액션(action), 데이터(data) 등을 전달하는 일종의 메신저 역할이라고 생각하면 됩니다. 즉 구성 요소가 어느 앱에 속하든 관계없이 다른 구성 요소로부터 작업을 요청하는 역할을 합니다. 가장 많이 사용하는 예로는 액티비티 간의 화면 전환이 있습니다.

참고 사이트: 구글 공식 문서, 참고 블로그

안드로이드 관련 자료들을 찾아보면 안드로이드 컴포즈에 관한 글이나 자료가 굉장히 많습니다. 기업의 채용 공고를 찾아봐도 android compose를 다루는 능력을 요구하는 회사가 굉장히 많았습니다. 도대체 안드로이드 컴포즈는 뭘까요? 구글 공식 문서에 따르면 다음과 같이 컴포즈에 대해 소개하고 있습니다.

"Jetpack Compose는 네이티브 UI를 빌드하기 위한 Android의 최신 도구 키트이다. Jetpack Compose는 Android에서 UI 개발을 간소화하고 가속화한다"

🤔 왜 쓰는걸까?

그렇다면 컴포즈는 왜 사용하는 걸까요? 기존의 UI를 작성하는 XML파일 방식과는 어떤 차이점이 있는걸까요? 구글 공식 문서에 따르면 다음과 같은 장점들로 컴포즈를 사용한다고 합니다.

• 코드 감소 코드를 적게 작성하면 개발의 모든 단계에 영향을 미칩니다. 작성자는 테스트와 디버그 작업과 버그 발생 가능성이 줄어들어 당면 문제에 집중할 수 있게 되며 검토자 또는 유지관리자는 읽고, 이해하고, 검토하고, 유지관리할 코드가 적어집니다.

• 직관적 Compose는 선언적 API를 사용합니다. 즉, Compose가 나머지를 처리하므로 UI를 설명하기만 하면 됩니다. API는 직관적이므로 찾아서 사용하기가 쉽습니다.
• 빠른 개발 과정 Compose는 기존의 모든 코드와 호환됩니다. Compose에서 Views를, Views에서 Compose 코드를 호출할 수 있습니다. Navigation, ViewModel, Kotlin 코루틴과 같은 대부분의 일반적인 라이브러리는 Compose와 함께 작동하므로 언제 어디서든 원하는 대로 채택할 수 있습니다.
• 강력한 성능 Compose는 Android 플랫폼 API에 직접 액세스하고 머티리얼 디자인, 어두운 테마, 애니메이션 등을 기본적으로 지원하여 멋진 앱을 만들 수 있습니다.

실제로 구글에서 제공하는 튜토리얼 문서를 따라 안드로이드 컴포즈를 살짝 사용해 보았을 뿐인데 위와 같은 장점들을 느낄 수 있었습니다. 너무 흥미롭고 신기해서 컴포즈에 대해서 이것저것 찾아보다가 구글이 왜 컴포즈에 힘을 싣고 있는지 알게되었습니다. 구글이 컴포즈를 만들고 빠르게 개발하는 이유는 크게 3가지 입니다.

1. XML 파일을 사용하지 않는 UI 작성

기존의 XML 파일을 통해 UI를 작성하는 경우(명령형 UI) findViewById와 같이 데이터와 뷰 사이에 추가적인 레이어가 필요합니다. 하지만 컴포즈를 사용하면 추가적인 레이어 없이 데이터를 바로 UI에 적용할 수 있습니다.

2. 선언형 UI

선언형 프로그래밍이란 기존의 명령형 프로그래밍을 세련되게 추상화한 것이라고 볼 수 있습니다. 기존의 명령형 프로그래밍에서는 컴퓨터에게 원하는 명령을 내리기 위해서 a to z까지 세세하게 명령을 내려야 했습니다. 하지만 선언형 프로그래밍에서는 일일이 명령하는 것이 아니라 원하는 기능을 선언하기만 하면 알아서 컴퓨터가 처리해줍니다. 안드로이드의 XML 파일은 이미 선언형 프로그래밍 방식이지만 이미 선언한 UI를 동적으로 변경하는 것은 매우 복잡했습니다. 하지만 컴포즈는 선언형 프로그래밍을 사용함과 동시에 굉장히 쉽게 동적으로 UI를 변경할 수 있습니다.

명령형 프로그래밍 예시

val myList = listOf(1,2,3)
val targetList = mutableListOf<Int>()
for (i in myList) {
    if (i % 2 == 0) tempList.add(i)
}

선언형 프로그래밍 예시

val targetList = listOf(1,2,3).filter { it % 2 == 0 }

3. 상속이 아닌 확장

기존의 안드로이드 UI의 뷰는 모두 상속으로 이루어져 있었습니다. 하드웨어가 발달하고 복잡한 뷰들이 등장하면서 상속에 대한 관계도 애매해졌습니다. 예를 들어 Button은 TextView를 상속받은 것인데 Button 안의 Text를 고치기 위해 Button의 부모인 TextView로 가서 Text를 고치는 것은 안됩니다. 이를 컴포즈는 해결해줍니다.

참고한 블로그

운영체제는 커널과 인터페이스로 구성되어 있고 커널은 프로세스 관리와 같은 운영체제의 핵심적인 기능을 담당한다고 했었다. 그렇다면 프로세스는 뭘까?

프로세스란 프로그램이 실행을 위해 메모리에 올라온 동적인 상태이다. OS관점에서의 프로세스는 하나의 작업 단위이다. 프로그램이 프로세스가 된다는 것은 운영체제로부터 프로세스 제어 블록(PCB)를 얻는다는 뜻이고 프로세스가 종료된다는 것은 해당 프로세스 제어 블록이 폐기된다는 뜻이다.

프로세스 = 프로그램 + 프로세스 제어 블록 프로그램 = 프로세스 - 프로세스 제어 블록

프로세스 제어 블록..? 뭔가 중요해 보이는데 그건 뭐지?

🤔 프로세스 제어 블록(Process Control Block, PCB)

프로세스 제어 블록은 운영체제가 해당 프로세스를 위해 관리하는 자료 구조이다. 각 프로세스는 고유의 프로세스 제어 블록을 가지며 다음과 같이 구성 되어 있다.

이미지 출처 : https://math-coding.tistory.com/99

• 포인터 : 준비 상태나 대기 상태의 큐를 구현할 때 사용

• 프로세스 상태 : 프로세스가 현재 어떤 상태에 있는지를 나타내는 정보
• 프로세스 구분자 : 운영체제 내에 있는 여러 프로세스를 구현하기 위한 구분자 -> Process Identification, PID라고 한다.
• 프로그램 카운터 : 다음에 실행될 명령어의 위치를 가리키는 프로그램 카운터의 값
• 프로세스 우선순위 : 프로세스의 실행 순서를 결정하는 우선순위
• 각종 레지스터 정보 : 프로세스가 실행되는 중에 사용하던 레지스터의 값
• 메모리 관리 정보 : 프로세스가 메모리의 어디에 있는지 나타내는 메모리 위치 정보, 메모리 보호를 위해 사용하는 경계 레지스터 값과 한계 레지스터 값 등
• 할당된 자원 정보 : 프로세스를 실행하기 위해 사용하는 입출력 자원이나 오픈 파일 등에 대한 정보
• 계정 정보 : 계정 번호, CPU 할당 시간, CPU 사용 시간 등
• 부모 프로세스 구분자와 자식 프로세스 구분자 : 부모 프로세스를 가리키는 PPID와 자식 프로세스를 가리키는 CPID 정보

뭔가 굉장히 복잡해 보이지만 일단 프로세스에 관련된 정보를 가지는 자료 구조라고 이해해보자! 그렇다면 프로세스와 PCB는 어떠한 상태로 존재하고 운영체제가 관리할까?

💻 프로세스의 상태

기본적으로 프로세스는 네 가지 상태로 존재하지만 운영체제가 발전함에 따라 한 가지 상태를 추가하여 다섯 가지 상태로 존재하는 경우가 많다. 네 가지 상태부터 살펴보자. 이미지 출처 : https://cch5980.github.io/process/2020/11/12/%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4-%EC%83%81%ED%83%9C.html 만든 사람 : cch

• 생성 상태 : 프로세스가 메모리에 올라와 실행 준비를 완료한 상태(PCB 생성)

• 준비 상태 : 생성된 프로세스가 CPU를 얻을 때까지 기다리는 상태
• 실행 상태 : 준비 상태에 있는 프로세스 중 하나가 CPU를 얻어 실제 작업을 수행하는 상태
• 완료 상태 : 실행 상태의 프로세스가 주어진 시간 동안 작업을 마치면 진입하는 상태(PCB 폐기)
• 디스패치 : 준비 상태의 프로세스 중 하나를 골라 실행 상태로 바꾸는 CPU 스케줄러의 작업
• 타임아웃 : 프로세스가 자신에게 주어진 하나의 타임 슬라이스 동안 작업을 끝내지 못하면 다시 준비 상태로 돌아가는 것

다음은 다섯 가지 상태를 알아보자. 이미지 출처 : https://cch5980.github.io/process/2020/11/12/%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4-%EC%83%81%ED%83%9C.html 만든 사람 : cch

• 생성 상태 : 프로그램이 메모리에 올라오고 운영체제로부터 프로세스 제어 블록을 할당받은 상태, 생성된 프로세스는 바로 실행되는 것이 아니라 준비 상태에서 자기 순서를 기다리며, 프로세스 제어 블록도 같이 준비 상태로 옮겨짐

• 준비 상태 : 실행 대기 중인 모든 프로세스가 자기 순서를 기다리는 상태, 프로세스 제어 블록은 준비 큐에서 기다리며 CPU 스커줄러에 의해 관리. CPU 스케줄러가 어떤 프로세스 제어 블록을 선택하는 작업이 dispatch(PID)이고 dispatch(PID)를 실행하면 해당 프로세스가 준비 상태에서 실행 상태로 바뀌어 작업이 이루어짐
• 실행 상태 : 프로세스가 CPU를 할당받아 실행되는 상태, 실행 상태에 있는 프로세스는 타임 슬라이스 동안만 작업할 수 있음. 시간이 끝나면 timeout(PID)가 실행되어 실행 상태에서 준비 상태로 옮겨짐. 실행 상태 동안 작업이 완료되면 exit(PID)가 실행되어 프로세스가 정상 종료됨. 실행 상태에 있는 프로세스가 입출력을 요청하면 CPU는 입출력 관리자에게 입출력을 요청하고 block(PID)를 실행. block(PID)는 입출력이 완료될 때까지 작업을 진행할 수 없기 때문에 해당 프로세스를 대기 상태로 옮기고 CPU 스케줄러는 새로운 프로세스를 실행 상태로 가져옴
• 대기 상태 : 실행 상태에 있는 프로세스가 입출력을 요청하면 입출력이 완료될 때까지 기다리는 상태. 대기 상태의 프로세스는 입출력 장치별로 마련된 큐에서 기다리다가 입출력이 완료되면 인터럽트가 발생하고 대기 상태에 있는 여러 프로세스 중 해당 인터럽트로 깨어날 프로세스를 찾는데 이것이 wakeup(PID)이고 wakeup(PID)로 해당 프로세스의 프로세스 제어 블록이 준비 상태로 이동함
• 완료 상태 : 프로세스가 종료되는 상태로 코드와 사용했던 데이터를 메모리에서 삭제하고 프로세스 제어 블록을 폐기함. 정상적인 종료는 exit(PID)로 처리

문맥 교환이란 CPU를 차지하던 프로세스가 나가고 새로운 프로세스를 받아들이는 작업으로 실행 상태에서 나가는 프로세스 제어 블록에는 지금까지의 작업 내용을 저장하고 반대로 실행 상태로 들어오는 프로세스 제어 블록의 내용으로 CPU가 다시 세팅 된다. 두 프로세스의 PCB를 교환하는 작업이다. 인터럽트나 타임 아웃이 발생하면 일어난다.

💻 프로세스의 구조

이미지 출처 : https://zeichi.tistory.com/27

• 코드 영역 : 프로그램의 본문이 기술된 곳으로 프로그래머가 작성한 코드가 탑재되며 탑재된 코드는 읽기 전용으로 처리된다.

• 데이터 영역 : 코드가 실행되면서 사용하는 변수나 파일 등의 각종 데이터를 모아놓은 곳으로 데이터는 변하는 값이기 때문에 이곳의 내용은 기본적으로 읽기와 쓰기가 가능하다.
• 스택 영역 : 운영체제가 프로세스를 실행하기 위해 부수적으로 필요한 데이터를 모아놓은 곳으로 프로세스 내에서 함수를 호출하면 함수를 수행하고 원래 프로그램으로 되돌아올 위치를 이 영역에 저장한다. 운영체제가 사용자의 프로세스를 작동하기 위해 유지하는 영역이므로 사용자에게는 보이지 않는다.

💻 프로세스의 복사

프로세스는 fork()라는 함수의 호출에 의해 복사된다. fork()가 무슨 함수인지 자세히 알아보자!

fork()는 실행 중인 프로세스로부터 새로운 프로세스를 복사하는 함수이다. 이 때 실행하던 프로세스는 부모 프로세스, 새로 생긴 프로세스는 자식 프로세스로서 부모-자식 관계가 된다. 단 프로세스 제어 블록의 내용 중 프로세스 구분자, 메모리 관련 정보, 부모 프로세스 구분자와 자식 프로세스 구분자의 내용은 변경된다.

fork() 시스템 호출의 장점은 프로세스 생성 속도가 빠르고 추가 작업 없이 자원을 상속할 수 있으며 시스템 관리를 효율적으로 할 수 있다.

드디어 말로만 들었던 운영체제 수업을 듣게 되었다...!! CS면접에서 빼먹을 수 없다, 굉장히 중요한 과목이다는 말만 들었을 뿐 무슨 내용을 배우는지 왜 배우는지에 대해서는 알지 못했다. 운영체제가 뭐야? 라고 하면 음.. 윈도우같은거? 뭐.. 안드로이드?라고 하는 수준이었다. 그럼 운영체제는 무엇일까?

• 운영체제의 정의

  운영체제는 응용 프로그램이나 사용자에게 컴퓨터 자원을 사용할 수 있는 인터페이스를 제공하고 그 결과를 돌려주는 시스템 소프트웨어이다. 또한 디바이스의 전원을 켜면 가장 먼저 만나게 되는 소프트웨어이다.

  위의 사진에도 나와있듯이 운영체제는 인터페이스와 커널로 이루어져있다. 이 포스트의 제목이 커널과 인터페이스 인 것도 운영체제의 구조 때문이다. 그렇다면 커널은 뭐고 인터페이스는 뭐지?

💡 커널과 인터페이스의 정의

커널은 프로세스 관리, 메모리 관리, 저장장치 관리와 같은 운영체제의 핵심적인 기능을 모아놓은 것이다.

인터페이스는 커널에 사용자의 명령을 전달하고 실행 결과를 사용자에게 알려주는 역할을 한다.

시스템 호출은 커널이 자신을 보호하기 위해 만든 인터페이스로 사용자나 응용 프로그램으로부터 컴퓨터 자원을 보호하기 위해 자원에 직접 접근하는 것을 차단한다.

드라이버는 커널과 하드웨어의 인터페이스를 담당하며 디바이스 드라이버라고도 불린다. 마우스와 같이 간단한 제품은 드라이버를 커널이 가지고 있으나, 그래픽카드와 같이 복잡한 하드웨어의 경우 제작자가 드라이버를 제공한다.

아 그러면 인터페이스는 커널과 사용자 간의 다리 역할이고 커널이 핵심적인 기능을 하는 것이기 때문에 운영체제의 핵심 기능은 프로세스 관리, 메모리 관리, 저장장치 관리 등이 있겠군!

• 운영체제의 역할과 목표

  자원 관리 <-------> 효율성
  자원 보호 <-------> 안정성
  하드웨어 인터페이스 제공 <-------> 확장성
  사용자 인터페이스 제공 <--------> 편리성

📝 커널의 구성

커널은 여러가지 형태로 존재하는데 크게 단일형 구조 커널, 계층형 구조 커널, 마이크로 구조 커널로 나뉜다.

• 단일형 구조 커널

  초창기 운영체제 구조이고 커널의 핵심 기능을 구현하는 모듈들이 구분 없이 하나로 구성되어 있다. MS-DOS가 단일형 구조 커널을 가진다.
  

  • 장점 모듈 간의 통신 비용이 줄어들어 효율적인 운영이 가능하다.
    
    
  • 단점 모든 모듈이 하나로 묶여 있기 때문에 버그나 오류를 처리하기가 어렵다. 상호 의존성이 높아 기능상의 작은 결함이 시스템 전체로 확산될 수 있다. 다양한 환경의 시스템에 적용하기 어렵다. 현대의 운영체제는 매우 크고 복잡해 단일형 구조 커널로는 구현하기가 어렵다.

• 계층형 구조 커널

  비슷한 기능을 가진 모듈을 묶어서 하나의 계층으로 만들고 계층 간의 통신을 통해 운영체제를 구현하는 방식으로 window와 같은 운영체제에서 사용하는 구조이다.
  

  • 마이크로 구조 커널

    프로세스 관리, 메모리 관리, 프로세스 간 통신 관리 등 기본적인 기능만 제공하며 커널의 각 모듈은 세분화되어 존재하고 모듈 간의 정보 교환은 프로세스 간 통신을 이용하여 이루어진다. 간단하게 CPU용량이 작은 시스템에 사용하므로 android, ios와 같은 휴대용 디바이스의 운영체제에 많이 사용된다.

이미지 출처 : 쉽게 배우는 운영체제(조성호)

앞서 공부한 다익스트라 알고리즘과 벨만-포드 알고리즘이 특정 노드로부터의 최단거리를 구할 수 있는 알고리즘이었다면 플로이드-와셜 알고리즘은 모든 노드 사이의 최단거리를 구할 수 있다. 이렇게 말하면 더 어려운 알고리즘일 것 같지만 앞의 알고리즘들에 비해서 구현 난이도는 낮은 편이다.

🤔 어떻게 구현하지?

핵심 원리는 특정 노드를 거쳐가는 경우의 거리값과 현재 저장되어 있는 최단거리 값을 비교해서 값을 갱신하는 것이다. 이를 점화식으로 나타내면 다음과 같다. D는 거리로 기존에 저장되어 있던 a노드에서 b노드로 가는 거리를 아래 첨자로 표현한 것이다. 점화식을 사용해 문제를 부분적으로 해결할 수 있고 최소값을 그래프의 배열에 메모이제이션하기 때문에 플로이드-와셜 알고리즘은 다이나믹 프로그래밍에 속한다. 노드의 개수가 K개라면 K개의 노드를 돌면서 모든 노드들을 비교해야 하기 때문에 삼중 반복문을 사용한다. 따라서 시간복잡도가 다익스트라 알고리즘에 비해 크기 때문에 조건을 잘 보고 사용해야 한다. 보통 노드가 500개 이하이고 문제에서 모든 노드들 사이의 최단경로를 구해야한다고 할 때 사용하는 것 같다.

💻 구현해보자!

백준에서 플로이드-와셜 알고리즘을 사용하는 대표적인 문제이다. 11404번이다.

import sys
input = sys.stdin.readline

INF = 1e9

n = int(input())
m = int(input())

# 그래프 배열 만들고 자기 자신은 0으로 설정
graph = [[INF]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            graph[i][j] = 0

# 시작 도시, 도착 도시, 버스 한 번 타는데 필요한 비용을 입력받아 graph에 저장
# 이 때 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있으므로 같은 노선일 경우 최솟값을 저장
for i in range(m):
    a, b, c = map(int, input().split())
    if graph[a][b] > c:
        graph[a][b] = c

# 플로이드-와셜 알고리즘
# 특정 노드 k를 거쳐가는 경우를 생각해서 k를 안거치는 경우의 값과 k를 거치는 경우의 값을 비교해서 갱신
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])

for i in range(1, n+1):
    for j in range(1, n+1):
        if graph[i][j] >= INF:
            print(0, end=' ')
        else:
            print(graph[i][j], end=' ')
    print()

그래프를 사용하는 최단거리 알고리즘 중 하나이다. 알고리즘은 배워도 배워도 끝이 없다. 하나 배우면 앞에 배운거 까먹고 ㅎㅎ.. 그래서 이렇게 기록을 해놔야 한다. 다익스트라 알고리즘이라는 많이들 사용하는 알고리즘이 있는데 왜 벨만-포드 알고리즘을 써야하는 경우가 생기는가?
-> 간선의 가중치가 음수가 포함된 경우에도 최단거리를 구할 수 있기 때문이다. 특히 가중치가 음수인 경우 간선을 거치면 거칠수록 최단거리가 점점 작아져 음의 무한대로 발산하는 경우가 생기는데, 벨만-포드 알고리즘을 통해 이러한 경우를 구별할 수 있다.

💡 어떤 원리인데?

기본적인 원리는 다익스트라 알고리즘과 같다. 다른점은 다익스트라 알고리즘은 하나의 정점을 기준으로 해당 정점에 연결된 간선들과 정점을 고려했다면 벨만-포드 알고리즘은 모든 정점을 돌면서 모든 간선을 고려해야 한다. 왜냐하면 가중치가 음수인 간선은 항상 최단거리를 줄일 여지가 있기 때문이다. 따라서 벨만-포드 알고리즘의 시간복잡도는 O(|V||E|)로 다익스트라 알고리즘보다는 느리다.

💡 구현 코드

일반화한 벨만-포드 알고리즘 코드는 아니고 백준의 11657번 타임머신 코드이다. 그냥 벨만-포드를 정석적으로 사용하면 되는 문제라서 바로 올린다.

import sys
input = sys.stdin.readline

INF = 1e9

# 벨만 포드 알고리즘
def bf(start):
    # 시작 노드는 최단거리가 자기 자신이므로 0으로 줌
    dists[start] = 0
    # 값을 계속해서 갱신하기 때문에 N번 순회함
    # N-1번 순회해도 되는데 N번 순회하는 이유는 음수 간선이 사이클로 존재할 경우 최단 거리를 표시할 수 없는 경우가 발생하는지 여부를 판단하기 위함
    for i in range(N):
        # 모든 간선을 순회함
        for j in range(M):
            # 간선의 정보를 저장한 배열에서 현재 노드, 연결된 노드, 값을 가져옴
            cur_node = edges[j][0]
            next_node = edges[j][1]
            cost = edges[j][2]
            # cur_node를 거쳐서 next_node로 도달했을 때의 거리값이 최단거리 배열에 기록된 거리값보다 작으면 값을 갱신해줌
            if dists[cur_node]!=INF and dists[next_node] > dists[cur_node] + cost:
                dists[next_node] = dists[cur_node] + cost
                # 이미 N-1번 순회해서 값의 갱신이 더이상 일어나지 않아야 하는데 갱신이 일어난다는 것은 음수 간선에 의한 순환이 일어난다는 것임
                if i==N-1:
                    return True
    return False

# 노드의 개수 N, 간선의 개수 M
N, M = map(int, input().split())

# 간선의 정보를 저장할 배열
edges = []

# 1번 노드로부터의 최단 거리를 저장할 배열
dists = [INF] * (N+1)

# 간선의 정보를 입력받음 각 정보는 A노드에서 B노드로 갈 때 C의 값을 가짐
for _ in range(M):
    A, B, C = map(int, input().split())
    edges.append((A, B, C))

isCycle = bf(1)

if isCycle == True:
    print(-1)
else:
    for i in range(2, N+1):
        if dists[i] == INF:
            print(-1)
        else:
            print(dists[i])

앱개발을 하다보면 다음 사진과 같이 반복되는 형식의 뷰를 나열해야 하는 경우가 있다.

사진에서는 특정 사용자의 프로필 사진, 이름 접속 상태 등이 반복적으로 나타난다. 이러한 뷰를 우리는 리스트(list)라고 한다. 그리고 안드로이드에서는 리스트뷰(List View)를 통해 이를 구현할 수 있다.

그런데 안드로이드 공부를 하다보면 리스트뷰 대신 리사이클러뷰를 사용하는 것이 좋다는 의견을 많이 듣는다. 왜그럴까? 항상 어떤 기술이 왜 사용되는지에 대해 알아볼 필요가 있다.

안드로이드 제트팩의 한 요소인 리사이클러뷰 안드로이드 공식문서를 들여다보면 (항상 공식문서를 중심으로 공부하고 서칭하는 것이 좋다.) 화면에서 스크롤된 뷰가 재사용된다고 나온다. 즉, 어차피 같은 형식의 뷰이니 밑으로 내리면서 사라진 뷰를 안의 내용만 바꿔서 재사용한다는 것이다. -> 뷰를 재사용하면 앱의 응답성을 개선하고 전력 소모를 줄이기 때문에 성능이 개선된다. 따라서 기존의 리스트뷰 대신 리사이클러뷰를 사용한다.

💡 사용방법

그렇다면 리사이클러뷰는 어떻게 사용하는지에 대해 알아보자. 개인적으로 처음 리사이클러뷰를 접했을 때는 굉장히 어렵고 복잡하다고 느꼈다. 근데 코드를 한줄한줄 파악하면서 따라하다보면 어느새 적응이 된다.

1. 반복되는 뷰를 만든다. 맨 위의 사진인 카카오톡 친구 목록을 예를 들면 밑의 사진과 같은 형식이 반복됨을 알 수 있다. 안드로이드 스튜디오의 res->layout 패키지 안에 반복되는 뷰의 xml파일을 만든다. 보통 이렇게 반복되는 뷰의 이름은 item을 붙이는 경우가 많다.

2. 반복되는 뷰가 나타날 xml파일에 리사이클러뷰를 추가한다. 원하는 위치에 다른 뷰처럼 추가하면 된다.

        <androidx.recyclerview.widget.RecyclerView
            android:id="@+id/scrap_recycler_view"
            android:layout_width="match_parent"
            android:layout_height="0dp"
            app:layout_constraintTop_toBottomOf="@id/history_title_view"
            app:layout_constraintLeft_toLeftOf="parent"
            app:layout_constraintRight_toRightOf="parent"
            app:layout_constraintBottom_toBottomOf="parent"
            android:layout_marginTop="10dp"
            app:layoutManager="androidx.recyclerview.widget.LinearLayoutManager"
            tools:listitem="@layout/item_idea_list_recyclerview"
            />

여기서 중요한 것은 아까 만든 item.xml파일을 반복시킬 것이라는 것을 리사이클러뷰에게 알려주어야 한다. 따라서 tools:listitem에 아까 만든 item.xml파일을 연결해준다. 또한 app:layoutManager를 통해 어떤 수직으로 나열할 것인지 그리드 형태로 나열할 것인지 등을 선택할 수 있다. 이는 검색을 통해 본인에게 맞는 것을 선택해 쓰면 된다.

3. 여기서부터 복잡하다. 바로 adapter와 viewholder를 만드는 것이다. 공식문서에 따르면 ViewHolder는 목록에 있는 개별 항목의 레이아웃을 포함하는 View의 래퍼, Adapter는 필요에 따라 ViewHolder 객체를 만들고 이러한 뷰에 데이터를 설정하는 것이라고 나온다. 말이 좀 어려운데, 쉽게 말해서 viewholder를 통해 1번에서 만든 item.xml에 들어갈 요소 즉, 프로필 사진, 이름, 활동 상태 등의 뷰에 서버에서 받아온 데이터나 직접 입력한 데이터를 넣어준다. 그리고 adpater는 이러한 데이터를 viewholder에 넣어주기 위한 중간 다리 역할을 한다고 생각하면 된다. 안드로이드 프로젝트에서 새로운 코틀린 파일을 만들고 다음과 같은 코드를 이용한다.

// 여기서 dataSet의 형식은 본인이 서버에서 데이터를 GET해서 오는 것이라면 reponsedata를, 직접 만든 데이터클래스를 사용하고 싶으면 dataclass의 이름을 넣으면 된다.
class CustomAdapter(private val dataSet: Array<String>) :
        RecyclerView.Adapter<CustomAdapter.ViewHolder>() {

     // 뷰홀더를 만들고 뷰를 초기화하는 함수이다. 아직 바인딩이 안되었기 때문에 뷰에 내용이 직접적으로 담기는 과정은 아니다.    
    override fun onCreateViewHolder(viewGroup: ViewGroup, viewType: Int): ViewHolder {

        val view = LayoutInflater.from(viewGroup.context)
                .inflate(R.layout.text_row_item, viewGroup, false)

        return ViewHolder(view)
    }

    // 여기서 뷰와 데이터의 결합이 이루어진다. 만약 이미지 url을 가져오면 이 함수에서 url을 뷰에 넣어서 사진을 출력할 수 있다.(단, 이미지는 Glide와 같은 외부 라이브러리 사용을 추천)
    override fun onBindViewHolder(viewHolder: ViewHolder, position: Int) {
        // 이런식으로 글자를 넣을 수도 있다.
        viewHolder.textView.text = dataSet[position]
    }

    // 총 몇개의 반복되는 뷰 데이터가 있는지, 즉 친구목록에서 총 친구가 몇 명인지와 같다.
    override fun getItemCount() = dataSet.size

}

4. 어뎁터와 뷰홀더를 만들었으면 리사이클러뷰를 사용하는 xml과 연결된 kt파일로 가서 리사이클러뷰를 객체 참조한다. findViewById를 쓰거나 뷰 바인딩으로 참조하면된다. 그리고 참조한 리사이클러뷰의 어댑터를 작성한 어댑터로 바꾸어준다.

binding.myRecyclerView.adapter = CustomAdapter()

그리고 원하는 데이터를 넣은 뒤 데이터가 변경되었다는 것을 알려주기 위해서 다음과 같이 어댑터에게 알려주는 코드를 사용한다. 즉, 이 코드를 통해 리사이클러뷰를 갱신할 수 있다.

CustomAdapter().notifyDataSetChanged()

사실 리사이클러뷰는 안드로이드의 기본 중 하나이고 다른 블로그에 너무나 정리가 잘되어있어서 나만의 필기용으로 정리했다. (혹시라도 안드로이드 처음 하는 분이거나 도움이 필요하신 분이라면 댓글로 질문 남겨주시면 최대한 도와드리겠습니다.)

💡 활용

프로젝트를 하다보면 리사이클러뷰가 정말 굉장히 많이 쓰인다. 근데 위의 친구목록처럼 같은 형태로 반복되는 경우도 있지만 아닌 경우도 많다. 내가 프로젝트에서 사용했던 활용을 공유해보자고 한다.

1. 채팅과 같은 리사이클러뷰 채팅은 상대방의 메시지와 나의 메시지로 구성이 된다.일반적으로 상대방의 메시지의 경우 왼쪽에 말풍선과 같은 ChatView가 나타나있고 내가 보낸 메시지의 경우 오른쪽에 ChatView가 나타나고 둘의 색 또한 다르다. 하지만 동적으로 계속해서 리스트가 추가된다. 즉, 리사이클러뷰를 이용해야 한다. 이럴때는 어떻게 할까?

-> 하나의 adapter 안에 viewholder를 2개 만든다. 하나의 뷰홀더에는 상대방의 메시지를 상대방 ChatView에 넣는 작업을 하고 하나의 뷰홀더에는 나의 메시지를 나의 ChatView에 넣는 작업을 한뒤, onBindViewHolder에서 어떠한 뷰홀더를 사용할 것인지 결정한다. 나 같은 경우는 메시지 작성자의 아이디를 나의 아이디와 비교해 상대방인지 나인지 결정했다.

override fun onBindViewHolder(holder: RecyclerView.ViewHolder, position: Int) {
        if(messageList[position].senderId== userNickName){
            (holder as MyChatViewHolder).onBind(messageList[position])
            holder.setIsRecyclable(false)
        }
        else{
            (holder as ChatViewHolder).onBind(messageList[position])
            holder.setIsRecyclable(false)
        }
    }

2. 중첩 리사이클러뷰 ToDo 리스트같은 앱을 만들다보면 날짜를 기준으로 날짜 밑에 내가 적은 할일들이 쭉 나열되는 것을 구현해야 될 때가 있다. 즉, 날짜들도 리사이클러뷰로 구현해야하고 해당 날짜에 할 일들도 리사이클러뷰 형태로 구현해야한다. 이러한 것을 중첩 리사이클러뷰라고 부른다. 이 때는 그냥 리사이클러뷰를 두 개 만든다고 생각하면 된다. adpater도 2개 만들어야한다. 그 후 날짜 리사이클러뷰(즉, 범위가 더 큰 리사이클러뷰)의 어댑터의 뷰홀더에서 바인딩한 리사이클러뷰의 어댑터를 작은 범위의 리사이클러뷰 어댑터로 설정하면 된다.

게시판을 구현하던지, SNS앱을 구현하다보면 서버에 이미지와 같은 파일을 보내야할 때가 있다. 사실 저번 프로젝트에서도 사진과 String과 같은 데이터를 서버에 업로드해야했지만 결국 내가 못하고 다른 팀원이 했었다. 그래서 이번 프로젝트에서는 꼭 성공하고 싶었다. 관련 자료를 찾아봐도 내 프로젝트와 환경이 다르고 api 형식도 달라서 한참 헤맸다. 코틀린으로 된 코드도 많이 없었다...

먼저 위 사진은 서버파트 쪽에서 넘겨준 api 형식이다. 일단 이미지 파일과 같은 파일이 있는 경우 form-data 형식으로 api를 작성해서 넘겨줄 확률이 매우 높다.

먼저 retrofit의 service를 작성할 때 맨 윗줄에 Multipart를 어노테이션 해야 한다. 그 뒤 @Body를 통해 보내던 request를 저 위의 사진인 KEY, VALUE 개수 많큼 @Part를 이용해서 데이터를 담아야한다.

interface CreateProjectService {
    @Multipart // 중요!!
    @POST("/project/registration")
    fun postCreateProject(
        @Header("X-ACCESS-TOKEN") jwt: String,
        @Part ("jsonList") jsonList: RequestBody, // 여기 RequestBody를 확인
        @Part images: MultipartBody.Part?,
    ): Call<ResponseCreateProjectData>
}

만약 KEY, VALUE값이 너무나 많아서 하나로 묶고 싶으면 Part 대신 PartMap을 사용하면 된다. 또 중요한건 @Part 어노테이션이 들어간 변수의 형식은 RequestBody를 써야 한다. 서버측 api에서 jsonList가 String이라길래 String으로도 해봤는데 안된다. 그 뒤에 서버 연결하는 파일로 가서 다음과 같이 이미지 파일을 form-data 형태로 변환시켜준다. MIME 타입 참고 사이트

// mediaPath는 이미지 파일의 경로로 추후에 갤러리와 카메라로부터 사진 가져오기를 하면서 블로그에 남길 예정이다.
fileToUpload = if (mediaPath!=null){
                val file = File(mediaPath)
                // image/jpeg 타입은 MIME 타입을 따르기 위함이다. 일반적인 String같은 경우 text/plain과 같이 쓴다.
                val requestBody = file.asRequestBody("image/jpeg".toMediaTypeOrNull())
                MultipartBody.Part.createFormData("images", file.name, requestBody)
              // 우리 프로젝트에서는 이미지 파일이 없으면 null로 넘겨주기로 약속했기 때문에 이미지 경로가 없으면 null처리 해준다.
            } else{
                null
            }

이미지 파일 뿐만 아니라 jsonList의 키 값을 가진 형식도 RequestBody 형식으로 변환해주어야 한다.

val jsonString = "{프로젝트마다 들어가야 할 요소들}"
val jsonList = jsonString.toRequestBody("text/plain".toMediaTypeOrNull())

마지막으로 평상시 서버 연결할때 처럼 인자에 fileToUpload와 jsonList를 넣어주면 된다.

 val call : Call<ResponseCreateProjectData> = ServiceCreator.createProjectService
                .postCreateProject(jwt, jsonList , fileToUpload)

그래프를 이용한 알고리즘으로 최단 경로를 구하는 대표적인 알고리즘 중에 하나이다. 다익스트라가 만들어서 다익스트라 알고리즘이다. 하나의 특정 노드에 대해서 모든 노드까지의 최단 경로를 알 수 있으며 다음과 같은 특징이 있다.

• 가중치가 음수이면 안된다. -> 가중치의 합을 비교하는 알고리즘이기 때문에

• 그리디 알고리즘에 해당한다. -> 매 상황에서 비용이 가장 작은 경로와 노드를 선택하기 때문에
• 단계를 거치며 한 번 처리된 노드의 최단 거리는 변하지 않는다.

📝 간단한 구현

다익스트라 알고리즘을 간단하게 구현해보면, 총 3개의 데이터를 저장할 자료구조가 필요하다. 먼저 어떤 노드에 인접한 노드와 가중치를 저장할 graph 배열, 해당 노드의 방문 처리를 위한 visited 배열, 최단 거리를 저장할 distance 배열이다.

다익스트라 알고리즘은 다음과 같은 순서를 반복한다.

1. 시작노드(start라고 하자)에 대해서 방문처리 및 인접 노드의 최단 거리를 갱신한다.
2. 방문처리가 안된 노드 중 최단 거리가 가장 짧은 노드(now라고 하자)를 선택하고 방문처리 해준다.
3. 시작노드(start)로부터 해당 노드(now)를 거쳐 해당 노드의 인접한 노드까지의 거리와 기존의 distance에 저장되어 있는 시작노드부터 해당 노드와 인접한 노드의 거리를 비교하여 최솟값을 갱신해준다.
   예를 들어, A(start)->C가 8인데 A(start)->B(now)가 2이고 B->C(now에 인접한 노드)가 3이면 A->C보다 A->B->C가 더 가까우므로 A->B->C값을 distance에 갱신해준다.

import sys
input = sys.stdin.readline

V, E = map(int, input().split())
S = int(input())
INF = 10000000
# 인접 노드를 저장하는 배열
graph = [[] for _ in range(V+1)]
# 노드 방문 여부
visited = [False]*(V+1)
# 최단 거리 저장하는 배열
distance = [INF]*(V+1)

for _ in range(E):
    U, E, W = map(int, input().split())
    graph[U].append((E, W))

# 방문 처리가 안된 노드 중 가장 최단 거리가 짧은 노드를 찾는 함수
def get_smallest_node():
    min_value = INF
    temp_index = 0
    for i in range(V+1):
        if visited[i] == False and min_value > distance[i]:
            min_value = distance[i]
            temp_index = i
    return temp_index

# 다익스트라 알고리즘을 실행하는 함수
def dijsktra(start):
    distance[start] = 0
    visited[start] = True
    # start노드에 인접한 노드들의 최단거리 갱신
    for i in graph[start]:
        distance[i[0]] =i[1]

    # 시작 노드를 제외한 V-1개의 노드를 방문해야 하므로 V-1번 반복
    for _ in range(V-1):
        # 최단 거리가 가장 작은 노드를 now에 저장
        now = get_smallest_node()
        # 방문처리
        visited[now] = True
        # now에 인접한 노드들을 돌면서 최단 거리 갱신
        for i in graph[now]:
            if distance[i[0]] > distance[now] + i[1]:
                distance[i[0]] = distance[now] + i[1]

dijsktra(S)

for i in range(1, V+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])

💡 효율적인 구현

그런데 위의 코드는 최대 노드의 개수가 적을 때에만 OJ시스템에서 통과될 가능성이 높다. 시간복잡도가 O^2이기 때문이다. 효율적인 다익스트라 알고리즘을 짜기 위해서는 방문처리가 안된 노드 중 가장 최단 거리가 짧은 노드를 찾는 방식을 우선순위 큐를 이용하는 방식으로 바꾸면 된다.

import sys, heapq
input = sys.stdin.readline

V, E = map(int, input().split())
S = int(input())
INF = 10000000
# 인접 노드를 저장하는 배열
graph = [[] for _ in range(V+1)]
# 최단 거리 저장하는 배열
distance = [INF]*(V+1)

for _ in range(E):
    U, E, W = map(int, input().split())
    graph[U].append((E, W))

# 다익스트라 알고리즘을 실행하는 함수
def dijsktra(start):
    distance[start] = 0
    priority_q = []
    heapq.heappush(priority_q, (0, start))
    while priority_q:
        dist, now = heapq.heappop(priority_q)
        # 이미 최단거리가 확정된 상태이므로 우선순위큐에 넣을 필요가 없다.
        # 이 부분이 간단한 부분의 visited배열을 대체한다.
        if dist > distance[now]:
            continue
        for i in graph[now]:
            if dist + i[1] < distance[i[0]]:
                distance[i[0]] = dist + i[1]
                heapq.heappush(priority_q, (distance[i[0]], i[0]))

dijsktra(S)

for i in range(1, V+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])

관련 문제 및 강의

백준 1753번 이코테 2021 최단거리 알고리즘

dp 문제이다. 핵심은 dp[i][j]를 i번째 파일부터 j번째 파일을 합쳤을 때 최솟값이라고 두고 푸는 것이다. dp[1][2], dp[2][3], dp[3][4], ... dp[i][[i+1]은 연속된 두 개의 파일을 합치는 것으로 파일 i와 i+1의 크기를 단순히 합친 것과 같다.

dp[1][4]와 같은 경우 dp[1][1]+dp[2][4], dp[1][2]+dp[3][4], dp[1][3]+dp[4][4] 다음과 같은 경우의 수가 나온다. 즉, 위의 경우 중 최소값을 찾은 뒤 sum을 이용해 1번부터 4번 파일까지의 크기를 합하면 dp[1][4]값을 구할 수 있다.

📝 소스코드

import sys
input = sys.stdin.readline

def solve():
    K = int(input())
    arr = [0] + list(map(int, input().split()))

    # dp[i][j]는 i번째 파일부터 j번째 파일을 합치는 최소값
    dp = [[0]*(K+1) for _ in range(K+1)]

    # 먼저 dp[i][i+1]을 구한다. 즉, 두 파일이 연속으로 되어있을 때의 합을 구하는 경우만 dp에 저장한다.
    for i in range(1, K+1):
        for j in range(1, K+1):
            if j==i+1:
                dp[i][j] = arr[i] + arr[j]

    # dp의 맨 밑에서부터 위로 올라오면서 dp를 채워 나간다.
    # dp[1][4]는 dp[1][1]+dp[2][4], dp[1][2]+dp[3][4], dp[1][3]+dp[4][4]와 같은 경우의 수를 가진다.
    for i in range(K-1, 0, -1):
        for j in range(1, K+1):
            if dp[i][j] == 0 and j>i:
                dp[i][j] = min([dp[i][k]+dp[k+1][j] for k in range(i,j)]) + sum(arr[i:j+1])

    print(dp[1][K])

T = int(input())
for _ in range(T):
    solve()

파이썬의 라이브러리 중 순열, 조합을 가져와서 풀면 굉장히 짧고 쉽게 풀리지만 코딩 테스트에서는 해당 라이브러리를 허용하지 않을 수 있을 뿐더러 이 문제의 의도는 dfs 재귀를 활용한 브루트 포스이므로 dfs를 이용해 풀었다.

일단 뽑은 번호를 저장하고 추후에 결과로 출력할 배열인 dp를 만들었다. 어차피 번호는 6개니까 dp의 크기도 6으로 했다.

이후 dfs를 구현했는데, 인자를 start와 depth로 주었다. depth는 현재 몇 번째 수를 뽑는 것인지 나타내는 것이다. start는 뽑는 수에 경우의 수가 생기기 시작하는 바로 앞 지점이다. 이게 이해하는데에 오래걸렸는데, 예를 들어 1,2,3,4,5,6,7 중 6개를 사전순으로 뽑을 때 1,2,3,4,5까지 뽑고 6을 뽑을지 7을 뽑을지 선택할 수 있다. 이 때 start의 값이 5가 된다. 그래서 dfs(0,0)을 시작으로 재귀를 쭉 들어가보면 dfs(5,5)가 나오게 되고 for i in range(5,7)에 의해 arr[5]의 값이 마지막 depth에 들어가는 경우와 arr[6]의 값이 마지막 depth에 들어가는 경우가 나온다. 즉 1,2,3,4,5,6과 1,2,3,4,5,7의 경우이다.

📝소스코드

import sys
input = sys.stdin.readline

def dfs(start, depth):
    # 길이가 6이면 숫자를 다 뽑은 것이므로 출력하고 return
    if depth == 6:
        print(*dp)
        return
    # 갈림길 start에서 경우의 수를 dfs 재귀를 통해 구현
    for i in range(start, len(arr)):
        dp[depth] = arr[i]
        dfs(i+1, depth+1)

while True:
    dp = [0]*6
    arr = list(map(int, input().split()))
    K = arr[0]
    if K == 0:
        break
    arr = arr[1:]
    dfs(0, 0)
    print()