Last time we saw the development of paging systems which allowed us to store processes scattered throughout memory, wherever available frames of memory were. We will return to paged memory management later in this lecture. In the meantime, we need to examine more closely, ways in which memory is used by our programs. Maybe we can redesign the system to help our normal usage patterns.
Traditionally we have learnt to think of memory as a large array of cells, capable of holding a certain number of bits of information, numbered from zero to whatever. This is not the only way to think of memory. In fact if we concentrate on the way our programs use memory, we may see that some other form is more appropriate.
These different understandings of memory we will refer to as memory models. A memory model is the way we the memory appears to be organised. Different memory models have different ways of representing addresses, different ways of allocating memory etc. A memory model is sort of like a data type. We can define a structure describing the model and a set of operations we need to be able to perform on that memory.
Since we have already seen that we have to do some translation between the memory addresses used in our processes and the real memory anyway, we can make this translation act to our advantage, to fit the memory model our programs require.
All of the last lecture presumed we were working with the flat memory model. If our programs want to do anything special with memory they have to impose their own structure on top of the array of memory.
The operations we get with a flat memory model are simple. We can request a contiguous chunk of this memory and access any particular cell with an index into the memory array. This contiguous chunk must go on the end of our currently allocated space.
The question we need to ask ourselves is, "is this the way we normally use memory in our programs?".
The answer is, sort of, but less and less.
Lets take an ordinary C program for our example. What do we refer to in our program?
Where our variables are stored usually doesn't matter. We don't need our global variables to all be held in one place. We refer to variables by their names. The compiler turns the names into addresses (or offsets). Similarly we don't worry about how our functions are placed in memory, as long as we can refer to them and jump to them as required. In fact if memory came in individual chunks, one for each function, it would usually not matter to our programs. In fact we do need to grab new space for our local variables (and for the rest of the activation record) whenever we call a function. This is quite a development. Memory needs to be allocated when we need it, and returned when we have finished with a chunk.
With C programs it is common to request contiguous chunks of memory for storing strings and other potentially structureless data.
Considerations such as this lead us to the "stack memory model". Where memory is allocated (pushed) on a stack of activation records as functions are called. Strictly speaking only memory on the top of the stack should be accessible. Few programming languages enforce this strictly. Since the values of local variables are not used after the function which brought them into existence has returned, we also require the ability to pop memory off the stack.
Actually we need an unlimited supply of memory with the type of program we want to run here, because a function may call itself repeatedly an arbitrary amount of times. Before we had such recursive routines, or if local variables were stored statically as they were in many early versions of Fortran for example we knew exactly how much memory our local variables were going to take before our program executed.
An aspect of almost all programming languages is breaking the code and data up into chunks as we have been describing here. This leads to another approach to thinking about memory. Being able to allocate chunks which are logical units in the program. What sort of logical units am I thinking of?
These chunks corresponding to logical units are known as segments. Different programs and indeed different programming languages give different sorts of segments.
What tasks do we need with a segment based memory model? We need to be able to allocate and deallocate segments of any size. It doesn't matter where the segment is in memory. Each segment should be a contiguous chunk of memory, but they don't have to be anywhere near each other.
This means that our memory addresses have to change. Instead of the simple address of the flat memory model we have a two dimensional address, <segment name, displacement>. The segment name is reduced to a number (as long as we can uniquely identify the segment it doesn't matter what we call it). The displacement must be able to cover the whole address space (we don't want to have to put artificial requirements on the size of our segments). This last requirement of course means that our programs (or compilers) are free to ignore segments if they want to. All memory for a process could be allocated as one huge segment.
From the process's point of view, this is the way memory should be allocated. If the process needs a certain amount of memory for a procedure, that is what it should get. There is no reason (in these days of structured programming) to allow one procedure to access the internals of another procedure, therefore they do not have to be in the same address space. In a similar way, large areas of data, can be allocated the exact amount of space as required.
What about small chunks of memory, such as individual small variables (like integer and character variables)? From the point of view of implementation it doesn't make much sense to allocate an individual segment for each of these, however there is more than likely a collection of variables which can be allocated together (the local variables of a procedure is a good example).
Some programs, compilers and linkers in particular should be easier to write if generating code for a segmented memory system.
The system has to provide segment descriptor tables. The same sort of thing as page tables, however rather than concatenating the displacement with a base address, it must be added, because the segment can be stored anywhere in real memory.
In what ways is it similar to and different from a paged memory system?
This has consequences such as not knowing in advance how big the segment table for a process will be. As we saw earlier, it may only require one entry. Also, not only must we store the base address information for a segment in the segment descriptor table, we must also store the length of the segment. Otherwise we can't check the validity of our memory references. There are other places to store the lengths of segments as we will see shortly.
This last difference means that we have to have an allocation strategy, in exactly the same way as when we were talking about placement algorithms when we first developed location independent processes. Except this time we will talk about them a bit.
With the first fit algorithm we start searching for a section of free physical memory which is big enough. The first one we find we use.
The next fit algorithm is the same the first fit except the next time we look for a chunk of space we start from where we left off last time.
The best fit algorithm looks through all the memory and finds the chunk of space which best matches the requested size.
Sometimes the worst fit algorithm is suggested, because it leaves the biggest remaining chunk. It is interesting that simulations and real case studies have shown that the long term behaviour of the first fit and best fit algorithms are better than worst fit. First fit is usually faster.
There is one new method now (however it must be backed up by one of the other algorithms in most cases) - exact fit. Now that we have segments it is common to have certain system dependent sizes (such as the size of a disk block) which are quite common and hence it is likely that we can find an empty block of exactly the right size.
All of these methods gradually end up with some contiguous blocks of memory which are just too small to allocate as segments. Even more commonly we have memory allocated randomly throughout the real address space and we don't have enough contiguous memory for a large segment. We are going to want to be able to do something about this.
When we have a segment returned to the system which is next to another segment we want the system to join the segments together to make one larger segment (large segments give more potential for allocation). This is known as coalescing.
One way to do this is to store segments with header and trailer information inside the segment. We then link all free segments together. The header says if the segment is free or who it belongs to, it says how long the segment is and points to the next free segment (if this is free). The trailer says whether the segment is free and how long it is.
Then when a segment is returned the trailer from the previous block is checked. If it shows a free segment, the freshly returned one is coalesced with it. In the same way the next segment is also checked.
It is interesting to try to work out the long term behaviour of such a segmented system. A long time ago Donald Knuth in his classic "The Art of Computer Programming" vol 1 (I think), came up with a result now known as Knuth's 50% rule.
Basically the rule states that in a stably running segmented memory system the number of free segments is approximately half the number of allocated segments.
Because of the external fragmentation in a pure segmented system, some architectures provide paging underneath the segments.
In this case the memory at the bottom level is simple fixed sized frames. Each segment is allocated as several pages (unless it is small enough to fit within one page). Instead of the segment table providing the base address of the segment in memory it could provide the address of a page table for the segment.
Another approach (as in the Intel architectures) sees the segment table used to generate another logical (linear address) which is then turned into an ordinary physical address via a paged memory management system. Some people would claim that the Intel architecture is not a real segmentation system because different segments can overlap.
So far we have been thinking of separate memory for each process. In reality we would like to be able to have sections of memory shared between different processes. Why would we like to have shared memory?
One of the most important reasons is that we can put more processes into memory if we share some of it. For example every time a new user starts up an editor we no longer need to have identical copies of the same code in memory, we have one copy of the code shared between all the users. Of course each user will have to have their own memory for data but these days we write programs with the code separate from the data.
Similarly we can save space by sharing commonly used routines between programs. Libraries of code which are commonly used by many different programs need only be in memory once (if our system is smart enough to handle this). What does the system have to provide if we are going to have shared libraries?
Once we have shared memory we can also use it in other ways. So far we have only mentioned sharing code, what about data? Well, data can be shared for the same reason we gave above, to save space. However sharing data can also be used as a method of communication between processes. We will come back to this in the section on interprocess communication.
To share data we really need a paging or segmented memory system. Then sharing a page or a segment is as simple as referring to the same real memory address for the page or segment in the page/segment table of both processes. We don't even need to have the same address in the sharing processes for the same memory. e.g. A different segment number can have the same real memory base address stored there. We have a problem here. If the segment refers to itself, what segment number does it use?
Sharing memory is another area where segmented memory systems are superior to paged memory systems. Because a segment is a logical section of code or data, it makes sense to share it; a page could contain the memory required to be shared plus some other information which we don't want shared.
If we have shared memory, we have to be more careful than we were in the past. Up until now the memory management hardware has protected the operating system memory and the memory of other processes from anything we might do. If we are going to allow sections of memory to be shared we have to be aware of the risks.
To provide the type of protection we require here we merely extend the concept of the page (or segment) table information. With each page table entry we associate a sequence of access bits which define the protection over this page. We certainly want to know whether we can write to this page and we commonly know if we can read it or execute it.
Because these access bits are in the page table entries of each process, it is possible to give different access rights to the same page. One process may be able to write to it and several others read from it, for example.
It is worthwhile noting that these access bits are more flexible in a segmented memory system than in a paged memory system, because the program has control over its request for logical segments, whereas the pages are under the complete control of the operating system.