๐Ÿฆ• ๊ณต๋ฃก์ฑ…์œผ๋กœ ์ •๋ฆฌํ•˜๋Š” ์šด์˜์ฒด์ œ Ch.6

Synchronization

ํ”„๋กœ์„ธ์Šค๋Š” ๋™์‹œ์— ์‹คํ–‰๋  ์ˆ˜ ์žˆ์œผ๋ฉฐ, ์—ฌ๋Ÿฌ ๊ฐœ์˜ ํ”„๋กœ์„ธ์Šค๊ฐ€ ํ˜‘๋ ฅํ•  ๋•Œ๋Š” ํ”„๋กœ์„ธ์Šค ์‚ฌ์ด์— ๋ฐ์ดํ„ฐ๊ฐ€ ๋™๊ธฐํ™”๋˜์ง€ ์•Š๋Š” ๋ฌธ์ œ๊ฐ€ ๋ฐœ์ƒํ•  ์ˆ˜ ์žˆ๋‹ค.

Background

๋งŒ์•ฝ ๋‘ ํ”„๋กœ์„ธ์Šค๊ฐ€ ๋™์‹œ์— ์–ด๋–ค ๋ณ€์ˆ˜์˜ ๊ฐ’์„ ๋ฐ”๊พผ๋‹ค๋ฉด ํ”„๋กœ๊ทธ๋ž˜๋จธ์˜ ์˜๋„์™€๋Š” ๋‹ค๋ฅธ ๊ฒฐ๊ณผ๊ฐ€ ๋‚˜์˜ฌ ๊ฒƒ์ด๋‹ค. ์ด์ฒ˜๋Ÿผ ํ”„๋กœ์„ธ์Šค๊ฐ€ ์–ด๋–ค ์ˆœ์„œ๋กœ ๋ฐ์ดํ„ฐ์— ์ ‘๊ทผํ•˜๋Š๋ƒ์— ๋”ฐ๋ผ ๊ฒฐ๊ณผ ๊ฐ’์ด ๋‹ฌ๋ผ์งˆ ์ˆ˜ ์žˆ๋Š” ์ƒํ™ฉ์„ ๊ฒฝ์Ÿ ์ƒํƒœ(race condition)๋ผ๊ณ  ํ•œ๋‹ค.

The Critical-Section Problem

์ฝ”๋“œ์ƒ์—์„œ ๊ฒฝ์Ÿ ์กฐ๊ฑด์ด ๋ฐœ์ƒํ•  ์ˆ˜ ์žˆ๋Š” ํŠน์ • ๋ถ€๋ถ„์„ critical section์ด๋ผ๊ณ  ๋ถ€๋ฅธ๋‹ค. critical section problem๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ๋ช‡๊ฐ€์ง€ ์กฐ๊ฑด์„ ์ถฉ์กฑํ•ด์•ผ ํ•œ๋‹ค.

  • Mutual exclution (์ƒํ˜ธ ๋ฐฐ์ œ): ์ด๋ฏธ ํ•œ ํ”„๋กœ์„ธ์Šค๊ฐ€ critical section์—์„œ ์ž‘์—…์ค‘์ผ ๋•Œ ๋‹ค๋ฅธ ํ”„๋กœ์„ธ์Šค๋Š” critical section์— ์ง„์ž…ํ•ด์„œ๋Š” ์•ˆ ๋œ๋‹ค.
  • Progress (์ง„ํ–‰): critical section์—์„œ ์ž‘์—…์ค‘์ธ ํ”„๋กœ์„ธ์Šค๊ฐ€ ์—†๋‹ค๋ฉด ๋‹ค๋ฅธ ํ”„๋กœ์„ธ์Šค๊ฐ€ critical section์— ์ง„์ž…ํ•  ์ˆ˜ ์žˆ์–ด์•ผ ํ•œ๋‹ค.
  • Bounded waiting (ํ•œ์ • ๋Œ€๊ธฐ): critical section์— ์ง„์ž…ํ•˜๋ ค๋Š” ํ”„๋กœ์„ธ์Šค๊ฐ€ ๋ฌดํ•œํ•˜๊ฒŒ ๋Œ€๊ธฐํ•ด์„œ๋Š” ์•ˆ ๋œ๋‹ค.

Non-preemptive kernels๋กœ ๊ตฌํ˜„ํ•˜๋ฉด ์ž„๊ณ„ ์˜์—ญ ๋ฌธ์ œ๊ฐ€ ๋ฐœ์ƒํ•˜์ง€ ์•Š๋Š”๋‹ค. ํ•˜์ง€๋งŒ ๋น„์„ ์  ์Šค์ผ€์ค„๋ง์€ ๋ฐ˜์‘์„ฑ์ด ๋–จ์–ด์ง€๊ธฐ ๋•Œ๋ฌธ์— ์Šˆํผ ์ปดํ“จํ„ฐ๊ฐ€ ์•„๋‹ˆ๊ณ ์„  ์ž˜ ์‚ฌ์šฉํ•˜์ง€ ์•Š๋Š”๋‹ค.

Petersonโ€™s Solution

Petersonโ€™s solution์œผ๋กœ ์ž„๊ณ„ ์˜์—ญ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค. ์ž„๊ณ„ ์˜์—ญ์—์„œ ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ž‘์—…์ค‘์ธ์ง€ ์ €์žฅํ•˜๋Š” ๋ณ€์ˆ˜ flag์™€ critical section์— ์ง„์ž…ํ•˜๊ณ ์žํ•˜๋Š” ํ”„๋กœ์„ธ์Šค๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ๋ณ€์ˆ˜ turn ์„ ๋งŒ๋“ค์–ด ์–ด๋–ค ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ž„๊ณ„ ์˜์—ญ์— ์ง„์ž…ํ•˜๋ฉด flag๋ฅผ lockํ•˜๊ณ , ๋‚˜์˜ค๋ฉด unlockํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ์ž„๊ณ„ ์˜์—ญ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•œ๋‹ค.

do {
  flag[i] = true;
  turn = j;
  while (flag[j] && turn == j);
  // Critical section
  flag[i] = false;
  // Remainder section
} while(true);

Mutex Locks

mutex locks์€ ์—ฌ๋Ÿฌ ์Šค๋ ˆ๋“œ๊ฐ€ ๊ณตํ†ต ๋ฆฌ์†Œ์Šค์— ์ ‘๊ทผํ•˜๋Š” ๊ฒƒ์„ ์ œ์–ดํ•˜๋Š” ๊ธฐ๋ฒ•์œผ๋กœ, lock์ด ํ•˜๋‚˜๋งŒ ์กด์žฌํ•  ์ˆ˜ ์žˆ๋Š” locking ๋งค์ปค๋‹ˆ์ฆ˜์„ ๋”ฐ๋ฅธ๋‹ค. (์ฐธ๊ณ ๋กœ 'mutexโ€™๋Š” 'MUTual EXclusionโ€™์„ ์ค„์ธ ๋ง์ด๋‹ค.) ์ด๋ฏธ ํ•˜๋‚˜์˜ ์Šค๋ ˆ๋“œ๊ฐ€ critical section์—์„œ ์ž‘์—…์ค‘์ธ lock ์ƒํƒœ์—์„œ ๋‹ค๋ฅธ ์Šค๋ ˆ๋“œ๋“ค์€ critical section์— ์ง„์ž…ํ•  ์ˆ˜ ์—†๋„๋ก ํ•œ๋‹ค.

Semaphores

์„ธ๋งˆํฌ์–ด(Semaphore)๋Š” ์—ฌ๋Ÿฌ ๊ฐœ์˜ ํ”„๋กœ์„ธ์Šค๋‚˜ ์Šค๋ ˆ๋“œ๊ฐ€ critical section์— ์ง„์ž…ํ•  ์ˆ˜ ์žˆ๋Š” locking ๋งค์ปค๋‹ˆ์ฆ˜์ด๋‹ค. ์„ธ๋งˆํฌ์–ด๋Š” ์นด์šดํ„ฐ๋ฅผ ์ด์šฉํ•ด ๋™์‹œ์— ๋ฆฌ์†Œ์Šค์— ์ ‘๊ทผํ•  ์ˆ˜ ์žˆ๋Š” ํ”„๋กœ์„ธ์Šค๋ฅผ ์ œํ•œํ•œ๋‹ค. ๋ฌผ๋ก  ํ•œ ํ”„๋กœ์„ธ์Šค๊ฐ€ ๊ฐ’์„ ๋ณ€๊ฒฝํ•  ๋•Œ ๋‹ค๋ฅธ ํ”„๋กœ์„ธ์Šค๊ฐ€ ๋™์‹œ์— ๊ฐ’์„ ๋ณ€๊ฒฝํ•˜์ง€๋Š” ๋ชปํ•œ๋‹ค. ์„ธ๋งˆํฌ์–ด๋Š” P์™€ V๋ผ๋Š” ๋ช…๋ น์œผ๋กœ ์ ‘๊ทผํ•  ์ˆ˜ ์žˆ๋‹ค. (P, V๋Š” try์™€ increment๋ฅผ ๋œปํ•˜๋Š” ๋„ค๋œ๋ž€๋“œ์–ด Proberen๊ณผ Verhogen์˜ ๋จธ๋ฆฟ๊ธ€์ž๋‹ค.)

Semaphore Usage

์„ธ๋งˆํฌ์–ด์˜ ์นด์šดํ„ฐ๊ฐ€ ํ•œ ๊ฐœ์ธ ๊ฒฝ์šฐ ๋ฐ”์ด๋„ˆ๋ฆฌ ์„ธ๋งˆํฌ์–ด(Binary semaphore), ๋‘ ๊ฐœ ์ด์ƒ์ธ ๊ฒฝ์šฐ ์นด์šดํŒ… ์„ธ๋งˆํฌ์–ด(Counting semaphore)๋ผ๊ณ  ํ•œ๋‹ค. ๋ฐ”์ด๋„ˆ๋ฆฌ ์„ธ๋งˆํฌ์–ด๋Š” ์‚ฌ์‹ค์ƒ mutex์™€ ๊ฐ™๋‹ค.

Deadlocks and Starvation

๋‘ ํ”„๋กœ์„ธ์Šค๊ฐ€ ์„œ๋กœ ์ข…๋ฃŒ๋  ๋•Œ๊นŒ์ง€ ๋Œ€๊ธฐํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์‹คํ–‰ํ•œ๋‹ค๊ณ  ์ƒ๊ฐํ•ด๋ณด์ž. ํ”„๋กœ์„ธ์Šค A๋Š” B๊ฐ€ ์ข…๋ฃŒ๋  ๋•Œ๊นŒ์ง€, ํ”„๋กœ์„ธ์Šค B๋Š” A๊ฐ€ ์ข…๋ฃŒ๋  ๋•Œ๊นŒ์ง€ ์ž‘์—…์„ ํ•˜์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์— ํ”„๋กœ๊ทธ๋žจ์€ ์–ด๋–ค ๋™์ž‘๋„ ํ•˜์ง€ ๋ชปํ•  ๊ฒƒ์ด๋‹ค. ์ด์ฒ˜๋Ÿผ ๋‘ ํ”„๋กœ์„ธ์Šค๊ฐ€ ๋ฆฌ์†Œ์Šค๋ฅผ ์ ์œ ํ•˜๊ณ  ๋†“์•„์ฃผ์ง€ ์•Š๊ฑฐ๋‚˜, ์–ด๋– ํ•œ ํ”„๋กœ์„ธ์Šค๋„ ๋ฆฌ์†Œ์Šค๋ฅผ ์ ์œ ํ•˜์ง€ ๋ชปํ•˜๋Š” ์ƒํƒœ๊ฐ€ ๋˜์–ด ํ”„๋กœ๊ทธ๋žจ์ด ๋ฉˆ์ถ”๋Š” ํ˜„์ƒ์„ ๋ฐ๋“œ๋ฝ(Deadlock)์ด๋ผ๊ณ  ํ•œ๋‹ค. ์šด์˜์ฒด์ œ๋„ ๊ฒฐ๊ตญ ์†Œํ”„ํŠธ์›จ์–ด์ด๊ธฐ ๋•Œ๋ฌธ์— ๋ฐ๋“œ๋ฝ์— ๋น ์งˆ ์ˆ˜ ์žˆ๋‹ค.

Classic Problems of Synchronization

๋ฐ๋“œ๋ฝ์— ๊ด€ํ•œ ์œ ๋ช…ํ•œ ๋น„์œ ๊ฐ€ ์žˆ๋‹ค. ์ฒ ํ•™์ž 5๋ช…์ด ์‹ํƒ ๊ฐ€์šด๋ฐ ์Œ์‹์„ ๋‘๊ณ  ์ฒ ํ•™์ž๋“ค์€ ์‚ฌ์ƒ‰๊ณผ ์‹์‚ฌ๋ฅผ ๋ฐ˜๋ณตํ•œ๋‹ค. ํฌํฌ๋Š” ์ด 5๊ฐœ, ๋‹จ ์Œ์‹์„ ๋จน์œผ๋ ค๋ฉด 2๊ฐœ์˜ ํฌํฌ๋ฅผ ์‚ฌ์šฉํ•ด์•ผ ํ•œ๋‹ค. ์ฆ‰, ๋™์‹œ์— ์Œ์‹์„ ๋จน์„ ์ˆ˜ ์žˆ๋Š” ์‚ฌ๋žŒ์€ ๋‘ ๋ช…๋ฟ์ด๋‹ค. ์šด์ด ์ข‹์œผ๋ฉด 5๋ช…์˜ ์ฒ ํ•™์ž๋“ค์ด ๋Œ์•„๊ฐ€๋ฉด์„œ ์‚ฌ์ƒ‰๊ณผ ์‹์‚ฌ๋ฅผ ์ด์–ด๊ฐˆ ์ˆ˜ ์žˆ๋‹ค. ํ•˜์ง€๋งŒ ๋ชจ๋‘๊ฐ€ ํฌํฌ๋ฅผ ํ•˜๋‚˜์”ฉ ๋“ค๊ณ  ์‹์‚ฌ๋ฅผ ํ•˜๋ คํ•˜๋ฉด ๋ˆ„๊ตฌ๋„ ์‹์‚ฌ๋ฅผ ํ•  ์ˆ˜ ์—†๋Š” ์ƒํƒœ, ๋‹ค์‹œ๋งํ•ด ๋ฐ๋“œ๋ฝ์— ๋น ์ ธ ๋ฒ„๋ฆฐ๋‹ค. ์ด๊ฒƒ์ด ๋ฐ”๋กœ ์ฒ ํ•™์ž๋“ค์˜ ๋งŒ์ฐฌ ๋ฌธ์ œ(Dining-Philosophers Problem)์ด๋‹ค.