EEw360P/w380L.6  Interfacing to Operating Systems    Summer 1999
Class: ENS302 MWF 10-11:30am
EE360P Unique Number: 77070               EE380L.6 Unique Number: 77117
Instructor:      Jonathan W. Valvano
          Office: ENS617A, 471-5141
          Research Lab: ENS619/621, 471-1216
          Office Hours: MWF12-1
          email: valvano@uts.cc.utexas.edu
Web page    http://www.ece.utexas.edu/~valvano
TA:          TBA
Engineering Library reserve:
          Silberschatz, Operating System Concepts, 1994
          Hans-Peter Messmer, The Indispensable PC Hardware Book, Addison-Wesley, 1995
          Microsoft, MS-DOS Programmer’s Reference, Microsoft Press, 1993
HKN:    Valvano, EE360P Lecture Notes, Summer 1999
Text:     Silberschatz, Operating System Concepts, 1994
Course Topics:
     1. Introduction to operating systems
     2. Introduction to IBM-PC hardware
          architecture , assembly language programming
          gadfly, interrupts, DMA
     3. Real-time programming in C
          data structures, quality software, hierarchical programming, software latency
          mapping into 8086 assembly language, software traps, hardware interrupts
     4. Process and processor management
          scheduling, synchronization, deadlock
     5. Memory management
          contiguous allocation, compaction, paging, segmentation, virtual memory
     6. I/O device drivers:
          installation, trap handlers, interrupt handlers, redirection, filters
          parallel port, serial port, floppy disk
     7. File system management
          allocation, free space, performance, directories
Cognitive Objective Categories
1. Knowledge, the repetition of facts
2. Comprehension, the ability to paraphrase into one’s own words
3. Application, the ability to apply a general principle to a new specific instance
4. Analysis, the ability to identify component parts
5. Synthesis, the ability to create a new system out of components
6. Evaluation, the ability to make critical judgments
Affective Objective Categories
1. Willingness to receive and incorporate new information
2. Acceptance, organization and commitment to a value system
Prerequisites: EE360C with a grade of C or better. Many students will also have had EE345L (it is suggested but not required). EE345L topics in this class include interrupts, keyboard interfacing, software traps, and real time clocks. It is OK if you know C but not C++. In this case, you will be required to put in some additional work to catch up (the texts for EE312&EE360C are recommended.)
Cheating: Cheating is very uncivilized behavior and is to be avoided at all cost. Cheating is defined as "any time you put your name on someone else’s work". You are allowed to talk to your classmates and previous students about the assignments. It is considered scholastic dishonesty to look at the written work of any student other than the member of your lab group. Oral discussion about an assignment is encouraged and is not considered to be cheating. Copying of any part of a program is cheating. If two programs are found to be copied, there will be a substantial penalty to both students, e.g., failure in the course. Students who cheat on tests will fail. Prosecution of cases is very traumatic to both the student and instructor. PLEASE DO YOUR OWN WORK. Policies concerning the use of other peoples’ software in this class:
     • I strongly encourage you to study existing software.
     • All applications and libraries must be legally obtained. E.g.,
          You may use libraries that came when you bought a compiler.
          You may use software obtained from a BBS or on the WWW.
          You may copy and paste from the existing source code.          
     • You may use any existing source code that is clearly referenced and categorized:
          original: completely written by you,
          derived: fundamental approach is copied but it is your implementation,
          modified: source code significantly edited to serve your purpose,
          copied: source code includes minor modifications.
Grading:     40% Six Laboratory assignments
          25% In class closed book Midterm, Monday, 7/12, in class
          35% Closed book Final, Saturday, August 14, 9am-12n, Room regularly scheduled
There will be no re-tests, make-ups, or incompletes. An average above 70 is required to receive a credit (CR/NR). Lab performance (effort, debugging skills, and citizenship) as observed by the TA will be used to decide course grades in borderline situations.
Laboratories: There are six lab assignments to be implemented on an actual computer and demonstrated to the TA. Any machine in the building that allows C or C++ software development including setting of software interrupt vectors, establishing a periodic hardware-based real time clock interrupt and generating interrupt-driven I/O is adequate. Most students will develop C++ programs that run on an IBM-PC compatible and executed under DOS. See the TA for more information on the specific grading policy and late penalties for the lab assignments. You will perform the lab assignments in a group of two. I do not recommend you attempt to perform the assignments alone. The TA will give a lab demonstration. Report machine failures to the proper authorities.
General: Attendance in class is expected. In this class, a large part of the material is not in any one book. If you miss class you may find it difficult to catch up. All software for lab, and tests must include comments. The purpose of groups is to encourage the students to help each other. If you work in a group, the group turns in one solution stapled together with both names on it. The paper will receive one grade, and both members receive that grade. I expect that both members of the group to contribute. The group partners do not have to be approved in advance and may change week to week. The maximum group size is two.
Software Grading SHEET
     50% Demonstration of the software (graded by the TA)
          Does it satisfy the stated objectives?
          It is better than the expected?
          Hardcopy printouts of your software is required at demonstration
          All group members must be present      
     50% Software quality (graded by the TA/Valvano)    
          Proper data and program structures:
          Well-structured modular software:
          Descriptive labels:
          Top-down or bottom up structure:
          Interface to the user:
     Late Penalties (5% 1-2 working days, 10% 3-5 working days, 30% over)
          Working days include M-F, but not Saturday, Sunday and UT holidays
Legal Stuff: Drop date is June 16, 1999. After this date, I will sign a drop card only if it has been approved by the Dean. Your current grade status must be a "C" or better for you to receive a "Q". Course/instructor evaluation is conducted on the last class day in accordance with the Measurement and Evaluation Center form. The final exam is at the time and place stated in the course schedule. The University of Texas at Austin provides upon request appropriate academic adjustments for qualified students with disabilities. For more information, contact the Office of the Dean of Students with Disabilities at 471-6259, 471-4241 TDD.
Summer 1999 EE360P/EE380L.6 schedule
June 4-11
     Lecture Notes Sections 1, 2, 3
     Intel x86 real mode instruction set
     Messmer Chapters 1, 2, 3.1, 3.2, 3.3, 3.4 (real mode)
     Silberschatz Chapters 1, 2, 3
June 14-18
     Lecture Notes Sections 4, 6, 9
     Intel 8253
     Messmer Chapter 24
     Silberschatz Chapter 8
June 21-25
     Lecture Notes Sections 5, 8
     Intel 8259
     Messmer Chapters 3.6, 23.1, 23.2, 23.3, 31.1
     Silberschatz Chapters 4, 5
June 28-July 9 (no class July 4)
     Lecture Notes Section 7
     Silberschatz Chapters 6, 7
July 12 Closed book Quiz in class on all material covered so far
July 14-30
     Lecture Notes Sections 10, 11
     Intel 8237
     Messmer Chapters 25, 27
     Silberschatz Chapters 10, 11
August 2-13 (no class on July 25)
     Lecture Notes Section 12
     Intel 386 protected mode
     Messmer Chapters 3.7, 3.8, 3.9
     Silberschatz Chapter 9
August 14, 9am-12noon, Closed book, Final regularly scheduled on all material
Lab1 Command Interpreter/FIFO Queue     100 points due 6/11 (easy)
Lab2 Assembly Lang and Real Time Meas   100 points due 6/18 (easy)
Lab3 Memory Manager                  100 points due 6/25 (moderate)
Lab4 Device Drivers                    150 points due 7/9 (hard)
Lab5 Preemptive Thread Scheduler        200 points due 7/23 (hardest)
Lab6 Floppy Disk File System           150 points due 8/6 (hard)

Midterm exam study guide Simple Definitions
process
    heavyweight process
thread
    lightweight process
multiprocessing
context switch
real time systems
    hard real time systems
    soft real-time systems
local variables (8086 code):
    binding
    allocation
    access
    deallocation
What is a data structure?
    vector, string, list
    array, table
    LIFO, FIFO
     fixed allocation
     dynamic allocation
    double buffer
    linked list
        single linked lists
        double linked lists
    binary tree
What is an object?
    encapsulation of data and methods
    message handling
information hiding

nine phases of software development
    discover requirements/constraints
    build conceptual model
    estimate cost/schedule/performance
    preliminary design
    detailed design
    implementation
    optimization
    validation/debugging
    maintenance
latency
throughput/bandwidth
I/O synchronization
    blind cycle
    gadfly/polling
    interrupt
        polled
        vectored
    periodic polling using RTI
    DMA
debugging terms
    stabilize
    performance debugging
    functional debugging
    intrusiveness
    invasiveness
separation of mechanism and policy
layered OS
microkernel OS
Gantt chart
indefinite blocking/starvation
aging
CPU bound process
    histogram
I/O bound process
    histogram
process mix
cascading termination
CPU burst
I/O burst
dispatch, dispatch latency
time quantum
priority inversion
    priority inheritance protocol
critical code
    mutual exclusion
    bounded waiting
test and set instruction
atomic operation
fragmentation
    internal
    external
device driver
resident device driver
installable device driver
character vs block device
software interrupt (8086 code):
    passing parameters
    handler address
    local/global variables
device driver installation
    resident
    explicit installation
    Plug and Play
        serial PROM
device driver specifications
    define data structures
    specify calling sequence
    interrupt handlers
    filters, redirection
programmable I/O interface parameters
    address decoder
    interrupt request lines
    DMA channel numbers
I/O functions are traps to OS
I/O interrupt handlers
    replace/capture vs append/chain
    data structures
    error handling
    set up its own stack?

Midterm exam study guide Concepts/Algorithms/Techniques
relocatable code
    what
    why and
    how?
local variable
    registers
    stack
global variable
parameter passing in C
    8086 assembly instructions
    value and reference
reentrant programming
    what
    why and
    how?
modular/structured programming
    what
    why and
    how?
top down versus bottom up
    what
    why and
    how?
elegant software
    what
    why and
    how?
program verification/testing
interrupt concepts
    when/why to use interrupts
    steps occurring during context switch
    polling versus autovector
    parameter passing
    local variables
    round robin polling
    arm versus enable
    interrupt priority mask
    hardware vs software acknowledge
    trap or software interrupt
context switch
thread/process management concepts
    creation/deletion
    suspension/resumption
    synchronization
    communication
    deadlock handling
thread control block, TCB
    ready, blocked, running, terminated
    What goes in the TCB?
    queues of TCB’s
scheduling performance measures
    CPU utilization
    throughput
    turnaround time
    waiting time
    response time
scheduling algorithm concepts
    nonpreemptive/preemptive
        FCFS
        SJF
        priority
    preemptive round robin
    real time
proof that SJF minimizes waiting time
methods to predict next CPU burst time
Little’s formula
semaphore
    Dijkstra: P,V
    binary and counting
    spinlock vs blocking
producer/consumer problem
    bounded buffer
dining-philosophers problem
readers-writers problem
deadlock concepts
    necessary conditions
        mutual exclusion
        hold and wait
        no preemption
        circular wait
    resource allocation graph
        assignment edge
        request edge
        claim edge
    prevention
    avoidance
        resource allocation graph
        banker’s algorithm
    detection/recovery
    safe versus unsafe
first fit and best fit memory manager
merging
compaction
protection, user/supervisor mode
    CPU, memory, and I/O protection
    
Final exam study guide Simple Definitions
mapping of logical into physical devices
    partitions

file types
    source, object, executable, batch,
    text, library, print, archive, picture,
    sound, movie

file attributes
    name, type, location, size,
    protection, time, date,
    creator/magic number

packing logical records into physical blocks
file sharing using an acyclic graph
file block/sector vs cluster
file control block/descriptor
file system mounting
best-fit vs first fit file allocation
virtual/RAM disk
motivations for paging
    external fragmentation
    virtual memory
    sharing
    protection

frame vs page
associative memory
TLB hit ratio
effective memory access time
page fault interrupt
compaction
handle vs pointer
    compaction
virtual memory
fat code
motivations for virtual memory
    not constrained by physical memory
    more concurrent processes
    less process I/O swapping

why virtual memory is successful
    error handling software rarely run
    data structures allocated too large
    certain options rarely used
pure demand paging
locality of reference
effective access time for virtual memory
Belady’s anomaly
components vs objects

Final exam study guide Concepts/Algorithms/Techniques
DMA concepts
    single address vs dual address
    cycle steal vs burst
    internal vs external request

DMA programming concepts
    specifications at initialization
    Single or Block Transfer
    Read or Write Transfer
    Autoinitialization
    Address inc or dec
    DMA Page Register value
    8237 Address register value
    8237 Count register value
    software synchronization
        blind (internal 100%)
        gadfly
        interrupts

file operations
    create
    read
    write
    open
    close
    reposition
    delete
    truncate
    append
    rename
    copy

file structure
file access methods
    sequential vs direct

file directory operations
    search
    create
    delete
    list,
    rename
    change directory

file directory structure
    single vs multiple level vs tree
    linear vs hashed
file system protection mechanisms
    access rights vs encryption

file allocation methods
    contiguous
    linked
    DOS FAT implementation
    indexed
    multilevel indexed
    combined: direct+single+double+...
file system free space management
    bit vector
    DOS FAT implementation
    linked list

file system performance
    internal/external fragmentation
    maximum disk size
    number of disk accesses

disk cache
    LRU
    free-behind and read-ahead    

file system recovery
    consistency checking
    effect of bad blocks

paging concepts
    page table, address translation
    translation look-aside buffers (TLB)
    P(present), A(accessed), D(dirty) bits
    protection and sharing
    multilevel paging
    Intel 486

Segmentation/memory allocation concepts
    Intel 8051 and 8086 approaches
    protected mode on 386+
    Motorola 6811 and 6812(in C)
    fragmentation

virtual memory with demand paging
    page fault interrupt sequence
        single vs multiple process
        with/without replacement
    physical memory initialization
        prepaging
    page replacement algorithms
        FIFO
        optimal
        LRU
        counting
        page buffering
    thrashing
    page size

Protected Mode Address Calculation on 386
    selector registers
    basic concepts

Golden Rule of Software Development
    Write software for others as you
    wish they would write for you.