코딩 대장

 이번 시간에는 스레드에 대해서 알아보자. 스레드가 무엇인지, 어디에서 구현하는지, 어떻게 스케줄링을 해야하는지에 대해서 알아볼 예정이다.

 우선 스레드와 프로세스를 비교해보자.

 프로세스는 컴퓨터에서 연속적으로 실행되고 있는 컴퓨터 프로그램이라면 스레드의 경우 프로세스 내에서 연속적으로 실행되고 있는 흐름을 말한다. 스레드는 하나의 프로세스 내부로 제한되어 있고, 프로세스는 여러 개의 스레드를 가지고 있을 수 있다. 하나의 프로세스 내부에 위치한 여러 개의 프로세스는 서로 자원을 공유하기도 하고, stack이나 register의 경우, 독립적으로 사용하기도 한다. 따라서 응답성과 효율성이 향상된다는 장점이 있지만, 자원을 공유하기 때문에 하나의 스레드에 문제가 발생하는 경우 전체 프로세스에 영향을 미칠 수 있다는 문제점이 있다.

 스레드를 여러 개 사용하는 것을 멀티스레드라고 하는데, 이 멀티스레드에도 여러 개의 모델이 존재한다. 각각에 대해서 구체적으로 살펴보면 다음과 같다.

• 커널 레벨 스레드

 커널 레벨 스레드란 스레드의 존재를 커널이 알고 있는 경우이다. 따라서, 커널 스레드 간의 switching은 작은 context switch를 필요로 하게 되고, 커널이 스레드를 관리하고 스케줄링한다. 커널이 제공하는 보안 서비스를 받을 수 있지만 상대적으로 커널의 비중이 커지기 때문에 시스템의 성능이 떨어질 수 있다는 단점이 존재한다.

• 유저 레벨 스레드

 유저 레벨 스레드란 운영체제가 스레드의 존재를 모르는 경우이다. 따라서 OS는 스레드를 직접 스케줄링하지 않게 된다. 프로그래머는 스레드 라이브러리를 통해 스레드를 관리할 수 있다. 따라서 context switch가 필요 없게 되고, 처리 속도가 빨라지게 된다. 그러나 OS는 유저 레벨 스레드의 존재를 알지 못하므로 좋지 않은 스케줄링 결정을 내리게 될 수 있다.

이번 시간에는 스케줄링에 대해서 공부해보도록 하겠다.

하나 이상의 프로세스를 동시에 운영하고자 할 때, CPU와 I/O에서는 오버랩이 발생할 수 있다. 따라서, 모든 프로세스는 OS에 의해서 관리되어야 한다.

커널은 인터럽트가 발생할 때, 프로세스가 생성 또는 종료될 때, 프로세스가 실행에서 대기 상태로 돌아갈 때 스케줄러를 동작한다.

이 때, Non-preemtive System의 경우 스케줄러는 해당 이벤트가 종료될 때까지 기다렸다가 동작하게 되고, Preemtive System의 경우 스케줄러가 실행중인 프로세스를 일시 정지하고 동작하게 된다.

스케줄링에는 다양한 알고리즘이 존재하고 이를 비교하기 위한 비교자는 다음과 같다.

• CPU Utilization (CPU 사용률) : 시스템 동작 시간 중 CPU가 사용된 시간을 측정하는 방법
• Throughput (처리량) : 단위 시간 당 작업을 마친 프로세스의 수
• Turnaround time (반환 시간) : 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는데 걸리는 시간
• Waiting time (대기 시간) : 프로세스가 CPU를 할당 받아 실행되기 전 대기 상태의 시간
• Response time (응답시간) : 대기 상태에 들어와 CPU를 최초로 얻기까지 걸리는 시간

이상적으로 CPU 스케줄러는 모든 조건이 최적인 경우가 가장 좋겠지만, 실제로는 가능하지 않다. 따라서 스케줄링 알고리즘은 스케줄링 정책에 부합하는 알고리즘으로 선택하도록 한다.

스케줄링 알고리즘의 종류는 다음과 같다.

• FCFS (First Come, First Served): State Queue에 먼저 도달한 프로세스에게 CPU를 할당하는 비선점형 방식이다.
• Round Robin : 프로세스에게 각각 동일한 time slice를 할당하여 이 시간 동안만 CPU를 이용하게 한다. 만약 할당 시간동안 처리를 다 하지 못하면 CPU는 다음 차례의 프로세스에게 넘어가게 된다. 이 알고리즘의 경우 모든 프로세스가 최초 응답 시간을 빠르게 보장받을 수 있다는 장점을 가진다.
• SJF (Shortest Job First) : 실행 시간이 가장 짧은 작업부터 CPU를 할당한다. 앞 순서에 실행 시간이 긴 프로세스가 있다면 오래 기다려야 하는 문제를 완화했지만, 시간이 짧은 프로세스가 계속해서 들어온다면 State Queue에서 영영 기다리게 되는 Starvation 문제가 발생한다.
• Multilevel Feedback Queue : Multilevel Queue의 경우 우선순위에 따라 여러 개의 Queue를 사용하는 방식으로 우선 순위가 높은 Queue에 먼저 CPU가 할당되는 방식이다. 각 Queue 내에서는 독립적인 알고리즘을 사용할 수 있다. 그러나 Multilevel Queue에서도 역시 공평성과 Starvation 문제가 발생하게 되는데 이를 해결한 것이 해당 알고리즘이다. 이와 같은 경우에는 한 번 CPU를 할당받은 프로세스는 우선 순위가 낮아지게 되고, 우선 순위가 낮은 큐로 이동하게 된다. 또한 우선 순위가 낮은 Queue에 time slice가 더 길게 주어지게 되는데 이는 공평성 문제를 해결하기 위함이다.

지난 시간에 이어, 이번 시간에는 프로세스에 대해 다뤄 볼 계획이다.

OS는 User의 프로그램, Command Script, System 프로그램 등 다양한 활동을 관리한다.

각각의 활동은 프로세스 내부에 캡슐화되어 있고 프로세스는 실행에 필요한 모든 정보와 execution context를 포함한다.

프로세스는 프로그램이 아니다. 프로세스는 실행 중인 프로그램의 한 인스턴스로 여러 프로세스가 하나의 프로그램을 실행할 수 있으며, 프로세스는 독립적인 entitiy다.

OS와 프로세스의 관계는 어떻게 될까?

OS는 프로세스를 생성/삭제하고, 중단/재개할 수 있다. 프로세스를 관리하고 스케줄링하며 프로세스 내부의 통신과 동기화에 관여하며 자원을 할당하는 것도 OS의 몫이다.

프로세스를 한 마디로 정리하면 다음과 같다.

실행 중인 프로그램의 dynamic execution context

여러 개의 프로세스가 동일한 프로그램을 실행할 수 있지만, 각각은 개별적인 다른 프로세스이며 개별적인 state를 가진다. 예를 들어 Word 프로그램을 동작시킨다고 가정해보면, 여러 개의 문서를 작성할 수 있지만 각각이 다른 state를 가지는 것을 알 수 있다.

그렇다면 프로세스의 state에는 어떤 것들을 포함할 수 있는지 알아보자.

프로세스의 state에는 최소한 다음과 같은 정보가 포함되어야 한다.

• 실행 중인 프로그램의 코드
• 실행 중인 프로그램의 static data
• 동적 데이터를 위한 공간(heap)과 heap pointer
• 프로그램 카운터 (PC) (다음 instruction을 가르킴)
• 프로그램의 call chain을 가진 execution stack과 stack pointer
• CPU 레지스터 값
• 사용 중인 OS resource set
• 프로세스 execution state

다른 것들보다 프로세스 execution state는 잘 와닿지 않을 것이다.

프로세스는 다음과 같은 state를 가진다.

각각의 state에 대한 자세한 설명은 아래와 같다.

1. new : OS가 프로세스의 state를 settting up한다.
2. running : instruction을 실행한다.
3. ready : 실행할 준비가 되었지만 CPU를 기다린다.
4. waiting : event가 완료될 때까지 기다린다.
5. terminated : 프로세스를 종료시킨다.

실행된 프로그램은 프로그램 action(system call 등), OS action(scheduling) 또는 external action(interrupt)의 결과로 state와 state 사이를 이동하게 된다. 또한 여러 프로세스를 제어할 때는 state queue를 활용하여 제어한다.

또한 프로세서를 제어하기 위해서 사용되는 OS의 자료 구조를 Process Control Block이라고 한다.

PCB는 프로세스의 현재 execution state를 추적한다.

OS는 프로세스가 생성될 때 PCB를 할당하고, 프로세스가 종료될 때 PCB를 해제한다. PCB에 반드시 포함되어야하는 데이터는 다음과 같다.

• 프로세스 state
• 프로세스 번호
• PC
• Stack Pointer
• Memory Magagement Information
• State queue의 Queue pointers
• ...

프로세스를 시작하고 종료하는 것을 Context Switch라고 한다. 즉 새로운 프로세스를 시작하기 위해서 현재 진행 중인 상태를 저장하고, 새로운 프로세스를 적재하는 것을 말한다.

OS는 PCB에서 하드웨어 레지스터를 로드하여 프로세스를 준비하고 시작한다. 프로세스가 진행될 때 CPU는 SP, PC, 레지스터 등을 변경하고, 프로세스가 종료될 때 현재 상태를 다시 해당 프로세스의 PCB에 저장한다.

이러한 프로세스의 switching이 바로 Context Switch이다.

또한 프로세스는 새로운 프로세스가 동작하도록 만들 수도 있다. 이러한 관계를 Parents와 Child라고 한다. 또한 Parents는 Child 프로세스를 종료시킬 수 있고, 공유 메모리를 통해 통신이 가능하다.

오늘 다룰 내용은 특히 System Call에 대한 내용이다. 또한, OS의 Structure, component와 organization에 대해서 언급하도록 하겠다.

System Call이란 지난 시간에 언급했던 것 처럼, 다음과 같이 정의할 수 있다.

OS에 의해 제공되는 서비스에 대한 요청에 따라 커널에 접근하기 위한 인터페이스

주로 C나 C++ 같은 고급 언어에 의해 사용되며, 직접적인 system call보다는 high-level API를 사용해서 접근하게 된다.

각각의 System call에는 주로 번호가 부여된다.

사용자는 실제로 System Call이 어떻게 동작하는지에 대해 알 필요가 없다. 많은 OS의 detail이 숨겨져 있으며, 사용자는 어떤 값이 return되는지만 정확히 알면 된다.

System Call이 parameter를 전달할 때는 총 세 가지 방법이 사용된다.

1. 가장 단순한 방법으로 register를 통해 전달한다. 다수의 parameter가 필요하다면 register의 크기는 매우 작기 때문에, 이러한 방법은 유용하지 않다.
2. memory 내부의 block에 parameter를 저장하고, 이 block의 주소를 register를 통해 전달한다. 주로 Linux에서 사용되는 방식이다.
3. Stack을 통해 전달한다.

다음으로, OS의 Structure에 대해 알아보자.

기본적인 OS Structure는 다음과 같다.

커널은 컴퓨터 하드웨어와 프로세스의 보안을 책임지는 부분이다. 커널이 주로 담당하는 기능은 프로세스 관리, 메모리 관리, 시스템 관리, 입출력 관리, 프로세스간 통신 관리 등이다. 커널의 기능은 복잡하게 얽혀있으므로, 커널이 기능적으로 어떻게 구성되어야 하느냐에 따라 종류가 다양하다.

종류에 대해서 알아보기 전에 Layered OS design에 대해서 먼저 언급하겠다.

Layered OS design에서 N번째 Layer는 N-1번째 Layer를 사용하게 되고, N+1번째 Layer에 새로운 기능을 제공한다.

해당 design의 장점과 단점은 다음과 같다.

• 장점 : 디자인하기 쉽고, 디버깅이 편리하다. 모듈성이 높고, 단순하며 이식성이 높다.
• 단점 : layer 차가 많이 나는 경우, communication이 어렵고 과도하게 데이터가 복사될 수 있다.

다시 돌아와서 커널의 종류에 대해 알아보자. 커널에 추가되는 feature의 양에 따라 다음과 같은 분류가 가능하다.

1. 단일형 커널(monolithic kernel) : 초창기의 운영체제 구조로, 핵심 기능을 구현하는 모듈들이 별도의 구분 없이 하나로 구성되어 있다. 초기 Unix 운영체제, Linux에서 사용되는 커널로, Application을 제외한 모든 기능들을 커널이 관리한다. 모듈 간의 통신 비용이 절감 된다는 장점이 있지만, 모든 모듈이 하나로 묶여 있기 때문에 버그를 처리하기 어렵고 각 기능이 서로 연결되어 상호 의존성이 높기 때문에 작은 결함 하나가 시스템 전체에 영향을 미칠 수 있다.
2. 마이크로 커널(microkernel) : Scheduling, Memory 관리 등의 주요 기능만을 커널에 담아 가볍게 만든 기능이다. 기존의 시스템 기능은 유저 프로세스에 존재한다. 장점은 시스템이 견고하고, customization이 쉽다.

이렇듯 OS 디자인에는 simplicity와 performance 사이에 tradeoff가 존재하고, 일반적으로는 simplicity에 집중하면 된다고 한다.

지난 시간, Introduction과 더불어 운영체제의 정의와 역사에 대해 알아보았다. 운영체제를 한마디로 정의한다면 다음과 같다.

"운영체제란 user와 architecture 사이의 interface다."

이번 시간에는 운영체제와 컴퓨터 구조에 대해서 살펴보자.

단순하게 나타낸 컴퓨터 구조는 다음과 같다.

컴퓨터는 CPU, Memory, I/O 장치, bus로 이루어져 있다. 각각에 대한 자세한 설명은 아래와 같다.

• CPU : 실제로 연산이 일어나는 프로세서 (최근에는 이 코어가 여러 개 있는 것이 대부분이다.)
• I/O device : terminal, disk, video board, printer, Network card와 같이 입력과 출력을 담당하는 장치
• Memory : CPU가 사용하는 프로그램과 데이터가 담긴 RAM (Random Access Memory; 임의의 영역에서 읽고 쓰기가 가능한 주기억 장치. 휘발성 메모리로 컴퓨터의 체감 속도를 좌우한다.)
• System bus : CPU, Memory, 주변기기들과 통신하는 매체

또한, 최근의 운영 체제는 다음과 같은 기능성을 가진다.

1. Process와 Thread에 의해서 manage된다.
2. Concurrency (동시성) : 동시에 다양한 업무를 수행할 수 있다.
3. I/O device : I/O device가 작동 중일 때, CPU의 작업 속도는 느려진다.
4. Memory management : OS는 메모리를 위치시키고, 주기억 장치와 디스크 사이에서 데이터를 이동시킨다.
5. Distributed Systems & Networks : 분산된 하드웨어에서 함께 업무를 처리할 수 있다.

OS service에서 동기 부여된 Architectural Feature는 다음과 같은데, 하나씩 자세하게 살펴보자.

• Protection

어떤 명령어들은 민감하기 때문에 권한이 필요하다. 이 때 두 가지 모드가 존재하는데, 바로 커널 모드와 유저 모드이다.

유저는 I/O를 직접 처리할 수 없다. / Memory 상태를 직접 조작할 수 없다. / interupt를 활성화하거나 비활성화 할 수 없다. / 기계를 중지시킬 수 없다. / 유저 모드와 커널 모드를 판별하는 mode bits를 설정할 수 없다.

그러나 커널모드에서는?

모두 가능하다. 위와 같이 보호된 명령어들이 커널모드에서는 모두 수행 가능하다.

이 커널 모드와 유저 모드 사이에서 인터페이스 역할을 하는 것을 'System Call'이라고 부른다.

또한 메모리도 보호할 수 있어야 한다.

메모리 보호는 컴퓨터 메모리의 사용을 제어하는 방법으로 실행하고 있는 프로세스가 자신에게 할당되지 않은 영역의 메모리에 접근하는 것을 막음으로써 보호가 가능하다.

• Register

Register는 일반적으로 현재 계산 중인 값을 저장하는 데 사용된다.

특히 Stack Pointer, Frame Pointer, Program Couter 등 특수 목적 Register의 경우, 프로그램의 상태를 저장한다.

Memory Hierarchy 상에서, Rigister는 최상위에 존재한다.

• Traps (a.k.a exception or fault)

Trap이란 예외 상태(page fault, read-only memory에 write, overflow, system call etc.)에 의한 비동기식 interrupt의 한 종류이다.

• I/O Control

I/O Method에는 3가지 방식이 있다.

1. Synchronous I/O : 데이터가 전송될 때까지 기다려야 하는 방식
2. Asynchronous I/O : 데이터의 전송을 마치기 전에, 프로세스가 계속하도록 허가하는 방식
3. Memory-mapped I/O : CPU가 입출력 장치에 접근할 때, 입출력과 메모리의 주소 공간을 분리하지 않고, 하나의 메모리 공간에 취급하여 배치하는 방식

• Virtual Memory

Virtual Memory는 RAM을 관리하는 방법 중 하나로, 각 프로그램에 실제 메모리의 주소가 아닌 가상의 메모리 주소를 할당하는 방식을 말한다. 가상 주소 공간은 MMU(Memory Management Unit)에 의해서 물리 주소로 변환된다. Virtual Memory를 통해 프로그래머는 프로그램이나 데이터가 주메모리에서 어떻게 동작하는지 의식할 필요가 사라졌다.

CS 377 Spring ‘14 Operating System

전체적인 Course의 Out line은 다음과 같다.

• Course Outline & Topics
  1. Process and Threads
  2. Memory Management
  3. Storage and File Systems
  4. Distributed Systems

Lecture 01. Introductions

Operating System의 정의

User와 Arichitecture 사이의 인터페이스 또는 Raw hardware보다 프로그래밍하기 쉬운 가상 머신

 즉, User와 Architecture 사이에서 architecture의 detail은 감추면서 동시에 보다 프로그래밍이 간편하게 만들어 주는 것이 Operating System이다.

Operating System의 특징

• Services: OS는 표준 서비스를 제공해야 한다.
  – Examples: the file system, virtual memory, networking, CPU scheduling, and time-sharing
• Coordination: OS는 여러 응용 프로그램과 사용자의 조절을 통해 공정성과 효율성을 갖춰야 한다.
  – Examples: concurrency, memory protection, networking, and security.
• Goal: 기계가 사용하기 편리하고 효율적이게 OS를 설계해야 한다.

Operating System의 역사

1. Sigle-User Computers : hardware의 가격은 비싸고, 인건비는 비교적 저렴했다. 컴퓨터는 한 번에 하나의 함수밖에 실행할 수 없었기 때문에 Overlap이 없었다. User는 Console에서만 Debugging을 할 수 있었다.
2. Batch Processing : 다양한 업무를 일괄적으로 처리하였다. (Scheduling은 당연히 인간이 해야했다.)
3. Overlap I/O and Computation : 비교적 새로운 방식이 적용되었다. Output 이전에 buffer 단계를 추가하였고, I/O event의 경우, interrupt를 통해 처리할 수 있게 만들었다. 그러나 여전히 한 번에 하나의 업무만 수행할 수 있었다.
4. Multiprogramming : 몇 개의 프로그램이 동시에 수행가능하게 되었다. 또한, scheduling이 OS에 의해 수행되었다.

점차 functionality와 complexity가 증가하였고, OS design에서 complexity를 다루는 것이 중요해졌다. 그리고 이 후, 70년대로 들어서면서 Renaissance를 맞이하게 된다.

• The Renaissance (1970's) : hardware의 가격이 저렴해지고, 인건비가 더 비싸졌다. User는 terminal을 통해 system을 공유하였다. 또한 대부분의 현대적인 OS의 원형이 된 UNIX가 출시되었다. Multics가 그 기원으로, Shell을 통해 사용자 인터페이스를 제공하였다. 그러나 response time과 thrashing(; 메모리 영역에 접근할 때, 메모리에 page fault가 높은 것) 문제가 있었다.
• Industrial Revolution (1980's) : hardware의 가격이 매우 저렴해졌다. PC의 사용이 늘어났다. (1981년 IBM PC, 1984년 Macintosh) DOS, MacOS 등 비교적 단순한 OS가 출현하였고, GUI가 추가되었다.
• The Modern Era (1990's - now) : 요구되는 processing이 더욱 증가하였고, 실질적인 OS가 개발되었다. 다양한 조건에 맞춘 OS가 출시되었다.