Lemonyun

Race Condition

storage를 공유하는 둘 이상의 입력이 있는 경우 발생할 수 있음

1. 여러개의 CPU가 메모리에 접근하려는 경우

2. 공유 메모리 주소 공간에 여러개의 Process가 접근하려는 경우

구체적인 상황

1. 프로세스 A에서 커널의 코드가 실행중(커널의 데이터를 쓰는 중)에 인터럽트가 발생하여 프로세스B로 넘어가고 B에서 커널의 코드가 실행되어 커널 주소공간의 커널의 데이터를 쓰는 경우

ㄴ 커널의 데이터를 쓰는동안 interrupt를 비활성화하는 방법으로 해결

2. 프로세스 A에서 커널의 코드가 실행중인데 타이머 interrupt로 인해 context switching이 일어나는 경우

ㄴ 커널모드가 끝날때까지 기다렸다가 CPU를 뺏는 방법

Critical Section(임계 구역)

공유 데이터를 접근하는 코드

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

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

1. mutual exclusion

ㄴ 한 프로세스가 자원을 쓰고 있으면 다른 프로세스는 들어오면 안됨

2. progress

ㄴ 자원을 아무도 안 쓰고 있으면 들어가야 함

3. bounded Waiting

ㄴ 기아가 되는 프로세스가 없어야 함

소프트웨어적 해결

 Peterson's Algorithm -> Busy waiting (무한반복문 대기 : CPU와 메모리를 쓰면서 wait)

하드웨어적 해결

읽기와 쓰기를 한번에 하는(atomic) Test_and_set instruction을 사용하면 됨

세마포어

추상 자료형

세마포어 변수는 정수값을 가짐 (남아 있는 자원의 개수)

세마포어 변수에 대해서 P 연산 V 연산을 수행할 수 있음 P(s)는 자원을 하나 가져가는 것 V(s)는 자원을 하나 반납하는 것

P 연산과 V 연산의 구현은 시스템에 따라 다르게 구현될 수 있는데, 앞서 말했던 busy waiting 방식과 block & wakeup 방식이 있다. block & wakeup 방식은 기다리는 프로세스를 커널 데이터에 구현되어 있는 Resource queue로 보내 block(sleep)되게 하는 것임

일반적으로는 block/wakeup 방식이 좋지만 critical section의 길이가 매우 짧은 경우 busy-wait 오버헤드보다 block/wakeup 오버헤드가 커지는 경우도 있다.

Counting semaphore

ㄴ 0이상의 정수 값을 가짐

ㄴ resource counting에 사용

Binary semaphore (=mutex)

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

ㄴ 주로 lock unlock에 사용

세마포어를 이용해서 프로그래밍 할 때 프로그래머 논리적으로 코딩하지 않으면 deadlock 문제가 생길 수 있음

현대의 CPU는 Preemptive 스케줄링(CPU 자원을 뺏을 수 있는)이며 Round Robin 방식을 사용한다.

스케줄링 알고리즘은 multilevel feedback queue 방법을 사용한다.

Multi level feedback queue

CPU ready queue를 여러개 두는 방법, 각 큐마다 priority가 달라 우선순위가 높은 큐에 들어온 프로세스가 먼저 처리됨

CPU burst 시간이 긴 프로세스들은 특정 기간 내에 작업이 끝나지 않아 priority가 더 낮은 큐로 강등당함

I/O burst 시간이 긴 대화형 작업들은 강등당하기전에 끝나기 때문에 보통 빠른 시간내에 결과를 받을 수 있다.

Starvation 문제가 있다. -> 주기적으로 모든 프로세스를 가장 높은 우선순위의 큐로 이동시키는 방법으로 해결

다양한 변수 설정이 가능하다.

1. 사용할 큐의 개수

2. 큐당 타임슬라이스의 크기

3. 우선순위 상향 조정 기간

CPU가 여러개인 경우의 스케줄링

1. Homogeneous Processor인 경우

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

2. Load sharing

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

3. Symmetric Multiprocessing

ㄴ 각 프로세서가 각자 알아서 스케줄링을 결정

4. Asymmetric Multiprocessing

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

스레드 스케줄링

Local Scheduling

ㄴ 유저 레벨 스레드의 경우 사용자 수준의 스레드 라이브러리에 의해 어떤 스레드를 스케줄할지 결정

Global Scheduling

ㄴ 커널 레벨 스레드의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 스레드를 스케줄할지 결정

스케줄러의 종류

1. Long-term scheduler

ㄴ 어떤 프로세스를 메모리에 올릴 것인가?

2. Short-term scheduler

ㄴ 어떤 프로세스에게 CPU 제어권을 줄 것인가?

3. medium-term scheduler(Swapper)

ㄴ 어떤 프로세스를 swap area로 빼고 올릴 것인가? (Suspended된 프로세스를 먼저 뺀다)

ㄴ degree of multiprogramming을 제어

부모 프로세스가 자식 프로세스를 생성할 때 자식은 부모의 주소 공간을 복사함 (fork)

자식은 그 공간에 새로운 프로그램을 올림 (exec)

Copy-on-write : 자식 프로세스는 부모 프로세스의 code data stack을 쓰다가 write이 발생했을 때, 부모의 code data stack의 필요한 부분을 복제하여 메모리에 올린다.

프로세스 관련 시스템 콜

fork() -> 복제

exec() -> 덮어 쓰기

exit() -> 프로세스의 종료. 자식 프로세스의 경우 부모 프로세스엑 output data를 보냄 

abort() -> 부모가 자식을 강제 종료

ㄴ 자식이 자원의 할당 한계치를 넘어서는 경우

ㄴ 자식이 더 이상 필요 없는 경우

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

wait() -> 부모 프로세스에서 실행하면 Child Process가 종료될 때 까지 block(sleep)상태로 대기, 종료되면 ready상태

프로세스간 자원의 공유

메세지를 전달하는 방법 : message passing : 커널을 통해 메세지 전달

주소 공간을 공유하는 방법 : shared memory : 서로 다른 프로세스 간에도 일부 주소공간을 공유

스레드

스레드는 프로세스 하나에 CPU 수행단위를 여러개 두는 것이다.

스레드는 같은 프로세스의 다른 스레드와 프로세스의 code, data, os 자원을 공유한다. (= task)

프로세스 주소 공간 내부에 각각의 스레드별로 스택이 존재한다. PCB에도 각각의 스레드를 위한 PC 및 다른 레지스터 값들에 대한 정보를 담고 있다.

스레드의 장점

1. 하나의 스레드가 Blocked 상태인 동안에도 동일한 task 내에 다른 스레드가 실행(running)되어 빠른 처리를 할 수 있다.

2. 병렬성을 높일 수 있다. -> CPU가 여러개인 경우 여러개의 CPU에서 스레드가 병렬적으로 실행될 수 있다.

3. 메모리 낭비를 줄일  수 있다. -> 동일한 작업을 스레드가 아닌 프로세스 단위로 나누면 code data 부분이 중복되기 때문에

4. 비용적으로 좋다. -> 프로세스간의 CPU switching보다 스레드간의 CPU switching이 더 빠르다. 바꿔줘야 할 문맥이 적기 때문에

커널 스레드와 유저 스레드

커널 스레드: 운영체제가 스레드를 지원, 스레드 스케줄링을 커널에서 지원

유저 스레드: 운영체제는 스레드의 존재를 모름, 유저 라이브러리를 사용하여 알아서 처리

프로세스는 0번지부터 시작하는 자기 자신만의 독자적인 주소 공간을 가진다 (stack, data, code)

가상 메모리 주소를 physical memory 주소로 변환(mapping)하는 하드웨어는 MMU(memory management unit)이다.

MMU는 CPU 안에 있으며 base레지스터(접근할 수 있는 물리적 메모리 주소의 최소값)의 값과 limit 레지스터(논리적 주소의 범위)의 값을 이용하여 주소를 변환한다.

여기서 인터럽트 처리 코드는 시스템 콜에 의해 호출되는 인터럽트 처리 함수를 말한다.

어떤 프로세스가 커널을 요청을 할때 커널 함수가 호출 되는데 중간에 context 스위칭이 일어날 수도 있으므로 

프로세스마다 커널 스택이 필요하다. 이들은 커널 프로그램 stack 영역에 저장된다.

PCB

운영체제는 새로운 프로세스를 만들때 PCB를 만들고 모든 프로세스들의 PCB는 커널 프로세스 data 영역에 보관된다.

PCB가 저장하는 정보

1. 관리상 사용하는 정보

PID, process state, priority, 스케줄링 정보

2. CPU 수행 관련 하드웨어 값

PC 레지스터 값 같은거

3. 메모리 관련

code, data, stack 의 위치 정보

4. 파일 관련

파일 서술자

프로세스 상태

1. Running

프로세스가 CPU를 점유하고 있는 상태

CPU 스케줄러에 의해 ready queue에서 특정한 프로세스를 지정

2. Ready 

Running 상태에서 CPU 할당시간이 끝나 Timer 인터럽트에 의해 점유를 뺏기는 경우 (preempted)

I/O 요청을 기다리던중 (Block) I/O 끝났다는 인터럽트를 받은 경우

3. Blocked (wait)

CPU가 있어도 instruction을 수행 할 수 없는 상태 (I/O 작업중 이거나, 프로세스 Code 부분이 메모리에 올라와 있지 않은 경우)

block된 프로세스들은 device 큐와 ready 큐에서 관리된다.

커널 data 영역에 disk I/O queue, 공유 데이터에 대한 resource queue, cpu ready queue 등이 존재하는데 blocked된 프로세스들은 PCB 링크드 리스트로 구현되어 있다.

4. Suspended (inactive 상태)

프로세스가 통째로 swap area로 swap out 된 상태

외부에서 resume 명령을 해주어야 살아난다.

사용자가 직접 프로세스를 정지 시킬 수도 있다.

CPU

cpu는 프로그램 카운터 레지스터가 가리키는 주소(main memory상)에 존재하는 instruction을 매 clock 읽는다.

Timer

특정 프로그램이 CPU를 독점하는 것을 막기 위한 하드웨어

CPU 스케줄러에 의해 새로운 프로세스가 CPU 제어권을 얻을 때 운영체제는 Timer에 시간을 기록하게 되는데, 이 시간은

cpu clock 마다 줄어드며 이 값이 0이되면 인터럽트를 발생시켜 CPU 제어권을 빼앗는다. (preemptive)

다중 프로그래밍을 위해 존재한다.

modebit

modebit : 0 ---> 커널모드

modebit : 1 ---> 유저모드

인터럽트나 예외 발생시 하드웨어가 modebit를 0으로 바꾼다.

운영체제 프로그램이 CPU를 점유하고 있으면 0, 사용자 응용 프로그램이 CPU를 점유하고 있으면 1의 값을 가진다.

커널 모드에서는 모든 instruction을 수행 할 수 있고

유저 모드에서는 한정된 instruction만을 수행 할 수 있다.

I/O 장치에 대한 접근과 같은 중요한 instruction을 사용자 응용 프로그램이 직접적으로 사용할 수 있게 하는 대신에 

사용자 프로그램이 소프트웨어 인터럽트(트랩)을 발생시켜 운영체제가 임무를 수행하도록 한다.

Interrupt line

인터럽트 발생여부를 확인하기 위한 일종의 배열? 매 클럭마다 체크하여 인터럽트 발생했으면 mode bit 0으로 바꾸고 

운영체제에 제어권을 넘긴다.

DMA controller

I/O 장치에 의해 interrupt가 너무 잦아 CPU의 성능이 떨어지기 때문에 DMA가 I/O 장치들의 local buffer 내용을 직접 메모리에 복사 할 수 있도록 함. I/O 로컬 버퍼에 페이지 단위 크기의 데이터가 쌓이면 그때 한번에 interrupt를 검

Memory controller

CPU와 별개로 메모리에 I/O local buffer 내용을 쓰는 DMA controller와 CPU가 동시에 메모리에 쓰지 않도록 관리

메모리 장치의 주소에 대한 읽기 쓰기 작업 관리

Device controller

device를 전담하는 작은 cpu 역할

응용 프로그램에서 I/O 처리 과정

1. 응용 프로그램에서 System Call을 한다 (커널 함수 호출)

2. 실행 중이던 프로세스 현재 상태를 저장한다.

3. 메인 메모리 커널의 Code 부분에 올라와 있는 인터럽트 벡터에 접근 (시스템 콜 번호에 따라 인덱스로 접근)

4. 해당 벡터 원소가 가리키는 인터럽트 처리 루틴 정의부로 이동

5. 운영체제는 올바른 요청인지 확인 후 I/O 컨트롤러에 요청

6. 아까 저장했던 프로세스 상태 복구

같은 종류의 코인으로 이미 계산된 dp 테이블 값을 중복으로 계산하는 것을 주의하자

C++ 스킬 35: typename과 class 키워드의 차이를 이해하자

C++ 스킬 36: 매개변수에 독립적인 코드는 템플릿으로부터 분리시키자

C++ 스킬 37: 타입 변환이 바람직할 경우에는 비멤버 함수를 클래스 템플릿 안에 정의해 두자

C++ 스킬 38: 특성 정보 클래스를 만들 때 오버로딩을 사용하는 방법이 있다.

C++ 스킬 39: 템플릿 메타 프로그래밍 (template metaprogramming : TMP) 을 알아두자