University of Phoenix's Virtual Instructor's Manual

Introduction to Operating Systems


Section One   Fundamentals of Operating Systems

  1. List of Objectives



  2. Don't spend more than thirty minutes on this material; let the students read it. Go over a few key terms and emphasize the basic functions of an operating system. Take some time to outline the course, linking the text to your own syllabus.


    Because operating systems are so complex, it is easy to become bogged down in details and miss the main point. The intent of this material is to provide the reader with a nontechnical overview of an operating system's primary functions. Given this base, the student should be able to avoid "missing the forest for the trees" in subsequent sections.


    Cover basic hardware, software, and data concepts. For many students, this material is review. It is included to ensure that all students start from a reasonable technical base.


    Discuss material that will move students to explore inside the operating system and toward concepts that are normally transparent to the application programmer.

    Microsoft Windows, MVS, UNIX, and LINUX will be presented in other Sections and these examples will provide a more in-depth view of how operating systems manage tasks and system resources.

    Stress why three primary functions (communication with the user, physical I/O support, and logical I/O support) are so important. Link the physical input/output control system and the file system to the difference between logical and physical I/O developed in Part I. Another option is to assign some simple exercises on a PC or a UNIX terminal and ask the students to explain what is happening in terms of the basic relationship between operating systems and file management.

    A computer programmer must become familiar with the operating system, data communications software, and database software. Together, they define the distributed computing environment -- the context in which application programs run transparently across a range of technologies in a wide area network. The main reason for this topic is to give the operating system student at least a basic introduction to the emerging trend known as network-centric computing (NCC).

  3. Chapter Summary
  4. An operating system is a set of programs through which the computer manages its own resources, such as the CPU, memory, secondary storage devices, and input/output devices. Conceptually the operating system software functions as an intermediary between the hardware and application program, such as word processing and database programs. Much of the work of an operating system is hidden from the user; many necessary tasks are performed behind the scenes. In other words, whether or not you are aware of it, using any software application requires that you invoke -- call into action -- the operating system as well. Users must be able to interact with an operating system at some level, however rudimentary.

    Operating systems for mainframe and other large computers are complex indeed, since they must keep track of several programs running at the same time. Although some personal computer operating systems also can support concurrent and simultaneous execution of programs, most are concerned only with a single user running a single program at a given time.

  5. Problems for Faculty to Assign or Work Through in Class
  1. Briefly explain how the operating system, a database management system, and data communication software define the programmer's environment.
  2. Answer: The key point here is that a modern application programmer must know how to communicate with the operating system, the database, and the network.

  3. When a programmer writes a complex program, the application logic is often the easy part. Explain.
  4. Answer: Often, each interface calls for a separate set of syntax rules, and that can be confusing. Ask students to consider their own experiences. Learning how to code I/O operations and control language commands is often much more difficult than learning to write logic.

  5. An operating system serves as a platform on which application programs are constructed. What does this mean and why is it important?
  6. Answer: The operating system is the programmer's interface to the computer. All communications with external devices must, directly or indirectly, go through the operating system. You might identify a few popular platforms such as Windows and the Macintosh and ask students who have experience with them to contrast the platforms.

  7. Have students list services provided by an operating system. Explain how each provides convenience to the users. Explain also in which cases it would be impossible for user-level programs to provide these services.
  8. Answer:

    Program Execution. The operating system loads the contents (or sections) of a file into memory and begins its execution. A user-level program could not be trusted to properly allocate CPU time.

    I/0 operations. Disks, tapes, serial lines, and other devices must be communicated with at a very low level. The user need only specify the device and the operation to perform on it, while the system converts that request into device or controller specific commands. User-level programs cannot be trusted to only access devices they should have access to, and to only access them when they are otherwise unused.

    File-system manipulation. There are many details in file creation, deletion, allocation, and naming that users should not have to perform. Blocks of disk space are used by files and must be tracked. Deleting a file requires removing the name file information and freeing the allocated blocks. Protections must also be checked to assure proper file access. User programs could ensure neither adherence to protection methods nor could they be trusted to allocate only free blocks and de-allocate blocks on file deletion.

    Communications. Message passing between systems requires messages be turned into packets of information, sent to the network controller, transmitted across a communication medium, and reassembled by the destination system. Packet ordering and data correction must take place. Again, user programs might not coordinate access to the network device, or they may receive packets destined for other processes.

    Error detection. Error detection occurs at both the hardware and software levels. At hardware level, all data transfers must be inspected to ensure that data have not been corrupted in transit. All data on media must be checked to be sure they have not changed since they were written to the media. At the software level, media must be checked for data consistency; for instance, do the number of allocated and unallocated blocks of storage match the total number on the device. There, errors are frequently process-independent (for instance, the corruption of data on disk), so there must be a global program (the operating system) that handles all types of errors. Also, by having errors processed by the operating system, processes need not contain code to catch and correct all the errors possible on a system.

  9. Explain the difference between logical and physical addresses.
  1. Explain the difference between internal and external fragmentation.
  2. Answer:

    Internal fragmentation is the area in a region or a page that is not used by the job occupying that region or page. This space is unavailable for use by the system until that job is finished and the page or region is released.

  3. How does a virtual memory system work? Distinguish between virtual memory and real memory.
  4. Answer:

    Virtual memory is a model of memory's contents. The operating system and a page pool are stored in real memory. Application programs are stored on an external paging device. As programs run, active pages are swapped into main memory and inactive pages are swapped back out to the external paging device.

  5. What are the advantages of virtual memory? What are the disadvantages?
  6. Answer:

    The major advantage of virtual memory is greater processor efficiency. The major disadvantage is overhead. Also, programmers working on a virtual memory system can code with little of no regard for memory space limitations.

  7. If virtual memory is a logical model of memory's contents, where are those contents physically stored?
  8. Answer:

    The operating system and the page pool are stored in real memory. The application programs are stored on an external paging device.

  9. Explain segmentation and paging.
  10. Answer:

    With segmentation and paging, a program is first divided into variable length segments, then into fixed length pages. Pages are loaded into memory. Addresses are broken into a segment, a page, and a displacement (offset). To compute an absolute address, the segment is used to search a segment table for the location of the segment's page table, the page is used to search the page table for the page's entry point address, and the entry point address is added to the displacement (offset).

  11. Distinguish between paging and segmentation.
  12. Answer:

    With segmentation, the segment size is variable and is a function of the program's logic. With paging, the page size is fixed at a size convenient for the hardware.

  13. What is a page fault? If a virtual memory system finds it necessary to page-out a page to some free space, how is this page selected?
  14. Answer:

    A page fault is an interrupt that results from a reference to a page that is not yet in real memory. If page out is necessary, the least currently referenced page is normally selected (although other algorithms could be used as well).

  15. Consider the following page-replacement algorithms. Rank these algorithms on a five-point scale from "bad" to "perfect" according to their page-fault rate. Separate those algorithms that suffer from Belady's anomaly from those that do not.
    1. LRU replacement
    2. FIFO replacement
    3. Optimal replacement
    4. Second-chance replacement
    5. Answer:

    RankAlgorithmSuffer from Belady's anomaly
    1 Optimal no
    2 LRU no
    3 Second-chance yes
    4 FIFO yes


    1. Consider a demand-paging system with the following time-measured utilizations:

    CPU                        20%

    Paging disk          97.7%

    Other I/O devices     5%

    Which (if any) of the following will (probably) improve CPU utilization? Explain your answer.

    1. Install a faster CPU
    2. Install a bigger paging disk
    3. Increase the degree of multiprogramming
    4. Decrease the degree of multiprogramming
    5. Install more main memory
    6. Install a faster hard disk, or multiple controllers with multiple hard disks.
    7. Add prepaging to the page fetch algorithms
    8. Increase the page size

    Answer: The system obviously is spending most of its time paging, indicating over-allocation of memory. If the level of multiprogramming is reduced, resident processes would page fault less frequently and the CPU utilization would improve. Another way to improve performance would be to get more physical memory or a faster paging disk.

    1. Get a faster CPU -- No
    2. Get a bigger paging disk -- No
    3. Increase the degree of multiprogramming -- No.
    4. Decrease the degree of multiprogramming -- Yes.
    5. Install more main memory -- Likely to improve CPU utilization as more pages can remain resident and not require paging to or from the disks.
    6. Install a faster hard disk, or multiple controllers with multiple hard disks -- Also an improvement, as the disk bottleneck is removed by faster response and more throughput to the disks, the CPU will get more data more quickly.
    7. Add prepaging to the page fetch algorithms -- Again, the CPU will get more data faster, so it will be more in use. This is only the case if the paging action is amenable to prefetching (i.e., some of the access is sequential).
    8. Increase the page size -- Increasing the page size will result in fewer page faults if data is being accessed sequentially. If data access is more or less random, more paging action could ensure because fewer pages can be kept in memory and more data is transferred per page fault. So this change is as likely to decrease utilization as it is increase it.
    1. Segmentation is similar to paging, but uses variable-sized "pages." Define two segment-replacement algorithms based on FIFO and LRU page-replacement schemes. Remember that since segments are not the same size, the segment that is chosen to be replaced may not be big enough to leave enough consecutive locations for the needed segment. Consider strategies for systems where segments cannot be relocated, and those for systems where they can:
    2. Answer:

    1. Name five major activities of an operating system with respect to process management, and briefly describe why each is required.
    2. Answer:

    1. The UNIX kernel will dynamically grow a process's stack in virtual memory as needed, but it will never try to shrink it. Consider the case in which a program calls a C subroutine that allocates a local array on the stack that consumes 10K. The kernel will expand the stack segment to accommodate it. When the subroutine returns, the stack pointer is adjusted and the kernel could release this space, but it is not released. Explain why it would be possible to shrink the stack at this point and why the UNIX kernel does not shrink it.
    2. Answer:

      It is possible to shrink a process's stack by deallocating the unused pages. By convention, the contents of memory beyond the current top of the stack are undefined. On almost all architectures, the current top of stack pointer is kept in a register. Therefore, the kernel can read the register and deallocate any unused pages as needed. This is not done because little is gained by the effort. If the user program will repeatedly call subroutines that need additional space for local variables (a very likely case), then much time will be wasted deallocating stack space in between calls and then reallocating it later on. If the subroutine called is used only once during the life of the program and no other subroutine will ever be called that needs the stack space, then eventually the kernel will page out the unused portion of the space if it needs the memory for other purposes. In either case, the extra logic needed to recognize the case in which a stack could be shrunk is unwarranted. Source: UNIX Systems for Modern Architectures. C. Schimmel, 1996.

    1. Consider an environment in which there is a one-to-one mapping between user-level threads and kernel-level threads that allows one or more threads within a process to issue blocking system calls while other threads continue to run. Explain why this model can make multithreaded programs run faster than their single-threaded counterparts on a uniprocessor machine.
    2. Answer:

      The issue here is that a machine spends a considerable amount of its waking hours waiting for I/O to complete. In a multithreaded program, one KLT can make the blocking system call, while the other KLTs can continue to run. On uniprocessors, a process that would otherwise have to block for all these calls can continue to run its other threads. Source: Lewis, B., and Berg, D. Threads Primer. Upper Saddle River, NJ: Prentice Hall, 1996.

    3. Describe the actions taken by a kernel to switch context
    1. Among threads
    2. Among processes
    3. Answer:

    1. The thread context must be saved (registers and accounting if appropriate), and another thread's context must be loaded.
    2. The same as (a), plus the memory context must be stored and that of the next process must be loaded.
    1. What are the differences between user-level threads and kernel-supported threads? Under what circumstances is one type "better" than the other?
    2. Answer: User level threads have no kernel support, so they are very inexpensive to create, destroy, and switch among. However, if one blocks, the whole process blocks. Kernel-supported threads are more expensive because system calls are needed to create and destroy them and the kernel must schedule them. They are more powerful because they are independently scheduled and block individually.

    3. Discuss the role of the DMA module.
    4. Answer: The DMA module transfers the entire block of data, one word at a time, directly to or from memory, without going through the CPU. When the transfer is complete, the DMA module sends an interrupt signal to the CPU. The CPU is involved only at the beginning and end of the transfer and is therefore able to continue with other work.

    5. Why do some systems keep track of the type of a file, while others leave it to the user or simply do not implement multiple file types? Which is "better?"
    6. Answer: Some systems allow different file operations based on the type of the file (for instance, an ASCII file can be read as a stream while a database file can be read via an index to a block). Other systems leave such interpretation of a file's data to the process and provide no help in accessing the data. The method which is "better" depends on the needs of the processes in the system, and the demands the users place on the operating system. If a system runs mostly database applications, it may be more efficient for the operating system to implement a database-type file and provide operations, rather than making each program implement the same thing (possibly in different ways). For general purpose systems it may be better to only implement basic file types to keep the operating system size smaller and allow maximum freedom to the processes on the system.

    7. List two types of system directories
    8. Answer:

    1. Device directory, describing physical properties.
    2. File directory, giving logical properties of the files.
    1. List the operations to be performed on directories.
    2. Answer: Search for a file, create a file, delete a file, list a directory, rename a file, and traverse the file system.

    3. List disadvantages of using a single directory.
    4. Answer: Users have no privacy. Users must be careful in choosing file names, to avoid names used by others. Users may destroy each others' work.

    5. Why would we want a subdirectory in our account?
    6. Answer: To group files into collections of similar nature, and to protect certain groups or files from other users.

    7. What is a file path name?
    8. Answer: A list of the directories, subdirectories, and files we must traverse to reach a file from the root directory.

    9. List kinds of access we might want to limit on a multiuser system.
    10. Answer: Reading files in a given account; creating, writing, or modifying files in given account; executing file in given account; deleting file in given account.

    11. List four ways systems might provide for users to protect their files against other users.

    Answer:

    1. Allowing user to use unprintable characters in naming files so other users can't determine the complete name.
    2. Assigning password(s) to each file that must be given before access is allowed.
    3. Assigning an access list, listing everyone who is allowed to use each file.
    4. Assigning protection codes to each file, classifying users as system, owner, group, and world (everyone else).
    1. Describe the distributed model of computing, known as distributed data processing (DDP).
    2. Answer:

      DDP is a computing architecture in which processors, data and other aspects of a data processing system may be dispersed within an organization. A DDP system involves a partitioning of the computing function and may also involve a distributed organization of databases, device control, and interaction (network) control.

    3. What are the major implications for operating systems in a DDP system?
    4. Answer:

    A common operating system shared by a network of computers. It looks to its users like an ordinary centralized operating system but provides the user with transparent access to the resources of a number of machines. The distributed operating system will need to rely upon communications architecture for basic communications functions; more commonly, a reduced set of communication functions is incorporated into the operating system to provide efficiency.

    1. What are three main purposes of an operating system?

      Answer: There are several possible purposes of an operating system:

    1. List the four steps that are necessary to run a program on a completely dedicated machine.

      Answer:

    1. Under what circumstances would a user be better off using a time-sharing system, rather than a personal computer or single-user workstation?
    2. Answer: When there are few other users, the task is large, and the hardware is fast, time-sharing makes sense. The full power of the system can be brought to bear on the user's problem. The problem can be solved faster than on a personal computer. Another case is when there are lots of other users needing resources at the same time.

    3. What is the main advantage of multiprogramming?
    4. Answer: Multiprogramming makes efficient use of the CPU by overlapping the demands for the CPU and its I/O devices from various users. It attempts to increase CPU utilization by always having something for the CPU to execute.

    5. Generally, the more programs in memory, the greater the utilization of the processor. Explain why this is so?
    6. Answer: Very simply, more application programs waiting in line means that the processor will spend less time waiting. Because the speed disparity between a CPU and its peripherals is so extreme, memory capacity, not processor time, is the primary limit.

    7. What are the main differences between operating systems for mainframe computers and personal computers?
    8. Answer: Personal computer operating systems are not concerned with fair use, or maximal use, of computer facilities. Instead, they try to optimize the usefulness of the computer for an individual user, usually at the expense of efficiency. Consider how many CPU cycles are used by graphical user interfaces (GUIs). Mainframe operating systems need more complex scheduling and I/O algorithms to keep the various system components busy.

    9. List and briefly define the five key requirements of memory management.
    10. Answer:

      Relocation -- support modular programming

      Protection -- process isolation; protection and access control

      Sharing -- protection and access control

      Logical Organization -- support of modular programming

      Physical Organization -- long-term storage; automatic allocation and management

    11. Consider a dynamic partitioning scheme. Show that, on average, the memory contains half as many holes as segments.
    12. Answer: Let s and h denote the average number of segments and holes, respectively. The probability that a given segment is followed by a hole in memory (and not by another segment) is 0.5, because deletions and creations are equally probable in equilibrium. So with s segments in memory, the average number of holes must be s/2. It is intuitively reasonable that the number of holes must be less than the number of segments because neighboring segments can be combined into a single hole on deletion.

    13. What is virtual memory? How can virtual memory help improve throughput?
    14. Answer: At this point, students should understand that, on a virtual memory system, programs are broken into segments and/or pages and stored on a secondary storage device, and that only active pages are actually loaded into main memory, more efficient programs can be loaded in the same amount of memory.

    15. Explain the difference between logical and physical addresses.

    Answer:

    1. Explain the difference between internal and external fragmentation.
    2. Answer:

      Internal fragmentation is the area in a region or a page that is not used by the job occupying that region or page. This space is unavailable for use by the system until that job is finished and the page or region is released.

      Multiple Choice Questions

    3. In a paging system, the operating system maintains a ____________ to help it manage main memory space.
    1. page frame table
    2. page table
    3. page address register
    4. all of the above
    1. An operating system presents the programmer with _____________ on which to develop application programs.
    1. an interface
    2. the resources
    3. an environment
    4. a platform
    1. The operating system
    1. is a hardware/software interface
    2. manages system resources
    3. both
    4. neither
    1. The average programmer uses ______________ command or job control language.
    1. the complete
    2. most of
    3. a subset of a
    4. none of the above
    1. On a paging system, the operating system maintains a ____________ to help it manage main memory space.
    1. page frame table
    2. page table
    3. page address table
    4. all of the above
    1. On a virtual memory system, the resident operating system is physically stored ___________.
    1. in virtual memory
    2. on the external paging device
    3. in real memory
    4. all of the above
    1. Excessive page swapping can create a problem called ___________.
    1. fragmentation
    2. thrashing
    3. a page fault
    4. an interrupt
    1. Bring a page into real memory only after it has been referenced is called _________.
    1. prepaging
    2. paging
    3. demand paging
    4. a page fault
    1. Under multiprogramming, two or more programs are executed ___________.
    1. asynchronously
    2. simultaneously
    3. synchronously
    4. concurrently
    1. The routine that manages the processor's time is called the _____________.
    1. scheduler
    2. command processor
    3. interrupt handler
    4. dispatcher
    1. In most multiprogramming systems the control fields that must be maintained in support of each application routine are stored in ____________.
    1. the dispatcher
    2. queues
    3. the foreground
    4. control blocks
    1. Many time-sharing systems are ______________ driven.
    1. poll
    2. interrupt
    3. command
    4. all of the above
    1. What is page replacement?
    2. Answer: Selecting a frame (preferably not in use) as a victim; swap it out; swap in the desired page into this frame; restarting program.

    3. Describe FIFO as a page-replacement algorithm.
    4. Answer: "First-in-First-out"; oldest page is chosen as victim; as determined by its position in a queue. Easy to understand; performance not always good.

    5. What is Belady's anomaly?
    6. Answer: You'd expect that the page-fault rate would decrease as the number frames increases; but Belady's anomaly says this is not true in all algorithms.

    7. What is deadlock?
    8. Answer: A deadlock occurs when two programs each need a resource controlled by the other and neither is willing to give in. If uncorrected, deadlock can lead to system failure.

    9. Why is memory protection necessary?
    10. Answer: To prevent concurrent programs from interfering with each other (accidentally or intentionally).

    11. What is a process?
    12. Answer: A program in execution.

    13. What does the long-term scheduler do?
    14. Answer: Determines which jobs belong in the current mix of running/waiting jobs.

    15. What does the short-term scheduler do?

    Answer: Determines which of the current jobs should run in the next CPU burst.