문제

https://www.acmicpc.net/problem/1620

안녕? 내 이름은 이다솜. 나의 꿈은 포켓몬 마스터야. 일단 포켓몬 마스터가 되기 위해선 포켓몬을 한 마리 잡아야겠지? 근처 숲으로 가야겠어.

(뚜벅 뚜벅)

얏! 꼬렛이다. 꼬렛? 귀여운데, 나의 첫 포켓몬으로 딱 어울린데? 내가 잡고 말겠어. 가라! 몬스터볼~

(펑!) 헐랭... 왜 안 잡히지?ㅜㅜ 몬스터 볼만 던지면 되는 게 아닌가...ㅜㅠ

(터벅터벅)

어? 누구지?

오박사 : 나는 태초마을의 포켓몬 박사 오민식 박사라네. 다솜아, 포켓몬을 잡을 때는, 일단 상대 포켓몬의 체력을 적당히 바닥으로 만들어놓고 몬스터 볼을 던져야 한단다. 자, 내 포켓몬 이상해꽃으로 한번 잡아보렴. 포켓몬의 기술을 쓰는 것을 보고 포켓몬을 줄지 안줄지 결정을 하겠네. 자 한번 해보아라. 다솜아.

이다솜 : 이상해꽃이라...음.. 꽃이니깐 왠지 햇빛을 받아서 공격을 할 것 같은데... 음... 이상해꽃! 햇빛공격!!!

(꼬렛이 이상해꽃에게 공격을 받아 체력이 25 감소했다.)    가라! 몬스터 볼!!!    (꼬렛을 잡았습니다.)    야호! 신난다. 꼬렛을 잡았다.

오박사 : 오우!! 방금 쓴 공격은 솔라빔이라고 하네.. 어떻게 공격을 한 건가? 솔라빔이란 공격에 대해서 공부를 한 건가?

이다솜 : 꽃이니깐 왠지 햇빛을 제대로 받으면 광합성을 해서 음.. 그냥 그럴 것 같아서요 ☞☜

오박사 : 다른 아이들은 넝쿨채찍이나, 나뭇잎 공격을 하는데, 다솜이는 역시 뭔가 다르구나. 그럼 나와 함께 연구소로 가자꾸나. 내가 포켓몬을 한 마리 줄 테니, 너의 꿈을 펼쳐보아라. 꿈은 이루어진단다.

이다솜 : 네! 오박사님, 고마워요.ㅜㅜ

오박사 : 가자. 나의 연구소는 너의 옆집의 아랫집이란다. 같이 가도록하자. 지금 포켓몬을 주마.

이다솜 : 네. 야호!!

'

오영식 : 어? 오박사님 얘는 누구인가요?

오박사 : 얘는 너의 라이벌이 될 친구 이다솜이라고 하네. 자, 포켓몬을 한 마리 골라보도록 해봐라 다솜아. 레이디퍼스트 네가 먼저 골라봐라.

이다솜 : 저는 생각해둔 포켓몬이 있어요. 피카츄 골라도 될까요?

오박사 : 그래 여기 피카츄가 한 마리 있단다. 피카츄를 가져가거라.

오영식 : 그럼 저는 이브이를 가져가겠어요. 그럼 나중에 보자 이다솜.

이다솜 : 그럼 꼬렛을 다시 잡으러 가야겠다. 영식아, 그리고 민식박사님 빠잉!

이다솜 : 피카츄 공격!

가라 몬스터 볼!

이다솜 : 야호! 신난다. 꼬렛을 잡았다!!!!!

이다솜 : 그럼! 일단 사천왕을 이기고 오겠어!

이다솜 : 여기가 사천왕과 대결하려면 가야하는 곳인가..

경비원 : 사천왕과 대결을 하려면, 마을의 체육관 리더를 이겨서 배지를 8개를 모아야 한다네... 배지를 모아서 오도록 하게

이다솜 : 잉ㅠㅜ... 그럼 배지부터 모아야 하는구나ㅠㅜㅠㅜ 나쁘당 그냥 좀 봐주지..

<1 년 후>

그동안의 줄거리 : 이다솜은 일단 상록 숲의 체육관 리더에게 도전을 했다. 하지만 상록숲 체육관의 리더는 실종된 상태. 따라서 회색마을부터 도전하기로 했다. 체육관의 리더를 이기면서, 로켓단을 해체시키기도 하고, 여러 가지 사건도 있었다. 결국 전설의 포켓몬도 잡고, 이제 사천왕을 이기려고 도전하기로 했다. 사천왕은 모두 가볍게 이기고, 이제 마지막 라이벌 오!영!식! 이다.

오영식 : 훗. 1년 전의 그 이다솜이 사천왕을 이기고 현재 포켓몬 마스터인 나에게 덤벼? 어디 한번 덤벼보시지.

이다솜 : 헐랭... 나를 우습게보네.... 한번 두고 보시지! 그럼 대결이닷!

이다솜 : 휴... 이겼다.

오영식 : 내가 지다니 분하다. ㅜㅜ

오박사 : 그럼 다솜아 이제 진정한 포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라. 일단 네가 현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라. 나의 시험을 통과하면, 내가 새로 만든 도감을 주도록 하겠네.

출력

첫째 줄부터 차례대로 M개의 줄에 각각의 문제에 대한 답을 말해줬으면 좋겠어!!!. 입력으로 숫자가 들어왔다면 그 숫자에 해당하는 포켓몬의 이름을, 문자가 들어왔으면 그 포켓몬의 이름에 해당하는 번호를 출력하면 돼. 그럼 땡큐~

이게 오박사님이 나에게 새로 주시려고 하는 도감이야. 너무 가지고 싶다ㅠㅜ. 꼭 만점을 받아줬으면 좋겠어!! 파이팅!!!

코드

import sys
input=sys.stdin.readline
n, m=map(int, input().split())
dic={}
dic2={}

for i in range(n):
    name=input().strip()
    dic[name]=(i+1)
    dic2[i+1]=name

for i in range(m):
    action=input().strip()
    if action.isdigit()==True:
        print(dic2[int(action)])
    if action.isalpha()==True:
        print(dic[action])

문제해결

문제가 길어서 그렇지 딕셔너리를 이용하면 복잡한 문제를 쉽게 해결할 수 있다.

입력 받은 값이 정수인지 확인하는 isdisit()함수와 문자인지 확인하는 isalpha() 함수를 이용하면

생각보다 쉽게 코드작성을 할 수 있다.

문제

https://www.acmicpc.net/problem/1476

코드

import sys
input=sys.stdin.readline

e, s, m= map(int, input().split())

year=s
if e==15: e=0
if s==28: s=0
if m==19: m=0

while True:
    if year%15==e and year%28==s and year%19==m:
       print(year)
       break
    else: year +=28

문제 해결

브루트포스 알고리즘을 활용하여 주어진 조건을 만족하는 가장 빠른 연도를 출력하면 된다.

여기서 제일 중요한 부분은 (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)이 이렇게 범위를 갖기 때문에 

주의해서 문제를 풀어야한다. 

문제

https://www.acmicpc.net/problem/1463

import sys
input=sys.stdin.readline

dp=[0]*((10**6)+1)

n=int(input())
for i in range(2, n+1):
    dp[i]=dp[i-1]+1
    if i%2==0:
        dp[i]=min(dp[i], dp[i//2]+1)
    if i%3==0:
        dp[i]=min(dp[i], dp[i//3]+1)

print(dp[n])

Semaphore

• semWait : Process 를 Block 시킬 수 있는 명령어이다.
• semSignal : 내가 아니라 Queue에 있는 프로세스를 Ready로 옮겨 실행할 수 있게 해준다.

Semaphore는 Critical Section뿐 아니라, 많은 동기화 문제에 사용된다.
↳ 특히 Critical Section을 다룰 때는 무조건 초기 세마포 변수 값을 1로 설정해야 한다!

• Race Condition : 실행 순서에 따라 결과가 어떻게 될지 모르는 상황
  → 여러 프로세스가 Critical Section 을 동시 접근할 때 발생한다.

어느 위치에 semWait과 semSignal를 사용할지 잘 선택해야 한다.

Mutual Exclusion Using Semaphore

하늘색 네모 부분은 해당 프로세스가 Blocked Queue 에서 대기하고 있다는 의미이다.

세마포 방과 문에 비유하기

step1

여러 프로세스들이 Critical Section에 진입하려고 문에 서 있다고 가정해보자.

step2

Process 2가 먼저 문을 열고 Critical Section에 들어가서 문을 닫아버리고 s 값을 0으로 바꾼다.
이후 접근하는 프로세스들은 s 값이 음수가 되기 때문에 Blocked Queue에 들어가서 대기하게 된다.

• s <= 0 : 문이 닫힌 상태
• s > 0 : 문이 열린 상태

step3

Process2가 Critical Section 실행을 마친 후,
나갈 때 semSignal 명령어를 통해 대기하던 프로세스를 문 안으로 데려온다.
s > 0 (s == 1) 이되면, 문이 다시 열리는 것을 의미한다.

Semaphore는 좋은 도구인가?

1. Mutual Exclusion O
2. Deadlock X
3. Livelock X
4. Busy-Waiting X
5. Starvation △
   • Strong Semaphore X (Queue 순서대로 진행)
   • Weak Semaphore O

Binary Semaphore Primitives

지금까지 진행했던 Semaphore 는 Counting Semaphore 이다.
Binary Semaphore는 Semaphore 값을 0 아니면 1만 설정 가능하다.

Binary Semaphore는 작은 group의 문제들을 해결할 수 있다.

semWaitB

Binary Semaphore 에서는 Semaphore 값 S가 0이 되면 무조건 Block을 시킨다.
→ 몇 개가 block 되어 있는지는 알 수 없다.

semSignalB

Queue에서 프로세스를 꺼낼 때 Semaphore 값 S를 보고는 몇개의 프로세스가 Queue에 있는 지 알 수 없다.
⇒ Queue 자체를 확인한다. → isEmpty()

Buffer

Producer Process

데이터를 생성해서 Buffer에 쓴다.

Consumer Process

Buffer에서 데이터를 읽어서 작업한다.

Producer Process와 Consumer Process는 한 번에 하나만 Buffer에 접근할 수 있다!

위의 버퍼를 I/O Buffer라고 가정하자.
Memory Data → I/O buffer → I/O Device 출력

두 Producer Process 가 동시에 버퍼에 접근하여 데이터를 쓸 수 있고, 두 Concumer Process가 동시에 버퍼에 접근하여 데이터를 출력할 수 있다.
이렇게 프로세스가 동시에 버퍼에 접근하는 문제는 Critical Section 해결 방법과 동일하게 해결할 수 있다!

동시 buffer 접근 문제

Critical Section 해결 방법과 동일하게 해결할 수 있다!

Buffer가 비어 있는 문제

Consumer Process 가 Buffer에서 데이터를 가져갈 수 없다.

Buffer의 크기 제한

Producer Process 가 Buffer에 데이터를 쓸 수 없다.

⇒ Buffer의 크기 문제를 해결해야 한다!

Producer/Consumer Problem

1. 보통의 상황:
   • Producer는 데이터를 생성하고 buffer 에 데이터를 놓는다.
   • Consumer 는 buffer에서 item을 가져간다.
   • 오직 한번에 하나의 Producer나 Consumer만 buffer에 접근할 수 있다.
2. 문제:
   Producer가 꽉찬 buffer에 데이터를 추가하지 못하거나 Consumer가 비어있는 buffer에서 데이터를 가져가지 못하는 상황

Bounded Buffer

처음엔 버퍼가 비어 있다.

In

Producer Process가 다음에 Data를 쓸 위치

Out

Consumer Process가 다음에 Data를 읽을 위치

in > out

out > in

위의 그림에서 아래 그림으로 바뀌는 동안, Producer 는 b[5] 부터 한바퀴를 돌아 b[2]까지 데이터를 쓴 것이고, Consumer는 b[4]까지 데이터를 읽은 것이다.

Buffer 가 비었을 때?

in == out → 데이터가 빈 것이라고 볼 수 있다.

Buffer 가 꽉찼을 때?

in == out → 데이터가 꽉 것이라고 볼 수 있다.

⇒ 그렇다면 어떻게 Buffer가 비고 꽉찼는지 구분할 수 있을까?
↳ 버퍼가 꽉차기 전에 버퍼 하나를 비워둔다.

⇒ 즉, in == out-1 → 버퍼가 꽉 찼다고 인식한다.

Funcions in a Bounded Buffer

Producer

• (in + 1) % n == out → Buffer가 가득찬 상황이므로 while문에 걸린다.
• 그 밖의 경우에는 buffer에 데이터 값을 넣고 in값을 하나 증가시킨다.

Consumer

• in == out → Buffer가 빈 상황이므로 while문에 걸린다.
• 그 밖의 경우에는 buffer에서 데이터를 읽고 out 값을 하나 증가시킨다.

Busy-Waiting O & Buffer 1개 낭비

좋은 Solution이 아니다.
⇒ Semaphore 를 이용해서 해결하자

Bounded Buffer using Semaphores

• semWait : 상황에 따라 프로세스를 기다리게 한다.
• semSignal : 상황에 따라 기다리고 있던 프로세스를 풀어준다.

프로세스가 기다려야 하는 상황 3가지

1. Producer Process의 입장에서 buffer가 가득 찼을 때
2. Consumer Process의 입장에서 buffer가 비었을 때
3. Producer Process와 Consumer Process가 Critical Section에 진입할 때 → 한 번에 하나만 접근해야하므로 기다려야 한다.

Producer Process, Consumer Process, Critical Section 의 Blocked Queue를 하나로 관리하지 않는다.
⇒ 3개의 Queue에서 3개의 Semaphore를 관리해야 한다.

Semaphores Logic

1. 프로세스가 기다려야 하는 상황을 생각해야 한다. (n개)
2. n → 같은 Queue에서 기다려도 되는 프로세스들인지 판단하여 필요한 Queue의 개수를 판단한다.

Semaphore를 사용한 Buffer 관리 코드

/* program boundedbuffer */
const int sizeofbuffer = /* buffer size */;
semaphore s = 1, n = 0, e = sizeofbuffer;
void producer()
{
	while(true) {
    	produce();
        semWait(e);
        semWait(s);
        append();
        semSignal(s);
        semSignal(n); // 버퍼에 데이터가 하나 증가한다. + blocked된 Consumer가 있으면 다시 Ready 상태로 깨워준다.
    }
}
void consumer()
{
	while(true) {
    	semWait(n);
        semWait(s);
        take();
        semSignal(s);
        semSignal(e); // 버퍼에 데이터가 하나 지워진다. + blocked된 Procuder가 있으면 다시 Ready 상태로 깨워준다.
        consume();
    }
}
void main()
{
	parbegin(producer, consumer); // 여러개의 producer들과 consumer 들이 함께 작업한다.
}

producer()

semSignal(n)의 의미:
버퍼에 데이터가 하나 증가한다. + blocked된 Consumer가 있으면 다시 Ready 상태로 깨워준다.

consumer()

semSignal(e)의 의미:
버퍼에 데이터가 하나 지워진다. + blocked된 Procuder가 있으면 다시 Ready 상태로 깨워준다.

즉, Producer와 Consumer는 서로 blocked 된 프로세스를 깨워준다.

Semaphore를 사용한 Buffer Logic

세개의 Semaphore 를 사용한다.
→ n, e, s
⇒ Semaphore 값이 어떻게 변하는지 알아야 한다.

s

Critical Section 처리 Semaphore

Critical Section에 여러 프로세스가 들어가려고 대기하면, s 값이 음수가 될 수 있다.

e

초기값: 버퍼의 크기

어느 순간 버퍼에 있는 빈칸의 수

• e > 0: 쓸 수 있는 버퍼의 수
• e <= 0: 버퍼가 꽉차, 버퍼에 데이터를 쓰기 위해 Blocked queue에서 대기 중인 Producer Process의 수

n

초기값: 0

어느 순간 버퍼에 있는 데이터의 개수

• n > 0: 읽을 수 있는 데이터의 수
• n <= 0: 버퍼가 비어있어, 버퍼의 데이터를 읽기 위해 Blocked queue에서 대기 중인 Consumer Process의 수

n+e

버퍼의 크기 (단, n > 0, e > 0 ⇒ blocked queue에 프로세스가 대기 중이지 않은 경우만 성립한다.)

n == 0 → 버퍼가 비었다.
e == 0 → 버퍼가 가득 찼다.

Q. 코드 순서를 변경할 때, 문제가 발생할 수 있다.

/* program boundedbuffer */
const int sizeofbuffer = /* buffer size */;
semaphore s = 1, n = 0, e = sizeofbuffer;
void producer()
{
	while(true) {
    	produce();
        /*순서 교체*/
        semWait(s);
        semWait(e);
        /*순서 교체*/
        append();
        semSignal(s);
        semSignal(n); // 버퍼에 데이터가 하나 증가한다. + blocked된 Consumer가 있으면 다시 Ready 상태로 깨워준다.
    }
}
void consumer()
{
	while(true) {
    	/*순서 교체*/
        semWait(s);
        semWait(n);
        /*순서 교체*/
        take();
        semSignal(s);
        semSignal(e); // 버퍼에 데이터가 하나 지워진다. + blocked된 Procuder가 있으면 다시 Ready 상태로 깨워준다.
        consume();
    }
}
void main()
{
	parbegin(producer, consumer); // 여러개의 producer들과 consumer 들이 함께 작업한다.
}

코드 순서를 변경할 때, 숫자 값의 변화는 없어도, Deadlock이 발생할 수 있다.
semWait(e) ↔ semWait(s) 이나 semWait(n) semWait(s) 를 바꾸는 경우 문제 발생

1. buffer가 어떤 상황일 때 어떤 순서로 producer와 consumer가 도착했을 때 Deadlock이 발생하는가?
   → 2가지 case가 존재한다.
2. 시스템이 Semaphore 제공 X → hardware instruction으로 구현해야 한다.
   → hardware instruction으로 buffer 문제 해결이 가능한가?
   → 가능하다면, 어떻게 구현해야하는가? swap&compare, exchange가 몇 개 필요한가?

Requirements for Mutual Exclusion

Mutual Exclusion

Mutual Exclusion : 전체 코드가 아닌, Critical Section code 가 한 번에 하나의 프로세스만 실행할 수 있도록 하는 것.

Mutual Exclusion 은 어떠한 경우에도 지켜져야 한다.
오직 하나의 프로세스만 Critical Section 의 자원에 접근할 수 있다.

→ Critical Section Code 가 아닌 코드는 막 섞여서(interleaving, overlapping) 실행되어도 상관 없다.

Critical Section Code 와 Non-Critical Section Code 가 섞여 실행되는 것도 상관 없다.
⇒ Non-Critical Section Code 와 Critical Section Code 가 서로 때문에 정지하는 일은 없어야 한다.

Dekker와 Peterson의 알고리즘은
DeadLock X
Starvation X
LiveLock X

→ 하지만 DeadLock, Starvation, LiveLock이 발생해도 사용해야하는 경우가 존재한다.

Critical Section 을 사용하는 다른 프로세스가 없을 때, Critical Section 에 대한 액세스를 지연시켜서는 안 된다.

(Solution 1처럼)

프로세스의 상대적 속도 가정 의미 X

프로세스의 상대적 속도를 가정하면 안된다. (Solution4와 같이)
↳ 해법 X, 프로세스는 CPU가 있는지 없는지 신경쓰지 않는다.
⇒ 얼마나 기다릴지 모르기 때문에 몇 초를 기다린다는 말은 의미가 없다.

몇초 기다릴지 각 프로세스마다 부여 받아도, Ready Queue로 들어가게 되면,
원래 몇초 기다릴지 부여 받은 초보다 더 오래 기다릴 수도 있고,
먼저 CPU를 받은 프로세스가 먼저 다시 Running 하게 된다.

프로세스의 개수 가정 의미 X

Dekker와 Peterson 알고리즘은 2개의 프로세스 일 때를 가정한 것이다.
⇒ General한 Solution은 이러한 가정을 두면 안된다.

프로세스는 Critical Section 안에 유한한 시간 동안만 남아있는다.

무한루프 돌면 안된다.

한 번에 하나의 프로세스만을 실행할 건데, DeadLock X, LiveLock X, Starvation X, 어떠한 가정도 X
⇒ 문제 해결 방안 찾기!

Approaches for Mutual Exclusion

Software approaches

1. Dekker's algorithm
2. Peterson's algorithm

Hardware approaches
An approaches using the special-purpose machine instruction

1. Compare_and_swap instruction
2. Exchange instruction

starvation 이 발생할 가능성이 있다.

Software+Hardware approaches
An approach using support within the OS or a programming language

1. Semaphore
2. monitor

Q. 위의 접근 방법을 다 알아야하는 이유?

하드웨어 instruction, Semaphore, ...
내가 사용하는 프로그램 OS 가 모든 방법을 제공하지 않을 수 있기 때문이다.

⇒ 즉, 시스템 상황이 어떻게 될 지 알 수 없기 때문이다.

Compare&Swap Instruction (Hardware Instruction)

• 함수 형태이다.
• 인자가 3개 있다.
• word 포인터 인자가 하나 있다. (memory location을 가르킨다.)
• Compare&Swap은 밑에처럼 코드로 나타내져있지만, 사실 코드가 아니다. 따라서 호출만 가능하고 수정은 불가능한 코드이다. (exchange도 마찬가지)

int compare_and_swap (int *word, int testval, int newval)
{
	int oldval;
    
    oldval = *word;
    if(oldval == testval) *word = newval;
    return oldval;
}

1. word 와 testval 의 값이 같을 경우
   → word의 값을 newval의 값으로 변경한다.
2. word 와 testval 의 값이 다를 경우
   → word의 값 변경하지 않는다.
3. 항상 oldval, 즉 word에 들어 있던, 원래의 값이 return 된다.

Compare&Swap Instruction 의 특징

1. Compare&Swap 은 atomic instuction이다. (Hardware instruction)
   → 하드웨어 instruction 이기 때문에 인터럽트가 발생하지 않는다.
   ↳ 이유: 하나의 instruction 이기 때문이다.

⇒ 위의 코드 중간에서 끊기는 상황은 발생하지 않는다.

⇒ instruction 은 Fetch stage + Execution stage 를 거치고 나서야 Interrupt stage 를 거치게 된다.

1. Compare&Swap Instruction 의 실행 시간 동안,
   그 공간을 참조하는 모든 instruction 들은, 메모리 공간(위의 코드에서 word 가 가르키는 메모리 영역) 접근이 blocked 된다.

10개의 CPU 가 있을 때,
Process 개수 제한 없이 10개의 CPU를 이용하여 동시에 실행
→ 이 중 하나의 Process가 Compare&Swap 을 실행하고 있다면, 다른 Process는 Compare&Swap 을 실행할 수 없다.
⇒ Compare&Swap 은 하나의 Process 만 가능하다.

⇒ Compare&Swap 은 Interleaving , Overlapping 이 불가능하다.

Compare&Swap 진행 단계

Step1

처음 bolt 값은 0으로 설정된다.

n개의 프로세스가 메소드 P를 동시 실행한다.

Step2

여러 프로세스 중 P2가 먼저 메소드 P를 실행해서 compare_and_swap while문을 실행한다.

Step3

P2는 bolt 값(0) 과 0을 비교하는데, bolt값이 0이었기 때문에 bolt 값을 1로 바꾸고 0을 반환한다. while문 조건에 거짓이기 때문에 P2는 while문을 빠져나와 Critical Section 을 실행한다.

이제 다른 프로세스들은 bolt에 접근해 compare_and_swap while문을 돌려도 bolt값(1)과 0이 이제 다르기 때문에 bolt 값을 바꾸지 않고 1을 반환한다.
while문을 보면, 1과 같을 때 참이기 때문에 while문을 빠져나오지 못한다.

compare_and_swap while문은 Critical Section 전에 하나의 Process만 빠져나올 수 있다.

Step4

P2가 Critical Section을 실행하고 나면, bolt 값을 다시 0으로 바꿔준다.
이후 다음에 CPU를 차지한 프로세스가 compare_and_swap 을 실행하여 while문을 통과 한 다음 Critical Section에 진입하게 된다.

Starvation 가능성 O

P2가 Critical Section을 실행하다가 TIMEOUT
→ P2를 제외한 나머지 Process가 CPU를 잡음
→ compare_and_swap while문에 걸림
→ P2가 CPU를 다시 잡는다.
→ P2가 bolt값을 0으로 바꾸고 바로 다시 P2가 compare_and_swap을 실행
→ P2가 Critical Section 다시 진입

Exchange Instruction
(Hardware Instruction)

void exchange (int *register, int *memory) {
	int temp;
    
    temp = *memory;
    *memory = *register
    *register = temp;
}

1. register(key) 값과 memory(bolt) 값을 교환한다.

Exchange Instruction 의 특징

1. Exchange는 atomic instruction이다. (Hardware instruction)
   ↳ 하나의 instruction 이기 때문에 중간에 interrupt가 발생하지 못한다.
   (fetch, execution stage 까지 진행한 후 interrupt 가 진행된다.)
   
   
2. Exchange Instruction 의 실행 시간 동안,
   그 공간을 참조하는 모든 instruction 들은, 메모리 공간(위의 코드에서 word 가 가르키는 메모리 영역) 접근이 blocked 된다.
   → 동시 접근 불가 ⇒ 한 번에 하나의 Process 만 exchange 가 가능하다.

⇒ Exchange 은 Interleaving , Overlapping 이 불가능하다.

Exchange 진행 단계

현재 코드에는 문제가 없지만, critical section과 non-critical section을 다르게 배열하면, 문제가 발생할 수 있다.

Step1

처음 bolt 값은 0으로 설정된다.

n개의 프로세스가 메소드 P를 동시 실행한다.

bolt는 공유 변수이고, key 값은 지역 변수이다.
초기 key 값은 1로 설정된다.

Step2

여러 프로세스 중 P2가 먼저 메소드 P를 실행해서 Exchange do-while문을 실행한다.

Step3

P2는 bolt 값(0) 과 key2 의 값(1) 을 교환한다.
bolt 값은 1이되고, P2의 key2 값은 0이 된다.
key2의 값이 0이 아니므로 while문을 통과하게 되어 Critical Section 을 실행하게 된다.

이제 다른 프로세스들은 bolt에 접근해 Exchange do-while문을 돌려도 bolt값(1)과 keyi 값(1)이 같기 때문에 bolt 값과 key 값을 바꾸어도 서로 같은 값 (1) 을 바꾸게 된다.
while문을 보면, key 값이 0아 아닐 때 참이기 때문에 key 값이 1이므로 while문을 빠져나오지 못한다.

⇒ Exchange do-while문은 Critical Section 전에 하나의 Process만 빠져나올 수 있다.

Step4

P2가 Critical Section을 실행하고 나면, bolt 값을 다시 0으로 바꿔준다.
이후 다음에 CPU를 차지한 프로세스가 Exchange 을 실행하여 do-while문을 통과 한 다음 Critical Section에 진입하게 된다.

Hardware Mutual Exclusion

Softawre instruction: 복잡하지만, Starvation X, Deadlock X
Hardware instruction: 단순하지만, Starvation O, Deadlock O

장점

1. 프로세스의 수에 제한이 없다.
   ↳ CPU, Process 숫자를 가정할 필요가 없다. → n개 적용 가능하다.
2. 간단하다 → 증명하기 쉽다. (한 줄)
3. multiple critical section 을 지원한다.
   ↳ OS가 Critical Section 뿐만 아니라 시스템 설계에 있어,
   해결해야하는 문제들이 존재하는데, 이 문제들은 while문을 여러개 통과해야 한다.
   ⇒ 그래도 Hardware instruction은 간단하기 때문에 쉽게 적용할 수 있다.

단점

1. Busy-Waiting
   ↳ Process 한 개 이외에는, CPU를 차지해도 whiel문에 걸려있는 상태로 CPU 시간을 낭비한다.
2. Starvation
   ↳ 한 Process만 Critical Section을 독점할 수 있다.
3. Deadlock
   ↳ 위의 예시에서는 while문이 1개이기 때문에 모두가 못들어가는 상황은 발생하지 않지만, multiple critical section 에서는 Deadlock 이 발생할 가능성이 존재하게 된다.

Busy-Waiting은 Software Approach 와 Hardware Approach 모두 에서 발생한다.
하지만, Starvation과 Deadlock은 Hardware Approach에서만 발생하므로 더 심각하다.

Semaphore

Semaphore란?

프로세스들 간의 신호 전달에 사용되는 integer value이다.

⇒ Semaphore는 구조체 변수이다. (an integer + a queue)

Semaphore는 OS가 제공하는 Tool이다.

공유 메모리 변수 "bolt"

변수 bolt 는 공유 메모리 값으로 연산이(+, -) 가능하다. ⇒ 변화 가능 O

OS 변수 "S"

변수 S 는 OS의 변수 로 연산이(+, -) 불가능하다.(S++, S-- X)

변수 S 는 초기화할 때 0 이상의 값 만 가능하며, 음수는 불가능 하다.
변수 S 의 값: 어떤 상황을 의미한다.
⇒ 음수가 의미하는 상황이 따로 존재한다. 그렇기 때문에 음수로 초기화해서는 안된다.

System-Call

OS에게 무언가를 해달라고 요청하는 것으로, OS의 function을 실행해달라고 요청하는 것이다.

여기서 프로세스1과 프로세스2가 System call 하는 것은 OS의 변수인 S 에 접근 요청을 하기 위해서이다.

Semaphore에서는 오직 세가지 operation만 존재하며 모두 atomic 이다.

Semaphore에 대한 System-Call은 딱 3가지만 존재한다.

1. Initialize (w/ nonnegaive integer value)

초기화(S의 값 초기화)
↳단, 음수는 불가능하다. (0이상의 값만 가능)

2. SemWait

세마포어 값을 감소 시킨다.

• s >= 0 → process 그냥 통과
• s < 0 → process를 Blocked queue로 이동

결과 값이 음수 이면 프로세스를 block 할 수도 있고 block 시키지 않을 수도 있다(프로세스가 그냥 통과할 수도 있다).

3. Semsignal

결과 값이 0보다 작거나 같으면 세마포어 값을 증가 시키고 대기열에서 프로세스 block을 해제한다.

S의 값을 하나 더한다.

• s > 0 → 아무것도 안함
• s <= 0 → process를 Blocked Queue에서 빼서 Ready Queue로 옮겨준다.

Semsignal을 호출한 Process가 아니라,
Blocked queue에 있는 Process 중 하나를 꺼내서 Ready Queue로 옮긴다. ⇒ Running 가능

ProcessA → semWait → s < 0 → (ProcessA: BlockedQueue 이동 )
→ ProcessC → semSignal → s <= 0 → (ProcessA → ReadyQueue)
→ semSignal 다음 코드를 실행한다.

Semaphore Primitives

동기화 문제
↳ 내가 건드릴 수 있는 코드인가?
⇒ 내 application code X, OS code O
⇒ 함수 호출만 가능하며 함수 수정은 불가능하다.

밑의 코드는 OS 코드이기 때문에 수정할 수 없는 코드이다.
우리가 할 수 있는 것은 semWait, semSignal 함수 호출뿐이다.

struct semaphore {
	int count;
    queueType queue;
};
void semWait(semaphore s)
{
	s.count--;
    if (s.count < 0) {
    	/* place this process in s.queue */
        /* block this process */
    }
}
void semSignal(semaphore s)
{
	s.count++;
    if (s.count <= 0) {
    	/* remove a process P from s.queue */;
        /* place process P on ready list */;
    }
}

semWait(semaphore s)

1. s 변수의 값을 줄인다.
2. s 변수의 값이 0보다 작은지 확인하고, 0보다 작을 경우, block을 하여 blocked queue로 옮긴다.

semSignal(semaphore s)

1. s 변수의 값을 증가시킨다.
2. s 변수의 값이 0보다 작거나 같은지 확인하고, 0보다 작거나 같을 경우 blocked queue에 있던 프로세스를 하나 꺼내 ready queue로 옮겨 실행할 수 있도록 만들어 준다.

semaphore s 의미

S > 0

semWait을 그냥 통과 할 수 있는 횟수를 의미한다.

즉, 현재 CPU를 잡고 있는 프로세스가 semWait System Call 을 호출해도,
Blocked 되지 않고 넘어갈 수 있는 횟수를 의미한다.

ex) s = 0 → semWait을 그냥 통과할 수 없다.
    s = 3 → semWait을 3번 통과할 수 있다.

S <= 0

절대값 s 는 Blocked queue에 들어 있는 프로세스의 개수를 의미한다.

ex) s = 0 → Blocked queue에 들어있는 프로세스 개수 = 0
    s = -10 → Blocked queue에 들어있는 프로세스 개수 = 10

⇒ s 에는 의미가 있기 때문에 초기값은 반드시 0 또는 0 이상의 값으로 설정해주어야 한다.

Example of Semaphore Mechanism

Mutual Exclusion Using Semaphore

While문이 사라졌다!
OS는 OS 변수 S 값을 근거로 현재 CPU를 잡고 있는 프로세스를 Block 시킬지 말지를 결정한다.
초기 Semaphore s 의 값은 1로 설정한다.

여러 프로세스들 중 s가 1일 때

semWait을 실행한 프로세스가 block에 걸리지 않고 통과하여 Critical Section 을 실행할 수 있게 된다.
이미 s가 0이 된 이후에

semWait를 실행하는 프로세스들은 s < 0 이 되기 때문에 Block이 되어 Blocked Queue로 이동하게 된다.

↳ 앞에서는 Process가 Critical Section에 진입하면 다른 Process 들은 While 문에서 기다려야 했지만, 위의 코드에서는 OS가 실행하는 것이기 때문에 기다리는 Process들은 모두 Block 상태가 되어 Blocked Queue로 이동하게 된다.

(프로세스를 Block 시키는 것은 OS만 가능하다.)

OS는 누가 Critical Section을 진행하는지 안하는지 모른다.

Critical Section을 마친 프로세스는 semSignal을 실행해 s 값을 1증가시키고 아직 s 값이 0보다 작거나 같다면 Blocked Queue 에 있던 프로세스 중 하나를 꺼내 Ready Queue에 보내 Running 상태가 될 수 있게 해준다.

Block상태에서 Ready상태를 거쳐 다시 Running 상태가 된 프로세스는 semWait 다음 줄인 Critical Section을 실행할 수 있게 되고,
실행한 이후에는 다시 semSignal을 실행시켜 다른 프로세스가 Critical Section을 실행할 수 있도록 해준다.

앞의 approach들에서는 프로세스가 Critical Section에 들어갈 수 있게 보장을 해주었다면, 여기서는 아예 Critical Section에 넣어준다.

Mutual Exclusion O

S=1 → 하나만 semWait 통과 가능하다!

Busy Waiting X

semWait 을 통과한 프로세스 이외의 나머지 프로세스들은 Blocked Queue로 이동하게 된다.

Starvation △

Strong Semaphor → 가능성 X
Weak Semaphor → 가능성 O

Deadlock X

OS가 semapho 변수를 보고 동시 진입시, 하나는 진입할 수 있게 된다.
그러나 초기 s 값이 0 으로 되어 있으면, 아무도 들어가지 못하게 된다.
혹은 초기 s 값이 10으로 되어 있으면, 동시에 10개의 프로세스가 Critical Section을 실행할 수 있게 된다.
⇒ s의 초기값 설정이 중요하다.

Strong/Weak Semaphore

우리가 선택하는게 아니라 OS가 제공해주는 것이다.

Strong Semaphore

Blocked Queue에 먼저 들어간 Process가 먼저 들어간 순서대로 나온다. (FIFO)
⇒ Starvation 가능성 X

Weak Semaphore

Process가 Blocked Queue에 들어간 순서대로 나오지 않는다.
특정 Process 하나가 Process에서 나오지 않을 수 있다.
⇒ Starvation 가능성 O

1. Blocked Queue는 semaphore 위에서 기다리는 프로세스들을 잡아놓기 위해 사용되어 진다.
   ↳ 어떠한 순서로 프로세스들이 Queue 에서 빼내질까?
2. Strong Semaphore 는 FIFO 를 사용한다.
3. Weak Semaphore 는 queue 에서 프로세스를 제거하는 순서를 구체화하지 않는다.

Mutual Exclusion Using Semaphore(2)