๐ Major Study (Bachelor)/๐ง Operating System
[OS / ์ด์์ฒด์ ] Mutex, Semaphores, Monitors
by UKHYUN22
2022. 5. 16.
Mutex
Mutex์ ๊ฐ์ด 1์ด๋ฉด ๋ค์ด๊ฐ๋ ๋๋ค. Boolean variable์ ๋ป์ Availableํ๋ค๋ ๊ฒ์ ๊ฐ์ง๋ค. True์ด๋ฉด ๋ค์ด์๋ ๋๋ค! ์ด๊ธฐํ๋ฅผ True๋ก ์ค์ ์ ํด์ผ ํ๋ค. ํ์ง๋ง ์๋ฌด๋ ์ ๊ทผํ ์ ์๋ค. Atomic Operation์ ํตํด์๋ง ๋ฐ๊ฟ ์ ์๋ค. Class์ Private ๋ณ์๋ก ์ ์ธ์ ํ๋ ๊ฒ๊ณผ ๋์ผํ๋ค. acquire๋ Entry section์์ ์ฌ์ฉ๋๋ ํจ์์ด๋ค. ๋๊ฐ ๋ค์ด๊ฐ ์๋์ง ํ์ธ์ ํด์ผ ํ๋ค. release ํจ์๋ Exit function์ด๋ค. ๋ค์ ์น๊ตฌ๊ฐ ๋ค์ด์๋ ๋๋ค๊ณ ํ๋ ํ์ด์ฃผ๋ ๊ตฌ์ญ์ด๋ค.
acquire ํจ์
available์ ๊ฐ์ด ์ฒ์์ true์ด๋ฏ๋ก while ๋ฌธ์ ํต๊ณผํ๊ฒ ๋๋ค. ๊ทธ๋ฌ๋ฉด์ available๊ฐ false๋ก ๋ฐ๋๊ฒ ๋๋ค. ์ด๋ฏธ ๋ค์ด์์์ผ๋ฏ๋ก ์๋ฌด๋ ๋ค์ด์ค๋ฉด ์๋๋ค๊ณ ๋ฐ๊พธ๋ ๊ฒ์ ์๋ฏธํ๋ค. acquire ์์ฒด๊ฐ critical section ์์์ ํธ์ถ๋๋ ํจ์์ด๋ฏ๋ก available = false๋ก ๋ง๋๋ ๊ณผ์ ์ด ํจ๊ป ์งํ๋๋ค. 2๋ฒ Process๊ฐ ๋ค์ด์ค๊ฒ ๋๋ฉด acquire๋ฅผ ํธ์ถํ๊ฒ ๋๋ค. while์ ํต๊ณผํ์ง ๋ชปํ๊ณ waitํ๊ฒ ๋๋ค. ์ด๋ ๊ฒ Mutual Exclusion์ ๋ง์กฑํ๊ฒ ๋๋ค. P1์ด ๋์ฌ ๋ release ํจ์๋ฅผ ํธ์ถํ๋ค. available์ ๊ฐ์ true๋ก ๋ฐ๊พธ๊ฒ ๋๋ค. P2์ ์
์ฅ์์๋ while ๋ฌธ์ ๊นจ๋จ๋ฆฌ๊ณ ํต๊ณผํ๊ฒ ๋๋ค. ๊ทธ ์๊ฐ์ available์ false๋ก ๋ง๋ค๊ฒ ๋๋ค. ์ด ์ด์ ๋ Mutual Exclusion์ ๋ง์กฑํ๊ฒ ํ๊ธฐ ์ํจ์ด๋ค. ๊ฐ๊ฐ์ acquireํจ์์ release ํจ์๋ Atomic Operation์ด์ด์ผ ํ๋ค. knocking๊ณผ locking ์ฌ์ด์ Gap์ด ์์ด์๋ ์๋๋ค. (acquire์ ํจ์ ์ด๋ฆ์ด lock() wait()์ผ๋ก ์ฌ์ฉ๋๊ธฐ๋ ํ๋ค.) (release() ํจ์์ ๊ฒฝ์ฐ unlock()๊ณผ signal()์ ์ด๋ฆ์ผ๋ก ๋ถ๋ฆฌ๊ธฐ๋ ํ๋ค)
Mutex Locks
Entry Section์์ Acquire๋ฅผ ํธ์ถํ๋ค. Exit section์์๋ Releaseํจ์๋ฅผ ํธ์ถํ๋ค.
Semaphores
์ฃผ์ฐจํ ์ ์๋ ๊ณต๊ฐ์ด 3๊ฐ๊ฐ ์์ผ๋ฉด ํ ๋๋ง ๋ค์ด์๋ค๊ณ Lock์ ํด๋ฒ๋ฆฌ๋ฉด ์๋๋ค. semaphore์์๋ Integer ๋ณ์๋ฅผ ์ฌ์ฉํ๋ค. ์ง๊ธ ์ฌ์ฉํ ์ ์๋ Resource๊ฐ ๋ช ๊ฐ ๋จ์์๋์ง๋ฅผ ์ซ์๋ก ๋ํ๋ด์ค๋ค. ์ด๊ธฐ ์ํ๊ฐ S = 2 ๋ผ๊ณ ๊ฐ์ ์ ํด๋ณด์. P1์ด ๋ค์ด์จ๋ค. ๊ทธ ์๊ฐ S = 2์ธ ์ํ๋ก while๋ฌธ์ด false๊ฐ ๋ผ์ ํต๊ณผํ๊ฒ ๋๋ค. ๊ทธ๋ฌ๋ฉด์ S์ ๊ฐ์ 1 ๋งํผ ์ค์ด๊ฒ ๋๋ค. ์ด ์ํฉ์์ P2๊ฐ ๋ค์ด์จ๋ค. while์ ์กฐ๊ฑด์ด false๊ฐ ๋ผ์ P2๋ ๋ค์ด๊ฐ ์ ์๊ฒ ๋๋ค. P3๊ฐ ๋ค์ด์ค๋ ๊ฒฝ์ฐ while๋ฌธ์ด true๊ฐ ๋๋ฏ๋ก whlie๋ฌธ์ ํต๊ณผํ ์ ์๋ค. P1์ด ๋๊ฐ ๋ Signal์ ํธ์ถํด์ S๋ฅผ 1๋ก ์ฆ๊ฐ์ํค๊ฒ ๋๊ณ ๊ทธ ์๊ฐ P3๊ฐ while๋ฌธ์ ํต๊ณผํด์ ๋ค์ด์ค๊ฒ ๋๋ค. Shared Resource๊ฐ ํ๋๊ฐ ์๋ ๊ฒฝ์ฐ ์กด์ฌํ๋ค.
Implementation of Semaphore
busy waiting ์ด๋? ๊ธฐ๋ค๋ฆฌ๋ Process๊ฐ ๊ณ์์ ์ผ๋ก S ๋ณ์๋ฅผ ์ณ๋ค๋ณด๊ณ ์๋ ์ํฉ์ด ๋๋ค. CPU๋ฅผ ๊ณ์์ ์ผ๋ก ์๋ชจํ๊ฒ ๋๋ค. Block์ด๋ผ๋ ๊ธฐ๋ฒ์ ์ฌ์ฉํด์ผ ํ๋ค. Process ์์ฒด๋ฅผ Ready Queue์์ ๊บผ๋ด๋ ๊ฒ์ด๋ค. Waiting State๋ก ๋ฐ๊พธ๋ ๊ฒ์ด๋ค. ์ด ๊ฒฝ์ฐ ๋ ์ด์ CPU Time์ Waste ํ์ง ์๊ฒ ํ ์ ์๋ค. Waiting Queue์์ ๊ธฐ๋ค๋ ค์ผ ํ๋ค. ์ด๋ PCB๋ก ๊ตฌ์ฑ๋ Linked List์ด๋ค.
Implementation of Semaphore
semaphore Structure ์์ Integer ๋ณ์๊ฐ ํ๋ ์๊ณ struct process์ ํ์
์ PCB์ ํ์
์ด ๋๋ค. Linked List๋ฅผ ๊ฐ๊ธฐ ์ํด์๋ Head Pointer๋ฅผ ๊ฐ์ง๊ณ ์์ด์ผ ํ๋ค. *list๋ head๋ฅผ ์ ์ฅํ๋ ํฌ์ธํฐ์ ํด๋นํ๋ค.
wait()
black์ ๋ ์ด์ CPU Time Waste๋ฅผ ํ์ง ์๋๋ก Waiting State๋ก ๋ณ๊ฒฝํ๋ ๊ฒ์ ์๋ฏธํ๋ค. ์ด๊ธฐ๊ฐ์ S = 2 ์ด๋ผ๊ณ ์๊ฐ์ ํด๋ณด์. S = 1๋ก ๋ณํ๊ณ if๋ฌธ์ ์คํํ์ง ์๊ฒ ๋๋ค. P2์ ๊ฒฝ์ฐ S = 0์ด ๋๊ณ if๋ฌธ์ด ์คํํ ์ ์๋ค. P3์ ๊ฒฝ์ฐ S = -1์ด ๋๊ณ if๋ฌธ์ ์คํํ ์ ์๊ฒ ๋๋ค. P3๋ฅผ linked list์ ์ถ๊ฐ๋ฅผ ํ๊ณ block()์ ํธ์ถํด์ CPU Time์ ๋ฐ์ง ์๊ณ Waiting State๋ก ๋น ์ง๊ฒ ๋ง๋ค ์ ์๋ค. S๊ฐ Minus๊ฐ ๋๋ฉด ํ์ฌ Block๋ Process์ ๊ฐ์๋ฅผ ์๋ฏธํ๋ค.
Signal()
P1์ด ๋๊ฐ๋ฉด S = -1 ์ด ๋๊ณ list์์ ํ๋๋ฅผ ๊บผ๋ด์ P์ ๋ฃ๋๋ค. wakeup(p)๋ฅผ ํ๊ฒ ๋๋ฉด Waiting State์์ Ready State๋ก ๋ณํ๊ฒ ๋๋ค. wakeup()์ ํด์ ๊นจ๊ฒ ๋๋ฉด Block ์ดํ๋ถํฐ ์คํ์ ์ฌ๊ฐํ๊ฒ ๋๋ค. wakeup() ์ดํ๋ถํฐ ์คํํ๋ ๊ฒ์ด ์๋๋ผ wait() ํจ์์ block() ์ดํ๋ถํฐ ์คํ๋๋ค.
Semaphore Instruction์ ๋ฐ๋์ function์ผ๋ก ๊ตฌํ๋์ด์ผ ํ๋๋ฐ ์ด๋ป๊ฒ Atomic ํ๊ฒ ๊ตฌํ๋๊ฒ ํ ์ ์์๊น??
Implementation of Semaphore
Atomic ํ๊ฒ ๋ง๋ ๋ค๋ ๊ฒ์ ๋์์ Critical Section์ Atomic์ด ์๋๋ค. ์ฌ๊ธฐ์๋ Wait๊ณผ Signal Function์์์ Atomic ํ ๊ฒ์ ์๋ฏธํ๋ค. CPU๊ฐ ํ๋ ๋ฐ์ ์๋ค๋ฉด Interrupt๋ฅผ Disableํ๋ฉด ๋๋ค. (Single Processor์ธ ๊ฒฝ์ฐ) ๋ง์ฝ 2๊ฐ ์ด์์ CPU๋ผ๋ฉด Interrupt Disable์ด Atomic์ ๋ณด์ฅํ์ง ๋ชปํ๋ค. Atomic ํ ๊ฒ์ ๋ณด์ฅํ๊ธฐ ์ํด์ Spinlock์ ์ฌ์ฉํ๋ค. ์ด์ ์ Spinlock์ ์ด์ ์ Process๊ฐ Exitํ ๋๊น์ง์ ์๊ฐ์ด๊ณ ์ง๊ธ์ Spinlock์ Wait๊ณผ Signal ํจ์ ์์ฒด์ ์๊ฐ์ด๋ฏ๋ก ํจ์ฌ ์ ๊ฒ ๊ฑธ๋ฆฐ๋ค.
Atomic Function์ ์ค๊ฐ ์ํ๊ฐ ์๋ค๋ผ๋ ๊ฒ์ด๊ณ Mutual Exclusion์ ๋๊ตฌ ํ๋๊ฐ ๋ค์ด์ค๋ฉด ๋ค๋ฅธ ํ๋๊ฐ ๋ค์ด์ฌ ์ ์๋ค์ด๋ค. ์ ์๊ฐ ๋ค๋ฅด๋ค.
Monitors
semaphore๋ฅผ ์ฌ์ฉํ ์ ์์ง๋ง ์ด ์ญ์ Low level์ด๋ผ๊ณ ๋งํ๋ค. low level์ ๊ฒฝ์ฐ ์ ๋ชป ํธ์ถํ๋ฉด ์๋์ ๋ชปํ ์๋ ์๋ค.
Syntax of Monitor
Mutual Exclusion์ด ์๋์ ์ผ๋ก ๋ณด์ฅ๋๋ Class๋ผ๊ณ ์๊ฐํ๋ฉด ๋๋ค. (***********)
[OS / ์ด์์ฒด์ ] The Readers-Writers Problem, The Dining Philosopher's Problems, Synchronization within the Kernel, POSIX Synchronization (0) |
2022.05.23 |
[OS / ์ด์ ์ฒด์ ] Monitors, Condition Variable, Implementing a Monitor Using Semaphore, Deadlock and Starvation, Bounded Buffer Problem (0) |
2022.05.19 |
[OS / ์ด์์ฒด์ ] Mutual Exclusion using TestAndSet, Mutual Exclusion and Swap, Mutual Exclusion using CAS, Bounded Waiting Mutual Exclusion, Atomic Variable (0) |
2022.05.09 |
[OS / ์ด์์ฒด์ ] Peterson's solution, Erroneus Algorithm, Peterson's Solution, Memory Barriers, Hardware Instructions, compare and swap, TestAndSet (0) |
2022.05.02 |
[OS /์ด์ ์ฒด์ ] Thread Scheduling, Contention Scope, Pthread Scheduling, Linux Scheduler, Linux CFS Scheduler, Windows Scheduling, Process Synchronization, Critical Section, Progress (0) |
2022.04.28 |