[Conflict - Merge] 운영체제의 Mutex, 우선순위 스케줄링과 Busy Waiting의 상관관계

[Conflict]

mutex에 대한 코드가 이해가 잘안가는데 부가 설명이 가능할까요? R이 무엇을 의미하는지, 파란 코드 부분에 2번째 줄에 if가 있는데 3번째 줄에도 if가 붙어 있어서 헷갈리네요. 우선순위 스케줄링과 Busy wating이 무슨 관계인지도 궁금합니다!

 

[Merge]

용어 정리 먼저 간단하게 하겠습니다

우선순위 스케줄링(Priority scheduling)

• 각각의 프로세스마다 우선순위를 부여하고, 우선순위가 높은 프로세스를 먼저 스케줄링 하는 것
• 스케줄링을 하는 이유? → 프로세스의 효율성을 높이고, 응답시간을 최소화해 시스템 능력 향상 위해

Busy wating

• 특정 조건이 충족될때까지 무한히 반복하는 것
• 왜 무한히 반복하는가? → 조건이 충족되었는지 확인하고, 불충족이면 계속 기다려야 하는데 무한정 기다리고 있을수는 없으므로 계속해서 조건이 충족되었는지 무한히 반복적으로 확인하는 것

mutex를 간단하게 설명드리면,

프로세스(또는 스레드)간에 일을 수행할 때, 공유메모리를 통해서 공유된 자원에 여러개의 프로세스가 동시에 접근하는 경우가 생깁니다.

이 여러개의 프로세스가 동시에 접근해서 사용하는 특정구간을 Critical region(=Critical section 임계영역, 이하 cr)이라 합니다.

cr에 동시에 여러개의 프로세스가 입장해, 데이터를 공유하며 수행하면 문제가 발생할 수 있습니다.

(Race condition 문제 발생, 두 개 이상의 프로세스가 어떤 공유 데이터를 읽거나 쓰려고 할 때, 최종 결과는 누가 언제 수행되느냐에 따라 달라지는 상황)

그래서 이런 상황을 방지하고자, cr에 프로세스가 한번에 하나만 접근할 수 있게 제한(Mutual exclution, 상호배제)을 두는 동기화 방식을 취해야 하고, 그 방식 중 하나가 Mutex 입니다.

 

mutex의 동작을 이해하려면 Busy Waiting 방법중 하나인 TSL(Test and Set Lock)을 알아야 합니다.

하드웨어적인 지원을 통한 Busy Waiting 방법으로, 상호배제 목적으로 대부분 cpu에서 제공하고있는 명령어 기능입니다.

메모리 주소 A에서 cpu 내부 레지스터 R로 값을 읽어가고(test), 동시에 A에 0이 아닌 값(=1)을 저장(set lock)하는 방식으로 진행됩니다. → 이 2가지 작업을 분리하지 못하게 한개의 명령어로 동시에 이루어집니다.

 

사진을 설명드리면,

 

memory에 0이 기본적으로 세팅되어있고, cpu(내부의 레지스터 R 내부의 프로세스)에는 아직 아무것도 있지 않은 상태입니다.

이때 프로세스는 memory에 있는 0을 읽어갑니다. 그와 동시에 memory에는 다시 1이 세팅됩니다

프로세스에서 0을 읽어갔다는 의미는 memory를 최초로 읽었다는 의미가 됩니다(memory의 초기값은 0이고, 이후로는 무조건 1이 세팅되니까)

이후 프로세스는 memory로부터 1만 읽어올 수 있게 됩니다. 읽어감과 동시에 memory에는 다시 1이 계속 세팅됩니다.

위의 읽기와 저장(세팅)이 동시에 이루어지기 때문에 위를 이용해 상호배제가 가능해집니다. memory에 있는 0을 여러개의 프로세스가 읽어갈 수 없기 때문입니다.

 

아래 코드를 보면 더 자세하게 알 수 있습니다

까만글씨로 쓰인 부분은 어셈블리어로 작성된 cr 입장과 퇴장을 간단하게 구현한 부분입니다

(어셈블리어 assembly: 기계어와 일대일 대응이 되는 저급언어. 컴파일 속도는 빠르지만 유지보수 어려움)

파란글씨로 쓰인 부분은 어셈블리 코드의 설명입니다

 

[enter_region]

cr에 입장하면서 tsl이 작동합니다. (lock memory에서 0 읽어옴)

R값이 0인지 비교합니다 (=최초 입장이 맞는지 판별)

0이 아닌 경우에는 cr에 입장하지 못하고 다시 처음으로 이동합니다. (그러면 다시 또 0인지 비교, 아니면 다시 처음으로… 반복 = busy waiting)

0인 경우에는(위 조건식으로 판별되었으므로) 호출한 쪽(cr)에 입장합니다.

 

[leave_region]

cr을 퇴장하면서 lock memory에 0을 반환합니다. (다른 프로세스도 0을 읽어서 cr에 입장할 수 있게)

호출한 쪽(cr외부)으로 이동합니다.

 

이제 mutex 코드를 살펴보겠습니다.

이전 TSL을 생각해보면 mutex를 lock 한다는 건 cr에 입장하겠다는 의미가 되겠고, unlock한다는건 cr에서 퇴장한다는 의미가 되겠습니다.

 

결국

lock → 해당 프로세스만 cr 입장, 다른 프로세스는 unlock까지 busy waiting

unlock → cr 작업 완료, busy waiting 중인 다른 프로세스가 입장할 기회를 얻음

 

이전에 다룬 TSL 예제와 비슷한 모양입니다.

(마찬가지로 까만 부분은 어셈블리코드, 파란부분은 설명입니다)

 

[mutex_lock]

TSL이 작동하고 Lock memory에서 0을 읽어옵니다

프로세스가 0인지 판별후

0이라면 ok로 이동합니다

0이 아니라면(왜? 위 판별식에서 점프하지 못하고 걸러졌으므로) 스스로 block 상태로 전환합니다.(프로세스의 상태 의미, Ready, Running, Blocked)

mutex_lock으로 이동합니다(다시 cr에 입장할 기회를 잡기 위해)

ok로 이동한 경우, 호출한 쪽(cr)로 입장합니다.

 

[mutex_unlock]

lock memory에 0을 반환합니다(다른 프로세스의 입장 기회를 주기위해)

호출한 쪽(cr외부)로 이동합니다.

 

---

우선순위 스케줄링과 busy waiting은 직접적인 관계는 없습니다.

Sleep and Wakeup (Producer - Consumer)

• Busy wating 문제점
  • cpu time 소비
  • 우선순위 스케줄링 시 무한 대기

위 부분에서 busy waiting의 문제점 중 하나로 우선순위 스케줄링 시 무한 대기할 수 있다는 의미는,

우선 정말 그냥 계속 내가 권한을 받을 때 까지 계속 대기만 해야한다.. 라는 의미로 필기하긴 했으나 더 알아본 결과,,

 

우선순위 스케줄링을 한 경우 높은 우선순위를 가진 프로세스부터 순차적으로 스케줄링되고 실행되게 되는데, 이때 낮은 우선순위를 가진 프로세스는 우선 대기하게 되며 bust waiting 하게 됩니다.

이때 우선순위가 변경되거나, 멀티태스킹등의 문제로 우선순위가 낮은 프로세스가 먼저 실행되는 등의 이유로 우선순위 역전(Priority Inversion) 상태가 발생할 수 있습니다. 우선순위 역전 현상이 발생하면 높은 우선순위를 가진 프로세스가 낮은 우선순위의 프로세스가 공유된 자원을 해제할 때까지 busy waiting을 하게 되고, 이렇게 되면 낮은 우선순위의 프로세스는 CPU를 얻어 자원을 해제하는 것이 불가능해지므로 무한 대기 상태에 빠지게 됩니다.

(Priority Inversion: 우선 순위가 낮은 프로세스 때문에 우선순위가 높은 프로세스가 실행되지 않는 현상)

 

저러한 busy waiting을 보완하기 위해 나온 방법이 sleep - wakeup(= Blocking & Wake-Up) 방식입니다.

 

운영체제 특성상 한 부분을 설명하려면 이전 부분까지 다 끄집어내와야 하는 경우가 있어서 조금 길어졌습니다. 제가 설명을 잘 했는지 모르겠네요…. 운영체제 역시 어려워요