def find(parent, x): # 특정 원소가 속한 집합 찾기
if parent[x] != x: # 루트 노드가 아니면, 루트 노드 찾을 때까지 재귀
return find(parent, parent[x])
return parent[x]
def union(parent, a, b): # 두 원소가 속한 집합 합치기
a = find(parent, a)
b = find(parent, b)
if a < b: # 더 작은 번호가 부모 노드
parent[b] = a
else:
parent[a] = b
n = int(input()) # 컴퓨터 개수
edges = []
result = 0
parent = [i for i in range(n + 1)] # 부모 테이블 초기화
for i in range(n):
s = input()
for j in range(len(s)):
cost = 0 # 0이면 그대로
ch = s[j]
if ch.islower(): # 소문자
cost = ord(ch) - ord('a') + 1
elif ch.isupper():
cost = ord(ch) - ord('A') + 27
edges.append((cost, i + 1, j + 1))
result += cost # 모든 비용 계산
edges.sort() # cost 오름차순 정렬
for cost, a, b in edges:
if cost == 0:
continue
if find(parent, a) != find(parent, b): # 사이클 발생 하지 않는 경우에 MST 포함
union(parent, a, b)
# print(cost)
result -= cost
flag = True
for i in range(1, n + 1):
if find(parent, i) != 1:
flag = False
if flag:
print(result)
else:
print(-1)
def find(parent, x):
if parent[x] != x:
return find(parent, parent[x])
return parent[x]
def union(parent, a, b):
a = find(parent, a)
b = find(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
n, m, k = map(int, input().split()) # 도시 개수, 케이블 수, 발전소 개수
numbers = list(map(int, input().split())) # 발전소 설치된 도시 번호
parent = [i for i in range(n + 1)]
edges = []
answer = 0
for num in numbers: # 발전소 설치된 도시의 루트를 0 으로 초기화
parent[num] = 0
for _ in range(m):
u, v, w = map(int, input().split()) # u 도시와 v 도시 연결 비용 w
edges.append((w, u, v))
edges.sort()
for cost, a, b in edges:
if find(parent, a) != find(parent, b): # 사이클이 아닌 경우에만 계산
union(parent, a, b)
answer += cost
print(answer)
- 프로세스는 메모리에 올라가는 프로그램으로 운영체제로부터 메모리, 주소 공간 등을 할당 받는다.
- 멀티 프로세스 환경에서는 메모리에 올라간 다양한 프로세스들이 CPU를 선점하며 진행된다.
- CPU 선점과정을 통해 PCB에 각각의 프로세스들이 실행되었던 정보들은 문맥 교환을 통해 저장된다.
- 스레드는 각 프로세스에서 실행 단위를 뜻한다. 하나의 프로세스에 여러 개의 스레드가 동작하는 것을 멀티 스레드라고 한다.
- 각각 스레드는 한 프로세스에서 힙 영역과 데이터 영역을 공유하고, 각 스레드마다 스택과 PC레지스터 값이 따로 존재한다.
- 멀티 스레드는 생성과 관리의 중복을 최소화하고, 멀티 프로세스에 비해 문맥 교환 비용이 낮다.
멀티 프로세스 vs 멀티 스레드
멀티 프로세스의 프로세스는 자원을 서로 공유하지 않는다.
프로세스 간 통신(IPC)으로, 프로세스 간에도 자원을 주고받을 수 있다.
멀티 스레드에서는 하나의 프로세스 자원을 스레드가 서로 공유한다.
멀티 스레드
- 장점 : 여러 프로세스를 동시에 처리하던 일을 자원과 메모리 공유로 자원 소모에 대한 비용 절감
- 또한 프로세스의 문맥 교환과 다르게 캐시 메모리를 비울 필요가 없어 속도가 빠르다.
- 단점 : 여러 자원을 공유하기 때문에, 동기화 문제를 해결하기 위한 작업 필요
-> 멀티 프로세스도 다른 프로세스가 점유하고 있는 자원에 대해 접근할 때 동기화 문제가 발생할 수 있다.
- 문재 해결 : 임계 영역으로 동시 접근 방지 -> 세마포어, 뮤텍스
CPU 스케줄링
운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 분배하는 것
프로세스 우선순위(priority) 에 따라 프로세스 실행 순서가 정해진다.
스케줄링 큐
선점(preemptive) 스케줄링
프로세스가 CPU를 할당받아 실행 중이어도, 운영체제가 CPU의 사용권을 선점 가능
처리 시간 예측이 어렵다.
잦은 문맥 교환으로 오버헤드 발생 가능성이 있다.
CPU 사용 독점 문제를 막을 수 있다.
Interrupt, I/O or Event Completion, I/O or Event Wait, Exit
비선점(non-preemptive) 스케줄링
프로세스가 CPU를 점유하고 있으면, 사용을 뺐을 수 없는 방식
필요한 문맥 교환만 일어나기 때문에 오버헤드가 상대적으로 적다.
처리 시간 예측이 쉽다.
I/O or Event wait, Exit
프로세스 상태 다이어그램
승인(Admitted) : 프로세스 생성이 가능하여 승인된 상태
스케줄러 디스패치(Scheduler dispatch) : 준비 상태에 있는 프로세스 중 하나를 선택하여 실행
인터럽트(Interrupt) : 예외, 입출력, 이벤트 등이 발생해서 현재 실행 중인 프로세스를 준비 상태로 바꾸고, 해당 작업을 먼저 처리
입출력 또는 이벤트 대기(I/O or event wait) : 실행 중인 프로세스가 입출력이나 이벤트를 처리해야 하는 경우, 입출력/이벤트가 모두 끝날 때 까지 대기 상태로 만드는 것
입출력 또는 이벤트 완료(I/O or event completion) : 입출력/이벤트가 끝난 프로세스를 준비 상태로 전환하여 스케줄러에 의해 선택될 수 있도록 만드는 것
CPU 스케줄링 종류
비선점 스케줄링
FCFS(First Come First Served) 선입 선처리 스케줄링
준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링
먼저 CPU를 요청한 프로세스부터 CPU 할당
실행 시간이 짧은 것이 뒤로 가면 평균 대기 시간이 길어진다.
SJF(Shortest Job First) 최단 작업 우선 스케줄링
수행 시간이 가장 짧다고 판단되는 작업을 먼저 수행
FCFS 보다 평균 대기 시간 감소, 짧은 작업에 유리하다.
선점 스케줄링
RR(Round Roubin) 라운드 로빈
FCFS + 타임 슬라이스(time slice) or Time Quantum
타임 슬라이스 : 실행의 최소 단위 시간, 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
정해진 시간을 모두 사용해도, 프로세스가 완료되지 않으면 큐의 맨 뒤에 삽입(문맥 교환)
Time Quantum이 크면 FCFS와 같고, 작으면 문맥 교환이 잦아져서 오버헤드 발생
SRT(Shortest Remaining Time) 최소 잔여 시간 우선 스케줄링
SJF + RR
정해진 시간만큼 CPU를 사용하고, 다음으로 CPU를 사용할 프로세스를 남은 작업 시간이 가장 적은 프로세스를 선택한다.
Priority Scheduling(우선순위 스케줄링)
프로세스들에 우선순위를 부여하고, 우선순위 높은 프로세스부터 실행
우선순위가 같은 프로세스들은 FCFS 스케줄링
단점 : 우선 순위가 낮은 프로세스를 무한정 기다리는 기아(starvation) 현상
Aging 방법으로 기아 현상 해결이 가능하다.
Aging : 오랫동안 대시한 프로세스의 우선순위를 점차 높이는 방식
Multilevel-Queue(다단계 큐)
우선순위 스케줄링이 발전된 형태
우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식
우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리하고, 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스를 처리한다.
우선순위가 높은 큐는 작은 Time Quantum, 우선순위가 낮은 큐는 큰 Time Quantum
Multilevel feedback queue(다단계 피드백 큐 스케줄링)
큐 간의 이동이 가능한 다단계 큐 스케줄링
자연스럽게 CPU 집중 프로세스의 우선순위는 상대적으로 낮아지고, 입출력 집중 프로세스의 우선순위는 높아진다.
동기화
프로세스들의 수행 시기를 맞추는 것
실행 순서 제어 : 프로세스를 올바른 순서대로 실행, reader writer problem
reader와 writer 프로세스는 아무렇게나 실행 되면 X
상호 배제 : 동시 접근이 안되는 자원에 하나의 프로세스만 접근하게 하기, bank account problem
한 번에 하나의 프로세스만 접근해야 하는 자원에 동시 접근을 피하기 위한 동기화
ex. 계좌에 입금할 때 현재 잔액 + 추가 금액
공유 자원 : 여러 프로세스 혹은 스레드가 공유하는 자원
ex. 전역 변수, 파일, 입출력장치, 보조기억 장치 등등
임계 구역 : 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역
ex. 총합 변수, 잔액 변수
레이스 컨디션(race condition) : 임계 구역에 동시에 접근하면 자원의 일관성이 꺠지는 것
Race Condition
공유 자원에 대해 여러 프로세스가 동시에 접근할 때, 결과값에 영향을 줄 수 있는 상태
동기화 기법
뮤텍스 락, 세마포어, 모니터
뮤텍스 락
상호 배제를 위한 동기화 도구, key를 기반으로 상호 배제
전역 변수 1개, 함수 2개로 구현
자물쇠 역할 : 프로세스들이 공유하는 전역 변수 lock
임계 구역을 잠그는 역할 : acquire 함수
임계 구역의 잠금을 해제하는 역할 : release 함수
busy waiting(바쁜 대기) 적용 : 임계 구역이 잠겨 있는지 확인하는 작업을 무한으로 작동
세마포어
일반화된 방식의 동기화 도구
공유 자원이 여러 개 있는 경우에도 적용 가능
멀티프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법
전역 변수 1개, 함수 2개로 구현
전역 변수 S : 임계 구역에 진입할 수 있는 프로세스 개수를 나타내는 변수
wait 함수 : 임계구역에 들어가도 되는지, 기다려야 하는지 알려주는 함수
signal 함수 : 임계 구역 앞에서 기다리는 프로세스에 가도 된다는 신호를 주는 함수
busy waiting(바쁜 대기) 적용 : CPU 사이클 낭비의 단점
계속 반복되는 연산으로 CPU 낭비
해결 방법
사용할 수 있는 자원이 없을 경우 대기 상태로 만든다. -> 해당 프로세스의 PCB를 대기 큐에 삽입
사용할 수 있는 자원이 생겼을 경우 대기 큐의 프로세스를 준비 상태로 만든다. -> 해당 프로세스의 PCB를 대기 큐에서 꺼내 준비 큐에 삽입
wait() {
while (S <= 0) // 임계 구역에 진입할 수 있는 프로세스 개수가 0 이하면
; // 사용 가능한 자원이 있는지 확인하고
S--; // 임계 구역에 진입할 수 있는 프로세스 개수가 1개 이상이면 S 감소하고 임계 구역 진입
}
signal() {
S++; // 임계 구역에서의 작업을 마치고 S 증가
}
교착 상태(Dead lock)
두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태
무한히 다음 자원을 기다리는 상태
교착 상태 조건
상호 배제 : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
점유와 대기 : 자원을 할당 받은 상태에서 다른 자원을 할당 받기를 기다리는 상태
비선점 : 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
원형 대기 : 프로세스들이 원의 형태로 자원을 대기하는 상태
교착 상태 해결 방법
예방(prevention) : 교착 상태가 발생하지 않도록 발생 조건 중 하나를 없애기
회피(avoidance) : 예방보다 덜 엄격한 제약 조건으로 자원을 좀 더 효율적으로 사용할 수 있도록 해결
은행원 알고리즘 : 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태인지 사전에 검사하여 교착 상태 회피
회복 : 교착 상태 발생을 인정하고 사후에 조치하는 방식
선점을 통한 회복, 프로세스 강제 종료를 통한 회복
무시 : 교착 상태를 해결할 때, 문맥 교환에 의한 오버헤드로 성능저하가 일어날 수 있어서 무시하는 방법
메모리 단편화
- 단편화(fragmentation) : 프로세스들이 메모리에 적재되고 해제되는 것이 반복되면, 프로세스들 사이에 사용 못하는 공간이 생긴다.
- 외부 단편화 : 메모리 공간 중 사용하지 못하게 되는 일부 물리 메모리 사이에 남는 공간들을 합쳤을 때 다른 프로세스를 할당할 수 있는 문제
- 내부 단편화 : 프로세스가 사용하는 메모리 공간 내에 사용하지 않는 부분
페이징
- 페이징 기법으로 논리 메모리는 물리 메모리에 저장될 때 연속되어 저장될 필요 없이 물리 메모리의 남는 프레임에 적절히 배치
- 페이지와 프레임을 대응하는 페이징 테이블 필요(paging table)
- 장점 : 외부 단편화를 해결
- 단점 : 내부 단편화 비중이 늘어난다.
세그멘테이션
- 페이징처럼 논리, 물리 메모리를 같은 크기의 블록이 아닌 서로 다른 크기의 논리적 단위인 세그먼트로 분할해서 할당
- 각 세그먼트는 연속적인 공간에 저장된다.
- mapping을 위한 segment table 필요
- 필요한 메모리 공간만큼 메모리를 할당하기 때문에 내부 단편화 문제는 없지만, 중간에 메모리를 해제하면 외부 단편화 발생
# 패턴 만들기
import re
p = re.compile('[a-z]+')
# match 매치 확인
m = p.match('3 python')
print(m) # None : 3이 [a-z]+ 에 매치 되지 않는다
# search
m = p.match('3 python')
print(m) # <re.Match object; span=(2, 8), match='python'>
# search는 문자열을 전체를 검색하기 때문에 매치된다.
findall
result = p.findall("life is too short")
print(result)
# ['life', 'is', 'too', 'short']
# [a-z]+ 와 매치되는 모든 값을 리스트로 리턴
finditer
result = p.finditer("life is too short")
print(result)
<callable_iterator object at 0x01F5E390>
for r in result: print(r)
...
<re.Match object; span=(0, 4), match='life'>
<re.Match object; span=(5, 7), match='is'>
<re.Match object; span=(8, 11), match='too'>
<re.Match object; span=(12, 17), match='short'>
