프로세스 스케줄링(2)

1. Context Switching

interrupt가 발생하게 되면 운영체제는 프로세스에게 할당됐던 CPU를 가져와 kernel routine을 실행할 수 있도록 해야한다. 이 말은 프로세스가 일시적으로 중단됐다가 interrupt 처리가 끝난 후 프로세스가 작업했던 위치로 돌아와야 한다는 말이다. 이 때 프로세스가 작업했던 위치의 정보를 Context라고 하며 Context는 PCB에 포함된다. Context는 CPU register 값, 프로세스 상태(state), 메모리 관리 정보 등을 포함한다. (그림 1)

[그림 1] Process Control Block

CPU를 다른 프로세스로 교환하려면 현재 프로세스의 Context를 저장하고 다른 프로세스의 Context를 복구하는 작업이 필요하다. 이 작업을 Context Switch라고 부른다. Context Switch가 일어나면 위에서 설명한대로 Context를 PCB에 저장하고 새로운 프로세스의 Context를 복구하는 작업을 한다. 이 때 CPU가 아무일도 못하므로 이 시간은 오버헤드이다. (그림 2)

Context Switch 시간은 하드웨어에 따라 크게 달라지고 (예를들어 레지스터가 많은 CPU는 일정 프로세스 개수 아래에선 단순히 레지스터에 대한 포인터만 변경하면 된다.) 운영체제가 복잡할수록 더 많은 작업을 해야하므로 오래걸린다.

[그림 2] CPU switching

2. Process Creation

프로세스는 실행 도중에 프로세스 생성 시스템 호출을 통해 새로운 프로세스를 생성할 수 있다. 이 때 생성하는 프로세스를 부모 프로세스, 새로운 프로세스를 자식 프로세스라고 부른다. 새로 만들어진 프로세스도 자식 프로세스를 만들 수 있는데 그 결과 프로세스 트리를 형성한다.

대부분의 운영체제는 프로세스를 식별할 때 process id(pid)로 구분하는데 보통 정수값이다. 예를 들어 아래 그림 3은 Solaris 운영체제의 전형적인 프로세스 트리를 보여준다.

[그림 3] Solaris process tree

보통 프로세스가 자신의 task를 수행하려면 자원들(CPU, 메모리, 파일, 입출력장치)이 필요하다. 프로세스가 subprocess(자식 프로세스)를 생성하면 운영체제로부터 직접 자원을 받던가 부모 프로세스 자원을 나눠갖는다. 이 때 초기화 자료를 부모 프로세스가 자식 프로세스로 넘겨줄 수도 있다. 예를 들어 img.jpg 파일을 넘길 때 어떤 프로세스는 파일 이름만 넘겨 자식 프로세스가 사용하게 할수도 있고, 어떤 운영체제는 그 둘을 두 프로세스에서 동시에 열어 공유하도록 할수도 있다.

프로세스가 새로운 프로세스를 생성할 때 실행과 관련하여 두 가지 가능성이 있다.

• 부모 프로세스와 자식 프로세스가 병렬로 실행
  
  
• 부모 프로세스가 자식 프로세스가 끝날때까지 기다림

그리고 자식 프로세스는 주소 공간 측면에서 두 가지 가능성이 있다.

• 자식 프로세스는 부모 프로세스의 복사본이다. (자식 프로세스가 부모 프로세스와 똑같은 프로그램과 데이터를 가진다.)
  
  
• 자식 프로세스가 자신에게 적재될 새로운 프로그램을 갖고 있다.

예를 들어 UNIX의 fork() 시스템 호출은 부모 프로세스의 복사본을 만드는데, fork함수의 리턴 값이 0이 아니면 부모 프로세스임을 알 수 있다. 만약 다른 프로그램을 실행하고 싶으면 fork()호출 후에 exec() 함수를 호출하면 된다. 만약 자식 프로세스가 끝날 때까지 기다린다면 wait()을 호출하면 된다. 그럼 ready queue에서 제거되고 자식 프로세스를 기다린다. 아래와 같이 C프로그램을 작성할 수 있다.

#include <stdio.h>

int main(int argc, char* argv[])
{
    int pid;

    /* 새 프로세스를 생성한다.(fork) */
    pid = fork();

    if(pid < 0) { // 오류
        fprintf(stderr, "Fork Failed");
        return 1;    
    }
    else if(pid == 0) { // 자식 프로세스
        /* 자식 프로세스를 새로운 프로그램으로 바꿈 */
        execlp("/bin/ls", "ls", NULL);
    }
    else { // 부모 프로세스
        /* 자식 프로세스가 완료되기를 기다림 */
        wait(NULL);
        printf("Child Complete");
    }
    return 0;
}

위의 프로세스 흐름이 아래 그림 4에 나타나있다.

[그림 4] 프로세스 생성 및 흐름

UNIX와 다르게 Windows C로 작성하면 fork 대신 CreateProcess 함수를 사용해서 자식 프로세스를 생성해야한다. fork에 비해 매개변수도 10개로 아주 많고, fork는 자식 프로세스 내부에서 exec함수로 새로운 프로그램으로 덮어씌우는데, CreateProcess에선 매개변수로 프로그램 경로를 받아 새로운 프로그램을 적재한다. wait도 Windows C에선 WaitForSingleObject를 호출한다. 다른 점은 자식 프로세스 핸들을 넘겨받고서 기다린다는 점이다.

코드는 생략하므로 자세히 알고싶으면 아래 참조 링크를 확인

3. Process Termination

프로세스는 종료를 위해 exit() 시스템 호출을 사용해야 한다. 이 때 프로세스는 부모 프로세스에게 wait 시스템 호출을 통해 상태값(보통 정수값)을 반환할 수 있다. 종료 시 모든 자원은 운영체제로 반환된다.

프로세스가 다른 프로세스를 종료시킬 수 있다. 보통 부모 프로세스가 자식 프로세스를 종료할 수 있도록 돼있는데, 이를 위해서 자식 프로세스를 생성할 때 자식 프로세스의 identity가 부모 프로세스에게 전달된다.

부모 프로세스가 자식 프로세스를 종료하는 경우 다음과 같은 이유 때문에 종료할 수 있다.

• 자식 프로세스가 자신에게 할당된 자원을 초과하여 사용할 때. 이 때 부모 프로세스가 자식 프로세스들의 상태를 검사할 수 있는 수단이 있어야 한다.
  
  
• 자식 프로세스에게 할당된 task가 더 이상 필요 없을 때
  
  
• 부모 프로세스가 exit한 이후에 운영체제가 자식 프로세스도 같이 종료할 것을 요구할 때 (VMS를 포함한 몇몇 프로세스에서 이렇다. 이것을 cascading termination라고 부르고 운영체제가 수행한다.)

4. Interprocess Communication

다른 프로세스들에게 영향을 받지 않는 프로세스는 독립적인 프로세스(Independent Process)라고 하며, 어떤 이유에서 다른 프로세스의 영향을 받으면 상호 협력적인 프로세스(Cooperating Process)라고 한다.

다른 프로세스와 협력을 하는 데는 아래와 같은 몇 가지 이유가 있다.

• information sharing: 여러 사용자가 동일한 정보(공유 파일 등)에 흥미를 가질 수 있으므로 그러한 정보를 병행적으로 접근할 수 있도록 환경을 제공해야 한다.
  
  
• computation speedup: 특정 task의 계산을 빠르게 하고 싶으면 그것을 subtask로 나누어 병렬로 수행되게 할 수 있다. 이 것은 여러개의 CPU 또는 I/O 채널 등 복수 개의 processing element가 있어야만 수행될 수 있다.
  
  
• modularity: 시스템 기능을 별도의 프로세스들 또는 스레드들로 나누어 모듈형 시스템을 구성해야 할수도 있다.
  
  
• convenience: 개별 사용자들이 많은 task를 동시에 수행할 수도 있다. 이 때 병렬로 처리되도록 환경을 제공해야한다.

Cooperating process들은 정보를 교환할 수 있는 프로세스간 통신(interprocess communication, IPC) 기법을 필요로 한다. 이 기법은 shared memory, message passing 이렇게 두 가지가 있다.
shared memory는 프로세스들에 의해 공유되는 메모리 영역이 구축되고, 그 영역에 데이터를 읽고 씀으로써 정보를 교환한다. message passing은 프로세스들 사이에 교환되는 메시지를 통해 정보를 교환한다. 아래 그림 5에 기법이 어떻게 구성되는지 나와있다.

[그림 5] 통신 모델. (a) message passing (b) shared memory

message passing은 충돌을 회피할 필요가 없기 때문에 적은 양의 데이터를 교환할 때 유용하고 구현이 쉽다. shared memory는 자원 사용 시 충돌 문제가 있지만 속도가 빠르고 편이를 제공한다. message passing은 system call을 통해 kernel을 거쳐야하므로 시간을 좀 더 소비한다. shared memory는 공유 메모리를 구축할 때만 system call을 사용한다.

5. Shared Memory System

공유 메모리를 사용하는 프로세스들은 공유 메모리를 구축해야 하며, 이 메모리는 공유 메모리 세그먼트를 생성하는 프로세스의 주소 공간에 위치한다. 다른 프로세스들은 이 세그먼트를 자신의 주소공간에 추가해야만 통신할 수 있다. 그 후에 프로세스는 이 메모리를 읽고 씀으로써 정보를 교환한다. 이 때 프로세스들이 동시에 동일한 위치에 쓰지 않는다는 것을 보장해야 한다.

보통 producer-consumer을 동기화하는 일반적인 패러다임으로 생각한다. producer는 버퍼에 채우고 consumer는 버퍼의 내용을 소비하는데, 이 때 동시에 접근해서는 안되고 버퍼가 꽉 차거나 비었을 때를 고려해야 한다.
아래 코드와 같이 공유 메모리에 유한 버퍼(bounded buffer)가 존재한다고 가정하자.

#define BUFFER_SIZE 10

typedef struct {
    ...
} item;

item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;

in은 버퍼내에서 다음으로 비어있는 위치, out은 버퍼 내에서 첫 번째에 차있는 위치를 가리킨다.

in == out; 일 때 버퍼는 비어 있고, ((in + 1) % BUFFER_SIZE) == out;이면 버퍼는 가득 차 있다. 아래 코드와 같이 producer와 consumer 코드를 작성할 수 있다.

생성자

item nextProduced;

while(true) {
    /* produce an item in nextProduced */
    while(((in + 1) % BUFFER_SIZE) == out); // wait

    buffer[in] = nextProduced;
    in = (in + 1) % BUFFER_SIZE;
}

소비자

item nextConsumed;

while(true) {
    while(in == out); // wait

    /* consume the item in nextConsumed */
    nextConsumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
}

여기엔 동기화가 적용이 안됐는데 producer와 consumer가 버퍼에 동시에 접근하는 경우 문제가 생길 수 있다. 이 것은 나중에 다룬다.

6. Message-Passing System

shared memory와 같은 효과를 낼 수 있는 다른 방법은 운영체제가 messaging-passing 설비를 구축하고 프로세스간 통신 수단을 제공해 주는 것이다. messaging-passing 방식은 통신하는 프로세스들이 서로 다른 컴퓨터에서 네트워크로 연결된 분산 환경일 때 특히 유용하다.

messaging-passing system은 최소한 send, receive 연산을 제공해야 한다. messaging-passing system을 고려할 때 고려해야 하는 세 가지 사항이 있다.

• direct or indirect communication (naming)
  
  
• synchronous or asynchronous communication
  
  
• automatic or explicit buffering

6.1 Naming

통신을 원하는 프로세스들은 서로를 가리킬 수 있는 방법이 있어야 한다. 그들은 direct 또는 indirect communication을 사용할 수 있다.

direct communication에선 send, receive 연산은 다음과 같이 정의된다.

• send(P, message): 프로세스 P에게 메시지 전달
  
  
• receive(Q, message): 프로세스 Q로부터 메시지를 수신

그리고 다음과 같은 특성을 가진다.

• 통신을 원하는 프로세스 쌍 사이에 연결이 자동으로 구축된다. 프로세스들은 통신하기 위해 서로의 identity만 알면 된다.
  
  
• 연결은 정확히 두 프로세스 사이에만 연관된다.
  
  
• 통신하는 프로세스들의 각 쌍 사이에는 정확히 하나의 연결만 존재해야 한다.

위 기법은 symmetric하지만 asymmetric의 경우 수신자는 송신자의 identity를 제시할 필요가 없다. asymmetric의 경우 send, receive 연산은 아래와 같이 정의된다.

• send(P, message): 메시지를 프로세스 P에 전송한다.
  
  
• receive(id, message): 임의의 프로세스로부터 메시지를 수신한다. 변수 id는 통신을 발생시킨 프로세스의 이름으로 설정된다.

symmetric이든 asymmetric이든 direct communication의 단점은 프로세스를 정확히 지정함으로써 모듈화를 제한한다는 것이다.

indirect communication에서 메시지들은 mailbox 또는 port로 송신되고, 그것으로부터 수신된다. mailbox는 고유의 식별자를 가지고 있고 두 프로세스들이 공유 mailbox를 가지고 있어야 통신할 수 있다. send, receive 연산은 아래와 같이 정의된다.

• send(A, message): 메시지를 mailbox A로 송신한다.
  
  
• receive(A, message): 메시지를 mailbox A로부터 수신한다.

그리고 다음과 같은 특성을 가진다.

• 한 쌍의 프로세스 사이의 연결은 공유 mailbox를 가질 때만 구축된다.
  
  
• 여러 개의 프로세스가 하나의 mailbox를 공유할 수 있다.
  
  
• 통신하고 있는 각 프로세스 사이에는 다수의 서로 다른 연결이 존재할 수 있고, 각 연결마다 하나의 메일박스가 할당된다.
      
  
• 한 순간에 하나의 프로세스가 mailbox에 대해서 receive 연산을 수행할 수 있다. 어떤 프로세스가 수신할지는 시스템이 알고리즘(예를들면 Round-Robin)으로 결정한다.
  
  
• 운영체제는 mailbox가 닫힐 때 mailbox에서 메시지를 송신하는 모든 프로세스에게 통보해야 한다.

6.2 Synchronization

메시지 송/수신은 blocking 또는 non-blocking이다. 나중에 자세히 알아본다.

6.3 Buffering

통신이 direct든 indirect든 프로세스 간에 교환되는 메시지는 임시 queue에 들어 있다. 이 queue를 구현하는 방식은 세 가지가 있다.

• Zero Capacity: queue의 최대 길이가 0이다. sender는 receiver가 메시지를 수신할 때까지 기다려야 한다.
  
  
• Bounded Capacity: queue가 유한한 길이를 가진다. queue가 꽉차면 sender는 기다려야 하고, queue가 비어있으면 receiver가 기다려야 한다.
  
  
• Unbounded Capacity: queue가 무한한 길이를 가진다. sender는 blocking 될 일이 없다. receiver만 queue가 비어있을 때 기다려야 한다.

7. Communications in Client-Server Systems

클라이언트-서버 통신 모델에는 세가지가 있다. Socket, RPC(Remote Procedure Calls), Pipe. 뭐가 있는지만 알고 책이나 검색을 통해 자세히 보도록 한다.

• Socket: endpoint 간 통신. Message-Passing과 비슷하지만 서로 다른 기계에서 통신할 수 있다. 네트워크에 대한 지식이 있어야 한다. 연결기반인 TCP와 비연결기반인 UDP가 있다.
  
  
• RPC: 분산시스템에서 많이 사용된다. 분산시스템을 사용하게 될 때 자세히 살펴보자.
  
  
•  Pipe: 프로세스 간 통신에서 자주 사용하는 기법이다. 보통 파일을 읽고 쓰는 것과 같이 read, write system call을 통해 접근할 수 있다. anonymous pipe, named pipe 두 가지가 있는데 프로세스 간 통신을 해야할 때 살펴보자.

* 참조

https://www2.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/3_Processes.html