------------------------------------------------------------------------------ This paper surveys the algorithms developed for scheduling real-time tasks in distributed systems. In section 2 the authors establish the basic definition that are required for the discussion to follow. This section is well structured and reveals all main terms for task characteristics (arrival patterns, inter-task dependencies, deadline laxity) and systems architectures (homogeneous and heterogeneous). In section 3, three key design choices are pointed - static vs. dynamic scheduling, priority and preemption and assignment-oriented vs. sequence-oriented. However, there is no explanation why the authors tend to assume these to be the most important issues. May be some references have to be added to algorithms proving that these are the main design problems indeed (there is only one reference - for the duplication based approach in the static scheduling algorithms). Section 4 provides the readers with several algorithms for scheduling real-time applications. The description of each of them is in-depth. First the authors start with RMS algorithms. Here they assert that this algorithm is fundamental as a theoretical basis for most current scheduling algorithms but don't explain why. Since this solution is applicable only for single processor architecture, it's not obvious how it can be used or further generalized for more complicated cases. In the presentation of this algorithm they say that the authors of RMS showed "if a given set of hard real-time tasks can be scheduled by any algorithm, then it can be scheduled by the RMS", which is very unclear and need more justification. After RMS a set of synchronization protocols follow. It's quite surprising the change of terminology from "algorithms" to "protocols". There is no explanation about this. It's also not very clear why the name of the subsection is Release Guard Protocol since three different protocols are described (and RGP is the last one). The section ends with detailed description of two other algorithms. The paper ends with future work suggestions that look sound in the context of the paper. On the whole, the paper is well written with a lot of details about the proposed algorithms. As a main drawback I can point the lack of separate section with a discussion on the topic (after presenting the basic algorithms), instead each approach is discussed separately. ------------------------------------------------------------------------------ For Section 3.3 "Assignment-Oriented Vs Sequence-Oriented", it need further discussion. About section 4.1, the "mixed algorithm" it use both RMS and Deadline-Driven scheduling, but how they are mixed was not quit clear..! Table 1: system configuration. Need to be explained, otherwise, it is better to drop it from the discussion. ------------------------------------------------------------------------------ The topic seems very relevant; it would be nice (although perhaps beyond the scope of your paper) to know about some implementations of systems using the given algorithms, and how they perform. Section 2 on problem formulation was very helpful and well-written, as was Section 3 on characterization of different algorithms. Maybe I just don't have the necessary background, but I had trouble following many of the explanations of the algorithms, which seemed brief. It may just be because the material itself is dense, but the explanations seemed to cram too much information into too few words. I would like to see a more protracted explanation of each. I found the captions on the figures to be insufficient. They often did not explain enough about what the figure represents. One could often decipher the meaning from the paragraphs around the figure, but it became more difficult as the algorithms became more complex. ------------------------------------------------------------------------------ The paper presents observations that are not very clear or not well supported. - Page 2: "However, the problem of finding an optimal schedule for real-time tasks has been shown to be NP-complete" R. Rate-Monotonic and Earliest Deadline First [Liu73] are examples of optimal polinomial time algorithms that solve the real-time task scheduling problem. Most of the real-time task scheduling problems instances are NP-Hard, but some instances are not; - Page 3: "While preemptive schedulers might be able to produce better schedules, they..." R. This statement should be supported with some examples or references. Many solutions to the priority inversion problem are based on some kind of preemption avoidance (e.g. Kernelized Monitor [Mok83] and Priority Ceil Protocol [Sha90]). Therefore, it is not straightforward that preemption is always a good solution; - Page 5: "...all algorithms presented in this subsection are very analythical (e.g. impractical)". R. This is not a true statement. Many systems today actually implement Rate-Monotonic and EDF (e.g. RT-Mach [Toku90] and Chorus extensions [Couls94]); - Page 12: "There seems to be virtually no work at all on distributed scheduling of real-time tasks". R. The literature has several proposals to distributed scheduling in real-time systems (e.g. [Stank85] [Shin94]). ------------------------------------------------------------------------------ The paper presented ideas of interest to me, but I found it difficult to follow some of the arguments. For example, what is a domain? I wished for a little more discussion on the topic in general, further clarifying the salient characteristics of real-time schedulers, and specifically how distributed scheduling was especially unique for real-time systems. I disagree with one of the fundamental statements regarding inter-task dependencies: "... interdependent tasks are usually the subject of static schedulers." There is a body of current and recent research showing that dynamic schedulers can efficiently schedule interdependent tasks. Reference Sobalvaro (1998), Liu (1993), and Hamidzadeh(1995). Granted, though, these do not deal directly with real-time systems. A good job was done describing how scheduling of real-time systems often involves "hard deadlines", and how these deadlines direcly imply a priority-based system. ------------------------------------------------------------------------------ In section 3, the paper claims the preemptivity of tasks as one of the design options available for the schedulers. However, in section 4 , term "preemptive" is used as if it is one of the assumptions they make about the task characteristics. (It is used along with "aperiodic" or "interdependent") Since there are no definition of the term "phase", description of the PM protocol is very difficult to understand. There should be at least some description of what this parameter is intended to characterize. You should mention the goal of this research area. Which assumptions made about the tasks on current algorithms is awkward or inappropriate? What will the task characteristics of the ideal scheduler be? Are the proposed future works relevant to this goal? There were references made to publications not on the bibliography ([Dij68],[CHE96]). Make sure to add them on the list.