Design  | SFC  |  NOS  |  Code |  Diary  | WWW |  Essay |  Cisco | [Home]

 

 

[Bill's Home Page]
[ Old page]

Essays


One of the best-known software errors occurred on 22 July 1962 when the Mariner I rocket had to be blown-up, after it followed an erratic path after it took off. It was caused by a single incorrect character in a FORTRAN statement for the motion equations.

In 1963, ANSI defined the 7-bit ASCII standard code for characters. At the same time IBM had developed the 8-bit EBCDIC code which allowed for up to 256 characters, rather than 128 characters for ASCII. It is thought that the 7-bit code was used for the standard as it was reckoned that eight holes in punched paper tape would weaken the tape. Thus the world has had to use the 7-bit ASCII standard, which is still popular in the days of global communications.
Key characters to remember are:
'A' 41h 0100 0001
'a' 61h 0110 0001
'0' 30h 0011 0000

LF 0Ah 0000 1010
CR 0Dh 0000 1101

Mastering Comput-ing, W.Buchanan, Palgrave

Isn't that interesting?

 


 


 

 

 

 

 

 

 

Shortest first or round robin?

6 July 2001 WORK IN PROGRESS!

ultitasking operating systems can run many programs at the same time, but these must be organized in some way. This is the task of the process scheduler, which must allow each process some time on the processor. A badly designed scheduler simply allows each of the processes the same period of time. Whereas a well-designed scheduler allows for priority levels, and can make decisions on which processes should be run, at a given time. Typically system processes are more important than user programs, and need to be run at regular intervals, and will thus be given a higher priority over user programs. Two typical scheduling algorithms are round-robin and shortest-job-first.

Round-Robin (RR) is a first-come, first-served schedule with pre-emption, where each process is given a finite time slice on the processor. The queue is circular, thus when a process has been run, the queue pointer is moved to the next process, as illustrated in Figure 1. This is a relatively smooth schedule and gives all processes a share of the processor. As children we would typically be assigned to things in a round-robin way, especially when there were too many demands on a certain resource, and we didn't get enough time on it. A good example is when children want to get access to a bouncy castle, and there's a limit on the number that can be on the castle at any one time. An example schedule might be to allow a child onto the castle for a minute, and then they must come off, and go back to the end of the queue. The next child in the queue can then take their place on the castle.

Figure 1: Round robin (© billatnapier)

This is one of the most efficient algorithms, and involves estimating the amount of time that a process will run for, and taking the process which will take the shortest time to complete. A problem for the scheduler is thus to determine the amount of time that the process will take to complete its task. This is not an easy task. For example, let's say that we've got four tasks to complete. Task 1 will take one hour, task two take two hours, task three will take three hours, and finally task four will take eight hours to complete. We could schedule the task to each get half-an-hour of processing time. Once we have finished this time, we make a decision on what task to do next. Thus within four hours we would have the following:

ROUND ROBIN

Time slot (in half hour blocks)

Task (remaining time to completion)

1

Task 1 (0:30)

2

Task 2 (1:30)

3

Task 3 (2:30)

4

Task 4 (7:30)

5

Task 1 (complete)

6

Task 2 (1:00)

7

Task 3 (2:00)

8

Task 4 (7:00)

It can be seen that we have only completed one task, but if we were to take the shortest-job first, then:

SHORTEST-JOB-FIRST

Time slot (in half hour blocks)

Task (remaining time to completion)

1

Task 1 (0:30)

2

Task 1 (complete)

3

Task 2 (1:30)

4

Task 2 (1:00)

5

Task 2 (0:30)

6

Task 2 (complete)

7

Task 3 (2:30)

8

Task 3 (2:00)

We can see that we've now completed two tasks, and we're at the same point as the previous example with Task 3. From the user's point-of-view this will be perceived as possibly the most satisfying as more tasks have actually been competed in a shorter time. From a computer system point-of-view the user will perceive that the processes are running faster, as they are being completed at a perceived a faster time (although Task 4 is being starved on processing time, in order to achieve this). The only problem in that some of the processes will not make any progress until they are allowed access to the processor.

The time remain in each of the cases will be the same as the first scheme will require 10 hours to complete (Task 2 still requires 1 hours, Task 3 still requires 2 hours and Task 4 still requires 7 hours), and the short-job first scheme still requires 10 hours (Task 3 still requires 2 hours and Task 4 still requires 8 hours). Thus the short-job-first is only perceived to be running tasks faster. Shortest-job-first is very efficient on processor time with batch systems, as batch processes are less susceptible to process starvation. The round-robin approach works in a much fairer way, but can suffer if there are large processes running on the system, as these will general slow down the completion of other processes.

Chapter 4, Mastering Computing, W.Buchanan, Palgrave.

Comments on this essay

If you've got any comments on this essay (no matter if you agree or disagree with it), please send them to me using the form below.

Details

Name (Surname, First Name):

[Not required]

E-mail:



Your comment

 

Note your comments may be published to a comments pages, but none of your details will be added to the comment, just the date that it was sent. Thank you.