CS & 알고리즘 스터디: 네 번째 스터디

게시 2024/07/12

By Jaehee Nam 29 분읽는 시간

네 번째 스터디

저번 주의 스터디 분량과 내용이 꽤 맘에 들었다. 이렇게 면접 방식으로 내용을 안 보고 대답을 하니 내가 실제로 이해한 것과 단순히 옮겨 적은 게 무엇인지 구분이 되어 복습 측면에서도 도움이 되었다.

이번 주는 지난 주에 이어서 운영체제 부분을 더 다루기로 했다. 이제 스터디에 차차 익숙해지고 있어서 주제 및 질문들, 그리고 풀 문제들만 지정하여 각자 열심히 하면 되는 단계인 것 같다. 문제의 난이도는 지난 주에 비해 꽤 많이 올라서 시간을 예상보다 많이 잡아먹었으며, 끝내지 못했다… 못 푼 문제들은 추후 다시 도전해볼 예정이다.

키워드

스케줄링 알고리즘

Q: 스케줄링 알고리즘에는 어떤 것들이 있나요?
A:

가장 간단하게 구현할 수 있는 프로세스 스케줄링 알고리즘은 FCFS(First Come First Serve) 스케줄링으로, 단순히 준비 큐에 도착한 순서에 따라 자원을 할당받는 방법이다. 먼저 디스패치된 프로세스가 CPU를 차지하면 해당 프로세스의 수행이 완료된 후에 다음 프로세스가 CPU를 차지하고 수행하면 된다.

이 밖의 스케줄링 알고리즘으로는 가장 짧은 실행 시간을 가질 것으로 예상되는 프로세스부터 처리하는 SJF(Shortest Job First) 스케줄링, 남은 실행시간이 가장 짧다고 예상되는 프로세스를 먼저 디스패치하는 SRT(Shortest Remaining Time) 스케줄링, 정해진 시간 할당량에 의해 실행을 제한하는 선점 방식의 RR(Round Robin) 스케줄링, 우선순위를 프로세스에 부여하여 우선도에 따라 처리하는 우선순위 스케줄링 등등이 있다.

Q: RR을 사용할 때, Time Slice에 따른 trade-off를 설명해 주세요.
A:

Round Robin 스케줄링은 각 프로세스에 동일한 CPU 할당 시간(Time Slice)를 주는 방식이다.

짧은 Time Slice의 경우 각 프로세스는 CPU를 상대적으로 빠른 시간 이내에 점유할 수 있음으로 응답 시간을 개선할 수 있다. 다만, 잦은 컨텍스트 스위칭으로 인해 오버헤드가 필연적으로 증가한다.

긴 Time Slice는 반대로 응답 시간은 상대적으로 늘어나지만 컨텍스트 스위칭 오버헤드는 감소한다.

Q: 싱글 스레드 CPU 에서 상시로 돌아가야 하는 프로세스가 있다면, 어떤 스케쥴링 알고리즘을 사용하는 것이 좋을까요? 또 왜 그럴까요?
A:

싱글 스레드 CPU에서 상시로 돌아가야 하는 프로세스가 있다면 FCFS 또는 Priority Scheduling을 사용할 것이 좋다.

FCFS
도착한 순서대로 프로세스를 실행시키기 때문에 상시로 돌아가야 하는 프로세스를 가장 먼저 도착하도록 한다면 이는 자원을 가장 먼저 할당받아 계속 실행될 것이다. FCFS는 특히 비선점형 스케줄링 알고리즘이기 떄문에 프로세스가 CPU를 점유하는 중에는 다른 프로세스에게 CPU를 빼앗기지 않는다.

Priority Scheduling
상시로 돌아가야 하는 프로세스에 가장 높은 우선도를 부여한다면 알고리즘이 선점형으로 설계가 되어도 프로세스는 자원을 빼앗기지 않는다.

Q: 타 스케쥴러와 비교하여, Multi-level Feedback Queue는 어떤 문제점들을 해결한다고 볼 수 있을까요?
A:

MLFQ는 타 스케줄러 타 스케줄러 대비 다음의 개선점들이 있다:

스루풋 향상: 다양한 우선순위 레벨을 가진 큐를 활용하여 여러 종류의 작업에 대응할 수 있다.
응답 시간 개선 & 기아 상태 방지: 우선순위가 낮은 작업들도 시간이 지남에 따라 더 높은 우선순위 큐로 이동할 수 있으며 이는 응답 시간을 개선하며, 우선순위를 높여줌으로 무한정 기다려야 하는 기아 프로세스의 발생을 방지한다.

Q: 유저 스레드와 커널 스레드의 스케쥴링 알고리즘은 똑같을까요?
A:

유저 스레드와 커널 스레드의 스케줄링 알고리즘은 서로 다르다. 주요 차이점들은 다음과 같다:

스케줄링 주체: 유저 스레드는 사용자 수준의 스레드 라이브러리 또는 패키지에 의해 스케줄링되지만, 커널 스레드는 운영체제의 커널에 의해 스케줄링된다.
알고리즘: 유저 스레드는 개발자가 선택한 스레드 라이브러리에 따라 다양한 스케줄링 기법을 사용할 수 있으나 커널 스레드의 스케줄링은 운영체제의 커널이 사용하는 스케줄링 알고리즘을 따른다.
컨텍스트 스위칭: 빠른 컨텍스트 스위칭이 가능한 유저 스레드들 대비 커널 스레드는 컨텍스트 스위칭 시 오버헤드가 많이 발생하기 때문에 이를 고려하여 스케줄링 알고리즘을 설계해야 한다.

뮤텍스와 세마포어

뮤텍스와 세마포어 포스트

Q: 뮤텍스와 세마포어의 차이는 무엇인가요?
A:

뮤텍스와 세마포어 모두 다중 스레드 환경에서 동기화 문제를 해결하기 위해 사용되는 기법이다.

뮤텍스는 ‘상호 배제’를 뜻하는 Mutual Exclusion의 약자로, 임계 영역에 대한 접근을 Lock을 사용하여 제어하는 메커니즘이다. 이를 통해 특정 자원에 대해 단일 스레드만 접근이 가능하도록 보장한다. 뮤텍스의 Lock은 소유권이 존재하며, 보유자 스레드만이 이를 해제할 수 있다.

세마포어는 주어진 자원에 접근할 수 있는 스레드의 수를 제한하는 동기화 메커니즘이다. 카운터로 접근 가능한 스레드의 수를 제어하며, 카운터가 허용하는 한 다수의 스레드가 동시에 자원에 접근할 수 있다.

Q: lock을 얻기 위해 대기하는 프로세스들은 Spin Lock 기법을 사용할 수 있습니다. 이 방법의 장단점은 무엇인가요? 단점을 해결할 방법은 없을까요?
A:

Spin Lock 기법이란 프로세스가 Lock을 얻기 위해 반복적으로 Mutex의 상태를 확인하며 대기하는 Busy-Waiting 기반 기법이다.

장점:

빠르고 간단하게 구현할 수 있음
Lock을 얻기 위해 기다리는 동안 컨텍스트 스위칭이 발생하지 않으므로 오버헤드가 적음
Lock이 빠른 시간 이내에 해제될 것이라고 예상되는 경우에 효율적

단점:

CPU 자원 낭비
우선순위가 낮은 프로세스가 Lock을 얻지 못하고 계속 대기하는 기아상태 발생 가능

단점을 해결할 방법으로는 다음이 있다:

자원 낭비 최소화: 임계 구역의 실행 시간이 매우 짧은 경우에만 적용
어댑티브 Spin Lock: 일정 시간동안 Spin Lock을 시도하고, 얻지 못하는 경우에는 대기 상태로 전환
Backoff 알고리즘: Spin Lock 시도 실패 시 점진적으로 대기 시간 늘리기
기아 방지: 우선순위를 조정하여 낮은 우선순위의 프로세스에게 락을 부여

Q: 뮤텍스와 세마포어 모두 커널이 관리하기 때문에, Lock을 얻고 방출하는 과정에서 시스템 콜을 호출해야 합니다. 이 방법의 장단점이 있을까요? 단점을 해결할 수 있는 방법은 없을까요?
A:

해당 방법의 장점으로는, 우선 커널이 관리하기 때문에 데이터의 보호와 동기화가 확실하게 보장된다. 즉, 안정성 및 일관성이 보장되며 커널의 관리로 인해 동기화 메커니즘이 효율적으로 처리된다. 두번째로, 커널 공간에서 관리된다는 것은 서로 다른 프로세스 간에도 동기화가 가능하다는 것을 의미하며, 다중 프로세스 환경에서 유리하다.

단점으로는, 시스템 콜의 호출은 사용자 모드에서 커널 모드로의 전환이 필요하기 때문에 오버헤드가 높으며 성능 저하를 초래할 수 있다.

사용자 모드 Lock을 사용함으로 짧은 임계 구역에서는 사용자 모드에서 Spin Lock을 사용하면 커널 모드로의 전환을 피할 수 있으며 빠른 락 획득이 가능해진다.

Deadlock

Deadlock 포스트

Q: 데드락이 발동하는 4가지 조건에 대해 설명해주세요.
A:

데드락이란 두 개 이상의 프로세스가 서로의 자원을 기다리면서 무한하게 대기하는 상황을 말한다.
데드락이 발동하기 위한 필요조건으로는 다음 네가지가 있다:

상호배제
- 자원은 한 번의 하나의 프로세스만 사용할 수 있음
- 다른 프로세스가 점유하고 있는 자원이 필요한 경우에 반드시 대기
- 자원의 일관성을 유지해야 하는 경우에 상호배제는 필요하지만, 데드락을 유발할 수 있음
- 예: 프로세스 A가 프린터를 사용 중인 경우, 프로세스 B는 프린터를 사용할 수 없으며 대기해야 함
점유대기
- 프로세스가 최소 하나의 자원을 점유하고 있으며, 다른 자원을 추가로 요청하여 대기 중
- 지원을 점유한 프로세스가 다른 자원을 기다리면서 데드락 발생 가능
- 예: 프로세스 A가 자원1을 점유한 상태에서 자원 2를 요청하고, 프로세스 B는 자원2를 점유한 상태에서 자원1을 요청
비선점
- 프로세스가 강제로 자원을 빼앗기지 않으며, 자원을 점유한 프로세스가 스스로 해제해야 함
- 자원을 요청한 프로세스는 이미 점유된 다른 자원을 강제로 빼앗을 수 없음
환형대기(순환대기)
- 자원들 사이에 프로세스들이 순환 형태로 대기
- 자원을 점유하고 있는 프로세스들이 서로의 자원을 기다리면서 무한하게 대기할 수 있음

Q: 이 중 하나가 빠진다고 가정하면 왜 Deadlock이 발생하지 않을까요?
A:

상호 배제 조건이 빠진 경우:
- 여러 프로세스가 동시에 같은 자원을 사용할 수 있기 때문에 자원을 두고 경쟁할 필요 자체가 없어지며, 자원 대기 상태가 생기지 않는다.
점유 대기 조건이 빠진 경우:
- 프로세스가 자원을 점유하며 대기하는 것이 방지되면 필요한 모든 자원을 처음부터 할당받거나, 자원을 해제하고 다시 요청해야 한다. 즉, 자원을 붙잡고 기다리는 상황이 없어진다.
비선점 조건이 빠진 경우:
- 자원을 점유하고 있는 프로세스가 다른 프로세스에 의해 강제로 자원을 빼앗길 수 있다면 특정 프로세스가 점유한 필요 자원을 가져올 수 있기 때문에 대기 상태에 빠지지 않는다.
순환 대기 조건이 빠진 경우:
- 위상 정렬과 같이 자원 요청이 선형적으로 이루어지게 되는데, 이러면 순차적으로 모든 자원이 해제가 되며 데드락이 발생하지 않는다.

Q: Deadlock 예방은 어떻게 하나요?
A:

데드락의 발생 조건 네가지 중 하나라도 발생하지 않도록 설계하고 관리하면 데드락을 예방할 수 있다.

상호 배제 방지:
- 가능한 경우 자원을 공유 가능하도록 설계한다.
- 단, 읽기 전용 데이터 같은 경우에는 위의 설계가 가능하지만, 프린터와 같은 자원의 경우 상호 배제를 피할 수 없기 떄문에 다른 조건을 통해 예방해야 한다.
점유 대기 방지:
- 프로세스가 자원을 요청할 때 다른 자원을 점유하지 않은 상태에서만 요청하도록 설계한다.
- 자원을 모두 해제한 후 다시 요청하는 방식으로 구현 가능하다.
- 프로세스가 시작하기 전에 필요한 모든 자원을 한꺼번에 요청하고 할당받도록 설계한다.
- 필요한 모든 자원을 할당받지 못하는 경우 실행하지 않는다.
비선점 방지:
- 이미 할당된 자원을 강제로 회수할 수 있는 방식을 도입한다.
- CPU 스케줄링에서 선점형 스케줄링 기법을 사용하면 된다.
순환 대기 방지:
- 자원 할당 순서 규칙을 만들어 자원에 고유한 순서를 부여하고, 프로세스가 자원을 요청할 때 해당 순서대로 요청하게 한다.
- 자원 A와 B가 있을 때 프로세스는 A를 요청한 후 B를 요청해야 하며, 반대로 요청할 수 없다.

Q: Wait Free와 Lock Free를 비교해 주세요.
A:

Wait-Free란 모든 스레드가 유한한 시간 내에 작업을 완료할 수 있도록 보장하는 알고리즘이다. 스레드는 무한하게 대기하지 않으며, 특정 스레드가 블록되지 않도록 설계되어있다. 이는 스레드가 정해진 시간 내에 작업이 완료될 수 있게 만듦으로 실시간 성능을 보장하지만 설계가 복잡하고 오버헤드가 상대적으로 커 고비용이다.

Lock-Free란 시스템 전체적으로는 진행할수 있도록 보장하지만 개별 스레드는 무한히 기다릴 수도 있는 알고리즘이다. 즉, 하나의 스레드는 특정 시간 내에 작업을 완료할 수 있다. 이는 Wait-Free보다 상대적으로 단순하게 구현이 가능하며, 비용면에서 효율적이다.

특성	Wait-Free	Lock-Free
정의	모든 스레드가 유한 시간 내 작업 완료 보장	시스템 전체는 진행 보장, 개별 스레드는 지연 가능
실시간 성능	실시간 성능 보장	실시간 성능 보장 어려움
복잡성	높은 복잡성, 구현 어려움	상대적으로 단순
성능 오버헤드	상대적으로 높음	상대적으로 낮음
진행 보장	모든 스레드의 진행 보장	시스템 전체의 진행 보장, 개별 스레드는 보장 X

프로그램 컴파일

Q: 링커와 로더의 차이에 대해 설명해주세요.
A:

링커는 여러 개의 오브젝트 파일 및 라이브러리 파일을 결합하여 하나의 실행 파일로 만드는 역할을 한다.

각 오브젝트 파일의 심볼(함수, 변수 등)을 결합하여 참조를 해결한다.
서로 다른 오브젝트 파일에 정의된 심볼을 연결한다.
각 오브젝트 파일의 코드와 데이터를 실행 파일 내의 특정 주소에 배치한다.
상대 주소를 절대 주소로 변환한다.
라이브러리 파일을 포함시켜 프로그램을 완전한 상태로 만든다.
정적 및 동적 라이브러리를 처리한다.

로더는 실행 파일을 메모리에 적재하고 실행을 준비시키는 역할을 한다.

실행 파일을 메모리에 적재한다.
필요한 메모리 공간을 할당하고, 파일의 코드 및 데이터를 메모리에 로드한다.
동적 라이브러리를 사용하는 경우, 실행 시점에 이를 메모리에 적재 및 연결한다.
초기화 작업을 수행하고 프로그램의 진입점으로 제어를 넘긴다.

특성	링커(Linker)	로더(Loader)
역할	오브젝트 파일과 라이브러리를 결합하여 실행 파일 생성	실행 파일을 메모리에 적재하고 실행 준비
주요 기능	심볼 결합, 주소 지정, 라이브러리 연결	메모리 적재, 동적 링크, 프로그램 시작 준비
출력	실행 파일	메모리에 적재된 실행 가능한 프로그램

Q: 컴파일 언어와 인터프리터 언어의 차이에 대해 설명해주세요.
A:

Q: 본인이 사용하는 언어는 어떤 식으로 컴파일 및 실행되는지 설명해주세요
A:

자바스크립트를 사용하는데, 자바스크립트는 본래 인터프리터식으로 한 줄씩 읽는 방식이었다. 자바스크립트가 발전함에 따라 컴파일러 방식도 같이 사용하는 하이브리드 형태로 바뀌게 되었다.

문제 풀이

줄 세우기

  
import sys 
input = sys.stdin.readline

N = int(input())
kids = []
dp = []

for _ in range(N):
    kids.append(int(input()))

def lis(arr):
    n = len(arr)
    dp = [1] * n 

    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j]+1)
    
    return max(dp)

print(N - lis(kids))

완전 이진 트리

  
import sys
input = sys.stdin.readline

K = int(input())
inorder = list(map(int, input().split()))

# 레벨에 해당하는 배열 생성
levels = [[] for _ in range(K)]
 
def make_level(arr, current_level, levels):
    if not arr:
        return

    mid = len(arr)//2 

    levels[current_level].append(arr[mid])

    make_level(arr[:mid], current_level + 1, levels)
    make_level(arr[mid+1:], current_level + 1, levels)

make_level(inorder, 0, levels)

for level in levels:
    print(*level, sep= " ")

로봇 청소기

  
class Vacuum:
    def __init__(self, r, c, d):
        self.r = r  # 청소기의 시작 행 위치
        self.c = c  # 청소기의 시작 열 위치
        self.d = d  # 청소기의 시작 방향

        # 방향 설정: 북, 동, 남, 서 순서
        self.directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]

    def turn_left(self):
        # 현재 방향에서 왼쪽으로 90도 회전
        self.d = (self.d - 1) % 4

    def move_forward(self):
        # 현재 방향으로 한 칸 이동
        self.r += self.directions[self.d][0]
        self.c += self.directions[self.d][1]

# 방향 전환과 움직임을 테스트하기 위한 함수
def clean(room_map, r, c, d):
    N = len(room_map)
    M = len(room_map[0])

    vacuum = Vacuum(r, c, d)

    cleaned_count = 0

    while True:
        # 현재 위치 청소
        if room_map[vacuum.r][vacuum.c] == 0:
            room_map[vacuum.r][vacuum.c] = 2
            cleaned_count += 1

        # 네 방향 탐색하며 청소할 위치 찾기
        cleaned = False
        for _ in range(4):
            vacuum.turn_left()
            nr = vacuum.r + vacuum.directions[vacuum.d][0]
            nc = vacuum.c + vacuum.directions[vacuum.d][1]

            if room_map[nr][nc] == 0:
                vacuum.move_forward()
                cleaned = True
                break

        # 네 방향 모두 청소할 공간이 없는 경우 후진 또는 종료
        if not cleaned:
            back_d = (vacuum.d + 2) % 4
            nr = vacuum.r + vacuum.directions[back_d][0]
            nc = vacuum.c + vacuum.directions[back_d][1]

            if room_map[nr][nc] != 1:
                vacuum.r, vacuum.c = nr, nc
            else:
                break

    return cleaned_count

# 입력 받기
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
r, c, d = map(int, input().split())
room_map = [list(map(int, input().split())) for _ in range(N)]

# 청소 시작
result = clean(room_map, r, c, d)
print(result)

devlog, study