CS40 Operating Systems

David Morgan
Santa Monica College
see syllabus for email address



Grade information

Course outline

SMC dates/deadlines

Zoom meeting recordings

Homework schedule

Stallings book's site
 8th edition
 6th edition
 5th edition

Remote Unix accounts


 different types
 why it works
 chip schematic

Fundamental Unix Commands

System calls

Linux syscall cheat sheet

Disks & booting:
 - Linux loader doc
 - Comparative MBRs
 -Interpreting Partition Records

Old school photos

Punched cards

1959 utility bill on punched card (like those mailed to my childhood home)

Memory mgmt:
 - Segmentation
 - Page replacement
 - Intel architecture (pdf)
 - Management types

Code relocation

 - code composition
 - memory organization 


Deadlock example

Filesystem analysis

Files vs devices

Foundation concepts

ASCII chart
 version 1
 version 2

Sys. architecture (interrupts)

Number bases:
  -Hex tutorial
  -Hex advocacy
  -Binary numbers
  -Number systems
conversion tools:
  Table, or
   - binary
   - hexadecimal

 Instruction sets
    instructions A-M
     instructions N-Z
   -Intel chip architecture
    Z80 instructions
  -Other makers

  -CPU registers
  -a CPU instruction

An assembler program
  -source code

Symbol management
for compiling, linking,
and loading

Data structures


FALL 2020
Section 4106 6:45p - 9:50p Tue
online via Zoom

This Website (http://classpage.dmorgan.us/)  will be used extensively to communicate with you. Announcements, grade reports, and assignments will be posted here. Please access the website from any SMC computer lab. Alternatively, it can be viewed from an internet-connected browser anywhere. You are responsible for awareness of the information posted here

Announcements/grades/current topics

Homework -
do - reading and homework, course outline section 13. Do the "ext2 filesystem" assignment on paper, specifically on a printed copy of this dump of a floppy diskette (or use this pre-labeled version of the dump). It will be beneficial if you are able to have that copy during my related lecture, during which I will refer to it a lot.  due in your assignments directory on the remote server by the end of 12/11
reading and homework - per course outline section 13, the 9-page section of the textbook about secondary storage management.
view - the links in section 13's Reading column to articles depicting the structure of the FAT and the ext filesystems. Do not read them in any great detail, just to note the parallelism between two ways to accomplish the same thing-- having files. (12/1)

Grades - have been updated, link entitled "Grade information" at left. Includes address translation, but not yet buddy system. Please call any anomalies to my attention. (12/1)

Second test - our final class meeting will be next Tuesday 12/8. The SMC College District Calendar shows a final exam period December 15-22. We will have an online, non-cumulative Test2 on current topics, similar to our recent Test1 on the earlier topics. It will be on Tuesday 12/15. (12/1)

Homework -
read - I call your attention to Chapter 7's appendix 7A on Loading and Linking
 (part of Chapter 7, previously assigned, but don't overlook it)
do - address translation in course outline section 11due in your assignments directory by end-of-day Monday 11/30.
do - the page replacement exercise; prepare it on paper then scan or photograph it into pagerepl.jpg (or .png, or .zip or .pdf) - due in your assignments subdirectory by end of day next Friday 12/11
anticipate -  reading and homework, course outline section 13 on the subject of device and file management.  (11/24)

Grades - have been updated, link entitled "Grade information" at left. Includes no new assignments, but some individual changes. Please call any anomalies to my attention. (11/24)

Office hours meeting for any interested students, will be by Zoom Sunday, November 22, 1pm. No agenda, we can talk about anything you care to raise. (11/20)

Homework -
read - per course outline sections 11 and 12 (chapters 7 and 8)
listen - to this lecture segment about the buddy system; a homework assignment about it will follow here shortly, stay tuned...  (11/19 update)
do - buddy system homework in course outline section 11 due in your assignments directory by end-of-day Sunday 11/29.  (11/22)
 (11/17  updated 11/22)

Remaining topics - memory management (chapters 7, 8); filesystems. (11/17)

"memory3.c" memory exhaustion / virtual mem demo experiment:

  classroom dell rh (old P166) monarch V1
RAM 512 512 64 1037 64
swap 1024 1024 150 2048 313
slowdown     51   45
termination 1309/1450 1434

these are some results I got in the past on some older machines. If you wish to run the memory-exhauster programs yourself, the memory1.c, memory2.c, and memory3.c source files are in /home/public/ on the server, get them as outlined here. Compile as: gcc memory3.c -o memory3 ).

more, newer data:

  bkupserver frausto f16 vserver
OS knoppix fedora 10 fedora 16 fedora 14
kernel version 2.6.24 2.6.27 3.1.0 2.6.35
bit architecture 32 32 32 64
RAM amount 495 375 1002 7946
swap amount 0 767 11625 10446
slowdown point none ~300 ~630 ~7400
terminate point 404 1088 3044 17775

The general pattern is that the amount of physical memory available to the program is as much as is installed in the box less how much of it is already in use (by the operating system and maybe other things). Then beyond that, an amount of "pseudo-memory," apparent to the program as if physical and called swap space or virtual memory, is also available. When the program has consumed all the available physical  memory and begins to consume swap, it slows down (because using swap is using the disk). When it consumes all of the box's available swap space, the operating system gracefully terminates it. Historically overconsuming memory resulted in a system crash requiring a reboot. (11/17)

Context - put the different types of memory management we are talking about into this context.

For overlays, see link at left under heading entitled "Overlays". (11/17)

Homework - per 11/3/ posting below (11/10)

Grades - have been updated, link entitled "Grade information" at left. Includes "process states exercise" and the test. Please call any anomalies to my attention. (11/10)

Test - will be available on Canvas under "Quizzes" for a 2-day period, Sunday and Monday November 8 and 9. It is timed, once you open the test a clock is running and gives you 90 minutes within which to answer the questions. Please take the test at a time of your choosing during the 2-day interval while the test is available. (11/4)

Homework - turn your attention to these after the test
do - the "Peterson's Algorithm" assignment in course outline section 14. The platform on which to perform this assignment is sputnik.smc.edu due in your assignments subdirectory by end of day next Monday 11/16 (about a week after the test is over)
read - per course outline sections 11 and 12 (chapters 7 and 8) on memory management (11/3)

Grades - have not been updated; I owe you grades for your completed "process states" exercise. (11/3)

Mutual exclusion - why do we need it?

integer n is shared between processes P and Q

Process P 
Account receives amount nP

Computation: n = n +nP:

P1. Load Reg_P, n
P2. Add Reg_P, nP
P3. Store Reg_P, n
Process Q 
Account receives amount nQ

Computation: n = n +nQ:

Q1. Load Reg_Q, n
Q2. Add Reg_Q, nQ
Q3. Store Reg_Q, n

what's wrong?

Some possible Interleaves of Executions of P and Q:
these 2 give the expected result n= n + nP + nQ
  P1, P2, P3, Q1, Q2, Q3
  Q1, Q2, Q3, P1, P2, P3

these 5 give erroneous result n = n+nQ
  P1, Q1, P2, Q2, P3, Q3
  P1, P2, Q1, Q2, P3, Q3
  P1, Q1, Q2, P2, P3, Q3
  Q1, P1, Q2, P2, P3, Q3
  Q1, Q2, P1, P2, P3, Q3

these 5 give erroneous result n = n + nP
  Q1, P1, Q2, P2, Q3, P3
  Q1, Q2, P1, P2, Q3, P3
  Q1, P1, P2, Q2, Q3, P3
  P1, Q1, P2, Q2, Q3, P3
  P1, P2, Q1, Q2, Q3, P3


Grades - have been updated, link entitled "Grade information" at left. Includes "process scheduling exercise." Please call any anomalies to my attention. (10/27)

do - "process states exercise" per 10/20 homework posting below
read - about threads, per course outline section 10 Reading column
read - the concurrency related topic material in course outline section 8 Reading column

Process scheduling exercise explanatory lecture. (10/20)

Grades - have been updated, link entitled "Grade information" at left. Includes the "multifork" assignment (process scheduler's unpredictability) and caching (textbook prob 1.12).. Please call any anomalies to my attention. (10/20)

homework and reading in course outline section 8
do - link entitled "process scheduling exercise" in homework column of course outline section 8 due in your assignments subdirectory by end of day next Monday 10/26
do - "process states exercise" in course outline section 8; please use name "process-states.jpg" or "process-states.png" for the file you submit showing your filled-in spreadsheet due in your assignments subdirectory by end of day next Saturday, 10/31
read - about threads, per course outline section 10 Reading column
read - the concurrency related topic material in course outline section 8 Reading column
listen - to the several snippets of videos identified in the "Real-world real-time" and "Online university classes" postings below.

Real-world real-time process scheduling for self-driving cars. youtube videos:
Google's self-driving cars (8:50-13:45)
University of York research toward autonomous car operating systems (0:00-3:15)

Grades - have been updated, link entitled "Grade information" at left. Includes the "waste time" assignment (busy, resource consuming loop vs sleeping, resourceless loop). Please call any anomalies to my attention. (10/13)

Online university classes have become popular and available in recent years. I have been listening to several of the lectures in one of them recently. It's UC Berkeley's Advanced Operating Systems Structures and Implementation by professor John Kubiatowicz. In relation to process scheduling these parts of his lecture 9 apply: (40:40-43:20), lecture 10 (0:00-3:00), and lecture 11 (14:45 - ~20:00). There is  another UC Berkeley course online, that I have not listened to but seems interesting, Operating Systems and System Programming. (10/13)

Components of a process - book gives 1) program code, 2) associated data, 3) information about it (a.k.a. execution context). Compare that with this diagram. (10/13)

Test - after we finish covering the topic of processes. (10/13)

reading in course outline section 7
do - link entitled "order is unpredictable" due in your assignments subdirectory by end of day next Monday, October 19  (we may or may not have time to discuss this fully and, if not, do it nevertheless and we will discuss it in the next class after you've done it)
view - video at link entitled "process scheduler video animation"  (10/13)

Opportunity - NASA Community College Aerospace Scholars (10/8)

Grades - have been updated, link entitled "Grade information" at left. The "3+2=5 in debugger" assignment is incorporated. Please call any anomalies to my attention. (9/29)

What's wrong  
- with this video?

- with this headline's claim?


Here is what's wrong. You can't know.  (10/6)

Homework -
do - the exercise at the link entitled "waste time" in course outline section 5's Topic column. Do it in your VM. When you reach the end of the instructions, before you exit from the two terminal windows you will use, make a screenshot. I suggest you use a screenshot maker in your host computer (not the VM) for that purpose. I want to see your VM's screen, split horizontally, with the terminated exercise in the upper terminal window and the "top" utility active in the lower one. Name the screenshot timewasters.jpg or timewasters.png and upload it to your assignments directory on sputnik. Due on sputnik by end-of-day Monday 10/12.
read - textbook chapter 2
past reading - make sure that by now you have read everything in the Reading column of the first 6 sections of the course outline. When I make up a test anything in the reading to-date is potential material for creating questions.
listen - to the video at the link entitled "Time sharing" below
anticipate - next topic, after finishing chapter 2, will be processes. It will involve chapter 3 and part of 9. (10/6)

Time sharing - a way to allow multiple interactive processes to share a computer's CPU pioneered by Fernando Corbato at MIT. (10/6)

Grades - have been updated, link entitled "Grade information" at left. They include 1) the variation on textbook Figure 1.4 to incorporate devices (textbook's problem 1.1) and 2) the assembly language assignment (producing file "disassembly" on sputnik. Please call any anomalies to my attention. (9/29)

Caching - there are lots of different kinds, computer and non-computer
  memory cache
  disk cache
    inside disks themselves
    within operating systems
  virtual memory page cache
  web page cache
  instruction branch / execution order cache
  book cache (Mutlu 41:20-43:50)
  food cache (hamsters, birds)  (9/299)

Homework - 
 do the reading in the Reading column of section 4  of the course outline.
 do the assignments found in the "Homework" column of sections 4 and 5.

submittal instructions for "caching" assignment write it out on paper and submit it as a scan of that page. Name the file containing your scan caching.jpg (or caching.png). Upload that file to your assignments directory on sputnik.smc.edu. Due on sputnik by end-of-day Thursday 10/7

Some helpful explanation - here is how to correspond or reconcile the vocabulary in the textbook problem, and that at the end of my related writeup. There are 3 terms involved. What he calls T
m, I call Tslow. What he calls Tc, I call Tfast. What he calls "effective access time, I call Tave. There is no difference between what he and I are talking about, it's the same situation. The first term is talking about the native access time of one type of manufactured physical memory, and the second term about that of another. The second one is superior, does its job (moving data in and out) faster, costs more no doubt. Engineers buy that to make their caches. They buy the first, slower kind to make their RAM memory modules (regular memory) that you stick into the slots on your motherboard. The third term, on the other hand, is a little different in that it isn't talking about the native access time of anything. Rather, it's talking about the access time that would be experienced in actually using the computer. That doesn't match the native access time of either of the 2 memory types that the computer contains, since the computer uses a blend of both so that the experienced access time will fall somewhere in between their native times. Better than the slow one, not as good as the fast one. But in doing the problem just recognize that

 Tm = = Tslow

 Tc = = Tfast

 effective access time = = Tave



How interrupts save time - my in-class example put some numbers on the textbook's figure 1.5, "Program Flow of Control without and with Interrupts." I assigned time units to the various portions of the program shown in the Figure, both the 5 numbered ones and the I/O Command. Then I calculated the elapsed time from the start of the program till the time it finishes. I did that twice, once where interrupts are not used (Figure's left panel (a) ) and once where they are used (Figure's center panel (b) ). I assigned/posited the following amounts of time:
 1 - takes 6 units
 2 - takes 20 units
 3 - takes 18 units
 4 - takes 4 units
 5 - takes 4 units
 I/O command - takes 8 units

If that were the case, I reached the conclusion that the program as a whole would take 76 time units to complete if all phases ran consecutively (i.e., without interrupts) in the order shown in the Figure, versus only 60 time units if some phases ran concurrently (i.e., with interrupts). A similar question appears on an upcoming test. The question is to perform the identical analysis/calculation, but with different input numbers supplied. Be sure you can do this problem, and you'll be able to do its companion problem on the test. (9/29)

Grades - have been updated, link entitled "Grade information" at left. They include your upload of introduction.txt, and "binary math." (9/22)

Microfilm for long-term storage durability - is preferred by the National Archives (the people who keep the Declaration of Independence). A discussion of data storage durability came up in class last year. It may surprise that  for data archiving, old-school is oldest. (9/22)

Stress test SMP/multicore
- I stumbled on y-cruncher (9/22)

Homework - 
 do the reading in the Reading column of section 2 and 3  of the course outline.
 listen to the "hardware interrupts" discussion in the Homework column of section 3
 do the "variation on figure 1.4" assignment found in the "Homework" column of section 3.
Some helpful explanation about textbook's problem 1.1 at the end of the chapter. It is very similar to the one in the book in Figure 1.4 (and the matching assembly language in-class exercise we did). The difference is, he wants to get/put numbers from/to some devices, instead of memory. So, he gives you 2 new instructions (to go with the 3 you already know) in his hypothetical machine language, for the purpose of shuttling data back and forth to devices.  The instructions require id's of some kind for devices (just as memory locations require addresses, which serve as their id's). The author doesn't provide id's for the devices, but you can do so. You can make up your own id format and system. A good choice for this academic exercise might be 3-digit numbers such as 001 for device 1, 002 for device 2, and so on. Then, putting together the drawing I ask for is a matter of showing the devices and their contained values, and constructing a drawing pretty much the same as the one in Figure 1.4.)

submittal instructions submit it as a scan of your diagram. Name the file containing your scan device-io.jpg (or device-io.png). Upload that file to your assignments directory on sputnik.smc.edu. Due on sputnik by end-of-day  Monday 9/28

Homework - 
 read the first 2 readings in the Reading column of section 3  of the course outline, about instruction sets and the IA-32 Intel Architecture Software Developer's Manual.
read and view - see the posting below entitled "The answer is." In that posting are some links. Visit them all and understand what you see there.
 do the "assembly language" assignment found in the "Homework" column of section 3. It illustrates the use of numeric instructions and their interspersion with straight numbers (their operands), a centerpiece of the Von Neuman architecture.
Due on sputnik (where it is also to be performed) by end-of-day Wednesday 9/23.
catch up - on whatever reading previously assigned in these first two weeks that you didn't do yet.

VM files on Google Drive - I have asked students to download some files from OneDrive. Some of you have not yet done so or encountered problems in doing so that we have not solved.  I have placed a second copy of the files elsewhere, namely on Google Drive. I have also emailed you an access link today. Please copy it into a browser. It should take you directly to a screen offering you the files. If you have not yet obtained the files from OneDrive as originally instructed, please try to get them from Google Drive now instead. (9/10)

Dropped students - I dropped 6 students, for whom I see no sign of presence or activity. If you are among them and want to be reinstated it's easy to do, please contact me. (9/10)

What does forty-five mean? to your Intel CPU (9/8)

What does "run" mean? (9/8)

Versatility of the computer: not only can it add, it can subtract!!! - but how do we get it to do one of the tricks in its repertoire, versus some other? In the earliest computers, they were rewired to do each task:

"The ENIAC was programmed by wiring cable connections and setting three thousand switches on the function tables. This had to be done for every problem and made using the machine very tedious." 

the term for setting the computer to do some certain task is "programming the computer."
see "Programing the ENIAC"

Do modern computers re-wire in order to set and determine what they will do? (9/8)

Homework - please
do -  the "transfer" found at the top of the homework column of course outline section 1. The purpose is to make sure you become accustomed to using the remote server and moving files to it, so that you can submit other homework files there in the future.   due date (file on remote server) Wednesday September 17 end-of-day  
 do - the "binary and hexadecimal addition problems" assignment found in the "Homework" column of section 2 of the course outline.  due date (file on remote server) Wednesday September 17 end-of-day  
read - about the hex dump tools, related links in the homework column of section 2
read - the readings in sections 1 and 2. (9/8)

Recording link for tonight's Zoom meeting. (9/1)
[ see link at left entitled "Zoom meeting recordings" ]

Architect Philip Johnson surfaces and illusions (9/1)

Course outline - with approximate weekly topic coverage corresponded to related readings, homework assignments, and in-class slides I will use. Please follow this outline as we move through the topics, for assignments and reading I will want to assign.

First homework
do - all the activities in section 1 of the course outline. Visit each of the links, read and listen to the indicated materials. (9/1)

A virtual machine (VM) for you - hands-on lab exercises will be performed on a virtual machine that you can run in your own computer.
- Obtaining and installing your VM
- Transferring files in and out of it if necessary
- Your VM's configuration

A Remote Unix system account is available for your use.

Internships - a link I have been asked to publicize to students. (8/30)

Using ssh (secure shell). ssh is an important tool you will use for interacting with remote computers. For that you will need an ssh client. There are a number of ssh client alternatives.

Distributing files from sputnik to the class as a whole,  publicly - the above file transfer discussion describes file movement to and from your own home directory, exclusive to you. Sometimes I will want to have someplace to put a file so everybody can get to it and download it. When I do that, here's how to download them.

Three revelatory pictures - I will refer back to them a number of times during our class. Each depicts relationships that, if learned early, will clarify your understanding of computers
 1 - Role and position of an operating system

 2 - Devices, and friends - partition tables, partitions, filesystems, files

 3 - Liftoff - how the computer picks itself up by its bootstraps in the morning

The answer is ... (read the lights),  what is the question? Let's understand what this picture shows. The device shows a project for adding 6 and 5 to produce 11. Here are "6 and 5". And here is "11".
Listen to this video from the 7:30 timing mark to the end, describing addition with switches for inputting addends, lights for outputting sums, and a 74xx Texas Instruments chip to hold the "wiring" that does the math.
74xx chip in 1962? No such thing. My classmate then made a science project that did the same thing as in the above video: switches to input addends, lights to output sums. But how did he make the math happen? He built the same functional circuitry as contained in 74xx chips, from basic discrete circuit components ( resistors, capacitors, inductors, diodes, transistors ). The circuits he wired up are as shown here in the several kinds of "logic gates" (scroll down to the circuit diagrams) and further described here.
Here is another discrete component enthsiast/purist's page

First personal computer - Altair by Ed Roberts

Altair - first personal computer

(click photo to enlarge, note switches and lights on front panel)

Fedora linux installation - time permitting I hope to demonstrate the installation of an operating system on a laptop in class.

Jobs for which operating systems have responsibility:
  memory management
  process management
  device management
  file management
  user interface

Textbook - Operating Systems: Internals and Design Principles, eighth edition, William Stallings, Pearson Prentice Hall. See the information about it on the author's website.  

Foundation concepts you should be(come) familiar with as background/prerequisite for this class:
 Data structures (lists, stacks)
 Binary and hexadecimal number representation
 Compiling/linking/loading (symbols, address fixups)
 ASCII code
 Processor instruction sets
 System architectures (bus, data lines, interrupt lines)
 Use of ssh
 Use of sftp for file transfer

Running linux at home.



Milestones in the history of computation

Tommy Flowers

Tommy Flowers

Colussus - 1944

Colossus - 1944



Eniac - 1946

Eniac - 1946 -