Operating Systems
CS 273 (OS), Fall 2019
Structure of a device driver
First, must do research.
- Learn about what the device can do
- Determine the functions desired by higher level code
- Find out the interface expected by OS for a device driver
Generic structure:
Initialize (device controller, driver data structures) while (1) { receive a request (with desired function and parameters) switch (function) { case f1: ... break; case f2: ... break; ... } deliver results }
Disks
Disk seeks are expensive, whereas reading from the same cylinder after a seek is relatively cheap.
Disk arm scheduling algorithms:
FCFS (First Come, First Served).
- Example: Cylinders 17, 1, 33, 68, 18, 43, 7, 42 arrive in this
order.
Total cylinders crossed: 16+32+35+50+25+36+35 = 228
- Advantages: Simple to implement
- Disadvantages: Can reduce seek time by reordering
- Example: Cylinders 17, 1, 33, 68, 18, 43, 7, 42 arrive in this
order.
SSF (Shortest Seek First)
- Example: Reorder 17, 1, 33, 68, 18, 43, 7, 42 as
17, 18, 7, 1, 34, 42, 43, 68
Total cylinders crossed: 1+11+6+32+9+1+25 = 85 - Advantages: Significantly reduced seek time, especially if several requests are pending.
- Disadvantages: Requests don't arrive all at once, and a
steady stream of requests for one part of disk tends to isolate
requests for other parts of disk.
- Example: Reorder 17, 1, 33, 68, 18, 43, 7, 42 as
Elevator algorithm
- Satisfy all requests in one direction, then all requests in other direction, and repeat alternating direction.
- Advantages: Fairer service
- Disadvantages: Response time still varies, and long waits increase average response time relative to SSF.
- Variant: Only "stop" when going in one direction, to reduce
variation in response time.
- Makes response time more uniform, e.g., for cylinder 1 in example
- Note that it's often quick to move all the way back to cylinder 0.
Use simulation to make performance comparisons during design.
Error handling with disk devices
- Programmer error, e.g., requesting non-existent sectors or tracks
- Bad sectors
- Detectible as checksum error
- If detected during manufacture, can substitute good sectors (nearby?) and write a table on disk to inform a controller about the subtitutions.
- If develop during customer's use,
- Controller can retry, hoping problem corrects itself (e.g., dust)
- If that fails, remap sectors (in OS, if controller can't handle this). But then, lost data, potential problems with backup copying bad blocks, etc.
- Seek error.
- Response: recalibrate and try again... Disk may ultimately need reformatting.
- A few recalibrations could be a serious problem for a realtime system
- Controller error. Device driver would need to detect this (and panic?)
Caching of sectors at the level of controller
- E.g., retrieving all sectors in track even if only one is requested, in case nearby sectors are about to be requested
- Advantages: Improves performance if nearby sectors frequently requested at about same time.
- Disadvantages: Increased complexity of controller.
Clocks
Hardware description
- Basically an oscillator attached to a decrementing counter. When counter becomes 0, interrupt is sent and counter re-initialized.
Uses of clocks in an OS
- Time sharing scheduling
- CPU accounting
- Time of day
- Alarm system calls
- Diagnostic profiling
Character-oriented terminals
Still used for mainframes... mostly emulated in GUI terminal windows elsewhere
RS-232 standard; UART (Universal Asynchronous Receiver/Transmitter) chip on controller and in terminal.
Input issues: Raw vs. cooked mode; use of buffers; echoing (in driver? locally at terminal?);
ioctl
Output issues: processing of control characters (e.g., CTRL/H, CTRL/G, newline); maintaining cursor position; scrolling; control sequences
Timing issues: waiting for RS-232 communications
GUIs (Graphics User Interfaces) and network terminals
Devices
Keyboard, as above
Memory-mapped terminals
Pointer: mouse, track ball, etc.
Speakers
Elements of a GUI
- Windows
- Icons
- Menus
- Pointing device, e.g., mouse
X windows
Architecture for applications:
- Application, e.g.,
xterm
,emacs
,Netscape
.- Note: The window manager is simply an application in X windows system.
- Motif or another package providing "look and feel"
- X Intrinsics, consisting of widgets representing buttons, scroll bars, menus, etc.
Xlib
, library procedures, e.g., for drawing lines, filling regions, managing color maps- X client software, providing access to the resources of an X device (e.g., X terminal, Linux desktop, VNC desktop) potentially across a network via the X protocol.
- OS kernel, e.g., UNIX or Linux
- Hardware
- Application, e.g.,
Architecture at the X device
- X server, providing access to the GUI resources of the device; receives commands from X client via X protocol.
- OS kernel
- Hardware
Comments
- OS only used for device drivers, network communication. E.g., window manager, etc.
- "Client" and "server" seem backward
Some advantages:
- Flexibility of implementing most of the GUI services in user-level software, providing for evolutionary system development
Some disadvantages:
- Computational overhead of managing GUI services as user-level processes
Microsoft Windows
Architecture:
- Win32 application program
- Win32 API (Application Program Interface)
- Windows kernel (e.g., Windows 98, Windows NT, Windows 2000)
Comments
- The actual system calls of a Windows kernel are unpublished and proprietary. They change all the time. Programmers can only access the features of the system through Win32 API.
- Win32 API is platform independent: same application should run on all the platforms.
- Win32 API is huge and complex, providing multiple ways to accomplish the same task and offering high-level services (e.g., file copying) that extend far beyond the notion of a system call in UNIX.
Some advantages
- Portability of applications
- By hiding the actual kernel boundary behind Win32 API, Microsoft can readily respond to newly recognized performance issues without disturbing the applications.
- Whereas GNU/X/Linux development is accomplished by its users, all Windows development is proprietary to Microsoft.
Some disadvantages
- Win32 API is somewhat inconsistent and redundant, owing to back-compatability goals
Thin client
Architecture: Applications run on a server; GUI clients are "dumb terminals" (thin clients) only capable of presenting the GUI for an application, with no general-purpose computing capabilities.
Comments:
- Compare to mainframe terminals.
- Assuming sufficient network bandwidth, server can drive client with good realtime performance.
Some advantages:
- Thin client terminals are cheap.
- Simple design. For example, instead of entire X protocol, thin clients may be based on a handful of rudimentary message types.
- Centralized computing resource is easier to maintain than an army of individual PCs
Some disadvantages:
- No local computing power
- Server is a shared, all-important single point of failure
Some data structures and algorithms
GUI applications employ event-driven paradigm.
- GUI events include mouse movement or click, keyboard action, request to move window, resize window, etc.
- Events occur at random; must be perceived and packaged by the system, presented to the application (or window manager, etc.), then processed by the application.
- Event "handlers" in an application are called callbacks in X, Windows. Each application includes callbacks for the events that application is supposed to respond to.
Structure of a GUI application is comparable to structure of a device driver.
Data structures include:
Graphics context (X, Java) or device context (Windows), holds current parameters and settings for a window.
Raster or rectangular bitmap of pixels ("picture element"), each corresponding to a position on the screen, together with its color.
Color pallet (color map in X), an array of colors, allowing (multi-byte) color specifications to be referenced by a (shorter) index.
Code page (or key map), for transforming actual keyboard codes into codes delivered to an application.
Font, collection of bitmaps associated with character codes. Each font has attributes such as size (in points = 1/72 inch), style (e.g., slanted), family (e.g., Courier or Times Roman), etc.
Objects for representing windows, buttons, menus, scroll bars, cursors, etc. These are called widgets in X,
Component
s in Java, etc.
Power management
OS issues:
Display
Hard disk
CPU
Memory
Wireless
Thermal management
Battery management
Driver interface