KR19990077481A - 세마포어연산을수행하기위한방법및장치 - Google Patents

세마포어연산을수행하기위한방법및장치 Download PDF

Info

Publication number
KR19990077481A
KR19990077481A KR1019990006340A KR19990006340A KR19990077481A KR 19990077481 A KR19990077481 A KR 19990077481A KR 1019990006340 A KR1019990006340 A KR 1019990006340A KR 19990006340 A KR19990006340 A KR 19990006340A KR 19990077481 A KR19990077481 A KR 19990077481A
Authority
KR
South Korea
Prior art keywords
semaphore
value
queue
field
replacement
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
KR1019990006340A
Other languages
English (en)
Inventor
올트도날드에프.
포사이쓰존엠.
Original Assignee
포만 제프리 엘
인터내셔널 비지네스 머신즈 코포레이션
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 포만 제프리 엘, 인터내셔널 비지네스 머신즈 코포레이션 filed Critical 포만 제프리 엘
Publication of KR19990077481A publication Critical patent/KR19990077481A/ko
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/16—Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/52—Program synchronisation; Mutual exclusion, e.g. by means of semaphores
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/30003—Arrangements for executing specific machine instructions
    • G06F9/30076—Arrangements for executing specific machine instructions to perform miscellaneous control operations, e.g. NOP
    • G06F9/30087—Synchronisation or serialisation instructions

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Computer Hardware Design (AREA)
  • Multi Processors (AREA)

Abstract

정보 처리 시스템에서 공유 자원으로의 액세스를 제어하기 위한 세마포어는 오퍼랜드를 비교값과 비교하고, 오퍼랜드가 비교값과 동일하면, 비교된 오퍼랜드 및 최대 세 개의 추가 오퍼랜드까지 대체값으로 대체하는 어토믹(atomic) 연산을 사용하여 구현된다. 세마포어는 소정 값과 연속 번호(sequence count)를 포함하는 제1 세마포어 필드와 세마포어를 위한 큐에 대한 포인터를 포함하는 제2 세마포어 필드를 갖는다. 큐는 세마포어를 얻기 위해 대기자에 대응하는 0 이상의 엔트리(entry)를 갖고, 각 엔트리는 다음 엔트리 및 다음 엔트리에 대한 포인터를 갖는다. 세마포어를 수행하기 위해, 제1 세마포어 필드의 이전값은 비교값으로 저장된다. 증가된 연속 번호를 포함하는 제1 대체값은 특정 연산(specified operation)에 따른 제1 오퍼랜드로서 제1 세마포어 필드용으로 발생된다. 큐가 수정되면 제2 세마포어 필드를 위한 제2 대체값과 큐 엔트리 중 하나를 위한 제3 대체값은 제2 및 제3 오퍼랜드로서 발생된다. 그후 제1 세마포어 필드의 현재값은 현재값이 비교값과 일치하는지를 확인하기 위해 연속 번호를 포함하는 비교값과 비교된다. 그 다음 어토믹 연산으로의 비교 단계로(atomically with the comparing step), 제1 세마포어 필드의 현재값이 비교값과 일치하면 제1 오퍼랜드는 제1 대체값으로 대체되고, 큐가 수정되면, 제2 및 제3 오퍼랜드중 하나 또는 모두는 각 대응하는 대체값으로 대체된다. 제1 세마포어 필드의 현재값이 비교값과 일치하지 않으면, 세마포어 필드에 새롭게 저장된 값을 비교값으로 사용하여, 세마포어 연산이 재시도된다.

Description

세마포어 연산을 수행하기 위한 방법 및 장치 {METHOD AND APPARATUS FOR PERFORMING A SEMAPHORE OPERATION}
본 발명은 세마포어(semaphore)에 관한 연산을 수행하는 방법 및 장치에 관한 것으로, 더욱 상세하게는, 이진 세마포어(binary semaphore)를 수행하는 방법 및 장치에 관한 것이다.
컴퓨터 연산에서, 세마포어(semaphore)로 잘 알려진 직렬화 메카니즘(serialization mechanism)은 공유 자원(shared resource)으로의 액세스를 직렬화하기 위해 사용된다. 세마포어는 "0"과 소정의 양의 수(n) 사이에서 변화할 수 있는 정수이다(여기에서, n은 자원을 동시에 사용할 수 있는 요구자(requester)의 수임). 이진 세마포어의 경우, n=1이고 단지 한번에 하나의 요구자만이 자원을 이용할 수 있다. 초기에 세마포어 값은 n으로 설정된다. 자원으로의 액세스하기 위해, 요구자(예를 들어, 프로세스나 스레드(thread)와 같은 작업 유니트는 세마포어의 현재 값을 검사(test)한다. 현재 값이 "0"보다 크면, 요구자는 현재 값을 "1"씩 감소하고 자원을 사용하기 시작한다. 한편, 현재 값이 "0"이면, 요구자는 보류(suspend)되고 (즉, 슬립(sleep)되고) 세마포어를 얻기 위한 대기자(waiter)로 큐(queue)에 놓여진다. 자원을 해제(release)하기 위해, 요구자는 세마포어 값을 "1"씩 증가한다. 게다가, 큐에 세마포어를 얻기 위한 소정의 대기자가 존재하면, 대기자중 하나는 기입(post)되고, 그에 따라 요구자는 초기에 했던바와 같이 세마포어를 검사하여 자원을 사용하기 위한 시도를 재실행한다. 세마포어는 1965년 E. W. Dijkstra에 의해 처음 제안되었고, 인용참증으로 본 명세서에서 구체화된 것처럼, A. S. Tanenbaum의 Mordern Operating System (1982), 페이지 41-43; J. P. Hayes의 Computer Architecture and Organization (1988), 페이지 540; 및 W. R. Stevens의 UNIX Network Programming (1990), 페이지 137-152와 같은 간행물에 기재되어 있으며, 본 명세서에서 참조되어 본 발명의 일부를 이룬다.
세마포어의 두가지 주요 유형으로는 카운팅 세마포어(counting semaphore, n > 1)와 이진 세마포어(n=1)가 있다. 본 명세서에서는 세마포어를 구현할 때 발생하는 많은 고유의 문제점을 기술할 것이고 그런 다음 본 발명의 고성능 세마포어 구현을 기술할 것이다. 비록 본 발명은 이진 세마포어에 한정되지 않지만, 주로 이진 세마포어에 관해 설명할 것이다.
도 1은 세마포어 셋트의 C 언어 예를 도시한다. 세마포어 셋트는 C 프로그램이 셈겟 함수(semget function)를 호출할 때 처음 생성된다. (C 원시 언어에 관한 설명은 설명을 쉽게 하기 위한 것이다. 실행 단계를 실제로 실행하는 코드는 물론 원시 코드를 컴파일 함에 따라 생성된 목적 코드이다.) 호출자(caller)는 얼마나 많은 세마포어(120)가 세마포어 셋트(115)에 존재하는지를 명백히 보여준다. 세마포어 셋트(115)가 생성될 때, 세마포어 ID(semid)는 호출자에게로 리턴된다. 그런 다음 상기 세마포어 ID(semid)는 세몹(semop: 이하 'semop'이라 함) 함수에 해당하는 각 후속 호출(subsequent call)에 사용된다. 운영 체제(operating system)는 테이블(105)에 존재하는 세마포어 셋트를 계속 추적하고, 각 엔트리(entry, 110) 및 관련된 세마포어 셋트(115)는 상기 테이블(105)을 계속 추적한다.
도 2는 일반적으로 어떻게 세마포어 프로세싱이 동작하는지에 관한 일반적인 설명을 제공한다. 도 2는 동일한 세마포어를 얻기 위해 경쟁하는 프로세스 1(205)과 프로세스 2(210)를 도시한다. 이진 세마포어의 일반적인 동작은 세마포어 값을 1(이용가능)로 초기화하는 것이다. 애플리케이션이 세마포어를 얻길 원할 때, 상기 애플리케이션은 세마포어의 값을 감소하기 위해 semop를 semop(-1)로 한다. 중요한 세마포어 규칙은 세마포어 값이 음(nagative)으로 되지 않도록 하는 것이다. 따라서 "0"으로 세마포어 값을 감소시키는 semop의 제1 호출자는 세마포어를 소유한다. 세마포어 값을 감소시키는 임의의 후속 요구는 호출자가 보류되는 결과를 초래한다.
따라서 프로세서 1(205)은 semop(-1)를 호출한다(단계 220). semop(-1)는 세마포어 프로세싱을 위한 커널(kernel, 215)로 입력된다. 커널(215)은 세마포어의 상태를 보고 현재 "1"의 값인지를 확인한다. 커널(215)은 상기 세마포어 값을 "1"에서 "0"로 변경하여, 값을 감소시켜서, 프로세서 1(205)에게 액세스를 승인한다(단계 222). 그런 다음 커널(215)은 프로세스 1(205)로 리턴한다(단계 224). 현재 프로세스 1(205)은 중요한 자원(critical resource)이 세마포어에 의해 보호되더라도 액세스할 수 있다(단계 226). 상기 자원은 메모리, DASD에 있는 파일 또는 단지 다수의 프로세스에서 동시에 실행할 수 없는 코드의 중요 섹션(critical section)일 수 있다.
프로세서 1(205)이 세마포어를 소유하고 있는 동안에, 프로세스 2(210)는 역시 동일한 세마포어에 대해 semop(-1)를 요구한다(단계 228). 세마포어 값이 현재 0이고 음으로 될 수 없기 때문에, 커널(215)은 -1 을 수행할 수 없다. 따라서 커널(215)은 호출자(프로세서 2)를 보류한다(단계 230).
결국, 프로세스 1(205)이 중요 자원을 액세스하는 것을 종료하고 semop(+1)를 수행한다(단계 232). 커널(215)은 보류된 프로세스 2(210)가 다시 계속되도록 "0"에서 "1"로 세마포어 값을 수정한다(단계 234). 그런 다음 프로세스 2(210)를 동작하는 커널(215)은 세마포어 값을 "1"에서 "0"으로 수정하여(단계 236), 프로세스 2(210)에게 세마포어의 소유권을 인정한다. 그러면 프로세스 2(210)는 중요 자원을 액세스할 수 있다(단계 240). 제1 대기자를 기입한 후, 제어는 호출자에게 리턴된다(단계 238). 프로세스 2(210)가 자원을 액세스할 때, 프로세스 2(210)는 세마포어를 해제하기 위해 semop(+1)을 요구한다(단계 242). 커널(215)은 세마포어의 값을 "0"에서 "1"로 수정하여 세마포어를 이용 가능하게 한다. 세마포어를 얻기 위한 대기자가 존재하지 않기 때문에, 제어는 호출자에게 리턴된다(단계 244).
이상의 설명은 세마포어 프로세싱이 어떻게 동작하는지에 관한 논리적인 설명이었다. 대칭형 멀티프로세서(symmetric multiprocessor: SMP) 환경에서 작동할 때, 다른 중앙 처리 장치(Central Processing Units: CPUs)에서 동작하는 프로세스는 세마포어를 획득하고 해제하기 위한 시도를 동시에 할 수 있다. 도 3은 일반적인 세마포어 구현으로 발생할 수 있는 문제를 도시한다.
커널 세마포어 로직이 세마포어 값을 어토믹 연산으로(atomically) 갱신(update)하고 대기 큐(wait queue)를 유지하기 위해, 커널은 락(lock) 또는 뮤텍스(mutex)의 소정 형식(form)을 얻을 필요가 있다. 상기 커널이 얻을 수 있는 형식은 여러개 존재하고, 어떤 특별한 플랫폼(platform)에 독특한 것은 아니다. 커널이 이러한 락을 소유할 때, semop의 다른 호출자는 보류되어 상기 락을 기다리게 된다. 이러한 락은 세마포어의 개념과 매우 유사하다.
도 3에서, 의사코드(pseudocode)의 제1 블록은 semop(-1)를 수행하거나 또는 이진 세마포어를 획득하기 위해 semop로 프로세싱하는 것을 기재한다(단계 310). 첫 번째 단계는 세마포어 구조를 직렬화하기 위한 락을 획득하는 것이다(단계 312). 상기 락이 이용 불가능하다면, 시스템은 호출 스레드(calling thread)를 보류하고 프로세스를 표시하기 위한 큐 요소(queue element, 362)를 생성하여 락 대기 큐(360)에 상기 호출 스레드를 배치한다. 상기 락이 이용 가능하게 되면, 상기 프로세스는 다시 계속되고 프로세스가 프로세싱하는 동안 세마포어 구조가 변경되지 않을 것이라는 것을 알려주는 상기 단계(312)를 계속할 수 있다. 세마포어가 이용 가능하면(단계 314), 커널은 세마포어 값을 수정(modify)하여 호출자에게 세마포어를 승인한다. 그런 다음 커널은 내부 락(internal lock)을 해제하면, 내부 락은 대기 큐(360)에 존재하는 다른 프로세스를 다시 계속되게 할 수 있다(단계 318). 그런 다음에 제어는 호출자에게 리턴된다(단계 319).
세마포어 값이 이용 불가능하면(단계 320), 커널은 내부 락을 해제하고(단계 322) 세마포어 대기 큐(370)에 세마포어 대기자 요소(372)를 추가하여 호출자를 보류한다. 이러한 프로세스가 다시 계속되면(단계 326), 프로세tm는 단계(312)에서 시작한다(단계 328).
프로세스가 이진 세마포어를 해제하기 위해 semop(+1)를 호출하면(단계 340), 우선 커널은 세마포어 구조로의 액세스를 직렬화하기 위해 내부 락을 획득한다(단계 342). 상기 락이 이용 불가능하면, 시스템은 호출 스레드를 보류하고 프로세스를 표시(represent)하기 위한 큐 요소(362)를 생성하여 락 대기 큐(360)에 상기 호출 스레드를 배치한다. 상기 락이 이용 가능하게 되면, 상기 프로세스는 다시 게속되고 프로세스가 프로세싱하는 동안 세마포어 구조가 변경되지 않을 것이라는 것을 알려주는 상기 단계(342)를 계속할 수 있다. 그런 다음에 커널은 세마포어 값을 "1"씩 증가하여 세마포어 값을 수정한다. 세마포어 큐(370)에 대기자(372)가 존재하면, 제1 요소(372)는 제거되고 제1 요소(372)가 표시하는 프로세스는 다시 계속된다(단계 346). 다음으로 커널은 내부 락을 해제하며(단계 348), 내부 락은 대기 큐(360)에 존재하는 다른 프로세스를 다시 계속되게 할 수 있다. 제어는 호출자에게 리턴된다(단계 350).
이제 병리적(pathological) 예를 고려하여 500개의 프로세스가 세마포어를 동시에 요구한다고 하자. 하나의 프로세스는 내부 락을 성공적으로 획득하며 499개의 프로세스는 보류되고 내부 락을 위해 대기 큐(360)에 추가된다. 그런 다음 제1 프로세스는 내부 락을 해제하고, 각각의 프로세스는 차례로 세마포어가 사용 불가능한지를 검색하기 위해 락을 획득하고 세마포어 대기 큐(370)에서 2차로 보류된다. 이제 499개의 프로세스가 이러한 프로세싱 중일 때, 제1 프로세스는 세마포어를 해제하기 위해 준비한다. 세마포어를 해제하는 것은 역시 같은 내부 락을 요구하는 것이기 때문에(단계 342에서), 상기 프로세스는 내부 락을 얻기 위해 대기 큐(360)의 마지막에 놓여진다. 이것은 각 프로세스가 단순히 내부 락 대기 큐(360)에서 세마포어 대기자 큐(370)로 단순히 이동되도록 하는 것이다.
상기 동작을 유사한 형식으로 설명하기 위해, 쇼 티켓을 사기 위해 기다리는 사람의 줄을 상상하자. 각각의 사람은 줄의 앞쪽으로 이동함에 따라, 이용 가능한 티켓이 없다는 말을 듣는다. 그러나 그들은 누군가가 티켓을 취소할 때까지 줄을 서서 기다린다. 자신의 티켓을 취소하기 원하는 사람이 오더라도, 티켓을 사길 원하는 모든 사람들과 동일한 선에서 기다려야 한다. 그렇다면 이러한 것을 계속 반복하면 당신은 많은 시간을 의미없이 기다려야 한다. 컴퓨터 시스템에서, 이러한 것은 컴퓨터 성능을 떨어뜨리고 용량을 제한한다.
도 1은 다수의 세마포어 셋트를 관리하는 커널용 내부구조(infrastructure)를 도시하는 도면.
도 2는 도 1과 동일한 세마포어를 요구하는 두 개의 프로세스 사이의 상호작용(interaction)을 도시하는 도면.
도 3은 종래의 세마포어 프로세싱을 위한 로직 순서도.
도 4는 세마포어 셋트의 각 세마포어의 구조 및 동작 실행 유니트를 나타내는 스레드 제어 블록을 도시하는 도면.
도 5a는 세몹(semop) 함수로의 엔트리를 도시하고 세마포어가 이용 불가능할 때 프로세싱을 도시하는 본 발명에 따른 세마포어 프로세싱을 위한 로직 순서도.
도 5b는 세마포어가 이용 가능하고 요구가 세마포어를 얻고자하는 것일 때 세마포어 프로세싱의 로직 순서도.
도 5c는 세마포어의 대기자가 존재하거나 존재하지 않을 두가지 경우에 대해서, 세마포어 해제를 위한 세마포어 프로세싱의 로직 순서도(대기자가 존재하면 큐로부터 제거된다).
도 5d는 대기자가 기입(post)되는 경우 세마포어 해제를 위한 세마포어 프로세싱의 로직 순서도. (기입이 실패하면, 다음 대기자는 대기 큐로부터 제거되어 기입되며, 대기자가 성공적으로 기입되거나 또는 대기 큐가 비어있을 때까지 계속된다.
도 5e는 대기 큐로부터 스레드 제어 블록을 제거하기 위한 회복 프로세싱(recovery processing)을 도시하는 도면.
도 6a는 비교 및 교체(COMPARE AND SWAP) 연산 전에, 세마포어가 이용 불가능하고 대기 큐가 비어있을 때 세마포어에 대한 요구를도시하는 도면.
도 6b는 비교 및 교체 연산이 성공적으로 이루어진 후에, 세마포어가 이용 불가능하고 대기 큐가 비었을 때 세마포어에 대한 요구를 도시하는 도면.
도 7a는 비교 및 교체 연산 전에, 세마포어가 이용 불가능하고 대기 큐가 비어있지 않을 세마포어를 얻기 위한 요구를 도시하는 도면.
도 7b는 비교 및 교체 연산 후에, 세마포어가 이용 불가능하고 대기 큐가 비어있지 않을 때 세마포어를 얻기 위한 요구를 도시하는 도면.
도 8a는 비교 및 교체 연산 전에, 세마포어가 이용 가능하고 대기 큐가 비어있을 때 세마포어를 얻기 위한 요구를 도시하는 도면.
도 8b는 비교 및 교체 연산 후에, 세마포어가 이용 가능하고 대기 큐가 비어있을 때 세마포어를 얻기 위한 요구를 도시하는 도면.
도 9a는 비교 및 교체 연산 전에, 대기 큐에 대기자가 존재하지 않을 때 세마포어 해제를 도시하는 도면.
도 9b는 비교 및 교체 연산 후에, 대기 큐에 대기자가 존재하지 않을 때 세마포어 해제를 도시하는 도면.
도 10a는 비교 및 교체 연산 전에, 대기 큐에 대기자가 존재할 때 세마포어 해제를 도시하는 도면.
도 10b는 비교 및 교체 연산 후에, 대기 큐에 대기자가 존재할 때 세마포어 해제를 도시하는 도면.
도 11a는 비교 및 교체 연산 전에, 세마포어가 이미 해제된 후 대기 큐로부터 대기자를 제거하는 프로세싱을 도시하는 도면.
도 11b는 비교 및 교체 연산 후에, 세마포어가 이미 해제된 후 대기 큐로부터 대기자를 제거하는 프로세싱을 도시하는 도면.
도 12a는 비교 및 교체 연산 전에, 스레드가 종료하기 때문에, 대기 큐로부터 스레드 제어 블록을 제거하는 회복 프로세싱을 도시하는 도면.
도 12b는 비교 및 교체 연산 후에, 스레드가 종료하기 때문에, 대기 큐로부터 스레드 제어 블록을 제거하기 위한 회복 프로세싱을 도시하는 도면.
도 13은 비교 및 교체 연산을 수행하는데 사용된 세마포어 및 내부 데이터 구조(internal data structure)를 도시하는 도면.
본 발명은 오퍼랜드를 비교값(comparison value)과 비교하고 오퍼랜드가 상기 비교값과 같다면, 비교된 오퍼랜드와 세 개의 추가 오퍼랜드(additional operand)까지 대체값으로 대체하는 어토믹 연산을 사용하여 구현되는 정보 처리 시스템에서 공유 자원(shared resource)으로의 액세스를 제어하기 위한 세마포어에 관한 것이다. 본 발명에 따라서, 세마포어는 소정 값을 포함하는 제1 세마포어 필드 및 세마포어를 위한 큐에 대한 포인터(pointer)를 포함하는 제2 세마포어 필드를 갖는다. 큐는 세마포어의 대기자에 대응하는 "0" 또는 그 이상의 엔트리(entry)를 갖고, 각 엔트리는 다음 엔트리 및 다음 엔트리에 대한 포인터를 갖는다. 세마포어를 구현하기 위해, 세1 세마포어 필드의 이전값은 비교값으로 저장된다. 제1 대체값은 특정 연산(specified operation)에 따른 제1 오퍼랜드로서 제1 세마포어 필드용으로 발생된다. 큐가 수정되면 제2 세마포어 필드를 위한 제2 대체값과 큐 엔트리중 하나를 위한 제3 대체값은 제2 및 제3 오퍼랜드로서 발생된다. 그 후 제1 세마포어 필드의 현재값은 현재값이 비교값과 일치하는지를 확인하기 위해 비교값과 비교된다. 그 다음, 어토믹 연산으로 비교하는 단계로(atomically with the comparing step), 현재값과 비교값이 일치하면, 제1 오퍼랜드는 제1 대체값으로 대체되고, 만약 큐가 수정되면, 제2 및 제3 오퍼랜드 중 하나 또는 모두는 각 대응하는 대체값으로 대체된다. 제1 세마포어 필드의 현재값이 비교값과 일치하지 않으면, 세마포어 필드에 새롭게 저장된 값을 비교값으로 사용하여 세마포어 연산은 재시도된다.
바람직하게, 제1 세마포어 필드는 또한 세마포어를 갱신하기 위해 마지막 프로세스를 식별하는(identify) 프로세서 ID(PID)와 세마포어가 갱신될 때마다 증가되는 연속 번호를 포함한다. 본 발명은 특별 플랫폼 또는 이진 세마포어에 한정되지 않지만, IBM 시스템/390TM(S/390TM) 하드웨어 플랫폼으로 구현된 본 발명의 바람직한 실시예에서는 세마포어 작용 중에서 가장 일반적으로 사용된 형태, 즉 이진 세마포어를 직렬화하기 위해 새로운 S/390 하드웨어 인스트럭션 플랫폼 락 연산(Perform Locked Operation, 이하, 'PLO'라 칭함)을 사용한다.
PLO 인스트럭션의 비교 및 교체(compare and swap) 형태는 필드가 변경되지 않는다면 필드가 대체되도록 하며 이는 비교 복사(comparision copy)가 상기 필드뿐만 아니라 최대 세 개의 다른 필드까지 대체하며 획득되었기 때문이다. 일반적으로 본 발명은 이진 세마포어에 한정되지 않지만, 이진 세마포어로의 구현을 제한하여, 세마포어 변경으로 수정될 필요가 있는 필드는 PLO 인스트럭션에 의해 허용된 최대 네 개로 한정될 수 있다. PLO 인스트럭션을 사용하여, 세마포어 값과 세마포어 대기 큐에 대한 갱신은 하나의 미세한 인스트럭션에 대해 직렬화될 수 있다. 이진 세마포어 규칙은 다음과 같다.
1. semop()에 관한 세마포어 연산의 개수는 한 개이다.
2. 세마포어 값이 "0" 또는 "-1"일 때 semop() 값은 반드시 +1이다("0" 또는 "1" 세마포어 값이 가짐).
3. SEM_UNDO는 semop()에서는 인정되지 않는다.
4. semctl() setval 또는 setall value는 setall이 실행될 수 있을 때 제한으로 "0" 또는 "+1"로만 될 수 있고, "1에서 0" 또는 "0에서 0"으로부터는 단지 "0에서 1"로는 설정될 수 없다.
이러한 확장(extension)을 위한 어떠한 규칙 위반도 요구된 연산을 실패하게 한다. 이미 우리가 주목해온 광범위한 대부분의 세마포어 사용은 상기한 규칙을 준수한다.
모든 세마포어 값 또는 세마포어 대기 큐 변경에서 증가되고 PLO 비교와 교체 연산의 대상인 연속 번호의 사용은 변경의 설정과 실제 변경 사이에서 세마포어에 생긴 소정 변경을 검출한다. 변경이 발생하지 않으면 갱신이 이루어진다. 변경이 발생했다면 갱신은 이루어지지 않고 다시 설정된다.
본 발명에 따른 연산의 특별한 예로서, 동작 유니트 (예를 들면 스레드)가 이진 세마포어를 요구했다고 가정한다. 스레드는 연속 번호와 세마포어 값을 포함하는 복사된 비교 및 교체 영역을 갖는다. 그런 다음 세마포어가 유지되는지를 판정한다. 세마포어가 유지되는 경우, 스레드는 대기 큐를 탐색한다. 대기 큐에 대기자가 없는 경우, 스레드는 비교 및 교체 파라메터(parameter)를 설정하여 연속 번호는 증가되고 대기 큐의 헤드(head) 및 테일(tail) 포인터는 상기 스레드를 가리킨다. 그런 다음 비교 및 교체 인스트럭션이 실행된다. 비교 및 교체 인스트럭션이 성공적이면, 연속 번호는 갱신되고 대기 큐 포인터는 상기 스레드를 가리킨다. 그런 다음 상기 스레드는 보류된다. 비교 및 교체 인스트럭션이 성공적이지 않으면, 상기 스레드는 동작을 처음부터 다시 시작한다. 가장 가능성이 있는 것은, 세마포어가 해제되거나 또는 대기 큐가 갱신된 것이다. 세마포어가 현재 이용 가능하다면, 스레드는 세마포어 값을 변경하고 연속 번호를 증가하기 위해 설정된다. 대기 큐가 변경되었다면, 스레드는 대기 큐의 마지막에 스레드 자신을 추가하도록 설정한다. 그런 다음, 어떤 경우에도 비교 및 교체 인스트럭션이 실행되고, 비교 및 교체 인스트럭션이 성공적이지 않으면, 스레드는 동작을 처음부터 다시 시작한다.
다음은 PLO 비교 및 교체 인스트럭션으로 전술한 바와 같은 세마포어 흐름을 갖는 것이다.
1. 동작 유니트(즉, 스레드)는 세마포어(semop(-1))를 획득하기 위해 semop요구를 발행한다.
2. 커널은 비교 및 교체 데이터(세마포어 값, 연속 번호 및 세마포어를 갱신하기 위한 마지막 프로세스의 프로세스 ID)를 저장한다. 세마포어가 이용 불가능하면(semval 0), 커널은 대기 큐에 동작 유니트를 배치하고 연속 번호를 증가하도록 설정한다.
3. 커널은 세마포어 대기 큐에 동작 유니트를 배치하고 연속 번호를 갱신하기 위해 (세개의 추가 필드까지 저장될 수 있는) PLO 비교와 교체 및 저장 인스트럭션을 사용한다. 비교 및 교체 데이터가 변경되지 않으면 갱신은 실행된다. 비교 및 교체 데이터가 변경되면, 커널은 이전 단계로 되돌아간다.
4. 동작은 보류된다(즉, 대기한다).
5. 동작 유니트가 결국 기입된다(이미 작동 상태로 됨)
6. 커널은 비교 및 교체 데이터(세마포어를 갱신하기 위한 마지막 프로세스의 세마포어 값, 연속 번호 및 프로세스 ID)를 저장한다. 세마포어가 이용 가능하면(semval 1, 대기 큐가 비어있거나 상기 스레드가 기입), 커널은 새로운 세마포어 값(semval 0)을 설정하고 연속 번호를 증가하도록 설정한다.
7. 커널은 세마포어 대기 큐로부터 동작 유니트를 제거하고, 새로운 세마포어 값을 설정하고 연속 번호를 갱신하기 위해 PLO 비교와 교체 및 저장 인스트럭션을 사용한다. 비교 및 교체 데이터가 변경되지 않으면, 갱신이 실행된다. 비교 및 교체 데이터가 변경되면, 커널은 이전 단계로 되돌아간다.
8. 커널은 호출자에게로 빠져 나간다.
유사하게, 본 발명의 해제 흐름은 다음과 같다.
1. 동작 유니트는 세마포어(semop(+1))를 해제하기 위해 semop 요구를 발행한다.
2. 커널은 비교 및 교체 데이터(세마포어를 갱신하기 위한 마지막 프로세스의 세마포어 값, 연속 번호 및 프로세스 ID)를 저장하고, 새로운 세마포어 값(semval 1)을 설정하고 연속 번호를 증가하기 위해 설정한다. 대기 큐가 비어있지 않으면, 커널은 역시 제거되는 제1 대기자를 설정한다.
3. 커널은 대기 큐가 비어있지 않으면 새로운 세마포어 값을 설정하고, 연속 번호를 갱신하고 제1 대기자를 제거하기 위해 PLO 비교와 교체 및 저장 인스트럭션을 사용한다. 비교 및 교체 데이터가 변경되지 않으면 업 데이트된다. 비교 및 교체 데이터가 변경되면, 커널은 이전 단계로 되돌아간다.
4. 커널은 대기 큐에 제1 동작 유니트를 기입한다.
5. 커널은 호출자에게로 빠져 나간다.
상기한 예로부터 보여지는 것처럼, 본 발명에서 세마포어가 이용 불가능하다면 아마도 세 번 대신에 단지 한번의 보류만이 이루어진다. 세마포어의 해제는 락을 대기하지 않는다. 대표적인 구현에서, 종래 방법(심할 경우)을 이용하여 세마포어를 획득하기 위한 인스트럭션의 개수는 대략 30,000개 정도인데 반하여 본 발명을 위해서는 약 400개의 인스트럭션이 필요하다.
도 4 내지 도 13은 본 발명을 기술한다. 본 발명의 주요 결과는 락(lock)이 추가되지 않는 세마포어를 제공하는 것이다.
도 4는 세마포어 셋트(115)(도 1)에 존재하는 세마포어(120) 구조를 도시한다. 세마포어(415)로 생각되는 상기 구조 부분은 프로세스 ID(PID, 425), 연속 번호(SEQ, 430), 및 세마포어 값(VAL, 435)으로 이루어진다. 바람직한 실시예에서, 세마포어 필드(415)는 4-바이트(32-비트) PID(425), 2-바이트 연속 번호(430) 및 2-바이트 세마포어 값(435)을 포함하는 더블 워드(64-비트) 필드이다. 세마포어 외에, 세마포어를 얻기 위해 대기하고 있는 스레드를 계속 추적하기 위해 사용되는 큐 앵커(queue anchor)(또는 큐 헤더(queue header,420)가 존재한다. 대기자 큐(370, 도 3)는 단일 스레드(single-threaded)의, 더블-헤드 큐(double-headed queue)로 취급된다. 상기 큐 앵커(420)는 큐(370)의 헤드에 해당하는 포인터(440) 및 큐의 테일(마지막 엔트리 372)에 해당하는 포인터(445)를 필요로 한다. 바람직한 실시예에서, 큐 헤더(420)는 4-바이트 헤드 포인터(440)와 4-바이트 테일 포인터(445)를 포함하는 더블-워드 필드이다.
본 명세서에서, 동작 유니트는 스레드(프로세스에는 하나 이상의 스레드가 존재할 수 있으나, 이러한 것은 설계에 영향을 미치지 않음)로 불리운다. 상기 스레드는 스레드 제어 블록(450)을 갖는 운영 체제OS, Operating System) 커널(215, 도 2)에 의해 추적(track)된다. 스레드 제어 블록(450)의 부분(470)은 세마포어와 스레드와의 관계(involvement)를 계속 추적하기 위해 사용된다. 이러한 세마포어 영역(470)에는 대기자 큐(370)를 위해 사용되는 포워드 포인터(NEXT, 455)와 세마포어 프로세싱에 사용되는 플러그 셋트(460)가 존재한다. 상기 영역(470)에 존재하는 주 플래그(primary flag)는 스레드 제어 블록이 대기 큐에 존재하는지를 나타낸다. 바람직한 실시예에서, 스레드 제어 블록 부분(470)은 4-바이트 포워드 포인터(455) 및 4-바이트 플래그 영역(460)을 포함하는 더블-워드 필드이다.
이미 기술된 것처럼, semop(-1)는 세마포어의 소유권을 획득하기 위해 이용되고 semop(+1)는 세마포어의 소유권을 해제하기 위해 사용된다. semop를 위한 개략적인 순서도는 도 5a 내지 도 5d에 도시된다.
도 5a는 semop 함수로 들어가는 것을 도시한다(단계 502). semop 프로세싱하는 초기 동안에, 세마포어 로직은 세마포어 ID의 테이블(105)에서 세마포어 ID(semid, 110)를 탐색(look up)하여 세마포어 셋트(115)의 위치를 정한다. 그런 다음 상기 세마포어 로직은 semop 호출에서 지나간 세마포어 번호에 따라 특정 세마포어(120)의 위치를 정한다. 이러한 것은 세마포어 프로세싱의 일반적인 단계이지 본 발명에 해당하는 부분은 아니다. 본 발명의 해당 부분이 아니기 때문에 검사하게 기술되지 않는 일반적인 단계는 호출자 파라메터를 검사하는 타탕성(validity) 단계와 사용자가 세마포어 셋트로 액세스하는 것을 검사하는 허가(permission) 단계이다. 세마포어의 프로세싱은 다음에 집중적으로 설명될 것이다.
semop 프로세싱이 해야할 첫 번째 일은 semop 프로세싱이 획득(-1) 또는 해제(+1)인지를 판단하는 것이다(단계 504). 해제(OP=1)라면, semop 프로세싱은 도 5c에 도시된 것처럼 이루어진다(단계 506). 요구가 세마포어(OP=-1)를 획득하기 위한 것이라면, 세마포어가 획득될 때까지 무한 루프(infinite loop)로 들어간다(단계 508). 프로세싱은 여러개의 가능한 세마포어 상태(possible state)를 처리하기 위해 분산된다. 경우 1(단계 510)로 도시된 검사는 세마포어가 이용 불가능하고(semval=0) 대기 큐(370)(헤드 포인터(440)에 의해 가리켜진 것처럼)가 비어있는지를 판정한다. 상기 경우에, 프로세싱은 도 6a 내지 도 6b에 도시된 것처럼 이루어진다(단계 512).
경우 2로 도시된 다음 검사는 세마포어가 이용 불가능한지를 판정한다(단계 514). 이용 불가능하다는 것은 세마포어 값(semval)이 '0"과 같거나 또는 대기 큐(370)에 대기자가 존재할 때와 같은 일반적인 경우가 될 수 있으나, 상기 스레드가 세마포어를 얻기 위해 다음에 기입되었던 경우는 아니다. 이용 불가능한 세마포어를 얻기 위한 상기 두 번째 경우는 대기중인 세마포어의 요구에 앞서 새로운 세마포어의 요구를 차단하지 못하도록 하는 것이다. 이러한 경우에, 프로세싱은 도 7a 내지 도 7b에 도시된 것처럼 이루어진다(단계 516).
상기 경우 중 어느 경우에도 해당되지 않으면, 프로세싱은 도 5b에 도시된 것과 같이 이루어진다(단계 522).
경우 1 또는 2를 위해 발생된 프로세싱이라면, 세마포어 조작 기능(semaphore mainpulation)이 성공적이었는지를 검사하는 도 5adml 단계(524)에서 도 5a로 제어가 리턴된다. 모든 것이 "예(OK)"이면, 호출 스레드는 대기 상태로 놓여진다(단계 526). 세마포어를 소유하는 스레드(owning thread)가 세마포어를 해제할 때까지 상기 스레드는 대기 상태를 유지한다. 세마포어 조작 기능이 성공적이지 않으면, 단계(508)로 되돌아가고, 연산을 재시도한다. 세마포어 조작 기능의 실패 원인이 다른 스레드가 세마포어 상태를 수정하였기 때문이므로, 단계(510)에서 시작하는 모든 검사는 재실행된다.
도 5b는 semop(-1)이 처리되고 있고 세마포어가 현재 이용 가능한 경우를 도시한다. 대기 큐(370)에 대기자가 존재하지 않을 경우나 또는 상기 스레드가 세마포어를 획득하기 위해 기입되는 경우는, 경우 3에 해당되고(단계 530), 도 8a 내지 도 8b에 도시된 것처럼 프로세싱이 이루어진다(단계 532). 비교 및 교체 연산이 성공적이었다면(단계 542), 제어는 세마포어를 가지는 사용자에게로 리턴한다(단계 544). 비교 및 교체 연산이 실패하였다면, 프로세싱은 처음부터 다시 시작하고 도 5a의 단계(508)로 리턴한다(단계 546).
도 5a에서 검사(504)가 semop(+1)를 검출할 때, 제어는 도 5c로 넘어간다(단계 506). 도 5c를 참고로 하여, 세마포어 해제 로직은 DO FOREVER 루프로 시작한다(단계 550). 세마포어를 해제할 때 고려해야 할 2가지 경우가 존재한다. 경우 4(단계 552)는 대기 큐(370)에 대기자가 존재하지 않을 때이다. 경우 4에 해당하는 비교 및 교체 연산은 도 9a 내지 도 9b에 도시된 바와 같다(단계 554). 세마포어 조작 기능이 시도된 후에, 비교 및 교체 연산 결과가 검사된다(단계 560). 연산이 성공적이었다면, 제어는 호출자로 리턴한다(단계 566). 비교 및 교체 연산이 성공적이지 않았다면, 제어는 세마포어를 해제하기 위한 시도를 반복하기 위해 단계(550)로 리턴한다(단계 564). 세마포어 해제가 실패하는 주요 원인은 새로운 대기자가 대기 큐(370)에 추가되었기 때문이다.
경우 5(단계 556)는 대기 큐(370)에 대기자가 존재할 때이다. 경우 5에 해당하는 비교 및 교체 연산은 도 10a 내지 도 10b에 도시된 것과 같다(단계 558). 연산이 성공적이었다면(단계 568), 제어는 도 5d로 넘어간다. 비교 및 교체 연산이 성공적이지 않았다면, 제어는 세마포어를 해제하기 위한 시도를 반복하기 위해 단계(550)로 리턴한다(단계 570). 세마포어 해제가 실패하는 주요 원인은 새로운 대기자가 대기 큐(370)에 추가되었기 때문이다.
도 5d는 세마포어가 해제된 이후에 발생하는 프로세싱을 도시한다. 제1 단계는 도 5c의 세마포어 해제 연산에서 대기 큐(370)로부터 제거되었던 대기자를 기입(즉 다시 계속하기 위한)하기 위한 것이다(단계 572). 기입이 성공적이었다면(단계 574), 제어는 호출자로 리턴된다(단계 576). 기입이 실패하면, 대기 큐(370)에 대기자가 존재하는지를 확인하기 위한 체크가 이루어진다. 대기 큐(370)에 대기자가 존재하면, 도 11a 내지 도 11b에 도시된 비교 및 교체 연산은 최상위 대기자(top waiter)를 제거하기 위해 실행된다(단계 580). 비교 및 교체 연산이 성공적이었다면(단계 582), 대기 큐(370)에서 방금 제거된 대기자는 이전과 같이 기입된다(단계 572). 단계(578)에서 대기 큐(370)에 대기자가 존재하지 않으면, 기입할 대기자가 존재하지 않기 때문에, 제어는 호출자로 리턴된다(단계 576). 기입이 실패하는 주요 원인은 목표 스레드가 신호를 수신하고 더 이상 대기 상태로 있지 않기 때문이다. 단계(582)에서 비교 및 교체 연산이 실패하면, 제어는 다른 대기자가 존재하는지를 검사하는 단계(578)로 리턴한다.
도 5e는 스레드의 종료를 통지받을 때(아마도 종료신호) 스레드가 세마포어 대기 큐에 자신의 스레드 제어 블록을 갖고 있을 경우 단계(584)에서 시작하는 회복 프로세싱의 순서도를 도시한 것이다. "DO FOREVER"루프는 스레드 제어 블록이 세마포어 대기 큐(370)로부터 성공적으로 제거되거나 또는 스레드 제어 블록이 더 이상 큐(370)에 존재하지 않는다고 판정될 때까지 계속된다(entered). 세마포어는 대기자를 기입하기 위해 탐색중인 다른 프로세스에 의해 제거될 수 있다는 것을 주의해야 한다. 이러한 것은 대기 큐(370)가 스캔(scan)되는 곳에서만 이루어진다. 세마포어 연속 번호(430)는 루프를 시작할 때에 저장된다(단계 588). 그런 다음 대기 큐(370)는 대기 큐(370)에 존재하는 스레드 제어 블록의 위치를 검색하기 위해 스캔된다(단계 590). 연속 번호(430)가 대기 큐(370)의 스캔 도중 어느 때라도 변경되면(단계 592), 루프는 처음부터 다시 시작된다(단계 586). 회복 프로세싱에서 스캔되고 있는 요소가 스레드 제어 블록을 위한 요소가 아니면(단계 594), 대기 큐(370)의 마지막에 도달했는지를 검사한다. 스캔 동작이 대기 큐(370)의 마지막에 도달하면, 스레드 제어 블록은 이미 제거된 상태이고 더 이상의 프로세싱은 요구되지 않는다(단계 599). 단계(596)에서 스캔 동작이 대기 큐(370)의 마지막에 도달하지 않으면, 루프는 되돌아간다(단계 590). 대기자 요소가 단계(594)에서 발견되면, 도 12a 내지 도 12b에 도시된 비교 및 교체 연산은 대기 큐(370)로부터 상기 대기자의 요소를 제거하기 위해 수행된다(단계 597). 비교 및 교체 연산이 실패하면(단계 598), 코드 루프는 처음으로 되돌아가 재시도한다(단계 586). 비교 및 교체 연산이 성공적이면, 상기 스레드는 더 이상 대기 상태(wait chain)에 존재하지 않고 종료될 수 있다(단계 599).
도 6a 내지 12b에 도시된 비교 및 교체 연산을 검사하게 설명하기 전에, 본 발명의 바람직한 실시예에 의해 사용되는 PLO 인스트럭션에 대한 일반적인 이해를 제공하여 설명을 돕는다. PLO 인스트럭션의 사용은 도 4와 관련하여 기술될 것이다. 대부분의 컴퓨터 시스템은 시스템 저장 장치(storage)로 어토믹 갱신(atomic updates)을 수행하도록 하는 하드웨어 인스트럭션을 포함한다. IBM S/390 하드웨어 플랫폼에서 몇 개의 이전 인스트럭션(previous instruction)은 Enterprise Systems Architecture/390 Principles of Operation, IBM Publication SA22-7201-02(1994)에 기재된, Compare and Swap(CS), Compare Double and Swap(CDS), 및 Test and Set(TS)이며, 상기 문헌은 본 명세서에서 참조되어 본 발명의 일부를 이룬다. PLO는 S/390 하드웨어 플랫폼에서는 상대적으로 새로운 어토믹 인스트럭션이다. 상기 리스트된 어토믹 인스트럭션이 저장 장치의 싱글 워드 또는 더블 워드의 어토믹 갱신이 가능하도록 하는 반면에, PLO 인스트럭션은 저장 장치의 해체 위치(disjoint location)에서 다수의 필드의 어토믹 갱신이 가능하게 한다. PLO 연산은 다음의 특허 출원 및 특허 공보에 기재되어 있으며, 이들은 본 명세서에서 참조되어 본 발명의 일부를 이룬다.
1997년 5월 28일에 출원된, 미국 출원 번호 제08/864,402호(제목: 동시의 프로세서 요청에 의해 데이터 자원을 액세싱하는 직렬화되는 컴퓨터 시스템에서의 블록킹 심볼 제어(Blocking Symbol Control in a Computer System to Serialize Acessing a Data Resource by Simultaneous Processor Requests), 발명자: S. J.Greenspan 등).
1997년 5월 28일에 출원된, 미국 출원 번호 제08/864,585호(제목: 컴퓨터 시스템에서의 데이터 자원의 액세싱을 직렬화하기 위한 블록킹 심볼 제어 관련 프로세서(Processor Associated Blocking Symbol Controls for serializing the Acessing a Data Resource in a Computer System), 발명자: S. J.Greenspan 등).
1997년 9월 5일에 출원된, 미국 출원 번호 제08/924,890호(제목: 프로세서 실패로 인해 로스트(Lost)라면 데이터 일관성(data consistency)의 회복을 지지하기 위한 PLO 인스트럭션을 실행하는 방법, 및 프로세서 실패후 데이터 일관성을 회복하는 방법(Method of Executing Perform Locked Operation Instructions for Supporting Recovery of Data Consistency If Lost Due to Processor Failure, and a Method of Recovering the Data Consistency After Processor Failure), 발명자: S. J.Greenspan et al).
"ESA/390 Principles of Operation" 7.5.79 via IBM BookManager BookServer,http://ppdbooks.pok.ibm.com/cgi-bin/bookmgr/bookmgr.층/BOOKS/DZ9AR004/7.5.69
본 발명에 의해 사용되는 PLO 인스트럭션에 의해 제공된 연산은 다음과 같다.
1. 추가 저장없는 더블 비교 및 교체(compare and swap double). 이것은 더블-워드(64-비트) 오퍼랜드를 더블-워드 비교값(double-word comparison value)과 비교하고, 오퍼랜드가 비교값과 동일하면, 더블-워드 대체값(double-word replacement value)으로 비교된 오퍼랜드를 대체한다.
상기 연산은 세마포어가 획득되거나 해제되고 대기 큐(370)에 대기자가 존재하지 않으면 사용된다(도 8a 내지 도 8b 및 도 9a 및 도 9b). 세마포어 대기 큐(370)에 해당하는 요구된 갱신이 존재하지 않기 때문에, 수정되는 더블-워드 필드만이 세마포어 필드(415)로 된다.
1. 더블 비교와 교체 및 두 개의 추가 더블 워드 저장. 이것은 더블-워드(64-비트) 오퍼랜드를 더블-워드 비교값과 비교하고, 오퍼랜드가 비교값과 같으면, 더블-워드 대체값으로 비교된 오퍼랜드와 추가된 두 개의 더블-워드 오퍼랜드를 대체한다.
상기 연산은 첫 번째 대기자가 큐에 추가되거나 큐로부터 제거되면 사용된다(도 6a와 도 6b, 도 10a와 도 10b 및 도 11a와 도 11b). 세 개의 더블-워드 필드(즉, 세마포어 필드(415), 큐 헤더(420) (만약 첫번째 대기자가 추가되면) 대기 큐(370)의 마지막에서 (첫번째 대기자가 제거되면) 대기 큐(370)의 헤드에서 스레드의 현재 스레드 제어 블록(770))은 수정된다
1. 더블 비교와 교체 및 세 개의 추가 더블 워드를 저장. 이것은 더블 워드(64-비트) 오퍼랜드를 더블-워드 비교값과 비교하고, 오퍼랜드가 비교값과 같으면, 더블-워드 대체값으로 비교된 오퍼랜드와 추가된 세 개의 더블-워드 오퍼랜드를 대체한다.
상기 연산은 후속 대기자(subsequent waiter)가 대기 큐(370)에 추가되거나 대기 큐(370)로부터 제거되는 경우 사용된다(도 7a와 도 7b 및 도 12a와 도 12b). 네 개의 더블-워드 필드(즉, 추가되거나 제거되는 세마포어 필드(415), 큐 헤더(420) 및 스레드 제어 블록 필드(470 및 770), 및 추가되고 제거되는 대기 큐(370)에 존재하는 스레드의 바로 이전 선행자(immediate predecessor)인)는 수정된다.
비교 및 교체 연산은 필드(415)에 대해(against) 항상 수행된다. 비교 및 교체 연산이 매번 성공적이라는 것은 단지 필드(415)의 이전값(old value)이 비교 및 교체 호출(invocation)을 위해 시작된 설정 시간이후 변경되지 않았다는 것을 의미한다. 비교 및 교체 연산이 성공적이면, 필드(415)는 갱신된다. 특히, 중요한 것은 연속 번호(430)의 갱신이다. 연속 번호(430)는 항상 갱신되기 때문에, 소정 시간에 두 개의 비교 및 교체 연산은 같은 세마포어에서 충돌하고, 단지 하나의 비교 및 교체 연산만을 완료하고 다른 하나는 다시 설정을 수행하기 위해 되돌아간다.
PLO 인스트럭션의 비교 및 교체 부분에서 주요 세마포아 필드(415)를 갱신하는 것 외에, 인스트럭션은 대기 큐 필드(420)를 또한 수정하기 위해 설정된다. 대기자가 대기 큐(370)로부터 제거되거나 첫 번째 대기자가 대기 큐(370)에 추가되면, 대기 큐 헤드(440)는 갱신된다. 대기자가 대기 큐의 마지막에 추가되거나 첫 번째 대기자가 추가되면, 테일 포인터(445)는 갱신된다. 스레드 제어 블록(450)이 추가되거나 대기 큐(370)로부터 제거될 때면, 플래그(460)와 혹은 NEXT 포인터(455)는 갱신된다. 스레드 제어 블록(450)이 대기 큐(370)에 존재할 때마다, 플래그(460)는 스레드 제어 블록(450)이 대기 큐(370)에 존재하는다는 것을 표시하도록 설정된다. 이러한 모든 필드는 단일 PLO 비교 및 교체 인스트럭션에 의해 수정된다.
도 13은 이하의 설명에서 자주 언급되는 세마포어와 대기 큐 필드를 도시한다. 세마포어 필드(415)는 비교값으로 세마포어 필드의 이전값(previous value)을 저장하기 위해 oldsem(1310)으로 불리우는 영역(area)에 복사된다. 그런 다음 oldsem(1310)는 newsem(1320)으로 복사되고 newsem(1320) 내부의 필드는 세마포어 필드(415)를 위해 대체값을 발생하기 위한 특정 세마포어 연산에 따라 갱신된다. 대기 큐(370)가 상기 연산에 의해 수정되면, 스레드 제어 블록의 NEXT과 플래그 필드를 위한 대체값이 1340으로 마크되는 영역에 형성되는 반면, 대기 큐 헤드(440)와 테일(445)을 위한 대체값은 영역(1330)에 형성된다. 그후 PLO 인스트럭션이 실행되면, PLO 인스트럭션은 세마포어 필드(415)의 현재값을 oldsem(1310)에 저장된 비교값과 비교한다. 어토믹걸하게 비교 단계에서(atomically with the comparing step), 값이 일치하면, 세마포어를 변경하는 다른 스레드가 존재하지 않는다는 것을 표시하고, 그런 다음 PLO 인스트럭션은 대체값(1330)으로 대기 큐 헤드(420)를 갱신하고, 대체값(1340)으로 스레드 제어 블록의 NEXT 및 플래그 필드(470)를 갱신하고, 그런 다음 newsem(1320)으로부터의 대체값으로 실제 세마포어(415)를 갱신한다.
도 6a는 세마포어가 이용 불가능하고(semval=0, 435) 대기 큐(370)(헤드 포인터(440)에 의해 가리켜진 것처럼)가 비어있을 때 semop(-1)용 프로세싱을 도시한다. 비교 및 교체 설정을 위한 테스팅 프로세스 초기에, 세마포어 필드(415)의 현재 값은 oldsem(1310)에 저장되었다. 새로운 대기자가 추가되어도 세마포어 값(435)이나 PID(425)는 변경되지 않는다. 이러한 모든 비교 및 교체 연산으로, 연속 번호(430)의 값이 증가한다. 그래서 연속 번호(430)가 1 이상이라는 것을 제외하고는, oldsem(1310)와 같은 newsem(1320)이라고 불리우는 영역이 생성된다. 대기 큐(370)가 현재 비어있기 때문에, (엔트리(372)로서) 대기 큐(370)에 새로운 스레드 제어 블록(450)을 추가하면, 헤드(440)와 테일(445) 모두는 스레드 제어 블록(450)을 가리키도록 설정된다. 그래서, 이러한 경우에, 두 개의 추가 저장을 갖는 더블 PLO 비교 및 교체가 이루어진다. 상기 추가 저장은 큐 헤더(420)와 스레드 제어 블록 필드(470)를 목표로 한다. 다른 대기자가 존재하지 않기 때문에, 단지 대기 플래그(460)만이 필드(470)에서 수정된다.
도 6b는 비교 및 교체 연산이 성공적일 때 세마포어 필드의 내용을 도시한다. 연속 번호(430)는 이전값보다 1 크다. 현재 큐 헤드(440)는 호출 스레드의 스레드 제어 블록(450)을 가리킨다. 큐 테일(445)은 같은 스레드 제어 블록(450)을 가리킨다. 대기 플래그(460)는 세마포어 대기 상태(chain)에 존재하는 스레드 제어 블록(450)을 표시하도록 설정된다. 비교 및 교체 연산이 실패하면, 세마포어 필드(415 및 420)는 영향을 받지 않는다. 다른 스레드가 세마포어(415)를 해제하거나 또는 다른 스레드가 대기자 큐에 자신을 추가하면 비교 및 교체 연산은 실패한다. 비교 및 교체 연산이 성공적이었는지를 판단하기 위한 검사는 도 5a의 단계(524)에 도시되어 있다.
도 7a는 세마포어가 이용 불가능하고(semval=0) 대기 큐(440)가 비어있지 않을 때 semop(-1)을 위한 프로세싱을 도시한다. 비교 및 교체 설정을 하기 위한 테스팅 프로세스 초기에, 세마포어 필드(415)의 현재 값은 oldsem(1310)에 저장되었다. 새로운 대기자가 추가되어도 세마포어 값(435)이나 PID(425)은 변경되지 않는다. 이러한 모든 비교 및 교체 연산으로, 연속 번호(430)의 값이 증가한다. 그래서 연속번호(430)가 "1" 이상인 것을 제외하면 oldsem(1310)과 같은 newsem(1320)이라고 불리우는 영역이 생성된다. 대기 큐 헤드(440)는 현재 스레드 제어 블록(750)을 가리키고 테일(445)도 스레드 제어 블록(750)을 가리킨다.
대기 큐 헤더(420)에 새로운 스레드 제어 블록(450)을 추가하면, 헤드(440)는 계속 스레드 제어 블록(750)을 가리키고 있고 테일(445)은 스레드 제어 블록(450)을 가리키도록 설정된다. 대기 큐(370)의 마지막에 호출 스레드를 추가하기 때문에, 스레드 제어 블록(750)의 NEXT 포인터(755)는 대기 큐로 추가되는 스레드 제어 블록(450)을 가리키도록 갱신된다. 이러한 경우에, 더블 PLO 비교 및 교체와 세 개의 추가(triple) 저장은 세마포어 필드(415), 큐 헤더(420), 및 스레드 제어 블록 필드(770 및 470)를 목표로 한다.
도 7b는 비교 및 교체 연산이 성공적일 때 세마포어 필드의 내용을 도시한다. 연속 번호(430)는 이전값보다 "1" 크다. 큐 헤드(440)는 여전히 스레드 제어 블록(750)을 가리키고 있다. 큐 테일(445)는 현재 스레드 제어 블록(450)을 가리킨다. 스레드 제어 블록(750)의 NEXT 포인터(755)는 현재 스레드 제어 블록(450)을 가리키고, 스레드 제어 블록(450)의 대기 플래그(460)는 스레드가 대기 큐에서 대기하고 있다는 것을 표시하도록 수정된다. 비교 및 교체 연산이 실패하면, 어떤 필드도 수정되지 않는다. 다른 스레드가 세마포어를 해제하거나 또는 다른 스레드가 대기자로 자신을 추가하면 비교 및 교체 연산은 실패한다. 비교 및 교체 연산이 성공했는지를 판단하기 위한 검사는 도 5a의 단계(524)에 도시되어 있다.
도 8a는 세마포어가 이용가능할 때(semval=1 435), semop(-1)를 위한 프로세싱을 도시한다. 비교 및 교체 설정을 위한 테스팅 프로세스 초기에, 세마포어 필드(415)의 현재 값은 oldsem(1310)에 저장되었다. newsem(1320)이라고 불리우는 영역이 생성되고 newsem(1320)은 oldsem(1310)이 복사되어 초기화된다. 상기 newsem(1320)의 복사에서, PID는 호출자의 프로세스 ID로 설정되고, 연속 번호는 "1"씩 증가되며 세마포어 값은 "1"에서 "0"으로 변경된다. 대기 큐 헤더(420)가 이러한 연산에 영향을 받지 않기 때문에, 대기 큐 헤더(420)의 필드는 수정되지 않는다. 수행된 비교 및 교체 연산은 추가 저장이 없는 단일 비교 더블 및 교체이다.
도 8b는 비교 및 교체 연산이 성공적일 때 세마포어 필드의 내용을 도시한다. 연속 번호(430)가 이전값 보다 "1" 크다. PID 필드(425)는 호출자의 프로세스 ID를 갖는다. 현재 세마포어 값(435)은 "0"으로 세마포어를 보유하고 있다는 것을 표시한다. 대기 큐 헤더(420)는 변경되지 않는다. 비교 및 교체 연산이 실패하면, 수정된 필드는 존재하지 않는다. 비교 및 교체 연산이 실패하는 가장 일반적인 원인은 다른 스레드가 세마포어를 획득하는 것이다. 비교 및 교체 연산이 성공했는지를 판단하기 위한 검사는 도 5b의 단계(542)에 도시되어 있다.
도 9a는 이전에 획득되었던 세마포어를 해제하는 호출자인 semop(-1)를 위한 프로세싱을 도시한다. 이러한 경우에 세마포어를 위한 대기자는 존재하지 않는다. 비교 및 교체 설정을 위한 테스팅 프로세스 초기에, 세마포어 필드(415)의 현재 값은 oldsem(1310)에 저장되었다. newsem(1320)이라고 불리우는 영역이 생성되고 newsem(1320)은 oldsem(1310)이 복사되어 초기화된다. 상기 newsem(1320)의 복사에서, PID는 호출자의 프로세스 ID로 설정되고, 연속 번호는 "1"씩 증가되며 세마포어 값은 "0"에서 "1"로 변경된다. 대기자가 존재하지 않기 때문에, 대기 큐 헤더(420)는 변경되지 않는다. 수행된 비교 및 교체 연산은 추가 저장이 없는 단일 비교 더블 및 교체이다.
도 9b는 비교 및 교체 연산이 성공적일 때 세마포어 필드의 내용을 도시한다. 연속 번호(430)가 이전값 보다 "1" 크다. PID 필드(425)는 호출자의 프로세스 ID를 갖는다. 현재 세마포어 값(435)은 "1"로 세마포어가 이용 가능하다는 것을 표시한다. 대기 큐 헤더(420)는 비어있다. 비교 및 교체 연산이 실패하면, 수정된 필드는 존재하지 않는다. 다른 스레드가 대기 큐에 자신을 추가하는 프로세스를 행하면 이는 비교 및 교체 연산이 실패하는 가장 중요한 원인으로 작용한다. 비교 및 교체 연산이 실패함에 따라, 소정 대기자를 기입하지 않고 세마포어를 해제하여 이러한 프로세스를 방해한다(prevent). 비교 및 교체 연산이 성공했는지를 판단하기 위한 검사는 도 5c의 단계(560)에 도시되어 있다.
도 10a는 이전에 획득되었던 세마포어를 해제하는 호출자인 semop(+1)를 위한 프로세싱을 도시한다. 이러한 경우에 세마포어를 위한 대기자는 존재한다. 비교 및 교체 설정을 위한 테스팅 프로세스 초기에, 세마포어 필드(415)의 현재 값은 oldsem(1310)에 저장되었다. newsem(1320)이라고 불리우는 영역이 생성되고 newsem(1320)은 oldsem(1310)이 복사되어 초기화된다. 상기 newsem(1320)의 복사에서, PID는 호출자의 프로세스 ID로 설정되고, 연속 번호는 "1"씩 증가되며 세마포어 값은 "0"에서 "1"로 변경된다. 대기 큐 헤더(420)는 첫 번째 대기자(750)를 제거하기 위해 수정된다. 단지 하나의 대기자밖에 존재하지 않는다면, 헤드(440)와 테일(445) 모두는 "0"으로 설정된다. 다수개의 대기자가 존재하면, 헤드(440)는 첫 번째 구성요소(750)의 NEXT 포인터(755)와 같은 값을 갖도록 변경되고 테일(445)은 변경되지 않고 이전 상태를 유지한다. NEXT 포인터(755)와 플래그(760)는 스레드 제어 블록(750)이 더 이상 세마포어 대기 큐에 존재하지 않다는 것을 표시하도록 클리어된다. 수행된 비교 및 교체 연산은 더블 비교이고 첫 번째 대기자의 큐 헤드(420)와 스레드 제어 블록 필드(770)속으로 두 개의 추가 저장을 갖는 교체이다.
도 10b는 비교 및 교체 연산이 성공적일 때 세마포어 필드의 내용을 도시한다. 연속 번호(430)는 이전값 보다 "1" 크다. PID 필드(425)는 호출자의 프로세스 ID를 갖는다. 현재 세마포어 값(435)은 "1"로 세마포어가 이용 가능하다는 것을 표시한다. 현재 대기 큐 헤더(420)는 스레드 제어 블록(450)을 가리킨다. NEXT 포인터(755)와 플래그(760)는 클리어되어 있다. 비교 및 교체 연산이 실패하면, 어떠한 필드도 수정되지 않는다. 다른 스레드가 대기 큐에 자신을 추가하는 프로세스를 행하면 이는 비교 및 교체 연산이 실패하는 가장 중요한 원인으로 작용한다. 비교 및 교체 연산이 실패함에 따라, 무효 상태(invalid state)일 때 대기 큐를 벗어나(leaving) 상기 프로세스를 방해한다. 비교 및 교체 연산이 성공했는지를 판단하기 위한 검사는 도 5c의 단계(560)에 도시되어 있다.
도 11a는 대기 큐에 존재하는 맨 위의 스레드를 제거하기 위한 프로세싱을 도시한다. 이러한 것은 세마포어의 해제가 맨 위의 대기자 스레드를 제거할 때 단계(580)(도 5d)에서 일어난다. 그러나 세마포어를 얻기(wake up) 위한 기입에는 실패한다. 이러한 경우에 다음 대기자는 중지 조건(hang condition)을 방해하기 위해 반드시 기입되어야 한다. 비교 및 교체 살장을 위한 테스팅 프로세스 초기에, 세마포어 필드(415)의 현재 값은 oldsem(1310)에 저장된다. newsem(1320)이라고 불리우는 영역이 생성되고 newsem(1320)은 oldsem(1310)이 복사되어 초기화된다. 상기 newsem(1320)의 복사에서, PID와 세마포어 값은 변경되지 않는다. 연속 번호는 "1"씩 증가된다. 대기 큐 헤드(420)는 첫 번째 대기자를 제거하기 위해 수정된다. 하나의 대기자만이 존재하면, 헤드(440)와 테일(445) 모두는 "0"으로 설정된다. 다수의 대기자가 존재하면 헤드(440)는 첫 번째 구성요소(750)의 NEXT 포인터(755)와 같은 값을 갖도록 변경되고 테일(445)은 변경되지 않고 이전 상태를 유지한다. NEXT 포인터(755)와 플래그(760)는 스레드 제어 블록(750)이 더 이상 세마포어 대기 큐에 존재하지 않다는 것을 표시하도록 클리어된다. 수행된 비교 및 교체 연산은 더블 비교이고 큐 헤더(420)와 첫 번째 대기자의 스레드 제어 블록 필드(770)속으로 두 개의 추가 저장을 갖는 교체이다.
도 11b는 비교 및 교체 연산이 성공적일 때 세마포어 필드의 내용을 도시한다. 연속 번호(430)는 이전값 보다 "1" 크다. PID 필드(425)와 세마포어 값(435)은 변경되지 않는다. 현재 대기 큐 헤드(440)는 스레드 제어 블록(450)을 가리키고 테일 포인터(445)는 변경되지 않는다. 마지막 스레드 제어 블록이 대기 큐로부터 제거되면, 헤드(440)의 값은 "0"이고 테일(445) 값 또한 "0"이다. 제거되는 스레드 제어 블록(750)의, NEXT 포인터(755)와 대기 플래그(760)는 클리어된다. 비교 및 교체 연산이 실패하면, 어떠한 필드도 수정되지 않는다. 다른 스레드가 대기 큐에 자신을 추가하는 프로세스를 행하면 이는 비교 및 교체 연산이 실패하는 중요한 원인으로 작용한다. 비교 및 교체 연산이 실패함에 따라, 상기 연산은 무효 상태에서 대기 큐를 벗어나(leaving) 상기 프로세스를 방해한다. 비교 및 교체 연산이 성공했는지를 판단하기 위한 검사는 도 5d의 단계(574)에 도시되어 있다.
도 12a는 스레드가 회복 프로세싱으로 도입할 때 단계(597)(도 5e)에서 세마포어를 대기하고 있는 스레드를 제거하기 위한 프로세싱을 도시한다. 세마포어 필드(415)의 현재 값은 oldsem(1310)에 저장된다. newsem(1320)이라고 불리우는 영역이 생성되고 newsem(1320)은 oldsem(1310)이 복사되어 초기화된다. 상기 newsem(1320)의 복사에서, 호출이 세마포어 값(435)을 수정할 때만 PID가 변경되기 때문에 PID는 변경되지 않는다. 연속 번호는 "1"씩 증가된다. 도 5e의 순서도에서, 제거되는 스레드 제어 블록(450)은 대기 큐에 위치하고 스레드 제어 블록(750)은 현재 NEXT 포인터(755)로 스레드 제어 블록(450)을 가리키고 있다. 비교 및 교체 연산은 대기 큐 헤드(420)로부터 구성요소(450)를 제거한다.
이러한 예에서, 헤드(440)는 변경되지 않고, 요소(450)가 현재 대기 큐의 마지막에 존재하고 상기 요소(450)를 제거하면 테일 포인터(445)를 변경하기 때문에 테일(445)은 구성요소(750)를 가리키기 위해 변경된다. NEXT 포인터(755)는 스레드 제어 블록(450) 내에 있는 NEXT 포인터가 무엇이든지 간에 이를 가리키도록 변경된다. 이러한 경우에, NEXT 포인터(455)의 값은 "0"이다. NEXT 포인터(455)와 대기 플래그(460)는 클리어된다. 수행된 비교 및 교체 연산은 더블 비교이고 대기 큐 필드(420), 스레드 제어 블록 필드(770) 및 스레드 제어 블록 필드(470)속으로 세 개의 추가 저장을 갖는 교체이다.
스레드가 대기 큐(370)에서 첫 번째 대기자도 아니고 마지막 대기자도 아니면, 단지 세마포어 필드(415)와 스레드 제어 블록 필드(770 및 470)만이 갱신되고; 큐 포인터 필드(420)는 동일한 상태를 유지한다. 더블 비교와 세 개의 추가 저장을 갖는 교체가 상기의 경우(scenario)에 이용되면, 큐 포인터 필드(420)는 자신의 이전 내용으로 단순히 갱신된다.
도 12b는 비교 및 교체 연산이 성공적일 때 세마포어 필드의 내용을 도시한다. 연속 번호(430)가 이전값 보다 "1" 크다. PID 필드(425)와 세마포어 값(435)은 변경되지 않는다. 대기 큐 헤드(440)는 스레드 제어 블록(450)을 여전히 가리키고 테일 포인터(445)는 현재 스레드 제어 블록(750)을 가리킨다. 마지막 스레드 제어 블록이 큐로부터 제거되면, 헤드(440)값은 "0"이고 테일(445) 값 또한 "0"이다. NEXT 포인터(755)는 현재 "0"이다. NEXT 포인터(755)와 대기 플래그(460)는 스레드 제어 블록(450)이 더 이상 대기 큐에 존재하지 않다는 것을 표시하기 위해 클리어된다. 비교 및 교체 연산이 실패하면, 어떠한 필드도 수정되지 않는다. 비교 및 교체 연산이 실패함에 따라, 상기 무효 상태일 때 대기 큐를 벗어나(leaving) 상기 프로세스를 방해한다. 비교 및 교체 연산이 성공했는지를 판단하기 위한 검사는 도 5e의 단계(590)에 도시되어 있다.
본 발명은 바람직하게 하드웨어 머신에서 실행하는 소프트웨어(즉, 프로그램 저장 장치에서 유형적으로 구현된 인스트럭션의 머신-판독가능 프로그램)로 수행된다. 특정한 실시예가 보여지고 기재되어 있으나, 해당 분야의 당업자라면 발명의 본질을 벗어나지 않고 다양한 변경을 할 수 있다는 것이 명백할 것이다. 따라서, 본 발명이 IBM S/390 하드웨어 플랫폼에서 PLO 인스트럭션을 사용하는 것으로 기술되어 있지만, 본 발명은 상기 플랫폼의 인스트럭션에 한정되지 않으며, 다른 환경에서도 사용될 수 있다. 더욱이, 본 발명은 이진 세마포어를 실행하는 것으로서 기술되어 있지만, 본 발명은 상기 이진 세마포어에 한정되지 않으며, 카운팅 세마포어에 적합하게 변경시켜도 사용할 수 있다.
이와 같이 동작하는 본 발명의 효과는 연산 실행 시간은 단축시키고, 별도의 락을 추가할 필요가 없으므로, 컴퓨터 성능을 향상시키고 처리 용량을 증대할 수 있다.

Claims (20)

  1. 공유 자원으로의 액세스를 직렬화하기 위해 세마포어가 사용되는 정보 처리 시스템에서, 세마포어는 소정 값을 포함하는 제1 세마포어 필드 및 상기 세마포어를 위한 큐에 대한 포인터를 포함하는 제2 세마포어 필드를 포함하고, 상기 큐는 상기 세마포어의 대기자에 대응하는 0 이상의 엔트리를 가지며, 각 엔트리는 다음 엔트리 및 다음 엔트리에 대한 포인터를 가지고, 상기 세마포어에 관한 특정 연산을 수행하기 위해 요구자로부터의 요구를 처리하는 방법에 있어서,
    a) 제1 세마포어 필드의 이전값을 비교값으로 저장하는 단계;
    b) 상기 특정 연산에 따라서, 제1 오퍼랜드로 제1 세마포어 필드에 대한 제1 대체값을 발생하고, 큐가 연산에 의해 수정되면 제2 오퍼랜드로 제2 세마포어 필드에 대한 제2 대체값을 발생하며 제3 오퍼랜드로서 큐 엔트리 중 하나에 대한 제3 대체값을 발생하는 단계; 및
    c) 그 후에 제1 세마포어 필드의 현재값을 상기 비교값과 오토믹 연산으로(atomically) 비교하고, 현재 값이 비교값과 일치하면, 제1 대체값으로 제1 오퍼랜드를 대체하고, 큐가 상기 연산에 의해 수정되면, 제2 및 제3 오퍼랜드 중 하나 또는 모두를 제2 및 제3 오퍼랜드의 대응 대체값으로 대체하는 단계
    로 포함하는 요구 처리 방법.
  2. 제1항에 있어서,
    상기 세마포어를 갱신하기 위해 상기 세마포어 필드가 마지막 요구자의 식별자(identifier)를 포함하는 요구 처리 방법.
  3. 제1항에 있어서,
    상기 세마포어 필드가 연속 번호(sequence number)를 포함하는 요구 처리 방법.
  4. 제3항에 있어서,
    상기 c)의 비교 단계가
    상기 제1 세마포어 필드의 현재값의 연속 번호를 상기 비교값의 연속 번호와 비교하는 단계
    를 포함하는 요구 처리 방법.
  5. 제3항에 있어서, 상기 b)의 발생 단계가
    증가된 연속 번호를 발생시키기 위해 상기 제1 세마포어 필드의 이전값에 포함된 연속 번호를 증가하는 단계; 및
    상기 증가된 연속 번호를 포함하는 제1 대체값을 발생하는 단계
    를 포함하는 요구 처리 방법.
  6. 제1항에 있어서,
    상기 세마포어는 두 개의 세마포어 값 중 하나를 갖는 이진 세마포어인 요구 처리 방법.
  7. 제1항에 있어서,
    상기 특정 연산은 상기 세마포어 값을 감소하는 연산을 포함하는 요구 처리 방법.
  8. 제1항에 있어서,
    상기 특정 연산은 상기 세마포어 값을 증가하는 연산을 포함하는 요구 처리 방법.
  9. 제1항에 있어서,
    상기 제2 세마포어 필드는 상기 세마포어의 제1 대기자에 대한 포인터를 포함하는 요구 처리 방법.
  10. 제1항에 있어서,
    상기 제2 세마포어 필드는 상기 세마포어의 마지막 대기자에 대한 포인터를 포함하는 요구 처리 방법.
  11. 제1항에 있어서,
    상기 요구가 세마포어를 구하는 요구일 경우, 상기 b)의 대체값 발생 단계가,
    i) 상기 세마포어가 이용 가능하지를 판정하기 위해 상기 세마포어 값을 검사하는 단계;
    ii) 상기 세마포어 값이 세마포어가 이용 가능하다는 것을 표시하면, 제1 대체값을 발생하기 위해 세마포어 값을 감소하는 단계;
    iii) 상기 세마포어 값이 세마포어가 이용 불가능하다는 것을 표시하면, 세마포어의 대기자가 존재하는지를 판정하는 단계;
    iv) 상기 세마포어의 대기자가 존재하지 않으면, 제2 대체값을 발생하기 위해 큐 포인터가 제2 대기자를 새로운 제1 대기자로 가리키도록 상기 큐 포인터를 수정하는 단계; 및
    v) 상기 세마포어의 대기자가 하나 이상 존재하면, 제3 대체값을 발생하기 위해 요구자가 새로운 마지막 대기자를 가리키도록 현재 마지막 대기자의 큐 엔트리를 수정하는 단계
    를 포함하는 요구 처리 방법.
  12. 제1항에 있어서, 상기 요구가 세마포어를 가지고 있는 요구자로부터 세마포어를 해제하기 위한 요구일 경우, 상기 b)의 대체값 발생 단계는,
    i) 제1 대체값을 발생하기 위해 세마포어 값을 증가하는 단계;
    ii) 세마포어의 제1 및 제2 대기자가 존재하는지를 판정하는 단계;
    iii) 세마포어의 제1 및 제2 대기자가 존재하면, 제2 대체값을 발생하기 위해 큐 포인터가 제2 대기자를 새로운 제1 대기자를 가리키도록 상기 큐 포인터를 수정하고 제3 대체값을 발생하기 위해 큐로부터 제1 대기자를 제거하도록 제1 대기자에 대응하는 큐 엔트리를 수정하는 단계; 및
    iv) 세마포어의 제1 대기자만이 존재하면, 제2 대체값을 발생하기 위해 대기자가 존재하지 않는다는 것(absence)을 표시하도록 큐 포인터를 수정하고 제3 대체값을 발생하기 위해 큐로부터 제1 대기자를 제거하도록 제1 대기자에 대응하는 큐 엔트리를 수정하는 단계
    를 포함하는 요구 처리 방법.
  13. 제1항에 있어서,
    제1 세마포어 필드의 현재 값이 비교값과 일치하지 않으면, 새로운 비교값으로 제1 세마포어 필드의 현재값을 저장하고 상기 b)의 발생 단계와 상기 c)의 비교 및 대체 단계를 반복하는 단계
    를 추가로 포함하는 요구 처리 방법.
  14. 제1항에 있어서,
    상기 c)의 비교 및 대체 단계는 오퍼랜드를 비교값과 비교하는 단일 하드웨어 인스트럭션을 사용하여 수행되고, 상기 오퍼랜드가 비교값과 같으면, 비교된 오퍼랜드 및 선택적으로 추가된 오퍼랜드를 대체값으로 대체하는 요구 처리 방법.
  15. 제1항에 있어서,
    각각의 큐 엔트리는 대응하는 요구자를 위한 제어 블록을 포함하는 요구 처리 방법.
  16. 제15항에 있어서,
    상기 각 제어 블록은 큐의 다음 엔트리에 대한 포인터를 포함하는 요구 처리 방법.
  17. 제15항에 있어서,
    상기 각 제어 블록은 요구자가 큐에서 대기하고 있는지를 표시하는 플래그를 포함하는 요구 처리 방법.
  18. 제1항에 있어서,
    상기 b)의 발생 단계는 한 쌍의 큐 엔트리에 대한 대체값을 발생하는 단계를 추가로 포함하고
    상기 c)의 대체 단계는 한쌍의 큐 엔트리를 대응하는 대체값으로 대체하는 단계를 포함하는 요구 처리 방법
  19. 공유 자원으로의 액세스를 직렬화하기 위해 세마포어가 사용되는 정보 처리 시스템에서, 세마포어는 소정 값을 포함하는 제1 세마포어 필드 및 상기 세마포어를 위한 큐에 대한 포인터를 포함하는 제2 세마포어 필드를 포함하고, 상기 큐는 상기 세마포어의 대기자에 대응하는 0 이상의 엔트리를 가지며, 각 엔트리는 다음 엔트리 및 다음 엔트리에 대한 포인터를 가지고, 상기 세마포어에 관한 특정 연산을 수행하기 위해 요구자로부터의 요구를 처리하는 장치에 있어서,
    a) 제1 세마포어 필드의 이전값을 비교값으로 저장하는 수단;
    b) 특정 연산에 따라서, 제1 오퍼랜드로 제1 세마포어 필드에 대한 제1 대체값을 발생하고, 큐가 연산에 의해 수정되면 제2 오퍼랜드로 제2 세마포어 필드에 대한 제2 교체값을 발생하며 제3 오퍼랜드로 큐 엔트리 중 하나에 대한 제3 교체값을 발생하는 수단; 및
    c) 제1 세마포어 필드의 현재값을 상기 비교값과 어토믹 연산으로 비교하고, 현재 값이 비교값과 일치하면, 제1 오퍼랜드를 제1 대체값으로 대체하고, 큐가 상기 연산에 의해 수정되면, 제2 및 제3 오퍼랜드 중 하나 또는 모두를 제2 및 제3 오퍼랜드의 대응 대체값으로 대체하는 수단
    을 포함하는 요구 처리 장치.
  20. 공유 자원으로의 액세스를 직렬화하기 위해 세마포어가 사용되는 정보 처리 시스템에서, 세마포어에 관한 특정 연산을 수행하기 위해 요구자로부터 요구를 처리하는 방법의 단계를 수행하도록 머신에 의해 실행될 수 있는 인스트럭션 프로그램을 유형적으로 구현하며, 머신에 의해 판독 가능한 프로그램 저장 장치에 있어서,
    상기 세마포어는 소정 값을 포함하는 제1 세마포어 필드 및 상기 세마포어를 위한 큐에 대한 포인터를 포함하는 제2 세마포어 필드를 포함하고, 상기 큐는 상기 세마포어의 대기자에 대응하는 0 이상의 엔트리를 가지며, 각 엔트리는 다음 엔트리 및 다음 엔트리에 대한 포인터를 가지고,
    상기 요구처리 방법은
    a) 제1 세마포어 필드의 이전값을 비교값으로 저장하는 단계;
    b) 상기 특정 연산에 따라서, 제1 오퍼랜드로 제1 세마포어 필드에 대한 제1 대체값을 발생하고, 큐가 연산에 의해 수정되면 제2 오퍼랜드로 제2 세마포어 필드에 대한 제2 대체값을 발생하며 제3 오퍼랜드로서 큐 엔트리 중 하나에 대한 제3 대체값을 발생하는 단계; 및
    c) 그 후에 제1 세마포어 필드의 현재값을 상기 비교값과 어토믹 연산으로 비교하고, 현재 값이 비교값과 일치하면, 제1 오퍼랜드를 제1 대체값으로 대체하고, 큐가 상기 연산에 의해 수정되면, 제2 및 제3 오퍼랜드 중 하나 또는 모두를 제2 및 제3 오퍼랜드의 대응 대체값으로 대체하는 단계
    를 포함하는 프로그램 저장 장치.
KR1019990006340A 1998-03-18 1999-02-25 세마포어연산을수행하기위한방법및장치 Ceased KR19990077481A (ko)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US9/040722 1998-03-18
US09/040,722 US6237019B1 (en) 1998-03-18 1998-03-18 Method and apparatus for performing a semaphore operation

Publications (1)

Publication Number Publication Date
KR19990077481A true KR19990077481A (ko) 1999-10-25

Family

ID=21912574

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1019990006340A Ceased KR19990077481A (ko) 1998-03-18 1999-02-25 세마포어연산을수행하기위한방법및장치

Country Status (4)

Country Link
US (1) US6237019B1 (ko)
EP (1) EP0943993A3 (ko)
JP (1) JPH11327931A (ko)
KR (1) KR19990077481A (ko)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100803450B1 (ko) * 2002-11-19 2008-02-14 엘지노텔 주식회사 공유 버스 시스템의 스케줄링 장치 및 그 방법

Families Citing this family (52)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6701429B1 (en) * 1998-12-03 2004-03-02 Telefonaktiebolaget Lm Ericsson(Publ) System and method of start-up in efficient way for multi-processor systems based on returned identification information read from pre-determined memory location
US6560627B1 (en) * 1999-01-28 2003-05-06 Cisco Technology, Inc. Mutual exclusion at the record level with priority inheritance for embedded systems using one semaphore
US7334229B1 (en) 1999-01-28 2008-02-19 Cisco Technology, Inc. Mutual exclusion at the record level with priority inheritance for embedded systems using one semaphore
US6874144B1 (en) * 1999-04-05 2005-03-29 International Business Machines Corporation System, method, and program for implementing priority inheritance in an operating system
US6920633B1 (en) * 2000-01-14 2005-07-19 Microsoft Corporation Cross-process common system resource data sharing
US6615286B1 (en) * 2000-02-14 2003-09-02 Intel Corporation Method and apparatus for updating device driver control data
US6745274B1 (en) * 2000-04-25 2004-06-01 Hewlett-Packard Development Company, L.P. Apparatus and method for synchronizing multiple accesses to common resources
US6609161B1 (en) 2000-06-01 2003-08-19 Adaptec, Inc. Two-dimensional execution queue for host adapters
US6789134B1 (en) 2000-06-01 2004-09-07 Adaptec, Inc. Dequeuing from a host adapter two-dimensional queue
EP1199632A1 (en) 2000-10-20 2002-04-24 Sun Microsystems, Inc. Method and apparatus for resource access synchronization
US7353515B1 (en) 2001-02-04 2008-04-01 Cisco Technology, Inc. Method and apparatus for dynamic allocation and management of semaphores for accessing shared resources
US7237013B2 (en) * 2001-04-16 2007-06-26 National Instruments Corporation Network system including data socket components for accessing internet semaphores
AU2002356884B2 (en) * 2001-11-01 2008-12-04 Verisign, Inc. Transactional memory manager
US7065765B2 (en) * 2001-12-05 2006-06-20 International Business Machines Corporation Serializing event handling in a threaded system with no wait states
US7174552B2 (en) * 2002-01-12 2007-02-06 Intel Corporation Method of accessing a resource by a process based on a semaphore of another process
FI20020210L (fi) * 2002-02-04 2003-08-05 Nokia Corp Moniprosessoriympäristöön tarkoitettu laitteistopohjainen opastin
US6978330B1 (en) * 2002-04-04 2005-12-20 Applied Micro Circuits Corporation Shared resource access via declarations that contain a sequence number of a packet
US7421693B1 (en) 2002-04-04 2008-09-02 Applied Micro Circuits Corporation Logic for synchronizing multiple tasks at multiple locations in an instruction stream
US6938132B1 (en) 2002-04-04 2005-08-30 Applied Micro Circuits Corporation Memory co-processor for a multi-tasking system
US7036125B2 (en) * 2002-08-13 2006-04-25 International Business Machines Corporation Eliminating memory corruption when performing tree functions on multiple threads
US6938054B2 (en) * 2002-11-25 2005-08-30 International Business Machines Corporation Systems, methods, and computer program products to optimize serialization when porting code to IBM S/390 UNIX system services from a UNIX system
US7092973B2 (en) 2002-12-23 2006-08-15 Sap Aktiengesellschaft Conflict detection in a distributed system landscape
US7047337B2 (en) * 2003-04-24 2006-05-16 International Business Machines Corporation Concurrent access of shared resources utilizing tracking of request reception and completion order
US7739252B2 (en) * 2003-07-14 2010-06-15 Oracle America, Inc. Read/write lock transaction manager freezing
US7512950B1 (en) * 2003-08-14 2009-03-31 Sun Microsystems, Inc. Barrier synchronization object for multi-threaded applications
US7500242B2 (en) * 2003-09-08 2009-03-03 Intel Corporation Low-contention lock
US7493618B2 (en) * 2003-09-19 2009-02-17 International Business Machines Corporation Fault tolerant mutual exclusion locks for shared memory systems
US7395527B2 (en) 2003-09-30 2008-07-01 International Business Machines Corporation Method and apparatus for counting instruction execution and data accesses
US8381037B2 (en) 2003-10-09 2013-02-19 International Business Machines Corporation Method and system for autonomic execution path selection in an application
US7458078B2 (en) * 2003-11-06 2008-11-25 International Business Machines Corporation Apparatus and method for autonomic hardware assisted thread stack tracking
US7415705B2 (en) 2004-01-14 2008-08-19 International Business Machines Corporation Autonomic method and apparatus for hardware assist for patching code
US7895382B2 (en) 2004-01-14 2011-02-22 International Business Machines Corporation Method and apparatus for qualifying collection of performance monitoring events by types of interrupt when interrupt occurs
US7366727B2 (en) 2004-03-12 2008-04-29 Sap Aktiengesellschaft Management of inbound conflicts when merging data of distributed systems
EP1574955B1 (en) * 2004-03-12 2012-10-24 Sap Ag Management of inbound conflicts when merging data of distributed systems
US7770172B2 (en) * 2004-09-01 2010-08-03 Microsoft Corporation Conditional variables without spinlocks
GB2427045B (en) 2005-06-06 2007-11-21 Transitive Ltd Method and apparatus for converting program code with access coordination for a shared resource
US7730491B2 (en) 2005-08-30 2010-06-01 Intel Corporation Fair scalable reader-writer mutual exclusion
JP2007179190A (ja) * 2005-12-27 2007-07-12 Mitsubishi Electric Corp セマフォ管理方法、およびセマフォ管理プログラム
US8099538B2 (en) * 2006-03-29 2012-01-17 Intel Corporation Increasing functionality of a reader-writer lock
US7624237B2 (en) * 2006-05-03 2009-11-24 International Business Machines Corporation Compare, swap and store facility with no external serialization
GB2437760A (en) * 2006-05-03 2007-11-07 Ibm Computer program for compare, swap and store facility with no external serialization
JP5227604B2 (ja) * 2008-02-14 2013-07-03 株式会社日立製作所 情報処理システム、ファイルの排他制御方法、及び排他制御プログラム
US8429144B2 (en) * 2010-07-16 2013-04-23 International Business Machines Corporation Interprocess communication using a single semaphore
US8392627B2 (en) * 2011-04-25 2013-03-05 Microsoft Corporation Adaptive semaphore
US9141438B2 (en) 2011-06-30 2015-09-22 Net Navigation Systems, Llc Logic for synchronizing multiple tasks
US10185564B2 (en) * 2016-04-28 2019-01-22 Oracle International Corporation Method for managing software threads dependent on condition variables
US20200401412A1 (en) * 2019-06-24 2020-12-24 Intel Corporation Hardware support for dual-memory atomic operations
US11294737B2 (en) * 2019-06-24 2022-04-05 International Business Machines Corporation Self-managed lock access
US11734070B2 (en) * 2019-11-19 2023-08-22 Verizon Patent And Licensing Inc. Systems and methods for providing a compare and swap platform for sequence number generation in a cloud computing environment
US12619477B2 (en) 2021-12-13 2026-05-05 Nvidia Corporation Application programming interface to cause graph code to wait on a semaphore
US20230185634A1 (en) * 2021-12-13 2023-06-15 Nvidia Corporation Application programming interface to cause graph code to update a semaphore
CN114661481B (zh) * 2022-05-25 2022-09-06 广州市保伦电子有限公司 一种单进程中多线程多互斥量间的控制方法以及终端

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2253418A5 (ko) * 1973-11-30 1975-06-27 Honeywell Bull Soc Ind
FR2253423A5 (ko) * 1973-11-30 1975-06-27 Honeywell Bull Soc Ind
JPH02300939A (ja) * 1989-05-16 1990-12-13 Toshiba Corp セマフォオペレーション方式
US5313638A (en) * 1992-03-24 1994-05-17 International Business Machines Corp. Method using semaphores for synchronizing communication between programs or processes resident in a computer system
US5922057A (en) * 1997-01-10 1999-07-13 Lsi Logic Corporation Method for multiprocessor system of controlling a dynamically expandable shared queue in which ownership of a queue entry by a processor is indicated by a semaphore

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100803450B1 (ko) * 2002-11-19 2008-02-14 엘지노텔 주식회사 공유 버스 시스템의 스케줄링 장치 및 그 방법

Also Published As

Publication number Publication date
JPH11327931A (ja) 1999-11-30
EP0943993A3 (en) 2004-04-07
EP0943993A2 (en) 1999-09-22
US6237019B1 (en) 2001-05-22

Similar Documents

Publication Publication Date Title
US6237019B1 (en) Method and apparatus for performing a semaphore operation
US10180903B2 (en) Hybrid hardware and software implementation of transactional memory access
JP2500101B2 (ja) 共用変数の値を更新する方法
US7395383B2 (en) Realtime-safe read copy update with per-processor read/write locks
JP4764430B2 (ja) マルチプロセッサ環境におけるトランザクションベースの共有データオペレーション
Fernandes et al. Lock-free and scalable multi-version software transactional memory
US7206903B1 (en) Method and apparatus for releasing memory locations during transactional execution
US7653910B2 (en) Apparatus for thread-safe handlers for checkpoints and restarts
RU2501071C2 (ru) Механизм запроса поздней блокировки для пропуска аппаратной блокировки (hle)
US7571288B2 (en) Scalable rundown protection for object lifetime management
EP0887730B1 (en) Method for providing exclusive access to a resource in a multiprocessor computer system
US20030037223A1 (en) Apparatus and method for ownership load locked misses for atomic lock acquisition in a multiprocessor computer system
JPH0465414B2 (ko)
EP0549140A2 (en) Record updating method
US7747996B1 (en) Method of mixed lock-free and locking synchronization

Legal Events

Date Code Title Description
PA0109 Patent application

Patent event code: PA01091R01D

Comment text: Patent Application

Patent event date: 19990225

A201 Request for examination
PA0201 Request for examination

Patent event code: PA02012R01D

Patent event date: 19990910

Comment text: Request for Examination of Application

Patent event code: PA02011R01I

Patent event date: 19990225

Comment text: Patent Application

PG1501 Laying open of application
E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 20010621

Patent event code: PE09021S01D

E601 Decision to refuse application
PE0601 Decision on rejection of patent

Patent event date: 20011009

Comment text: Decision to Refuse Application

Patent event code: PE06012S01D

Patent event date: 20010621

Comment text: Notification of reason for refusal

Patent event code: PE06011S01I