모두가 쉘 스크립트와 친해졌으면 하는 바람으로 작성해봅니다.
위상정렬이란?
위상정렬은 이해하기 쉽게 말하자면 작업의 의존성 그래프를 받아서 해야 할 작업의 순서대로 정렬하는 것입니다.
예를 들어서, A 작업을 위해 B 작업을 해야 된다면, B 작업을 먼저 한 다음에 A 작업을 해야겠죠.
거기에 A 작업을 위해 C 작업도 해야 되는데 B 작업이나 C 작업을 위해 D 작업을 해야 한다면?
이 때의 작업 순서는 D - B - C - A 또는 D - C - B - A로 두 가지 모두 가능한데요,
이 둘이 모두 위상 정렬이 된 상태입니다.
순환 의존성
A 작업을 위해 B 작업을 해야 하는데, B 작업을 위해서는 A 작업이 필요하다면 어떨까요?
A도 못 하고 B도 못 하게 될 것입니다. 이를 순환 의존성이라고 합니다.
이 글에서는 위상정렬을 깊게 다룰 것이 아니니 순환 의존성을 따로 처리하지는 않겠습니다.
엄청 쉬운 위상정렬 구현 방법
위상정렬을 구현하는 아마도 가장 쉬운 방법은 이렇습니다.
flowchart TD
start(시작!) --> remainTaskExistsEvery{"(모든 작업) 처리할 작업이 남았는가"} --> CallAddThisTask1[이 작업을 추가] --> remainTaskExistsEvery --> End(끝!)
AddThisTask(이 작업을 추가) --> remainTaskExistsDependency{"(의존성 중) 처리할 작업이 남았는가"} --> CallAddThisTask2[이 작업을 추가] --> remainTaskExistsDependency --> SubEnd("이 작업을 먼저 해야 합니다!")Mermaid
복사
여기서 이 작업을 추가는 재귀적으로 호출됩니다.
예시를 들어서 설명하자면…
A ← B일 때 A 작업을 위해 B 작업이 필요하다고 할 때
•
A ← B
•
A ← C
•
B ← D
•
C ← D
•
E
이런 경우로 예를 들어서 설명하겠습니다.
•
전체 중 남은 작업 A, B, C, D가 있네? 아무거나… A를 처리하자!
◦
A를 처리하는 중… A의 의존성 중 남은 작업 B, C가 있네? 아무거나… B를 처리하자!
▪
B를 처리하는 중… B의 의존성 중 남은 작업 D가 있네? 아무거나… D를 처리하자!
•
D를 처리하는 중… D는 의존성이 없네? 그러면 D 작업을 먼저 하면 됩니다.
▪
B를 처리하는 중… B의 의존성 중 남은 작업이 없네? 그러면 다음으로 B 작업!
◦
A를 처리하는 중… A의 의존성 중 남은 작업 C가 있네? 아무거나… C를 처리하자!
▪
C를 처리하는 중… B의 의존성 중 남은 작업이 없네? 그러면 다음으로 C 작업!
◦
A를 처리하는 중… A의 의존성 중 남은 작업이 없네? 그러면 다음으로 A 작업!
•
전체 중 남은 작업 E가 있네? 아무거나… E를 처리하자!
◦
E를 처리하는 중… E는 의존성이 없네? 그러면 다음으로 E 작업!
•
전체 중 남은 작업이… 없구나! 위상정렬 완료!
이런 과정을 거쳐 D - B - C - A - E 순서로 정렬됩니다.
실제 구현 및 코드 설명
전체 코드는 GitHub에서도 확인할 수 있지만…
사실 별도의 링크가 필요하지 않을 정도로 간단합니다!
우선 남은 작업을 처리하는 것은 구현하기 귀찮으니 전체를 순회하되 이미 작업이 완료됐으면 넘어가는 방식으로 구현하겠습니다.
내부 데이터 처리 방법
필요한 기능을 대충 나열해 봅시다.
1.
전체 작업을 순회하는 기능
2.
주어진 작업에 대해, 해당 작업의 의존성 작업을 순회하는 기능
3.
재귀적으로 호출될, 작업을 추가하는 기능
4.
다음으로 해야 할 작업이라고, 결과를 출력하는 기능
정말 간단하죠?
각각을 구현하기 위해서 다음과 같은 방법을 사용했습니다.
1.
임시 폴더에 모든 작업에 대한, 작업의 이름으로 된 파일을 하나씩 만들 것입니다.
2.
그 작업에 대한 파일 안에, 그 작업의 의존성 작업 목록을 넣을 것입니다.
3.
해당 부분의 스크립트를 별도의 파일로 분리해서 그 파일을 재귀적으로 호출할 것입니다.
4.
그냥 echo
이 때 작업의 이름으로 된 파일을 만들 때 작업의 이름에 / 등의 특수문자가 있으면 곤란하니 파일명을 8진수로 인코딩해서 저장할 것입니다.
8진수 인코딩/디코딩
왜 하필 8진수냐고 생각할 수 있는데, 그냥 제가 구현하기 이게 제일 쉬웠어요.
POSIX 환경에서 BASE64나 16진수 같은 건 구현하는 방법을 못 찾았거든요.
encode_octal() {
STRING="$1"
RESULT=""
for c in $(printf "%s" "$STRING" | od -An -v -t o1 | tr -d ' '); do
RESULT="$RESULT$c"
done
echo "$RESULT"
}
decode_octal() {
STRING="$1"
RESULT=""
while [ -n "$STRING" ]; do
c=$(printf "%s\n" "$STRING" | cut -c 1-3)
RESULT="$RESULT$(printf "\\$c")"
STRING=$(printf "%s\n" "$STRING" | cut -c 4-)
done
echo "$RESULT"
}
Shell
복사
인자 하나를 받아서 8진수로 인코딩 및 8진수를 디코딩하는 함수
od 명령어를 사용해 한 글자씩 세 자리의 8진수로 바꿔서 이어붙이는 방식으로 인코딩,
3자리씩 잘라서 printf로 한 글자씩 출력해서 이어붙이는 방식으로 디코딩했습니다.
여기서 나오는 문법이 다양한데요, 하나씩 천천히 짚어보겠습니다.
단, 기본적인 쉘 사용법이나 파이프(|) 정도는 알고 있다고 가정합니다.
함수
encode_octal() {부터 }까지가 encode_octal 함수입니다.
함수를 정의하면 encode_octal one two three처럼 호출할 수 있고,
이렇게 호출하면 $1은 one이, $2는 two가, $3은 three가 됩니다.
변수
방금 얘기한 $1, $2, $3이 변수입니다.
STRING="$1" 이런 식으로 STRING 변수에 "$1"이라는 값을 대입할 수 있습니다.
이 외에도 $$(현재 쉘 프로세스의 PID)처럼 미리 설정된 변수도 있습니다.
확장
따옴표 밖에서, 또는 큰따옴표 안에서 변수를 쓰면 그 변수의 값으로 확장됩니다.
예를 들어 $1이 one일 때 echo "Hello $1"을 입력하면 Hello one이 출력됩니다.
그리고 $(echo world)는 echo world를 실행한 결과로 확장됩니다.
이 외에도 쉘에는 정말 다양한 확장이 있지만, 일단은 이 정도만 짚고 넘어가겠습니다.
반복문
for X in Y; do Z; done은 변수 $X가 Y의 처음부터 끝까지 반복해서 Z를 실행합니다.
예를 들어 for X in 1 2 3; do echo $X; done은 1, 2, 3을 출력합니다.
while X; do Y; done은 X가 참(exit code가 0)이면 반복해서 Y를 실행합니다.
이제 여기에서 나온 문법은 다 짚었습니다. [는 사실 문법이 아니라 명령어입니다.
임시 폴더
임시 폴더에 모든 작업에 대한, 작업의 이름으로 된 파일을 하나씩 만들 것이라고 했는데요,
어떻게 해야 프로세스가 끝나면서 임시 폴더가 같이 지워질까요?
TMP_DIR="tmp.$$"
cleanup() {
rm -rf "$TMP_DIR"
}
trap cleanup EXIT
trap cleanup INT
trap cleanup TERM
mkdir -p "$TMP_DIR"
Shell
복사
exit을 만나거나 SIGINT(ctrl + C) 등을 받아서 종료하기 전에 임시 폴더를 삭제하는 코드
trap으로 간단히 해결할 수 있습니다.
trap cleanup EXIT으로 종료할 때 cleanup을 실행하도록 했습니다.
입력
입력 형식은 각 줄을 A 작업을 위해 B, C 작업을 해야 할 때 A=B C처럼 받겠습니다.
mkdir -p "$TMP_DIR/input"
while IFS="=" read -r dependent dependencies; do
echo "$dependencies" | xargs -n 1 echo > "$TMP_DIR/input/$(encode_octal "$dependent")"
echo "$dependencies" | xargs -n 1 echo | while IFS= read -r line; do
touch "$TMP_DIR/input/$(encode_octal "$line")"
done
done
Shell
복사
주어진 모든 작업에 대한 파일을 만드는 코드입니다.
read
read는 IFS(input field separator)를 기준으로 잘라서 입력받은 결과를 변수에 넣어줍니다.
IFS=x read FIRST SECOND에 AxBxC를 입력하면 FIRST는 A가, SECOND는 BxC가 됩니다.
-r 옵션은 \를 다음 줄에서 이어서 받으라는 뜻 대신에, 줄의 일부로 처리하는 옵션입니다.
while 안에서 쓰면 모든 줄을 한 줄씩 입력받을 수 있습니다.
메인 로직
드디어 메인 로직입니다! 모든 작업에 대해 sub.sh를 실행합니다.
mkdir -p "$TMP_DIR/process"
(cd "$TMP_DIR/input" && echo * | xargs -n 1 echo | grep -v '^*$') | sort | while IFS= read -r line; do
TMP_DIR="$TMP_DIR" sh "$(dirname "$0")/sub.sh" "$line"
done
Shell
복사
여기에서 $0에는 이 쉘 스크립트를 호출할 때 사용한 이름이 들어있습니다.
아래는 sub.sh의 내용입니다. (8진수 인코딩/디코딩 등 일부를 생략했습니다.)
[ -f "$TMP_DIR/process/$1" ] || {
touch "$TMP_DIR/process/$1"
< "$TMP_DIR/input/$1" grep -v '^$' | while IFS= read -r line; do
sh "$0" "$(encode_octal "$line")"
done
decode_octal "$1"
}
Shell
복사
이미 처리했으면 그냥 넘어가고, 처리가 안 됐으면 의존성을 먼저 처리한 후 처리 완료했다고 표시하는 간단한 코드입니다.
단, 순환 의존성이 있을 때 재귀호출이 무한히 일어나는 것을 방지하기 위해 처리가 완료됐다는 것을 나타내는 플래그를 먼저 만들었습니다.
결론
쉘 스크립트 별 거 아닙니다.
쉘 스크립트와 친하지 않으시다면 조금씩 친해져 보는 것도 좋을지도…?
