).@www.csse.monash.edu.au |
| Assessment | Contacts | Laboratories | Lectures | Resources | Timetables | Tutorials | Unit Outline |
| Last modified: 20080911:124507/revised JobQ to inherit from standard data type list (this was not an option when the code was first written). | FIT2022 AJH-2008-28 |
Objectives and Outcomes | Introduction | The Job Queue | Memory Allocation | Process Execution | The Literate Program | Reflections | Group Work
Please make sure you read through this lab sheet before you attend the lab! Demonstrators have been asked to give not satisfactory to those students they feel have not been diligent enough in their preparation!
At the end of this lab session, you should:
Your demonstrator may ask you questions about these points, and will only give you a "satisfactory" for the lab if you can respond correctly.
For the group work, you will need to complete the required work within your groups by the next lab session. Failure to do so will result in an unsatisfactory mark.
This lab builds a very simple operating system, called PythOS.
Memory management is about making sure that there is enough memory available within the system to run the various processes on offer. Each process needs memory to run, and some processes require more than others to run. It is the role of the memory management algorithm to allocate memory to processes in such a way as to satisfy one or more policies. Those policies may give priority to such things as simplicity, fairness, performance, efficiency, etc., and often these goals may be in conflict. Operating systems design is a compromise!
We will demonstrate memory management by building a simple high level operating system. This system is high level, because it executes Python programs directly, rather than compiling them into machine code. It is simple, because we do not address data management issues, but focus only upon the memory management of the code space. Nevertheless, it does demonstrate some vital principles, not the least being the use of processes (threads in our implementation) at the operating system level as well as the user level.
Our simple model is this:
Each of the first four of the above components is modelled as a Python class, called respectively: read_progs, load_progs, JobQ, and memory_alloc. A further class, Process, models each user-level process in execution. To run this lab, you should download the modules: job_queue.py, mem_sys.py, and process_ex.py now.
Let's start with the simplest component of all, the job queue. This is so simple that we could just use a standard Python list data type to model it, but it is important enough to single it out. Besides which, we want to add a few bells and whistles!
***************************************** to FIX !!!!!! *******
"job_queue.py" 3.1 =We build the JobQ on the standard data type list. All the standard list methods are available, but we wish to define some methods peculiar to our job queue model (and give them slightly different names).
<define the add a job method 3.2> =The first method is to add a new job to the queue. Since we are inheriting from the standard list type, just define the add method to be a list append.
<define the next job method 3.3> =The other major method is to select the next job from the queue and remove it. Again, FIFO semantics means that we select the first element in the list, returning that as the value of next, and then deleting it from the job queue. Inheritance makes this easy.
The check method allows us to inspect the details of the next job in the queue (if there is one) without actually removing it. This will be useful later, as we shall see.
Note that this method embodies the essence of the long-term job scheduling algorithm. It defines how the next job is selected. While we use a simple First-In First-Out strategy here, it would not be too hard to use some other algorithm, such as Shortest Job First (SJF). Indeed, see Group exercise 1 below.
<define the printable representation of the job queue 3.4> =Here's one of the bells and whistles. We see later that the structure of a "job" on the queue is a tuple of various things, the first field of which is the job name, the second of which is the job size (defined appropriately). Using python's convenient tuple extraction from an iterator (remember, we are inheriting from list), we iterate over all jobs in the queue, picking off the filename and length of each job. We could rely upon the default representation of a tuple when printing the job queue, but we'll restrict it to just the job name (actually the name of the file from which the job was read), and the size of the job. We scan through the data structure extracting just those fields.
Here's a simple little test program exercise2.py for the job queue class. Add the job test2 with length 2048 before the "next" call and see what happens. Extend it with further adds and removes, and print the queue out each time.
"exercise2.py" 3.5 =Next in this lab is a simple memory allocation algorithm, based on contiguous allocation of space. Various requests for space arrive (such as might be occasioned by the need to load a process image of a particular size), and the allocation algorithm either returns the address of an area of memory that will satisfy the request, or it will be unable to do so, in which case it signals an error by returning a negative address.
Note that this algorithm is not modelling memory itself. That turns out to be inessential to our modelling process. All that is necessary here is to model how memory would be used, if we were to build a full scale system.
"mem_sys.py" 4.1 =Define a memory allocator class. The definition of the various methods of the class is deferred. We use a class, rather than a set of procedures, since that allows us to encapsulate the memory behaviour. One use of this class, for example, would be to model the behaviour of different sizes of memory. We can do that by instantiating this class with different memory size parameters. Each of these instances (objects) can co-exist. (See exercise 5.)
<mem: initialize 4.2> =Define the class constructor for a memory of MemSize bytes, divided into allocation units or chunks of 16 bytes (ChunkSize). It initializes the free bitmap, represented here as an array of "bits" of length NChunks, one bit for each unit of allocation. All of these bits are initialized to zero, indicating that the memory is initially completely free.
<mem: string representation 4.3> =We cheat a bit. Rather than pure bits, each value in the "bitmap" is actually an integer (strictly it needs only to be 8 bits long, since a single byte is the minimum Python data size - for a single character). We exploit this by storing not just the integer 1 in each "bitmap", but rather a flag character, chosen to indicate which areas are allocated to which job. The flag character is folded into its integer (ordinal) value, and type-coerced out again on use. This provides a convenient string representation of the current state of memory allocation, as determined by the free bit map.
Print a "." character if the chunk is free, otherwise print the first letter of the parameter flag if the chunk is allocated. (This is the ordinal value stored in the bitmap vector itself.) The parameter flag will be used to customize the allocation map.
<mem: allocate 4.4> =This method is the heart of the memory allocation system. We scan over all chunks, looking for free chunks. Whenever we find one, indicated by a zero value, we check forward to see whether there are sufficient free blocks in a contiguous group to satisfy the request.
This algorithm is order n x m, where n is the number of chunks, and m is the block size requested. See if you can write an order n algorithm.
Finally, the free method. This is quite simple, assuming that the address of the free block and its size as originally requested can be passed in as parameters. We just zero out the appropriate "bits" in the bitmap. Note that the allocator may fail if the adr and length values differ from the corresponding original request.
Run the exercise4.py test program. Note that the memory is large enough to satisfy all requests. Reduce the memory size until some requests cannot be satisfied, and note the behaviour.
"exercise4.py" 4.6 =Run the exercise5.py test program. Note that it is effectively the same as exercise4, but we model both memory sizes at the same time.
"exercise5.py" 4.7 =If we had modelled the memory allocator as a non-object-oriented suite of procedures, this exercise would not have been possible.
We build a simple model of process execution
"process_ex.py" 5.1 =The time module is used to perform sleep operations, the sys module is used to access the stdin file, threading is used to model three sets of processes, and the job_queue module, described above, is used to instantiate the job queue jobs.
The running flag indicates that the operating system is "operating", and when set to zero, shuts the system down. active counts the number of jobs that are currently active
The event variable runajob signals when an event that might cause a new job to run has occurred. This happens when new jobs are read into the job queue or current jobs terminate. Note, however, that there may not be space in memory for the job to run.
This class defines the process instance creator that will be responsible for reading the names of files containing programs for execution, reading those files themselves, and storing them in the job queue.
<define the read_progs constructor 5.3> =Create the thread for this process.
<define the read_progs start thread 5.4> =Start the thread for this process.
<define the read_progs run method 5.5> =We assume that there is a list jobs of programs that have been read. Incoming programs are appended to this queue. The global flag running is used to indicate when the system is active (running == 1) or whether it should be shut down (running == 0). Exit (terminate) the read programs thread in this latter case.
<read a program name from stdin 5.6> =Read a filename from standard input (the terminal), using the special i/o function raw_input, which prints a prompt (with no trailing newline), and returns the string read (also without newline). You will note when you run this code that the prompt doesn't always appear before the string actually typed in response, since there may be other i/o activity happening asynchronously.
If the filename is halt, special action is taken. In this case, no file is read, but a pseudo job is placed in the queue. (See below for explanation of the parameters.) The fact there there is a new (pseudo) job to run prompts us to signal the event runajob, and we then return from the thread. This means the reading process shuts down and no more jobs are read, but the system continues running until the halt job is executed.
<read that file 5.7> =Read the nominated file and compute its length in bytes. Notice that here we use Python's execption handling mechanism to ensure that if there is no such file (or some other error happens on reading), the read programs process does not terminate abnormally. Any IOError exception thrown by the I/O calls will be captured, and a message printed. The thread then continues normally, although a flag ok is cleared to indicate that no job was read.
<add program to job list 5.8> =If a job was read successfully, add it to the job queue and signal the runajob event. The actual entry in the job queue is a 3-tuple, containing the filename, the length of the job (in characters), and the actual program text.
To test out the load programs code, try running exercise6.py, shown below. At the prompts, enter the filename of a Python program. Three simple programs a, b, and c are given, but feel free to write your own. Terminate the program by typing halt.
Since there's not much you can see happening, you might add a print jobs statement after the jobs.add call (and before the event set) in chunk <add program to job list 5.8> to see the job queue as each job is added.
"exercise6.py" 5.9 =This class defines the process instance creator responsible for the loading and execution of programs in the job queue.
<define the load_progs constructor 5.14> =Create the thread for this process. Initialize the memory size to be used.
<define the load_progs start thread 5.15> =Start the thread for this process.
<define the load_progs run method 5.16> =The main loop for executing processes. We grab a memory allocator, and start picking jobs off the job queue to run. Only when the global variable running is reset do we terminate the thread.
<select next program and run 5.17> =Here's the crunch. We may or may not have memory space to run the next job. We first look at the job parameters, and check that the memory is large enough to run the job, even there is no other allocation of memory. In that case we discard the job, and try the next one in the queue.
We then try to allocate memory to it. If the memory allocation succeeds, we can run the job, otherwise we just wait until there is space.
Running the job entails creating a new Process thread, see later.
<inspect next job j on job queue 5.18> =This is why we added that check method to the job queue. It allows us to look ahead on the job queue, and if there are no jobs waiting to be run, we go into a wait instead.
<get job parameters 5.19> =We've found a job, first check if it is that pseudo job halt. If so, turn off the running flag and terminate the load programs thread. This will exit the entire PythOS program (and turn PythOS off ).
We also check that the jobfits in the available memory, otherwise there is no point in waiting for other jobs to free memory. This job could never run anyway.
<wait until we have space to run it 5.20> =We try and allocate space. If unsuccessful, print a message, wait for a job to terminate, and try again.
<update job information 5.21> =We can run a job. Update the associated information, and print job and memory state.
In chunk <wait until we have space to run it 5.20> above, we wait on the runajob event. But this may happen when a new job arrives, which clearly isn't going to free up any space. Can you rewrite process_ex.py so that we do not needlessly go round the while loc<0 loop?
If you attempted group task 1 from lab 2, you might recognise this code. This is the process wrapper class that you would need for chunk <example5: create a process instance for that code >. It collects various job parameters (including the code to execute - in practice this would be the memory address of the now loaded code), and sets up the environment to execute that code. The execution is actually done in the run method ...
<define the Process run method 5.23> =... which does an exec of the code, then frees the memory afterwards, updates the active count, and signals that a job has completed (see Exercise 7).
All that remains is to write a little driver environment, and we have the final PythOS! Download pythos, and do a chmod 755 on it, so that you can execute it directly.
Run this program, and enter the job names a,b,c,halt; then c,b,a,halt. Experiment.
"pythos" 5.24 =Try to enter a sequence of jobs that causes memory to fragment, that is, there is enough memory for a job to run, but it is split and cannot be used. Try this sequence of jobs: a, b, a, a, c, a, b, c, a, a. Does it cause fragmentation?
Run PythOS, and then type in exercise4.py. Cool eh?
Warning:You do not need to understand the following section: it is included for information and interest only. The literate program source code of lab 4 is available on-line. See Lab 2 for details of how this is constructed.
Now read on:
The first-in first-out job scheduler used in the JobQ class is very simple. Rewrite the JobQ class to use shortest job first (SJF), where the length of the job is measured in bytes (rather than the more usual seconds), and experiment to see if it gives better performance. How might you define "better"?
An obvious problem is the lack of memory compaction. Rewrite the memory allocation so that when a request fails, memory is compacted, and the request retried. Again, does this give "better" performance?
| 20080911:124507 | 2.0.1 | ajh | revised JobQ to inherit from standard data type list (this was not an option when the code was first written). |
| 20080812:165716 | 2.0.0 | ajh | initial version for 2008 |
| This page maintained by John Hurst. Copyright Monash University Copyright Policy |
|   | |
Generated at 20090708:1320 from an XML file modified on 20080912:0853 | |||