| 1 | due: Sun 28th January. | A simple program in BCPL. | |
| 2 | due: Thur 22nd February. | Properly maintain a free block list. | |
| 3 | due: Sun 3rd March. | Create a level 1 index file system. | |
| 4 | due: Sat 20th April. | Much improved file system. | |
| 5 | due: Thur 9th May. | Communicating programs. |
| Quick introductions. Two points of view, operating systems are about making the computer convenient and safe to use, but can be thought of as virtualising the hardware. Looking at a little BCPL program and single-stepping through it to see stack frames being created. These are the BCPL and CPU details we saw today. | ||||||
| A lot of progress with BCPL, we start next time at section 34. | ||||||
| Finished BCPL, included two binary tree implementations. | ||||||
| Starting up, what is usually responsible for memory allocation? Historical things tht are still relevant (to varying degrees): Magnetic tapes, drums, and discs: one, two, three, four, five, six, seven. Why data has to be organised into blocks, probability based. BIOS, CHS, access speed; contiguous allocation file systems. | ||||||
| How magnetic tapes are used to give access to real files in the Unix system. Example of writing and reading a tape file. IOSB, a much better way of organising things. Quick look at simplest possible disc system: superblock, root dir, and one block files. | ||||||
| (slight changes to iosb: unreadch, readline, abandon, extra exports). Trivial one block disc files: illustrating things with a tiny interactive shell. One way to make large files is with a linked list of blocks. Each block of a file has only 508 bytes of real data, the other 4 bytes contain the block number for the next 508. Good because simple and unlimited. Bad because exceptionally slow for random access. | ||||||
| Dean's special event. (od improved -ta and -A d) DO THE CLASSROLL Schemes better than a linked list of blocks. Directory entries: big or little? Microsoft's original design (bottom of page 3). Can't look at Unix directories any more. The point of clusters and partitions. Unix's hard and soft links, the usual structure of a directory, a file's meta-data. How to connect a large number of blocks as a file with reasonable access times and size limits. Buffering pointer blocks, why deep structure does not really increase serial access time. | ||||||
| Review of the tree-like file structures, terminology: header block, N level index. Changing the number of levels is very easy. Why are clusters and partitions still used? Which blocks are free to be used? FAT no good; bit per block only if small; make them into a dummy file. | ||||||
| I-nodes. a-time, m-time, c-time, birth-time (man 2 stat). Runs, used by windows NTFS now but made big by files-11. Defragmentation has become important again. ReiserFS, a file system for murderers, a rough picture. | ||||||
| A bit of practice with an alternative way of keeping track of free blocks: devote a number of consecutive blocks to storing a list of the block numbers for all the free blocks, treat it as a stack, | ||||||
| Mount points, files that are not files, journalling. RAID. SSDs and discs, failure modes. | ||||||
| Have I solved the mystery of the SSD access time? Stack management: easy because we've mostly done it already. Memory technology: M1, M2, N1. C1: C2, C3, C4, C5, C6, C7. A very primitive but mostly workable implementation of virtual memory. | ||||||
| Do the classroll. Virtual memory, virtual address, physical address, address translation. Multiple segments. Pages. Intel's 32-bit scheme, (CR3; 10, 10, 12). Translation look-aside buffer. | ||||||
| Our virtual machine's virtual memory model, (PDBR; 10, 11, 11). The big picture, VM is use with two processes. The registers and special flags. | ||||||
| Doing something real but basic with virtual memory. | ||||||
| Building page-tables, running an almost-process. Too much recursion outgrew the stack and caused a page fault. Adding an interrupt handler to catch the page fault and enlarge the stack. | ||||||
| Non-resident pages, another aspect of vitual memory. How to do page allocation under Unix. Memory mapping files, both data and executable, load on demand. | ||||||
| Doing something more practical with programs and VM. | ||||||
| More clever stuff. Even more. | ||||||
| Being a grown-up programmer, Using the emacs editor. A few more steps before getting more abstract. How are we going to handle multiple processes? Process Corntrol Blocks, What goes in a PCB? process states, register values, and so on. | ||||||
| (backspace and delete now work with emacs) The life-cycle of a process (a Unix process that is). What could possibly go wrong here? Race conditions, critical sections, Atomic operations, Mutexes. | ||||||
| Various atomic test and set instructions and how they are used: Intel, VAX: remqhi, sobgeq, DEC-10: SOSL. P and V, mutexes and semaphores, usually semaphores are made out of mutexes. Queues of sleeping processes, added to by unsuccessful P, V wakes one up. Shared resources protected by mutexes, the card-reader/line-printer deadlock. Introducing the dining philosophers, identified the problem but that's as far as we got. | ||||||
| A lot more about the new filesystem assignment. What to do about the dining philosophers and how that relates to operating systems. Butlers, footmen, fork-boys, but in general the conditions that lead to deadlock can't be known. Monsters and murderers are required, detecting deadlock once it has happened can be done. Off-line processing makes the problem go away in many cases. Requiring ordered allocation of resources also prevents the problem from arising. | ||||||
| Some shared single user devices: card reader, (codes),
line printer, graph plotter. Interprocess communication through shared memory with a mutex. P and V by software: 0, a, b, c, d, e, f. Monitors. | ||||||
| Tricky stuff to do with processes. Some debugging help. | ||||||
| Heaps. The Buddy system illustrated. | ||||||
| The ugly email attachment in case there are any questions. Techniques for creating virtual machines. | ||||||
| Garbage collection. words. |
