Week 15 (Last Week), 20/23 October, 1997

Operating System

On top of the computer hardware is operating system, utility programs, and application programs, which are the software component of a computer. The operating system manages the user/computer hardware interface, so that it is easier and friendlier to end users. The operating system supports the program creation, execution, manages the memory system, I/O devices and user processes.

UNIX operating system is a multi-user, multi-tasking operating system with an elegant hierarchical file system. The UNIX kernel does the real job of management. The user interacts with the kernel through a program called shell. Shell is just one of the many programs. There are several slightly different shells (sh: Bourne shell, csh: C shell, ksh: Korn shell, tcsh: Enhanced C shell).

A process in UNIX is a currently running program plus addition bookkeeping information. A process is created when you login. You can create process by running a program. Process A can create Processes B and C; Processes B and C is called children of A, A is parent of B and C. You can display the current running processes with the Unix command:

   ps -aux         (or ps -ef on other systems)
or kill a process with the kill [pid] command.

Unix is a time sharing operating system. A typical workstation will have 30 to 40 processes running. But only one process is actually executing the instructions. The other processes are waiting for the CPU resources. The operating system controls which process should be executed and for how long. The operating system switches the running processes quickly. It gives user the impression that all processes are running simultaneously.

Unix has a large collection of commands (well over 300). It takes years of experience to be good at them. Here I list some of the interesting ones.

   cd       change directory
   cp       copy file
   rm       delete file  mkdir/rmdir  make/remove directory
   pwd      print working directory 
   ls       list file
   df       file system usage
   du       disk usage
   quota or diskquota
   chmod    change mode of the file protection
   ln       create a link
   cat      display a file
   diff     print out the difference of two files
   vi                               tex/latex   (document formating)
   emacs                            troff

   man      display manual page
   grep     pattern search
   awk      pattern scanning and processing 
   perl     more advanced pattern scanning and processing
   dbx      symbolic debugger
   make     program maintenance
   spell    spelling checker
   pine     E-mail



Arithmetic instructions

     R-form  Immediate Unsigned   U/I   single   double      C 

      add      addi      addu    addiu   add.s   add.d      "+"
      sub                subu            sub.s   sub.d      "-"
      mult/mul           multu           mul.s   mul.d      "*"
      div                divu            div.s   div.d      "/"
Remarks: (1) Most arithmetic instructions take 3 operands, except mult and div, which take 2. (2) Floating point instructions take only 3 floating-point registers. (3) First register is usually the result. Result for mult and div is in hi and lo. (4) Immediate values take the third operand. (5) What is the difference between signed and unsigned version of the instructions? Note that the same "+" in C can be translated into any one of the 6 different addition instructions.

Logical instructions

           Immediate         C

     and      andi          "&"
     or       ori           "|"
     xor      xori          "^"
     sll                   "<<"     shift left
     srl                   ">>"     shift right
     sra                   ">>"     shift right arithmetic
Remarks: (1) Again, these instructions take 3 operands, first is result, the last may take immediate value. (2) Logical operations are BITWISE, e.g.,
  and   1011001...1001
result  0001000...0000

Conditional branch and jump

   beq $2, $3, L        "if($2==$3) goto L;"
   bne $2, $3, L        "if($2!=$3) goto L;"

   j L                  "goto L;"

   jal f                "f(a,b,c ...);"

   slt    slti   sltu   sltiu    "$2<$3?"

Remark: (1) Conditional branch and jump instructions are used to control the execution of code, corresponding to C states like for(..), while(..), do {}, if(..) else. (2) jal is used for function call.

Data transfer instructions

Move from memory to registers:
     lw $2, address        l.s $f0, address,     l.d $f0, address

Move from registers to memory:
     sw $2, address        s.s $f0, address      l.d $f0, address

Move between registers:
     mflo $1
     mfhi $1
     mtc1 $1, $f0  (move from CPU to FPU)
     mfc1 $1, $f0  (move from FPU to CPU)

Remarks: (1) Address is either of the form 100($4), for example, or a label (pseudo-instruction). (2) Only load/store instructions access memory. (3) A word occupies 4 bytes. (4) "Move" does not actually mean moving the data, "copy" is more appropriate.


   move     (copy contents)
   li       (load immediate)
   li.s li.d (load immediate floating point)
   la       (load address)

Remarks: (1) Pseudo-instructions (also called assembly instructions but not machine instructions) are translated into one or several machine instructions by the assembler. (2) Pseudo-instructions do not have machine encoding.

Assembly Programming

Program structure

A MIPS assembly program looks like this:
   str:     .ascii  "string\0"
   A:       .word   1
                           # code goes here
             j $31 

Argument passing, register usage convention, and stack

We should know these concepts. In particular, $2 is for integer type return value, $4 to $7 are for 1st to 4th integer type arguments.

Data Repesentations

All types of data on computer are ultimately represented by bit patterns. Given a bit pattern of 32 bits (1 word)

   b_31   b_30  B_29 ...... b_3 b_2 b_1 b_0
it can represent:

Remarks: (1) We should know how to negate a (two's complement) number, and sign extending a number. (2) Binary <-> decimal conversion, including floating point binary numbers. (3) Divide/multiply by 2 methods for binary/decimal conversions.

Computer Arithmetic

Following points are expected to know:

We do an addition and a Booth algorithm multiplication as examples.
           unsigned signed
      1101   -> 13  -3                  1101    ->  -3
   +  0111   ->  7   7              x   0111    ->   7
   -------                     -------------
   (1)0100   -> 20   4              00000000
    ^                             - 11111101
    |                           ------------
 overflow bit                       00000011
                                  + 11101 
                                    11101011    -> -21 

Remarks: (1) Whether there is an overflow or not depends on the interpretation (signed or unsigned number). (2) Booth algorithm is for signed number. The result has twice the original bits.

Computer Organization

How does computer execute instructions (datapath and control, pipelining)? How can we have a fast as well as large memory? How the various components of a computer are connected? Coverage on these questions will be light, but not excluded from exam.

Final Examination (Monday afternoon 2:00-4:00 PM, 10 Nov, 97, at IMM)

How to Review

(1) Read and understand the lecture notes. Read the relevant chapters of the textbook. (2) Do or re-do the tutorial/lab problems without referring to the answers. Then check against the answers. (3) If you have time or energy, do extra problems in the past exams, problems in textbook or other reference books.

Dr. Wang Jian-Sheng (office S16 02-35, tel x6880) is available for consultation in the reviewing period.

[ previous week ]