CS40 Operating Systems

David Morgan
Santa Monica College
see syllabus for email address



Grade information

Course outline

SMC dates/deadlines

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

Remote Unix access with ssh

Using scp/sftp


 different types
 why it works
 chip schematic

Fundamental Unix Commands

System calls

Linux syscall cheat sheet

Disks & booting:
 - Partitioning primer
 - Linux loader doc
 - Comparative MBRs
 -Interpreting Partition Records
 - Future of BIOS

Sys. architecture
(disk organization)

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)

Sys. architecture
(disk organization)

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

 Instruction sets
    instructions A-L
     instructions M-U
   -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
  - Datastructures
  - Linked list of states


FALL 2018
Section 4113 6:45p - 9:50p Fri Bus 263

This Website (http://homepage.smc.edu/morgan_david/)  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

Thank you - for taking this course. I hope what you learned will serve you well. (12/14) 

Other classes I teach - There is a related class that follows on from this one in a sense, a detailed exploration of the linux operating system specifically. It is less theoretical, more practical and hands-on than CS40. It might interest some of you. You can get a very concrete idea of its content, by which to judge, since the final website remains online from last time I taught it. It is:

CS41 - Linux Workstation Administration (3hr credit, traditionally offered each Fall but not this year. Scheduled for Spring 2019)

I also teach other SMC courses less directly operating-systems-related but also of possible interest to you. They are:

CS70 - Network Fundamentals and Architecture TCP/IP networking (3hr credit, next offered Spring 2019)

CS75 - Network Protocols further depth and variety on the topic beyond CS70 (2hr credit, next offering unscheduled)

CS78 - Secure Server Installation & Administration (3hr credit, next offering unscheduled.)
In this class, with cooperation from USC/ISI, we will have accounts on the DETER testbed where we will create remote test networks (comparable to using cloud services). (12/14)

Grades published, complete and up-to-date as of  this afternoon to the best of my knowledge. Please see link entitled "Grade information," at left. There may be errors or omissions so please check your grades and call any anomalies to my attention.  (12/14)

Final exam date - Friday, December 14, in our classroom at class time. Here is the school calendar. Please bring a scantron form #882 (12/7)

Homework -
do - the page replacement exercise specified in the Homework posting below dated 11/30.
read - 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/7)

Grades - updated, to include address translation. Please call any anomalies in the grades to my attention. (12/7)

"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. (12/7)

Summary of topics for our final two regular meetings

Processes (loose ends)
 demo: conclude semaphore demonstration
 demo: threads

Memory Management
 - addressing
 - paging
 - virtual memory

 demo: memory exhaustion and effect of virtual memory

 homework: addressing
 homework: paging


 demo: device vs file

Homework -
do - homework in course outline section 11, address translation which now has a due date (see "Homework" posting below dated 11/16)
do - page replacement exercise, course outline section 12 - due on on paper in class at next week's meeting 12/7 if we cover the topic tonight or, at your option whether we do so or not, on final exam night 12/14.
read - per course outline sections 11 and 12 (chapters 7 and 8)
anticipate - topics upcoming per course outline. (11/30)

Grades - have been updated, link entitled "Grade information" at left. They include the  the recent test. (11/29)

Devices, etc. - understanding distinctions among these entities is fundamental to understanding what you are partitioning when you partition, what you are formatting when you format, what you are mounting when you mount, what you are encrypting when you encrypt. People often confuse them.

Western Digital manufactures hard disks
Given a hard disk, grub manufactures a partition table
Given a partition table , fdisk manufactures a partition
Given a partition, mkfs manufactures a filesystem
Given a filesystem, vi manufactures a file (11/30)

Grades - have been updated, link entitled "Grade information" at left. They include the  the process scheduling problem. (11/16)

Homework -
read - per course outline sections 11 and 12 (chapters 7 and 8)
do - homework in course outline section 11, address translation due in your assignments directory by ... t.b.d pending class coverage end-of-day Thursday December 6. (I will try to include it in published grades by the following evening's class.)

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

No class meeting November 23 - SMC observes Thanksgiving.
Remaining calendar - meetings November 30, December 7
Final exam date - December 14   (11/16)

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/16)

Test - November 16. Please bring a scantron form 882 (green) available from the school bookstore. (11/3)

What's wrong with this headline's claim?


Test - probable 11/9. I will talk about it next week 11/2. Please bring a scantron form 882 (green) available from the school bookstore. (10/26)

reading in course outline section 7
homework and reading in course outline section 8. process scheduling exercise due in your assignments subdirectory by end of day next Saturday 11/3 (gives you opportunity to raise any questions in class Friday 11/2 if you wish) (10/26)

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)

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 I may play for us in class parts of his lecture 9 (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/26)

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


Demonstration programs for unix process mechanism "fork/exec"
- If you wish to examine or experiment, here is the series of 11 programs used in my slides demonstrating the workings of fork and exec. You can get them from the unix server under the same names by which they appear in the slides shown in class: fork1.c, fork2.c,..., fork11.c. (Files are in /home/public/molay/ch08/, get them as outlined here. Slides are at links, lower left, entitled "Processes" and "Homemade shell". If you download these source files and want to compile so you can run them, the command to compile would be, for example:

  gcc  fork1.c  -o  fork1

The summary of the point of these programs is:

Version Purpose
fork1 shows fork, demonstrates that 2 processes result
fork2 shows PIDs (process id numbers) of these processes, and that they're distinct
fork3 shows fork's return value to the child copy (zero) and its return value to the parent copy (child's PID)
fork4 shows how to code differentiated behavior via an "if" structure conditioned on fork's return value
fork5 incorporates an exec call in the child
fork6 introduces exit call in child and wait call in parent, to give orderly discipline to their relative timing
fork7 gets the name of the program to be exec'd from the user via the command line
fork8 interactively gets the name of the program to be exec'd by prompting user
fork9 puts the activity inside a loop to extend it to second, third, fourth,... commands
fork10 shows a zombie process
fork11 shows an adopted child, init process as its step-parent after being pre-deceased by its original parent


Dropped from class - Alfaro, K. Brown, Ladhar, Lindsay, not participating. (10/19)

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/19)

Upcoming topic - will be processes - after we do Chapter 2
read - textbook chapters we will cover on the topic of processes. Those are chapters 3 and 9 (process scheduling; through p. 415)).
anticipate - assgt in course outline section 8 at the link entitled "process scheduling exercise," to be done later, after I have demonstrated how to do it in class. (10/19)

Grades - have been updated, link entitled "Grade information" at left. They include the  the caching problem. (10/19)

Homework -
 read - complete Chapter 2
 listen - the video at the link entitled "Time sharing" below.
 anticipate - next topic, processes, chapters 3 and part of 9 (10/12)

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

Grades - have been updated, link entitled "Grade information" at left. They include the variation on textbook Fig. 1.4 but not the caching problem. (10/12)

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)  (10/5)

Grades - have been posted, link entitled "Grade information" at left. I believe I have correctly published your anonymous student ID numbers by which you cal look yourselves up. (9/28)

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. Caching assignment due on paper in class 10/5.

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/28)

Grades - have been posted, link entitled "Grade information" at left. (9/21)

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  old school is oldest. (9/21)

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

Homework - 
 do the reading in the Reading column of section2 and 3  of the course outline.
 do the 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.)

due dates - there are 2 assignments in section 3 homework column. Please perform the first, "some assembly language," on sputnik by the end of the day Tuesday 9/25. It leaves the result on sputnik. Please do the second, "make a variation..." on paper and submit it in class Friday 9/28 if you can do it - if you feel you cannot, because I did not adequately cover it in class last night, we can defer the due date for you - to 10/5 meeting (9/22)

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

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

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/7)

Homework - please
 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) Tuesday September 18 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/7)

Luddites - symbols of interaction between technical change and its social impact. (9/3)

Accounts created - per the link below entitled "Remote Unix system account". Please do the homework item (under the link "First homework" below) that asks you to perform an initial login. (9/6) 

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 want you to do (8/31)

Role and position of an operating system (8/31)

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. (8/31)

First homework - please
 read chapter 1 of the textbook. Slowly. Twice.
 read the 7 links about binary and other number systems, below left, under the heading "Number bases" in the "Foundation Concepts" section.

read - write-up at link entitled "Remote Unix access with ssh" at left, and then:
log in - to your remote unix account. Please see section here entitled "Remote Unix system account for you". I will see your login history and record a minor grade credit for your having logged in. Log in by the end of Friday 9/21. After logging in, get out by running the "exit" command.

listen - to this podcast about operating systems (skip the part from the 6:00 minute mark to the 39:00 minute mark). It spans a lot of topics that we'll encounter in coming weeks, in a broad summary touching on all the items on the OS's job description list (the ones in paragraph titiled "Jobs" below). You won't understand some of it, and I considered not asking you to listen to it on the grounds that it bites off more than you can chew. But that's what the coming weeks are for. Listen to it now. Then, it would be interesting if you did so again after the course to see if I taught you anything.

anticipate, from assignment 1.5, the book's problem 1.1 at the end of Chapter 1, by reviewing the instruction execution example in Figure 1-4 of the textbook and associated discussion. (8/31)

First personal computer - Altair by Ed Roberts

Altair - first personal computer

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

PCBSD installation - time permitting I hope to demonstrate the installation of an operating system on a laptop in class. I'll use PCBSD. See this related YouTube video and PCBSD's website (the project has changed its name to TrueOS). (8/31)

Virtual machines - on class laptops (screenshot).

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. (8/31)

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

Handout - explaining use of class computers.

A Remote Unix system account is available for your use. 

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.

Running linux at home.



Milestones in the history of computation

Tommy Flowers

Tommy Flowers

Colussus - 1944

Colossus - 1944



Eniac - 1946

Eniac - 1946 -