Transcript chp06

Chapter 6: System Software and Virtual
Machines




Chapter 4 and 5 investigated the hardware behind a VonNeumann computer
A computer is capable of executing programs written in machine
language (binary data and instructions)
Should human users also use the control unit language in order
to manipulate programs and data?
The “naked” machine described in the last chapters is hard to
interact with, human users need further support (e.g. tools) in
order to make computers more effective and more useful.
1
Features of the Naked
Machine




It uses binary representation of data and instructions
It only performs the fetch/execute cycle of instructions
automatically, but nothing else.
It is designed with the goal of simplifying the hardware task in
mind, people using the machine were not taken into consideration
Suppose you want to use the naked machine directly:


1. Step:
You have to provide your program and data in binary
  very time-consuming
  very error-prone
 Example: 10  00001010
ADD  00000111
2. Step:
You have to store the program in memory
  You have to go to each memory cell and set its values to the
corresponding instructions
  Have fun!!!
2
Features of the Naked
Machine



3. Step:
You have to start the program
 Put the beginning address of your program into the program
counter (PC)
 Now the processor can do everything automatically
You might be asking yourself, have programmers and users of
computers to be also electrical engineers?
What the naked machine needs in order to be useful is a User
Interface that
 hides unnecessary details
 allows access to the resources of the computers
 prevents accidental or intentional damages of hardware, programs,
and data.
3
Outline of this chapter

System Software



Assemblers and Assembly Language
Social Issues
Applications
Assembly Language
Translation and Loading
Virtual Machine
Operating Systems (OSs)
Hardware



Virtual Machine
Types of System Software


Tasks of the operating system
History of operating systems
Software
Algorithmic Foundations
4
System Software





Software means any program or set of programs
Remember: Hardware is the machine itself or any part thereof
The system software is a collection of computer programs that
manage the resources of the computer and facilitate access to
those resources.
Resources: Any usable part of hardware or software
System software acts as an intermediary between users and
hardware
System Software
Virtual
Machine
Interface
(VMI)
Machine
Interface (MI)
Hardware
Virtual Machine
5
Virtual Machine


Compare: System software  Dashboard of an automobile
The system software has the following tasks:





Hide the details of the Von-Neumann architecture from the user
Present information in an easy to understand form
Allow for accessing resources in a simple and efficient form
Ensure security and safety of the environment
Examples:



a = b+c: should not need any further specification to be executed.
 abstract from registers, fetch, and store and so on.
Loading a program should be automatic, the VMI should offer a command
like “load my program into memory”
VMI should make it possible to move data from/to I/O devices without
dealing with details such sector and track addresses in a disk
6
Types of System Software

System software includes different types of programs:
System Software
Language Translators
e.g.
-Assemblers
-Compilers
Memory Managers
e.g.
- Loaders
- Linkers
Information Managers
e.g.
-File systems
-Databases
Utilities
e.g.
-Text Editors
- Draw Programs
Operating System (OS)
Hardware
7
Types of System Software



OS: a program that controls the overall operation of the computer and
manages its resources.
It communicates with a user and lets him/her activate the different
software packages to handle a specific request.
Some of these packages are:

Language translators: Assemblers and compilers are programs that
allow for writing programs in a user-oriented way (not in binary)

Memory managers: Programs that allocate memory space for
programs and data and load programs into memory

File systems: Programs that allow for storage and retrieval of data
kept in mass storage (e.g. CD-Roms, Disks)

Utilities: what you otherwise often use like editors, draw programs,
debugging programs
8
Using the System Software for Program
Development and Execution

Step 1: Use a text editor to create a program in a high-level (English-like)
language

Step 2: Use the file system to store the program into hard disk

Step 3:Use a language translator to get the program in binary

Step 4: Use a loader in order to assign memory to your program

Step 5: Use the operating system to start the program

Step 6: Use the file system to store results of your program

Step 7: Potentially (in case of errors) use a debugger to find the error(s) in your
program
9
Assemblers and Assembly
Language

Machine language drawbacks are:







Use of binary
No names are allowed for addresses (only numbers)
Difficult to change
Assembly language is a the first step towards more user-friendly
interface for computers (programming).
Appeared in 1950s (2nd Generation of computers)
Philosophy behind it: make it easy for both machines and users
at the same time
Today assembly languages are viewed as low-level languages,
since each instruction of the assembly language is translated
into a single instruction of the machine language
10
Assembly Language



In contrast: Basic, Fortran, Cobol, Pascal, and C are considered
high-level languages (HLLs).
HLLs are more user-oriented than Assembly languages, a typical
HLL instruction is translated to many machine language
instructions
Evolution of programming languages:
Increasing level
of abstraction
HLLs
Assembly Language
Machine languages
11
Assembly Language

Process of translation, loading, and execution
Assembly
Language
Program
Assembler
Machine
Language
Program
Source Program
Loader
Results
Hardware
Machine
Language
Program (loaded)
12
Assembly Language

Example of an assembly language:

Instruction format:
label:

op code mnemonic address field
-- comment
Labels: names that identify instructions or data, e.g.
BEGIN: ADD A, B
…
JUMP BEGIN
 More clarity
 Better Maintainability



Op-code mnemonic: No more binary numbers are used, your
assembly program includes the word “ADD” (for +), “SUB” (for -)
and so on.
Address field: Names of operands and not their addresses
Comment: Any remarks connected to the instruction, not processed
by the assembler
13
Assembly Language

Examples of assembly instructions:
LOAD
X
STORE
X
CLEAR
X
ADD
X
INCREMENT X
DECREMENT X
SUBSTRUCT X
COMPARE X
JUMP X
JUMPGT X
JUMPLT X
JUMPEQ X
IN X
OUT X
HALT
-- value of X is copied to a register R (XR)
-- RX
-- 0X
-- R+XR
-- X+1X
-- X-1X
-- R-XR
-- Set GT (if X>0), EG (if X=0), or LT (if X <0)
-- XPC
-- if GT=true then XPC
-- if LT=true then XPC
-- if EQ=true then XPC
-- (integer value from keyboard)X
-- X(New line on the screen)
-- stop program execution
14
Assembly Language

Also assemblers allow pseudo-instruction for e.g. data generation

Example:
 FIVE: .DATA +5 -- generates the binary value of 5 and
-- puts it in a memory cell called FIVE
 Suppose: Assembler chooses address 53 for FIVE
53:
000000101
Now: LOAD FIVE is equivalent to LOAD 53
LOAD 5 in contrast would mean to load the address 5
which may holds another value than “5”

Other pseudo-instructions are for example .BEGIN and .END:
.BEGIN
…
HALT
…
.END
-- here any instruction ADD, JUMP, and so on
-- here .DATA instructions
15
Examples for Pseudo-Code to
Assembly Translations

A piece of the Sequential Search Algorithm:
Set I to 1
…
Add 1 to I
Translated into assembly language:
.BEGIN
LOAD
ONE
-- 1R
STORE I
-- RI (I is now = 1)
…
INCREMENT I
-- Add 1 to I
…
HALT
I:
.DATA 0
ONE:
.DATA 1
.END
16
Examples for Pseudo-Code to
Assembly Translations

Another example using a While loop:
1.
2.
9.
10.
11.

Set I to 0
While I is not equal 10,000
…
Add 1 to I
End loop
Stop
In assembly language:
LOOP:
DONE:
ZERO:
I:
MAX:
LOAD ZERO
STORE I
LOAD MAX
COMPARE I
JUMPEQ DONE
…
INCREMENT I
JUMP LOOP
HALT
.DATA
0
.DATA
0
.DATA
10000
-- 0R
-- RI
-- 10,000R
-- compare I and 10,000
-- if I=10,000 we are done
-- Step 9 of above
-- Repeat the loop
-- stop execution
17
Translation and Loading

Tasks of an assembler:





Convert symbolic op-codes to binary
Convert symbolic addresses to binary
Perform assembler services needed by pseudo-operations (like
.DATA)
Put the translated instructions in a file
Op-code conversion:


Use of an op-code table
An op-code table may look
ADD
CLEAR
COMPARE
DECREMENT
…
like the following
0011
0010
0111
0110
18
Translation and Loading


Assembler reads the program line by line and looks for
corresponding binary value of each instruction in op-code table
What search algorithm?




Sequential search: O(n)
Better: organize the op-code table in a sorted way, then binary
search can be used O(log(n))
More difficult is converting symbolic addresses and labels into
binary, because these differ from a program to another one
Normally, assembler goes through the code 2 times

 2 passes are needed
19
Translation and Loading

First pass:


Task: build so-called symbol table, which binds each symbol to the
appropriate address.
Example:
Code
LOOP:
DONE:
X:
Y:
Location counter
IN X
0
IN Y
1
LOAD X
2
COMPARE Y
3
JUMGT DONE
4
OUT X
5
JUMP LOOP
6
OUT Y
7
HALT
8
.DATA 0
9
.DATA 0
10
Symbol table

LOOP
DONE
X
Y
0
7
9
10
20
Translation and Loading
Second pass:






Use of the op-code table for translating mnemonic op-codes
Use of the symbol table for translating symbolic addresses to binary
Example:
SUBSTRACT X
involves the following steps:
1. Look up SUBSTRUCT in op-code table
 e.g. 0101
2. Look up the symbol X in the symbol table
 e.g. 0000 1001 (9)
3. Get the whole instruction in binary:
 0101 0000 1001
Other instructions are handled in the same way, except data generation
ones where a conversion from decimal to sign-magnitude binary is also
made.
The generated code is put into a (new) file called object file
21
Loader




The object file is handed out to the loader
The loader’s task is to assign memory to instructions
and data of the program
When loading is complete, the loader places the
address of the first instruction into the PC (Program
Counter)
The hardware begins then processing the program
instruction by instruction
22
Operating System

To carry out the services described, the user must issue system
commands e.g.:





> assemble MyProgram (which invokes the assembler)
> run MyProgram (which invokes the loader)
Often the point-and-click technique via a mouse is used
The program that waits for such user commands and invokes on
his/her behalf the desired services (like assembler and loader) is
called operating system (OS)
The word “system” is used, because this program is often a huge
one including many components.
23
Main Tasks of the OS

The main tasks of the OS are:





User Interface
Security and protection
Efficient allocation of resources
Safe use of resources
User Interface (UI):



The OS runs whenever no user programs are occupying the processor
It gets commands from users and runs the appropriate package to process
the request
OS acts like a computer receptionist and dispatcher
24
User Interface

Examples of commands:







Log on and off the computer
Translate program
Run program
Save a file
Print a file
Read data from mass storage (e.g. disk, CD-Rom)
Types of UI:


Text-based:
 Example: list files in the current directory:
 dir thisDirectory (DOS)
 ls thisDirectory (Unix)
  requires to learn the command language
Graphical user interface:
 Icons, pull-down menus, scrolling windows
  requires less expertise
25
Security and Protection

Authentication of users
 Only users that are allowed to use the computer are accepted
 Other users are rejected
 Mechanism is based on passwords:






The first interaction with the OS includes providing a user name and
password
Passwords are stored in a password file
Password file is protected against malicious modifications
Only a special user, the super user, is allowed to modify the
password file
Super user is often the administrator of the computer
OS may use encryption in order to safeguard the contents of the
password file

E.g. ABC  01000001 01000010 01000011 (ASCII)
 010100001001000011011111 (encrypted)
(here left-shift 6 positions circularly and add 15)
26
Security and Protection

Authorization




Authenticated users must not do everything
E.g. password file should not be accessible to them or at least they
should at most be able to read - not modify - it
Principle: use of access rights
Example: Authorization list for file GRADES
Adam
Suzanne
Bob
Admin

RA
R
RAC
RACD
R: Read only
A: Append
C: Change
D: Delete
Checks are also made when deleting a huge amount of data e.g.
the whole hard disk. The OS first asks the user to confirm the
operation, since when deleted, data are lost forever!
27
Efficient Allocation of
Resources




Recall that I/O controllers were introduced in order to avoid idle
phases of the processor
However, this assumes that there is always something to do for
the processor
To ensure this last assumption and to keep the processor busy
as long as possible the OS takes the appropriate measures
Example:


OS classifies programs into 3 categories: waiting, ready-to-run, and
running
Assume we there are 4 programs (A, B, C, and D) loaded and A is
running whereas the other programs are ready-to-run:



 Waiting = {}
 Ready = {B, C, D}
 Running = {A}
28
Efficient Allocation of
Resources

Assume that A (during its execution) issued an I/O operation
that reads a sector from the disk


 A would now wait for several milliseconds for the data to come
At this time the OS intervenes:

 Waiting = {A}
 Ready = {C, D}

 Running = {B}

 Now B is running, that is, the processor is not idle
Later when the I/O operation is complete:





 Waiting = {}
 Ready = {B, A, D}
 Running = {C}
29
Safe Use of Resources


OS prevents programs and users from using operations that lead to a
“frozen” state, where the computer is incapable of doing any further
work
Suppose we have 2 programs A and B:
A: A1. Get tape drive
A2. Get the laser printer
A3. Print file

If A1 and B1 are already executed, the two programs will wait forever!





B: B1. Get laser printer
B2. Get tape drive
B3. Print file
A will wait for the laser printer occupied by B
B will wait for the tape drive occupied by A
 Deadlock
Deadlock prevention: e.g. ask for all resources simultaneously
Deadlock recovery: e.g. ask a program to undo the operation
30
History of OSs

First Generation (1945-1955)






No system support, except assembler and loader
One user at a time (users sign up for a block of time)
Special buttons for starting assembler/loader
Most of the time the machine was idle because the user was analyzing results and
thinking what to do next
 system administrators realized the need of keeping the costly machines (millions
of dollars!) busy as long as possible.
Second Generation: Batch operating systems (1955-1965)




User was not the programmer (like above) but the highly trained computer operator
Operator collected set of programs (batch) –typically on punched cards – and carried
them to a small I/O computer that put them on tape
The tape was then carried to the machine room in order to be executed by the “big”
computer, where results were written into an output tape
The output tape was carried back to the I/O computer in order to print results of the
various programmers
31
History of OSs




Since programmers did not operate the machines, they needed to “tell” the OS what
is to be done
 job control language
Examples of commands: Assemble, Load, Run, etc.
In the same period integrated circuit emerged, and the difference in speed between
processor and I/O became larger
 Just one program at a time was no longer beneficial
Third Generation: Multi programming operating systems (1965-1985)





More than one program in memory
Higher utilization of processor could be achieved (waiting cycles do not lead to idle
ones)
Since different programs are allowed to work simultaneously, OS have to protect each
of them in memory
 A program is no longer allowed to use any memory address
Similarly, HALT instruction is no longer allowed to a program
 Privileged instructions (allowed to OS only)
Due to the progress in computer networks, time-sharing systems (TSS) evolved
32
History of OSs





A TSS is also a multi-programmed one with the single difference that commands,
programs, and data are no longer supplied at the beginning (in the batch), instead the
users can give these commands on-line from different terminals
 interactive environment
Users do not go to the “big” computer, they sit at their terminals and communicate data
and commands
However, there was a minor change needed in TSS:
 computation-bound programs were taken into consideration
Observe that computation-intensive tasks were no problems in multiprogramming OSs
because they highly utilized the processor without bothering users, but now (in a TSS)
users were waiting for results after starting their programs
Therefore, in a TSS, a program may be suspended if either of the following happens:



The program initiates an I/O operation (like in multiprogramming OS)
The program has run for a maximum length of time, called time slice e.g. 100 milliseconds (new)
The number of users that can be served simultaneously depends on:



Speed of processor
Length of time slice
Type of operation being done by each users (e.g. I/O-intensive, computation intensive)
33
History of OSs






Early 1980s: Appearance of personal computers (PCs)
Initially, PCs were only viewed as another type of “dumb” terminals, however soon
thereafter (due to improvements in technology) people realized that much of the work
of the central computer can be done by the desktop PC.
In late 1980s and in the 1990s computing changed from centralized environment
(batch, multi-programmed, TSS) to a distributed environment, where computing
moved to the front-end (e.g. office, lab, classroom).
OSs in PCs were initially single-user OSs (since they were -and still are- cheap, so no
sharing of resources was needed)
However, I/O devices (e.g. laser printers, tapes) and special software packages
(possibly in different locations) were not cheap, these needed to be shared: This led to
the 4-th generation of OSs, where remote access to resources was supported.
Fourth Generation: Network operating systems (1985-present)



A network operating system (NOS) is able to manage not only local resources but also
remote ones.
Machines are connected via a network, e.g. a local area network (LAN).
A LAN is used to connect machines within a building for example. Using a LAN, users
can access shared resources (called servers).
34
History of OSs




Users at their workstations can perform local computing oblivious to the network. OS
performs in this case as described above.
However, the OS lets the user access the remote resources, too, thereby hiding the
communication needed to access them.
Examples of shared resources (NOS makes all of them appear like local ones):
 Files servers: Manage large disks in the network.
 Print servers: E.g. one printer for a department.
 Compute server: A high-speed machine can be shared by many users
 Mail server: LAN supports communication with users connected to it. A mail server
gets every email; if it is for a local user, it forwards it to the user, if not, it forwards
it to an outgoing link that connects the LAN to a wide-area network, a WAN, e.g.
the internet.
Fifth Generation (??)


Multimedia user interfaces, e.g. voice-based commands, tell the system your
commands
Distributed OS (DOS): You don’t see the network, everything is hidden.
35