개인구독
소속 기관이 없으신 경우, 개인 정기구독을 하시면 저렴하게
논문을 무제한 열람 이용할 수 있어요.
지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 저널정보
- Korean Institute of Information Scientists and Engineers Journal of Computing Science and Engineering Journal of Computing Science and Engineering Vol.14 No.3
- 발행연도
- 2020.9
- 수록면
- 121 - 130 (10page)
- DOI
- 10.5626/JCSE.2020.14.3.121
이용수
초록· 키워드
오류제보하기
The problem of scheduling a set of periodic tasks on a uniform multiprocessor system is considered in the present study. Each processor in a uniform multiprocessor system is characterized by its speed or computation capacity, i.e., execution of a job on a processor with speed s for t time units completes s × t units of execution. In the commonly-known partitioned scheduling, each task is assigned to a processor and all of its jobs are required to be executed on that processor. However, partitioning of periodic tasks requires solving the bin-packing problem, which is known to be intractable (NPhard in the strong sense). This paper presents a global scheduling algorithm that transforms a given periodic task system into another using a “task-splitting” (as opposed to the “set-splitting”) technique. Each transformed periodic task system is guaranteed to be scheduled successfully on any uniform multiprocessor using a partitioned scheduling algorithm. The earliest deadline first (EDF) algorithm is chosen for scheduling tasks on each processor. It is proven that the proposed algorithm results in the theoretical-maximum utilization bound on any uniform multiprocessor platform if the platform is “reasonably powerful”. Therefore, the proposed algorithm is optimal in the sense of maximizing achievable utilization. Since the task-splitting technique will incur context switches during runtime, we have also considered the ways of reducing the number of context switches, and suggest a method which can significantly reduce the number of context switches in the schedules generated by the proposed algorithm.
목차
Abstract
I. INTRODUCTION
II. BACKGROUND
III. THE ALGORITHM
IV. PRACTICAL CONSIDERATIONS
V. CONCLUSIONS
REFERENCES
참고문헌 (20)
참고문헌 신청
M. Dertouzos, “Control robotics: the procedural control of physical processes,” in Proceedings of the 6th IFIP Congress, Stockholm, Sweden, 1974, pp. 807-813.
C. L. Liu and J. W. Layland, “Scheduling algorithms for multiprogramming in a hard-real-time environment,” Journal of the ACM, vol. 20, no. 1, pp. 46-61, 1973.
J. H. Anderson, V. Bud, and U. C. Devi, “An EDF-based scheduling algorithm for multiprocessor soft real-time systems,” in Proceedings of the 17th Euromicro Conference on Real-Time Systems (ECRTS), Balearic Islands, Spain, 2005, pp. 199-208.
F. Zhang and A. Burns, “Schedulability analysis for realtime systems with EDF scheduling,” IEEE Transactions on Computers, vol. 58, no. 9, pp. 1250-1258, 2009.
A. K. L. Mok, “Fundamental design problems of distributed systems for the hard-real-time environment,” Ph.D. dissertation, Massachusetts Institute of Technology, Cambridge, MA, 1983.
C. L. Liu and J. W. Layland, “Scheduling algorithms for multiprogramming in a hard-real-time environment,” Journal of the ACM, vol. 20, no. 1, pp. 46-61, 1973.
J. H. Anderson, V. Bud, and U. C. Devi, “An EDF-based scheduling algorithm for multiprocessor soft real-time systems,” in Proceedings of the 17th Euromicro Conference on Real-Time Systems (ECRTS), Balearic Islands, Spain, 2005, pp. 199-208.
F. Zhang and A. Burns, “Schedulability analysis for realtime systems with EDF scheduling,” IEEE Transactions on Computers, vol. 58, no. 9, pp. 1250-1258, 2009.
A. K. L. Mok, “Fundamental design problems of distributed systems for the hard-real-time environment,” Ph.D. dissertation, Massachusetts Institute of Technology, Cambridge, MA, 1983.
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
Static Task Scheduling Algorithm with Minimum Distance for Multiprocessor System (STMD)
SmartCR
2015 .04
-
Arbitrary Processor Network Scheduling Algorithms in Parallel Computing
SmartCR
2015 .06
-
A Novel Approach for Task Scheduling in Parallel Computing using Priority Attributes
SmartCR
2015 .08
-
Review of Task Duplication Based (TDB) Scheduling Algorithms
SmartCR
2015 .02
-
Energy-efficient Scheduling of Periodic Real-time Tasks on Heterogeneous Grid Computing Systems
International journal of internet, broadcasting and communication : IJIBC
2017 .01
-
멀티프로세서 시스템에서의 실시간 태스크 스케줄링 연구 동향과 도전 과제
정보과학회지
2017 .10
-
시각물체 추적 시스템을 위한 멀티코어 프로세서 기반 태스크 스케줄링 방법
한국자동차공학회논문집
2016 .03
-
Fault-tolerant Scheduling of Real-time Tasks with Energy Efficiency on Lightly Loaded Multicore Processors
International journal of advanced smart convergence
2018 .01
-
A Task Scheduling Method after Clustering for Data Intensive Jobs in Heterogeneous Distributed Systems
Journal of Computing Science and Engineering
2016 .03
-
Dynamic Priority Assignment for Aperiodic Tasks in Limited Preemptive Scheduling
IEIE Transactions on Smart Processing & Computing
2020 .10
-
Energy Aware Task Scheduling for a Distributed MANET Computing Environment
Journal of Electrical Engineering & Technology
2016 .07
-
Task Scheduling System Based on Consensus Algorithm in P2P Network
한국통신학회 APNOMS
2020 .09
-
A genetic algorithm for scheduling problem in cell culturing
대한산업공학회 춘계공동학술대회 논문집
2023 .05
-
다중프로세서 시스템에서 개선된 합성 이용율을 이용한 혼합 태스크 스케줄링
한국정보통신학회논문지
2015 .02
-
고성능 멀티프로세서를 위한 유전 알고리즘 기반의 반복 데이터흐름 최적화 스케줄링 알고리즘
한국인터넷방송통신학회 논문지
2015 .01
-
A Multi-Objective Evolutionary Algorithm for Scheduling Flexible Manufacturing Systems
Industrial Engineering & Management Systems
2017 .06
-
계시별 요금제에서 State-Task Network를 이용한 단기 일괄작업 부하계획 모형
조명·전기설비학회논문지
2023 .12
-
Application of Forest Optimization Algorithm for the Resource Constraint Project Scheduling
Industrial Engineering & Management Systems
2022 .06
-
Multi-objective Mathematical Modeling for Scheduling Machines in Parallel with Batch Processors
Industrial Engineering & Management Systems
2022 .06
-
무선 애드혹 네트워크에서 우선순위를 고려한 분산 노드 스케줄링
제어로봇시스템학회 논문지
2020 .02
이 논문의 저자 정보
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2020-569-001305211
