IT/모바일
제공: 한빛미디어 네트워크 기사
원문 : http://www.onjava.com/pub/a/onjava/2006/04/05/ajax-mutual-exclusion.html
저자 : Bruce Wallace, 한동훈 역
브라우저 페이지의 뒷단에서 서버 데이터를 요청하는 동안, 앞단에서는 사용자 인터페이스를 계속해서 사용할 수 있게 해주는 에이잭스(AJAX)가 나날이 인기를 얻고 있다. 그러나, 이 두가지 동작은 자바스크립트와 DOM 데이터 구조를 동시에 사용해야 한다. 병행 프로그래밍(Concurrent Programming)에 대한 고적전인 해결책 조차 자바스크립트는 지원하지 않는다. 여기서는, 자바스크립트의 제한을 해결하기 위해, 이미 증명된 상호배제(Mutual Exclusion)를 사용하는 것에 대해 살펴볼 것이다.
왜 상호 배제인가?
같은 데이터에 접근하는 멀티 스레드 프로그램 로직이 동시에 실행되면 문제가 발생한다. 일반적으로 프로그램은 사용하고 있는 데이터가 바뀌지 않는다고 가정한다. 이들 공유 데이터에 접근하는 코드 영역을 임계영역(Critical Sections)이라 하며, 한 번에 하나의 스레드만 프로그램을 실행하게 하는 것을 상호 배제(Mutual Exclusion)라고 한다. AJAX 응용프로그램에서는 사용자 인터페이스 코드에서 사용하는 데이터를 조작하기 위해 XMLHttpRequest에서 가져온 응답을 비동기적으로 처리하는 코드에서 이런 동기화 문제가 발생한다. 공용으로 접근하는 데이터는 웹 페이지 자체의 DOM이나 MVC 모델 등을 사용해서 구현한 자바스크립트 변수일 것이며, 이 두가지 중에 어느 한쪽이 공유 데이터에 대해 변경을 하면, 각각의 로직은 동작하지 않게 될 것이다.
"잠깐만요, 왜 이 문제를 내가 다뤄야하죠?" 라고 얘기할지도 모른다. 불행히도, 이런 종류의 문제는 시간 종속적(timing dependent)인 문제이기 때문에(경쟁조건(Race Condition), 항상 발생하는 것은 아니다. 동기화 문제는 수 많은 요소들에 의해 발생하는 개연적인 문제다. AJAX 응용프로그램을 견고하게 만들기 위해서는 다양한 사용자 인터페이스를 제공하는 인터넷 응용프로그램에서 이런 문제가 발생하지 않도록 보장하는 방법을 통해 이런 상황이 발생하지 않게 하면 된다.
상호 배제는 오직 한 스레드만 임계 영역을 시작하고, 종료한 후에 다른 스레드가 시작할 수 있게 하는 방법이다. 주요 컴퓨터 언어나 프레임워크에서는 상호 배제를 제공하고 있으나, 브라우저에서 사용하는 자바스크립트는 상호 배제를 제공하지 않는다. 언어나 환경의 특별한 지원 없이 상호 배제를 구현하는 고전적인 방법들이 있지만, 이런 방법들은 인터넷 익스플로러 같은 브라우저와 자바스크립트에서 제공하지 않는 몇 가지를 이용하고 있기 때문에 사용할 수 없다. 다음에 소개할 고전적인 알고리즘은 브라우저와 자바스크립트 제한을 해결하기 위해 변형한 것이다.
빵집 알고리즘(Bakery Algorithm)
컴퓨터 과학 분야에는 상호 배제 알고리즘이 몇 가지 있는데, 그 중에서 하나가 램포트의 빵집 알고리즘(Lamport"s Bakery Algorithm)이다. 이 알고리즘은 프로세스 사이의 커뮤니케이션에 공유 메모리만 사용할 때, 경쟁하는 멀티 스레드를 제어하기 위한 방법이다.(즉, 이 방법은 세마포어, 최소단위 TAS(Test-and-Set)과 같은 특별한 방법에 의존하지 않는다) 알고리즘의 뼈대는 위키백과사전에서 가져왔으며, 목록 1과 같다. 이 알고리즘은 각 스레드가 충돌없이 임계 영역에 진입하고, 빠져나올 수 있다.
(역주1: 베이커리 알고리즘(Bakery Algorithm)은 빵집에 사람이 너무 붐벼서 빵을 아무도 사지 못할 때, 번호표를 받고, 빵을 사기위해 기다리는 사람들을 프로세스에 비유해서 만든 알고리즘이다. 따라서, 빵집 알고리즘으로 옮겼다.)
(역주2: 동기화 문제에서 반드시 실행될 것을 보장하는 연산의 최소 단위를 "최소 단위 연산(Atomic Operation)"이라 하며, 대부분의 번역서는 "원자적인 실행" 정도로 옮기고 있다.)
(역주3: Atomic Set-And-Test 알고리즘은 SAT 알고리즘이라 부르기도 하며, 일부 책은 Atomic Test-And-Set 알고리즘 또는 TAS(태스) 알고리즘이라 부른다.)
목록1. 램포트의 빵집 알고리즘(의사코드)
위에서 보인 것처럼, 알고리즘은 각 스레드가 자신의 스레드 번호(상수 i)와 모두 몇 개의 스레드가 현재 동작중인지(상수 N) 알고 있다고 가정한다. 또한, 대기(wait or sleep)할 수 있는 방법이 있다고 가정한다. 예를 들어, CPU 제어권을 포기하고 다른 스레드에게 제어권을 넘길 수 있는 방법이 있다고 가정한다. 불행히도, 인터넷 익스플로러의 자바스크립트는 이런 기능을 갖고 있지 않다. 그러나, 실제로 스레드 하나에서 실행되는 코드의 여러 부분들을 각각의 개별적인 가상 스레드로 동작하는 것처럼 할 수 있으면 빵집 알고리즘을 사용할 수 있다. 또한, 자바 스크립트는 지정된 시간 만큼 지연 시킨 후에 함수를 실행시킬 수 있는 방법을 제공한다. 따라서, 이들 대안을 사용해서 구현할 수 있는 알고리즘이 빵집 알고리즘이다.
월러스 변형(Wallace Variation)
자바스크립트에서 램포트의 빵집 알고리즘을 구현하는 데 있어 가장 큰 문제는 스레드 API가 없다는 점이다. 자바스크립트에서는 어떤 스레드가 실행중인지, 얼마나 많은 스레드들이 동작(active)중인지 알 수 있는 방법이 없으며, 다른 스레드에게 CPU를 양보할 수 있는 방법도 없으며, 다른 스레드를 관리하기 위해 새로운 스레드를 생성할 방법도 없다는 점이다. 이런 점들 때문에, 어떤 브라우저 이벤트가 스레드에 할당되었는지 검사할 수 없다.
역주: 월러스 변형은 자신의 이름을 따서 붙인 이름이다
이런 문제들을 해결하기 위한 방법으로 명령 디자인 패턴(Command Design Pattern)을 응용하는 것이다. 로직을 초기화하는 데 필요한 모든 데이터, 임계 영역에 진입하는 모든 로직에 command 객체를 삽입하는 방법을 사용해서 명령들을 관리하는 클래스 안에 빵집 알고리즘을 동작하게 할 수 있다. 상호 배제 클래스는 다른 임계 영역들이 실행되지 않을 때만 임계 영역에 진입하는 코드를, 마치 각각이 고유의 가상 스레인 것처럼, 호출할 수 있다.(각 임계 영역은 command 객체 메서드로 캡슐화되어 있다) 자바스크립트의 setTimeout()은 다른 대기중인 명령들에 CPU를 양보하기 위해 사용된다.
command 객체를 위해 다음과 같은 간단한 기본 클래스를 사용한다. 클래스는 빵집 알고리즘의 월러스 변형을 구현하기 위해 정의한 것이다(목록3에 Mutex) 자바스크립트에서 클래스 기반 객체를 구현하는 다양한 방법들이 있지만, 어떤 객체 스킴도 고유한 ID를 가지며, 전체 임계 영역은 하나의 메서드로 캡슐화할 수 있는 한 여기서 설명하는 방법이 동작할 것이다.
1 function Command() {
2 if (!Command.NextID) Command.NextID = 0;
3 this.id = ++Command.NextID;
4 // unsynchronized API
5 this.doit = function(){ alert("DOIT called"); }
6 this.undo = function(){ alert("UNDO called"); }
7 this.redo = function(){ this.doit(); }
8 // synchronized API
9 this.sDoIt = function(){ new Mutex(this,"doit"); }
10 this.sUnDo = function(){ new Mutex(this,"undo"); }
11 this.sReDo = function(){ new Mutex(this,"redo"); }
12 }
목록2. Command 객체에 사용한 간단한 기본 클래스
Command 클래스는 임계 영역 메서드를 흉내내기 위한 함수 세 개(5-7번째 줄)가 있으며, 호출을 Mutex 객체로 감출 수 있는 한 어떤 메서드도 정의할 수 있다(9-11번째 줄) 이게 일반 메서드 호출(비동기 메서드를 호출하는 것 같은)과 동기 메서드 호출과의 핵심적인 차이점이다. 모순되지만, 동기화 메서들은 동기적으로 실행하지 않는다고 가정한다. 다시 말해서, sDoIt()이 호출되면 sDoIt()이 반환되더라도 doit()이 아직 실행되지 않았다고 가정해야 한다. 미래의 어떤 시점에서 doit() 메서드의 실행이 끝났거나, doit() 메서드가 시작되지 않았다고 가정해야 한다. 다른 말로 하자면, Mutex 인스턴스화는 새로운 스레드를 시작하는 것처럼 생각해야 한다는 것이다.
1 function Mutex( cmdObject, methodName ) {
2 // define static field and method
3 if (!Mutex.Wait) Mutex.Wait = new Map();
4 Mutex.SLICE = function( cmdID, startID ) {
5 Mutex.Wait.get(cmdID).attempt( Mutex.Wait.get(startID) );
6 }
7 // define instance method
8 this.attempt = function( start ) {
9 for (var j=start; j; j=Mutex.Wait.next(j.c.id)) {
10 if (j.enter
11 || (j.number && (j.number mmlt; this.number ||
12 (j.number == this.number
13 && j.c.id mmlt; this.c.id))))
14 return setTimeout
15 ("Mutex.SLICE("+this.c.id+","+j.c.id+")",10);
16 }
17 //run with exclusive access
18 this.c[ this.methodID ]();
19 //release exclusive access
20 this.number = 0;
21 Mutex.Wait.remove( this.c.id );
22 }
23 // constructor logic
24 this.c = cmdObject;
25 this.methodID = methodName;
26 //(enter and number are "false" here)
27 Mutex.Wait.add( this.c.id, this );
28 this.enter = true;
29 this.number = (new Date()).getTime();
30 this.enter = false;
31 this.attempt( Mutex.Wait.first() );
32 }
목록3. Mutex 클래스로 구현한 월러스 변형 알고리즘
Mutex 클래스의 기본 로직은 각각의 새로운 Mutex 인스턴스를 마스터 대기 목록에 넣고, 시작할 때 까지 인스턴스들이 줄을 서서 기다리는 것이다. "줄의 앞자리"를 얻으려는 각각의 시도 후에는 대기를 해야하며, setTimeout은 각각의 새로운 시도들을 스케줄하기 위해 사용된다. "앞 자리(the head)"에 도착하면(17번째 줄), 상호 배제가 성립한다. 따라서, 임계 영역 메서드가 호출될 수 있다. 임계 영역이 끝나면 베타적인 접근을 해제(release)하고, Mutex 인스턴스는 대기 목록에서 제거된다(20-21번째 줄).
Mutex 생성자(23-31번째 줄)는 Command 객체와 메서드 이름 매개변수들을 기록하고, 목록4에서 Map 클래스로 구현한 희소 배열(Sparse Array)에 스스로를 등록한다. "다음 번호"를 얻은 후에, 줄의 끝에서 대기를 시작한다. 대기자 번호는 연속된 번호이고, 같은 번호는 없기 때문에, 현재 시간(timestamp)를 "다음" 번호로 사용한다.
attemp() 메서드는 원본 의사 코드에서 두 개였던 대기 루프를 줄의 앞자리에 올 때 까지 임계 영역에 도달하지 않는 단일 루프로 결합한다. 이 루프는 바쁜 대기 투표(Busy-wait polling)의 형태로, setTimeout() 호출에서 지정된 시간만큼 대기한다. setTimeout은 객체 메서드가 아니므로 "일반 함수(flat function)"이어야 한다. 따라서, 정적 메서드 Mutex.SLICE를 4-6번째 줄에 정의했다. SLICE는 지정된 Mutex 객체를 마스터 대기 목록에 추가하고, 대기자 목록에서 얼마나 멀리 떨어져 있는지 지정하는 시작 매개변수와 함께 attempt() 메서드를 호출한다. 각 SLICE() 호출은 "CPU의 슬라이스"를 얻는 것과 같다. CPU 제어권을 반환하는 협동형 접근방법(Cooperative Approach)는 코루틴(Coroutine)을 생각나게 한다.
function Map() {
this.map = new Object();
// Map API
this.add = function( k,o ){
this.map[k] = o;
}
this.remove = function( k ){
delete this.map[k];
}
this.get = function( k ){
return k==null ? null : this.map[k];
}
this.first = function(){
return this.get( this.nextKey() );
}
this.next = function( k ){
return this.get( this.nextKey(k) );
}
this.nextKey = function( k ){
for (i in this.map) {
if ( !k ) return i;
if (k==i) k=null; /*tricky*/
}
return null;
}
}
목록4. Map 자료구조로 구현한 희소 배열(Sparse Array)
리치 인터넷 응용프로그램 통합
Mutex는 동적으로 변하는 스레드(가상 또는 실제 스레드)들을 다루며, 브라우저는 각 브라우저 이벤트에 각각의 스레드를 할당하는 식으로 동작한다면 실제 스레드 ID를 알 수 없다는 사실을 이용할 수 있다. 이와 유사하게 단순화시키는 가정은 각 완료 이벤트 핸들러가 복잡한 임계 영역을 구성할 수 있다는 점이다. 각 이벤트 핸들러 함수는 command 객체로 변환할 수 있으며, Mutex를 사용해서 이들을 호출하고 관리할 수 있다. 물론, 코드가 이벤트 처리 함수로 사용할 수 없게 되어 있다면 리팩토링을 해야 한다. 다시 말해서, HTML 이벤트 속성(예를 들어, onclick="++var")에 로직을 직접 써 넣은 경우라면 이벤트 처리 함수를 정의하고, 이를 호출하도록 변경해야 한다.(예를 들어, onclick="FOO()"와 function FOO(){ ++var; } )
mmlt;htmlmmgt;
mmlt;script language="JavaScript"mmgt;
function newState(){
if (XMLreq.readyState==4) processReply();
}
function requestData(){
...set up asynchronous XML request...
XMLreq.onreadystatechange = newState;
...launch XML request...
}
function processReply(){
var transformedData = ...process data to HTML...
OutputArea.innerHTML = transformedData + "mmlt;brmmgt;";
}
function clearArea(){
OutputArea.innerHTML = "clearedmmlt;brmmgt;";
}
mmlt;/scriptmmgt;
mmlt;body onload="requestData();"mmgt;
mmlt;input type="button" value="clear" onclick="clearArea()"mmgt;
mmlt;div id="OutputArea"/mmgt;
mmlt;/bodymmgt;
mmlt;/htmlmmgt;
목록5. 비동기 이벤트 핸들러를 사용하는 웹 페이지 예제
예를 들어, 목록5에서 보인 것처럼 공통된 데이터를 조작하는 이벤트 처리 함수가 3개 정의되어 있다고 하자. 이들 함수는 페이지 로드 이벤트, 버튼 클릭 이벤트, XML 요청으로부터 받은 응답 이벤트로 구성되어 있다. 페이지 로드 이벤트 핸들러는 데이터에 대한 비동기 요청을 시작한다. 이 핸들러는 받은 데이터를 처리하고, 공통 데이터 구조로 읽어들일 수 있는 요청-응답 이벤트 핸들러를 지정한다. 버튼 클릭 핸들러도 공통 자료 구조에 영향을 미친다. 이들 이벤트 핸들러가 충돌하지 않게 하기 위해 목록6과 같이 각 명령을 변환하고, Mutex를 사용해서 호출할 수 있다.(자바스크립트에서 Map과 Mutex는 mutex.js 파일에 정의되어 있다고 가정한다) 우아한 클래스 상속을 사용해서 Command의 서브 클래스를 구현할 수 있으며, 여기서 사용한 코드는 전역 변수 NEXT_CMD_ID만 사용하는, 정말 최소한의 것만 사용하는 방법을 설명하고 있다.
mmlt;htmlmmgt;
mmlt;script src="mutex.js"mmgt;mmlt;/scriptmmgt;
mmlt;script language="JavaScript"mmgt;
function requestData (){
new Mutex(new RequestDataCmd(),"go"); }
function processReply(){
new Mutex(new ProcessReplyCmd(),"go"); }
function clearArea (){
new Mutex(new ClearAreaCmd(),"go"); }
function newState (){
if (XMLreq.readyState==4) processReply(); }
var NEXT_CMD_ID = 0;
function RequestDataCmd(){
this.id = ++NEXT_CMD_ID;
this.go = function(){
...set up asynchronous XML request...
XMLreq.onreadystatechange = NewState;
...launch XML request...
}
}
function ProcessReplyCmd(){
this.id = ++NEXT_CMD_ID;
this.go = function(){
var transformedData = ...process data to HTML...
OutputArea.innerHTML = transformedData + "mmlt;brmmgt;";
}
}
function ClearAreaCmd(){
this.id = ++NEXT_CMD_ID;
this.go = function(){
OutputArea.innerHTML = "clearedmmlt;brmmgt;"; }
}
mmlt;/scriptmmgt;
mmlt;body onload="requestData();"mmgt;
mmlt;input type="button" value="clear" onclick="clearArea()"mmgt;
mmlt;div id="OutputArea"/mmgt;
mmlt;/bodymmgt;
mmlt;/htmlmmgt;
목록6. 동기 이벤트 핸들러를 사용하도록 수정된 웹 페이지
세 가지 이벤트 핸들러 함수들은 Mutex를 사용해서 원래 로직을 호출하도록 변경되었다. 각 command 클래스는 유일한 ID, 임계 영역 로직을 포함한 메서드를 정의하고 있기 때문에 command 인터페이스 요구사항을 만족시킨다.
결론
AJAX와 RIA로 인해 복잡한 사용자 인터페이스를 구축하려는 열기로 인해 "비대한" GUI 클라이언트에서 전형적으로 사용되던 동일한 디자인 패턴(예를 들어, 모델-뷰-컨트롤러(MVC))을 웹에서도 사용하려 한다. 모듈로 정의되는 뷰와 컨트롤러에서 각각은 고유의 이벤트와 이벤트 핸들러를 갖고 있지만 공통 데이터 모델을 공유하는 디자인 패턴으로 인해 문제가 발생할 가능성이 높다. Command 클래스 안에 이벤트 처리로직을 캡슐화함으로써 월러스 변형을 구현할 수 있었으며, 다양한 undo/redo 기능, 스크립트 인터페이스, 단위 테스트를 사용할 수 있는 기반을 만들게 되었다.
리소스
원문 : http://www.onjava.com/pub/a/onjava/2006/04/05/ajax-mutual-exclusion.html
저자 : Bruce Wallace, 한동훈 역
브라우저 페이지의 뒷단에서 서버 데이터를 요청하는 동안, 앞단에서는 사용자 인터페이스를 계속해서 사용할 수 있게 해주는 에이잭스(AJAX)가 나날이 인기를 얻고 있다. 그러나, 이 두가지 동작은 자바스크립트와 DOM 데이터 구조를 동시에 사용해야 한다. 병행 프로그래밍(Concurrent Programming)에 대한 고적전인 해결책 조차 자바스크립트는 지원하지 않는다. 여기서는, 자바스크립트의 제한을 해결하기 위해, 이미 증명된 상호배제(Mutual Exclusion)를 사용하는 것에 대해 살펴볼 것이다.
왜 상호 배제인가?
같은 데이터에 접근하는 멀티 스레드 프로그램 로직이 동시에 실행되면 문제가 발생한다. 일반적으로 프로그램은 사용하고 있는 데이터가 바뀌지 않는다고 가정한다. 이들 공유 데이터에 접근하는 코드 영역을 임계영역(Critical Sections)이라 하며, 한 번에 하나의 스레드만 프로그램을 실행하게 하는 것을 상호 배제(Mutual Exclusion)라고 한다. AJAX 응용프로그램에서는 사용자 인터페이스 코드에서 사용하는 데이터를 조작하기 위해 XMLHttpRequest에서 가져온 응답을 비동기적으로 처리하는 코드에서 이런 동기화 문제가 발생한다. 공용으로 접근하는 데이터는 웹 페이지 자체의 DOM이나 MVC 모델 등을 사용해서 구현한 자바스크립트 변수일 것이며, 이 두가지 중에 어느 한쪽이 공유 데이터에 대해 변경을 하면, 각각의 로직은 동작하지 않게 될 것이다.
"잠깐만요, 왜 이 문제를 내가 다뤄야하죠?" 라고 얘기할지도 모른다. 불행히도, 이런 종류의 문제는 시간 종속적(timing dependent)인 문제이기 때문에(경쟁조건(Race Condition), 항상 발생하는 것은 아니다. 동기화 문제는 수 많은 요소들에 의해 발생하는 개연적인 문제다. AJAX 응용프로그램을 견고하게 만들기 위해서는 다양한 사용자 인터페이스를 제공하는 인터넷 응용프로그램에서 이런 문제가 발생하지 않도록 보장하는 방법을 통해 이런 상황이 발생하지 않게 하면 된다.
상호 배제는 오직 한 스레드만 임계 영역을 시작하고, 종료한 후에 다른 스레드가 시작할 수 있게 하는 방법이다. 주요 컴퓨터 언어나 프레임워크에서는 상호 배제를 제공하고 있으나, 브라우저에서 사용하는 자바스크립트는 상호 배제를 제공하지 않는다. 언어나 환경의 특별한 지원 없이 상호 배제를 구현하는 고전적인 방법들이 있지만, 이런 방법들은 인터넷 익스플로러 같은 브라우저와 자바스크립트에서 제공하지 않는 몇 가지를 이용하고 있기 때문에 사용할 수 없다. 다음에 소개할 고전적인 알고리즘은 브라우저와 자바스크립트 제한을 해결하기 위해 변형한 것이다.
빵집 알고리즘(Bakery Algorithm)
컴퓨터 과학 분야에는 상호 배제 알고리즘이 몇 가지 있는데, 그 중에서 하나가 램포트의 빵집 알고리즘(Lamport"s Bakery Algorithm)이다. 이 알고리즘은 프로세스 사이의 커뮤니케이션에 공유 메모리만 사용할 때, 경쟁하는 멀티 스레드를 제어하기 위한 방법이다.(즉, 이 방법은 세마포어, 최소단위 TAS(Test-and-Set)과 같은 특별한 방법에 의존하지 않는다) 알고리즘의 뼈대는 위키백과사전에서 가져왔으며, 목록 1과 같다. 이 알고리즘은 각 스레드가 충돌없이 임계 영역에 진입하고, 빠져나올 수 있다.
(역주1: 베이커리 알고리즘(Bakery Algorithm)은 빵집에 사람이 너무 붐벼서 빵을 아무도 사지 못할 때, 번호표를 받고, 빵을 사기위해 기다리는 사람들을 프로세스에 비유해서 만든 알고리즘이다. 따라서, 빵집 알고리즘으로 옮겼다.)
(역주2: 동기화 문제에서 반드시 실행될 것을 보장하는 연산의 최소 단위를 "최소 단위 연산(Atomic Operation)"이라 하며, 대부분의 번역서는 "원자적인 실행" 정도로 옮기고 있다.)
(역주3: Atomic Set-And-Test 알고리즘은 SAT 알고리즘이라 부르기도 하며, 일부 책은 Atomic Test-And-Set 알고리즘 또는 TAS(태스) 알고리즘이라 부른다.)
// 전역 변수의 선언과 초기화
Enter, Number: array [1..N] of integer = {0};
// 각 스레드에서 사용할 로직
// where "(a, b) mmlt; (c, d)"
// means "(a mmlt; c) or ((a == c) and (b mmlt; d))"
Thread(i) {
while (true) {
Enter [i] = 1;
Number[i] = 1 + max(Number[1],...,Number[N]);
Enter [i] = 0;
for (j=1; jmmlt;=N; ++j) {
while (Enter[j] != 0) {
// 스레드 j가 번호를 받을 때 까지 대기
}
while ((Number[j]!=0)
&& ((Number[j],j) mmlt; (Number[i],i))) {
// 스레드가 보다 작은 수 또는 같은 수를 할당받을 때까지 대기
// 보다 높은 우선순위가 도착하면 작업을 종료
}
}
// 임계 영역...
Number[i] = 0;
// 비임계 영역
}
}
목록1. 램포트의 빵집 알고리즘(의사코드)
위에서 보인 것처럼, 알고리즘은 각 스레드가 자신의 스레드 번호(상수 i)와 모두 몇 개의 스레드가 현재 동작중인지(상수 N) 알고 있다고 가정한다. 또한, 대기(wait or sleep)할 수 있는 방법이 있다고 가정한다. 예를 들어, CPU 제어권을 포기하고 다른 스레드에게 제어권을 넘길 수 있는 방법이 있다고 가정한다. 불행히도, 인터넷 익스플로러의 자바스크립트는 이런 기능을 갖고 있지 않다. 그러나, 실제로 스레드 하나에서 실행되는 코드의 여러 부분들을 각각의 개별적인 가상 스레드로 동작하는 것처럼 할 수 있으면 빵집 알고리즘을 사용할 수 있다. 또한, 자바 스크립트는 지정된 시간 만큼 지연 시킨 후에 함수를 실행시킬 수 있는 방법을 제공한다. 따라서, 이들 대안을 사용해서 구현할 수 있는 알고리즘이 빵집 알고리즘이다.
월러스 변형(Wallace Variation)
자바스크립트에서 램포트의 빵집 알고리즘을 구현하는 데 있어 가장 큰 문제는 스레드 API가 없다는 점이다. 자바스크립트에서는 어떤 스레드가 실행중인지, 얼마나 많은 스레드들이 동작(active)중인지 알 수 있는 방법이 없으며, 다른 스레드에게 CPU를 양보할 수 있는 방법도 없으며, 다른 스레드를 관리하기 위해 새로운 스레드를 생성할 방법도 없다는 점이다. 이런 점들 때문에, 어떤 브라우저 이벤트가 스레드에 할당되었는지 검사할 수 없다.
역주: 월러스 변형은 자신의 이름을 따서 붙인 이름이다
이런 문제들을 해결하기 위한 방법으로 명령 디자인 패턴(Command Design Pattern)을 응용하는 것이다. 로직을 초기화하는 데 필요한 모든 데이터, 임계 영역에 진입하는 모든 로직에 command 객체를 삽입하는 방법을 사용해서 명령들을 관리하는 클래스 안에 빵집 알고리즘을 동작하게 할 수 있다. 상호 배제 클래스는 다른 임계 영역들이 실행되지 않을 때만 임계 영역에 진입하는 코드를, 마치 각각이 고유의 가상 스레인 것처럼, 호출할 수 있다.(각 임계 영역은 command 객체 메서드로 캡슐화되어 있다) 자바스크립트의 setTimeout()은 다른 대기중인 명령들에 CPU를 양보하기 위해 사용된다.
command 객체를 위해 다음과 같은 간단한 기본 클래스를 사용한다. 클래스는 빵집 알고리즘의 월러스 변형을 구현하기 위해 정의한 것이다(목록3에 Mutex) 자바스크립트에서 클래스 기반 객체를 구현하는 다양한 방법들이 있지만, 어떤 객체 스킴도 고유한 ID를 가지며, 전체 임계 영역은 하나의 메서드로 캡슐화할 수 있는 한 여기서 설명하는 방법이 동작할 것이다.
1 function Command() {
2 if (!Command.NextID) Command.NextID = 0;
3 this.id = ++Command.NextID;
4 // unsynchronized API
5 this.doit = function(){ alert("DOIT called"); }
6 this.undo = function(){ alert("UNDO called"); }
7 this.redo = function(){ this.doit(); }
8 // synchronized API
9 this.sDoIt = function(){ new Mutex(this,"doit"); }
10 this.sUnDo = function(){ new Mutex(this,"undo"); }
11 this.sReDo = function(){ new Mutex(this,"redo"); }
12 }
목록2. Command 객체에 사용한 간단한 기본 클래스
Command 클래스는 임계 영역 메서드를 흉내내기 위한 함수 세 개(5-7번째 줄)가 있으며, 호출을 Mutex 객체로 감출 수 있는 한 어떤 메서드도 정의할 수 있다(9-11번째 줄) 이게 일반 메서드 호출(비동기 메서드를 호출하는 것 같은)과 동기 메서드 호출과의 핵심적인 차이점이다. 모순되지만, 동기화 메서들은 동기적으로 실행하지 않는다고 가정한다. 다시 말해서, sDoIt()이 호출되면 sDoIt()이 반환되더라도 doit()이 아직 실행되지 않았다고 가정해야 한다. 미래의 어떤 시점에서 doit() 메서드의 실행이 끝났거나, doit() 메서드가 시작되지 않았다고 가정해야 한다. 다른 말로 하자면, Mutex 인스턴스화는 새로운 스레드를 시작하는 것처럼 생각해야 한다는 것이다.
1 function Mutex( cmdObject, methodName ) {
2 // define static field and method
3 if (!Mutex.Wait) Mutex.Wait = new Map();
4 Mutex.SLICE = function( cmdID, startID ) {
5 Mutex.Wait.get(cmdID).attempt( Mutex.Wait.get(startID) );
6 }
7 // define instance method
8 this.attempt = function( start ) {
9 for (var j=start; j; j=Mutex.Wait.next(j.c.id)) {
10 if (j.enter
11 || (j.number && (j.number mmlt; this.number ||
12 (j.number == this.number
13 && j.c.id mmlt; this.c.id))))
14 return setTimeout
15 ("Mutex.SLICE("+this.c.id+","+j.c.id+")",10);
16 }
17 //run with exclusive access
18 this.c[ this.methodID ]();
19 //release exclusive access
20 this.number = 0;
21 Mutex.Wait.remove( this.c.id );
22 }
23 // constructor logic
24 this.c = cmdObject;
25 this.methodID = methodName;
26 //(enter and number are "false" here)
27 Mutex.Wait.add( this.c.id, this );
28 this.enter = true;
29 this.number = (new Date()).getTime();
30 this.enter = false;
31 this.attempt( Mutex.Wait.first() );
32 }
목록3. Mutex 클래스로 구현한 월러스 변형 알고리즘
Mutex 클래스의 기본 로직은 각각의 새로운 Mutex 인스턴스를 마스터 대기 목록에 넣고, 시작할 때 까지 인스턴스들이 줄을 서서 기다리는 것이다. "줄의 앞자리"를 얻으려는 각각의 시도 후에는 대기를 해야하며, setTimeout은 각각의 새로운 시도들을 스케줄하기 위해 사용된다. "앞 자리(the head)"에 도착하면(17번째 줄), 상호 배제가 성립한다. 따라서, 임계 영역 메서드가 호출될 수 있다. 임계 영역이 끝나면 베타적인 접근을 해제(release)하고, Mutex 인스턴스는 대기 목록에서 제거된다(20-21번째 줄).
Mutex 생성자(23-31번째 줄)는 Command 객체와 메서드 이름 매개변수들을 기록하고, 목록4에서 Map 클래스로 구현한 희소 배열(Sparse Array)에 스스로를 등록한다. "다음 번호"를 얻은 후에, 줄의 끝에서 대기를 시작한다. 대기자 번호는 연속된 번호이고, 같은 번호는 없기 때문에, 현재 시간(timestamp)를 "다음" 번호로 사용한다.
attemp() 메서드는 원본 의사 코드에서 두 개였던 대기 루프를 줄의 앞자리에 올 때 까지 임계 영역에 도달하지 않는 단일 루프로 결합한다. 이 루프는 바쁜 대기 투표(Busy-wait polling)의 형태로, setTimeout() 호출에서 지정된 시간만큼 대기한다. setTimeout은 객체 메서드가 아니므로 "일반 함수(flat function)"이어야 한다. 따라서, 정적 메서드 Mutex.SLICE를 4-6번째 줄에 정의했다. SLICE는 지정된 Mutex 객체를 마스터 대기 목록에 추가하고, 대기자 목록에서 얼마나 멀리 떨어져 있는지 지정하는 시작 매개변수와 함께 attempt() 메서드를 호출한다. 각 SLICE() 호출은 "CPU의 슬라이스"를 얻는 것과 같다. CPU 제어권을 반환하는 협동형 접근방법(Cooperative Approach)는 코루틴(Coroutine)을 생각나게 한다.
function Map() {
this.map = new Object();
// Map API
this.add = function( k,o ){
this.map[k] = o;
}
this.remove = function( k ){
delete this.map[k];
}
this.get = function( k ){
return k==null ? null : this.map[k];
}
this.first = function(){
return this.get( this.nextKey() );
}
this.next = function( k ){
return this.get( this.nextKey(k) );
}
this.nextKey = function( k ){
for (i in this.map) {
if ( !k ) return i;
if (k==i) k=null; /*tricky*/
}
return null;
}
}
목록4. Map 자료구조로 구현한 희소 배열(Sparse Array)
리치 인터넷 응용프로그램 통합
Mutex는 동적으로 변하는 스레드(가상 또는 실제 스레드)들을 다루며, 브라우저는 각 브라우저 이벤트에 각각의 스레드를 할당하는 식으로 동작한다면 실제 스레드 ID를 알 수 없다는 사실을 이용할 수 있다. 이와 유사하게 단순화시키는 가정은 각 완료 이벤트 핸들러가 복잡한 임계 영역을 구성할 수 있다는 점이다. 각 이벤트 핸들러 함수는 command 객체로 변환할 수 있으며, Mutex를 사용해서 이들을 호출하고 관리할 수 있다. 물론, 코드가 이벤트 처리 함수로 사용할 수 없게 되어 있다면 리팩토링을 해야 한다. 다시 말해서, HTML 이벤트 속성(예를 들어, onclick="++var")에 로직을 직접 써 넣은 경우라면 이벤트 처리 함수를 정의하고, 이를 호출하도록 변경해야 한다.(예를 들어, onclick="FOO()"와 function FOO(){ ++var; } )
mmlt;htmlmmgt;
mmlt;script language="JavaScript"mmgt;
function newState(){
if (XMLreq.readyState==4) processReply();
}
function requestData(){
...set up asynchronous XML request...
XMLreq.onreadystatechange = newState;
...launch XML request...
}
function processReply(){
var transformedData = ...process data to HTML...
OutputArea.innerHTML = transformedData + "mmlt;brmmgt;";
}
function clearArea(){
OutputArea.innerHTML = "clearedmmlt;brmmgt;";
}
mmlt;/scriptmmgt;
mmlt;body onload="requestData();"mmgt;
mmlt;input type="button" value="clear" onclick="clearArea()"mmgt;
mmlt;div id="OutputArea"/mmgt;
mmlt;/bodymmgt;
mmlt;/htmlmmgt;
목록5. 비동기 이벤트 핸들러를 사용하는 웹 페이지 예제
예를 들어, 목록5에서 보인 것처럼 공통된 데이터를 조작하는 이벤트 처리 함수가 3개 정의되어 있다고 하자. 이들 함수는 페이지 로드 이벤트, 버튼 클릭 이벤트, XML 요청으로부터 받은 응답 이벤트로 구성되어 있다. 페이지 로드 이벤트 핸들러는 데이터에 대한 비동기 요청을 시작한다. 이 핸들러는 받은 데이터를 처리하고, 공통 데이터 구조로 읽어들일 수 있는 요청-응답 이벤트 핸들러를 지정한다. 버튼 클릭 핸들러도 공통 자료 구조에 영향을 미친다. 이들 이벤트 핸들러가 충돌하지 않게 하기 위해 목록6과 같이 각 명령을 변환하고, Mutex를 사용해서 호출할 수 있다.(자바스크립트에서 Map과 Mutex는 mutex.js 파일에 정의되어 있다고 가정한다) 우아한 클래스 상속을 사용해서 Command의 서브 클래스를 구현할 수 있으며, 여기서 사용한 코드는 전역 변수 NEXT_CMD_ID만 사용하는, 정말 최소한의 것만 사용하는 방법을 설명하고 있다.
mmlt;htmlmmgt;
mmlt;script src="mutex.js"mmgt;mmlt;/scriptmmgt;
mmlt;script language="JavaScript"mmgt;
function requestData (){
new Mutex(new RequestDataCmd(),"go"); }
function processReply(){
new Mutex(new ProcessReplyCmd(),"go"); }
function clearArea (){
new Mutex(new ClearAreaCmd(),"go"); }
function newState (){
if (XMLreq.readyState==4) processReply(); }
var NEXT_CMD_ID = 0;
function RequestDataCmd(){
this.id = ++NEXT_CMD_ID;
this.go = function(){
...set up asynchronous XML request...
XMLreq.onreadystatechange = NewState;
...launch XML request...
}
}
function ProcessReplyCmd(){
this.id = ++NEXT_CMD_ID;
this.go = function(){
var transformedData = ...process data to HTML...
OutputArea.innerHTML = transformedData + "mmlt;brmmgt;";
}
}
function ClearAreaCmd(){
this.id = ++NEXT_CMD_ID;
this.go = function(){
OutputArea.innerHTML = "clearedmmlt;brmmgt;"; }
}
mmlt;/scriptmmgt;
mmlt;body onload="requestData();"mmgt;
mmlt;input type="button" value="clear" onclick="clearArea()"mmgt;
mmlt;div id="OutputArea"/mmgt;
mmlt;/bodymmgt;
mmlt;/htmlmmgt;
목록6. 동기 이벤트 핸들러를 사용하도록 수정된 웹 페이지
세 가지 이벤트 핸들러 함수들은 Mutex를 사용해서 원래 로직을 호출하도록 변경되었다. 각 command 클래스는 유일한 ID, 임계 영역 로직을 포함한 메서드를 정의하고 있기 때문에 command 인터페이스 요구사항을 만족시킨다.
결론
AJAX와 RIA로 인해 복잡한 사용자 인터페이스를 구축하려는 열기로 인해 "비대한" GUI 클라이언트에서 전형적으로 사용되던 동일한 디자인 패턴(예를 들어, 모델-뷰-컨트롤러(MVC))을 웹에서도 사용하려 한다. 모듈로 정의되는 뷰와 컨트롤러에서 각각은 고유의 이벤트와 이벤트 핸들러를 갖고 있지만 공통 데이터 모델을 공유하는 디자인 패턴으로 인해 문제가 발생할 가능성이 높다. Command 클래스 안에 이벤트 처리로직을 캡슐화함으로써 월러스 변형을 구현할 수 있었으며, 다양한 undo/redo 기능, 스크립트 인터페이스, 단위 테스트를 사용할 수 있는 기반을 만들게 되었다.
리소스
- 이 기사의 예제 코드는 다운로드 할 수 있다. 서버 연결 없이 웹 페이지를 브라우저에서 직접 실행하는 것과 같은 생략된 내용들을 포함하고 있다.
- 이 기사에 사용된 기술을 사용한 자바스크립트 프레임워크(Gravy)를 다운로드 할 수 있으며, JsDoc 문서를 갖추고 있다. Gravy는 자바스크립트로 응용프로그램에서 필요한 모든 기능들을 제공한다. 응용프로그램은 데이터베이스 CRUD 연산을 위해 서버에 접근만 할 수 있다.
TAG :
이전 글 : IIS7 미리 보기
최신 콘텐츠