______ Operating Systems (CS 273 (OS), Fall 2019)
Home
>>    




Operating Systems

CS 273 (OS), Fall 2019

Structure of a device driver

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

    • 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.

    • 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

  • 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, Components in Java, etc.

    Power management

    OS issues:

    • Display

    • Hard disk

    • CPU

    • Memory

    • Wireless

    • Thermal management

    • Battery management

    • Driver interface