모두가 쉘 스크립트와 친해졌으면 하는 바람으로 작성해봅니다.
위상정렬은 이해하기 쉽게 말하자면 작업의 의존성 그래프를 받아서 해야 할 작업의 순서대로 정렬하는 것입니다.
예를 들어서, 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("이 작업을 먼저 해야 합니다!")
예시를 들어서 설명하자면…
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에서도 확인할 수 있지만…
https://github.com/my-trash-bin/shell-topological-sort
사실 별도의 링크가 필요하지 않을 정도로 간단합니다!
우선 남은 작업을 처리하는 것은 구현하기 귀찮으니 전체를 순회하되 이미 작업이 완료됐으면 넘어가는 방식으로 구현하겠습니다.
필요한 기능을 대충 나열해 봅시다.
정말 간단하죠?
각각을 구현하기 위해서 다음과 같은 방법을 사용했습니다.
echo
이 때 작업의 이름으로 된 파일을 만들 때 작업의 이름에 /
등의 특수문자가 있으면 곤란하니 파일명을 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"
}
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"
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
주어진 모든 작업에 대한 파일을 만드는 코드입니다.
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
여기에서 $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"
}
이미 처리했으면 그냥 넘어가고, 처리가 안 됐으면 의존성을 먼저 처리한 후 처리 완료했다고 표시하는 간단한 코드입니다.
단, 순환 의존성이 있을 때 재귀호출이 무한히 일어나는 것을 방지하기 위해 처리가 완료됐다는 것을 나타내는 플래그를 먼저 만들었습니다.
쉘 스크립트 별 거 아닙니다.
쉘 스크립트와 친하지 않으시다면 조금씩 친해져 보는 것도 좋을지도…?