정확한 포인터 식별을 위한 프로세서 아키텍처 document_id A220623041324

동적으로 생성된 메모리 영역의 자동 해제에 대한 다양한 알고리즘이 있는데, 이들은 참조 카운팅, 복사 및 마크 스위프 콜렉션의 개념하에서 본 분야의 숙련자들에게는 알려져 있다. 이들 알고리즘의 개략에 대해서, R. Jones, R. Lins: "Garbage Collection: Algorithm For Automatic Dynamic Memory Management", John Wiley 0026# Sons, 1996을 참조한다. 이들 알고리즘의 간단한 구현은 가비지 콜렉션 사이클의 전체 기간 동안 애플리케이션 프로그램을 인터럽트한다. 이들은 전형적으로 프로그램 실행시에 길고 예측할 수 없는 포즈(pause)를 야기하고, 따라서 인터랙티브 시스템 또는 실시간 환경에 대해서 적절하지 않다. 증분 및 동시 방법은 가비지 콜렉션 사이클 동안 프로그램 실행이 지속되게 한다. 그러나, 이들은 애플리케이션 프로그램과 가비지 콜렉터 간의 동기화를 요구한다. 관련된 객체가 가비지 콜렉터에 의해 이미 처리되었는지를 결정하기 위해서는, 이러한 소프트웨어 내에서의 동기화는 중요하나, 그 이유는 사용된 방법에 따라, 짧은 코드 시퀀스가 각 포인터 로드(판독 배리어) 전에 또는 각 포인터 저장(기입 배리어) 전에 채택되어야 하기 때문이다. 많은 증분 방법은 "실시간 가능(real-time capable)"으로서 기술되는데, 그 이유는 가비지 콜렉터에 의해 생긴 포즈가 사용자에 의해 등록될 대부분의 경우에 너무 짧기 때문이다. 그러나, 하드 실시간 가능성(hard real-time capability)은 시스템의 응답 시간에 대한 일정한 상한 한계치의 보장을 요구한다. 소프트웨어-근거 방법들이 전체 객체의 프로세싱 또는 루트 세트(레지스터 및 스택)의 모든 포인터들의 심사와 같은 논-인터럽트가능(non-interruptible) 동작에 전형적으로 좌우되기 때문에, 이들 방법은 하드 실시간 필요 조건을 충족시키지 못한다. 무제한 기간의 분할 불가능 동작 없이 가능한 소프트웨어 솔루션이 알려져 있지만, 계산 시간 및 메모리 내에서의 이들 솔루션의 오버헤드는 중요하다. 자동 가비지 콜렉션에 대한 모든 기술의 기본적인 문제점은 포인터를 찾고 식별하는 것이다. 포인터가 논-포인터로부터 분명하게 구별화될 수 없다면, 보수적인 가비지 콜렉션이 수행될 수 있다. 이것이 의미하는 것은 포인터를 표현할 수 있는 모든 비트 패턴이 계속 사용중인 메모리의 해제를 방지하기 위해서 포인터로서도 보여질 수 있어야 한다는 것이다. 따라서, 객체 및 업데이트 포인터를 이동시키는 비압축 방법(no compacting methods)은 보수적인 가비지 콜렉션에 사용될 수 있다. 그러나, 메모리는 압축 방법없이 분해된다. 이들 방법을 방지하고 정확한 가비지 콜렉션을 수행하기 위해서, 더 큰 비용이 포인터를 탐색하고 식별하는데 사용된다. 많은 객체-지향 언어에서, 포인터 및 객체는 모든 객체 내에 포함되는 타입 디스크립터(type descriptor)를 통해 식별될 수 있다. 프로그램 스택 및 프로세스 레지스터 내에서의 포인터의 국부화는 좀 더 어려우나, 특히 컴파일러의 최적화와 관련하여 어렵다. 현재 포인터를 포함하는 프로세서 레지스터 및 스택 포지션이 상세된 데이터 구조를 유지하는 것이 가능하나, 프로그램 실행중에 이러한 타입의 데이터 구조를 구현하기 위한 비용은 매우 높다. 이러한 이유로, 대부분의 소프트웨어 근거 방법은 프로그램 스택 및 레지스터 내의 포인터의 포지션을 기술하는 컴파일러에 의해 생성된 테이블을 사용한다. 가비지 콜렉션이 수행될 수 있는 모든 프로그램 포인트에 있어서, 이러한 타입의 테이블 세트가 준비된다. 이러한 기술의 구현은 그러나, 프로그램 코드의 중대한 인플레이션을 야기한다. 더구나, 실시간 시스템은 중지될 스레드(thread)가 제한된 시간 범위 내에 이러한 타입의 다음 프로그램 포인트에 도달하는 것을 보장해야 한다. 따라서, 다양한 문제점은 소프트웨어 내에 자동 가비지 콜렉션을 주로 사용하는 현행 시스템을 사용하여 극복되어야 한다. 이는 무엇보다도 소프트웨어가 하위 하드웨어가 제공하지 못하는 기능들을 시물레이션하여야 하기 때문이다. 효율성 및 실시간 가능성과 관련된 많은 문제점들은 프로세서 자체가 하드웨어 내에서 자동 가비지 콜렉션을 전체적으로 또는 부분적으로 수행하는 경우에 극복될 수 있다. 그러나, 프로세서가 이러한 목적을 위해 포인터를 식별할 수 있는 것이 절대적으로 필요하다. 다음에, 다양한 공지된 아키텍처 중에서, 2개만이 예시적 목적으로 기술되는데, 이는 정확한 포인터 식별 및/또는 자동 가비지 콜렉션을 지지하고, 본 발명의 주 과제가 중요하다. 따라서, 메모리 영역을 어드레스하기 위해서 직접 포인터 대신에 가능성을 이용하는 아키텍처가 1966년 이래로 공지되어 있다. 가능성은 객체의 액세스 인가 및 식별에 대한 스테이트먼트를 포함한다. 이들은 객체의 물리적 어드레스를 포함하지 않지만, 오히려 객체의 위치, 사이즈 및 속성을 기술하는 디스크립터에 대한 참조를 포함한다. 이러한 타입의 아키텍처를 포함하는 프로세서의 예는 예를 들어, H. M. Levy: "Capability-Based Computer Systems", Digital Press, 1984, 159-186 페이지에 기술된 Intel iAPX 432이다. 이러한 아키텍처에서, 가능성은 2-스테이지 맵핑 프로세스를 통해 관련 객체와 관련된다. 객체 테이블 내의 고유 엔트리가 모든 객체마다 존재하는데, 이는 객체의 위치, 사이즈 및 상태를 기술한다. 모든 객체는 2개의 영역: 데이터 영역 및 가능성에 대한 영역을 포함한다. 정확한 가능성 식별은 이러한 방식으로 가능하게 된다. iAPX 432는 가능성 및 객체 디스크립터를 통해 객체의 2중 간접 어드레싱 및 레지스터 세트의 부족으로 인해 매우 비효율적이다. 더구나, 자동 가비지 콜렉션 자체를 수행하지는 못한다. 가비지 콜렉션은 소프트웨어 내에서 수행되어야 하고, 실시간으로 가능하지는 못한다. 직접 포인터를 식별하기 위한 모든 공지된 방법은 포인터와 논-포인터 간의 구별을 위해 모든 메모리 워드 내의 특별한 식별 비트 (태그; tag)를 사용한다. 이러한 예는 US 5,560,003A 내에 기술된 실시간의 증분 가비지 콜렉션을 위한 시스템 및 하드웨어 모듈인데, 이는 가비지 콜렉션을 수행하는 로컬 프로세서 및 2개의 메모리 뱅크들로 이루어진다. 모든 메모리 뱅크는 각 메모리 액세스 시에 대응하는 객체의 스타트 어드레스에 어드레스들을 맵핑하는 객체 공간 매니저에 의해 지지된다. 그 복잡성 때문에, 이러한 객체 공간 매니저는 메모리 자체로서 유사한 칩 영역을 점유하는 개별 ASIC로서 구현되어야 한다. 이러한 타입의 시스템은 매우 비싸다. 더구나, 식별 비트의 도움으로 포인터의 식별은 필요한 메모리 및 계산 시간의 형태로 추가 비용을 야기한다. 임베디드 시스템 내의 소프트웨어의 복잡성의 계속적인 증가 때문에, 이러한 경제적으로 중요한 분야에 대해 액세스가능한 자동 가비지 콜렉션의 장점을 또한 만들기 위해서 매우 큰 노력이 수년간 취해졌다. 가장 큰 피스 카운트는 현대 정보 기술의 이 영역에서 정확하게 얻어진다. 제조 사이클이 계속적인 혁신을 통해 점점 짧아지기 때문에, 현대 객체 지향 언어를 위한 임베디드 시스템을 위한 로버스트 및 실시간 가능 플랫폼을 위한 요구가 계속해서 증가한다. 그러나, 이들 애플리케이션에 있어서, 자동 가비지 콜렉션은 대부분의 경우에 사치를 계속 고려해야 하는데, 이는 자동 가비지 콜렉션의 확실한 장점에도 불구하고 제공될 수 없다. 이러한 관련 기술로부터 진행하여, 본 발명의 목적은 객체 근거 및 객체 지향 프로그램을 위한 프로세서 아키텍처를 특정하는 것인데, 이는 비용 효율적이고 정확한 포인터 식별을 허용하고 따라서 하드웨어 내에서 전체적으로 또는 부분적으로 구현될 수 있는 효율적이고 실시간 가능한 자동 가비지 콜렉션을 위한 경로를 개방한다.