Comp111: Operating Systems
Classroom Exercise 1 Answers
In class we have discussed a bit about how time is parceled out to
processes. Let's go a bit deeper. In a typical 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.
- 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.
- 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.
- 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?
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%.
- 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.
- 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.
- (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
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.
- (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.