02OS

Processes p1 and p2 execute on a system with a single CPU and 2 identical I/O devices. Each process executes a compute-bound phase followed by an I/O-bound phase. The system uses multiprogramming without time-sharing. The following table shows the lengths of each phase.

	Compute	I/O
p1	10	70
p2	40	80

p1 starts first at time 0.

Without multiprogramming, the computation terminates at time ??????

With multiprogramming, the computation terminates at time ?????

Expected: 200, 130

p1 needs 10 + 70 = 80 time units and p2 needs 40 + 80 = 120 time units. Without multiprogramming, the processes execute in sequence for a total of 80 + 120 = 200 time units.

With multiprogramming, p1 runs from 0 to 10, followed by the I/O phase from 10 to 80. p2 starts as soon as p1's compute phase terminates and runs from 10 to 50, followed by the I/O phase from 50 to 130.

With multiprogramming, the compute phases are sequential because only 1 CPU is available, but the I/O phases can overlap since 2 I/O devices are available.

Processes p1 and p2 execute on a system with a single CPU and 2 identical I/O devices. Each process executes a compute-bound phase followed by an I/O-bound phase. The system uses multiprogramming without time-sharing. The following table shows the lengths of each phase. Compute I/O p1 10 70 p2 40 80 p1 starts first at time 0. Without multiprogramming, the computation terminates at time ???? With multiprogramming, the computation terminates at time ????? Expected: 200, 130 p1 needs 10 + 70 = 80 time units and p2 needs 40 + 80 = 120 time units. Without multiprogramming, the processes execute in sequence for a total of 80 + 120 = 200 time units. With multiprogramming, p1 runs from 0 to 10, followed by the I/O phase from 10 to 80. p2 starts as soon as p1's compute phase terminates and runs from 10 to 50, followed by the I/O phase from 50 to 130. With multiprogramming, the compute phases are sequential because only 1 CPU is available, but the I/O phases can overlap since 2 I/O devices are available.

01OS

 1.1 The role of an operating system

Bridging the hardware/user gap

The basic hardware of a computer system consists of a CPU, random access main memory, secondary storage, typically in the form of a disk, and input/output (I/O) devices. The CPU repeats a cycle of fetching and executing low-level machine instructions. In contrast, programmers and casual users need to think in terms of high-level operations executed on complex data structures. Most users also do not wish to deal with the internal organizations and low-level interfaces of disks and other devices. Casual users wish to be even more remote from computer hardware and only interact with the system using high-level commands or graphics interfaces.

The mismatch between the low-level capabilities of hardware and the high-level needs of users must be bridged by system software, including compilers, interpreters, editors, linkers, and the operating system.

The operating system (OS) is the software that runs on the bare hardware of a computer and provides essential support for users to develop and use applications in the most efficient and safe manner.

 

Table 1.1.1: Mismatch between hardware capabilities and user needs.

Hardware component	Hardware capabilities	User needs
CPU	Machine instructions perform operations on contents of registers and memory locations.	The user thinks in terms of arrays, lists, and other high-level data structures, accessed and manipulated by corresponding high-level operations.
Main memory	Physical memory is a linear sequence of addressable bytes or words that hold programs and data.	The user must manage a heterogeneous collection of entities of various types and sizes, including source and executable programs, library functions, and dynamically allocated data structures, each accessed by different operations.
Secondary storage	Disk and other secondary storage devices are multi-dimensional structures, which require complex sequences of low-level operations to store and access data organized in discrete blocks.	The user needs to access and manipulate programs and data sets of various sizes as individual named entities without any knowledge of the disk organization.
I/O devices	I/O devices are operated by reading and writing registers of the device controllers.	The user needs simple, uniform interfaces to access different devices without detailed knowledge of the access and communication protocols.

The hardware/user gap is bridged by the OS or by other system software. Which of the following tasks would require OS support?

1)

Input a character from the keyboard.

Definitely

Not necessarily

Correct

All devices require OS support to carry out the complex interactions transparently to the user.

2)

Invoke a high-level matrix manipulation operation.

Definitely

Not necessarily

Correct

The compiler can translate high-level operations on complex data structures into the corresponding machine instructions, which then execute without any help of the OS.

3)

Allocate n bytes of memory for a new data structure.

Most likely

Not necessarily

Correct

The OS must manage the partitioning of memory to protect concurrent users from one another and to optimize the use of memory. Some portion of the dynamic memory could be pre-allocated but, in general, an OS intervention is required.

4)

Load a program into memory.

Definitely

Not necessarily

Correct

The OS must manage the partitioning of memory to protect concurrent users from one another and to optimize the use of memory.

5)

Change the layout of a document.

Definitely

Not necessarily

Correct

A document is manipulated by a text editor. If the document is in memory then the change is made without requiring any OS services.

6)

Call a shared library function.

Most likely

Not necessarily

Correct

Due to the large numbers of possible library functions, the OS may postpone the loading and linking of a function until the function is actually needed.

7)

Call a function defined within the current program.

Definitely

Not necessarily

Correct

The compiler and the linker combine functions into a single module, where the call results in a branch instruction within the program. No OS involvement is needed.

8)

Exit current program.

Definitely

Not necessarily

Correct

When a program terminates, the OS must free up memory and other resources used by the program.

9)

Sleep for n seconds.

Definitely

Not necessarily

Correct

The OS must select and run another program while the requesting program is blocked to avoid wasting CPU time and other resources.

The OS as a resource manager

An application executes code stored in main memory, reads data from an input device, and outputs results to a printer or disk. Performance of the application depends on the efficient use of various devices. In addition, performance is affected by the presence of other concurrent applications. One of the main tasks of an OS is to optimize the use of all computational resources to ensure good overall performance, while satisfying the requirements of specific applications, including guaranteeing acceptable response times for interactive processes, meeting deadlines of time-critical tasks, and allowing safe communication among different tasks.

A program typically alternates between phases of input, computation, and output. Consequently, the CPU is underutilized during the I/O phases, while the I/O devices are idle during the compute phase. The overall performance of all applications can be improved by using concurrency. The OS strives to keep the CPU, main memory, and all storage and I/O devices busy at all times by overlapping independent operations whenever possible.

uniprogramming, one program starts and runs in full to completion; the next job would start instantly after the first one finished. The problem with this approach is that programs consist of both CPU instructions and I/O operations. CPU instructions are very fast, as they consist of electrical signals. I/O operations are very slow

Multiprogramming is a technique that keeps several programs active in memory and switches execution among the different programs to maximize the use of the CPU and other resources. Whenever a program enters an I/O-bound phase where little CPU time is needed, other programs can resume and utilize the CPU in the meantime. Similarly, whenever a device completes an operation, the OS activates computations that can utilize the now available device.

Time-sharing (multitasking) is an extension of multiprogramming where the CPU is switched periodically among all active computations to guarantee acceptable response times to each user. Time-sharing employs the concept of virtualization by creating the illusion of having a separate virtual CPU for each computation.

Principles of multiprogramming and time-sharing.

A

Sequential execution

Multiprogramming

Time-sharing

CPU

I/O 1

I/O 2

CPU

I/O 1

I/O 2

CPU

I/O 1

I/O 2

A

A

B

B

A

B

A

B

A

B

A

B

A

B

A

B

A

A

A

A

B

A

B

B

Captions

1. Computation A alternates between CPU-bound and I/O-bound phases.
2. When A terminates, another computation B starts and executes in a similar manner by alternating between the CPU and another I/O device.
3. Under multiprogramming, both A and B are active. When A enters the I/O phase and waits for the device to complete the operation, B uses the CPU.
4. Computation A resumes when I/O 1 has completed while B waits for the I/O 2 phase to complete.
5. Due to the overlapping of the CPU and I/O-bound computations, the total time to complete both A and B is significantly reduced.
6. Under time-sharing, both A and B take turns at the CPU during short time intervals.
7. As a result, both computations appear to be running concurrently, albeit at a reduced speed.

Effects of multiprogramming and time-sharing.

1)

Multiprogramming generally improves CPU utilization and throughput.

True

False

Correct

Multiprogramming overlaps phases of computation and I/O from different computations to better utilize the CPU and other resources, which improves overall performance.

2)

The main objective of time-sharing is to improve resource utilization.

True

False

Correct

Resource utilization is improved by multiprogramming, which overlaps CPU-bound and I/O-bound computations. Time-sharing only switches the CPU among different computations to create the illusion of simultaneous execution, which generally does not improve resource utilization beyond simple multiprogramming.