Monitor는 공유 데이터에 대한 접근은 오직 Monitor 안에 정의된 함수를 통해서만 접근이 가능하도록 하고, Monitor 안에서 active 하게 실행되는 프로세스는 하나로 제한한다. 따라서 프로그래머는 lock을 걸 필요 없이 Monitor 안에 있는 코드로 데이터에 접근하도록 하면 알아서 동기화가 된다.

목차

1. Semaphore
   1. Deadlock and Starvation
   2. Classical Problems of Synchronization : Semaphore
      1. Bounded-Buffer Problem (Producer-Consumer Problem)
      2. Readers-Writers Problem
      3. Dining-Philosophers Problem
   3. Semaphore의 문제점
2. Monitor
   1. Classical Problems of Synchronization : Monitor
      1. Bounded-Buffer Problem (Producer-Consumer Problem)
      2. Dining-Philosophers Problem

이전 글에서는 프로세스 동기화의 문제점과 이 문제를 해결하기 위한 초기 알고리즘 3가지를 알아보았다.

Synchronization Hardware는 앞서 나온 알고리즘들의 한계점을 보안해 준다.

이제는 좀 더 추상적인 동기화 문제 해결 방안 두 가지를 알아본다.

바로 세마포어 (Semaphore)와 모니터 (Monitor)이다.

이 방안들은 프로그래머로 하여금 더욱 쉽고 효율적으로 문제를 해결할 수 있도록 도와준다.

Semaphore

➳ 이전 글에서 나온 방식들을 추상화시킨다.

➳ Semaphore S

    • integer variable

    • 아래 두 가지 atomic 연산에 의해서만 접근이 가능하다.

P 연산은 자원을 획득하는 과정이고, V 연산은 자원을 반납하는 과정이다.

예를 들어 Semaphore 5라면 자원이 5라는 의미이다. 만약 프로세스 5개가 동시에 P 연산을 하면 모든 자원을 쓰고 있게 된다. 다른 프로세스가 자원을 획득하고 싶어도 자원의 여분이 없다면 기다려야 한다. 자원의 사용은 P 연산과 V 연산 사이에서 이루어진다. 자원을 다 사용했다면 V 연산을 통해 자원을 내놓게 된다. S는 자원을 count 한다고 볼 수도 있다.

Critical Section of n Processes

mutex : mutual exclusion의 줄임말

여기에서도 쓸데없이 while문을 도는 busy-wait 문제가 있다. 이는 어떻게 해결하면 좋을까 ?

Block / Wakeup Implementation

value 값과 줄을 세우는 list 구조를 둔다. 만약 Semaphore 여분이 없어 기다려야 한다면 변수 L에 대해서 프로세스를 block 시키고, 줄을 세워서 기다리게 한다. 이는 busy-wait 문제를 해결해 준다. busy-wait는 spin lock이라고도 부른다. 따라서 block/wakeup 방식을 sleep lock이라고 부르기도 한다.

이제 Block/Wakeup 방식으로 Semaphore 연산을 정의해 보자 !

P 연산은 자원을 획득하므로 value 값에 1을 빼준다.

S.value가 음수라면 S.L (Semaphore list)에 Block 시킨다.

V 연산은 자원을 내놓으므로 value 값에 1을 더한다.

S.value가 0 이하라면 S.L에서 하나를 꺼내 깨워준다.

Which is better ?

" busy-wait  VS block/wakeup "

일반적으로는 block/wakeup이 훨씬 낫다. 하지만 block 하고  wakeup 하는 것도 어떻게 보면 overhead라고 볼 수도 있다.

➳ block/wakeup overhead VS critical section 길이로 판단한다.

    • critical section의 길이가 긴 경우 block/wakeup이 적당하다.

    • critical section의 길이가 매우 짧은 경우 block/wakeup overhead가 busy-wait overhead보다 더 커질 수가 있다.

    • 일반적으로는 block/wakeup 방식이 더 좋다.

💡

사실 길이보다는 얼마나 경쟁이 치열한가로 이해하는 것이 올바르다.

경쟁이 치열하다면 block/wakeup이, 별로 치열하지 않다면 busy-wait이 더 좋을 수가 있다는 것이다.

Two Types of Semaphores

Counting semaphore

➳ 도메인이 0 이상인 임의의 정수값

➳ 주로 resource counting에 사용

Binary semaphore (= mutex)

➳ 0 또는 1 값만 가질 수 있는 semaphore

➳ 주로 mutual exclusion (lock / unlock)에 사용

Semaphore는 프로그래밍을 조금만 잘 못 해도 큰 문제가 생길 수가 있다. 

바로 Deadlock과 Starvation이다.

다음은 이러한 Semaphore의 문제점에 대해서 알아보자 !

Deadlock and Starvation

Deadlock

" 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상이다. "

e.g. S와 Q가 1로 초기화된 semaphore라고 하자.

세마포어 변수 S와 Q, 두 자원 모두 있어야만 작업이 가능한 경우를 생각해 보자. S와 Q를 동시에 얻어서 작업을 하고, 동시에 반납해야 한다. P0가 S를 얻은 상태에서 P1에게 CPU를 빼앗겼다고 해보자. 그리고 P1은 Q를 획득했다. P0은 S를 획득하였고, P1은 Q를 획득한 것이다. 이 상태에서 P1은 S가 없으므로 계속 실행할 수가 없다. P0으로 넘어가도 S는 있지만 Q가 없으므로 실행이 불가하다. 이처럼 각각 프로세스가 자원을 하나씩만 가져서 영원히 그 아래로는 수행이 안 되는 문제점이 발생할 수 있다.

프로세스는 자원을 획득하면 무조건 일을 다 끝난 다음에서야 자원을 내놓는다는 점이 바로 이 문제의 근본적인 이유이다. 다른 프로세스가 또 다른 자원을 가지고 있으니 어차피 자원을 가지고 있어 봐야 소용이 없다고 생각해 자원을 내어준다면 애초에 이런 문제가 안 생길 것이다.

Starvation

" indefinite blocking이다. 프로세스가 suspend 된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상이다. "

만약 아래 그림처럼 획득하는 자원의 순서를 동일하게 정해준다면 위와 같은 문제가 발생하지 않을 것이다 !

Classical Problems of Synchronization

공유 데이터에 접근 시 발생하는 전통적인 동기화의 문제점 세 가지에 대해서 알아보자. 

해결하는 방안은 Semaphore를 이용한다.

➳ Bounded-Buffer Problem (Producer-Consumer Problem)

➳ Readers-Writers Problem

➳ Dining-Philosophers Problem

1. Bounded-Buffer Problem (Producer-Consumer Problem)

Bounded-Buffer는 크기가 유한한 공유 buffer이다. 즉, 여러 프로세스가 동시에 접근할 수 있다. 여기서 프로세스는 producer(생산자) process와 consumer(소비자) process, 두 가지로 나뉜다. 이 프로세스들이 공유 buffer에서 하는 일은 무엇일까 ? producer process는 데이터를 만들어서 buffer에 넣어주는 역할을 한다. consumer process는 데이터를 꺼내가는 역할을 한다. 

producer process는 빈 버퍼를 발견하고, '여기에다 데이터를 넣어야지 !' 생각하는 찰나 CPU를 빼앗겼다고 해보자. 다른 producer process도 똑같이 빈 버퍼를 발견하고 똑같은 생각을 한다면 데이터 유실의 문제가 생긴다.

이 문제를 해결하기 위해서는 공유 buffer를 접근할 때 lock을 걸고, 작업이 끝나면 lock을 풀어주는 방법을 사용한다. 이는 consumer process도 마찬가지이다.

✨ Shared data

- buffer 자체 및 buffer 조작 변수 (empty/full buffer의 시작 위치)

✨ Synchronization variables

- mutual exclusion ➳ Need binary semaphore (shared data의 mutual exclusion을 위해)

- resource count ➳ Need integer semaphore (남은 full/empty buffer의 수 표시)

코드로 보면 다음과 같다.

mutex는 lock을 거는 세마포어 변수이다.

2. Readers-Writers Problem

➳ 한 process가 DB에 write 중일 때 다른 process가 접근하면 안 된다.

➳ read는 동시에 여럿이 해도 된다.

➳ solution

    • Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기 중인 Reader들을 다 DB에 접근하게 해 준다.

    • Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다.

    • 일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다.

    • Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다.

✨ Shared data

- DB 자체

- readcount ➳ 현재 DB에 접근 중인 Reader의 수

✨ Synchronization variables

- mutex ➳ 공유 변수 readcount를 접근하는 코드 (critical section)의 mutual exclusion 보장을 위해 사용한다.

- db ➳ Reader와 Writer가 공유 DB 자체를 올바르게 접근하게 하는 역할이다. (역시 lock을 걸고 푼다.)

코드는 다음 그림과 같다.

이는 starvation이 발생할 수 있다는 문제가 있다. Reader가 계속 들어온다면 아무리 Writer가 먼저 도착했어도 영영 기다려야 할 수가 있다. 어떻게 하면 이 문제를 해결할 수 있을까 ? 일정 시간 내 접근한 Reader만 접근이 가능하도록 하고, 일정 시간 후에는 기다리고 있는 Writer에게도 접근 기회를 주는 방식으로 starvation 문제를 해결할 수 있다. 

3. Dining-Philosophers Problem

젓가락 다섯 짝이 공유 데이터이고, 다섯 명의 철학자는 굶어 죽으면 안 된다. 철학자는 생각을 할 수도 있고, 밥을 먹을 수도 있다. 만약 모든 철학자가 동시에 배고파서 동시에 왼쪽에 있는 젓가락 한 짝을 집었다면 오른쪽에 있는 나머지 한 짝을 모두 집을 수 없으므로 모두 밥을 먹을 수 없는 사태가 발생한다.

❓ 문제점

 ➳ 모든 철학자가 동시에 배가 고파서 왼쪽 젓가락 한 짝을 집어버린 경우 Deadlock 가능성이 있다.

❗ 해결 방안

 ➳ 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.

 ➳ 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.

 ➳ 비대칭 : 짝수 (홀수) 철학자는 왼쪽 (오른쪽) 젓가락부터 집도록 한다. 획득하는 자원의 순서를 정해주는 것이다.

두 번째 해결 방안을 코드로 살펴보면 다음과 같다.

Monitor 방안으로 Dining-Philosophers Problem를 해결한 코드를 semaphore 방안으로 고스란히 옮긴 것이다.

Semaphore의 문제점

 ➳ 코딩하기 힘들다.

 ➳ 정확성 (correctness)의 입증이 어렵다.

 ➳ 자발적 협력 (voluntary cooperation)이 필요하다.

 ➳ 한 번의 실수가 모든 시스템에 치명적인 영향을 준다.

그렇다면 좀 더 쉽게 프로세스 동기화를 할 수는 없을까 ?

이 생각으로부터 나온 방안이 바로 Monitor이다.

Monitor 

동시 수행 중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct

Monitor는 공유 데이터 동시 접근에 대한 모든 책임을 진다. 하지만 Semaphore는 그렇지 않다. Semaphore는 P 연산이나 V 연산을 통해 원자적으로  자원의 남은 개수를 count 하는 연산을 제공한다. 실제 동기화 문제는 프로그래머의 몫이다. 공유 데이터에 접근하기 전에 프로그래머가 lock을 걸고, 접근이 끝나면 프로그래머가 lock을 풀어주어야 한다.

Monitor는 공유 데이터에 대한 접근은 오직 Monitor 안에 정의된 함수를 통해서만 접근이 가능하도록 하고, Monitor 안에서 active 하게 실행되는 프로세스는 하나로 제한한다. 따라서 프로그래머는 lock을 걸 필요 없이 Monitor 안에 있는 코드로 데이터에 접근하도록 하면 알아서 동기화가 된다.

아래는 Monitor를 추상적으로 그린 것이다.

하나의 프로세스가 이미 Monitor 안에서 작업을 수행 중이라면 접근을 하고 싶어 하는 또 다른 프로세스는 Queue에 줄을 서서 기다리도록 한다.

Monitor의 특징

➳ 모니터 내에서는 한 번에 하나의 프로세스만이 활동이 가능하다.

➳ 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없다.

➳ 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable을 사용한다. ( condition x, y; )

➳ condition variable은 wait와 signal 연산에 의해서만 접근이 가능하다.

x.wait();

➳ x.wait()를 invoke 한 프로세스는 다른 프로세스가 x.signal()을 invoke 하기 전까지 suspend 된다.

x.signal();

➳ x.signal()은 정확하게 하나의 suspend 된 프로세스를 resume 한다. suspend 된 프로세스가 없으면 아무 일도 일어나지 않는다.

condition variable은 semaphore 변수와 비슷한 역할을 한다. 자원의 여분이 있을 때에는 그냥 수행을 하도록 하고, 없을 때에는 잠들도록 한다. 잠들도록 한다는 것은 queue에 줄을 세워 blocked 상태로 만든다는 의미이다. x라는 자원이 없다면 x.wait()를 호출하고, condition variable은 x라는 queue에 줄을 서서 잠들도록 하는 역할을 담당한다. 만약 x라는 자원을 다 사용하고 반환하는 프로세스가 있다면 x.signal()을 호출해 혹시 x 자원의 여분이 없어 잠들어있는 프로세스가 있다면 깨우도록 한다.

이제 Monitor를 사용해 동기화 문제를 해결하는 예를 살펴보자 !

앞서 나온 Semaphore를 사용한 예와 비교하면 이해하는데 도움이 된다.

1. Bounded-Buffer Problem (Producer-Consumer Problem)

full.signal()을 호출했을 때, 만약 줄 서서 기다리고 있는 프로세스가 없다면 그냥 아무 일도 안 일어난다. 

2. Dining-Philosophers Problem

공유 데이터인 다섯 짝의 젓가락과 다섯 명의 철학자 상태 변수가 monitor 함수 안에 있다. condition variable은 철학자가 밥을 먹고자 할 때 젓가락 두 짝을 모두 잡을 수 있는 상태라면 밥을 먹도록 하고, 그렇지 않은 상태라면 큐에 잠들어서 기다리도록 한다.

공유 데이터 (shared data)의 동시 접근 (concurrent access)은 데이터의 불일치 문제 (inconsistency)를 발생시킬 수 있다. 일관성 (consistency) 유지를 위해서는 협력 프로세스 (cooperating process) 간의 실행 순서 (orderly execution)를 정해주는 메커니즘이 필요하다

목차

1. 데이터의 접근
2. Race Condition
3. OS에서의 Race Condition
4. Process Synchronization 문제
5. The Critical-Section Problem
6. Initial Attempts to Solve Problem
7. Synchronization Hardware

데이터의 접근

컴퓨터에서 연산을 할 때에는 항상 데이터를 읽어와서 연산을 하고, 연산 결과를 다시 어딘가로 저장하고 내보내도록 되어 있다.

Race Condition

만약 count를 플러스도 하고 마이너스도 했다면 원래 값이 되어야 하지만 마이너스만 반영된다. 이렇게 하나의 데이터를 여럿이 동시에 접근하게 되면 문제가 생긴다. 이러한 문제를 Race Condition, 즉 경쟁 상태라고 한다. 

Race Condition 문제는 정말 생기는 것일까 ? 

문제가 안 생긴다는 관점에서 이야기를 시작해보자. CPU가 한 개든 여러 개든 문제는 안 생긴다. count와 같은 데이터는 프로세스 내부에 있는 데이터이다. 프로세스는 자기 자신의 주소 공간에 있는 데이터만 접근할 수 있다. 따라서 서로 다른 프로세스 간에는 애초에 데이터를 공유할 수 없다.

하지만 문제는 운영체제가 끼어드는 경우이다. 이러한 경우는 CPU가 하나만 있어도 문제가 생긴다. 예를 들어 프로세스 A가 CPU에서 실행 중인 경우를 생각해 보자. 프로세스는 본인이 스스로 할 수 없는 일을 운영체제에게 부탁하는 system call을 한다. 프로세스 A가 system call을 하고 운영체제 내 데이터 값을 바꾸려던 찰나 자신의 CPU 할당 시간이 종료되어 CPU는 프로세스 A로부터 프로세스 B로 넘어갔다고 해보자. B 또한 system call을 했는데 우연히 A가 건드리던 똑같은 운영체제 내 데이터 값을 변경하는 상황이 발생했다면 Race Condition 문제가 발생할 수가 있다. 

OS에서의 Race Condition

" OS에서 race condition은 언제 발생할까 ? "

1) kernel 수행 중 interrupt 발생하는 경우

Interrupt handler VS kernel

2) process가 system call을 하여 kernel mode로 수행 중, context switch가 일어나는 경우

preempt a process  running in kernel ?

➳ 두 프로세스의 address space 간에는 data sharing이 없다.

➳ 그러나 system call을 하는 동안에는 kernel address space의 data를 access 하게 된다. (share)

➳ 이 작업 중간에 CPU를 preempt 해가면 race condition이 발생한다.

If you preempt CPU while in kernel mode,

3) multiprocessor에서 shared memory 내의 kernel data인 경우

CPU가 여러 개 있는 경우 생기는 문제점이다.

방법 1은 운영체제 전체에 lock을 걸어 혼자 독점하는 방법이다. 하지만 방법 2는 운영체제 내 각 데이터 별로 사용 중일 때 lock을 거는 방법이다. 따라서 여러 CPU가 운영체제를 수행 중이어도 해당 데이터를 건드리지만 않는다면 충분히 운영체제 코드를 동시에 실행할 수 있다.

Process Synchronization 문제

공유 데이터 (shared data)의 동시 접근 (concurrent access)은 데이터의 불일치 문제 (inconsistency)를 발생시킬 수 있다. 일관성 (consistency) 유지를 위해서는 협력 프로세스 (cooperating process) 간의 실행 순서 (orderly execution)를 정해주는 메커니즘이 필요하다.

➳ race condition

    • 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황

    • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라진다.

race condition을 막기 위해서는 concurrent process는 동기화 (synchronize) 되어야 한다.

Example of a Race Condition

공유 데이터를 접근하는 코드를 critical-section이라고 부른다.

The Critical-Section Problem

➳ n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우에 발생한다.

➳ 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재한다.

➳ Problem

    • 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.

Initial Attempts to Solve Problem

➳ 두 개의 프로세스가 있다고 가정한다. 

➳ synchronization variable : 프로세스들은 수행의 동기화 (synchronize)를 위해 몇몇 변수를 공유할 수 있다. 

프로세스들의 일반적인 구조

critical section 앞(= entry section), 뒤(= exit section)로 어떤 코드를 붙여야 문제를 해결할 수 있을까 ?

다음은 동기화 문제를 해결해주는 알고리즘들을 살펴볼 것이다.

그전에 프로그램적 해결법의 충족 조건을 알아본다.

프로그램적 해결법의 충족 조건

➳ Mutual Exclusion (상호 배제)

    • 특정 프로세스가 critial section을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다.

➳ Progress (진행)

    • 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.

➳ Bounded Waiting (유한한 대기)

    • 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.

🔮 가정

✔ 모든 프로세스의 수행 속도는 0보다 크다.

✔ 프로세스 간의 상대적인 수행 속도는 가정하지 않는다.

Algorithm 1

synchronization variable로 turn 변수를 사용한다. turn이 1이라면 상대방 차례로 바꾼 것이다. 반드시 한 번씩 교대로 들어가야만 하므로 단점도 존재한다. 프로그램적 해결법의 충족 조건을 보면 mutual exclusion은 충족하지만 progress는 충족하지 않는다. 

Algorithm 2

boolean 변수 flag를 활용해 들어가고 싶은 경우 깃발을 들어 의사를 알린다. 상대방의 깃발이 들려있는지 확인하고, 없다면 critical section에 들어갈 수 있다. 누구나 critical section에 들어가서 나올 때에는 깃발을 내려 다른 사람이 들어올 수 있도록 해준다. 프로그램적 해결법의 충족 조건을 보면 Algorithm 1과 마찬가지로 mutual exclusion은 충족하지만 progress는 충족하지 않는다. 깃발은 들고 critical section은 실행하지 않은 상태에서 CPU를 빼앗긴 경우, 새로 CPU를 잡은 다른 프로세스도 깃발을 들기 때문에 서로 끊임없이 양보하는 문제가 있을 수 있다는 것이다.

따라서 Algorithm 1과 Algorithm 2 둘 다 제대로 작동하지 않는다.

Algorithm 3 (Peterson's Algorithm)

깃발도 들고, turn 변수도 사용한다. 즉, 상대방이 깃발을 들고 있으면서 동시에 상대방 차례인 경우에만 기다린다. 프로그램적 해결법의 충족 조건을 모두 충족한다 ! 하지만 비효율적이라는 문제가 있다. 계속 critical section에 들어가지 못하는 경우에 불필요하게 계속 while문을 돌기 때문이다. 이를 busy  waiting 혹은 spin lock이라고 한다. 쓸데없이 바쁘게 기다리고, 자원을 낭비한다는 것이다. 

Synchronization Hardware

➳ 하드웨어적으로 Test & modify를 atomic 하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결된다.

lock이 true라면 애초에 while문을 읽어 내려갈 수가 없다. lock이 풀렸을 때 스스로 lock을 걸고 critical section을 실행해나갈 수 있다.

다음 글에서는 앞서 소개한 세 가지 알고리즘 방식처럼 코드를 직접 작성하지 않고, 좀 더 추상화시킨 process synchronization 문제 해결 방안을 알아본다.  이는 프로그래머로 하여금 도구를 가져다 좀 더 쉽고 효율적으로 문제를 풀 수 있도록 한다.

Reference

KOCW 운영체제 강의 (이화여자대학교, 반효경 교수님)

이 고민을 해결하기 위해서 CPU 스케줄링이 필요하다. 여러 종류의 job(=process)이 섞여 있기 때문이다. Interactive job에게는 적절한 response를 제공하는 것이 필요하다. CPU 스케줄링은 CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용할 수 있도록 한다.

목차

1. CPU and I/O Bursts in Program Execution
2. CPU-burst Time의 분포
3. CPU Scheduler & Dispatcher
4. Scheduling Algorithms
   1. FCFS (First-Come First-Served)
   2. SJF (Shortest- Job First)
   3. SRTF (Shortest-Remaining-Time-First)
   4. Priority Scheduling
   5. RR (Round Robin)
   6. Multilevel Queue
   7. Multilevel Feedback Queue
5. 다음 CPU Burst Time의 예측
6. 특수한 CPU 스케줄링
7. Algorithm Evaluation

CPU and I/O Bursts in Program Execution

위 그림은 한 프로세스의 일생을 시작부터 종료까지 담았다.

Burst : 계속되는 작업을 의미한다.

CPU burst : CPU를 사용하는 구간을 의미한다.

I/O burst : I/O를 실행하는 구간을 의미한다.

어떤 프로세스는 CPU를 굉장히 오래 사용하고, I/O는 아주 잠깐만 사용한다. 다른 어떤 프로세스는 CPU 잠깐, I/O 잠깐 자주 번갈아 가면서 사용하기도 한다. 이처럼 항상 상황은 다르다. 주로 과학 계산과 같이 연산량이 많이 필요한 프로그램은 CPU를 오래 사용하고, 사람과 Interaction이 많은 프로그램은 CPU와 I/O가 번갈아가면서 사용된다. 아래 CPU-burst Time의 분포를 보면 이를 확인할 수 있다.

CPU-burst Time의 분포

위 그래프에서 보다시피 프로세스는 특성에 따라 두 종류로 나눈다. CPU를 길게 쓰는 프로세스를 CPU bound job(= CPU bound process), I/O가 중간에 많이 끼어들어서 CPU를 짧게 씩 쓰는 프로세스를 I/O bound job(= I/O bound process)이라고 한다.

프로세스의 특성 분류

➳ I/O-bound process

    •  CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job

    •  many short CPU bursts

➳ CPU-bound process

    • 계산 위주의 job

    • few very long CPU bursts

그럼 둘 중 CPU를 누구한테 먼저 주어야 할까 ? 준다면 얼마만큼 주어야 할까 ?

이 고민을 해결하기 위해서 CPU 스케줄링이 필요하다. 여러 종류의 job(=process)이 섞여 있기 때문이다. Interactive job에게는 적절한 response를 제공하는 것이 필요하다. CPU 스케줄링은 CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용할 수 있도록 한다.

CPU Scheduler & Dispatcher

" CPU Scheduler "

➳  Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.

" Dispatcher "

➳  CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다.

➳  이 과정을 context switch(문맥 교환)라고 한다.

CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다.

1) Running ➳ Blocked (e.g. I/O 요청하는 system call)

2) Running ➳ Ready (e.g. 할당시간만료로 timer interrupt)

3) Blocked ➳ Ready (e.g. I/O 완료 후 interrupt)

4) Terminate

1), 4)의 경우는 nonpreemptive (= 강제로 빼앗지 않고 자진 반납)

All other scheduling is preemptive (= 강제로 빼앗음)

Scheduling Criteria

Performance Index (= Perrformance Measure, 성능 척도)

✔ CPU utilzation (이용률)

Keep the CPU as busy as possible

✔ Throughput (처리량)

# of processes that complete their execution per time unit

✔ Turnaround time (소요시간, 반환시간)

amount of time to execute a particular process

✔ Waiting time (대기 시간)

amount of time a process has been waiting in the ready queue 

✔ Response time (응답 시간)

amount of time it takes from when a request was submitted until the first response is produced, not output 

(for time-sharing environment)

이용률과 처리량은 높을수록 좋다. 시간과 관련된 세 가지 성능 척도는 낮을수록 좋다.

Scheduling Algorithms

• FCFS (First-Come First-Served)
• SJF (Shortest-Job-First)
• SRTF (Shortest-Remaining-Time-First)
• Priority Scheduling
• RR (Round Robin)
• Multilevel Queue
• Multilevel Feedback Queue

FCFS (First-Come First-Served)

먼저 온 순서대로 처리해 준다. 강제로 빼앗지 않는 nonpreemptive이다. 인간 세상에서는 널리 쓰이는 방법이지만, CPU 스케줄링에서는 대단히 효율적이지 못하다. 위 예제를 보면 성능 척도 중 하나인 waiting time의 평균은 17초이다. 만약 CPU를 짧게 쓰는 프로세스가 먼저 도착했다면 어떻게 될까 ?

똑같은 세 개의 프로세스가 똑같이 선착순으로 왔지만 이번엔 waiting time이 굉장히 짧아졌다. 

CPU를 오래 쓰는 프로세스가 먼저 도착한 바람에 CPU를 짧게 쓰는 프로세스가 아주 오래 기다려야 하는 안 좋은 효과를 Convoy effect라고 한다.

SJF (Shortest-Job-First)

➳ 각 프로세스의 CPU burst time을 가지고 스케줄링에 활용한다.

➳ CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄 한다.

💡 Two schemes :

1) Nonpreemptive

일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점 (preemption)하지 않는다.

2) Preemptive

현재 수행 중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착한다면 CPU를 빼앗긴다. 이 방법을 Shortest-Remaining-Time-First (SRTF)이라고도 부른다.

" SJF is optimal "

주어진 프로세스에 대해 minimum average waiting time을 보장한다. optimal은 최적의 방법이라는 뜻이다. 즉, 다른 어떤 CPU 스케줄링 알고리즘을 쓰더라도 SJF보다 대기 시간의 평균을 더 짧게 할 수는 없다는 의미이다. SJF는 두 가지로 나뉘지만 제일 optimal 한 방법은 Preemptive 버전인 SRTF이다.

Example of Non-Preemptive SJF

Example of Preemptive SJF

그러나 SJF는 치명적인 약점을 가지고 있다. 바로 starvation을 발생시킬 수 있다는 점이다. SJF는 극도로 효율성을 중시하다 보니 짧은 프로세스에게 무조건 우선순위를 준다. 따라서 long job, 즉 CPU를 길게 쓰는 프로세스는 영원히 CPU를 못 얻을 수도 있다. Queue가 계속 쌓일 수 있기 때문이다. 어떤 프로세스가 10초라고 한다면 앞에 계속 1초짜리 10000개, 3초짜리 10000개가 속속히 도착을 한다면 10초가 걸리는 프로세스는 아예 기회가 없을 수 있다는 것이다.

SJF는 CPU를 짧게 쓰는 프로세스한테 준다고 했다. 하지만 누가 짧게, 누가 길게 쓰는지 처음에 알 수가 없다. 짧게 쓴다고 했는데 막상 계속 길게 쓰는 경우가 있고, 길게 쓴다고 했는데 막상 짧게 쓰고 I/O를 하러 가버리는 경우도 있기 때문이다. 즉, 얼마큼 CPU를 사용한 후 I/O를 하러 갈 것인지, CPU burst를 예측하기 힘들다는 것이다. 정확히는 예측하기 어렵지만 과거의 CPU burst 이력을 보고 다음번의 CPU burst를 예측하는 방법을 알아보자 !

다음 CPU Burst Time의 예측

다음번 CPU burst time을 어떻게 알 수 있을까?

추정(estimate)만이 가능하다. 과거의 CPU burst time을 이용해서 추정한다. (exponential averaging)

1. t는 실제 과거의 CPU burst 값이다. n은 이미 과거에 지나간 것으로, n번째 CPU burst 값이 얼마였는지 알려준다.

2. 𝛕 는 예측값이다. n+1번째의 CPU Burst 값을 예측하는 것이다.

3. α는 어느 정도 가중치를 두어 반영할 것인지를 결정한다.

4. n번째 실제 CPU Burst 값과  n번째 CPU Burst를 예측한 값에 어느 정도 가중치를 두어 두 값을 더하는 것이다.

Priority Scheduling

➳ A priority number (integer) is associated with each process`

➳ highest priority를 가진 프로세스에게 CPU를 할당한다. (smallest integer = highest priority)

    •  preemptive

    •  nonpreemptive

" SJF는 일종의 priority scheduling이다. "

priority = predicted next CPU burst time

🌀 Problem 

➳ Starvation : low priority processes may never execute

🌀 Solution

➳ Aging : as time progresses increase the priority of the process

SJF의 문제점인 Starvation을 해결하는 방법은 Aging이다. Aging은 나이 든 프로세스를 우대한다. 먼저 온 프로세스는 시간이 지날수록 우선순위를 높여주는 것이다. 다음은 실제 현재 CPU Scheduling에서 가장 많이 사용하는 방법의 근간이 되는 알고리즘, Round Robin을 알아보자 !

Round Robin (RR)

➳ 각 프로세스는 동일한 크기의 할당 시간 (time quantum)을 가진다.

    • 일반적으로는 10-100 milliseconds

➳ 할당 시간이 지나면 프로세스는 선점(preempted)당하고, ready queue의 제일 뒤에 가서 다시 줄을 선다.

➳ n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.

    • 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.

➳ Performance

    • q large : FCFS

    • q small : context switch 오버헤드가 커진다.

long job과 short job이 섞여있기 때문에 Round Robin을 사용하는 것이 효율적인 것이다. 만약 long job만 있거나, short job만 있도록 통일된 프로세스를 생각해 보자. 만약 똑같이 5분 걸리는 프로세스가 100개라고 한다면 Round Robin 알고리즘보다는 그냥 5분씩 끝까지 처리해주는 것이 더 나을 것이다. 

Multilevel Queue

" Ready Queue를 여러 개로 분할한다. "

➳ foreground (interactive)

➳ background (batch - no human interaction)

" 각 큐는 독립적인 스케줄링 알고리즘을 가진다. "

➳ foreground - RR

➳ background - FCFS

" 큐에 대한 스케줄링이 필요하다. "

➳ Fixed priority scheduling

    • serve all from foreground then from background

    • possibility of starvation

➳ Time slice

    • 각 큐에 CPU time을 적절한 비율로 할당한다.

    • e.g. 80% to foreground in RR, 20% to background in FCFS

Multilevel Feedback Queue

➳ 프로세스가 다른 큐로 이동이 가능하다.

➳ 에이징 (aging)을 이와 같은 방식으로 구현할 수 있다.

➳ Multilevel-feedback-queue scheduler를 정의하는 파라미터들

    • Queue의 수

    • 각 큐의 scheduling algorithm

    • Process를 상위 큐로 보내는 기준

    • Process를 하위 큐로 내쫓는 기준

    • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

Example of Multilevel Feedback Queue

위의 사진은 Multilevel Feedback Queue의 한 예이다. 제일 우선순위가 높은 맨 위 큐에서 프로세스가 끝나지 않았다면 그다음 큐로 내려가는 방식을 표현한 것이다. Round Robin만 사용하는 것이 아니라 상황에 맞게 이런 식으로도 사용을 한다. I/O Bound, 즉 CPU를 빨리 쓰려는 프로세스를 빨리 걸러내서 처리를 하는 효과가 있다.

➳ Three queues

    • Q0 : time quantum 8 milliseconds

    • Q1 : time quantum 16 millisseconds

    • Q2 : FCFS

➳ Scheduling

    • new job이 queue Q0으로 들어간다.

    • CPU를 잡아서 할당 시간 8 milliseconds 동안 수행한다.

    • 8 milliseconds 동안 다 끝내지 못했으면 queue Q1으로 내려간다.

    • Q1에 줄 서서 기다렸다가 CPU를 잡아서 16ms 동안 수행한다.

    • 16 ms에 끝내지 못한 경우 queue Q2로 쫓겨난다.

특수한 CPU 스케줄링

지금까지는 한 CPU가 있는 환경에서의 CPU 스케줄링 알고리즘에 대해 알아보았다.

지금부터는 특수한 경우의 CPU 스케줄링을 알아본다.

Multiple-Processor Scheduling

➳ CPU가 여러 개인 경우 스케줄링은 더욱 복잡해진다.

➳ Homogeneous processor인 경우

    • Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내 가도록 할 수 있다.

    • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해진다.

➳ Load sharing

    • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요하다.

    • 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법

➳ Symmetric Multiprocessing (SMP)

    • 각 프로세서가 각자 알아서 스케줄링을 결정한다.

➳ Asymmetric multiprocessing

    • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따른다.

Real-Time Scheduling

Real-Time OS는 정해진 시간 안에 어떠한 일이 반드시 종료됨이 보장되어야 하는 실시간시스템을 위한 OS이다. 따라서 해당 deadline을 만족시키는 것이 중요하다.

➳ Hard real-time systems 

    • Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링을 해야 한다.

➳ Soft real-time computing

    • Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 한다.

Thread Scheduling

➳ Local Scheduling

    • User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄 할지 결정한다.

➳ Global Scheduling

    • Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정한다.

User level thread는 운영체제가 thread의 존재를 모르고, 사용자 본인이 내부에 thread를 여러 개 두는 것이다. Kernel level thread는 운영체제가 thread의 존재를 알고, 운영체제가 직접 CPU 스케줄링에 관여한다.

Algorithm Evaluation

물론 성능 척도가 좋은 것이 좋은 CPU 스케줄링 알고리즘이다. 그렇다면 성능 척도를 어떻게 구해서 알고리즘을 어떻게 평가할까? 알고리즘 평가 방법을 알아보자 !

➳ Queueing models

    • 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산한다.

     • 복잡한 수식을 계산하는 대단히 이론적인 방법이다.

     • 현재 CPU Scheduling에서 사용하지는 않는다.  

➳ Implemetation (구현) & Measurement (성능 측정)

    • 실제 시스템에 알고리즘을 구현하여 실제 작업 (workload)에 대해 성능을 측정하여 비교한다.

    • 실제로 구현하여 성능을 측정하는 것은 매우 어렵다. (대안 = Simulation)  

➳ Simulation (모의 실행)

    • 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과를 비교한다.

trace : input이 되는 데이터이므로 중요하다.

Reference

KOCW 운영체제 강의 (이화여자대학교, 반효경 교수님)

fork() System Call이 새로운 프로세스를 생성한다. 부모를 그대로 복사 (OS data except PID + binary) 후, 주소 공간을 할당한다. fork() 다음에 이어지는 exec() System Call을 통해 새로운 프로그램을 메모리에 올린다.

목차

1. 프로세스 생성 (Process Creation)
2. 프로세스 종료 (Process Termination)
3. fork( ) System Call
4. exec( ) System Call
5. wait( ) System Call
6. exit( ) System Call
7. 프로세스 간 협력

프로세스 생성 (Process Creation)

➳ 부모 프로세스 (parent process)가 자식 프로세스 (children process)를 생성한다.

    • 운영체제에게 만들어달라고 요청한다. - fork() system Call

➳ 프로세스의 트리 (계층 구조)를 형성한다.

➳ 프로세스는 자원을 필요로 한다.

    • 운영체제로부터 받는다.

    • 부모와 공유한다.

➳ 자원의 공유

    • 부모와 자식이 모든 자원을 공유하는 모델

    • 일부를 공유하는 모델

    • 전혀 공유하지 않는 모델

➳ 수행 (execution)

    • 부모와 자식은 공존하며 수행되는 모델

    • 자식이 종료 (terminate)될 때까지 부모가 기다리는 (wait) 모델

➳ 주소 공간 (address space)

    • 자식은 부모의 공간을 복사한다. (biinary and  OS data)

    • 자식은 그 공간에 새로운 프로그램을 올린다.

➳ 유닉스의 예

    • fork() System Call이 새로운 프로세스를 생성한다. 부모를 그대로 복사 (OS data except PID + binary) 후, 주소 공간을 할당한다.

    • fork() 다음에 이어지는 exec() System Call을 통해 새로운 프로그램을 메모리에 올린다.

프로세스 종료 (Process Termination)

프로세스가 마지막 명령을 수행한 후 운영체제에게  이를 알려준다. (exit)

➳ 자식이 부모에게 output data를 보낸다. (via wait)

➳ 프로세스의 각종 자원들이 운영체제에게 반납된다.

부모 프로세스가 자식의 수행을 종료시킨다. (abort)

➳ 자식이 할당 자원의 한계치를 넘어선 경우

➳ 자식에게 할당된 task가 더 이상 필요하지 않은 경우

➳ 부모가 종료 (exit)하는 경우

    • 운영체제는 부모 프로세스가 종료하는 경우 자식이 더 이상 수행되도록 두지 않는다.

    • 단계적인 종료이다.

    •  e.g. 티스토리 글쓰기 창을 없애면 글쓰기 창 안의 여러 프로세스들도 동시에 없어지는 것과 같다.

fork( ) System Call

" create a child (copy) "

➳ A process is created by the fork() system call.

    • creates a new address space that is a duplicate of the caller.

fork()는 자식을 하나 만들어달라고 요청하는 함수이다. fork() 하는 순간 아래와 같이 복제한다.

물론 메모리 공간, Program Counter도 복제한다.

부모와 자식 모두 fork() 한 다음부터 실행한다. 그리고 이 둘은 별개의 프로세스가 되는 것이다. 복제했기 때문에 내가 부모인지 자식인지 알 수가 없어 서로 구분할 필요가 있다. fork()를 호출한 return 값이 부모 프로세스는 양수 값, 자식 프로세스는 0이므로 이를 통해 구분이 가능하다.

fork()는 한 프로세스의 동일한 실행 파일을 실행한 것과 같다. 완전히 다른 프로그램을 실행하고 싶다면 fork() system call 로만은 어렵다. 새로운 프로그램을 덮어 씌우는 서비스가 필요한데, 이를 위한 것이 바로 exec() system call이다.

• pid = 프로세스 식별자

exec( ) System Call

" overlay new image "

➳ A process can execute a different program by the exec() system call.

    • replaces the memory image of the caller with a new program.

wait( ) System Call

" sleep utill child is done "

프로세스 A가 wait() System Call을 호출하면

➳ 커널은 child가 종료될 때까지 프로세스 A를 sleep 시킨다. (block 상태)

➳ child process가 종료되면 커널은 프로세스 A를 깨운다. (ready 상태)

아래 프로세스의 상태를 살펴보면, 자식의 종료를 기다리며 block 상태가 되도록 하는 부분이 wait() system call이라고 볼 수 있다.

만약 wait() system call이 없다면 부모  프로세스와 자식 프로세스는 CPU를 먼저 차지하기 위해 서로 경쟁할 것이다. 하지만 부모 프로세스가 fork() 후, wait()를 호출한다면 자식이 종료될 따까지 부모는 block 상태에 있는 것이다.

exit( ) System Call

" frees all the resources, notify parent " 

프로세스의 종료

🔮 자발적 종료

➳ 마지막 statement 수행 후 exit() system call을 통해 종료한다.

➳ 프로그램에 명시적으로 적어주지 않아도 main 함수가 리턴되는 위치에 컴파일러가 넣어준다.

🔮 비자발적 종료

➳ 부모 프로세스가 자식 프로세스를 강제 종료시키는 경우

    • 자식 프로세스가 한계치를 넘어서는 자원을 요청하는 경우

    • 자식에게 할당된 task가 더 이상 필요하지 않은 경우

➳ 키보드로 kill, break 등을 친 경우

➳ 부모가 종료하는 경우

    • 부모 프로세스가 종료하기 전에 자식들이 먼저 종료된다.

프로세스 간 협력

✔ 독립적 프로세스 (Independent process)

프로세스는 각자의 주소 공간을 가지고 수행되므로 원칙적으로 하나의 프로세스는 다른 프로세스의 수행에 영향을 미치지 못한다.

✔ 협력 프로세스 (Cooperating process)

프로세스 협력 메커니즘을 통해 하나의 프로세스가 다른 프로세스의 수행에 영향을 미칠 수 있다.

✔ 프로세스 간 협력 메커니즘 (IPC, Interprocess Communication)

1)  메시지를 전달하는 방법

" message passing "

커널을 통해 메시지를 전달한다.

2) 주소 공간을  공유하는 방법

" shared memory "

서로 다른 프로세스 간에도 일부 주소 공간을 공유하게 하는 shared memory 메커니즘이 있다.

" thread "

thread는 사실상 하나의 프로세스이므로 프로세스 간 협력으로 보기는 어렵지만 동일한 프로세스를 구성하는 thread 간에는 주소 공간을 공유하므로 협력이 가능하다.

원칙적으로는 각 프로세스는 본인만의 code, data, stack만 접근할 수 있으므로 서로 다른 프로세스가 메모리 공간을 share 할 수 없다. Shared Memory를 위해 운영체제에게 system call로 부탁하는 것이다. 프로세스 간 서로 신뢰할 수 있는 경우에만 shared memory를 만들어야 한다.

Reference

KOCW 운영체제 강의 (이화여자대학교, 반효경 교수님)

🦌 크리스마스 D-10 기념으로 트리에 대해서 알아보자 🎅🏻 물론 크리스마스 트리 말고 ,,  자료구조 트리이다 ^_^ 트리는 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조이다. 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1이다. 부모-자식 관계로 이루어져 있다. 트리 내에 하위 트리가 있고, 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료구조이기도 하다.

🦌 크리스마스 D-10 기념으로 트리에 대해서 알아보자 🎅🏻 

물론 크리스마스 트리 말고 ,,  자료구조 트리이다 ^_^ 

목차

1. 트리 (Tree)란 ?
2. 이진 탐색 트리 (Binary Search Tree)
3. 트리의 순회 (Tree Travelsal)

트리 (Tree)란 ?

트리는 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조이다. 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1이다. 부모-자식 관계로 이루어져 있다. 트리 내에 하위 트리가 있고, 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료구조이기도 하다. 컴퓨터의 directory 구조가 트리 구조의 대표적인 예이다.

❄️ 루트 노드 (root node) : 부모가 없는 최상위 노드

❄️ 단말 노드 (leaf node) : 자식이 없는 노드

❄️ 크기 (size) : 트리에 포함된 모든 노드의 개수

❄️ 깊이 (depth) : 루트 노드부터의 거리 (= 간선의 수)

❄️ 높이 (height) : 깊이 중 최댓값

❄️ 차수 (degree) : 각 노드의 (자식 방향) 간선 개수 (= 하위 트리 개수)

이진 탐색 트리 (Binary Search Tree)

이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종이다.

🔔 이진 탐색 트리의 특징 : 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

이진 탐색 트리가 이미 구성되어 있다면 데이터를 조회하는 방법은 다음과 같다.

🔔 루트 노드부터 방문하여 탐색을 진행한다.

🔔 현재 노드와 찾고자 하는 값을 비교한다.

🔔 원소를 찾았다면 탐색을 종료한다.

트리의 순회 (Tree Traversal)

트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법을 의미한다.

대표적인 트리 순회 방법은 다음과 같다.

🎄 전위 순회 (pre-order traverse) : 루트를 먼저 방문한다.

    • 노드 - 왼쪽 자식 - 오른쪽 자식 순

🎄 중위 순회 (in-order traverse) : 왼쪽 자식을 방문한 뒤에 루트를 방문한다.

    • 왼쪽 자식 - 노드 - 오른쪽 자식 순

🎄 후위 순회 (post- order traverse) : 오른쪽 자식을 방문한 뒤에 루트를 방문한다.

    • 왼쪽 자식, 오른쪽 자식, 노드 순

전위 순회 : A - B - D - E - C - F - G

중위 순회 : D - B - E - A - F - C - G

후위 순회 : D - E - B - F - G - C - A

Reference

CPU는 하나이기 때문에 CPU에서 기계어를 실행하고 있는 프로세스는 매 순간 하나이다. 실행 중인 프로세스는 'Running 상태에 있다.'라고 표현한다. CPU를 쓰기 위해 기다리고 있는 프로세스는 Ready 상태라고 한다. 또한, CPU를 주어도 당장 기계어 실행이 불가능한 프로세스도 있다. 예를 들어 디스크에서 파일을 읽어야 한다면, 이 작업이 다 끝날 때까지는 CPU를 줘봐야 소용이 없다. 이처럼 CPU를 얻어도 무의미한 프로세스를 두고 Blocked 상태라고 한다.

목차

1. 프로세스의 개념
2. 프로세스의 상태 (Process State)
3. 프로세스 상태도
4. Process Control Block (PCB)
5. 문맥 교환 (Context Switch)
6. 프로세스를 스케줄링하기 위한 큐  
7. 스케줄러 (Scheduler)
8. 스레드 (Thread) 
9. Process와 Thread

프로세스의 개념

" Process is a program in execution "

프로세스의 문맥 (context)

➳ CPU 수행 상태를 나타내는 하드웨어 문맥

    • Program Counter

    • 각종 Register

➳ 프로세스 주소 공간

    • code, data, stack

➳ 프로세스 관련 커널 자료 구조

    • PCB (Process Control Block)

    • Kernel stack

프로세스의 상태를 나타내는 개념이 프로세스의 문맥이다. 즉, 프로세스의 문맥은 시간에 따라 현재 CPU를 얼마나 사용했는지, 메모리를 얼마나 가지고 있는지, 무슨 함수를 실행하고 있는지, 과거에 나쁜 짓은 하지 않았는지 (?) 등의 프로세스의 상태를 나타내는 정보이다. 운영체제는 프로세스의 문맥을 매우 중요하게 생각한다. 

프로세스의 상태 (Process State)

CPU는 하나이기 때문에 CPU에서 기계어를 실행하고 있는 프로세스는 매 순간 하나이다. 실행 중인 프로세스는 'Running 상태에 있다.'라고 표현한다. CPU를 쓰기 위해 기다리고 있는 프로세스는 Ready 상태라고 한다. 또한, CPU를 주어도 당장 기계어 실행이 불가능한 프로세스도 있다. 예를 들어 디스크에서 파일을 읽어야 한다면,  이 작업이 다 끝날 때까지는 CPU를 줘봐야 소용이 없다. 이처럼 CPU를 얻어도 무의미한 프로세스를 두고 Blocked 상태라고 한다.

🔅 프로세스는 상태 (state)가 변경되며 수행된다.

➳ Running

    • CPU를 잡고 instruction을 수행 중인 상태이다.

➳ Ready

    • CPU를 기다리는 상태이다. (메모리 등 다른 조건은 모두 만족한 경우)

➳ Blocked (wait, sleep)

    • CPU를 주어도 당장 instruction을 수행할 수 없는 상태이다.

    •  Process 자신이 요청한 event (ex) I/O)가 즉시 만족되지 않아 이를 기다리는 상태이다. (ex) 디스크에서 파일을 읽어와야 하는 경우)

➳ Suspended (stopped)

    • 외부적인 이유로 프로세스의 수행이 정지된 상태이다. (중기 스케줄러에 의해 쫓겨난 상태)

    • 프로세스는 통째로 디스크에 swap out 된다.

         e.g. 사용자가 프로그램을 일시 정지시킨 경우 (break key) 시스템이 여러 이유로 프로세스를 잠시 중단시킨다. 

         (메모리에 너무 많은 프로세스가 올라와 있을 때)

Blocked : 자신이 요청한 event가 만족되면 Ready

Suspened : 외부에서 resume 해주어야 Active

✔ New : 프로세스가 생성중인 상태이다.

✔ Terminated : 수행(execution)이 끝난 상태이다.

운영체제는 PCB를 통해 각 프로세스의 상태를 일일이 관리한다.  또한, 자료구조 Queue를 사용해 줄을 세워두고 일을 처리한다.

Disk I/O queue에서 기다리던 프로세스가 디스크에서 파일을 다 읽었다면 Interrupt를 걸어 운영체제로 하여금 Ready queue에 넣도록 한다.

오래 걸리는 작업은 하드웨어뿐만 아니라 여러 프로세스가 동시에 사용하는 공유 데이터를 사용하는 것도 해당하며, 이 경우 역시 Blocked 상태이다.

프로세스 상태도

CPU scheduler가 ready 상태인 프로세스를 CPU에게 주면 running 상태가 되는 것이다. 프로세스가 CPU에서 기계어를 실행하다가 CPU를 내놓는 경우는 세 가지 경우가 있다. 할당 시간이 만료되어 Timer Interrupt가 발생하는 경우, I/O 혹은 event 작업을 기다리는 blocked 상태인 경우, 본인의 일을 다해서 종료 (terminated)되는 경우이다.

이 상태도는 running을 user mode와 monitor mode로 나누었다.  어떤 프로세스가 자기 코드를 수행 중이라면 user mode의 running이고, IO작업과 같이 본인이 할 수 없는 일을 운영체제에게 부탁하여(= System Call), 운영체제에서 코드를 수행 중이라면  monitor mode(= kernel mode)의 running이다. 

그리고 이 상태도는 Suspended가 추가되었다. running, blocked, ready는 active 상태이지만, suspended는 inactive 상태이다.

프로그램의 실행

위의 그림에서는 모두 running 상태인 것이다. 

Process Control Block (PCB)

운영체제가 각 프로세스를 관리하기 위해 프로세스 당 유지하는 정보로, 운영체제 커널 주소공간에 있다.

구조체로 유지하는 구성 요소는 아래와 같다.

(1) OS가 관리상 사용하는 정보

    • Process state, Process ID

    • scheduling information, priority

(2) CPU 수행 관련 하드웨어 값

    • Program counter, registers

(3) 메모리 관련

    • code, data, stack의 위치 정보

(4) 파일 관련

    • Open  file descriptors

(2)를 보면, CPU 수행 관련 하드웨어 값을 PCB에 또 저장한다. 프로세스는 CPU를 얻었다가 빼앗겼다가 하는데,  매번 CPU를 빼앗길 때에는 해당 프로세스가 어디까지 수행되었는지 저장해두기 위함이다. 즉, 문맥을 저장해두는 것이다. 이를 통해 다음번에 CPU를 얻었을 때 해당 문맥 바로 다음 지점을 실행할 수가 있다.

문맥 교환 (Context Switch)

➳ CPU를 한 프로세스에서 다른 프로세스로 넘겨주는 과정이다.

➳  registers뿐만 아니라 Memory map과 관련된 정보들도 save 하고, load 한다.

➳ CPU가 다른 프로세스에게 넘어갈 때 운영체제는 다음을 수행한다.

    • CPU를 내어주는 프로세스의 상태를 그 프로세스의 PCB에 저장한다.

    • CPU를 새롭게 얻는 프로세스의 상태를 PCB에서 읽어온다.

문맥 교환인 경우와 그렇지 않은 경우를 헷갈리지 않도록 조심해야 한다.

System call이나 Interrupt 발생 시 반드시 문맥 교환이 일어나는 것은 아니다.

다른 사용자 프로세스에게 CPU가 넘어가는 경우만 문맥 교환이라고 볼 수 있다.

(1)의 경우는 문맥 교환이 아니다. (1)의 경우에도 CPU 수행 정보 등 context의 일부를 PCB에 save 해야 하지만 문맥 교환을 하는 (2)의 경우에는 그 부담이 훨씬 크다. (e.g. cache memory flush)

프로세스를 스케줄링하기 위한 큐

프로세스들은 각 큐들을 오가며 수행된다.

➳ Job queue

    • 현재 시스템 내에 있는 모든 프로세스의 집합이다.

➳ Ready queue

    • 현재 메모리 내에 있으면서 CPU를 잡아서 실행되기를 기다리는 프로세스의 집합이다.

➳ Device queue

    • I/O device의 처리를 기다리는 프로세스의 집합이다.

Ready Queue와 다양한 Device Queue

프로세스 스케줄링 큐의 모습

스케줄러 (Scheduler)

운영체제에서 스케줄링을 하는 함수 혹은 코드라고 볼 수 있다. 특정 기능을 수행하므로 스케줄러라고 명명하였다.

사실은 운영체제라고 볼 수 있다는 뜻이다.

✔ Long-term scheduler (장기 스케줄러, job scheduler)

➳ 시작 프로세스 중 어떤 것들을 ready queue로 보낼지 결정한다.

➳ 프로세스에 memory(및 각종 자원)를 주는 문제를 담당한다.

➳ degree of Multiprogramming을 제어한다.

    •  메모리에 올라가 있는 프로그램의 수 

➳ time sharing system에는 보통 장기 스케줄러가 없다. (무조건 ready)

    • time sharing system 이전의 옛날 시스템에서 사용했다. 

    • 현대 운영체제는 장기 스케줄러가 없는 대신 중기 스케줄러를 둔다.

✔ Short-term scheduler (단기 스케줄러, CPU scheduler)

➳ 어떤 프로세스를 다음번에 running 시킬지 결정한다.

➳ 프로세스에 CPU를 주는 문제를 담당한다.

➳ 자주 호출이 되므로, 충분히 빨라야 한다. (millisecond 단위)

✔ Medium-term scheduler (중기 스케줄러 or Swapper)

➳ 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아낸다.

➳ 프로세스에게서 memory를 뺏는 문제를 담당한다.

➳ degree of Multiprogramming을 제어한다.

스레드 (Thread)

"A thread (or lightweight process) is  a basic unit of CPU utilization "

Thread의 구성

➳ program counter

➳ register set

➳ stack space

Thread가 동료 thread와 공유하는 부분 (= task)

➳ code section

➳ data section

➳ OS resources

전통적인 개념의 heavyweight process는 하나의 Process가 하나의 thread를 가지고 있는 task로 볼 수 있다.

Benefits of Threads

➳ Responsiveness

    • e.g. multi-threaded Web - if one thread is blocked (e.g. network) another thread continues (e.g. display)

➳ Resource Sharing

    • n threads can share binary code, data, resource of the process

➳ Economy

    • creating & CPU switching thread (rather than a process)

    • Solaris의 경우 위 두 가지 overhead가 각각 30배, 5배

➳ Utilization of MP Architectures

    • each thread may be running in parallel on a different processor

🚀

다중 스레드로 구성된 task 구조에서는 하나의 서버 스레드가 blocked (waiting) 상태인 동안에도

동일한 task 내의 다른 스레드가 실행 (running)되어 빠른 처리를 할 수 있다.

🚀

동일한 일을 수행하는 다중 스레드가 협력하여 높은 처리율 (throughput)과 성능 향상을 얻을 수있다.

🚀

 스레드를 사용하면 병렬성을 높일 수 있다.

Implementation of Threads

➳ Some are supported by kernel -Kernel Threads

    • Windows 95/98/NT

    • Solaris

    • Digital UNIX, Mach

➳ Others are supported by library - User Threads    

    • POSIX Pthreads

    • Mach C-threads

    • Solaris threads

➳ Some are real-time threads

Process와 Thread

Process

우리는 웹 브라우저를 여러 개 띄워놓고 실행할 수 있다. 동일한 웹 브라우저 프로그램이지만 여러 개 띄워놓으면 여러 프로세스가 된다. 각각 프로세스마다 주소공간과 PCB가 하나씩 만들어질 것이다. 각각의 프로세스가 만들어지고, 각각 메모리에 올라가는 것은 비효율적이다. 여러 개 띄우더라도 같은 프로그램이므로 동일한 코드를 가지고 있을 것이다. 이를 좀 더 효율적으로 운용할 수 없을까? 

Thread

위의 방법보다 훨씬 효율적인 방법은 바로 Thread이다. Thread는 동일한 프로그램을 여러 개 띄우더라도 하나의 프로세스만 만들어지는 것이다. code와 같이 동일한 부분들을 한 번에 share 한다. 대신 여러 개 띄워놓은 각각의 프로그램은 서로 다른 부분의 코드를 수행할 수도 있다. 그 부분만 따로 관리를 해주기 위해 CPU의 수행단위, 즉 현재 CPU의 어느 부분을 실행하고 있는가와 관련된 정보만 따로 둔다. PCB에서 코드의 어느 부분을 수행하고 있는가에 해당하는 Program Counter 값은 각각의 Thread로 나누어 각각의 위치를 나타내고, registers 값도 현재 CPU에서 연산을 하면서 각자 CPU 수행단위가 따로 있으니까 따로 둔다. 각 Thread는 CPU를 얻었을 때 코드의 어느 부분을 실행하기 위해 함수를 호출하면서 Stack에 쌓이게 되고, 이 또한 별도로 관리한다. 

" Thread는 overhead를 줄여준다. "

프로세스 A에서 프로세스 B로 CPU를 넘겨주는 것을 문맥 교환 (Context Switch)이라고 한다. 이는 대단히 오버헤드(overhead)가 많은 작업이다. overhead란 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 및 메모리 등을 말한다. 동일한 프로세스 안에서 Thread1 로부터 Thread2 에게 CPU를 넘겨주는 것은 Context Switch의 값비싼 overhead가 필요가 없다. 따라서 효율적이다.

" Thread는 Process보다 효율적이다. "

그러나 크롬 브라우저는 보안 상의 문제로 여러 개의 창을 띄우는 것을 Thread가 아니라 Process로 한다는 이야기도 있다고 한다.

즉, 실제 구현 방식에 따라 효율적인 방안은 좀 다를 수 있다.

Reference

KOCW 운영체제 강의 (이화여자대학교, 반효경 교수님)

CPU의 독점을 막기 위해서는 부가적인 하드웨어가 필요하다. 즉, Timer가 필요하다. Timer는 일정 시간 간격으로 Interrupt를 발생시킨다. (= Timer Interrupt) 운영체제가 사용자 프로그램에게 CPU를 넘길 때에는 Timer에 시간을 세팅한 후 넘겨준다. 따라서 사용자 프로그램이 악의적으로 무한루프를 돌며 혼자 CPU를 독점하려고 해도 CPU의 제어권이 자동적으로 운영체제로 다시 넘어온다.

목차

1. 컴퓨터 시스템 구조
2. Mode bit
3. Timer  
4. Interrupt
5. 동기식 입출력과 비동기식 입출력
6. DMA
7. 프로그램의 실행 

컴퓨터 시스템 구조

➳ CPU와 device controller는 기계어를 연산하는 기능을 가지고 있다.

➳ Memory는 CPU의 작업 공간이고, local buffer는 device controller의 작업 공간이다.

Interrupt line 

Interrupt line에서는 다음 기계어를 실행하기 전, Interrupt가 들어와 있는지 확인한다.

Interrupt는 I/O 장치가 발생시킬 수 있다. 예를 들어, 사용자 프로그램 A가 디스크에서 어떤 파일을 읽어와야 한다면 CPU는 디스크 컨트롤러에게 파일을 읽어달라고 부탁한다. 파일을 읽는 동안 CPU는 운영체제로 갔다가 다른 프로그램으로 넘어간다. 디스크 컨트롤러는 파일 읽는 작업이 끝나면 CPU에게 알려주어야 하기 때문에 Interrupt를 건다. 따라서 CPU는 다음 기계어를 실행하기 전 Interrupt가 들어와 있는지 확인하고, 만약 Interrupt가 들어왔다면 CPU는 자동적으로 운영체제로 넘어간다. 즉, Mode bit이 0이 되고, 읽어온 파일을 사용자에게 넘겨주는 것과 같이 해당 Interrupt에 대응하는 일을 해준다.

Registers

CPU는 기계어를 연산하는데, Registers는 이 연산의 Input과 Output을 저장한다. 아주 빠르고 크기가 작다.

Registers 중 하나인 Program Counter (PC)는 다음 번에 실행할 기계어 메모리의 주소를 가리킨다. 

Device Controller

➳ I/O device controller

    • 해당 I/O 장치유형을 관리하는 일종의 작은 CPU이다.

    • 제어 정보를 위해 control register, status register를 가진다.

    • local buffer를 가진다. (일종의 data register)

➳ I/O는 실제 device와 local buffer 사이에서 일어난다.

➳ Device controller는 I/O가 끝났을 경우 interrupt로 CPU에 그 사실을 알린다. 

• device driver (장치 구동기) : OS 코드 중 각 장치별 처리루틴 (CPU가 실행하는 코드) : software

• device controller (장치제어기) : 각 장치를 통제하는 일종의 작은 CPU : hardware

Mode bit

운영체제는 믿고 CPU를 맡길 수 있지만, 사용자 프로그램은 무조건 믿고 맡길 수는 없다. 악의적일 수도 있다는 문제점이 있기 때문이다. 하지만 일단 CPU가 사용자 프로그램으로 넘어가면 운영체제는 제어할 길이 없다. 따라서 CPU를 운영체제가 실행하는지, 사용자 프로그램이 실행하는지를 구분할 필요가 있다.  즉, 사용자 프로그램의 잘못된 수행으로 다른 프로그램 및 운영체제에 피해가 가지 않도록 하기 위한 보호 장치가 필요하다.

이는 Mode bit이 도와준다. Mode bit을 통해 하드웨어적으로 두 가지 모드의 operation을 지원한다.

1 사용자 모드 : 사용자 프로그램 수행
0 모니터 모드 : OS 코드 수행

➳ 보안을 해칠 수 있는 중요한 명령어는 모니터 모드에서만 수행 가능한 특권명령으로 규정한다.

    • 만약 위험한 기계어인데, Mode bit이 0이 아니라면 자동적으로 CPU가 운영체제로 넘어간다.

    • CPU가 기계어를 실행할 때 안전한 명령어만 실행하도록 보호해준다.

➳ Interrupt나 Exception 발생 시 하드웨어가 mode bit을 0으로 바꾼다.

➳ 사용자 프로그램에게 CPU를 넘기기 전에 mode bit을 1로 세팅한다.

🔅 모니터 모드 = 커널 모드, 시스템 모드

Timer

운영체제는 CPU를 넘겨주는 것은 할 수 있지만, 일단 CPU가 다른 프로그램에게 넘어가면 혼자서 다시 뺏어올 수는 없다. CPU의 독점을 막기 위해서는 부가적인 하드웨어가 필요하다. 즉, Timer가 필요하다. Timer는 일정 시간 간격으로 Interrupt를 발생시킨다. (= Timer Interrupt) 운영체제가 사용자 프로그램에게 CPU를 넘길 때에는 Timer에 시간을 세팅한 후 넘겨준다. 따라서 사용자 프로그램이 악의적으로 무한루프를 돌며 혼자 CPU를 독점하려고 해도 CPU의 제어권이 자동적으로 운영체제로 다시 넘어온다. 현대 운영체제가 CPU 스케줄링을 할 때에는 Timer의 도움을 받는다.

➳ 정해진 시간이 흐른 뒤 운영체제에게 제어권이 넘어가도록 Interrupt를 발생시킨다.

➳ Timer는 매 클럭 틱 때마다 1씩 감소한다.

➳ Timer 값이 0이 되면 Timer Interrupt가 발생한다.

➳ CPU를 특정 프로그램이 독점하는 것으로부터 보호한다.

🔅 time sharing을 구현하기 위해 널리 이용된다.

🔅 현재 시간을 계산하기 위해서도 사용한다.

Interrupt

현대 운영체제는 Interrupt에 의해 구동된다. Interrupt 당한 시점의 레지스터와 program counter를 save 한 후, CPU의 제어를 Interrupt 처리 루틴에 넘긴다. 넓은 의미의 인터럽트는 소프트웨어 인터럽트도 포함하지만, 특별히 소프트웨어 인터럽트는 Trap이라고 부른다. 

🔅 Interrupt (하드웨어 인터럽트) : 하드웨어가 발생시킨 인터럽트

🔅 Trap (소프트웨어 인터럽트)

➳ Exception : 프로그램이 오류를 범한 경우

➳ System Call : 프로그램이 커널 함수를 호출하는 경우

System Call

I/O 장치에 접근하는 기계어는 전부 특권명령으로 규정된 기계어이다. 따라서 사용자 프로그램에게는 권한이 없고, 운영체제에게 요청을 해야만 한다. 이 역할은 시스템콜 (System Call)이 담당한다. System Call은 사용자 프로그램이 운영체제의 서비스를 받기 위해 커널 함수를 호출하는 것이다.

💡 인터럽트 관련 용어를 알아보자 !

✔ 인터럽트 벡터 
해당 인터럽트의 처리 루틴 주소를 가지고 있다.

✔ 인터럽트 처리 루틴 (= Interrupt Service Routine, 인터럽트 핸들러)
해당 인터럽트를 처리하는 커널 함수이다.

동기식 입출력과 비동기식 입출력

두 경우 모두 I/O의 완료는 인터럽트로 알려준다.

동기식 입출력 (synchronous I/O)

➳ I/O 요청 후 입출력 작업이 완료된 후에야 제어가 사용자 프로그램에 넘어간다.

➳ 구현 방법 1

    • I/O가 끝날 때까지 CPU를 낭비시킨다.

    • 매시점 하나의 I/O만 일어날 수 있다.

➳ 구현 방법 2

    • I/O가 완료될 때까지 해당 프로그램에게서 CPU를 빼앗는다.

    • I/O 처리를 기다리는 줄에 그 프로그램을 줄 세운다.

    • 다른 프로그램에게 CPU를 준다.

비동기식 입출력 (asynchronous I/O)

➳ I/O가 시작된 후 입출력 작업이 끝나기를 기다리지 않고 제어가 사용자  프로그램에 즉시 넘어간다.

DMA (Direct Memory Access)

➳ 빠른 입출력 장치를 메모리에 가까운 속도로 처리하기 위해 사용한다.

➳ CPU의 중재 없이 device controller가 buffer storage의 내용을 메모리에 block 단위로 직접 전송한다.

➳ 바이트 단위가 아니라 block단위로 Interrupt를 발생시킨다.

DMA controller

너무 빈번한 Interrupt는 CPU가 비효율적으로 사용된다. 

따라서 메모리에 접근할 수 있는 장치인 DMA를 하나 더 둔 것이다.

저장장치 계층 구조

➳ Primary : CPU에서 직접 접근 가능 / 빠름 / 높은 비용 / 휘발성

➳ Secondary : I/O를 통해서 접근 가능 / 느림 / 낮은 비용 / 비휘발성

➳ Cashing : 더 빠른 스토리지 시스템에 정보를 복수해두고 쓴다. (재사용성)

프로그램의 실행 (메모리 load)

프로그램은 실행 파일 형태로 저장되어있다. 마우스를 클릭해 실행하면 해당 프로그램이 메모리에 올라가서 프로세스가 된다. 운영체제 kernel은 기본적으로 메모리에 올라가 있다.

각각의 프로그램들은 자신만의 메모리 주소 공간이 존재한다. 당장 필요한 부분은 물리적인 메모리에 올라가지만, 그렇지 않은 부분은 디스크의 Swap area에 있다. 코드와 같은 일부는 파일 시스템의 실행파일 형태로 존재하기도 한다.

Virtual memory와 Physical memory에서의 주소는 다르므로 주소 변환 (Address translation)이 필요하다.

Virtual memory에서 각 프로세스의 주소 공간에는 code, data, stack이 있다.

code : 실행파일의 코드가 올라온다. 실제 CPU에서 실행할 기계어라고 할 수 있다.

data : 전역 변수나 프로그램 시작부터 종료까지 남아있는 데이터를 보관하는 영역이다.

stack : 함수 안에 있는 지역변수와 같은 데이터를 보관하는 영역이다. 함수의 호출과 리턴에 관련된 정보를 쌓아 둔다.

운영체제 커널도 하나의 프로그램이기 때문에 함수의 구조로 되어있고, 커널 주소 공간 역시 code, data, stack으로 이루어져 있다.

커널 주소 공간의 내용

시스템 안에서 돌아가는 프로세스를 관리하려면 자료 구조가 필요하다. 이를 PCB (Process Controll Block)라고 부른다. 

운영체제 stack은 조금 특이한 구조를 가지고 있다. 커널의 stack은 각 프로세스마다 별도로 두고 있다.

사용자 프로그램이 사용하는 함수

🔅 함수

➳ 사용자 정의 함수

    • 자신의 프로그램에서 정의한 함수

➳ 라이브러리 함수

    • 자신의 프로그램에서 정의하지 않고 갖다 쓴 함수

    • 자신의 프로그램의 실행 파일에 포함되어 있다.

➳ 커널 함수

    • 운영체제 프로그램의 함수

    • 커널 함수의 호출 = System Call

프로그램의 실행

프로그램을 만드는 사람은 여러 함수를 가져와 쓴다. 프로그램이 진행되면서 'CPU의 제어권이 어떻게 바뀌는가?'를 보면 내가 만든 함수나 라이브러리 함수가 실행될 때에는 내 주소 공간에 있는 코드가 user mode에서 실행된다. 반면 System Call을 부르게 되면 CPU 제어권이 운영체제에게 넘어가 kernel mode에서 운영체제 주소 공간에 있는 코드가 실행된다.  user mode는 Mode bit이 1, kernel mode는 Mode bit이 0인 상태이다.

Reference

KOCW 운영체제 강의 (이화여자대학교, 반효경 교수님)