세마포(프로그래밍)

컴퓨터 과학에서 세마포는 여러 스레드에 의해 공통 리소스에 대한 접근을 제어하고 멀티태스킹 운영 체제와 같은 동시 시스템에서 중요한 섹션 문제를 피하기 위해 사용되는 변수 또는 추상 데이터 유형입니다.세마포어는 동기 프리미티브의 일종입니다.일반 세마포는 프로그래머 정의 조건에 따라 변경되는 일반 변수입니다(예: 증가 또는 감소 또는 전환).

세마포를 실제 시스템에서 사용하는 것으로 생각하는 유용한 방법은 특정 자원의 몇 유닛을 사용할 수 있는지 기록으로서, 유닛이 취득 또는 해방될 때 해당 레코드를 안전하게(즉, 레이스 조건을 회피하기 위해) 조정하는 작업과 결합하고, 필요한 경우 자원 유닛이 사용 가능하게 될 때까지 기다리는 것이다.

세마포어는 레이스 상황을 예방하는 데 유용한 도구입니다. 그러나 세마포어의 사용이 프로그램이 이러한 문제로부터 자유롭다는 보장은 없습니다.임의의 자원 카운트를 허용하는 세마포어를 카운트 세마포어라고 하며, 값 0과 1(또는 잠금/잠금 해제, 사용 불가능/사용 가능)로 제한된 세마포어를 바이너리 세마포어라고 하며, 잠금을 구현하는 데 사용됩니다.

세마포 개념은 Dijkstra와 그의 팀이 Electrogica X8을 위한 운영 체제를 개발하던 1962년 또는 ^[2]1963년에 네덜란드의 컴퓨터 과학자인 Edsger Dijkstra에 의해 발명되었습니다.그 시스템은 결국 THE 멀티프로그래밍 시스템으로 알려지게 되었다.

라이브러리의 유사점

도서관에 한 번에 한 학생이 사용할 수 있는 동일한 공부방이 10개 있다고 가정합니다.학생들은 자습실을 이용하고자 할 경우 프런트에 방을 요청해야 한다.빈 방이 없을 경우, 학생들은 누군가 방을 포기할 때까지 책상에서 기다립니다.학생이 방 사용을 마치면, 학생은 책상으로 돌아와 방 하나가 비어 있음을 표시해야 한다.

가장 간단한 구현에서는 프런트 데스크의 점원은 빈 방의 수만을 알고 있습니다.이것들은 모든 학생이 실제로 방을 등록하고 나서 방을 돌려줄 때에만 정확하게 알 수 있습니다.학생이 방을 요청하면 점원은 이 숫자를 줄인다.학생이 방을 내주면 점원이 이 숫자를 늘린다.객실은 원하는 기간 동안 사용할 수 있기 때문에 미리 예약할 수 없습니다.

이 시나리오에서는 프론트 데스크의 카운트 홀더는 카운트 세마포, 회의실은 자원, 학생은 프로세스/스레드를 나타냅니다.이 시나리오에서 세마포의 값은 처음에는 10으로 모든 방이 비어 있습니다.학생이 강의실을 요청하면 접근이 허용되고 세마포의 값은 9로 변경됩니다.다음 학생이 오면 8, 7 등으로 떨어집니다.누군가 회의실을 요청하고 세마포의 현재 값이 ^[3]0인 경우, 회의실이 개방될 때까지 대기해야 합니다(카운트가 0에서 증가했을 때).방 중 하나가 공개되었지만 여러 학생이 대기하고 있는 경우, 어떤 방법으로든 방을 점유할 사람을 선택할 수 있습니다(FIFO 또는 랜덤으로 하나를 선택하는 등).그리고 물론, 학생은 정말로 방을 나간 후에야 점원에게 방을 내놓는 것을 알려야 한다.그렇지 않으면, 방을 나가기 전에 다른 학생이 방에 들어갈 때 어색한 상황이 발생할 수 있다.

중요한 관찰

리소스 풀에 대한 액세스를 제어하는 데 사용할 경우 세마포는 사용 가능한 리소스 수만 추적합니다. 사용 가능한 리소스는 추적하지 않습니다.특정 사용 가능한 리소스를 선택하려면 다른 메커니즘(세마포어가 더 필요할 수 있음)이 필요할 수 있습니다.

세마포 카운트는 많은 다른 액션에 유용한 트리거 역할을 할 수 있기 때문에 이 패러다임은 특히 강력합니다.위의 사서는 학생이 없을 때 자습실의 불을 끄거나, 대부분의 방이 꽉 차 있을 때 방이 매우 바쁘다는 팻말을 붙일 수 있다.

프로토콜이 성공하려면 응용 프로그램이 프로토콜을 올바르게 따라야 합니다.공정성과 안전성이 저하될 가능성이 있습니다(즉, 프로그램이 느리게 동작하거나 불규칙하게 동작하거나 중단하거나 크래쉬할 수 있습니다).여기에는 다음이 포함됩니다.

• 자원을 요청하고 해방하는 것을 잊은 경우
• 요청되지 않은 자원을 해방한다.
• 자원을 필요로 하지 않고 장기간 보유하는 것
• 리소스를 먼저 요청하지 않고(또는 해제한 후) 사용할 수 있습니다.

모든 프로세스가 이러한 규칙을 따르더라도 여러 세마포어에 의해 관리되는 서로 다른 리소스가 있고 프로세스가 동시에 둘 이상의 리소스를 사용해야 하는 경우 다중 리소스 교착 상태가 발생할 수 있습니다.

의미론 및 구현

카운트 세마포에는 과거 P와 V로 표기된2개의 연산이 있습니다(대체명은 § 연산명을 참조해 주세요).동작 V는 세마포 S를 증가시키고 동작 P는 감소시킨다.

세마포 S 값은 현재 사용 가능한 리소스의 단위 수입니다.P 작업은 세마포에 의해 보호되는 리소스를 사용할 수 있게 될 때까지 시간을 낭비하거나 절전 모드로 전환되며, 이 때 리소스가 즉시 할당됩니다.V 작업은 반대로 프로세스가 리소스를 사용한 후 리소스를 다시 사용할 수 있도록 합니다.세마포 S의 중요한 속성 중 하나는 V 및 P 연산을 사용하지 않는 한 값을 변경할 수 없다는 것입니다.

알기 쉬운 방법대기(P) 및 신호(V) 작동은 다음과 같습니다.

• wait: 세마포 변수 값을 1씩 줄입니다.세마포 변수의 새 값이 음수인 경우 대기 실행 프로세스가 차단됩니다(세마포의 큐에 추가됨).그렇지 않으면 리소스 단위를 사용하여 프로세스가 실행을 계속합니다.
• signal: 세마포 변수 값을 1씩 늘립니다.증가 후 사전 증가 값이 음수인 경우(리소스를 기다리는 프로세스가 있음을 의미), 차단된 프로세스를 세마포 대기 큐에서 준비 큐로 전송합니다.

많은 운영체제는 세마포어가 증가하면 대기 프로세스를 차단 해제하는 효율적인 세마포 프리미티브를 제공합니다.즉, 프로세스가 세마포 값을 확인하는 데 불필요한 시간을 낭비하지 않습니다.

카운트 세마포 개념은 Unix에서 구현된 기술인 세마포에서 하나 이상의 "유닛"을 요구하거나 반환할 수 있는 기능으로 확장할 수 있습니다.변경된 V 및 P 연산은 다음과 같습니다. 대괄호를 사용하여 원자 연산을 나타냅니다. 즉, 다른 프로세스의 관점에서 분할할 수 없는 것처럼 보이는 연산을 나타냅니다.

함수 V(세마포 S, 정수 I): [S ← S + I] 함수 P(세마포 S, 정수 I): 반복: [S i I: S ← S - I break]

단, 이 섹션의 나머지 부분에서는 달리 지정되지 않는 한 단항 V 및 P 연산을 사용하는 세마포어에 대해 설명합니다.

기아를 방지하기 위해 세마포에는 프로세스 큐가 관련지어져 있습니다(보통 FIFO 시멘틱스).프로세스가 값이 0인 세마포에 대해 P 작업을 수행하면 세마포의 큐에 프로세스가 추가되어 실행이 일시 중단됩니다.다른 프로세스가 V 작업을 수행하여 세마포를 증가시키고 대기열에 프로세스가 있는 경우 이들 중 하나가 대기열에서 제거되고 실행을 재개합니다.프로세스의 priority가 다른 경우 큐를 priority별로 정렬할 수 있으므로 큐에서 가장 높은 priority의 프로세스를 먼저 가져올 수 있습니다.

구현이 증가, 감소 및 비교 연산의 원자성을 보장하지 않으면 증가 또는 감소가 잊혀지거나 세마포 값이 음수가 될 위험이 있다.원자성은 세마포를 한 번의 작업으로 읽고, 수정하고, 쓸 수 있는 기계 명령을 사용하여 달성할 수 있습니다.이러한 하드웨어 명령이 없는 경우, 원자 연산은 소프트웨어 상호 배제 알고리즘을 사용하여 합성될 수 있다.단일 프로세서 시스템에서는 프리엠프션을 일시적으로 중단하거나 하드웨어 인터럽트를 비활성화함으로써 원자적인 동작을 보장할 수 있습니다.이 방법은 세마포를 공유하는2개의 프로그램을 동시에 다른 프로세서에서 실행할 수 있는 멀티프로세서 시스템에서는 동작하지 않습니다.멀티프로세서 시스템에서 이 문제를 해결하기 위해 잠금 변수를 사용하여 세마포에 대한 액세스를 제어할 수 있습니다.잠금 변수는 test-and-set-lock 명령을 사용하여 조작됩니다.

예

간단한 예

변수 A와 부울 변수 S를 고려합니다.A에는 S가 true로 표시되어 있는 경우에만 액세스 할 수 있습니다.따라서 S는 A의 세마포입니다.

기차역(A) 직전의 정지 신호(S)를 상상할 수 있다.이 경우 신호가 녹색이면 기차역에 들어갈 수 있습니다.노란색 또는 빨간색(또는 다른 색상)이면 기차역에 액세스할 수 없습니다.

로그인 큐

10명의 사용자만 지원할 수 있는 시스템을 고려합니다(S=10).사용자가 로그인할 때마다 P가 호출되어 세마포 S가 1씩 감소합니다.사용자가 로그아웃할 때마다 V이 호출되며 S가 1씩 증가하여 사용할 수 있게 된 로그인 슬롯을 나타냅니다.S가 0일 경우 로그인하려는 사용자는 S가 증가할 때까지 기다려야 합니다.로그인 요구는 슬롯이 해방될 때까지 FIFO 큐에 큐잉됩니다.상호 제외는 요청이 순서대로 큐잉되도록 하기 위해 사용됩니다.S가 증가할 때마다(로그인 슬롯을 사용할 수 있음) 로그인 요구가 큐에서 해제되어 해당 요청을 소유한 사용자는 로그인할 수 있습니다.S가 이미0 이상일 경우 로그인 요구는 즉시 큐에서 삭제됩니다.

생산자-소비자

생산자-소비자 문제에서는 한 공정(생산자)이 데이터 항목을 생성하고 다른 공정(소비자)이 데이터 항목을 수신하여 사용합니다.이들은 최대 크기N의 큐를 사용하여 통신하며 다음 조건을 따릅니다.

• 소비자는 대기열이 비어 있는 경우 생산자가 무언가를 생산할 때까지 기다려야 한다.
• 생산자는 대기열이 꽉 차면 소비자가 무언가를 소비할 때까지 기다려야 한다.

생산자와 소비자 문제에 대한 세마포 솔루션은 다음 2개의 세마포를 사용하여 큐의 상태를 추적합니다.emptyCount, 큐 내의 빈 플레이스 수 및fullCount큐 내의 요소의 수.무결성을 유지하기 위해emptyCount큐 내의 실제 빈 플레이스 수보다 적을 수 있습니다(단, 절대 클 수 없음).fullCount는 큐 내의 실제 항목 수보다 적을 수 있습니다(단, 결코 클 수 없습니다).빈 장소와 항목은 빈 상자와 가득 찬 상자, 그리고 세마포어의 두 가지 종류의 리소스를 나타냅니다.emptyCount그리고.fullCount이러한 자원에 대한 통제력을 유지합니다.

바이너리 세마포어useQueue는 예를 들어 2개의 생산자가 빈 큐에 아이템을 동시에 추가하려고 하는 등 큐 자체의 스테이트 무결성이 훼손되지 않도록 합니다.또는 바이너리 세마포 대신 뮤텍스를 사용할 수도 있습니다.

그emptyCount처음에는 N,fullCount초기값은 0 입니다.useQueue첫 번째는 1입니다.

프로듀서는 다음 작업을 반복한다.

product: P(empty Count) P(use Queue) put ItemIntoQue(항목) V(useQueue) V(fullCount)

전기 소비 장치가 반복적으로 다음을 수행합니다.

소비: P(fullCount) P(useQueue) 항목 ← getItemFromQue() V(useQueue) V(emptyCount)

다음으로 구체적인 예를 제시하겠습니다.

1. 하나의 전기 소비 장치가 중요 섹션에 들어갑니다.부터fullCount는 0, 컨슈머 블록입니다.
2. 여러 명의 프로듀서가 프로듀서 크리티컬 섹션에 들어갑니다.다음 이유로 인해 N명 이상의 프로듀서가 크리티컬 섹션에 들어갈 수 없습니다.emptyCount진입을 제한하고 있습니다
3. 제작자는 한 번에 하나씩 큐에 액세스합니다.useQueue아이템을 큐에 넣을 수 있습니다.
4. 첫 번째 프로듀서가 중요한 부분을 벗어나면fullCount는 증가하여 하나의 소비자가 중요 섹션에 들어갈 수 있도록 합니다.

주의:emptyCount큐 내의 실제 빈 공간 수보다 훨씬 적을 수 있습니다.예를 들어 많은 생산자가 큐를 줄였지만 켜기를 기다리고 있는 경우입니다.useQueue빈자리를 채우기 전에.주의:emptyCount + fullCount ≤ N 생산자 또는 소비자가 중요한 섹션을 실행하지 않는 경우에만 평등하게 항상 유지됩니다.

작업명

정식 이름 V와 P는 네덜란드어의 머리글자에서 유래했다.V는 일반적으로 verhogen("증가")으로 설명됩니다.프로브렌("테스트" 또는 "시도"),^[4] 파스렌("합격") 및 파켄("grab")을 포함한 여러 가지 설명이 P에 제공되었습니다.이 주제에^[2] 대한 Dijkstra의 초기 논문은 P에 대한 의미로는 passing("통과")을, V에 대한 의미로는 vrijgave("해제")를 제공한다.또한 이 용어는 철도 신호에서 따온 것이라고 언급하고 있습니다.Dijkstra는 이어서 P가 prolaag(^[5]프로버 테벨라겐)의 약자, 문자 그대로 "축소하려고 한다" 또는 다른 경우에 사용되는 ^[6][7][8]"축소하려고 한다"라는 용어와 병행하려고 의도했다고 썼다.

ALGOL 68, Linux ^[9]커널 및 일부 영어 교재에서는 V 및 P 연산을 각각 업 및 다운으로 호출한다.소프트웨어 엔지니어링 실무에서는 표준 Java^[11] 라이브러리가 사용하는 signal and wait, release and^[10] acquire(신호 및 대기,^[10] 해제 및 취득) 또는 post 및 pend라고 부릅니다.일부^[12][13] 텍스트는 네덜란드어의 원래 이니셜과 일치하도록 비워지고 조달한다고 합니다.

세마포어 대 뮤텍스

뮤텍스는 바이너리 세마포어와 동일한 기본 구현을 사용하는 잠금 메커니즘입니다.그 차이는 사용법에 있다.바이너리 세마포어는 구어적으로 뮤텍스라고 불리지만 진정한 뮤텍스는 뮤텍스를 잠근 태스크만이 잠금을 해제하도록 되어 있는 보다 구체적인 사용 사례와 정의를 가지고 있습니다.이 제약사항은 세마포어 사용 시 발생할 수 있는 몇 가지 문제를 처리하는 것을 목적으로 합니다.

1. 우선 순위 반전:뮤텍스가 누가 잠갔는지 알고 잠금을 해제해야 하는 경우 우선순위가 높은 태스크가 뮤텍스에서 대기하기 시작할 때마다 해당 태스크의 우선순위를 승격할 수 있습니다.
2. 작업 조기 종료:뮤텍스는 또한 뮤텍스를 유지하는 작업을 ^{[citation needed]}실수로 삭제하지 않는 삭제 안전성을 제공할 수도 있습니다.
3. 종료 교착 상태: 어떤 이유로든 뮤텍스 유지 작업이 종료되면 OS는 이 상태의 뮤텍스 및 신호 대기 태스크를 해제할 수 있습니다.
4. 재귀 교착 상태: 작업은 동일한 횟수만큼 재진입 뮤텍스를 여러 번 잠글 수 있습니다.
5. 우발적인 릴리스:릴리스 태스크가 소유자가 아닌 경우 뮤텍스 릴리스 시 오류가 발생합니다.

「 」를 참조해 주세요.

• 동기화(컴퓨터 과학)
• 흡연자 문제
• 식사 철학자의 문제
• 리더 라이터 문제
• 잠자는 이발사 문제
• 모니터
• 스플리어스 웨이크업

레퍼런스

외부 링크

개요

• Hilsheimer, Volker (2004)「읽기/쓰기 뮤텍스 실장」(웹 페이지).분기별 11호 - 2004년 3분기
• Zelenski, Julie; Parlante, Nick. "Thread and Semaphore Examples" (PDF). Handout. CS107 Programming Paradigms. Stanford Engineering Everwhere (SEE). Spring 2008 (23).

레퍼런스

• Dijkstra, Edsger W. Cooperating sequential processes (EWD-123) (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (등기) (1965년 9월)
• "semaphore.h - semaphores (REALTIME)". The Open Group Base Specifications Issue 6 IEEE Std 1003.1, 2004 Edition. Open Group. 2004.
• Downey, Allen B. (2016) [2005]. "The Little Book of Semaphores" (2nd ed.). Green Tea Press.
• Leppäjärvi, Jouni (May 11, 2008). "A pragmatic, historically oriented survey on the universality of synchronization primitives" (PDF). University of Oulu, Finland.