[운영체제] 세마포어(Semaphore) operation의 원리..

gyxor의 이미지

semaphore operation의 pseudo code입니다.
S.value의 초기값은 1입니다.

void wait(semaphore S)
{
S.value--;
if(S.value < 0) {

add this process to S.L;
block();
}
}

void signal(semaphore S)
{
S.value++;
if(S.value <= 0) {
remove a process P from S.L;
wakeup(P);
}
}

2개의 프로세스가

wait(S);

[critical section]

signal(S);

이러한 동일한 코드를 동시에(시분할 로) 실행한다고 했을때..

데드락에 빠지는 상황이 생길 수 있습니다.
파란색 코드 부분에서 context swicth가 일어나는 경우입니다.
예) A,B 프로세스가 번갈아 가면서 wait()함수를 실행했을 경우에
S.value--;
A프로세스가 부분을 실행한 뒤
B프로세스가 context switch 한뒤에 마찬가지로 이를 실행을 하게 되면 두 프로세스 모두가
if(S.value < 0) {
이 조건에 걸리게 되어서 critical section에 둘다 못들어가게 되고
무한정 block이 되어버립니다.
wait함수의

         S.value--;
         
         if(S.value < 0) {

이 코드를 race condition으로 실행을 하지 않도록..
즉, 이 코드 사이에서 context switch 가 일어나지 않도록
하드웨어적으로 보장하거나 소프트웨어적으로 보장을 해야 한다는데요..
어떻게 가능한지 궁금합니다.
소프트웨어적으로는...
context switch의 signal(?) 을 해당 코드범위를 실행하는 동안
무시하도록 하는 방법인가요?
(그런데..context switch에 따르는 signal은 없는것으로 알고 있습니다.)
하드웨어적으로는 또 어떻게 할 수 있는것인지..모르겠습니다.

설명부탁드립니다.

익명 사용자의 이미지

소프트웨어로는 불가하며, 하드웨어로 test+set을 atomic하게 할 수 있는 메카니즘이 필요합니다. 소위 값 비교와 동시에 값 변경하는 동안 context switch가 발생하지 않도록 하는(mutual exclusion) 연산이 필요한데, 이는 하드웨어로 부터 얻어야 합니다.
이를 하드웨어에서 보장하면, 이를 이용하여 소프트웨어단에서도 세마포 같은 동기화 프리미티브 연산(P, V)을 구현하게 됩니다. 이후, 상위수준의 IPC를 구현하게 되겠지요.

* atomic operation, InterlockedIncrement 등으로 검색하면, 어셈블리언어로 어떻게 이를(atomic 연산) 구현했는지를 보여주고 있습니다.

gyxor의 이미지

Operating System Concepts 6th 204p
In a uniprocessor environment(that is, where only one CPU exists),
we can simply inhibit interrupts during the time the wait and signal operations are executing.

uniprocessor 환경에서는 atomic 해야 하는 부분에서 interrupt를 disable해주면 된다고 하는데요..
기본적으로 하드웨어에서 interrupt enable/disable 기능을 지원해야
소프트웨어에서 요청할 수있는것이니.. 결국 하드웨어에서 지원하는 기능으로 생각됩니다.

그런데,
In a multiprocessor environment, inhibiting interrupts does not work. Instructions from different processes
(running on different processors)
may be interleaved in some arbitrary way.
If the hard ware does not provide any special instructions,
we can employ any of the correct software solutions for the critical-section problem,
where the critical sections consist of the wait and signal procedures.

multiprocessor 환경에서는 소프트웨어적으로 해결을 해야 한다는데요..
그러면서 앞절에서 소개된 알고리즘을 얘기하고 있습니다.

하드웨어적으로 atomic 함을 보장해야하는 알고리즘이거나
프로세스의 critical section진입 순서가 보장되어야 하거나

(A)
while(1){
turn = 1;
while(turn ==0);
[critical section]
turn =0;
}

(B)
while(1){
turn = 0;
while(turn ==1);
[critical section]
turn =1;
}

이렇게 두 프로세스의 코드가 서로 달라야 가능한.. 그런 알고리즘 들이었습니다.
이런 알고리즘은 두 프로세스 사이에서만 가능한데요..
N개의 프로세스 사이에서 가능한 bakery 알고리즘도 있긴 하지만요..

실제로 멀티프로세서 환경에서는 위의 알고리즘을 적용하는 방법밖에는 없나요?
설명부탁드립니다.

익명 사용자의 이미지

머신레벨의 락이 제공되어야 멀티프로세서에서 세마포가 구현가능합니다.
특정메모리 번지를 공유하게되는 멀티프로세서모델의 경우에는 특정 메모리에 대한 액세스 락을 거는 머신명령이 하드웨어에서 제공되어야하고, 이를 운용하는 것은 소프트웨어에 의하기 때문입니다.(소프트웨어로 호출, 마치 싱글프로세서 컴퓨터에서 인터럽트 디스에이블하듯이)

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.