Papering over not having enough memory

Start with the days before virtual memory. Main memory was divided into partitions and programs were placed one to a partition.

There were two ways of dividing it.

• Fixed partitioning … divided into sizes settled in advance. Put a small program in and the remainder is wasted
• Variable partitioning … divided to fit each program exactly. Less waste, but repeated placing and removing leaves it full of gaps

That phenomenon of "a great many small free areas appearing" is fragmentation. The trouble it causes is that although the free space adds up to enough, no contiguous area can be found, so the program cannot be placed.

Gathering the scattered contents to one side and consolidating the free space into a single large block is compaction (memory compaction). Fragmentation is the symptom and compaction is the treatment.

The idea that came out of this is virtual memory. The program is shown a false map saying "there is plenty of memory", while in reality main memory and auxiliary storage are combined to make do.

• Virtual memory space (virtual address space) … the larger map, as the program sees it
• Real memory (main memory) … the smaller place where things can actually be loaded

What matters is that the OS does all of this mapping. Whoever writes the program does not have to build in a module for using virtual memory or configure it per application. That is why the 20 GB game runs on 4 GB of memory with nothing special done.

But it is not free. If too little fits in main memory, all the swapping work makes it slow. That comes up in a later slide.

How are virtual memory and real memory mapped to each other? What is mainly used today is paging.

The method is simple: divide both the virtual memory space and the real memory space into fixed-length areas of the same size and manage the correspondence between those areas. A fixed-length area of this kind is a page.

Making them fixed-length is the trick. With sizes all equal, any page can go into any frame, so the fragmentation from before cannot arise. There is no need to "look for a place it fits exactly".

The correspondence is held in a page table, used to look up a real address from a virtual one. For a page not in real memory, the table records where in auxiliary storage it is.

When a program tries to touch an address, the page may not be loaded in real memory. What happens then is a page fault.

The sequence after that is this.

• Control passes to the OS (an interrupt occurs)
• The needed page is read from auxiliary storage into real memory (page in)
• If there is no room, something is evicted to make space (page out)
• The original instruction is executed again

So a page fault occurs when a page not present in main memory is accessed. Touching a page that is properly loaded, however many times, does not cause one, and neither does touching a page you have not touched for a long time. The only condition is whether it is loaded.

Reading and writing auxiliary storage is orders of magnitude slower than main memory, so more page faults translate directly into lower throughput.

When real memory is full, somebody has to go before a new page can come in. How that is chosen is the page replacement algorithm.

Two mainly come up in the exam.

• FIFO (first in, first out) … evict in the order they arrived. Whichever page has sat in real memory longest goes
• LRU (least recently used) … evict the page for which the longest time has passed since it was last referenced

The wording around LRU carries a lot of traps, so pin it down. What it looks at is the time it was last used. Not the time it arrived (that is FIFO), and not how many times it was used (that is LFU).

"Not referenced for a fixed period" also gets lined up, and that is wrong too. LRU does not decide by a time threshold; it picks the oldest among the candidates.

A calculation question falls out by writing one line at a time listing the frames in order of age. Skip the table and do it in your head and you will get it wrong.

The procedure is only this.

• If the referenced page is in a frame, that is a hit. Move that number to the newest position
• If not, add it to the frames. If the frames are full, evict the page in the oldest position

Follow four frames with the references 1,2,3,4,5,2,1,3,2,6. The left-hand side is the older end.

By the time 6 is touched, the one in the oldest position is 5. It was never referenced again along the way, so it was overtaken in turn by 2, 1 and 3.

Raise the number of programs running at once (the multiprogramming level) and each gets fewer page frames. Cut it too far and a page that is brought in is evicted at once and read back again, over and over.

That state is thrashing: page-ins and page-outs happening constantly, with most of the processing time spent swapping. Only the work of the OS (the overhead) grows, the processor utilisation for applications falls if anything, and response degrades sharply.

Since adding work reduces output, the counter-intuitive part is what gets asked about. Raising the multiprogramming level does not necessarily make things faster.

Keep the neighbouring terms apart.

• Memory leak … a bug where allocated main memory is never released. The usable area shrinks steadily
• Overlay … a technique for loading into main memory only the module that has become necessary, where the program area is limited
• Roll out … saving a running program wholesale to auxiliary storage

Now the auxiliary storage side. The arrangement for keeping files in order is the file system, and its skeleton is a tree.

The branching nodes are directories (folders). Learn three whose names are fixed.

• Root directory … the very base of the tree. Written as a single /, the top of the whole hierarchy
• Home directory … the patch allotted to one user. The top of the hierarchy that person uses for keeping files
• Current directory … where you are standing. It is what you moved around with cd in the CLI course

Watch the difference between root and home. Root is the top of the whole system; home is the top of what that user can use. An ordinary user cannot write into the root as they please, so what you ls around in is usually inside home.

The route describing where a file is is a path, and there are two ways of writing one.

• Absolute path … the route from the root directory to the target. The same string from wherever you look
• Relative path … the route from the current directory to the target. Change where you stand and the writing changes

An absolute path is defined as "from the root". "From the current directory" is a relative path, "from home" is not it either, and neither is "whichever is shortest".

Two symbols are used in a relative path: . is here and .. is one level up. Line up as many .. as you like to climb that many levels.

The knack for working it out is writing the current directory down and rubbing out from the right, once per ... Join the rest of the route onto what is left and you have the absolute path.

The exam sometimes writes the separator as something other than /, but the thinking is the same.

A backup is the copy you take so you can get back after a breakage. There are three ways of taking one.

• Full backup … take every file every time. It eats time and space, but restoring takes a single set
• Differential backup … take the files changed since the last full backup
• Incremental backup … take only the files changed since the backup taken immediately before

The only difference between differential and incremental is where the count starts from. A differential counts from the full backup each time, so each run grows fatter as the days pass. An incremental only covers since last time, so each run stays slim.

In exchange, the effort of restoring is reversed. A differential restores from two sets, the full plus the latest differential, whereas an incremental needs the full plus every incremental since, applied in order. Whichever is quicker to take is slower to restore.

The OS keeps a mark per file saying "updated since the last backup". An incremental resets that mark after taking a backup. A differential wants the same range next time, so it leaves the mark alone.

Last, the promises around using software. OSS (open source software) is software whose source code is published and which may be modified and redistributed.

Note that it does not mean "free software". The conditions of OSS are that a third party may redistribute it as a product, and the original developer may not charge a licence fee for that. Narrowing the disclosure to one industry also falls outside the definition of OSS.

Licences fall broadly into two families.

• The BSD and MIT licences … you may modify and incorporate without publishing your own source
• The GPL … if you redistribute after modifying, the derivative must be published on the same terms. That idea is called copyleft

What trips people up with the GPL is the scope. The obligation arises when you redistribute. Merely using a modified version inside your own company, even if you contracted the modification out, creates no obligation to publish.