SKEDSOFT

Real Time Systems

PROCESSORS ANDRESOURCES
We divide all the system resources into two major types: processors and resources. Again, processors are often called servers and active resources; computers, transmission links, disks, and database server are examples of processors. They carry out machine instructions, move data from one place to another, retrieve files, process queries, and so on. Every job must have one or more processors in order to execute and make progress toward completion.

  • Sometimes, we will need to distinguish the types of processors. Two processors are of the same type if they are functionally identical and can be used interchangeably. Hence two transmission links with the same transmission rate between a pair of sender and receiver are processors of the same type; processors in a Symmetrical Multiprocessor (SMP) system are of the same type, and so on. Processors that are functionally different, or for some other reason cannot be used interchangeably, are of different types. CPUs, transmission links, and disks are of different types, because they are functionally different. A transmission link connecting an on-board flight management system to the ground controller is a different type of processor from the link connecting two air traffic control centers even when the links have the same characteristics, because they cannot be used interchangeably.
  • We will consistently use the letter P to denote processor(s). When we want focus on how the jobs on each processor are scheduled, how the jobs on different processors are synchronized, and how well the processors are utilized, there is no need to be concerned with whether the processors are identical or different. At these times, we will ignore the types of processors and call the m processors in the system P1, P2, . . . , Pm.
  • By resources, we will specifically mean passive resources. Examples of resources are memory, sequence numbers, mutexes, and database locks. A job may need some resources in addition to the processor in order to make progress. One of the attributes of a processor is its speed. Although we will rarely mention this attribute, we will implicitly assume that the rate of progress a job makes toward its completion depends on the speed of the processor on which it executes. We can explicitly model this dependency by making the amount of time a job requires to complete a function of the processor speed. In contrast, we do not associate speed with a resource. In other words, how long a job takes to complete does not depend on the speed of any resource it uses during execution.
  • For example, a computation job may share data with other computations, and the data may be guarded by semaphores. We model (the lock of) each semaphore as a resource. When a job wants to access the shared data guarded by a semaphore R, it must first lock the semaphore, and then it enters the critical section of the code where it accesses the shared data. In this case, we say that the job requires the resource R for the duration of this critical section.
  • As another example, we consider a data link that uses the sliding-window scheme to regulate message transmission. Only a maximum number of messages are allowed to be in transit (i.e., they have been transmitted but their reception has not yet been positively acknowledged). One way to implement this scheme is for the sender to maintain a window of valid sequence numbers. The window is moved forward as messages transmitted earlier are acknowledged by the receiver. A message waiting to be transmitted must first be given one of the valid sequence numbers before it can be transmitted. We model the transmission of a message as a job; the job executes when the message is being transmitted. This job needs the data link, as well as a valid sequence number. The data link is a processor. The sequence numbers are units of the sequence-number resource.
  • Similarly, we usually model transactions that query and update a database as jobs; these jobs execute on a database server. If the database server uses a locking mechanism to ensure data integrity, then a transaction also needs the locks on the data objects it reads or writes in order to proceed. The locks on the data objects are resources.
  • We will use the letter R to denote resources. The resources in the examples mentioned above are reusable, because they are not consumed during use. (In contrast, a message produced by a process and consumed by another process is not reusable because it no longer exists after use.) In our discussion, a “resource” almost always mean a reusable resource. The statement that the system contains ρ resources means that there are ρ types of serially reusable resources, each resource may have one or more units, and each unit is used in a mutually exclusive manner. For example, if the sliding window of a data link has eight valid sequence numbers, then there are eight units of the sequence-number resource (type). The write lock on a file is a resource that has only one unit because only one job can have the lock at a time. A resource that can be shared by a finite number x of jobs is modeled as a resource (type) that has x units, each of which can be used by only one job at a time.
  • To prevent our model from being cluttered by irrelevant details, we typically omit the resources that are plentiful. A resource is plentiful if no job is ever prevented from execution by the lack of this resource. A resource that can be shared by an infinite number of jobs (e.g., a file that is readable simultaneously by all) need not be explicitly modeled and hence never appears in our model. You will notice later that we rarely mention the memory resource. Clearly, memory is an essential type of resource. All computing and communication systems have this resource. We omit it from our model whenever we can account for the speed of the memory by the speed of the processor and memory is not a bottleneck of the system. For example, we can account for the speed of the buffer memory in a packet switch by letting the speed of each input (or output) link equal the transmission rate of the link or the rate at which data can go in (or out of) the buffer, whichever is smaller. Therefore, there is no need to explicitly model this aspect of the memory. By memory not being the bottleneck, we mean that whenever a job is scheduled to execute, it always has a sufficient amount of memory.
  • Many real-time systems are designed so that this assumption is valid. When this assumption is not valid, the timing behavior of the system critically depends on how memory is allocated to jobs. Clearly, the model of the system must include the memory resource in this case. Another point to keep in mind is that we sometimes model some elements of a system as processors and sometimes as resources, depending on how we will use the model. For example, in a distributed system, a computation job may invoke a server on a remote processor.
  • When we want to focus on how the response time of this job depends on the way the job is scheduled with other jobs on its local processor, we may model the remote server as a resource. We may also model the remote server (or more precisely the remote processor) as a processor. As you will see that in Chapter 9, we indeed use both of these alternatives to model remote execution in distributed systems. They give us two different points of view and lead to different scheduling and resource management strategies.
  • As a final example, let us consider the I/O bus. Every computation job must have the I/O bus in addition to the processor to execute. Most of the time, we model the I/O bus as a resource, oftentimes a plentiful and therefore ignored resource. However, when we want to study how long I/O activities may delay the completion of computation jobs that share the I/O bus or when we want to determine the real-time performance of an I/O bus arbitration scheme, we want to model the bus as a resource or a processor.
  • There are no cookbook rules to guide us in making this and many other modeling choices. A good model can give us better insight into the problem at hand. A bad model can clutter our mind with irrelevant details and may even give us a wrong point of view and lead to a poor design and implementation. For this reason, the skill and art in modeling are essential to a system designer and developer.