[go: up one dir, main page]

KR20060135697A - 멀티-프로세서 시스템에서의 자원 관리 - Google Patents

멀티-프로세서 시스템에서의 자원 관리 Download PDF

Info

Publication number
KR20060135697A
KR20060135697A KR1020067013774A KR20067013774A KR20060135697A KR 20060135697 A KR20060135697 A KR 20060135697A KR 1020067013774 A KR1020067013774 A KR 1020067013774A KR 20067013774 A KR20067013774 A KR 20067013774A KR 20060135697 A KR20060135697 A KR 20060135697A
Authority
KR
South Korea
Prior art keywords
task
tasks
memory
data
processors
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.)
Withdrawn
Application number
KR1020067013774A
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 KR20060135697A publication Critical patent/KR20060135697A/ko
Withdrawn legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR 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/48—Program initiating; Program switching, e.g. by interrupt
    • G06F9/4806—Task transfer initiation or dispatching
    • G06F9/4843—Task transfer initiation or dispatching by program, e.g. task dispatcher, supervisor, operating system
    • G06F9/4881—Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR 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
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR 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/48—Program initiating; Program switching, e.g. by interrupt
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR 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/50—Allocation of resources, e.g. of the central processing unit [CPU]
    • G06F9/5005—Allocation of resources, e.g. of the central processing unit [CPU] to service a request
    • G06F9/5011—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resources being hardware resources other than CPUs, Servers and Terminals
    • G06F9/5016—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resources being hardware resources other than CPUs, Servers and Terminals the resource being the memory
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2209/00—Indexing scheme relating to G06F9/00
    • G06F2209/48—Indexing scheme relating to G06F9/48
    • G06F2209/485—Resource constraint

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Multi Processors (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

메인 메모리 요건들에 기초하여 태스크 선점 포인트들(task preemption points)을 선택하기 위해 멀티-프로세서 데이터 처리 시스템의 스케줄러에 의해 사용되는 방법 및 장치가 제공된다. 프로세서들에 태스크들을 할당하는 것에 따라서 3가지 대안적인 바람직한 실시예들이 존재하고, 이 실시예들은: (1)고정 할당: 매 태스크가 특정 프로세서에 할당, 즉 각각의 태스크는 주어진 프로세서상에서 배타적으로 실행된다. 이 실시예는 프로세서들이 전용될 때, 즉 각각의 프로세서가 그 밖의 모든 프로세서와 실질적으로 상이한 곳에서 바람직하다; (2)가변 할당: 매 프로세서상에서 매 태스크가 실행될 수 있다. 실행 시간에서, 스케줄러는 어느 프로세서가 어느 태스크를 실행할지를 결정한다. 태스크는 하나의 프로세서상에서 실행되면서 선점(preempt)되고 나서 또 다른 프로세서상에서 계속된다. 이 실시예는 모든 프로세서들이 동일할 때 바람직하다; 및 (3)혼합 할당: 매 태스크가 프로세서들의 서브셋에 할당된다. 이는 프로세서들의 세트가 프로세서들이 동일하게 되는 서브셋들로 분할될 때 자연적인 방법이다.
태스크 선점 포인트, 프로세서, 스케줄러, 데이터 처리 시스템, 메모리

Description

멀티-프로세서 시스템에서의 자원 관리{Resource management in a multi-processor system}
본 발명은 배타적인 것은 아니지만 특히 멀티-프로세서 실시간 시스템들의 자원 관리에 적합한 자원 관리 방법 및 장치에 관한 것이다.
필요로 되는 실리콘 량의 관점에서, 다른 프로세싱 코어를 부가하는 것은 더 이상 문제가 되지 않기 때문에, 시스템즈-온-실리콘(systems-on-silicon; SoS) 또는 시스템즈-온-칩 (systems-on-chip; SoC)에 대해, 메모리는 주요 제한 팩터가 되고 있다. 결국, SoS 또는 SoC는 다수의 프로세서 코어들을 포함할 수 있다.
메모리 관리는 멀티-프로세서 시스템을 위한 자원 관리의 중요한 양상이다. 특시 실시간 시스템들에서 메인 메모리의 관리를 위해 선점 포인트들(preemption points)을 사용하는 것을 포함하여, 단일 프로세서 시스템들에 대해 메모리 사용을 최적화하는 각종 방법들이 개발되어 왔다. 이들 방법들에서, 태스크들을 실행하는 동안 임의의 순간들에서 태스크들을 선점하는 것이 아니라, 이들 태스크들은 자신들의 메모리 사용에 기초하여 전용의 선점 포인트들에서만 선점되는 것이 바람직하다.
전형적인 종래 기술의 방법에서, 태스크의 중단(suspension)을 태스크 선점 또는 태스크의 선점이라 칭하고, 용어 "태스크(task)"는 메모리, CPU, I/O 장치들 등과 같은 시스템 자원들을 위해 독립적으로 경쟁할 수 있는 실행 유닛을 가리키는데 사용된다. 설명을 위해, 태스크는 일련의 연속적으로 실행되는 작업들(jobs)로 추정되며, 이들 작업들 각각은 하나 이상의 서브-작업들을 포함한다. 예를 들어, 태스크는 "비디오 스트림을 디멀티플렉싱(demultiplexing a video stream)하는 것"을 포함할 수 있고, 인입 스트림들을 판독-입력하고, 스트림들을 처리하고, 대응하는 데이터를 출력하는 것을 포함할 수 있다. 이들 단계들은 각 인입 데이터 스트림에 대해 실행되어, 단일 스트림에 대한 판독, 처리 및 출력이 하나의 작업을 수행하는 것에 대응하도록 하며, 각 작업은 3개의 서브-작업들을 갖는다. 따라서, 판독-입력되고 처리될 다수의 데이터 패킷들이 존재할 때, 작업은 이에 대응하여 다수회 수행된다. 서브-작업은 작업의 기능적인 구성요소에 관계하는 것으로 간주될 수 있고, 멀티-프로세서 시스템에서 각 스트림은 여러 프로세서들 또는 프로세서들의 서브셋에 할당된다.
데이터 처리 시스템에서 다수의 태스크들을 스케줄링하는 알려진 방법은 태스크의 각 서브-작업이 메모리 사용[4][5]에 기초하여 프로세싱 선점 포인트들 및 이에 대응하는 서브-작업의 중단을 위한 조건들을 지정하는 중단 데이터라 칭하는 중단 기준들의 세트를 갖는 것을 필요로 한다. 따라서, 데이터 처리 시스템에 의해 사용되는 메모리 량은 작업의 실행시 이들 선점 포인트들에서 필요로 되는 메모리 량을 지정하는 이들 선점 포인트들을 통해 이 중단 데이터에 의해 간접적으로 제어된다.
따라서, 이들 선점 포인트들은 메모리 부족으로 인한 데이터 처리 시스템 충돌들을 피하도록 하기 위해 사용될 수 있다. 실시간 태스크가 다수의 서브-작업들을 포함하는 것으로서 특징지워질 때, 이 태스크의 선점 포인트들은 태스크의 서브-작업 경계들과 일치하는 것이 바람직하다.
태스크의 각 서브-작업과 관련되는 중단 데이터에 일치하는 태스크의 메모리 사용을 나타내는 데이터는 예를 들어, 디스케줄링 이벤트를 요청하는 코드 라인을 통해 태스크에 임베드되어, 태스크의 처리시에 선점 포인트에 도달, 즉 서브-작업 경계에 도달된다라고 지정한다. 즉, 태스크의 서브-작업들의 시작 포인트들의 세트는 이 태스크의 선점 포인트들의 세트를 구성한다. 태스크 τi의 j번째 선점 포인트 Pi,j는 선점 포인트 자체와 관련된 정보 및 j번째 선점 포인트와 다음 선점 포인트, 즉 j+1번째 선점 포인트 사이의 연속 선점될 수 없는 서브-작업 간격 Ii,j에 관련된 정보에 의해 특징 지워진다.
실행 시간에서, 태스크는 제어 운영 시스템에 태스크가 선점 포인트들에 도달할 때, 예를 들어, 태스크가 서브-작업들을 시작할 때를 통지하며, 서브-작업들간을 스위치하고 서브-작업을 완료하고, 운영 시스템은 태스크 실행이 선점되는 때 및 장소를 결정한다. 이상적으로, 선점은 태스크의 실행 동안 선점 포인트 또는 이외 다른 임의의 포인트에서 발생될 수 있다. 그러나, 선점 선택의 이와 같은 유연성은 일관성(consistency)를 희생함으로, 선점은 일관성을 유지하기 위해 선점 포인트들로 제한된다.
시스템의 일관성을 위험하게 하지 않는 메인 메모리 요건들에 기초하는 종래 기술의 선점 포인트 방식은 서브-작업 경계 내에 있도록 자원의 배타적인 사용을 제어하는 정합 동기화 프리미티브들(matching synchronization primitives) 및 선점 포인트들로 모든 태스크들의 선점을 반드시 제한한다. 알려진 바와 같이, 구성요소(예를 들어, 하나 이상의 태스크들을 포함할 수 있는 소프트웨어 컴포넌트)는 이 구성요소가 [6]을 지정하는 특성들, 기능들, 또는 방법들 및 이벤트들을 포함하는 프로그램가능한 인터페이스를 가질 수 있다. 설명을 위해, 태스크는 도 1에 도시된 바와 같이 태스크에 요구되는 메인 메모리 데이터 MPi,J(101b)를 최소로 포함하는 인터페이스(100)와 함께 수반된다라고 추정된다.
설명을 위해, 태스크는 주기적이고 실시간이라고 추정되고, 주기 T 및 페이싱 F에 의해 특징 지워지고, 여기서 0<=F<T이며, 이는 태스크가 서브-작업들의 시퀀스를 포함하며, 이들 태스크 각각은 시간 F+nT에서 릴리스되며, 여기서 n=0... N이다. 단지 일예로서 그리고 도 2에 도시된 바와 같이, 셋-톱 박스(200)는 3가지 태스크, 즉 (1) 사용자 인터페이스(205) 상에 메뉴를 디스플레이, (2) 내용 프로바이더(203)로부터 텍스트 정보 검색 및 (3) 일부 비디오 신호들 처리를 실행하는 것으로 추정되며, 이들 3가지 태스크들 각각은 다수의 서브-작업들을 포함하는 것으로 추정된다. 프리젠테이션을 용이하게 하기 위해, 서브-작업들은 순차적으로 실행되는 것으로 추정된다.
이들 서브-작업들의 적어도 일부는 선점될 수 있고 선점될 수 있는 이들 서 브-작업들 사이의 경계들은 선점 포인트들을 제공하고 표 1에 요약되어 있다.
태스크 τi 태스크 설명 태스크 τi m(i)의 서브-작업들을 선점할 수 있는 수
τ1 GUI 상에 메뉴 디스플레이 3
τ2 내용 프로바이더로부터 텍스트 정보 검색 2
τ3 비디오 신호들 처리 2
표 1
또한 도 3을 참조하면, 각 태스크에 대해, 중단 데이터(101)는, 선점 포인트에서 요구되는 메모리 MPi,j(302)의 최대 량과 같은 선점 포인트 Pi,j(301)에 관계하는 정보 및 최악의 경우 내부-선점 포인트 간격에서 요구되는 메모리 MIi,j(304)의 량과 같은 연속적인 선점 포인트들 사이의 간격 Ii,j(303)에 관한 정보를 포함한다(i는 태스크 τi를 표시하고 j는 선점 포인트를 표시한다).
특히, 중단 데이터(101)는 다음을 지정하는 데이터를 포함한다.
1. 태스크 τi(Pi,j)(101a)의 선점 포인트 j;
2. 태스크의 선점 포인트 j에서 태스크 τi의 최대 메모리 요건들 MPi,j(101b), 여기서 1≤j≤m(i);
3. 태스크 τi의 서브-작업에 대응하는 연속적인 선점 포인트들 j와 j+1 사이의 간격 Ii,j(101c), 여기서 1≤j≤m(i); 및
4. 태스크의 간격 j에서 태스크 τi의 최대(최악의 경우에) 메모리 요건들 MIi,j(101d), 여기서 1≤j≤m(i);
표 2는 현재 예에 대한 중단 데이터(101)를 도시한다(현재 예에서, 제 1 태스크 τ1에 대응하는 중단 데이터(101)는 표 2의 제 1 행에서 데이터를 포함하고, 제 2 태스크 τ2에 대응하는 중단 데이터(101)는 표 2의 제 2 행을 포함하도록, 각 태스크는 자체 인터페이스를 갖는다).
Figure 112006048881313-PCT00001
표 2
셋-톱 박스(200)에는 메모리의 1.5 Mbytes가 제공된다라고 가정하자. 정규 또는 비메모리-기반 선점 조건들 하에서, 셋-톱 박스(200)는 다음과 같이 작용한다.
이제 도 4a를 참조하면, 프로세서(401)는 어떤 종류의 타임 슬라이싱 또는 우선순위-기반 선점에 따라서 태스크들을 스케줄할 것으로 예상될 수 있으며, 모두 3가지 태스크들을 동시에, 즉 효율적으로 동시에 실행된다는 것을 의미한다. 그러므로, 각 태스크는 스케줄링되어 동시에 자신의 대부분의 메모리 집중 서브-작업을 실행할 수 있다. 이들 3가지 태스크들 MP의 최악의 경우 메모리 요건은 다음과 같이 제공된다.
Figure 112006048881313-PCT00002
(식 1)
태스크들 τ1, τ2 및 τ3에 대해, MP는 τi의 최대 메모리 요건들 MI1,1 더하기 태스크(τ2)의 최대 메모리 요건들 MI2,2 더하기 태스크(τ3)의 최대 메모리 요건들 MI3,2이다. 이들 최대 요건들은 표 2 엔트리들에 볼드체로 표시된다.
Figure 112006048881313-PCT00003
이는 셋-톱 박스(200)에 이용가능한 메모리를 0.2Mbytes만큼 초과되어, 어떠한 예방 조치들의 부재시 이들 서브-작업들이 동시에 처리되는 경우, 셋-톱 박스(200)는 충돌하게 된다.
이제 도 5를 참조하면, 태스크들은 스케줄링 알고리즘에 따라서 스케줄링되고, 데이터 구조는 생성된 후에 각 태스크(τi)에 대해 유지된다라고 가정하고, 자원의 배타적인 사용을 위해 프리미티브들의 정합 쌍들은 서브-작업 경계에 걸쳐있지 않다라고 가정하자. 또한, 스케줄러(501)는 임의의 시점에서 현재 실행하는 태스크가 시스템 내의 모든 준비-대-실행 태스크들 중에서 반드시 최고 우선순위를 갖는 태스크가 되도록 하는 종래의 우선순위-기반 선점 스케줄링 알고리즘을 사용한다라고 가정하자. 알려진 바와 같이, 스케줄링 작용은 실행중이거나 준비-대-실행 태스크들을 위한 선점을 선택적으로 인에이블 및 디스에이블함으로써 수정될 수 있다.
태스크 관리기(503)는 새롭게 수신된 태스크에 대응하는 중단 데이터(101)를 수신하고 선점이 필요로 되는지 여부를 평가하고, 필요로 되는 경우, 이 새롭게 수신된 정보를 스케줄러(501)로 통과시켜, 선점을 요청한다. 태스크들의 상세사항들이 표 2에 지정된다라고 가정하고, 태스크 τ1(및 단지 τ1 만이)이 현재 처리되고 스케줄러가 메모리-기반 제약들이 존재하지 않는 모드로 초기에 동작한다라고 추정하자.
이제, 인터페이스 Int2(100)로부터 중단 데이터(101)를 판독하고 스케줄러(501)가 메모리-기반 선점에 따라서 수행중인지를 식별하는 태스크 관리기(503)에 의해 태스크 τ2가 수신된다라고 가정하자. 이 예에서, 그렇지 않기 때문에, 태스크 관리기(503)는 스케줄러(501)가 메모리-기반 선점으로 변경할 필요가 있는지를 평가한다. 그러므로, 이는 중단 데이터 저장장치(505)로부터 모든 현재 실행하는 태스크들(이 예에서 태스크 τ1)에 대응하는 최악의 경우의 중단 데이터를 검색하는 태스크 관리기(503)를 포함하여, (식 1)을 평가하고 이 평가된 최악의 경우의 메모리 요건들을 이용가능한 메모리 자원들과 비교한다. τ1, τ2에 대해 표 2, (식 1)에 소개된 예로 계속되면 다음과 같이 된다.
Figure 112006048881313-PCT00004
이는 이용가능한 메모리보다 적게 되어, 스케줄러(501)의 동작 모드를 메모리-기반 선점으로 변경할 필요가 없게 된다(즉, 메모리 사용에 기초하여 스케줄러를 제약할 필요가 없다). 따라서, 스케줄러(501)가 - 예를 들어, 2가지 태스크들이 동시에 메모리에 효율적으로 상주한다는 것을 의미하는 태스크 τ2의 실행 시간 제약들을 충족하기 위해- 태스크 τ1과 태스크 τ2 사이에서 스위칭하면, 프로세서는 이용될 수 있는 것 이상으로 메모리에 결코 액세스하지 못한다.
다음으로, 태스크들 τ1 및 τ2가 완료되기 전, 또 다른 태스크 τ3가 수신된다. 태스크 관리기(503)는 태스크 τ3과 관련된 인터페이스 Int3로부터 중단 데이터(101)를 판독하여, 스케줄러(501)가 메모리-기반 선점으로 변경할 필요가 있는지를 평가한다. 스케줄러(501)가 멀티-태스킹 태스크들 τ1 및 τ2라고 가정하면, 모든 3가지 태스크들에 대한 최악의 경우의 메모리 요건들은 지금부터 다음과 같이 된다.
Figure 112006048881313-PCT00005
이는 이용가능한 메모리를 초과하여, 태스크 관리기(503)가 중단 데이터 저장장치(505)로부터 모두 3개의 태스크들에 대해 메모리 사용 데이터 MPi,j 및 MIi,j(101b, 101d)를 요청하고 검색하고, 검색된 메모리 사용 데이터에 기초하여, 모두 3가지 태스크들을 실행하기 위해 충분한 메모리 자원들이 존재하는지를 평가한다. 이는 다음 식의 평가를 통해 확인될 수 있다.
Figure 112006048881313-PCT00006
(식 2)
이 메모리 요건은 이용가능한 메모리보다 적음으로, 태스크들이 자신들의 메모리 사용에 기초하여 선점된다라고 하면, 모두 3개의 태스크들은 동시에 실행된다는 것을 의미한다.
따라서, 태스크 관리기(503)는 태스크들에게 자신들의 지정된 선점 포인트들 MPi,j에서 스케줄러(501)에 디스케줄 명령들을 전송하도록 지시함으로써 "메모리-기반 선점 모드(memory-based preemption mode)"를 기동시킨다. 이 모드에서, 스케줄러(501)는 임의의 시점에서 한번에 기꺼해야 하나의 태스크가 자신의 선점 포인트들 중 하나의 선점 포인트 이외의 포인트에 있을 수 있다라는 제약을 가진채 각 태스크가 하나의 선점 포인트로부터 다음 선점 포인트로 비선점적으로 실행되도록 한다. 새롭게 도달된 태스크가 선점 포인트에서 시작한다라고 가정하면, 스케줄러(501)는 이 조건이 현재 실행중인 태스크들에 유지되도록 함으로써, 하나의 태스크를 제외한 모든 태스크가 선점 포인트에 있도록 제약한다.
따라서, 알려진 메모리-기반 선점 모드에서, 스케줄러(501)는 (메모리-기반 선점 포인트들에서 태스크로부터의 디스케줄 요청에 응답하여) 단지 자신들의 선점 포인트들에서 태스크들을 선점하도록 허용된다.
태스크들 중 하나의 태스크가 종료될 때, 이 종료하는 태스크는 태스크 관리기(503)에 태스크가 종료되었다는 것을 통지하여, 태스크 관리기(503)가 (식 1)을 평가하도록 하고 최악의 경우에 메모리 사용(이 작의 제거 고려)이 스케줄러(501)에 이용할 수 있는 것보다 낮게 되면, 이 태스크 관리기(503)는 시스템이 외부 이 벤트들에 더욱 빠르게 반응하도록 하는 이점을 갖는 메모리-기반 선점을 취소할 수 있다(그 이유는 프로세서가 서브-작업들의 지속기간 동안 더이상 "차단되지(blocked)"않기 때문이다). 일반적으로, 태스크의 종료는 전형적으로 자신의 환경, 예를 들어, 사용자에 의한 채널 스위치 또는 적용된 엔코딩의 데이터 스트림에서 변화 (또 다른 종류의 디코딩 필요)에 의해 초래되며, 이는 태스크 관리기(503) 및/또는 스케줄러(501)가 태스크의 종료를 인지해야 하고 아마도 심지어는 태스크를 종료하도록 지시한다는 것을 의미한다.
기동될 때, 메모리-기반 선점 제약들은 의무적이라는 점에 주목해야 한다.
태스크들은 소프트웨어 태스크들로서 설명되었지만, 태스크는 또한 하드웨어로 구현될 수 있다. 전형적으로, 하드웨어 장치(하드웨어 태스크으로서 작용)는 소프트웨어 태스크에 의해 제어되며, 이는 (최악의 경우) 하드웨어 장치에 의해 요구되는 메모리를 할당하고 나서 하드웨어 태스크를 실행하도록 지시한다. 하드웨어 태스크가 완료될 때, 이는 소프트웨어 태스크에 통지하고, 그 후, 이 소프트웨어 태스크는 메모리를 할당해제한다. 그럼으로, 소프트웨어 태스크를 제어함으로써, 하드웨어 태스크들은 상술된 바와 같이 간단히 취급될 수 있다.
이 방법은 단일 프로세서 시스템에 적용되고 멀티-프로세서 시스템에 최적화되지 않음으로, 멀티-프로세서 최적화가 필요로 된다.
본 발명은 멀티-프로세서 시스템들을 위한 상술된 메모리-기반 자원 관리에 대한 단일 프로세서 방식의 최적화를 제공한다. 태스크들 τi(1≤i≤n)의 세트 Γ 및 프로세서 πk(1≤k≤p)의 세트 P를 고려하고(여기서, n은 전형적으로 p보다 휠씬 크다), 비제약된 모드를 위한 고정-우선순위 선점 스케줄링(fixed-priority preemptive scheduling; FPPS) 방식 및 메모리-기반 선점 모드를 위한 고정-우선순위 방식과 함께 지연된 선점(fixed-priority scheduling scheme with deferred preemption; FPDP) 방식을 추정하자.
프로세서들에 태스크들을 할당하는 것에 따른 3가지 대안적인 바람직한 실시예들이 존재한다.
1. 고정 할당: 매 태스크 τi가 특정 프로세서 πk에 할당되고, 즉 태스크 τi는 프로세서 πk 상에서 배타적으로 실행될 것이다. 이 실시예는 프로세서들이 전용될 때, 즉 각 프로세서가 근본적으로 그 밖의 모든 프로세서와 근본적으로 다른 곳에서 바람직하다.
2. 가변 할당: 매 프로세서 πk 상에서 매 태스크 τi이 실행될 수 있다. 실행 시간에서, 스케줄러는 어느 프로세서가 어느 태스크를 실행할 지를 결정한다. 태스크는 하나의 프로세서상에서 실행되면서 선점되고 나서 또 다른 프로세서상에서 계속된다. 이 실시예는 모든 프로세서들이 동일할 때 바람직하다;
3 혼합 할당: 매 태스크 τi가 프로세서들의 서브셋에 할당된다. 이는 프로세서들의 세트가 프로세서들이 동일하게 되는 서브셋들로 분할될 때 자연적인 방법이다.
본 발명의 상술된 특징들 및 장점들과 그외 다른 특징들 및 장점들이 도면 전반에 걸쳐서 동일한 부품들에 동일한 참조 번호가 병기된 첨부 도면에 도시된 바람직한 실시예들에 대한 이하의 더욱 상세한 설명으로부터 명백하게 될 것이다.
도 1은 본 발명의 실시예를 따른 태스크 인터페이스의 구성요소들의 개요도.
도 2는 본 발명의 실시예가 동작되는 디지털 텔레비전 시스템의 예를 도시한 개요도.
도 3은 단일 프로세서를 위한 도 1에 도시된 태스크 인터페이스의 구성요소들 사이의 관계들의 개요도.
도 4a는 단일 프로세서 시스템을 위한 도 2의 셋-톱 박스를 구성하는 구성요소들을 도시한 도면.
도 4b는 멀티-프로세서 시스템을 위한 도 2의 셋-톱 박스를 구성하는 구성요소들을 도시한 도면.
도 5는 도 2 및 도 4a에 도시된 셋-톱 박스의 프로세서의 구성요소들을 도시한 도면.
당업자는 이하의 설명들이 예시를 위한 것이지 제한하고자 하는 것이 아니라는 것을 이해해야 한다. 당업자는 본 발명의 원리 내에 있고 첨부된 청구범위의 범위 내에서 많은 변형들이 존재한다는 것을 알 수 있다. 알려진 기능들 및 동작들의 불필요한 상세 설명은 본 발명을 모호하게 하는 것을 피하기 위해 본 상세한 설명으로부터 생략될 수 있다.
디지털 TV 세트들, 디지털적으로 개선된 아날로그 TV 세트들 및 셋톱 박스들(STB들)과 같은 고 볼륨 전자(HVE) 소비자 시스템들은 비용 효율적이고 신뢰성을 유지하면서 실시간 서비스들을 제공해야 한다. 소비자 제품들은 자신들의 특성상 상당히 자원 제약적이다. 결국, 이용가능한 자원들은 신뢰성과 같은 HVE 소비자 시스템들의 전형적인 품질들을 유지하고 엄격한 타이밍 요건들에 부합하면서 매우 효율적으로 사용되어야 한다. 신뢰성과 관련하여, 예를 들어, TV 세트가 "시스템을 재부팅하여 주십시오(please reboot the system)"와 같은 메시지로 TV 세트가 고장을 일으키는 것을 어떤 누구도 기대하지 않는다.
HVE 소비자 시스템들에서 매체 처리의 중요한 부품들은 데이터의 다수의 동시 스트림들을 취급하고 특히 멀티-태스킹 환경에서 메인 메모리와 같은 시스템 자원들을 매우 효율적으로 관리해야 하는 탑재된 소프트웨어로 구현된다. 실시간 자원 관리를 필요로 하는 HVE 소비자 시스템의 예로서 셋-톱 박스를 고려하자. 종래에, 도 2에 도시된 바와 같이, 셋-톱 박스(200)는 내용 프로바이더(203)(서버 또는 케이블) 및 사용자 인터페이스(205)로부터 텔레비전(201)용 입력을 수신한다. 사용자 인터페이스(205)는 사용자 제어되는 원격 장치(202), 예를 들어, 휴대용 적외선 원격 송신기로부터 신호들을 수신하는 원격 제어 인터페이스를 포함한다. 셋-톱 박스(200)는 안테나 및 케이블 텔레비전 출구 중 적어도 하나로부터 적어도 하나의 데이터 스트림을 수신하고 데이터 스트림을 처리하거나 데이터 스트림을 텔레비 전(201)으로 전달하는 것 중 적어도 하나를 수행한다. 사용자는 텔레비전(201)상에 디스플레이되는 적어도 하나의 데이터 스트림을 시청하고 사용자 인터페이스(205)를 통해 디스플레이되는 것에 기초하여 선택들을 행한다. 셋-톱 박스(200)는 사용자 선택 입력을 처리하고, 이 입력에 기초하여 셋-톱 박스(200) 및 이의 성능을 식별하는 다른 정보와 함께 내용 제공자(203)에게 사용자 입력을 전송할 수 있다.
도 4b는 태스크들을 프로세서들(460.1 내지 460.3)에 할당하고 셋-톱 박스(200)의 전체 동작을 제어하는 제어 및 할당 논리 모듈에 의해 관리되는 다수의 프로세서들(460.1 내지 460.3)을 포함할 수 있는 전형적인 셋-톱 박스(200)의 전형적인 시스템(450)의 간단화된 블록도를 도시한다. 제어 및 할당 논리 모듈(451)은 네트워크(407)로부터 그리고 저장장치(406)로부터 풋 데이터(put data)를 수신하는 데이터 수신기(452), 메모리 사용을 평가하는 평가기(453), 태스크들을 프로세서들에 할당하는 할당기(454), 태스크들의 실행을 개시 및 종료하기 위해 태스크들을 선택하는 선택기(455) 및 실행을 위한 태스크들을 스케줄링하고 실행되는 태스크들을 디스케줄링하는 스케줄러(501)를 포함한다. 제어 및 할당 논리 모듈(451)은 텔레비전 튜너(403), 메모리(405), 장기간 저장 장치(406), 통신 인터페이스(407) 및 원격 인터페이스(409)에 결합된다. 텔레비전 튜너(403)는 전송 라인(411)을 통해 텔레비전 신호들을 수신하고 이들 신호들은 안테나(도시되지 않음) 및 케이블 텔레비전 출구(도시되지 않음) 중 적어도 하나로부터 발신될 수 있다. 제어 및 할당 논리 모듈(451)은 사용자 인터페이스(205)를 관리하여, 데이터, 오디오 및 비디오 출력을 라인(413)을 통해 텔레비전(201)에 제공한다. 원격 인터페이스(409)는 무선 커넥션(415)을 통해 원격 제어로부터 신호들을 수신한다. 통신 인터페이스(407)는 데이터 경로(417)를 통해 웹 서버와 같은 적어도 하나의 원격 처리 시스템 및 셋-톱 박스(200) 사이에서 인터페이스 한다. 통신 인터페이스(417)는 전화 모뎀, 종합 정보 통신망(ISDN) 어댑터, 디지털 가입자 라인(xDSL), 케이블 텔레비전 모뎀 및 임의의 다른 적절한 데이터 통신 장치 중 적어도 하나이다. 도 4b의 전형적인 시스템(450)은 단지 설명을 위한 것이다. 이 설명이 통상적으로 특정 셋-톱 박스들(200)을 설명하기 위해 사용되는 용어들에 관한 것일 수 있지만, 이 설명 및 개념들은 마찬가지로 도 4b에 도시된 아키텍쳐들과 다른 아키텍쳐들을 갖는 시스템들을 포함하여 다른 제어 프로세서들에 적용된다.
바람직한 실시예에서 제어 및 할당 논리 모듈(451)은 셋-톱 박스(200)의 제어에 관한 다수의 실시간 태스크들을 메모리(405)를 공유하는 다수의 멀티-프로세서들(460.1 내지 460.3)에 할당하도록 구성된다. 이들 실시간 태스크들은 변경 채널들, 사용자 인터페이스(205) 상에 디스플레이되는 메뉴 옵션의 선택, 인입 데이터 스트림들을 디코딩, 장기간 저장 장치(406)를 이용하여 인입 데이터 스트림들을 기록, 및 이들을 재생 등을 포함한다. 셋-톱 박스의 동작은 셋-톱 박스(100)의 특성들에 기초하는 이들 실시간 제어 태스크들, 라인(411)을 통한 인입 비디오 신호들, 사용자 인터페이스(205)를 통한 사용자 입력들 및 이외 다른 어떤 보조 입력에 의해 결정된다.
바람직한 실시예에서, 멀티-프로세서들은 메모리(405)를 공유한다. 이들 멀티-프로세서들(460.1 내지 460.3) 각각은 CPU들 또는 코-프로세서들 또는 이외 다 른 프로세싱 장치들일 수 있다. 바람직한 실시예에서, 동일한 태스크는 결코 2개(또는 그 이상) 프로세서들에 의해 동시에 실행되지 않는다. 바람직한 실시예에서, 제어 및 할당 논리 모듈은 프로세서들(460.1 내지 460.3)의 전체 세트를 위한 단일 태스크-관리기를 포함한다. 집중된 방식은 단지 설명을 위한 것이다. 본 발명은 이 집중된 방식으로 제한되지 않고, 분산된 방식도 당업자가 손쉽게 이해할 수 있을 것이다.
매 태스크 τ가 특정 프로세서 π에 할당될 때마다, 태스크들의 세트 Γ는 p개의 디스조인트 세트들 Γ1-Γp로 분할될 수 있고, 여기서 서브셋 Γk은 프로세서 πk에 할당된다. 프로세서 πk에 의해 실행되는 바와 같은 FPPS 하에서 태스크들 Γk의 서브셋에 의해 필요로 되는 최대 메모리 량은 (식 1)의 변형인 (식 1s')에 의해 제공된다. (식 1s')에서 항 nk은 프로세서 πk에 할당되는 태스크들의 수(즉, 서브셋 Γk의 기수)를 나타내고, 변수 i는 Γk의 태스크들에 걸친 범위로 추정된다.
Figure 112006048881313-PCT00007
(식 1s')
태스크들의 전체 세트 Γ의 총 메모리 요건들 MP은 태스크들의 각 서브셋에 대해 구해진 결과들을 가산함으로써 결정된다. (식 1mfix)를 참조하라.
Figure 112006048881313-PCT00008
(식 1mfix)
MP가 이용가능한 메모리 Msys를 초과하지 않을 때, 임의의 프로세서들상의 태스크들의 스케줄링을 제약할 필요가 없다. MP가 Msys를 초과할 때, 하나 이상의 프로세서들상의 하나 이상의 태스크들의 스케줄링을 제약할 수 있다. 단일 프로세서 상의 모든 태스크들의 스케줄링을 제약하는 영향은 (식 2s)의 변형인 (식 2s')를 이용하여 결정될 수 있다.
Figure 112006048881313-PCT00009
(식 2s')
모든 프로세서들상의 모든 태스크들의 스케줄링을 제약하는 영향은 (식 2mfix)에 의해 결정될 수 있고, 총 메모리 요건들 MD는 각 세트 Γk의 메모리 요건들
Figure 112006048881313-PCT00010
의 합이다.
Figure 112006048881313-PCT00011
(식 2mfix)
명백히, 프로세서들의 서브셋 상에서만 모든 태스크드를 제약하고 프로세서들의 서브셋 상의 태스크들의 서브셋만을 제약하는 것과 같은 많은 매개적인 대안 실시예들이 존재한다.
대안적으로, 매 태스크는 매 프로세서(460.1 내지 460.3) 상에서 실행될 수 있고 태스크들의 스케줄링은 제어 및 할당 논리 모듈(451)에 의해 수행된다. 제약되지 않은 모드를 위한 최대 메모리 요건들 MP는 동일한 채로 유지되고, 즉 (식 1s) 를 이용하여 결정될 수 있다.
Figure 112006048881313-PCT00012
(식 1s)
p개의 태스크들이 현재 p개의 프로세서들 상에서 병렬로 실행될 수 있기 때문에, 제약된 모드(즉, 모든 태스크들은 단지 자신들의 선점 포인트들에서 선점된다)는 (식 2s)의 변형을 필요로 한다.
Figure 112006048881313-PCT00013
(식 2s)
총 메모리 요건들 MD은 현재 (식 2mvar)에 의해 제공된다.
Figure 112006048881313-PCT00014
(식 2mvar)
(식 2mvar)가 n≥p라고 추정하고 (식 2mvar)가 또한 n≥p에 대해 유효하다라는 점에 주목하자. 특수한 경우 n<p, 이 식은 다음과 같이 간단화될 수 있다.
Figure 112006048881313-PCT00015
명백히, 태스크들의 서브셋만을 제약하는 것과 같은 많은 매개적인 실시예들이 존재한다.
예로서, 2개의 프로세서들(즉, p=2) 및 3개의 태스크들(즉, n=3)인 경우를 고려하자. 태스크들이 상기 표 1과 2 및 이들과 관련한 설명에 서술된 바와 동일한 특성들(즉, 메모리 요건들)을 갖는다라고 추정하자. 제약되지 않는 모드를 위한 최 대 메모리 요건들 MP은 동일한 채로 유지되고, 즉 (식 1)을 이용하여 결정될 수 있음으로 이용가능한 메모리 Msys를 초과한다. (식 2mvar)를 이용하면, 메모리-기반 선점을 위한 최대 메모리 요건들 MD는 다음과 같다.
Figure 112006048881313-PCT00016
메모리 요건은 이용가능한 메모리보다 적은데, 이는 태스크들이 자신들의 선점 포인트들에서만 선점된다면, 모두 3개의 태스크들은 동시에 실행될 수 있다는 것을 의미한다.
프로세서들의 s개의 페어-와이즈 디스조인트 서브셋들(pair-wise disjoint subsets) P1,...Ps이 존재한다라고 추정하자. 매 태스크가 프로세서들의 특정 서브셋 Pl에 할당된다라고 하자(여기서 1≤l≤s). 그러므로, 태스크들의 세트는 태스크들의 s개의 페어-와이즈 디스조인트 서브셋들 Γ1,...,ΓS에서 분할될 수 있다. 프리젠테이션을 용이하게 하기 위해, 서브셋들 Γ1의 태스크들은 τi로 표시되고(여기서 1≤i≤nl), 즉 태스크들의 서브셋 당 태스크들이 번호가 매겨진다. 상술된 가변 할당과 유사하게, 비-제약된 모드를 위한 서브셋 Pl을 위한 최대 메모리 요건들
Figure 112006048881313-PCT00017
은 (식 1s")을 이용하여 결정될 수 있다.
프로세서 πk의 서브셋 Pl에 의해 실행되는 비제약된 모드에서 태스크들 Γl의 서브셋에 의해 필요로 되는 최대 메모리 량은 (식 1)의 변형인 (식 1s")에 의해 제공된다.
Figure 112006048881313-PCT00018
(식 1s")
(식 1s")가 (식 1s')와 유사하지만 동일하지 않지 않다는 점에 유의하라. 1은 전자의 식에서 프로세서들의 서브셋의 범위에 걸쳐 있으며, k는 후자의 식에서 서브셋 내의 프로세서 범위에 걸쳐 있다. 프로세서들의 모든 s개의 서브셋 총 메모리 요건들 MP은 개별적인 서브셋들을 위한 요건들의 합을 취함으로써 구해질 수 있다.
Figure 112006048881313-PCT00019
(식 1mmix)
MP가 Msys를 초과할 때, 스케줄링은 프로세서들의 자신들과 관련된 서브셋들에 대해 실행되는 태스크들의 하나 이상의 서브셋들 중 하나 이상의 서브셋들로 제약된다. p1 프로세서들의 단일 서브셋 Pl상의 Γ1의 모든 nl 태스크들의 스케줄링을 제약하는 영향은 (식 2mvar)와 유사한 식 (2mmix)를 이용하여 결정될 수 있다.
Figure 112006048881313-PCT00020
(식 2mmix)
(식 2mvar)와 유사하게, (식 2mmix)만이 nl≥pl에 대해서만 유지된다.
매 프로세서들의 서브셋 상에서 매 태스크들의 서브셋의 모든 태스크들의 스케줄링을 제약하는 영향은 (식 2mmix ' )에 의해 결정될 수 있으며, 총 메모리 요건들 MD은 프로세서 P1의 각 서브셋의 메모리 요건들
Figure 112006048881313-PCT00021
의 합이다.
Figure 112006048881313-PCT00022
(식 2mmix ' )
상술된 고정 할당 및 가변 할당 경우들에 대한 것처럼, 혼합 할당에 대해, 모든 태스크들이 단지 자신들의 선점 포인트들에서 선점되는 메모리-기반 선점 모드 및 비제약된 모드 사이에 많은 매개적인 해법들이 존재한다.
본 발명의 바람직한 실시예들이 도시되고 설명되었지만, 당업자는 각종 변경들 및 수정들이 행해질 수 있고 등가물들이 본 발명의 범위를 벗어남이 없이 이들 소자들에 대해 대체될 수 있다는 것을 이해할 것이다. 게다가, 많은 수정들은 본 발명의 중심 범위를 벗어남이 없이 특정 상황에 본 발명의 개시내용을 적응시키도로 행해질 수 있다. 그러므로, 본 발명을 실행하기 위해 고려되는 최적의 모드로 설명된 특정 실시예들로 본 발명이 제한되는 것이 아니라 본 발명의 모든 실시예들은 첨부된 청구범위 내에 있는 것으로 간주되어야 한다.

Claims (26)

  1. 다수의 프로세서들을 갖는 데이터 처리 시스템에서 다수의 태스크들을 스케줄링하는 방법에 있어서,
    상기 다수의 태스크들 각각에 대해, 사용된 메모리에 기초하여 상기 태스크의 중단(suspension)을 지정하는 중단 데이터를 제공하는 단계; 및
    상기 다수의 태스크들 각각을 상기 다수의 프로세서들 중 하나의 프로세서에 할당하는 단계를 포함하며,
    각각의 프로세서는:
    (i) 상기 프로세서에 할당된 태스크들 중 하나의 태스크를 처리하는 단계;
    (ii) 상기 태스크와 연관된 중단 데이터를 정합시키는 상기 태스크에 의해 사용된 메모리를 나타내는 입력에 대해 모니터링하는 단계;
    (iii) 상기 모니터링된 입력에 기초하여 상기 태스크를 중단하는 단계; 및
    (iv) 상기 프로세서에 할당된 상기 태스크들 중 다른 하나의 태스크를 처리하는 단계를 포함하는, 태스크 스케줄링 방법.
  2. 제 1 항에 있어서,
    프로세서에 태스크를 할당하는 단계는,
    a. 특정 프로세서에 할당된 매 태스크를 갖는 고정 할당;
    b. 매 프로세서에 할당된 매 태스크를 갖는 가변 할당; 및
    c. 상기 다수의 프로세서들의 서브셋에 할당된 매 태스크를 갖는 혼합 할당 중 하나의 할당에 기초하는, 태스크 스케줄링 방법.
  3. 제 2 항에 있어서, 상기 입력은 중단 요청을 나타내는 데이터를 포함하는, 태스크 스케줄링 방법.
  4. 제 3 항에 있어서,
    상기 다수의 태스크들과 연관된 최대 메모리 사용을 식별하는 제 1 데이터를 수신하는 단계;
    상기 다수의 태스크들을 처리하기 위해 이용될 수 있는 메모리를 식별하는 제 2 데이터를 수신하는 단계; 및
    상기 태스크들을 처리하기 위해 이용될 수 있는 충분한 메모리가 존재하는지를 상기 제 1 및 제 2 데이터에 기초하여 식별하는 단계를 더 포함하며,
    상기 모니터링 및 중단 단계들은 불충분한 메모리 식별에 응답하여서만 수행되는, 태스크 스케줄링 방법.
  5. 제 4 항에 있어서,
    태스크들의 종료를 모니터링하는 단계; 및
    태스크 종료에 응답하여, 태스크 종료에 응답하여 메모리의 가용성을 식별하는 상기 단계를 반복하는 단계를 더 포함하는, 태스크 스케줄링 방법.
  6. 제 5 항에 있어서, 나머지 태스크들을 실행하기 위한 충분한 메모리 식별에 응답하여, 상기 모니터링 단계는 불필요한 것으로 간주되는, 태스크 스케줄링 방법.
  7. 제 6 항에 있어서,
    상기 다수의 태스크들과 연관된 최대 메모리 사용을 식별하는 제 1 데이터를 수신하는 단계;
    상기 다수의 태스크들을 처리하기 위해 이용될 수 있는 메모리를 식별하는 제 2 데이터를 수신하는 단계; 및
    상기 태스크들을 처리하기 위해 이용될 수 있는 충분한 메모리가 존재하는지를 상기 제 1 및 제 2 데이터에 기초하여 식별하는 단계를 포함하며,
    상기 모니터링 및 중단 단계들은 불충분한 메모리 식별에 응답하여서만 수행되는, 태스크 스케줄링 방법.
  8. 제 7 항에 있어서,
    태스크들의 종료를 모니터링하는 단계; 및
    태스크 종료에 응답하여, 태스크 종료에 응답하여 메모리의 가용성을 식별하는 상기 단계를 반복하는 단계를 더 포함하는, 태스크 스케줄링 방법.
  9. 제 8 항에 있어서, 나머지 태스크들을 실행하기 위한 충분한 메모리 식별에 응답하여, 상기 모니터링 단계는 불필요한 것으로 간주되는, 태스크 스케줄링 방법.
  10. 제 2 항에 있어서,
    상기 다수의 태스크들과 연관된 최대 메모리 사용을 식별하는 제 1 데이터를 수신하는 단계;
    상기 다수의 태스크들을 처리하기 위해 이용될 수 있는 메모리를 식별하는 제 2 데이터를 수신하는 단계; 및
    상기 태스크들을 처리하기 위해 이용될 수 있는 충분한 메모리가 존재하는지를 상기 제 1 및 제 2 데이터에 기초하여 식별하는 단계를 더 포함하며,
    상기 모니터링 및 중단 단계들은 불충분한 메모리 식별에 응답하여서만 수행되는, 태스크 스케줄링 방법.
  11. 제 10 항에 있어서,
    태스크들의 종료를 모니터링하는 단계; 및
    태스크 종료에 응답하여, 태스크 종료에 응답하여 메모리의 가용성을 식별하는 상기 단계를 반복하는 단계를 더 포함하는, 태스크 스케줄링 방법.
  12. 제 11 항에 있어서, 나머지 태스크들을 실행하기 위한 충분한 메모리 식별에 응답하여, 상기 모니터링 단계는 불필요한 것으로 간주되는, 태스크 스케줄링 방법.
  13. 다수의 프로세서들을 갖는 데이터 처리 시스템에서 다수의 태스크들을 스케줄링하는 방법에 있어서,
    상기 다수의 태스크들 각각에 대해, 사용된 메모리에 기초하여 상기 태스크의 중단을 지정하는 중단 데이터를 제공하는 단계; 및
    특정 프로세서에 할당된 매 태스크를 갖는 고정 할당, 매 프로세서에 할당된 매 태스크를 갖는 가변 할당, 및 상기 다수의 프로세서들의 서브셋에 할당된 매 태스크를 갖는 혼합 할당 중 하나의 할당에 기초하여 상기 다수의 태스크들 각각을 상기 다수의 프로세서들 중 하나의 프로세서에 할당하는 단계를 포함하며,
    각각의 프로세서는:
    (i) 상기 프로세서에 할당된 태스크들 중 하나의 태스크를 처리하는 단계;
    (ii) 상기 태스크와 연관된 중단 데이터를 정합시키는 상기 태스크에 의해 사용된 메모리를 나타내는 입력에 대해 모니터링하는 단계;
    (iii) 상기 모니터링된 입력에 기초하여 상기 태스크를 중단하는 단계; 및
    (iv) 상기 프로세서에 할당된 상기 태스크들 중 다른 하나의 태스크를 처리하는 단계를 포함하는, 태스크 스케줄링 방법.
  14. 다수의 프로세서들을 갖는 데이터 처리 시스템에서 사용하기 위한 스케줄러 로서, 상기 데이터 처리 시스템은 상기 다수의 프로세서들 상에서 다수의 태스크들을 실행하도록 배열되고 상기 태스크들을 실행하는데 사용하기 위한 지정된 메모리 량에 액세스하는, 상기 스케줄러에 있어서,
    태스크와 연관된 최대 메모리 사용을 식별하는 데이터를 수신하도록 배열된 데이터 수신기;
    상기 수신된 데이터에 기초하여, 상기 태스크들을 실행하기 위한 충분한 메모리가 존재하는지를 식별하도록 배열된 평가기;
    a. 특정 프로세서에 할당된 매 태스크를 갖는 고정 할당, b. 매 프로세서에 할당된 매 태스크를 갖는 가변 할당, 및 c. 상기 다수의 프로세서들의 서브셋에 할당된 매 태스크를 갖는 혼합 할당 중 하나의 할당에 기초하여 상기 다수의 태스크들 각각을 상기 다수의 프로세서들 중 하나의 프로세서에 할당하는 할당기;
    상기 태스크의 실행동안 중단을 위한 적어도 하나의 태스크를 선택하도록 배열된 선택기로서, 상기 중단은 상기 태스크에 의해 지정된 메모리 사용과 일치하는, 상기 선택기; 및
    상기 할당된 태스크의 실행을 초기화하고 상기 선택된 태스크를 중단하도록 배열된 스케줄러(501)를 포함하며,
    상기 다수의 태스크들을 실행하기 위한 불충분한 메모리가 존재한다라고 식별하는 상기 평가기에 응답하여, 상기 선택기는 지정된 메모리 사용 및 상기 데이터 처리 시스템에 이용가능한 지정된 메모리 량에 기초하여 중단을 위한 적어도 하나의 태스크를 선택하고, 상기 스케줄러는 상기 지정된 메모리를 이용하는 상기 태 스크에 응답하여 적어도 하나의 선택된 태스크의 실행을 중단하는, 스케줄러.
  15. 제 14 항에 있어서, 상기 평가기는, 태스크들의 종료를 모니터링하고, 태스크 종료에 응답하여, 나머지 태스크들을 실행하기 위한 충분한 메모리가 존재하는지를 식별하도록 배열되는, 스케줄러.
  16. 제 15 항에 있어서, 상기 나머지 태스크들을 실행하기 위한 충분한 메모리를 식별하는 상기 평가기에 응답하여, 상기 선택기는 상기 선택된 적어도 하나의 태스크를 선택해제하도록 배열되는, 스케줄러.
  17. 다수의 태스크들을 실행하도록 배열된 다수의 프로세서들을 갖는 데이터 처리 시스템에 있어서,
    태스크의 실행동안 명령들 및 데이터를 유지하도록 배열된 메모리;
    태스크와 연관된 최대 메모리 사용을 식별하는 데이터 및 상기 태스크의 선점성(preemptability)을 지정하는 데이터를 수신하도록 배열된 수신 수단;
    상기 수신된 데이터에 기초하여, 상기 태스크들을 실행하기 위한 충분한 메모리가 존재하는지를 식별하도록 배열된 평가 수단;
    특정 프로세서에 할당된 매 태스크를 갖는 고정 할당, 매 프로세서에 할당된 매 태스크를 갖는 가변 할당, 및 상기 다수의 프로세서들의 서브셋에 할당된 매 태스크를 갖는 혼합 할당 중 하나의 할당에 기초하여 상기 다수의 태스크들 각각을 상기 다수의 프로세서들 중 하나의 프로세서에 할당하도록 배열된 할당기; 및
    상기 평가 수단으로부터 수신된 입력에 기초하여 상기 태스크들의 실행을 스케줄링하도록 배열된 스케줄러를 포함하며,
    상기 다수의 태스크들을 실행하기 위한 불충분한 메모리의 식별에 응답하여, 상기 스케줄러는 상기 태스크에 의한 메모리 사용에 따라서 적어도 하나의 태스크의 실행을 중단하도록 배열되는, 데이터 처리 시스템.
  18. 다수의 프로세서들을 갖는 데이터 처리 시스템에 데이터를 전송하는 방법에 있어서,
    특정 프로세서에 할당된 매 태스크를 갖는 고정 할당, 매 프로세서에 할당된 매 태스크를 갖는 가변 할당, 및 상기 다수의 프로세서들의 서브셋에 할당된 매 태스크를 갖는 혼합 할당 중 하나의 할당에 기초하여 다수의 태스크들 중 각 태스크를 상기 다수의 프로세서들 중 하나의 프로세서에 할당하는 단계;
    상기 다수의 태스크들 중 각 태스크를 처리시 상기 데이터 처리 시스템에 의한 사용을 위해 데이터를 전송하는 단계; 및
    처리 동안의 메모리 사용에 기초하여 상기 다수의 태스크들 중 각 태스크의 중단을 지정하는 중단 데이터를 전송하는 단계를 포함하며,
    상기 데이터 처리 시스템은:
    상기 태스크와 연관된 중단 데이터를 정합시키는 각 태스크의 메모리 사용을 나타내는 입력에 대해 모니터링하는 단계; 및
    상기 모니터링된 입력에 기초하여 상기 각 태스크의 처리를 중단(suspending)하는 단계를 포함하는 프로세스를 수행하도록 구성되는, 데이터 전송 방법.
  19. 제 18 항에 있어서, 상기 중단 데이터는 상기 각 태스크와 연관된 최대 메모리 사용을 식별하는 데이터를 포함하는, 데이터 전송 방법.
  20. 제 18 항에 있어서, 상기 중단 데이터는 상기 각 태스크의 메모리 사용에 기초하여 각 태스크의 처리가 중단되는 적어도 한 포인트를 식별하는, 데이터 전송 방법.
  21. 제 20 항에 있어서, 상기 각 태스크는 다수의 서브-작업들을 포함하고, 상기 각 태스크의 처리가 중단될 수 있는 적어도 한 포인트를 식별하는 상기 데이터는 상기 각 서브-작업에 대응하는, 데이터 전송 방법.
  22. 제 20 항에 있어서, 상기 중단 데이터는 상기 각 태스크와 연관된 최대 메모리 사용을 식별하는 데이터를 포함하는, 데이터 전송 방법.
  23. 제 22 항에 있어서, 상기 각 태스크는 다수의 서브-작업들을 포함하고, 상기 각 태스크의 처리가 중단될 수 있는 적어도 한 포인트를 식별하는 상기 데이터는 상기 각 서브-작업에 대응하는, 데이터 전송 방법.
  24. 다수의 프로세서들을 갖는 데이터 처리 시스템에서 사용하기 위한 다수의 태스크들을 구성하는 방법으로서, 상기 방법은 상기 태스크와 중단 데이터를 연관시키는 단계를 포함하며, 상기 중단 데이터는 이와 연관된 메모리 사용에 기초하여 상기 태스크의 중단을 지정하며, 상기 데이터 처리 시스템은 다수의 프로세서들 상에서 실행하는 다수의 태스크들에 대한 프로세스를 수행하도록 배열되는, 상기 태스크 구성 방법에 있어서,
    상기 프로세스는:
    특정 프로세서에 할당된 매 태스크를 갖는 고정 할당, 매 프로세서에 할당된 매 태스크를 갖는 가변 할당, 및 상기 다수의 프로세서들의 서브셋에 할당된 매 태스크를 갖는 혼합 할당 중 하나의 할당에 기초하여 상기 다수의 태스크들 중 각 태스크를 상기 다수의 프로세서들 중 하나의 프로세서에 할당하는 단계;
    상기 태스크와 연관된 중단 데이터를 정합시키는 상기 태스크의 메모리 사용을 나타내는 입력에 대해 모니터링하는 단계; 및
    상기 모니터링된 입력에 기초하여 상기 태스크의 처리를 중단하는 단계를 포함하는, 태스크 구성 방법.
  25. 처리 시스템이 제 1 항에 따른 상기 방법을 수행하도록 배열된 명령들의 세트를 포함하는 컴퓨터 프로그램.
  26. 처리 시스템이 제 2 항에 따른 방법을 수행하도록 배열된 명령들의 세트를 포함하는 컴퓨터 프로그램.
KR1020067013774A 2004-01-08 2005-01-05 멀티-프로세서 시스템에서의 자원 관리 Withdrawn KR20060135697A (ko)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US53511304P 2004-01-08 2004-01-08
US60/535,113 2004-01-08

Publications (1)

Publication Number Publication Date
KR20060135697A true KR20060135697A (ko) 2006-12-29

Family

ID=34794342

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020067013774A Withdrawn KR20060135697A (ko) 2004-01-08 2005-01-05 멀티-프로세서 시스템에서의 자원 관리

Country Status (6)

Country Link
US (1) US20070124733A1 (ko)
EP (1) EP1706820A2 (ko)
JP (1) JP2007519103A (ko)
KR (1) KR20060135697A (ko)
CN (1) CN1910553A (ko)
WO (1) WO2005069155A2 (ko)

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100788328B1 (ko) * 2006-09-08 2007-12-27 (주)내셔널그리드 그리드 컴퓨팅을 이용한 미들웨어 시스템 및 그 동작 방법
KR20140109940A (ko) * 2012-01-09 2014-09-16 마이크로소프트 코포레이션 Paas 계층적 스케일링 및 자동 스케일링 기법
KR20140137582A (ko) * 2013-05-23 2014-12-03 한국전자통신연구원 스트림 처리 태스크 관리 장치 및 방법
US11194604B2 (en) 2012-01-09 2021-12-07 Microsoft Technology Licensing, Llc Assignment of resources in virtual machine pools

Families Citing this family (31)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7606236B2 (en) * 2004-05-21 2009-10-20 Intel Corporation Forwarding information base lookup method
JP4969791B2 (ja) * 2005-03-30 2012-07-04 株式会社日立製作所 ディスクアレイ装置およびその制御方法
US8281313B1 (en) * 2005-09-29 2012-10-02 Hewlett-Packard Development Company, L.P. Scheduling computer processing jobs that have stages and precedence constraints among the stages
US20070156879A1 (en) * 2006-01-03 2007-07-05 Klein Steven E Considering remote end point performance to select a remote end point to use to transmit a task
US8411734B2 (en) * 2007-02-06 2013-04-02 Microsoft Corporation Scalable multi-thread video decoding
US9648325B2 (en) 2007-06-30 2017-05-09 Microsoft Technology Licensing, Llc Video decoding implementations for a graphics processing unit
US8086455B2 (en) * 2008-01-09 2011-12-27 Microsoft Corporation Model development authoring, generation and execution based on data and processor dependencies
CN101694631B (zh) * 2009-09-30 2016-10-05 曙光信息产业(北京)有限公司 实时作业调度系统及方法
JP5336331B2 (ja) * 2009-11-24 2013-11-06 株式会社デンソー 車載装置
CN101867833A (zh) * 2010-06-12 2010-10-20 北京东方艾迪普科技发展有限公司 一种视频图像格式转换方法和装置
EP2591416A4 (en) 2010-07-05 2014-08-13 Saab Ab METHOD FOR CONFIGURING A DISTRIBUTED CONTROL SYSTEM FOR AEROSPACE TECHNOLOGY
JP2012079272A (ja) 2010-10-06 2012-04-19 Sony Corp 録画再生装置、ｉ／ｏスケジューリング方法、及びプログラム
CN102467373A (zh) * 2010-10-28 2012-05-23 微软公司 任务取消宽限期
US9706214B2 (en) 2010-12-24 2017-07-11 Microsoft Technology Licensing, Llc Image and video decoding implementations
KR20120077265A (ko) * 2010-12-30 2012-07-10 주식회사 팬택 이동 단말기 및 이동 단말기의 제어 방법
US8731067B2 (en) 2011-08-31 2014-05-20 Microsoft Corporation Memory management for video decoding
US9819949B2 (en) 2011-12-16 2017-11-14 Microsoft Technology Licensing, Llc Hardware-accelerated decoding of scalable video bitstreams
CN103294554A (zh) * 2012-03-05 2013-09-11 中兴通讯股份有限公司 片上系统soc的多处理器的调度方法及装置
CN102662740B (zh) * 2012-03-29 2014-12-10 迈普通信技术股份有限公司 非对称多核系统及其实现方法
US10255558B1 (en) * 2012-09-27 2019-04-09 EMC IP Holding Company LLC Managing knowledge-based authentication systems
GB2507038A (en) 2012-10-16 2014-04-23 Ibm Scheduling jobs weighted according to the memory usage using a knapsack problem.
CN102929723B (zh) * 2012-11-06 2015-07-08 无锡江南计算技术研究所 基于异构众核处理器的并行程序段划分方法
US10058777B2 (en) 2013-11-21 2018-08-28 Tencent Technology (Shenzhen) Company Limited Task execution method, apparatus and system
CN104657203B (zh) * 2013-11-21 2018-07-20 腾讯科技（深圳）有限公司 任务执行方法、装置和系统
US9727371B2 (en) 2013-11-22 2017-08-08 Decooda International, Inc. Emotion processing systems and methods
GB2521151B (en) * 2013-12-10 2021-06-02 Advanced Risc Mach Ltd Configurable thread ordering for a data processing apparatus
GB2521155B (en) 2013-12-10 2021-06-02 Advanced Risc Mach Ltd Configuring thread scheduling on a multi-threaded data processing apparatus
CN106598717B (zh) * 2016-12-07 2019-06-11 陕西尚品信息科技有限公司 一种基于时间片段的任务调度方法
CN109471705B (zh) * 2017-09-08 2021-08-13 杭州海康威视数字技术股份有限公司 任务调度的方法、设备及系统、计算机设备
CN113821311A (zh) * 2020-06-19 2021-12-21 华为技术有限公司 任务执行方法及存储设备
CN112685158B (zh) * 2020-12-29 2023-08-04 杭州海康威视数字技术股份有限公司 一种任务调度方法、装置、电子设备及存储介质

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5826082A (en) * 1996-07-01 1998-10-20 Sun Microsystems, Inc. Method for reserving resources
WO2004090720A2 (en) * 2003-04-14 2004-10-21 Koninklijke Philips Electronics N.V. Method and apparatus for task scheduling based on memory requirements

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100788328B1 (ko) * 2006-09-08 2007-12-27 (주)내셔널그리드 그리드 컴퓨팅을 이용한 미들웨어 시스템 및 그 동작 방법
KR20140109940A (ko) * 2012-01-09 2014-09-16 마이크로소프트 코포레이션 Paas 계층적 스케일링 및 자동 스케일링 기법
US11194604B2 (en) 2012-01-09 2021-12-07 Microsoft Technology Licensing, Llc Assignment of resources in virtual machine pools
KR20140137582A (ko) * 2013-05-23 2014-12-03 한국전자통신연구원 스트림 처리 태스크 관리 장치 및 방법

Also Published As

Publication number Publication date
US20070124733A1 (en) 2007-05-31
WO2005069155A3 (en) 2006-06-22
CN1910553A (zh) 2007-02-07
JP2007519103A (ja) 2007-07-12
WO2005069155A2 (en) 2005-07-28
EP1706820A2 (en) 2006-10-04

Similar Documents

Publication Publication Date Title
KR20060135697A (ko) 멀티-프로세서 시스템에서의 자원 관리
KR100628492B1 (ko) 실시간 동작 수행방법 및 시스템
US20060212869A1 (en) Resource management method and apparatus
KR100649107B1 (ko) 실시간 동작 수행방법 및 시스템
US9176774B2 (en) Workflow control of reservations and regular jobs using a flexible job scheduler
US6272517B1 (en) Method and apparatus for sharing a time quantum
US6212562B1 (en) Criticality and quality of service (QoS) based resource management
KR101953906B1 (ko) 태스크 스케줄링 방법 및 장치
KR20050016170A (ko) 실시간 동작 수행방법 및 시스템
US20070016907A1 (en) Method, system and computer program for automatic provisioning of resources to scheduled jobs
JP2009541848A (ja) コンピュータマイクロジョブを中断せずに実行するようスケジュールするための方法、システムおよび装置
JPH10283211A (ja) マルチシステム環境のプロセッサ・リソース管理方法
US20060288397A1 (en) Stream controller
JP2010044784A (ja) システムにおける要求のスケジューリング
US20070022423A1 (en) Enhanced method for handling preemption points
CN111190719B (zh) 优化集群资源分配的方法、装置、介质及电子设备
JP2000056992A (ja) タスクスケジューリングシステム、方法及び記録媒体
RU2450330C2 (ru) Аппаратно-реализуемый способ выполнения программ
JP2904483B2 (ja) 周期的プロセスのスケジューリング方法
Zhang et al. Scheduling best-effort and real-time pipelined applications on time-shared clusters
KR20010103719A (ko) 운영 체계 스케쥴링 동작을 제공하는 방법 및 장치
CN119440750A (zh) 接口通信方法、装置、系统、存储介质及电子设备
CN117609014A (zh) 图形处理器的调试装置和计算机设备
CN117056010A (zh) 一种跨云平台任务调度方法和装置
CN119172448A (zh) 对多通道数据编码进行调度的方法及装置、多核编码系统

Legal Events

Date Code Title Description
PA0105 International application

Patent event date: 20060707

Patent event code: PA01051R01D

Comment text: International Patent Application

PG1501 Laying open of application
PC1203 Withdrawal of no request for examination
WITN Application deemed withdrawn, e.g. because no request for examination was filed or no examination fee was paid