Browsing by Author "Shih, WK"

Now showing 1 - 9 of 9

A new real-time disk scheduling algorithm and its application to distributed multimedia storage systems
(1998)
Chang, RI
;
Shih, WK
;
Chang, RC
;
資訊工程學系
;
Department of Computer Science
In this paper, a new real-time disk scheduling algorithm called BFI (best-fit-insertion) is proposed. Notably, different from the conventional realtime problem, the service time of a disk request depends on its schedule result. As the service time is not a constant value, it is time-consuming to verify the feasibility of a schedule. In this paper, we introduce a temporal parameter called maximum tardiness. With the help of maximum tardiness, we can verify the improvement of an insertion test within a constant time. We have evaluated and implemented our proposed algorithm on operating systems. Experiments show that the proposed algorithm can support more requests and can achieve higher disk throughput than that of the conventional approach.
Cache-aware real-time disk scheduling
(2004-09-01)
Chang, HP
;
Chang, RI
;
Shih, WK
;
Chang, RC
;
資訊工程學系
Previous real-time disk scheduling algorithms assume that each disk request incurs a physical disk mechanical operation and only consider how to move the disk head under real-time constraints. However, with the increased capacity of on-disk cache, modern disk drives read-ahead data aggressively. Thus, the on-disk cache may service many disk requests without incurring physical disk access. By exploring the design methodology of on-disk cache, in this paper, we propose cache-aware real-time disk scheduling algorithms that take the on-disk cache into consideration during scheduling. Therefore, the scheduling algorithm can help the cache replacement scheme to minimize the cache miss ratio. Besides, the service timing estimation is more accurate in schedulability analysis since the cache effect is considered during scheduling. A simulation-based evaluation shows the proposed scheduling algorithms to be highly successful as compared with the classical real-time disk scheduling algorithms. For example, under sequential workload with 10 sequential streams, the data throughput of our scheme is 1.1 times that of DM-SCAN.
Enlarged-maximum-scannable-groups for real-time disk scheduling in a multimedia system
(2000)
Chang, HP
;
Chang, RI
;
Shih, WK
;
Chang, RC
;
資訊工程學系
In a multimedia system, disk I/O subsystem is the most important component due to its relatively limited throughput and large delay. Previously, by applying SCAN to reschedule tasks having the same deadline, SCAN-EDF tries to improve disk throughput while realtime constraints call be satisfied. In DM-SCAN, groups of tasks that can be successfully rescheduled by SCAN under specified real-time requirements are identified. They are called MSGs (maximum-scannable-groups). In this paper; an enlarged-MSG (E-MSG) is proposed to further expand the MSG concept and thus to obtain more improvement in disk throughput. By removing some excess constraints on MSG, E-MSG merges several MSGs as a new scannable-group. Experiment results show that the E-MSG scheme is better than both SCAN-EDF and MSG in the disk throughput obtained.
Fast dynamic code assignment in next generation wireless access networks
(2003-09-01)
Wan, CS
;
Shih, WK
;
Chang, RC
;
資訊工程學系
;
Department of Computer Science
In this paper, a fast dynamic code assignment (FDCA) algorithm is proposed to assign a single Orthogonal Variable Spreading Factor (OVSF)-code for a data rate requirement in next generation wireless access networks. Our algorithm uses the code assignment operation to evaluate the cost for an OVSF-code allocation. The cost is determined by maintaining the data structure that keeps track the number of available and occupied descendant codes of the code. Based on the cost assignment operation, FDCA algorithm can assign an OVSF-code by reassigning occupied descendant codes for a requested data rate. The OVSF-codes assigned by our algorithm is unrestricted with decreasing spreading factor. Moreover, two types of simulations and experimental measurements are presented. First, the proposed algorithm is applied on the OVSF-code assignment of restricted spreading vector. Our experimental results show that the number of reassigned OVSF-codes within FDCA algorithm is reduced comparing to other scheme proposed in the literature. Then, for serving higher data rate requirements, our scheme also shows significant improvement on the spectral efficiency over fixed code assignment scheme. (C) 2003 Elsevier Science B.V. All rights reserved.
Real-time data access on HSDPA for WCDMA
(2004-02-01)
Wan, CS
;
Shih, WK
;
Chang, RC
;
資訊工程學系
;
Department of Computer Science
This paper presents new High Speed Downlink Shared Channel (HS-DSCH) code management schemes on High Speed Downlink Packet Access (HSDPA) for IP-based multimedia provisioning. The proposed management schemes simplify HS-DSCH code allocation while simultaneously increasing HS-DSCH code utilization. Applying the code management schemes, furthermore, we implement two scheduling algorithms for real-time packets to guarantee the quality-of-service (QoS) requirement. The Real-Time Code Allocation (RTCA) algorithm applies the functionalities of the radio management framework to decide the admission for a new real-time service. Once a new real-time session is established, RTCA allocates HS-DSCH codes to that session such that all real-time packets in the session are scheduled before their related deadlines. Based on the RTCA algorithm, the Real-Time Code Sharing (RTCS) algorithm implements the Early-Deadline-First (EDF) scheme for the schedulability analysis, increasing the schedulable probability for the real-time sessions and thus to improve the utilization of HS-DSCH codes. Experimental results show that RTCS outperforms RTCA in terms of packet drop rates, HS-DSCH code blocking rates and the number of code-domain reassignments.
Real-time disk scheduling for multimedia applications with deadline-modification-scan scheme
(2000-09-01)
Chang, RI
;
Shih, WK
;
Chang, RC
;
資訊工程學系
;
Department of Computer Science
Real-time disk scheduling (RTDS) is important for time-critical multimedia applications. In conventional approaches of real-time disk scheduling, such as SCAN-EDF, the seek-optimizing SCAN scheme is applied to reduce the disk service time of the real-time EDF schedule. Since only tasks with the same deadline are seek-optimized, the obtained improvement of SCAN-EDF is limited. In this paper, based on the maximum-scannable-group (MSG) concept, a deadline-modification-scan (DMS or DM-SCAN) algorithm is proposed. Our algorithm uses MSG to automatically decide the suitable task groups for seek-optimizing. Based on the MSG concept, we repeatedly apply DMS to further increase disk throughput to support more tasks. We have implemented the proposed algorithm on UnixWare 2.01. The appropriate problem behaviors and parameter values to yield good solutions are investigated. Experiments show that DMS is better than conventional approaches in both the obtained disk throughput and the supported tasks. Moreover, our proposed approach can schedule task sets that are not schedulable by EDF and SCAN-EDF.
Real-time disk scheduling with on-disk cache conscious
(2003)
Chang, HP
;
Chang, RI
;
Shih, WK
;
Chang, RC
;
資訊工程學系
Previous real-time disk scheduling algorithms assume that each disk request incurs a disk mechanical operation and only consider how to move the disk head under real-time constraints. However, with the increased capacity of on-disk cache, modern disk drives read-ahead data aggressively. Thus, the on-disk cache may service lots of requests without incurring physical disk access. By exploring the design methodology of on-disk cache, in this paper, we propose CARDS: a cache-aware real-time disk scheduling algorithm that takes the on-disk cache into consideration during scheduling. Therefore, the scheduling algorithm can help to minimize the cache miss ratio. Besides, the service timing estimation is more accurate in schedulability analysis since the cache effect is considered. A simulation-based evaluation shows CARDS to be highly successful as compared to the classical real-time disk scheduling algorithms. For example, under sequential workload with 10 sequential streams, the data throughput of CARDS is 1.1 times of DM-SCAN.
Real-time packet scheduling in next generation radio access system
(2003-11-01)
Wan, CS
;
Shih, WK
;
Chang, RC
;
資訊工程學系
;
Department of Computer Science
All IP-based radio access network enable packet-oriented connections to offer real-time applications. Radio access networks must provide efficient radio management for data session establishments because of scarce radio resources. In this paper, we present three real-time scheduling algorithms to support quality-of-service at IP-based radio access networks. The real-time generic scheduling (RTGS) algorithm applies the functionalities of the radio management framework to establish new data sessions for real-time service requests. The real-time bandwidth scheduling (RTBS) algorithm implements the early-deadline-first scheme to do the schedulability analysis and to schedule the data sessions to reduce power consumption. The RTBS algorithm can decrease the power consumption more than can RTGS. Based on the RTBS mechanism, we design the real-time code scheduling (RTCS) algorithm. In this algorithm, we apply the dynamic code assignment scheme to increase the probability of schedulable sessions and improve the radio resource utilization. Experimental results show that RTCS outperforms RTBS and, in turn, RTBS outperforms RTGS. (C) 2003 Elsevier B.V. All rights reserved.
Reschedulable-Group-SCAN scheme for mixed real-time/non-real-time disk scheduling in a multimedia system
(2001-11-15)
Chang, HP
;
Chang, RI
;
Shih, WK
;
Chang, RC
;
資訊工程學系
Real-time disk scheduling is important for time-critical multimedia applications. Previous approaches, such as SCAN-earliest deadline first (EDF) or DM-SCAN, applied the SCAN scheme to reschedule service sequence of input tasks to reduce tasks' service time. However, they required the input to be in EDF order. In DM-SCAN, a deadline modification scheme was employed to obtain a pseudo-EDF sequence from non-EDF ordered input tasks. Because the modified deadlines were smaller than the original ones, number of tasks that could be rescheduled is decreased and thus data throughput is reduced. In this paper, we propose Reschedulable-Group-SCAN (RG-SCAN), a new real-time disk scheduling algorithm using the concept of Reschedulable-Group (R-Group). Differing from previous approaches, RG-SCAN has no limitation on the input task's sequence. In addition, by exploiting the service time's reduction after rescheduling in each R-Group, RG-SCAN has been extended to serve mixed real-time and non-real-time workloads. As shown in experimental results. our approach can support more tasks than DM-SCAN, both real-time and non-real-time. Additionally, our approach can provide larger data throughput and offer better response time to non-real-time tasks. For example, given 30 random-generated real-time tasks, the number of non-real-time tasks that can be supported by RG-SCAN is 1.3 times that supported by DM-SCAN. In addition, our data throughput is 1.1 times DM-SCAN's. (C) 2001 Elsevier Science Inc. All rights reserved.