2장 프로세스와 스레드

프로세스

　프로세스(Process)는 모든 운영체제에서 핵심 개념이다. 프로세스는 간단히 말해 실행하고 있는 프로그램이다. 각 프로세스는 프로세스가 읽고 쓸 수 있는 0에서 특정 최대 값에 이르는 메모리 주소를 일컫는 주소공간(address space)(core image)과 프로세스를 다시 시작할 수 있도록 해 주는 레지스터의 내용 등을 담고 있는 프로세스 테이블 엔트리(process table entry)들로 구성된다.

프로세스 모델

　하나의 프로세스는 실행중인 프로그램으로서 프로그램 카운터의 현재 값, 레지스터, 그리고 변수들을 포함한다. CPU는 다수의 프로세스 사이를 전환하고 있다. 프로그램 사이를 빨리 전환하는 것을 다중프로그래밍(multiprogramming)이라고 부른다.

　(a)는 메모리에 있는 네 개의 프로그램을 다중프로그래밍 형태로 수행하는 컴퓨터를 보여준다. (b)에서는 네 개의 프로그램을 볼 수 있는데, 각각은 자신만의 실행의 흐름을 가지며 또한 다른 프로그램과 독립적으로 수행된다. (c)에서 충분히 긴 시간 간격을 두고 보면 모든 프로세스가 모두 진행 중이지만 어떤 한 순간을 보면 단 하나의 프로세스만 실제로 수행 중임을 알 수 있다.
　프로세스는 어떤 종류의 행위이다. 프로세스는 프로그램, 입력, 출력 그리고 상태를 갖는다. 하나의 처리기(processor)는 다수의 프로세스들 간에 공유될 수 있으며 스케줄링 알고리즘이 언제 프로세스의 작업을 멈추고 다른 프로세스를 서비스 해야 할 지를 결정한다.

프로세스 상태

　다음 상태도는 프로세스가 가질 수 있는 세가지 상태를 보여준다.

• 실행(Running): 이 순간 실제로 CPU를 사용하고 있음
• 준비(Ready): 실행 가능하지만 다른 프로세스가 실행할 수 있도록 일시적으로 정지
• 대기(Blocked): 외부 이벤트가 발생할 때까지 실행할 수 없음

　위 그림에서 세 가지 상태 사이에 네 가지 상태 전이가 가능하다. 상태 전이 1은 어떤 프로세스가 수행을 지속할 수 없음을 운영체제가 발견한 경우이다. 몇몇 시스템의 경우 스스로 대기 상태가 되기 위해 프로세스는 pause와 같은 시스템 호출을 부를 수 있다. 또한 프로세스가 파이프나 특별한 파일로부터 읽으려고 하는데 입력이 주어지지 않은 경우 프로세스는 자동적으로 대기 상태가 된다.
　상태 전이 2와 3은 프로세스 자신은 이러한 상태 전이에 대해 모르는 상태에서 운영체제의 일부분인 프로세스 스케줄러에 의해 야기된다. 상태 전이 2는 스케줄러가 현재 수행중인 프로세스가 충분이 오랫동안 수행되었으며 이제 다른 프로세스에개 CPU 시간을 할당해야 한다고 결정했을 때 발생한다. 상태 전이 3은 다른 모든 프로세스가 공평하게 자신의 몫을 받았으며 이제 다시 처음 프로세스가 CPU를 할당 받아야 한다고 스케줄러가 결정했을 때 발생한다.
　상태 전이 4는 프로세스가 기다리던(입력이 주어지는 것과 같은) 외부 이벤트가 발생했을 때 생긴다. 만약 그 순간 수행중인 다른 프로세스가 없다면 다시 상태 전이 3이 발생하고 해당 프로세스는 실행을 시작한다. 수행중인 다른 프로세스가 존재하면 이 프로세스는 자신의 순번이 되어서 CPU가 이용 가능해질 때까지 준비 상태에서 기다려야 할 것이다.

　위 그림에서 운영체제의 가장 하위 계층은 스케줄러이며 그 위에 다수의 프로세서들이 존재한다. 모든 인터럽트처리와 실제 프로세스를 시작하고 중단하는 세부 사항은 실제로는 많지 않은 코드로 작성된 스케줄러라 불리는 것에의해 감추어진다. 운영체제의 나머지 부분은 프로세스 형태에 따라 아주 잘 구조화될 수 있다. 그러나 실제 시스템의 경우 이와 같이 잘 구조화되지는 않는다.

프로세스의 주소공간

　프로세스는 메모리를 텍스트 세그먼트(text segments)(프로그램 코드), 데이터 세그먼트(data segments)(변수), 스택 세그먼트(stack segments)라는 세 개의 세그먼트로 나눈다. 다음 그림에서처럼 데이터 세그먼트는 위로 자라고 스택은 아래로 자란다.

　이들 사이에는 사용되지 않는 주소공간이 존재한다. 스택은 필요에 따라 이 공간 안으로 자동적으로 증가한다.

프로세스 계층

　몇몇 시스템에서는 프로세스가 다른 프로세스를 생성하면 부모 프로세스(parent process)와 자식 프로세스(child process)는 특별한 방식으로 관계를 지속한다. 자식 프로세스 역시 다른 프로세스들을 생성하여 프로세스 계층 구조를 형성할 수 있다. 프로세스는 단 한 명의 부모만 가지고 있음을 주의해야 한다.
　한 프로세스가 하나 이상의 다른 프로세스를 생성할 수 있고, 이어 이 프로세스들이 또 다시 자식 프로세스를 생성할 수 있다면 다음과 같은 프로세스 트리 구조를 만들어 낼 수 있다.

　프로세스 A가 두 개의 자식 프로세스 B와 C를 생성했다. 프로세스 B가 세 개의 자식 프로세스 D, E, F를 생성했다.
　UNIX에서 프로세스와 그 자식들 그리고 그들의 후손들은 모두 프로세스 그룹을 형성한다. 이와 대조적으로 Windows는 프로세스 계층 구조라는 개념을 가지고 있지 않다. 모든 프로세스는 동등하다.

보호

　시스템 관리자는 시스템을 사용할 권한이 있는 각 사용자에게 UID(User IDentification)를 부여한다. 각 프로세스는 그 프로세스를 시작한 사람의 UID를 갖게된다. 자식 프로세스 역시 부모 프로세스의 UID를 갖는다. 사용자들은 특정 그룹의 멤버일 수 있는데 각 그룹은 GID(Group IDentification)를 갖는다.
　UNIX에서 슈퍼유저(superuser)라는 UID는 특별한 능력을 갖고 있어 보호에 관한 각종 규정들을 어길 수도 있다. 많은 시스템들을 갖춘 대형 시설에서 슈퍼유저 패스워드를 아는 사람은 시스템 관리자 한 명뿐이다. 그러나 패스워드 없이도 슈퍼유저가 되려고 시스템의 문제점들을 찾기 위해 상당한 시간을 헌신하는 일반 사용자들도 상당히 많다.

프로세스의 구현

　프로세스 모델을 구현하기 위해서 운영체제는 프로세스 테이블(process table)(프로세스 제어 블록(process control block))이라 불리는 각 프로세스마다 하나의 엔트리가 존재하는 테이블을 유지한다.
　엔트리는 프로세스 상태에 대한 중요한 정보들을 가지는데 이러한 정보로는 프로그램 카운터, 스택 포인터, 메모리 할당, 열린 파일들의 상태, 과금 및 스케줄링 정보, 기타 프로세스가 실행 상태에서 준비 또는 대기 상태로 전환될 때 저장되어야 할 프로세스에 대한 모든 정보를 포함하며 이들을 저장해야 프로세스는 마치 중단된 적이 없던 것처럼 나중에 재시작 할 수 있다. 다음 그림은 일반적인 시스템에서 볼 수 있는 핵심 필드들을 보여준다.

　첫 번째 열에있는 필드들은 프로세스 관리와 관계된 것이다. 다른 두 열은 각각 메모리 관리와 파일 관리와 관계된 것들이다.

프로세스 생성

　새로운 프로세스는 기존 프로세스가 프로세스 생성 시스템 호출을 실행해야만 생성할 수 있다. 다음은 프로세스의 생성을 유발하는 네 가지 주요 이벤트들이다.

• 시스템 초기화
  • 데몬(Daemon): 후위에 머물면서 전자 우편, 웹 페이지, 뉴스, 인쇄, 기타 등등의 작업을 담당하는 프로세스
• 실행중인 프로세스가 프로세스 생성 시스템 호출을 부르는 경우
  • fork 시스템 호출(fork system call)
• 사용자가 새로운 프로세스를 생성하도록 요청하는 경우
  • 명령어를 입력하거나 또는 아이콘을 클릭하여 수행할 수 있다.
• 배치 작업이 시작
  • 거대한 메인프레임 컴퓨터에서 볼 수 있는 배치 시스템에서만 관찰된다.

프로세스 종료

　다음은 프로세스가 종료되는 조건들이다.

• 정상적인 종료(자발적)
  • 대부분의 프로세스는 자신의 작업을 완료했기 때문에 종료한다.
• 요류 종료(자발적)
  • 프로세스가 치명적인 오류를 발견한 경우
• 치명적인 오류(비자발적)
  • 종종 프로그램의 버그때문에 발생한다.
  • 잘못된 명령어 실행, 존재하지 않는 메모리 접근, 0으로 나누기 등
• 다른 프로세스에 의해 종료(비자발적)
  • kill: 어떤 프로세스가 시스템 호출을 실행하여 운영체제에게 다른 프로세스를 종료시켜 줄 것을 요청하는 경우

프로세스 관리를 위한 시스템 호출

• 프로세스 생성/종료
• 자신의 전 코어 이미지를 자기의 첫 인자에 의해 명시된 파일로 완전히 대체하는 함수
• 자식이 종료되기만을 기다리는 명령
• 더 많은 메모리를 요구/사용하지 않은 메모리를 반납

　다음은 fork, waitpid, execve를 사용하는 아주 단순한 쉘이다.

#define TRUE 1

while (TRUE) {                        /* repeat forever */
  type_promt();                       /* display prompt on the screen */
  read_command(command, parameters);  /* read input from terminal */

  if(fork()!=0) {                     /* fork off child process */
    /* Parent code */
    waitpid(-1, &status, 0);          /* wait for child to exit */
  } else {
    /* Child code */
    execve(command, parameters, 0);   /* execute command */
  }
}

　프로세스를 생성할 수 있는 방법은 fork 시스템 호출 뿐이다. fork 호출에는 반환 값이 있는데 자식의 경우 0이고 부모의 경우 자식 프로세스의 식별자 또는 PID가 된다. waitpid는 특정 자식을 기다릴 수도 있고, 첫 인자를 -1로 설정하면 자식들 중에 임의의 하나를 기다리게 된다. waitpid가 종료되면 둘째 인자 statloc가 가리키는 주소에는 자식의 exit상태가 들어가게 된다. 셋째 인자에 의해 각종 옵션들을 설정할 수 있다. execve시스템 호출은 자신의 전 코어 이미지를 자기의 첫인자에 의해 명시된 파일로 완전히 대체하는 함수이다. execve는 세 개의 인자를 갖는데 각각 실행시킬 파일의 이름, 인자 배열을 가리키는 포인터, 환경 배열을 가리키는 포인터이다. 데이터 세그먼트의 확장은 brk라는 시스템 호출을 통해서 명시적으로 이루어진다. 이 시스템 호출은 데이터 세그먼트가 끝나는 새로운 주소를 명시하고 동적으로 할당 받을 때는 malloc 라이브러리 함수를 사용하도록 권장하고 있다.

인터럽트 처리

　다음은 인터럽트가 발생할 때 운영체제의 가장 하위 레벨에서 수행하는 작업이다.

프로세스간 통신

　프로세스는 종종 다른 프로세스와 통신할 필요가 있다. 프로세스간 통신(InterProcessCommunication, IPC)에는 세 개의 쟁점이 있다.

• 어떻게 프로세스가 다른 프로세스에게 정보를 정달하는가 이다.
  • 예를 들면 쉘의 파이프라인에서 첫 번째 프로세스의 출력은 두 번째 프로세스에게 전달되어야 한다.
• 둘 또는 그 이상의 프로세스가 서로 상대방을 방해하지 않도록 하는 것과 관련이 있다.
  • 예를 들면 항공 예약 시스템에서 두 프로세스가 서로 다른 손님을 위해 마직막 남은 좌석으 배정하기 위해 시도할 때 방생하는 것이다.
• 종속성(dependency)이 존재할 때 적정한 순서를 정하는 것이다.
  • 예를 들면 프로세스 A가 데이터를 생성하고 프로세스 B가 이를 프린트한다면 B는 프린트를 시작하기 전에 A가 데이터를 생성할 때까지 기다려야 한다.

경쟁 조건(Race conditions)

　몇몇 운영체제에서 협력하는 프로세스들은 종종 각 프로세스가 일고 쓸 수 있는 저장공간을 공유한다. 실질적으로 프로세스간 통신이 어떨게 작동하는지 살펴보기 위해 프린트 스풀러(print spooler)라는 간단하지만 일반적인 예제를 살펴보자. 프로세스가 파일을 프린트하고 싶으면 특별한 스풀러 디렉터리에 파일 이름을 기입한다. 프린터 데몬이라는 다른 프로세스는 주기적으로 프린트할 파일이 있는지 검사하며, 있으면 이를 프린트 하고 이를 디렉터리에서 지운다.

　스풀러 디렉터리는 0, 1, 2, …와 같이 번호로 색인되며 이름을 저장하는 다수의 슬롯(slot)을 가지고 있다. Out과 in 두 개의 공유 변수가 있다고 하자. Out은 프린트할 다음 파일을 가리키고 in은 디렉터리에서 다음 번 빈 슬롯을 가리킨다. 이 두 변수는 두 개의 워드로 구성된 파일에 존재하며 모든 프로세스가 이 파일에 접근할 수 있다. 위 그림은 어느 순간 슬롯 0에서부터 3까지 비어있고 (파일들이 이미 프린트 되었고) 슬롯 4에서 6까지 사용 중이다 (프린트할 파일 이름이 대기중이다).
　다음과 같은 상황을 보자.

• 플로세스 A가 in을 읽고 지역 변수 next_free_slot에 7 값을 적는다. 이 때 클록 인터럽트가 발생하고 프로세스 A가 충분히 오래 실행되었으므로 CPU는 이제 프로세스 B로 문맥교환 한다. 프로세스 B 역시 in을 읽고 7값을 적는다. 그리고 이 값을 역시 자신의 next_free_slot 변수(A의 next_free_slot 과 다름)에 저장한다. 이 순간 두 프로세스는 모두 다음 번 이용 가능한 슬롯이 7이라고 생각한다.
• 프로세스 B는 계속해서 수행하면서 자신의 파일 이름을 슬롯 7에 저장하고 in을 8로 변경한다.
• 프로세스 A가 다시 수행하여 문맥교환 직전에 실행하던 위치부터 다시 실행한다. 프로세스는 next_free_slot을 살펴보고 7값을 발견하여 자신의 파일 이름을 슬롯 7에 기록하는데, 이 때 프로세스 B가 기록했던 파일 이름이 지워진다. 그리고 next_free_slot + 1을 계산하여 in에 8을 기록한다. 스풀러 디렉터리는 이제 내부적으로는 일관성이 훼손되지 않는 상태이므로 프린터 데몬은 잘못된 사실을 알지 못한다.그러나 프로세스 B는 자신이 쓴 in값이 없어지므로 자신의 인쇄물을 받을 수 없다.

　둘 또는 그 이상의 프로세스가 공유 데이터를 읽거나 기록하는데 최종 결과는 누가 언제 수행되는가에 따라 달라지는 이러한 상황을 경쟁조건(race condition)이라 부른다.

임계구역(Critical Regions)

　경쟁조건을 회피하기 위해 공유 메모리, 공유 파일, 그리고 무언가를 공유하는 상황에서 문제를 방지하는 핵심은 둘 이상의 프로세스가 동시에 공유 데이터에 읽기와 쓰기를 수행하지 못하도록 금지하는 방법을 고안하는 것이다. 이를 상호배제(mutual exclusion), 즉 한 프로세스가 공유 변수나 파일을 사용 중이면 다른 프로세스들은 똑같은 일을 수행하지 못하도록 하는 것이다.
　공유 메모리를 접근하는 프로그램 부분을 임계구역(critical region, critical section)이라 한다. 만약 두 프로세스가 동시에 임계구역에 존재하지 않도록 조절한다면 경쟁조건을 피할 수 있다.
　비록 이러한 요구 조건이 만족되면 경쟁조건을 피할 수 있지만 병령 프로세스가 정확하게 그리고 효율적으로 공유 데이터를 사용하도록 하기에는 충분하지 않다. 좋은 해결책은 다음과 같은 네 가지 조건을 모두 만족해야 한다.

• 두 개의 프로세스가 동시에 자기의 임계구역 내에 존재하는 경우는 없어야 한다.
• CPU의 개수나 속도에 대해 어떤 가정도 하지 않는다.
• 임계구역 외부에서 실행하고 있는 프로세스는 다른 프로세스들을 블록시켜서는 안된다.
• 임계구역에 진입하기 위해 무한히 기다리는 프로세스는 없어야 한다.

　추상적인 관념에서 우리가 원하는 동작은 다음과 같다.

• 프로세스 A가 시간 $T_1$에 자신의 임계구역에 진입한다. 잠시 후 시간 $T_2$에 프로세스 가 자신의 임계구역에 진입하려고 시도하지만 다른 프로세스가 이미 임계구역에 존재하고 임계구역에는 오직 하나의 프로세스만 존재할 수 있으므로 프로세스 B의 시도는 실패할 것이다.
• B는 A가 지신의 임계구역을 나가는 시간 $T_3$까지 일시적으로 중단되고 A가 나가면 즉시 프로세스 B가 자신의 임계구역에 진입한다.
• 다음으로 B가 시간 $T_4$에 임계구역을 빠져 나가고 자신의 임계구역에 프로세스가 존재하지 않는 원래 상태가 된다.

바쁜 대기를 이용한 상호배제

인터럽트 끄기
　단일 처리기 시스템에서 가장 간단한 해결책은 각 프로세스가 임계구역에 진입하자마자 인터럽트를 끄고 임계구역에서 나가기 직전에 인터럽트를 켜도록 하는 것이다. 인터럽트를 끄면 클록 인터럽트가 발생하지 않는다. 이 방법은 일반적으로 매력적이지 못하는데 이는 사용자 프로세스에게 인터럽트를 끌수 있는 권한을 주는 것은 현명하지 못하기 때문이다. 만약 프로세스 중 하나가 인터럽트를 끄고 다시 켜지 않는다면 시스템은 더 이상 동작하지 않는다.
　반면 커널이 변수나 리스트를 변경하는 단 몇 개의 명령을 수행하는 동안 스스로 인터럽트를 금지시키는 것이 편리할 때가 많다. 결론적으로, 인터럽트 끄기는 운영체제 내부에서 사용할 수 있는 유용한 기법이지만 사용자 프로세스간 상호배제를 위해 일반적으로 사용하기에는 적절하지 않다.

락 변수
　소프트웨어 해법을 생각해 보자. 0으로 초기화된 단일 공유(락) 변수가 있다고 가정하고 다음 예를 보자.

• 임계구역에 진입하려는 프로세스는 먼저 락을 테스트한다.
• 만약 락이 0이면 프로세스는 이를 1로 설정하고 임계구역에 진입한다.
• 만약 락이 1이면 프로세스는 이 변수가 0이 될 때까지 기다린다.
• 따라서 0 값은 임계구역 내에 어떤 프로세스도 없다는 것을 의미하며 1은 임계구역에 어떤 프로세스가 존재함을 의미한다.

　이 생각은 스풀러 디렉터리에서 보았던 것과 정확히 동일한 결함을 가지고 있다. 한 프로세스가 락을 읽고 이 값이 0임을 알았다고 하자. 프로세스가 락을 1로 설정하기 전에 다른 프로세스가 스케줄되어 실행하면서 락을 1로 설정한다. 다시 첫 번째 프로세스가 실행하면서 락을 1로 설정할 것이며 두 개의 프로세스가 동시에 임계구역에 들어가게 된다.

엄격한 교대
　상호배제 문제의 기법이 다음과 같이 표시되어있다. (a)는 프로세스 0, (b)는 프로세스 1이다.

　초기값이 0인 정수 변수 turn은 임계구역에 진입하여 공유 메모리를 검사하고 변경할 순번을 나타낸다. 최초에 프로세스 0이 turn을 검사하여 이 값이 0임을 발견하면 임계구역에 진입한다. 또한 프로세스 1은 이 값을 검사하여 0임을 발견하고 turn이 1이 되는지를 검사하면서 루프를 돌게 된다. 변수가 특정 값이 될 때까지 계속해서 검사하는 것을 바쁜 대기(busy waiting)라 한다. 이것은 CPU 시간을 낭비하므로 바쁜 대기는 일반적으로 피해야 한다. 기다리는 시간이 짧을 것이라고 합리적으로 예상할 수 있는 경우만 바쁜 대기가 사용된다. 바쁜 대기를 사용하는 락을 스핀 락(spin lock)이라 부른다.
　프로세스 0이 임계구역을 떠나면서 turn을 1로 설정하여 프로세스 1이 임계구역에 진입할 수 있도록 한다. 이제 프로세스 1이 재빨리 임계구역 실행을 마치고, turn은 0으로 설정되어, 두 프로세스 모두 임계구역 밖에 있다고 하자. 다시 프로세스 0이 루프를 수행하고 임계구역을 벗어나면서 turn을 1로 설정한다. 이 순간 turn은 1이며 두 프로세스 모두 비임계구역을 수행 중이다.
　갑자기 프로세스 0이 비임계구역의 수행을 마치고 루프의 맨 윗부분을 실행한다. 불행하게도 이 프로세스는 임계구역 진입이 허가되지 않는데 이는 turn이 1이기 때문이며 이 순간 프로세스 1은 비임계구역을 바쁘게 실행하고 있다. 프로세스 1이 turn을 0으로 바꿀 때까지 프로세스 0은 while 루프에 묶여 있어야 한다. 다르게 표현하면 한 프로세스가 다른 프로세스보다 상당히 느린 경우 교대로 일하는 것은 좋은 생각이 아니다.
　프로세스 0은 임계구역에 존재하지 않는 다른 프로세스에 의해 블록되므로 이러한 상황은 앞에서 설정한 조건 3을 위반한다. 앞에서 살펴봤던 스풀러 디렉터리 문제에 대입해 보면 스풀러 디렉터리에 읽고 쓰는 동작을 임계구역이라고 할 때, 이 상황은 프로세스 1이 다른 일을 하고 있어서 프로세스 0이 또 다른 파일을 프린트 할 수 없는 것과 같다.
　이 해법은 두 프로세스가 엄격하게 교대로 임계구역에 진입하는 것을(예를 들어, 교대로 파일을 스풀링할 것을) 요구한다. (어떠한 프로세스도 연속해서 두 개의 파일을 스풀링 할 수 없다.) 이 알고리즘은 비록 경쟁조건을 피할 수는 있지만 조건 3을 위반하므로 진정한 해결책의 후보가 될 수 없다.

Peterson의 해법
　엄격한 교대를 요구하지 않는 간단한 방법의 상호배제 문제를 달성하는 소프트웨어 해결책을 제시하였다.

　공유 변수를 사용하기 전에(즉, 임계구역에 진입하기 직전에) 각 프로세스는 자신의 프로세스 번호 0 또는 1을 인자로 제공하면서 enter_region을 호출한다. 이 호출은 필요한 경우 안전하게 진입할 때 까지 기다리게 할 수도 있다. 임계구역에 진입하여 공유 변수 사용을 마친 후 프로세스는 leave_region을 호출하여 자신의 임계구역 수행 종료와 임계구역 진입을 원하는 다른 프로세스가 진입할 수 있음을 알려준다.
　이 해법이 어떻게 동작하는지 살펴보자.

• 초기에 어떤 프로세스도 임계구역에 존재하지 않는다. 이때 프로세스 0이 enter_region을 호출하였다. 이 프로세스는 자신의 배열 변수를 설정(interested[0]을 TRUE)하고 turn을 0으로 설정하여 자신이 임계구역에 진입하고 싶어함을 표시한다. 프로세스 1은 임계구역 진입에 관심이 없으므로 enter_region은 즉시 복귀하고 프로세스 0은 임계구역에 진입한다.
• 이제 프로세스 1이 enter_region을 호출하면 프로세스 1은 interested[0]이 FALSE가 될 때까지 기다려야 하며 이러한 변경은 프로세스 0이 임계구역을 나가기 위해 leave_region가 호출할 때 이루어진다.

　이제 두 프로세스가 거의 동시에 enter_region을 호출하는 경우를 보자. 누구의 변수 값 변경이 늦게 수행되었는지가 중요한데 이는 처음 값이 다음 변경에 의해 덮어 쓰여져서 사라지기 때문이다.

• 프로세스 1이 마지막에 변경하여 turn이 1이라고 하자.
• 두 프로세스 모두 while 문장에 도차하면 프로세스 0은 루프를 수행하지 않고 임계구역에 진입한다.
• 프로세스 0이 임계구역을 나올 때 까지 프로세스 1은 루프를 돌면서 임계구역에 진입하지 못한다.
  

TSL 명령
　하드웨어의 도움을 약간 필요로 하는 해결책을 살펴보자. 다중처리기를 염두에 두고 설계된 컴퓨터들은 다음과 같은 명령을 가지고 있다.

TSL RX(REGISTER), LOCK

　TSL(Test and SetLock) 명령은 다음과 같이 작동한다.

• 메모리 워드 LOCK의 값을 읽어 레지스터 RX에 저장하고 메모리 주소 LOCK에 0이 아닌 값을 기록한다. 이 연산이 완료될 때까지 다른 어떤 처리기도 메모리 워드에 접근할 수 없다.
  • TSL 명령을 수행하는 CPU는 수행이 끝날 때까지 메모리 버스를 잠금으로써 다른 어떤 CPU도 메모리에 접근할 수 없도록 한다.
• TSL 명령과 공유 변수 lock을 사용하여 공유 메모리에 대한 접근을 조정할 수 있다.
  • Lock이 0이면 어떤 프로세스도 TSL을 사용하여 이를 1로 설정하고 공유 메모리에 읽기와 쓰기를 수행할 수 있다.
• 작업을 마치면 프로세스는 일반적인 move 명령을 사용하여 lock을 다시 0으로 설정한다.

　두 개의 프로세스가 동시에 임계구역에 진입하는 것을 방지하는 방법은 다음과 같다.

　첫 번째 명령은 lock의 (이전) 값을 레지스터로 복사하고 lock을 (새로운 값) 1로 설정한다. 그리고 이전 값이 0인지를 비교한다. 이것이 0이 아니면 lock은 이미 전에 설정되었으며 따라서 프로그램은 서브루틴의 처음으로 돌아가 TSL 명령을 다시 시작한다. 현재 임계구역에 진입한 프로세스가 임계구역 작업을 마치면 lock 값은 0이 되고 이 서브루틴은 lock을 다시 설정하려고하며 락을 자신이 설정하면 복귀한다.
　임계구역 문제의 해결책은 이제 명확하다. 임계구역에 진입하기 위해서 프로세스는 enter_region을 호출하며 이 루틴은 락이 풀릴 때까지 바쁜 대기를 한 다음 락을 획득하고 복귀한다. 임계구역을 수행한 후 프로세스는 leave_region을 호출하며 이 루틴은 lock에 0을 저장한다. 임계구역의 다른 모든 해법과 마찬가지로 이 기법이 동작하기 위해서는 프로세스가 enter_region과 leave_region을 적절한 시점에 호출해야 한다.

슬립과 깨움

　앞의 기법들은 CPU 사간을 낭비할 뿐 아니라 예기치 못한 결과인 우선순위 역전 문제(priority inversion problem)이 발생한다.
　임계 구역 진입이 허용되지 않을 때 CPU 시간을 낭비하는 대신 블록하는 프로세스간 통신 프로미티브를 살펴보자. 가장 간단한 것이 슬립(sleep)과 깨움(wakeup)쌍이다. Sleep은 호출자를 블록 상태로 만드는 시스템 호출로 다른 프로세스가 호출자를 깨워출 때까지 블록 상태에 머물게 된다. Wakeup 호출은 깨울 프로세스를 가리키는 인자 하나를 가지고 있다.

생산자-소비자 문제
　두 프로세스가 고정된 크기의 버퍼를 공유한다. 이중 하나는 생산자로 정보를 버퍼에 저장하고 다른 하나는 소비자로 버퍼에서 정보를 꺼내온다.
　생산자가 새로운 아이템을 버퍼에 넣으려고 하는데 버퍼가 가득 차 있을 때 문제가 발생한다. 해결책은 생산자가 잠들고 소비자가 아이템을 하나 제거할 때 깨워주는 것이다. 마찬가지로 소비자가 아이템을 버퍼에서 가져오려고 하는데 버퍼가 비어 있으면 소비자는 잠들고 생산자가 버퍼에 아이템을 넣을 때 깨워준다.
　이 방법은 경쟁조건과 동일한 일이 발생할 수 있다. 버퍼에 존재하는 아이템의 개수를 표시하기 위해 count 변수를 사용한다고 하자. 버퍼에 존재하는 아이템의 최대 개수는 N이고 생산자 코드의 앞부분에서 count가 N인지를 검사한다. 만약 N이면 생산자는 잠들며 그렇지 않으면 생산자는 아이템을 추가하고 count를 증가시킨다.
　소비자 코드도 유사하다. 먼저 count가 0인지를 검사한다. 0이면 잠들고 0이 아니면 아이템을 제거하고 count를 감소시킨다. 각 프로세스는 또한 다른 프로세스를 깨워야 하는지 검사하여 필요하면 해당 프로세스를 깨운다. 이러한 생산자와 소비자 코드는 다음과 같다.

세마포어(Semaphore)

　세마포어(semaphore)라 부르는 새로운 변수형을 도입한다. 세마포어는 깨움이 저장되지 않은 0값 또는 하나 이상의 깨움이 대기 중인 양수 값을 가질 수 있다. down(P)과 up(V) 두 개의 연산을 제한하였다.

• down 연산
  • 값이 0보다 큰 지를 검사한다. 만약 그렇다면 이 값을 감소시키고 수행을 계속한다. 만약 이 값이 0이면 프로세스는 down의 수행을 완료하지 않고 즉시 잠들게 된다.
• up 연산
  • 세마포어 값을 증가시킨다.
  • 하나 또는 그 이상의 프로세스가 down 연산을 완료할 수 없어서 세마포어에서 잠들어 있으면 이 중 한 프로세스가 시스템에 의해 선택되어 down 수행을 완료할 수 있다.
  • 따라서 프로세스가 잠들어 있는 세마포어에 대해 up을 수행하면 세마포어 값은 여진히 0이지만 잠들어 있는 프로세스의 개수는 하나가 감소한다.
• 값을 검사하고, 변경하고, 경우에 따라 잠드는 이러한 모든 동작은 분할할 수 없는 하나의 원자적행위(atomic action)이다.
  • 한 번 세마포어 연산이 시작되면 이러한 원자성이 보장되어야 하며 이 연산이 완료되거나 프로세스가 잠들 때까지 다른 프로세스가 세마포어에 접근할 수 없도록 보장되어야 한다.

세마포어를 이용한 생산자-소비자 문제의 해결

　세마포어가 제대로 동작하게 만들기 위해 이들을 분할할 수 없는 방식으로 구현하는 것이 필수적이다. Up과 down을 구현하는 일반적인 방식은 시스템 호출 형태로 구현하는 것으로 운영체제가 잠시 모든 인터럽트를 끄고, 세마포어를 검사하고, 변경하고, 필요하다면 프로세스를 잠들도록 한다. 이러한 모든 행위는 단지 몇 개의 명령어로 수행되므로 인터럽트를 끄는 것은 큰 해를 끼치지 않는다.

• 생산자-소비자 문제의 해법은 세 개의 세마포어를 사용한다.
  • 하나는 full이라 불리며 아이템으로 채워진 슬롯의 개수를 나타내고 다른 하나는 empty라 불리며 빈 슬롯의 개수를 나타내며 나머지 하나는 mutex로 생산자와 소비자가 동시에 버퍼에 접근하지 못하도록 한다.
  • Full은 0으로 초기화 되고 empty는 버퍼에 있는 슬롯의 개수로 초기화되며 mutex는 1로 초기화된다.
  • mutex는 다음에 배울 뮤텍스와는 다르다.
• 세마포어가 1로 초기화되고 둘 또는 그 이상의 프로세스가 사용되면서 이 들 중 한 프로세스만 임계구역에 진입할 수 있도록 하는 용도로 사용되는 세마포어를 이진 세마포어(binary semaphore)라 부른다. 만약 각 프로세스가 임계구역에 진입할 때 down을 수행하고 임계구역을 나오면서 up을 부르면 상호배체가 이루어진다.
• Mutex 세마포어는 상호배체를 위해 사용되었다. 이것은 한 번에 단 하나의 프로세스만 버퍼나 관련된 변수를 읽고 쓰도록 보장하는 용도로 사용된다. 이러한 상호배제는 혼란을 막기 위해 필요하다.
• 세마포어의 다른 용도는 동기화(synchronization)이다.
  • Full과 empty 세마포어는 특정 이벤트 순서들이 발생하거나 발생하지 않도록 보장하기 위해 필요하다.
  • 이 세마포어들은 버퍼가 가득찬 경우 생산자가 정지하도록 하는 것을, 그리고 버퍼가 빈 경우 소비자가 정지하도록 하는 것을 보장한다.

뮤텍스

　세마포어의 개수를 세는 능력이 필요없는 경우 뮤텍스라 불리는 세마포어의 단순한 버전이 사용될 수 있다.(세마포어 자체는 아님)
　뮤텍스(mutex)는 변수로서, 언락(unlock)과 락(lock), 두 가지 중 한 상태를 가진다. 실제 구현에서 종종 하나의 정수가 사용되어 0인 경우 언락을, 그리고 다른 값은 락을 의미한다. 뮤텍스와 함께 두개의 프로시듀어가 사용된다. 스레드가 임계구역에 접근할 때 mutex_lock을 호출한다. 뮤텍스가 현재 언락이면 호출은 성공하고 호출한 스레드는 임계구역에 진입할 수 있다.
　이와 달리 뮤텍스가 이미 락 상태이면 스레드는 임계구역에 있는 스레드가 수행을 마치고 mutex_unlock을 호출할 때까지 블록된다. 락이 해지될 때 다수의 스레드가 하나의 뮤텍스에서 대기 중이면 이들 중 하나가 임의로 선택되어 락을 획득한다.

　mutex_lock 코드는 전의 enter_region 코드와 유사하지만 중요한 차이점이 있다.

• enter_region이 임계구역 진입에 실패하는 경우 락을 반복적으로 검사한다(바쁜대기). 그리고 시간이 흘러가면 다른 프로세스가 스케줄 되어 실행한다. 조만간 락을 획득한 프로세스가 수행되면서 락을 반환한다.
• mutex_lock의 경우 락을 획득하지 못하면 thread_yield를 호출하여 다른 스레드에게 CPU를 양보한다. 결과적으로 바쁜 대기는 존재하지 않는다. 나중에 스레드가 다시 수행하게 되면 락을 다시 검사한다.

모니터

　세마포어와 뮤텍스를 이용한 프로세스간 통신은 사용할 떄 매우 조심해야 한다. 한 가지 사소한 오류가 전체를 완전히 엉망으로 만든다. 정확한 프로그램을 좀 더 쉽게 작성할 수 있도록 모니터(monitor)라는 고급 동기화 프리미티브가 제안되었다.

• 모니터는 특별한 형태의 모듈 또는 패키지에 모아진 프로시듀어, 변수, 그리고 자료구조의 모음이다.
• 프로세스는 필요하면 언제든지 모니터의 프로시듀어를 호출할 수 있지만 모니터 밖의 프로시듀어에서 모니터의 내부 자료 구조를 직접 접근하는 것은 불가능하다.

　모니터는 상호배제를 성취하는데 유용한 중요한 속성을 가지는데 이 속성은 바로 “단 하나의 프로세스만 한 순간에 모니터에서 활동할 수 있다”는 것이다. 모니터를 진입할 때 상호배제를 구현하는 것은 컴파일러의 책임이지만 일반적으로 뮤텍스나 이진 세마포어를 사용한다. 상호배제를 달성하는 것은 프로그래머가 아닌 컴파일러의 책임이므로 잘못될 가능성은 훨씬 적다.
　생산자-소비자 문제에서 버퍼가 찼는지 또는 버퍼가 비어 있는지 검사하는 것을 모니터의 프로시듀어로 쉽게 만들 수 있지만 버퍼가 가득 차면 생산자는 어떨게 블록되어야 하는지의 문제는 조건 변수(condition variables)와 이들에 대한 두가지 연산 wait과 signal을 도입하여 해결할 수 있다.

• 모니터 프로시듀어가 더 이상 진행할 수 없음을 인식하면, 어떤 조건 변수에 대해 wait을 수행한다.
  • 이 동작은 호출한 프로세스를 대기하게 만든다. 이것은 또한 현재 모니터 진입을 금지 당하고 있는 다른 프로세스가 모니터에 진입할 수 있게 만든다.
• 파트너 프로세스가 대기 중인 조건 변수에 대해 signal을 수행하여 대기 중인 파트너를 깨울 수 있다.

메시지 패싱

　메시지 패싱(message passing)을 이용한 프로세스간 통신은 send와 receive 두 가지 프리미티브를 사용하는데 이들은 모니터처럼 프로그래밍 언어의 구조체가 아니라 세마포어처럼 시스템 호출의 일종이다. 이들은 다음과 같이 간단하게 라이브러리 프로시듀어로 만들어질 수 있다.

• send(destination, &message);
  • 메시지를 명시된 목적지에 전송한다.
• receive(source, &message);
  • 명시된 정보원으로부터 메시지를 받는다.
  • 전달된 메시지가 없으면 수신자는 메시지가 도착할 때까지 대기한다. 또는 이와 달리 오류 코드와 함께 즉시 복귀할 수도 있다.

메시지 전달 시스템의 설계 쟁점

• 메시지는 네트워크 상에서 사라질 수 있다.
• 메시지 전달 시스템은 또한 send와 receive 호출에서 지정하는 프로세스가 모호하지 않도록 각 프로세스의 이름을 어떻게 부여할 것인지를 해결해야 한다.
• 인증(authentication) 또한 메시지 전달 시스템의 쟁점이다.
• 송신자와 수신자가 같은 기계에 있는 경우 중요한 설계 쟁점들중 하나는 성능이다.

장벽

　어떤 응용들은 단계별로 구성되며 모든 프로세스가 다같이 다음 단계로 진행할 준비가 되기 전에 어떤 프로세스만 먼저 다음 단계로 진행할 수 없다는 규칙을 가지고 있다. 이러한 동작은 각 단계의 끝에 장벽(barrier)을 설치함으로써 달성할 수 있다.

스케줄링

　컴퓨터가 다중프로그래밍 형태로 동작할 때 종종 다수의 프로세스 또는 스레드가 동시에 CPU를 사용하기 위해 경쟁한다. 이런 상황은 둘 또는 그 이상의 준비 상태인 경우에 발생한다. 단 하나의 CPU만 사용할 수 있다면 다음에 실행할 프로세스를 선택해야한다. 이와 같은 선택을 하는 운영체제의 일부분을 스케줄러(scheduler)라 하고 스케줄러의 알고리즘을 스케줄러 알고리즘이라 부른다.

스케줄링 소개

　과거 자기 테이프에 담긴 카드 이미지 형태로 입력을 받는 배치 시스템 시대로 되돌아 가면, 기계에서 CPU시간은 희소성을 가진 자원이어서 좋은 스케줄러는 사용자가 인식하는 성능과 사용자가 만족도 면에서 큰 차이를 보일수 있다. 결과적으로 영리하고 효율적인 알고리즘을 고안하기 위하여 많은 일들이 행해졌다.
　개인용 컴퓨터의 등장으로 상황은 다음과 같은 형태로 바뀌었다. 첫째, 대부분의 경우 하나의 활성화된 프로세스만 존재한다. 둘째, 컴퓨터는 해마다 빠르게 발전하여 더 이상 CPU가 희소성을 가진 자원이 아니다. 결과적으로, 단순한 PC에서 스케줄링은 별로 문제가 되지 않는다.
　네트워크 서버로 눈을 돌려보면 훨씬 더 변화를 쉽게 감지할 수 있다. 이 경우 다수의 프로세스가 종종 CPU를 놓고 경쟁하기 때문에 스케줄링이 다시 문제가 된다. 프로세스간 문맥교환은 높은 비용을 요구하기 때문에 다음에 수행할 적당한 프로세스를 선정하는 것 이외의 스케줄러는 CPU를 효율적으로 사용하도록 관심을 기울여야 한다.

프로세스의 행동
　다음과 같이 거의 모든 프로세스는 한동안 계산을 수행하다가 다시 한동안 I/O를 요청하는 행동을 반복한다. 일반적으로 CPU는 한동안 계산을 수행하다가 파일을 읽거나 쓰기 위해 시스템을 호출을 수행한다. 시스템 호출이 완료되면 다시 데이터가 필요하거나 데이터를 기록해야 할 때까지 CPU는 계산을 수행하며 이러한 과정이 반복된다.

　위에서 주목해야 할 사항은 (a)와 같은 일부 프로세스의 경우 대부분의 시간을 소비하는 반면, (b)와 같은 프로세스의 경우 대부분의 시간을 I/O를 기다리면서 보낸다는 점이다. 전자를 CPU-바운드라 부르고 후자를 I/O-바운드라 부른다. CPU-바운드 프로세스는 일반적으로 긴 CPU 버스트를 가지며 드물게 I/O를 기다리는 반면, I/O-바운드 프로세스는 CPU 버스트가 짧은 반면 빈번히 I/O를 기다린다. 이들을 구분하는 핵심은 I/O 버스트의 길이가 아니라 CPU 버스트의 길이이다. I/O-바운드 프로세스의 경우 특별히 I/O 요청이 오래 걸려서가 아니라 I/O 요청 중간에 많은 계산을 필요로 하지 않기 때문에 I/O 바운드라고 부른다.

언제 스케줄 해야 하는가?

• 새로운 프로세스를 만들 때 자식 프로세스를 먼저 실행할 것인지 부모 프로세스를 먼저 실행할 것인지 결정해야 한다.
• 프로세스를 종료할 때 스케줄링 결정이 필요하다.
  • 해당 프로세스는 더 이상 존재하지 않으므로 수행할 수 없어 준비 상태의 다른 프로세스가 선택되어야 한다.
• 프로세스가 I/O, 세마포어, 또는 다른 무언가 때문에 대기해야 할 때 다음에 실행할 다른 프로세스를 선택해야 한다.
• I/O 인터럽트가 발생하는 경우 스케줄링 결정을 내려야 한다.
  • 다음에 수행할 프로세스로 새로 준비 상태가 된 프로세스를 선택할 것인지, 인터럽트가 발생할 때 실행 중이던 프로세스를 선택할 것인지, 아니면 제 삼의 프로세스를 선택할 것인지는 스케줄러에게 달려있다.

　스케줄링 알고리즘은 클록 인터럽트를 어떻게 다루는가에 따라 두 가지 범주로 나뉜다.

• 비선점(nonpreemptive) 스케줄링 알고리즘
  • 어떤 프로세스가 다음 수행 프로세스로 선정되면 이 프로세스는 I/O나 다른 프로세스를 기다리기 위해 대기하거나 자발적으로 CPU를 반환할 때까지 계속 수행할 수 있다.
• 선점형(preemptive) 스케줄링 알고리즘
  • 프로세스를 선택하고 최대 값으로 정해진 시간을 넘지 않는 범위에서 실행되도록 한다.
  • 만약 정해진 시간 간격의 끝에 도달하면 이 프로세스는 중단되고 스케줄러는 다음에 실행할 다른 프로세스를 (만약 존재하면) 선정한다.

스케줄링 알고리즘의 부류
　무엇을 목표로 스케줄러는 최적화 해야 하는가는 모든 시스템에서 동일하지 않다. 특징적인 세 가지 환경은 다음과 같다.

• 배치(Batch)
  • 비선점형 알고리즘 또는 각 프로세스에게 긴 주기를 제공하는 선점형 알고리즘이 적절하다.
  • 프로세스간 문맥교환을 줄여서 성능을 향상시킨다.
• 대화식(Interactive)
  • 한 프로세스가 CPU를 독점하여 다른 사용자의 서비스를 방해하는 것을 막기 위해서 선점이 필수적이다.
• 실시간(Real time)
  • 때때로 선점이 필요하지 않는데 그 이유는 프로세스들이 자신들이 실행을 오랫동안 할 수 없다는 점을 알고 있어 보통 자신이 해야 할 일을 바로 수행하고 바로 대기하기 때문이다.

스케줄링 알고리즘의 목표
　스케줄링 알고리즘을 설계하기 위해서는 좋은 알고리즘은 무엇을 해야 하는 지를 명확히 할 필요가 있다. 몇몇 목표는 환경(배치, 대화실, 실시간)에 따라 다르지만 모든 경우에 바람직한 무언가도 존재한다.

• 모든 시스템
  • 공평함 - 각 프로세스에게 공평한 몫의 CPU를 할당함
  • 정책 집행 - 정책이 집행되는지 관찰
  • 균형 - 시스템의 모든 부분이 활동하도록 함
• 배치 시스템
  • 성능 - 시간당 처리되는 작업 수 최대화
  • 반환시간 - 작업의 제출부터 종료까지 걸리는 시간을 최소화
  • CPU 이용률 - CPU가 항상 활용되도록 함
• 대화식 시스템
  • 응답시간 - 요청에 빠르게 응답하도록 함
  • 비례(proportionality) - 사용자의 기대를 만족시킴
• 실시간 시스템
  • 마감시간 만족 - 데이터 손실 방지
  • 예측 가능 - 멀티미디어 시스템에서 품질 저하를 방지

　모든 환경에서 공평함은 중요하다. 서로 비슷한 처지의 프로세스들은 비슷한 서비스를 받아야 한다. 물론, 프로세스의 부류가 다른 경우 서로 다르게 취급될 수 있다.
　시스템의 정책 집행은 공평함에 어느 정도 영향을 미친다. 만약 안전 관리 프로세스는 필요한 경우 언제든지 실행되어야 한다는 것이 내부의 정책이라면, 비록 급여 계산이 30초 늦어진다 하더라도, 스케줄러는 이 정책이 집행되도록 해야 한다.
　또 다른 일반적인 목표는 가능하면 시스템의 모든 부분을 바쁘게 구동하는 것이다. 만약 CPU 및 모든 I/O장치가 항상 계속 동작한다면 비록 일부 구성 요소가 유휴 상태에 있어도 초당 훨씬 많은 작업이 수행될 것이다.
　많은 배치 작업을 실행하는 대형 컴퓨터 센터의 관리자들은 일반적으로 자신들의 시스템이 얼마나 잘 수행하고 있는지 판단하기 위해 처리량, 반환시간, CPU 이용률, 세 가지 성능 기준을 사용한다. 처리율(throughput)은 시간 당 처리된 작업의 개수이다. 반환 시간(turnaround time)은 배치 작업이 제출된 순간부터 끝날 때까지 걸린 통계적인 평균 시간이다. 이것은 평균적으로 사용자가 얼마나 오래 출력을 기다려야 하는지를 측정한 것이다. 여기서 규칙은 “작을수록 좋은 것이다”이다. CPU 이용률은 종종 배치 시스템의 측정에 사용된다. 이것은 좋은 성능 측정 기준이 아니다. 진짜 중요한 것은 시간 당 얼마나 많은 작업 결과가 시스템으로부터 배출(처리량)되는지와 작업이 되돌아 오는데 얼마나 걸렸는지(반환 시간)이다.
　대화형 시스템의 경우 다른 목표가 적용된다. 가장 중요한 것은 응답 시간(response time)을 최소화하는 것으로 응답 시간은 명령을 입력한 후 결과를 받게 되는데 걸린 시간이다. 이것과 어느 정도 관련이 있는 주제 중 하나가 바로 비례성(proportionality)이다. 사용자는 일이 얼마나 걸리는지에 대한 선입견을 가지고 있다. 복잡하다고 생각하는 요청이 오래 걸리면 사용자는 이를 받아들이지만 단순하다고 생각한 요청이 오래 걸리면 사용자는 흥분한다.
　실시간 시스템은 대화식 시스템과는 다른 특성을 가지고 있어 스케줄링 목표도 다르다. 이들은 반드시 만족되어야 하는 마감시간(deadline)을 가지고 있다는 것이 특징이다. 일부 시스템에서, 특히 멀티미디어 관련 시스템에서, 예측 가능하다는 것은 중요하다.

배치 시스템의 스케줄링

선입선출(First-Come First-Served, FCFS)
　이 알고리즘에서 프로세스들은 요청 순서대로 CPU를 할당 받는다. 기본적으로, 준비 상태의 프로세스를 위해 단일 큐가 존재한다. 다른 작업이 도착하면 이들은 큐의 끝 부분에 놓인다. 실행중인 프로세스가 대기 상태가 되면 큐의 첫 번째 프로세스가 이어 실행된다. 대기 상태의 프로세스가 준비 상태가 되면 마치 새로 도착한 작업처럼 큐의 끝 부분에 놓인다. 이 알고리즘의 가장 큰 장점은 이해하기 쉽고 프로그램이 쉽다는 점이다. 이 알고리즘에서 단 하나의 연결 리스트로 모든 준비 상태의 프로세스를 관리한다. 다음에 수행할 프로세스를 선택하는 것은 단지 큐의 맨 앞에서 프로세스 하나를 제거함으로써 수행된다. 새로운 작업을 추가하거나 대기 상태의 프로세스를 다시 수행 가능하게 만들려면 프로세스를 큐의 맨 끝에 추가하면 된다.
　선입선출은 심각한 단점을 가지고 있다. 한 번에 1초씩 수행되는 CPU-바운드 프로세스와 CPU 시간은 거의 사용하지 않고 끝날 때까지 1000개의 디스크 읽기를 수행하는 다수의 I/O-바운드 프로세스가 존재한다고 가정하자. CPU-바운드 프로세스는 1초 수행한 후 디스크 블록을 하나 읽어온다. 전체적인 결과를 보면 각 I/O-바운드 프로세스는 초당 한 블록씩 읽게 되어 종료할 때까지 1000초가 걸릴 것이다.

최단작업우선(Shortest Job First, SJF)
　실행 시간을 미리 안다고 가정할 때 적용할 수 있는 또 다른 비선점 배치 시스템 알고리즘은 최단작업우선(Shortest Job First)이다. 몇 가지 똑같이 중요한 작업들이 입력 큐에 대기 중 일 때 스케줄러는 실행 시간이 짧은 최단 작업을 선택한다. 다음 예를 보자.

　여기서 각각 실행 시간이 8, 4, 4, 4분인 A, B, C, D 네개의 작업을 볼 수 있다.이들을 이 순서대로 실행하면 A의 반환시간은 8분, B는 12분, C는 16분, D는 20분이 되며 평균 14분이다. (b)처럼 최단적업우선 순으로 네 개의 작업을 실행시키는 경우를 생각해보자. 이제 반환 시간은 4, 8, 12, 20분으로 평균 11분이다. 최단작업우선이 최적이라는 것은 증명된 사실이다.
　모든 작업이 동시에 존재할 때만 최단작업우선이 최적임을 짚고 넘어갈 필요가 있다. 예로, A부터 E까지 다섯 개의 작업이 있고 각각 실행 시간이 2, 4, 1, 1, 1이라고 하자. 이들 각각의 도착 시간은 0, 0, 3, 3, 3이다. 처음에는 다른 작업이 도착하지 않았으므로 오직 A 또는 B를 선택해야 한다. 최단작업우선에 따라 작업들은 A, B, C, D, E 순으로 수행되며 평균 대기 시간은 4.6이 된다. 그러나 B, C, D, E, A순으로 수행되면 평균 대기 시간은 4.4가 된다.

최단잔여시간우선(Shortest Remaining Time Next, SRTN)
　최단작업우선의 선점형 버전이 최단잔여시간우선(Shortest Remaining Time Next)이다. 이 알고리즘에서 스케줄러는 항상 프로세스의 남은 실행 시간이 가장 짧은 작업을 선택한다. 새로운 작업이 도착하면 이것의 실행 시간을 현재 수행중인 프로세스가 작업을 마칠 때까지 필요한 시간보다 더 작은 경우, 현재 프로세스는 중단되고 새로운 작업이 실행을 시작한다.

대화식 시스템의 스케줄링

라운드 로빈 스케줄링(Round-Robin Scheduling)
　가장 오래되고, 간단하고, 공평하고, 널리 사용되는 알고리즘은 라운드 로빈 스케줄링(Round-Robin Scheduling)이다. 각 프로세스에게는 시간 할당량(time quantum)이라 불리는 시간 주기가 할당되며 한 번에 이 시간동안만 실행된다. 프로세스가 할당 시간 동안 실행하면 CPU는 선점되어 다른 프로세스에게 주어진다. 프로세스가 할당 시간이 끝나기 전에 대기하거나 종료하면 CPU는 다른 프로세스로 전환한다. 라운드 로빈은 구현이 간단하다.

　스케줄러가 해야 할 일은 그림 (a)처럼 실행 가능한 프로세스를 위한 리스트를 관리하는 것뿐이다. 프로세스가 할당 시간을 소비하면 (b)처럼 이 리스트의 맨 뒤에 놓인다.
　라운드 로빈에서 한 가지 흥미로운 주제는 할당 시간의 크기이다. 한 프로세스에서 다른 프로세스로 문맥교환하는 것은 레지스터 및 메모리 맵의 저장 및 적재, 여러 테이블과 리스트의 갱신, 메모리 캐시의 플러쉬와 재적재, 기타 등등 관리 작업을 수행하기 위하여 상당한 시간을 필요로 한다.
　결론적으로 다음과 같이 공식화 될 수 있다. 할당 시간이 짧으면 너무 많은 프로세스간 교환을 유발하고 CPU의 효율은 떨어진다. 그러나 너무 길면 짧은 대화식 요청의 응답의 질이 떨어진다.

우선순위 스케줄링
　우선순위 스케줄링(priority scheduling)의 기본적인 아이디어는 각 프로세스에게는 우선순위가 할당되며 가장 높은 우선순위를 가진 실행 가능한 프로세스가 다음에 수행한다.
　높은 우선순위의 프로세스가 무한히 실행되는 것을 막기 위해 스케줄러는 클록 인터럽트마다 현재 실행중인 프로세스의 우선순위를 낮출 수 있다. 만약 이러한 동작에의해 현재 수행중인 프로세스의 우선순위가 다음으로 가장 높은 프로세스의 우선순위보다 낮아지면 프로세스 교환이 발생한다. 다른 방식으로, 각 프로세스는 최대로 실행할 수 있는 할당 시간을 가진다. 이 할당 시간을 소비하면 다음으로 우선순위가 높은 프로세스에게 실행할 기회가 주어진다.
　우선순위는 프로세스에게 정적으로 또는 동적으로 할당될 수 있다.
　종종 프로세스들을 그룹으로 묶어 우선순위 클래스를 형성하고, 우선순위 클래스마다 우선순위를 할당하며 각 클래스 내에서는 라운드 로빈을 사용하면 편리하다. 다음은 네 개의 우선순위 크래스를 가진 시스템을 보여준다.

　여기서 스케줄링 알고리즘은 다음과 같다.

• 우선순위 클래스 4에 실행 가능한 프로세스가 있는 경우 각 프로세스는 라운드 로빈 형태로 한 번씩 할당 시간 동안 실행되며 낮은 우선순위 클래스로부터 방해 받지 않는다.
• 우선순위 클래스가 비어 있는 경우, 우선순위 클래스 3의 프로세스가 라운드 로빈 형태로 수행된다.
• 클래스 4와 3이 모두 비어 있으면 클래스 2가 라운드 로빈 형태로 수행된다.
• 다음으로 클래스 1이 수행된다.

　가끔 우선순위가 조정되지 않으면 낮은 클래스는 기아(starvation)가 발생하여 수행되지 않을 수도 있다.

다단계 큐
　우선순위 스케줄러를 최초로 도입했던 시스템 중 하나가 CTSS(Compatible Time Sharing System)이다. CTSS는 CPU-바운드 프로세스에게 할당 시간으로 작은 값이 아니라 큰 값을 주어야 더 효율적이다. 그러나 모든 프로세스에게 큰 할당 시간을 부여하면 응답시간이 저하된다. 이에대한 해결책으로 우선순위 클래스들을 설정하였다. 가장 높은 우선 순위 클래스는 한 단위(quantum)의 할당 시간동안 실행된다. 다음 우선순위 클래스는 두 단위의 할당 시간 동안 실행된다. 다음 우선순위 클래스의 프로세스는 네 단위의 할당 시간동안 실행된다. 프로세스가 할당된 시간을 모두 소비하면 한 단계 낮은 클래스로 이동한다.
　예를 들어 계산하는데 총 100개의 할당 시간이 필요한 프로세스를 생각해 보자.

• 처음 한 번의 할당 시간을 받고 스왑-아웃 된다. 다음에는 두 배의 할당 시간을 부여 받아 실행한 후 스왑-아웃된다. 계속해서 실행될 때마다 4, 8, 16, 32, 64 단위의 할당 시간을 받으며, 마지막에는 64 단위의 할당 시간 중 37 단위만 사용한 후 종료한다.
• 순수한 라운드 로빈 알고리즘으로는 100번의 스왑이 팔요했었는데 이제는 7번(초기 적재까지 포함하여)만 발생한다.
• 더욱이 프로세스는 점점 낮은 우선순위 클래스로 이동하므로 점점 덜 자주 수행되면서 다른 짧은 대화식 프로세스가 CPU를 차지할 수 있도록 한다.

최소프로세스순번
　배치 시스템에서 최단작업우선 정책은 항상 평균 응답 시간을 최소화 시키기 때문에 대화식 프로세스의 경우에도 사용될 수 있을 것이다. 유일한 문제는 실행 가능한 프로세스 중 어느 것이 실행 시간이 가장 짧은지 알아야 한다는 점이다. 한 가지 기법은 과거의 행동을 기반으로 추정하여 예상 실행 시간이 가장 짧은 프로세스를 실행하는 것이다.
　어떤 프로세스에서 명령 당 예상 시간을 $T_0$라고 가정하자. 그리고 다음 실행 시간이 $T_1$으로 측정되었다고 하자. 이제, $aT_0 + (1 - a)T_1$과 같이 이 두 수의 가중 합계를 구하여 예상치를 갱신할 수 있다. 적절한 $a$값을 선택하여 이전 수행 결과가 가중치에 미치는 영향을 빨리 감소시키거나 또는 이전 결과가 오랫동안 반영되도록 할 수 있다. $a=1/2$ 이면 예상치들은 다음과 같이 된다.

$T_0$,　$T_0/2 + T_1/2$,　$T_0/4 + T_1/4 + T_2/2$,　$T_0/8 + T_1/8 + T_2/4 + T_3/2$

　세 번 실행한 후 $T_0$가 새로운 실행 시간 예측에 미치는 영향은 1/8로 감소한다.

실시간 시스템에서 스케줄링

　실시간 시스템은 시간이 핵심 역할을 수행하는 시스템이다. 일반적으로 컴퓨터 외부에 있는 하나 이상의 물리적 장치가 컴퓨터에 자극을 주면 컴퓨터는 고정된 시간 안에 적절하게 그들에게 반응해야 한다. 예를 들어, 디스크 플레이어에 있는 컴퓨터는 드라이브에서 비트들을 가져와서 이를 매우 짧은 시간 간격안에 음악으로 변환해야 한다. 이러한 경우에 너무 늦게 도착하는 올바른 응답은, 응답을 전혀 하지 않은 것과 마찬가지로 매우 나쁠 수 있다. 　실시간 시스템은 일반적으로 마감시간이 절대적으로 만족되어야 하는 경성 실시간(hard real-time)가 바람직하지는 않지만, 때때로 마감시간을 지키지는 않아도 견딜 수 있는 연성 실시간(sotf real-time)으로 분류할 수 있다. 두 경우 모두, 프로그램을 행동이 예측 가능하고 미리 알려져 있는 여러 개의 프로세스들로 구성하여 실시간 성질을 성취한다. 이러한 프로세스들은 일반적으로 짧은 시간동안 활동하며 초 단위 이내에 수행을 마친다. 외부 이벤트가 검출되면 모든 마감시간이 만족되도록 프로세스를 스케줄 하는 것이 스케줄러의 책임이다.
　실시간 시스템이 응답해야 할 이벤트를 더 분류하면 일정한 시간 간격마다 발생하는 주기적(periodic)인 것과 예측할 수 없이 발생하는 비주기적(aperiodic)인 것이 있다. 한 시스템은 여러 개의 주기적인 이벤트들에 응답해야 한다. 각 이벤트 처리에 얼마나 많은 시간이 필요한 지에 따라 이들이 다 처리하는 것이 불가능 할 수도 있다. 다음 예제를 보자.
　m개의 이벤트가 존재하면 각 이벤트 $i$는 $P_i$의 주기로 발생하고 이 이벤트 처리에 $C_i$초의 CPU 시간이 필요하다면 시스템의 부하가 다음과 같을 때만 처리가 가능하다.

$\sum\limits_{i=1}^m \frac{C_i}{P_i} \le 1$

　이 기준을 충족하는 실시간 시스템은 “스케줄가능(schedulable)”이라 말할 수 있다. 다음 예제를 보자.
　100, 200, 500ms의 주기를 갖는 세 개의 주기적인 인벤트를 가진 연성 실시간 시스템이 있다. 이러한 이벤트들은 각각 50, 30, 100ms의 CPU 시간을 필요로 하며 $0.5 + 0.15 + 0.2 < 1$이므로 시스템은 “스케줄가능”이다. 만약 주기가 1초인 네 번째 이벤트가 추가되고 이벤트 처리에 150ms이내의 CPU 시간을 필요로 할 경우 이 시스템은 여전히 스케줄 가능 상태에 있다. 이러한 계산에서 문맥교환 비용이 무시할 정도로 매우 작다는 것을 잠재적으로 가정하고 있다.
　실시간 스케줄링 알고리즘은 정정 또는 동적이 될 수 있다. 정적인 경우 시스템이 실행을 시작하기 전에 스케줄 결정이 만들어 진다. 동적인 경우 스케줄 결정은 실행 중에 만들어 진다.

정책과 메커니즘

　지금까지 시스템의 모든 프로세스는 묵시적으로 서로 다른 사용자에게 속하며 서로 CPU를 놓고 경쟁한다고 가정했다. 종종 이것이 사실이기는 하지만 때떄로 하나의 프로세스는 자신이 관리하는 자식 프로세스를 가지기도 한다. 예를 들어 데이터베이스 관리 시스템 프로세스는 많은 자식을 가질 수 있고 각 자식 프로세스는 서로 다른 요청을 처리하거나 또는 각 자식 프로세스마다 특별한 기능을 담당한다. 중심 프로세스는 어느 자식이 가장 중요하고 어느 자식이 그렇지 않은 지에 대해 완벽하게 알고 있다. 지금까지 살펴본 모든 스케줄러는 스케줄 결정을 내릴 때 어떠한 사용자 프로세스의 입력도 받아들이지 않는다. 결과적으로, 스케줄러가 가장 좋은 선택을 하는 경우는 드물다.
　이 문제의 해결책은 스케줄링 정책(policy)과 스케줄링 메커니즘(mechanism)을 분리하는 것이다. 이것이 의미하는 것은 스케줄링 알고리즘은 몇 가지 방식으로 인자를 가지도록 만들어지며 사용자 프로세스가 이러한 인자를 선택하여 제공하는 것이다. 커널은 우선순위 알고리즘을 사용하지만 프로세스가 자식 프로세스의 우선순위를 설정, 변경할 수 있는 시스템 호출을 제공한다고 가정하자. 이렇게 하면, 비록 부모 자신이 스케줄링 하는 것은 아니지만, 부모는 자식이 어떻게 스케줄 될지에 대해 세밀하게 제어할 수 있다. 여기서 기법은 커널이 제공하고, 정책은 사용자 프로세스에의해 선택된다.

스레드 스케줄링

　여러 개의 프로세스들이 다수의 스레드를 가지고 있을 때 프로세스와 스레드라는 두 단계의 병렬성이 존재한다. 이러한 시스템에서 스케줄링은 사용자 레벨 스레드 또는 커널 레벨 스레드가 지원되는지에 따라 실질적으로 다르다.
　사용자 레벨 스레드를 먼저 고려하자. 커널은 스레드의 존재를 인식하지 못하므로 커널은 항상 하던 대로 프로세스 A를 선택하고 할당 시간만큼 A에서 CPU의 제어를 넘긴다. A 내부의 스레드 스케줄러는 어느 스레드를(예로 A1) 실행시킬지를 결정한다. 스레드를 다중프로그래밍 하기 위한 클록 인터럽트가 존재하지 않으므로 이 스레드는 자신이 원하는 만큼 실행할 수 있다. 이 스렏가 프로세스에게 할당된 할당 시간을 모두 소비하면 커널은 다른 프로세스를 선택하여 실행할 것이다. 프로세스 A가 다시 실행되면 스레드 A1은 다시 실행을 제개한다. 스레드는 다시 프로세스 A의 할당 시간을 모두 소비할 때까지 실행될 것이다.
　이제 프로세스 할당 시간이 50ms일 때 스레드의 작업은 5ms 걸려 스레드 A가 CPU-버스트 마다 해야 할 일이 별로 없는 경우를 고려해 보자. 결과적으로 스레드는 잠시 실행하고 CPU를 다시 스케줄러에게 반환한다. 결국 커널이 프로세스 A에서 B로 문맥교환 하기 전에 A의 스레드들은 A1, A2, A3, A1, A2, A3, A1, A2, A3, A1 순으로 실행될 것이다. 이러한 상황은 다음과 같다.

　이제 커널 레벨 스레드 경우를 보자. 여기서 커널은 어떤 스레드를 선택하여 실행한다. 커널은 스레드가 어느 프로세스에게 소속되어 있는지는 고려하지 않지만 커널이 원한다면 고려할 수는 있다. 스레드는 할당 시간을 부여 받고 이 시간을 초과하면 강제로 중단된다. 할당 시간이 50ms이고 스레드들이 5ms 이후에 대기한다면 특정 30ms 영역에서 스레드 수행 순서는 A1, B1, A2, B2, A3, B3이 될 수 있는데 이러한 순서는 동일한 인자를 갖는 사용자 레벨 스레드에서는 가능하지 않는 순서이다. 이러한 상황은 다음과 같다.

스레드

　전통적인 운영체제에서 각 프로세스는 주소 공간과 하나의 제어의 흐름(thread of control)을 가진다. 이것은 프로세스의 정의와 거의 같다. 그런데 하나의 주소 공간 내에서 주소 공간을 공유한다는 점을 제외하고 마치 별도의 프로세스인 것처럼 준 병렬적으로 수행하는 다수의 제어 흐름을 가지는 것이 바람직한 상황이 종종 있다.

고전적인 스레드 모델

　프로세스 모델(Process model)은 자원의 모음과 실행이라는 두 개의 서로 독립적인 개념에 기초를 두고 있다. 프로세스를 바라보는 한 가지 방식은 이것이 서로 관련된 자원을 한 군데 모으는 방법(resource grouping)이라는 것이다. 프로세스는 주소 공간을 가지고 있으며 이곳에는 프로그램 텍스트와 데이터, 그리고 기타 다른 자원들이 포함되어 있다. 이러한 자원으로는 열린 파일들, 자식 프로새스, 대기중인 알람 등이 있다. 이들을 프로세스 형태로 한 군데 모음으로써 더욱 쉽게 관리할 수 있다.
　프로세스가 가지는 다른 개념은 실행의 흐름(thread of executuin)이라는 것으로 보통 줄여서 스레드라 부른다. 스레드는 다음에 실행할 명령을 추적하는 프로그램 카운터를 가진다. 또한 현재 작업 변수를 저장하는 레지스터를 가진다. 뿐만 아니라 호출하였으나 아직 복귀하지 않은 프로시듀어마다 한 프레임씩 실행 히스토리를 담고있는 스택도 가지고 있다. 프로세스는 자원을 한 군데 모으기 위해 사용되며 스레드는 CPU에서 실행되도록 스케줄되는 개체이다.
스레드 모델(Thread model)은 프로세스 모델에 하나의 프로세스 환경에서 다수의 실행이 가능하도록 허용하는 것을 추가한 것이며, 이러한 다수의 실행은 대체로 서로에 대한 독립성을 가지고 있어야 한다. 스레드들은 프로세스의 속성을 어느 정도 가지고 있기 때문에 이들은 때떄로 경량 프로세스(lightweight process)라고 부른다. 다중스레딩(multithreading)은 다수의 스레드가 하나의 프로세스에서 수행되는 것이 가능한 상황을 기술하기 위해 사용된다.

　위 그림의 (a)에서 세 개의 전통적인 프로세스를 볼 수 있다. 각 프로세스는 자신의 주소 공간과 실행의 흐름을 한 개씩 가진다. 이와 대조적으로 (b)에서는 세 개의 실행의 흐름을 가진 하나의 프로세스가 있다. 비록 두 경우 모두 세 개의 스레드가 있지만 (a)의 경우 각각은 서로 다른 주소 공간에서 동작하는 반면 (b)에서는 세 스레드 모두 동일한 주소 공간을 공유한다.
　다중스레드 프로세스가 하나의 CPU를 가진 시스템에서 실행될 때 스레드는 순서대로 수행된다. 다수의 프로세스 사이를 전환함으로써 시스템은 개별적인 순차 프로세스들이 병렬로 수행다는 것과 같은 환상을 제공한다. 다중스레딩도 동일한 방식으로 동작한다. CPU는 빠르게 스레드 사이를 전환하여 스레드가 실제보다 더 느린 CPU에서 병렬로 수행되는 것과 같은 환상을 제공한다. 세 개의 계산 위주 스레드가 실행되면 스레드들은 실제 CPU보다 1/3정도 느리게 수행되는 CPU에서 병렬로 수행되는 것처럼 보인다.
　한 프로세스 내부의 서로 다른 스레드들은 서로 다른 프로세스들인 만큼 독립적이지 않다. 모든 스레드들은 완전히 동일한 주소 공간을 가지며 이는 그들이 동일한 전역 변수를 공유함을 의미한다.
　스레드들 간에는 어떠한 보호도 제공되지 않는데 그 이유는 불가능하고 불필요하기 때문이다. 하나의 프로세스는 한 명의 사용자에게 소속되어 있으며 이 사용자는 서로 싸우기 위해서가 아니라 협력하기 위해 다수의 스레드를 생성한 것이다. 따라서 (a)의 구조는 세 개의 프로세스가 본질적으로 서로 무관한 경우에 사용되며 (b)의 구조는 세 개의 스레드가 실질적으로 동일한 작업에 참여하고 서로 적극적으로 밀접하게 협동하는 경우에 적당하다.

　위에서 첫 번째 열에 있는 항목들(Per process items)은 한 프로세스 내 모든 스레드가 공유하는 항목들이 나열되어 있다. 이 항목들은 스레드의 속성이 아니라 프로세스의 속성이다. 두 번째 열은 각 스레드들이 개별적으로 보유하는 항목들이 나열되어 있다. 스레드 개념으로 얻고자 하는 것은 어떤 작업을 수행하기 위해 밀접하게 연관된 다수의 실행의 흐름이 자원의 집합을 공유하는 능력이다.
　전통적인 프로세스(하나의 스레드를 가진 프로세스)와 마찬가지로 스레드는 실행(running), 대기(블록, blocked), 준비(ready), 또는 종료(terminate)와 같은 상태 중 하나를 가진다. 실행중인 스레드는 현재 CPU를 점유하여 활동 중이다. 대기 중인 스레드는 어떤 이벤트가 발생하여 대기 상태에서 풀릴 때까지 기다리는 중이다.
　예를 들면 스레드가 시스템 호출을 불러 키보드에서 데이터를 입력 받고자 하면 이 스레드는 입력이 일어날 때까지 대기한다. 스레드는 외부 이벤트가 발생하거나 다른 스레드가 자신을 깨워주면 기다리는 것을 중단할 수 있다. 준비 상태의 스레드는 다음 번 실행 대상으로 스케줄 될 수 있으며 자신의 순서가 되자마자 실행될 것이다.

　위에 표시된 것처럼 각각의 스레드는 자신만의 스택을 가지고 있음을 알아야 한다. 각 스레드의 스택에는 호출되었으나 아직 복귀하지 않은 프로시듀어 당 하나의 프레임이 존재한다. 이 프레임은 프로시듀어의 지역 변수들과 프로시듀어 수행이 끝날 때 돌아갈 복귀 주소를 가지고 있다. 일반적으로 각 스레드는 서로 다른 프로시듀어들을 호출하며 따라서 서로 다른 실행 히스토리를 가진다. 이 점은 각 스레드들이 각자 자신의 스택을 가져야 하는 이유가 된다.
　스레드와 관련있는 라이브러리 프로시듀어는 다음과 같다.

• thread_create
  • 일반적으로 thread_create의 인자 중 하나는 새로운 스레드로 실행될 프로시듀어의 이름이다.
  • 다중스레딩이 지원되는 경우 프로세스는 일반적으로 하나의 스레드를 가진 채 시작한다. 그리고 이 스레드는 thread_create를 호출하여 새로운 스레드를 생성할 수 있다.
  • 자동적으로 새로운 스레드는 생성한 스레드와 동일한 주소 공간에서 실행되므로 새로운 스레드의 주소 공간을 지정하는 것은 불필요하다.
  • 일반적으로 생성한 스레드는 새로운 스레드를 지목하는 스레드 식별자(thread identifier)를 받는다.
• thread_exit
  • 스레드가 작업을 완료하면 thread_exit이라는 라이브러리 프로시듀어를 호출하여 종료할 수 있다. 그러면 스레드는 사라지고 더 이상 스케줄 되지 않는다.
• thread_wait
  • Blocks the calling thread until a specific thread has exited
• thread_yield
  • 스레드가 자발적으로 CPU를 포기하여 다른 스레드가 실행될 수 있도록 한다.
  • 프로세스들 간에 다중프로그래밍을 강제하는 클록 인터럽트가 스레드들 간에는 존재하지 않기 때문에 이 시스템 호출은 중요하다.

　종종 스레드가 유용하지만 이것은 또한 프로그래밍 모델에 상당한 수준의 복잡성을 야기한다.

스레드의 사용

　왜 프로세스 안에서 또 다른 프로세스 형태를 사용하려고 하는 걸까? 스레드(thread)라 불리는 미니 프로세스를 사용해야 하는 여러 가지 이유가 있다. 스레드를 사용해야 하는 주된 이유는 많은 응용에서 다수의 동작이 동시에 진행된다는 것이다. 이러한 응용을 준 병렬로 수행하는 다수의 순차적인 스레드로 분해하면 프로그래밍 모델이 훨씬 단순해진다.
　스레드를 사용해야 한다는 두 번째 이유는 이들이 프로세스보다 더 경량적이어서 프로세스보다 생성과 제거가 쉽다는 점이다.
　스레드를 사용해야 하는 세 번째 이유는 성능과 관련된 주장이다. 모든 스레드가 CPU-바운드라면 스레드를 사용할 때 성능 이득은 거의 없다. 그러나 많은 연산과 많은 I/O가 동시에 존재하는 경우 스레드를 사용하면 이러한 동작들을 겹치도록 수행할 수 있어 응용의 속도를 향상시킬 수 있다.
　마지막으로 스레드는 실질적인 병렬성을 제공하는 다수의 CPU를 가진 시스템에서 유용하다.
　예제로 워드 프로세서를 살펴보자. 여기서 세 개의 스레드를 도입하자.

• Interactive thread: 사용자와 대화한다.
• Reformatting thread: 후위에서 포멧팅을 담당한다.
  • 페이지 1에서 문장이 제거되자 마자 대화 스레드는 재포맷 스레드에게 전체 책을 다시 포멧하도록 지시한다. 그 동안 대화 스레드는 키보드와 마우스 입력을 받아들이면서 일을 계속하여 다른 스레드가 후위에서 열심히 작업하는 동안 대화 스레드는 페이지 1의 스크롤과 같은 간단한 명령에 응답한다.
• Disk-backup thread: 몇 분마다 자동적으로 파일을 디스크에 저장하는 기능을 가지고 있다.
  • 다른 두 스레드를 방해하지 않고 디스크에 저장하는 기능을 담당한다.

　위 예에서 첫 번째 스레드는 단지 사용자와 대화한다. 두 번째 스레드는 통보되는 경우 문서를 다시 포맷한다. 세 번째 스레드는 주기적으로 RAM의 내용을 디스크에 기록한다. 만약 프로그램이 하나의 스레드로 구성되었다면 디스크 백업이 시작되면 백업이 끝날 때까지 키보드나 마우스로 입력된 명령은 무시될 것이다. 사용자는 이러한 무응답을 확실히 인식할 것이다.
　스레드들은 모두 공통의 한 문서에서 동작해야 하므로 여기서 세 개의 서로 다른 프로세스로 구성하는 것은 제대로 동작하지 않는 것이 확실하다. 세 개의 프로세스가 아니라 세 개의 스레드로 구성해야 이들이 모두 메모리를 공유하여 편집중인 문서에 접근할 수 있다.
　웹 서버를 구성하는 한 가지 방법은 다음과 같다.

　여기서 디스패처라 불리는 스레드는 네트워크로부터 도착하는 작업 요청을 읽어 들인다. 이 요청을 검사한 후 스레드는 한가한(대기 상태의) 작업 스레드를 선정하고 각 스레드마다 지정된 위치의 워드에 메시지의 포인터를 기록함으로써 요청을 이 스레드에게 전달한다. 디스패처는 이제 잠들어 있던 작업 스레드를 꺠워 이 스레드가 대기 상태에서 준비 상태가 되도록 한다.
　작업 스레드가 꺠어나면 이 스레드는 먼저 요청이 모든 스레드가 접근할 수 있는 웹 페이지 캐시에서 만족될 수 있는지를 검사한다. 만약 그렇지 않으면 스레드는 디스크로부터 페이지를 가져오기 위해 읽기 연산을 시작하고 디스크 동작이 완료될 때까지 대기 상태가 된다. 이 스레드가 디스크 연산을 대기하는 동안 다른 스레드가 실행되는데 이 스레드는 아마 새로운 요청을 받아들이기 위한 디스패처가 되거나 준비 상태의 다른 작업 스레드가 실행될 것이다.
　이 모델은 서버 프로그램을 순차적인 스레드들의 집합으로 작성할 수 있도록 되어있다. 디스패어 프로그램은 작업 스레드를 선정하고 이 작업 스레드에게 요청을 전달하는 무한 루프로 구성된다. 각 작업 스레드 코드는 디스패처로부터 요청을 전달 받고 웹 캐시에서 해당 페이지가 존재하는지 검사하는 무한 루프로 구성된다. 만약 존재하면 페이지를 클라이언트에게 전달하고 작업 스레드는 새로운 요청을 기다리며 대기한다. 존재하지 않으면 디스크에서 페이지를 가져와서 이를 클라이언트에게 전달하고 새로운 요청을 기라리며 대기한다.
　이러한 코드의 개요는 다음과 같다.

　위 코드에서 TRUE는 상수 1로 가정한다. 또한 buf와 page는 각각 작업 요청과 웹 페이지를 저장하기 위한 구조체이다.

사용자 공간에서 스레드의 구현

　스레드 패키지를 구현하는 주요 방법으로는 두 가지가 있으며 하나는 사용자 공간에서, 그리고 다른 하나는 커널 내에서 구현하는 것이다.
　첫 번째 방법은 스레드 패키지 전체를 사용자 공간에 위치시키는 것이다. 커널은 이들에 대해 전혀 알지 못한다. 커널이 아는 것은 단지 자신이 평범한 단일 스레드 프로세스를 수행하고 있다는 점이다. 다음과 같은 모양으로 구현할 수 있다.

　사용자 레벨 스레드 패키지에서 장점은 다음과 같다.

• 사용자 레벨 스레드 패키지는 스레드를 전혀 지원하지 않는 운영체제에도 구현될 수 있다.
• 스레드 스케줄링을 매우 빠르게 한다.
  • 스레드 상태를 저장하는 프로시듀어와 스케줄러는 모두 프로시듀어와 스케줄러는 모두 프로세스 내 지역 프로시듀어이며 이들을 호출하는 것은 커널 호출보다 훨씬 효율적이다.
• 각 프로세스마다 자신에게 특화된 스케줄링 알고리즘을 가질 수 있도록 한다.
• 사용자 레벨 스레드는 확장성이 높다
  • 커널 스레드의 경우 커널 내부에 거의 고정된 양의 테이블 공간과 스택 공간을 필요로 한다.
  • 많은 수의 스레드가 존재하면 이러한 공간이 문제가 된다.

　이렇게 좋은 성능에도 불구하고 사용자 레벨 스레드 패키지는 몇 가지 중대한 문제점을 가지고 있다.

• 어떻게 블록킹 시스템 호출을 구현하는가 하는 문제
  • 블록킹 시스템 호출을 사용하면 전체 스레드가 중단된다.
    • 스레드가 실제로 시스템 호출을 부르면 모든 스레드들이 블록될 수 있기 때문에 스레드가 실제로 시스템 호출을 부르는 것은 받아들일 수 없다.
    • 스레드를 사용하는 중요 목적 중 하나가 이들을 각각이 블록킹 호출을 부르지만 한 스레드의 중단이 다른 스레드에 영향을 미치치 않도록 하는 것인데 이러한 목적을 달성하는 것이 어려울 수 있다.
  • 시스템 호출 주위에서 필요한 검사를 수행하는 코드를 자켓(jacket) 또는 랩퍼(wrapper)라 부른다.
• 만약 스레드가 실행을 시작하면 이 스레드가 자발적으로 CPU를 양보할 때까지 다른 스레드는 시행하지 못할 수도 있다
  • 무한히 실행하는 스레드 문제를 해결하기 위해 가능한 해법은 런타임 시스템으로 하여금 제어를 획득하기 위해 초당 한 번씩 클록 시그널을 받도록 요청하는 것이지만 이 역시 조잡하고 번잡한 프로그램이 된다.
  • 전체적으로 오버헤드가 상당할 것이고 시스템이 사용하는 클록과 간섭이 발생할 수 있다.

커널 내부에서 스레드 구현

　커널이 스레드에 대해서 알고 스레드를 관리하도록 하는 기법에 대해 알아보자. 이 경우 다음과 같이 프로세스마다 런타임 시스템이 팔요하지 않다. 또한 각 프로세스마다 스레드 테이블이 존재하지 않는다. 대신 커널은 시스템 내부의 모든 스레드를 관리하기 위하여 스레드 테이블을 가지고 있다. 스레드가 다른 스레드 생성을 요구하거나 또는 기존의 제거를 요구하면 이들은 커널 호출을 부르며 다시 커널 스레드 테이블을 변경하여 생성과 삭제를 수행한다.

　커널의 스레드 테이블은 각 스레드의 레지스터, 상태, 그리고 기타 정보를 가진다. 이러한 정보는 사용자 레벨 스레드의 경우와 동일하지만 이제는 사용가 공간이 아니라 커널에 유지된다. 커널은 프로세스들을 관리하기 위해 전통적인 프로세스 테이블도 가지고 있다.
　커널 스레드는 새로운 논블록킹 시스템 호출을 필요로 하지 않는다. 커널 스레드의 주 단점은 시스템 호출 비용이 크다는 것이며 따라서 스레드 연산이 빈번하다면 훨씬 많은 오버헤드가 발생한다.

단일 스레드 코드를 다중스레드 형태로 만들기

　기존의 많은 프로그램은 단일 스레드 프로세스 형태로 작성되었다. 이들을 다중스레드형태로 바꾸는 것은 보기보다 훨씬 요령이 필요하다. 다음 몇가지 위험에 대해 살펴보자.
　먼저 스레드의 코드는 일반적인 프로세스와 마찬가지로 다수의 프로시듀어로 구성된다. 이들은 지역 변수, 전역 변수 그리고 인자들을 가질 수 있다. 지역 변수와 인자는 문제를 일으키지는 않지만 스레드에게는 전역이면서 전체 프로그램 입장에서는 전역이 아닌 변수가 문제가 될 수 있다.

　위와 같은 문제를 해결하기 위해 한 가지는 모든 전역 변수를 모두 금지하는 것이다. 그러나 이는 이상적으로는 가능하지만 많은 기존 소프트웨어와 마찰을 일으킨다. 또 다른 방법은 다음과 같이 각 스레드에게 자신만의 개별 전역 변수를 할당하는 것이다.