Comp111: Operating Systems
Classroom Exercise 2 Answers
Fall 2018

In class we have discussed a bit about how time is parceled out to processes. Let's go a bit deeper. In an older linux instance, the amount of time that a process takes is measured by sampling every 1/100 of a second and counting that 1/100 of a second as being used by the process that is currently running when the sample is made. If a context switch is occurring, the time is counted toward the operating system itself, instead. The following time-space diagram depicts processes and context switches, as well as the times at which the operating system measures state. Time is depicted on the horizontal axis and process on the vertical axis. The states of the processes P1, P2, and P3 are checked at the times at which the vertical dotted lines appear. The time between lines represents 1/100 second.

  1. In the time-space diagram, how much time is recorded as being used by processes P1, P2, P3?
    P1: 7/100ths of a second.
    P2: 13/100ths of a second.
    P3: 12/100ths of a second.
  2. According to your best visual estimates, how much time is actually used by each process P1, P2, P3?
    P1: about 7/100ths of a second.
    P2: about 13.5/100ths of a second.
    P3: about 11.75/100ths of a second.
  3. The efficiency of an operating system is the percentage of time spent in doing useful work, relative to total time available. According to your best visual estimates, what is the actual efficiency of the operating system in the above diagram?
    Answer: The total elapsed (wallclock) time is 36/100 of a second, so that -- based upon a visual estimate of 3.5/100 of a second for context switches -- the useful work is (36/100-3.5/100) of a second, and the efficiency is approximately (36/100-3.5/100)/(36/100) = 90.3%.
  4. Why is the sum of all system and user time (for a single core machine) always less than elapsed wallclock time?
    Answer: Both user and system time are times spent on behalf of a process. Thus both qualify as "useful work". What does not count as useful work is the context switches (and other operating system overhead to be discussed later). Unless there are no context switches at all, useful work is always less than the total time available.
  5. What is the relationship between user time, system time, and wallclock time for a multi-core computer that can run two or more processes concurrently?
    Answer: In an n-core computer, the potential for useful work is n times the potential for a one-core computer. Thus the useful work is less than or equal to n times the wallclock time.
  6. (Advanced) Suppose that you are trying to do the above calculations and the times between samples are not equal, as they are in the diagram above. How would you change your algorithm to calculate efficiency?
    Answer: Then one would have to estimate the time for the measurement. One could add a number of seconds equal to the length of the interval after the observation or -- alternatively -- consider the measurement to be valid from the midpoint of the previous interval to the midpoint of the next one. These are both approximations; we don't know exactly when the state changes; just that a state is valid when observed.
  7. (Advanced) A "real-time operating system" is one in which one can be assured that responses to external events will occur very close in time to when the events occur. It is often claimed that "linux is not a real time operating system". Based upon your knowledge of the scheduler so far, what impedes "real-time" response?
    Answer: The scheduling I have described so far makes transitions from blocked to ready but not directly from blocked to running. Thus there is a delay in reacting to changes in state -- e.g., a device sending data -- based upon how long it takes to transition from ready to running.

    We will see that the brand new scheduler in the current Linux actually tries to address this with some "scheduler policies" that make a process run almost instantly after being put into the ready state. We will discuss this in class at a later time.