KR100528973B1

KR100528973B1 - 가비지 콜렉션 방법 및 그 장치

Info

Publication number: KR100528973B1
Application number: KR10-2003-0078126A
Authority: KR
Inventors: 정임영; 전성익; 정교일
Original assignee: 한국전자통신연구원
Priority date: 2003-11-05
Filing date: 2003-11-05
Publication date: 2005-11-16
Also published as: US7797498B2; KR20050043291A; US20070136401A1; GB2423172A; GB0608895D0; GB2423172B; WO2005045683A1

Abstract

가비지 콜렉션 방법 및 그 장치가 개시된다. 메모리에서 제거해야 할 객체 목록을 작성하고 외부로부터 수신한 명령에 대한 소정의 응답시간까지 남은 시간을 계산한 후 남은 시간 동안 객체 목록에 작성된 객체를 메모리에서 제거하고 남은 시간 동안 제거되지 못한 객체 목록의 리스트를 메모리에 저장한다. 이로써, 가비지 콜렉션의 로드(load)를 분산 처리하여 응답시간 지연 및 타임아웃에 의한 통신실패를 방지한다.

Description

가비지 콜렉션 방법 및 그 장치{Apparatus and method for garbage collection}

본 발명은 가비지 콜렉션 장치 및 그 방법에 관한 것으로, 보다 상세하게는 스마트 카드와 같은 계산 및 통신 능력을 가진 장치에서 가비지 콜렉션(garbage collection)을 수행하는 장치 및 방법에 관한 것이다.

종래의 가비지 콜렉션의 방법인 mark and sweep 방식은 mark phase와 sweep phase를 모두 수행하는 것이 하나의 가비지 콜렉션이 완료되는 것으로 본다. 따라서 mark and sweep 방식은 이 두 과정을 묶어 수행하거나, 전체 object를 대상으로 하지 않고 일부 object들에 대해 검사를 하고 검사한 부분에 대해서만 가비지 콜렉션을 수행하는 partial garbage collection을 수행한다.

스마트카드처럼 한정된 자원을 가진 사용자-상호작용 통신(user-interactive communication) 기반의 매체는 수행 시간이 긴 데이터 처리과정(processing)를 수용하기 힘들다. 따라서 수행시간이 별도로 배정되어 있는 것이 아닌 가비지 콜렉션과 같은 처리과정은 command/response의 communication 구도 상에서 행해지는 경우에 응답시간에 영향을 준다. 따라서 사용자가 느끼는 응답지연이 생기는 경우 및 응답지연에 의해 응답시간의 타임아웃(timeout)이 생기는 경우를 고려해야 한다.

또한 스마트카드의 경우는 processing의 효율을 위해 one-processor 장치에 single thread 연산의 간단한 구조를 띠고 있는 경우가 대부분이고, 한 순간에 사용자와의 communication에 관련된 응용프로그램은 한 개이다. 따라서, 가비지 콜렉션을 관리하는 process를 별도로 구비할 수 없으며 부분적인 object에 대한 partial garbage collection을 효율적으로 행할 수 있을 만큼 한번에 활성화되는 응용프로그램이 많지도 않다. 그리고 full/partial garbage collection을 늘 관리할만한 자원이 풍부한 것도 아니다.

따라서 가비지 콜렉션은 필요한 경우마다 호출되며 호출되는 순간에만 소정의 수행과정을 행한다. 수동적인 호출에 의해 간헐적으로 수행되는 가비지 콜렉션의 경우에 수행시간에 영향을 미치는 것은 수거해야 할 garbage가 어느 정도인지와 garbage 인지 아닌지를 검사하는데 걸리는 시간이다.

전자의 경우는 객체(object) 관리 테이블과 수거대상이 되는 객체가 주로 어느 메모리에 위치하는가에 따라 결정되며 쓰기연산에서의 시간이 많이 걸리는 메모리 매체를 주로 다뤄야 하는 경우에는 처리 시간이 처리량에 따라 영향을 많이 받는다. 후자의 경우는 검사할 대상이 되는 객체의 수에 영향을 많이 받는다.

스마트카드의 경우는 한 번의 가비지 콜렉션에서 mark와 sweep phase를 한꺼번에 수행하는 것이 부담스러운 매체이다. 스마트카드의 경우는 특히 persistent memory로 사용이 되는 EEPROM에의 쓰기에 시간이 많이 걸린다. 가비지 콜렉션과정의 sweep phase에서 persistent memory상의 객체(object)나 transient object라도 객체 관리 테이블이 EEPROM에 존재하는 경우에는 이 객체들의 메모리를 수거하기 위하여 EEPROM에의 쓰기가 동반된다. garbage collection 상에서 이로 인한 processing time이 많이 걸릴 수 있다. 따라서, 한 가비지 콜렉션을 구성하는 처리과정 자체를 나눠서 로드(load)를 분산하는 방법은 실제 의미가 있는 방법이다.

본 발명이 이루고자 하는 기술적 과제는, 가비지 콜렉션(garbage collcetion)의 로드(load)를 분산 처리하여 응답시간 지연 및 타임아웃에 의한 통신 실패를 방지하는 가비지 콜렉션 방법 및 그 장치를 제공하는 데 있다.

본 발명이 이루고자 하는 다른 기술적 과제는, 가비지 콜렉션의 로드를 분산 처리하여 응답시간 지연 및 타임아웃에 의한 통신 실패를 방지하는 가비지 콜렉션 방법을 컴퓨터에서 실행시기키 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체를 제공하는 데 있다.

상기의 기술적 과제를 달성하기 위한, 본 발명에 따른 가비지 콜렉션 방법의 일 실시예는, 메모리에서 제거해야 할 객체 목록을 작성하는 단계; 외부로부터 수신한 명령에 대한 소정의 응답시간까지 남은 시간을 계산하는 단계; 상기 남은 시간 동안 상기 객체 목록에 작성된 객체를 메모리에서 제거하는 단계; 및 상기 남은 시간 동안 제거되지 못한 상기 객체 목록의 리스트를 메모리에 저장하는 단계;를 포함한다.

상기의 기술적 과제를 달성하기 위한, 본 발명에 따른 가비지 콜렉션 장치의 일 실시예는, 외부로부터 수신한 명령에 대한 소정의 응답시간까지 남은 시간을 계산하는 타이머; 메모리에서 제거해야 할 객체 목록을 작성한 후 상기 남은 시간 동안 상기 객체 목록에 작성된 객체를 메모리에서 제거하고 상기 남은 시간 동안 제거되지 못한 상기 객체 목록의 리스트를 메모리에 저장하는 메모리 관리부;를 포함한다.

이로써, 가비지 콜렉션의 로드를 분산 처리하여 응답시간 지연 및 타임아웃에 의한 통신 실패를 방지한다.

이하에서, 첨부된 도면들을 참조하여 본 발명에 따른 가비지 콜렉션 방법 및 그 장치에 대하여 상세히 설명한다.

도 1a은 스마트카드 및 스마트카드의 통신 방식을 도시한 도면이다.

도 1a는 국제 표준에 의한 USIM(Universal Subscriber Identity Module), SIM(Subscriber Identity Module) 등의 스마트카드(104)가 호스트(또는 터미널)(100)과 ISO7816의 스마트카드 통신 표준에 의해 중간에 카드리더기(Card Acceptance Device:CAD)(102)를 매개로 통신하는 도식을 보여준다.

일반적으로 스마트카드(104)는 CPU, 메모리들(RAM,ROM,EEPROM), 버스, 타이머, 입출력 장치 등을 갖추고 있는 소형 시스템이다. 그러나 스마트카드(104) 칩 자체의 크기제한으로 인해 포함된 H/W의 메모리 용량 및 프로세서(processor)의 처리능력이 제한된다. 스마트카드는 수동적인 매체로서 외부로부터 명령(command)이 들어오면 이를 처리하고 처리결과에 대한 응답을 주는 것이 기본적인 구동방법이다.

도 1b는 스마트 카드의 일종인 Java 스마트 카드의 내부를 도시한 도면이다.

도 1b를 참조하면, 스마트 카드(120)는 하드웨어(실리콘 칩)(128)위에 소프트웨어인 카드운영체제(Card Operating System:COS)(126)가 올라가고 Java Card의 특성을 반영하는 자바카드 가상기계(Java Card Virtual Machine:JCVM)(124)가 올라간다. 카드의 응용 어플리케이션인 Java Card Applet(134)을 구동하기 위해 스마트카드(120)는 Java Card API(121)를 제공하고, COS단(126)에서 제공되는 function(130)들을 JCVM(124)이나 Java Card Applet(134)이 불러쓰도록 하기위해 native-interface와 기타 추가된 기능에 대한 API(122)를 제공한다.

스마트 카드(120) 내부의 가비지 콜렉션은 COS단(126)의 가비지 콜렉션 모듈(132)을 통해 제공된다. 자바 스마트 카드(120)는 가비지 콜렉션 모듈을 수동적으로 불러 사용할 수 있도록 API(122)를 제공한다. 자바 스마트 카드의 응용 애플리케이션인 applet(134)을 제외한 부분을 JCOS(136)라고 한다.

스마트 카드는 사용자의 요구에 빠르고 고른 응답시간을 보장하는 것과 카드 위에 올라가서 수행되는 어플리케이션의 운용에 필요한 워킹 메모리가 항상 확보되는 것이 중요하다. 전자의 경우는 특히 수행시간이 많이 걸리는 암호연산처리 부분과 EEPROM에의 쓰기 부분 시간에서 응답지연을 줄이는 노력을 해야 한다. 가비지 콜렉션의 경우 EEPROM에의 쓰기 접근을 줄이는 방법이 고려된다. 또한 스마트 카드의 경우는 처리과정에 비용이 많이 드는 이유로 메모리 컴팩션을 따로 하지 않기 때문에 사용되지 않으면서도 할당된 공간으로 되어있는 메모리의 수거는 새로운 메모리 할당을 위해 필수적인 부분이다.

도 1c는 스마트 카드의 명령 처리과정을 도시한 도면이다.

도 1c를 참조하면, 사용자 상호작용(user-interactive) 매체인 스마트 카드(150)는 호스트(또는 터미널)(140)에서 명령(command)을 받고 이에 대한 응답을 주는 데 걸리는 시간의 한계가 있다.

호스트(또는 터미널)(140)는 스마트카드(150)에서의 처리시간이 오래 걸려서 미리 설정된 시간의 한계를 지나 응답이 오는 경우에는 타임아웃(timeout)으로 처리한다. timeout 되는 경우에 호스트(140)는 소정의 횟수만큼 명령을 스마트카드(150)로 다시 보내어 정해진 시간 안에 정상적인 응답을 기대한다(144). 그러나 여전히 timeout이 되는 경우에는 호스트(또는 터미널)(140)는 도 1c와 같이 응답을 받는 것이 실패한 것으로 처리한다(146). 사용자는 응답이 오지 않는 경우에 명령을 몇 번이나 다시 스마트 카드(150)로 보낼 것인지 사용환경에 따라 임의적으로 정할 수 있다.

명령에 대한 처리 응답이 정해진 시간 내에 제대로 응신되는지를 기준으로 통신 성공/실패를 규정짓는 것과는 별도로, 스마트 카드와 같이 user-interactive 매체인 경우에 스마트카드(150)와의 통신 QoS(Quality of Service)를 결정짓는 중요한 요소 중에 하나가 스마트카드(150)가 얼마나 사용자의 요구에 빠르게 응답을 하는가이다.

도 1d는 사용자의 QoS를 보장하기 위한 시간 한계를 도시한 도면이다.

도 1d를 참조하면, 응답의 timeout(162)을 결정짓는 부분과 사용자가 느끼는 응답지연을 개선하고자 정하는 user endurable time limit(160)은 다르다. 스마트 카드와 관련된 응용서비스를 개발할 경우 및 스마트카드 관리 모듈을 설계할 경우에 response timeout(162)을 피하도록 하는 것 뿐만 아니라 사용자가 느끼는 응답 지연을 개선하기 위하여 빠른 응답을 지원해 줄 수 있도록 하여야 한다.

도 2a는 호스트와 통신하는 스마트 카드의 상태 변화를 도시한 도면이다.

구체적으로 도 2a는 호스트(또는 터미널)와 스마트카드가 CAD를 통하여 통신하는 경우에 통신 사이클(communication cycle)(200)과 스마트카드의 상태(status)(210,220) 변화를 도시한 도면이다.

하나의 통신 사이클(200)은 호스트(또는 터미널)가 스마트카드로 명령(command)을 전송하고 이에 대한 응답을 스마트카드로부터 받는 것으로 구성된다. 이런 통신 사이클이 여러개 모여 스마트카드와 호스트(또는 터미널) 간의 카드 통신 session을 구성한다. 즉 카드 통신 session은 스마트카드를 CAD에 넣어 인식을 시키고부터 스마트카드를 CAD에서 제거할 때까지를 지칭한다.

스마트카드는 응답을 보내고 새로운 명령을 받을 때까지 대기모드(220)이다. 대기모드(220)에서 스마트카드는 스마트카드내의 I/O장치와 논리적으로 연결된 통신 채널들을 체크한다. 호스트(또는 터미널)로부터 명령을 전송받고 명령에 대한 응답을 생성하여 전송할 때까지 활성 처리모드(210)이다. 이 두 상태(status)(210,220)를 반복하면서 스마트카드는 작동을 한다.

도 2b는 가비지 콜렉션 처리방법의 일 실시예를 도시한 도면이다.

도 2b를 참조하면, 하나의 프로세서(processor)를 가진 스마트카드는 활성 처리모드(260)에서 호스트(또는 터미널)로부터 수신한 명령 및 스마트 카드 관리를 수행한다. 따라서 가비지 콜렉션의 경우에 처리 요청이 내부적으로 생성되어 COS단(126)에 전달되면 현재의 통신 사이클(commnunicatin cycle)이나 다음 통신 사이클에서 가비지 콜렉션의 mark/sweep phase를 한꺼번에 수행한다.

가비지콜렉션을 호출할 때마다, 스마트 카드는 현재 스마트 카드에서 제거되지 말아야 할 객체의 목록을 작성하고(mark phase) 이를 제외한 모든 객체는 메모리에서 없애는 방법을 사용한다(sweep phase). mark phase 와 sweep phase를 정상적인 명령처리와 같이 한 통신 사이클에서 수행할 때 스마트 카드에서 응답시간의 지연 및 가비지 콜렉션 자체로 인한 순간적인 메모리의 요구량 부족에 처할 수가 있다. 제거 대상을 고르는데도 시간이 걸리지만, 객체를 제거하는 과정도 스마트카드의 EEPROM의 특성에 따른 프로세싱 시간도 많은 부분을 차지한다.

도 2b의 가비지 콜렉션 방법은 가비지 콜렉션에 필요한 어떤 정보도 이후의 쓰임을 위해 메모리에 저장해 둘 필요가 없고 당장 수행되는 가비지 콜렉션에서 요구되는 메모리만 확보하면 된다. 따라서, 이러한 방식에서는 EEPROM과 같은 쓰기 지연(writing delay)이 요구되는 메모리보다는 RAM공간을 활용한다. RAM공간도 공간을 지정하여 사용하는 것이 아니라, stack공간을 이용하거나 다른 공간으로 예약된 부분에서 데이터가 차지 않은 공간을 이용하는 방법으로 메모리 낭비를 막는다.

그러나, 가비지 콜렉션의 수행은 호스트로부터 수신한 명령을 처리하고 응답을 만들어 내는 일 자체와는 무관하여 가비지 콜렉션에 의해 초래되는 응답지연으로 사용자는 스마트 카드 사용에 불편을 느낄 수 있다.

가비지 콜렉션이 주는 부담으로 인해 스마트카드와 같이 처리(processing) 능력이 작고 메모리 크기도 제약을 받는 매체의 경우에는, 가비지 콜렉션을 자동으로 관리하는 모듈을 포함하지 않고 가비지 콜렉션이 필요할 때마다 불러서 사용하는 방법을 사용한다.

스마트카드의 메모리가 대형 매체에 비해 작기는 하지만 점점 커지는 추세이다. 또한 스마트카드 응용프로그램으로 생성이 되는 객체(object)의 개수도 많아지고 이에 따라 검사대상이 되는 객체의 수와 수집대상이 되는 garbage도 많아지므로 전체 메모리의 객체들을 대상으로 garbage를 찾는 과정과 이를 없애는 과정이 한번의 가비지 콜렉션 과정에 다 포함이 되는 경우에는 이로 인한 응답지연이나 timeout의 가능성이 커진다.

도 3a 내지 도 3g는 본 발명에 따른 가비지 콜렉션 처리방법의 일 실시예를 도시한 도면이다.

도 3a를 참조하면, 본 발명은 응답시간 지연 및 timeout의 가능성을 줄이기 위하여 한 번의 가비지 콜렉션을 여러 통신 사이클에 나누어서 수행한다(300). 여러 통신 사이클에 가비지 콜렉션을 어떻게 분산 수행하는가 하는 부분은 타이머(timer)에 의한 가용시간측정 방법을 이용한다.

mark phase는 현재의 스마트 카드 상태에서 제거되면 안되는 객체들의 목록을 만들고 이 객체목록을 토대로 객체 테이블에서 제거해야 할 객체목록도 만든다. 응용프로그램 수행 중에 객체를 새로이 생성하거나 제거할 때 이 목록들도 같이 갱신된다. 새로운 가비지 콜렉션이 호출될 때, 이미 기존에 만들어진 제거 대상 목록의 객체들이 제거가 다 안되어서 남은 것이 있다면 이 목록에 제거할 객체를 추가해 나간다. 테이블을 만드는 시점은 다음의 두 가지 경우인데 기존에 유지되던 제거 대상 객체 테이블이 없는 경우에는 새로 만든다.

1) 가비지 콜렉션 호출시

2) 스마트카드의 통신 세션이 초기화 될 때

새로운 가비지 콜렉션이 호출되었을 때, 기존에 만들어져 있던 제거목록의 객체들을 다 없애고 응답시간 한계까지에서 남은 시간이 있다면 이 새로 호출된 가비지 콜렉션의 mark phase에서는 새로운 제거 객체 목록을 만든다.

가비지 콜렉션의 sweep phase에서는 이미 만들어진 제거대상 객체목록을 토대로, 카드의 응답시간 한계까지 남은 시간을 측정해 보고, 남은 시간만큼 객체를 없앤다. 한 번의 응답시간 주기 내에 제거되지 못하고 남은 객체리스트는 EEPROM이나 RAM에 보관한다. 다시 CAD를 통해 카드로 수행할 명령이 오면 명령의 처리를 하고 이에 대한 응답시간 한계까지 남은 시간 동안 제거 대상 객체를 제거하는 것을 반복한다.

새로운 객체에 대한 메모리 할당 요구가 명령 처리 중에 발생하면, 제거할 대상이 되는 객체가 반납할 메모리 부분과 함께 기존 할당되지 않고 있는 메모리를 대상으로 전체 메모리의 조각이 가장 적게 나는 메모리 공간을 찾아서 할당을 하고, 관계되는 메모리 반납부분이 있다면 이도 같이 처리를 한다. 객체 리스트 정보는 비트맵으로 관리를 하여 필요한 메모리의 양을 줄인다.

도 3b를 참조하면, 스마트 카드는 명령을 처리하고 응답시간의 time limit까지 남은 시간을 측정하거나, QoS를 위해 사용자가 응답지연을 느끼지 않을 정도의 정해진 시간까지 남은 시간을 측정한다. 그리고 스마트 카드는 통신 사이클에서 수행할 가비지 콜렉션의 양을 가늠하여 남은 시간 안에 한번의 가비지 콜렉션의 수행을 완료할 수 있는 경우에는 가비지 콜렉션을 수행을 완료한다.

도 3c, 도 3d, 도 3e, 도 3f 및 도 3g의 경우는 정해진 시간 안에 한번의 가비지 콜렉션의 수행이 부담스러운 경우, 이에 대한 분산처리를 수행하는 실시예를 도시한 도면이다.

도 3c를 참조하면, 가비지 콜렉션을 두 번의 step(320,322)으로 나눠 수행을 하는 경우를 보여준다.

두 번으로 나눠서 수행하는 가비지 콜렉션 양의 기준은 각 통신 사이클에서 명령을 수행한 후 측정한 가용시간들을 근거로 한다. 가비지 콜렉션에서 mark and sweep 방식을 사용하는 경우에는 mark와 sweep의 두 phase를 나눠 수행하는 방법을 취하거나 sweep 단계에서 object의 메모리를 회수하는 부분을 나눠 수행하는 방법을 취한다.

여러 통신 사이클에 걸친 가비지 콜렉션 수행은 수거할 대상이 되는 객체들의 주소 목록을 따로 메모리에 보관을 하고 이를 이용해서 sweep과정을 수행하도록 한다. 여러 통신 사이클을 거치는 동안 mark phase로 조사한 수거대상이 되는 객체들의 목록을 잃어 이를 다시 조사해야하는 가능성을 배제하기 위해서는 제거대상 객체 목록을 EEPROM에 보관한다.

이전 통신 사이클에서 수행되지 않은 가비지 콜렉션의 양이 작으면, 도 3e에서와 같이 명령을 수신하고 이로 인한 새로운 통신 사이클이 시작이 되었을 때 명령처리에 앞서 가비지 콜렉션을 먼저 수행 한 후 명령 수행과정을 밟을 수 있다.

한 가비지 콜렉션 과정이 끝나기도 전에 새로운 가비지 콜렉션 수행이 호출되는 경우는, 현재의 가비지 콜렉션 과정을 수행하고 새로운 가비지 콜렉션 과정을 시작하는 경우와 현재 sweep 대상으로 모아놓은 object의 목록에 새로운 수거 대상이 되는 object의 목록을 추가하는 방법을 사용한다. 그러나 어떠한 경우라도 새로이 호출되는 가비지 콜렉션은 빠짐없이 수행이 되도록 스케줄 관리를 한다.

도 3d를 참조하면, 두 번째의 통신 사이클에서 두 개의 가비지 콜렉션(332,334)의 부분 과정들을 수행한다. 도 3d는 첫 번째 통신 사이클상에서 수행되던 가비지 콜렉션의 잔여분이 두 번째 통신 사이클로 넘어온 부분(332)과 두 번째 통신 사이클상에서 호출된 새로운 가비지 콜렉션의 수행이 남은 가용시간 안에 다 완료되지 못하고 부분적으로 수행된 부분(334)을 도시한다.

두 번째 통신 사이클에서 새로이 호출된 가비지 콜렉션의 잔여분(336)은 도 3d에서 세 번째 통신 사이클로 넘겨져 처리된다.

도 3e를 참조하면, 도 3d에서의 가비지 콜렉션의 수행 위치가 달라진 경우인데, 이전 가비지 콜렉션의 수행결과(340) 남은 부분(342)이 적을 경우 두 번째 통신 사이클에서 명령을 수신받자마자 남은 가비지 콜렉션(342)의 수행을 완료한 후 수신한 명령의 처리를 수행한다. 두 번째 통신 사이클에서 새로이 요청된 가비지 콜렉션(344)은 남은 가용시간동안 수행을 하고 남은 부분(346)세 번째 통신 사이클로 넘겨진다.

도 3f, 도 3g의 경우는 명령 처리의 중간에 가비지 콜렉션을 같이 수행하는 것에 관한 도면이다.

시간이 많이 걸리는 EEPROM 쓰기의 특성을 이용하여 가비지 콜렉션을 명령 처리와 동시에 처리하거나, 명령 수행 중 object deletion 과정과 가비지 콜렉션의 sweep 과정을 같이 수행하도록 하여 처리 효율을 높이는 방법을 사용한다(352,354).

전자의 경우를 살펴보면, EEPROM이 persistent memory로 사용되는 경우에 EEPROM은 페이지 단위의 쓰기를 기본으로 한다. 같은 페이지 내의 쓰기를 하는 경우는 페이지 간 쓰기를 하는 경우에 발생하는 block time을 없앨 수 있기 때문에 EEPROM의 한 페이지 내에 쓰여질 데이터를 모아서 한꺼번에 쓰기 처리를 하면 쓰기에서 걸리는 시간을 줄일 수 있다. 따라서, 명령 처리와 가비지 콜렉션 처리를 병행해서 진행하는 scheme을 사용할 수 있다. 또한 도 3f와 도 3g는 분산 수행되는 가비지 콜렉션들의 부분 step들이 어느 시점에서 수행이 될 수 있는지에 대해 도시한다.

도 4a 내지 도 4c는 본 발명에 따른 가비지 콜렉션 방법의 흐름을 도시한 도면이다.

도 4a 내지 도 4c는 도 3a 내지 도 3g의 통신 사이클의 도식에서 호스트(또는 터미널)와 스마트카드 사이의 통신 진행 중에 스마트카드 내의 가비지 콜렉션 처리에 대한 순서도를 나타낸다.

도 4a는 스마트 카드에서 명령처리가 끝나고 가비지 콜렉션 요청이 들어오면(S400), 허용된 남은 시간동안 처리되는 가비지 콜렉션 방법의 흐름을 보여준다.

스마트 카드는 이전에 수행하던 가비지 콜렉션이 있는지를 체크한다(S405). 이전에 수행하던 가비지 콜렉션이 남아있다면 현재로부터 응답 제한 시간까지 남은 가용시간 안에 어느 정도를 수행할 수 있는지를 결정한다(S410). 그리고 이전의 가비지 콜렉션 요청에서 처리못한 부분을 상기 단계에서 측정된 가용시간 내에서 수행한다(S415). 이전의 가비지 콜렉션의 남은 부분을 다 수행하지 못할 경우는 다음 통신 사이클로 넘긴다. 이전의 것을 처리하고 남는 시간이 있다면 새로 요청이 들어온 가비지 콜렉션을 처리한다(S420). 새로 들어온 가비지 콜렉션 요청은 가용시간까지만 처리를 하고 다음 통신 사이클로 남은 처리량을 넘긴다.

도 4b는 스마트 카드의 명령 처리 전에 이전 통신 사이클에서 처리하고 남은 가비지 콜렉션의 수행을 먼저 처리하고 명령 처리를 하는 경우를 보여준다.

스마트 카드는 호스트(또는 터미널)로부터 명령을 전송받는다(S430). 스마트 카드는 명령을 처리하기에 앞서 이전 통신 사이클에서 가비지 콜렉션의 남은 수행부분이 있는지 조사한다(S435). 스마트 카드가 명령 처리에 앞서 어느 정도 양의 가비지 콜렉션 처리를 할 것인지에 관한 것은 남은 가비지 콜렉션의 수행량을 근거로 한다. 정한 시간 내에 이전 가비지 콜렉션 요청에서 남은 부분을 처리한다(S440). 그리고 전송받은 명령을 수행한다(S445)). 명령을 처리한 후 남은 가용 시간을 측정해서 남은 시간으로 수행할 수 있는 가비지 콜렉션의 양을 측정한다(S450). 새로운 가비지 콜렉션의 요구가 있으면 이를 측정된 남은 시간만큼 처리한다(S455). 그리고, 명령 처리에 대한 응답을 보낸다(S460).

도 4c의 경우는 명령 처리의 중간에 이전에 미 처리로 남아있던 가비지 콜렉션의 남은 부분을 명령과 병행하여 처리하는 방법을 도시한 도면이다.

스마트 카드는 호스트(또는 터미널)로부터 명령을 입력받는다(S470). 스마트 카드는 명령의 수행전에 이전 통신 사이클에서 다 처리되지 못한 가비지 콜렉션이 남아 있는지를 조사한다(S472). 가지비 콜렉션이 남아 있다면 소정 시간 동안 이전 가비지 콜렉션 콜에서 처리되지 못한 부분을 처리한다(S474).

스마트 카드는 입력받은 명령을 수행한다(S476). 스마트 카드는 명령 수행 중에 EEPROM의 같은 페이지에 쓰기를 할 부분이 가비지 콜렉션 중에 있다면 같이 쓰기를 하기 위하여 가비지 콜렉션을 처리한다(S478). 그리고 스마트 카드는 입력받은 명령을 수행한다(S480).

명령 수행 후 스마트 카드는 다시 EEPROM의 같은 페이지에 쓰기를 할 부분이 가비지 콜렉션 중에 있는지 조사하여 있다면 가비지 콜렉션을 수행한다(S482). 그리고 스마트 카드는 타이머로 측정된 응답시간 한계까지 남은 시간으로 수행할 수 있는 가비지 콜렉션의 양을 측정한다(S484). 스마트 카드는 측정된 양만큼의 가비지 콜렉션을 처리한다(S486).

스마트 카드는 새로운 가비지 콜렉션 요청이 있을 때는 허용되는 시간까지 새로운 가비지 콜렉션을 수행한다(S488). 그리고 스마트 카드는 명령에 대한 응답을 생성하여 호스트(또는 터미널)로 전송(S490)함으로써 하나의 통신 사이클이 완료된다. 단계 S478, S482는 S480의 명령 처리과정과 병행되는 부분이다. 스마트 카드는 가비지 콜렉션 처리과정 중에 EEPROM에 쓰기를 할 부분을 골라내어 명령과 병렬하여수행을 하고, 단일 처리보다는 병행처리에서 이득을 얻을 수 있는 부분을 포함한 명령이라면 그 부분의 처리시에 가비지 콜렉션을 같이 수행한다.

본 발명은 또한 컴퓨터로 읽을 수 있는 기록매체에 컴퓨터가 읽을 수 있는 코드로서 구현하는 것이 가능하다. 컴퓨터가 읽을 수 있는 기록매체는 컴퓨터 시스템에 의하여 읽혀질 수 있는 데이터가 저장되는 모든 종류의 기록장치를 포함한다. 컴퓨터가 읽을 수 있는 기록매체의 예로는 ROM, RAM, CD-ROM, 자기 테이프, 플로피디스크, 광데이터 저장장치 등이 있으며, 또한 캐리어 웨이브(예를 들어 인터넷을 통한 전송)의 형태로 구현되는 것도 포함한다. 또한 컴퓨터가 읽을 수 있는 기록매체는 네트워크로 연결된 컴퓨터 시스템에 분산되어 분산방식으로 컴퓨터가 읽을 수 있는 코드가 저장되고 실행될 수 있다.

이상의 설명은 바람직한 실시예를 설명한 것에 불과한 것으로서, 본 발명은 상술한 실시예에 한정되지 아니하며 첨부한 특허청구범위 내에서 다양하게 변경 가능하다. 예를 들어 본 발명의 실시예에 구체적으로 나타난 각 구성요소의 형상 및 구조는 변형하여 실시할 수 있다.

본 발명에 따르면, 가비지 콜렉션의 분산 처리를 통하여 보다 효과적으로 메모리를 관리함으로써, 런타임 시에 안정적인 메모리를 확보할 수 있다. 또한 가비지 콜렉션의 로드를 분산 처리하여 응답시간 지연 및 타임아웃에 의한 통신 실패를 방지한다.

도 1a은 스마트카드 및 스마트카드의 통신 방식을 도시한 도면,

도 1b는 스마트 카드의 일종인 Java 스마트 카드의 내부를 도시한 도면,

도 1c는 스마트 카드의 명령 처리과정을 도시한 도면,

도 1d는 사용자의 QoS를 보장하기 위한 시간 한계를 도시한 도면,

도 2a는 호스트(또는 터미널)와 통신하는 스마트 카드의 상태 변화를 도시한 도면,

도 2b는 가비지 콜렉션 처리방법의 일 실시예를 도시한 도면,

도 3a 내지 도 3g는 본 발명에 따른 가비지 콜렉션 방법의 다양한 수행형태를 도시한 도면, 그리고,

Claims

스마트 카드에서의 가비지 콜렉션 방법에 있어서,

메모리에서 제거해야 할 객체 목록을 작성하는 단계;

외부로부터 수신한 명령에 대한 소정의 응답시간까지 남은 시간을 계산하는 단계;

상기 남은 시간 동안 상기 객체 목록에 작성된 객체를 메모리에서 제거하는 단계; 및

상기 남은 시간 동안 제거되지 못한 상기 객체 목록의 리스트를 EEPROM을 포함하는 비휘발성 메모리에 저장하는 단계;를 포함하는 것을 특징으로 하는 가비지 콜렉션 방법.
제 1항에 있어서,

상기 남은 시간 계산 단계는 상기 명령을 전송한 호스트에서 정한 타임아웃 한계시간 또는 사용자가 상기 명령에 대한 응답지연을 느끼지 않응 정도의 QoS를 보장하는 시간까지 남은 시간을 계산하는 단계를 포함하는 것을 특징으로 하는 가비지 콜렉션 방법.
제 1항에 있어서,

상기 객체목록 작성 단계는 가비지 콜렉션이 호출될 때 또는 상기 명령을 수신하기 위한 통신 세션이 초기화 될 때 작성되는 단계를 포함하는 것을 특징으로 하는 가비지 콜렉션 방법.
제 1항에 있어서,

상기 객체목록 작성단계는 이전에 제거되지 못한 객체 목록 리스트가 메모리에 존재하는 경우에 상기 객체 목록 리스트를 새로 작성하는 객체 목록에 추가하는 단계를 포함하는 것을 특징으로 하는 가비지 콜렉션 방법.
제 1항에 있어서,

상기 객체목록 작성단계는 상기 명령의 수행중에 객체를 새로이 생성하거나 제거하는 경우에 상기 객체 목록을 갱신하는 단계를 포함하는 것을 특징으로 하는 가비지 콜렉션 방법.
제 1항에 있어서,

상기 객체 제거 단계는 상기 객체 제거 후에 상기 남은 시간이 있다면 메모리에서 제거해야 할 새로운 객체 목록을 작성하는 단계를 포함하는 것을 특징으로 하는 가비지 콜렉션 방법.
제 1항에 있어서,

상기 객체목록 작성단계 전에, 상기 제거대상 객체에 대한 객체 목록이 메모리에 존재하는 경우에 상기 명령을 수행하기 전에 메모리에서 상기 객체를 제거하는 단계를 더 포함하는 것을 특징으로 하는 가비지 콜렉션 방법.
제 1항에 있어서,

상기 명령이 메모리에의 쓰기 또는 객체 삭제 명령을 포함하면 상기 쓰기 또는 삭제 명령을 수행하기 전에 이미 마련된 메모리에서 제거해야 할 객체 목록이 있으면 상기 객체의 제거를 상기 쓰기 또는 삭제 명령과 병행하여 수행하는 단계를 포함하는 것을 특징으로 하는 가비지 콜렉션 방법.
제 1항에 있어서,

상기 객체 제거 단계는 상기 제거 대상 객체들이 연속하여 메모리에 존재하는 경우에 상기 연속하여 존재하는 객체들을 동시에 제거하고, 메모리에 객체를 할당가능한 공간과 상기 제거 대상 객체의 메모리 공간이 연속공간 또는 동일공간이 되는 경우에 상기 할당과 제거과정을 동시에 수행하는 것을 특징으로 하는 가비지 콜렉션 방법.
스마트 카드에서 가비지 콜렉션을 수행하는 장치에 있어서,

외부로부터 수신한 명령에 대한 소정의 응답시간까지 남은 시간을 계산하는 타이머; 및

메모리에서 제거해야 할 객체 목록을 작성한 후 상기 남은 시간 동안 상기 객체 목록에 작성된 객체를 메모리에서 제거하고 상기 남은 시간 동안 제거되지 못한 상기 객체 목록의 리스트를 EEPROM을 포함하는 비휘발성 메모리에 저장하는 메모리 관리부;를 포함하는 것을 특징으로 하는 가비지 콜렉션 장치.
제 10항에 있어서,

상기 메모리 관리부는 상기 제거대상 객체에 대한 객체 목록이 메모리에 존재하는 경우에 상기 명령을 수행하기 전에 메모리에서 상기 객체를 제거하는 것을 특징으로 하는 가비지 콜렉션 장치.
제 10항에 있어서,

상기 메모리 관리부는 상기 명령이 메모리에의 쓰기 또는 삭제 명령을 포함하면 상기 쓰기 또는 삭제 명령을 수행하기 전에 이미 마련된 메모리에서 제거해야할 객체 목록이 있으면 상기 객체의 제거를 상기 쓰기 또는 삭제 명령과 병행하여 수행하는 것을 특징으로 하는 가비지 콜렉션 장치.
제 1항의 가비지 콜렉션 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체.