Introduction To Unix

Introduction to UNIX ❖

Objectives – –

Motivate the use of UNIX Introduce basic UNIX features (e.g. using directories, files) – Introduce vi

UNIX Intro. March

1

Contents 1. 2. 3. 4. 5.

Background on UNIX Starting / Finishing Typing UNIX Commands Commands to Use Right Away UNIX help continued

UNIX Intro.

2

6. 7. 8.

The UNIX File System Working with Directories Working with Files

9.

vi

UNIX Intro.

3

1. Background on UNIX 1.1. What is UNIX? 1.2. History 1.3. Why use UNIX?

UNIX Intro.

4

•1.1. What is UNIX? ❖

The UNIX Operating System (OS) is a large program (mostly coded in C) that turns the computer into a useable machine.

❖

It provides a number of facilities: – management of hardware resources – directory and file system – loading / execution / suspension of programs

UNIX Intro.

5

1.2. (Brief) History 1969 ❖ 1975 ❖ 1970’s ❖ 1980’s

First UNIX at Bell Labs Bell Labs makes UNIX freeware Berkeley UNIX (BSD) TCP/IP MIT X-Windows ❖ 1990’s The Web, LINUX ❖

UNIX Intro.

6

1.3. Why Use UNIX? multi-tasking / multi-user ❖ lots of software ❖ networking capability ❖ graphical (with command line) ❖ easy to program ❖ portable (PCs, mainframes, super-computers) ❖

continued UNIX Intro.

7

free! (LINUX, FreeBSD, GNU) ❖ popular ❖ profitable 1996 Sales: US$34.5 Billion, up 12% ❖ not tied to one company ❖ active community ❖

UNIX Intro.

8

2. Starting / Finishing 2.1. Your Account 2.2. Login to your Account 2.3. Password Tips 2.4. Logout from your Account UNIX Intro.

9

2.1. Your Account ❖

Each user has their own space on fivedots, called their account.

❖

Type your login ID and password to enter your account.

❖

Only if the login ID and password match will you be let in.

UNIX Intro.

10

2.2. Login to your Account login: ad

You type your ID and RETURN.

Password:

You type your password and RETURN. It does not appear.

$

The UNIX prompt (or similar). You can now enter commands.

UNIX Intro.

11

2.3. Password Tips NEVER tell anyone your password. ❖ Don’t write it down. ❖ A good password is: ❖

– 8 (or more) characters long – uses a mix of uppercase and lowercase letters, numbers, and symbols (e.g. #, %). ❖

UNIX Intro.

You can change your password with the passwd command (see later).

12

2.4. Logout from your Account logout

or ^D

Press CONTROL and D together

or exit

UNIX Intro.

13

3. Typing UNIX Commands 3.1. The Shell 3.2. Typing Commands 3.3. Control Characters 3.4. Changing your Password UNIX Intro.

14

3.1. The Shell The UNIX user interface is called the shell. ❖ The shell does 4 jobs repeatedly: ❖

display prompt read command

the shell

execute command

process command UNIX Intro.

15

3.2. Typing Commands ❖

Try these: date cal 3 1997 who ls -a man cal Press spacebar to continue; ^C (CONTROL and C) to stop clear

UNIX Intro.

16

3.3. Control Characters ❖

Erasing characters DELETE delete last character ^H delete last character (press CONTROL and H together). ^W delete last word ^U delete the line

UNIX Intro.

17

❖

Very useful control characters ^C

terminate command

^S

suspend output resume output

^Q

UNIX Intro.

18

Special Characters can be Altered ❖

Show current settings: stty -all

❖

Change a setting: stty erase ^?

❖

Type ^ and ?.

Reset: stty sane

UNIX Intro.

19

3.4. Changing your Password ❖

The command is: passwd

❖

UNIX Intro.

It will ask you for the new password twice.

20

4. Command to Use Right Away 4.1. Date Commands 4.2. You and the System 4.3. Calculators 4.4. Games UNIX Intro.

21

4.1. Date Commands ❖

date

Gives time and date

❖

cal cal cal cal

Calendar 1997 3 7 1962

cal 9 1752

UNIX Intro.

Not a mistake. Why?

22

4.2. You and the System ❖

uptime

❖

hostname

❖

whoami

❖

quota quota -v

UNIX Intro.

Machine’s ‘up’ time Name of the machine Your name Your quotas

23

4.3. Calculators ❖

xcalc

Requires X-Windows

❖

expr e

Simple arithmetic

expr 3 + 5 + 7 ❖

UNIX Intro.

bc

Programmable Calculator

24

Using bc ❖

bc 3 + 5 + 7 17 Output ^D

❖

bc -l

Use Maths library

scale=3 Set display to 3 dp 150/60 l(30) natural log function ^D UNIX Intro.

25

❖

bc obase=2 ibase=16 FFC1 ^D

UNIX Intro.

Output base Input base

26

5. UNIX Help 5.1. On-line Help 5.2. UNIX books

UNIX Intro.

27

5.1. On-line Help ❖

man

Manual pages Spacebar to go on; ^C to stop

man gnuchess man man ❖

apropos topic Lists commands related to topic apropos game apropos help

UNIX Intro.

28

man -k topic

Same as apropos

whatis cmd whatis nethack

One-line description

where cmd

Location of command Location

which cmd

UNIX Intro.

29

❖

locate cmd

List files with cmd in their name (or path)

locate game ❖

Output of these commands can be very long. See a screenful at a time with: | more locate game | more apropos print | more

❖ UNIX Intro.

Press spacebar to go on; ^C to stop.

30

5.3. UNIX Books ❖

A Student’s Guide to UNIX, Harley Hahn, McGraw-Hill, 1993.

❖

A Practical Guide to the UNIX System, Mark G. Sobell, Benjamin-Cummings, 3rd Edition, 1995.

❖

An Introduction to Berkeley UNIX, Paul Wang, Wadsworth, 1992.

UNIX Intro.

31

6. The UNIX File System 6.1. 6.2. 6.3. 6.4. 6.5.

UNIX Intro.

An upside-down Tree Some System Directories Where do you login? Pathnames Commands and Pathnames

32

6.1. An upside-down Tree ❖

A simplified UNIX directory/file system: /

etc ...

bin date. . .cal

export user

dev ...

tmp ...

home ad exam.txt UNIX Intro.

..... s3910120 .. proj1 work hobby.c ... ...

33

6.2. Some System Directories ❖

/ root directory

❖

/bin

❖

/etc

❖

/dev

UNIX Intro.

commands

system data files (e.g. /etc/passwd) files representing I/O devices

34

6.3. Where do you login? ❖

Your home directory, which is named after your login ID. /

export user s3910120’s home dir.

home s3910120 hobby.c

UNIX Intro.

proj1 ...

35

6.4. Pathnames ❖

A pathname is a sequence of directory names (separated by /’s) which identifies the location of a directory.

❖

There are two sorts of pathnames – absolute pathnames – relative pathname

UNIX Intro.

36

Absolute Pathnames The sequence of directory names between the top of the tree (the root) and the directory of interest. ❖ For example: /bin /etc/terminfo /export/user/home/ad /export/user/home/s3910120/proj1 ❖

UNIX Intro.

37

Relative Pathnames ❖

The sequence of directory names below the directory where you are now to the directory of interest.

❖

If you are interested in the directory proj1: proj1 if you are in s3910120 s3910120/proj1 if you are in home home/s3910120/proj1 if you are in user

UNIX Intro.

38

7. Working with Directories 7.1. Moving between Directories 7.2. Special Directory Names 7.3. Investigate the System 7.4. Making / Deleting / Renaming Directories UNIX Intro.

39

7.1. Moving between Directories ❖

s3910120’s home directory:

s3910120 hobby.c

UNIX Intro.

proj1

proj2

...

...

40

❖

If you are in directory s3910120 how do you move to directory proj1? cd proj1

❖

UNIX Intro.

You are now in proj1. This is called the current working directory.

41

Print name of current working directory

❖

pwd

❖

Move back to directory s3910120 (the parent directory): cd ..

UNIX Intro.

42

❖

When in proj1, move to proj2 with one command: cd ../proj2

❖

UNIX Intro.

../proj2 is a relative pathname

43

7.2. Special Directory Names / ❖. ❖ .. ❖

❖

~

❖

~user

UNIX Intro.

The root directory The current working directory The parent directory (of your current directory) Your home directory Home directory of user

44

Examples ❖

cd /

❖

cd ~

❖

cd

❖

cd ~ad

❖

cd ../..

UNIX Intro.

Change to root directory Change to home directory (Special case; means cd ~) Change to my home dir. Go up two levels.

45

7.3. Investigate the System ❖

Use cd

❖

cat file

List file

cd /etc cat passwd ❖

ls Directory listing ls List current dir. ls /etc List /etc ls -F

UNIX Intro.

-F option shows types

46

7.4. Making / Deleting / Renaming Directories ❖

Usually, you can only create directories (or delete or rename them) in your home directory or directories below it. mkdir rmdir mv

UNIX Intro.

Make a directory Delete a directory Rename a directory

47

❖

Create a lab directory in your home directory: cd ~ mkdir lab

❖

Create two directories inside the lab directory: cd lab mkdir week1 mkdir week2

UNIX Intro.

48

❖

Delete the week1 directory: rmdir week1

❖

Change the name of week2 to all-weeks mv week2 all-weeks

UNIX Intro.

49

8. Working with Files 8.1. 8.2. 8.3. 8.4. 8.5. 8.6.

UNIX Intro.

Creating a Text File Listing Files Filename Conventions Other Basic Commands Printing I/O Redirection

50

8.1. Creating a Text File ❖

A quick way: cat > file

❖

This will feed the text you type at the keyboard into file until you type ^D (CONTROL and a D together).

❖

A more powerful way is to use vi, a full screen editor (see later).

UNIX Intro.

51

8.2. Listing Files ❖

cat file

List the file

cat hobby.c cat /etc/passwd cat /usr/dict/words ❖

UNIX Intro.

more file

(^C to stop)

List the file a screen at a time. Type spacebar to go on; ^C to stop

52

❖

less file

Like more but more powerful

❖

head file

List the first few lines

❖

tail file

List the last few lines

UNIX Intro.

53

8.3. Filename Conventions ❖

Many files have a name and an extension: file.c A C program file.cpp A C++ program file.txt A text file

❖

However, you can call a file anything. It doesn’t have to have an extension.

UNIX Intro.

54

8.4. Other Basic Commands ❖

cp file1 file2

Copy file1, making file2

❖

mv file1 file2

Rename file1 as file2

❖

rm file rm -i file

UNIX Intro.

Delete file Double-check first

55

❖

wc file

Counts the lines, words, characters in file

❖

grep string file

Search file for string

UNIX Intro.

56

❖

List lines containing ‘Andrew’ in /etc/passwd grep Andrew /etc/passwd

❖

Lines containing ‘printf(‘ in hobby.c grep ‘printf(‘ hobby.c

❖

Lines starting with ‘loca’ in /usr/dict/words grep ^loca /usr/dict/words

UNIX Intro.

57

8.5. Printing Print file

❖

lpr file

❖

lpq

❖

lprm job-number Remove that

List the print queue. Each print job has a number.

print job UNIX Intro.

58

❖

You may have to name the printer with the -P option: lpr -Plj5 hobby.c

❖

UNIX Intro.

lpq and lprm understand the -P option

59

8.6. I/O Redirection ❖

Most commands output to the screen ls

❖

Output can be redirected to a file with‘>‘: ls > dir.txt cal 1997 > year1997

❖

Output can be appended to a file with ‘>>‘ cal 1997 > years cal 1998 >> years

UNIX Intro.

60

❖

Concatenate two files: cat f1 f2 > fs

❖

Input redirection (less common) uses ‘<‘ wc < years

❖

Combine input and output redirection: wc < years > year-counts

UNIX Intro.

61

10. vi ❖

vi is the standard UNIX text editor

❖

Contents 1. Why use vi? 2. vi Basics 3. Moving Around 4. Inserting Text

UNIX Intro.

62

5. 6. 7. 8.

UNIX Intro.

Deletion Cut & Paste File-related Commands Text Substitution

63

1. Why use vi? very powerful ❖ useful simple subset of commands ❖ portable (PCs, mainframes, etc.) ❖ designed for slow networks ❖ full-screen ❖

UNIX Intro.

64

2. vi Basics 2.1. 2.2. 2.3. 2.4. 2.5.

UNIX Intro.

Starting vi Two Modes The vi Window When to type RETURN Finishing a vi Session

65

2.1. Starting vi Start editing file

❖

vi file

❖

Changes are stored in a buffer, so you must save to change the file.

❖

If the machine crashes, the buffer can usually be recovered (see later).

UNIX Intro.

66

2.2. Two Modes ❖

Command mode – move cursor, save, delete text, quit vi, etc.

❖

Input mode – – – –

UNIX Intro.

for inserting text start by typing i; finish with ESC cannot quit, delete, etc. in this mode If in doubt, press ESC a few times. This will put you back in command mode.

67

2.3. The vi Window ❖

Bottom line is the status line

❖

Some, but not all, commands are shown on the status line.

❖

Often you type a command and nothing appears on the screen!

UNIX Intro.

68

2.4. When to type RETURN ❖

Colon commands (e.g. :q!) and search commands (e.g. /text) require a RETURN.

❖

Commands that start with a letter (e.g. ZZ, G) and control characters (e.g. ^L) do not require a RETURN

UNIX Intro.

69

2.5. Finishing a vi Session ❖

UNIX Intro.

Get to command mode (press ESCs) ZZ

save changes to the file and quit (no RETURN)

:q!

quit without saving (press RETURN)

70

3. Moving Around 3.1. Basic Cursor Movements 3.2. Larger Moves

UNIX Intro.

71

3.1. Basic Cursor Movements h j k l w b UNIX Intro.

move cursor one place to left down one up one right one

No RETURN required!

move forward one word back one word

72

3.2. Larger Moves G G

go to last line go to line number

10G

^G

shows the current line number

^F ^B

Forward a screen Back a screen

UNIX Intro.

73

Type RETURN!

/text

UNIX Intro.

Search forward for text

/func

search for func

/printf(

search for printf(

/^foo

search for foo at start of line

74

4. Inserting Text

No RETURN

❖

Move to insertion point

❖

Switch to input mode:

❖

Start typing; BACKSPACE or DELETE for deletion

❖

ESC

UNIX Intro.

i

finish; back in command mode

75

❖

Over a slow network, the screen may not refresh properly

^L UNIX Intro.

refresh screen (in command mode)

76

5. Deletion ❖

Must be in command mode.

x dd D

u UNIX Intro.

Delete character that cursor is on. Delete current line. Delete from cursor position to end of line Undo last command

77

Delete lines i to j :23,29d Delete lines 23 to 29

:i,jd

❖

Special line numbers: . means the current line number ^ means line number 1 $ means last line Delete from current line to the end of file.

:.,$d UNIX Intro.

78

6. Cut & Paste 6.1. Cut & Paste Meaning 6.2. Cut & Paste with Deleted Text 6.3. Moving Text

UNIX Intro.

79

6.1. Cut & Paste Meaning ❖

Cut commands remove text from the screen, and store it in a buffer

❖

Paste commands copy text from the buffer to the screen

UNIX Intro.

80

6.2. Cut & Paste with Deleted Text ❖

d or dd or D delete from screen and store text in a buffer

❖

move cursor to new location

❖

p paste contents of buffer

to right of cursor posn UNIX Intro.

81

6.3. Moving Text ❖

Cut and Paste with move

❖

:i,jmk

:3,8m10 :20m. :1,.m$

UNIX Intro.

move lines i through j to start after line k move lines 3 to 8 to start after line 10 move line 20 to after the current line move lines 1 through current line to the bottom

82

7. File-related Commands :w file :w >> file

writes vi contents to new file appends to file

:w! file :w!

writes over file writes over input file

:r file

read in file; places it starting at current cursor position

UNIX Intro.

83

UNIX Intro.

84

The C Language

UNIX Intro.

85

The C Language Currently, the most commonly-used language for embedded systems ❖ “High-level assembly” ❖ Very portable: compilers exist for virtually every processor ❖ Easy-to-understand compilation ❖ Produces efficient code ❖ Fairly concise ❖

UNIX Intro.

86

C History ❖ ❖ ❖

Developed between 1969 and 1973 along with Unix Due mostly to Dennis Ritchie Designed for systems programming – – – –

❖

UNIX Intro.

Operating systems Utility programs Compilers Filters

Evolved from B, which evolved from BCPL

87

C History ❖

Original machine (DEC PDP11) was very small – 24K bytes of memory, 12K used for operating system

❖

Written when computers were big, capital equipment – Group would get one, develop new language, OS

UNIX Intro.

88

C History ❖

Many language features designed to reduce memory – – –

❖

Forward declarations required for everything Designed to work in one pass: must know everything No function nesting

PDP-11 was byte-addressed – Now standard – Meant BCPL’s word-based model was insufficient

UNIX Intro.

89

Hello World in C #include <stdio.h>

Preprocessor used to share information among source files - Clumsy + Cheaply implemented

+ Very flexible void main() { printf(“Hello, world!\n”); }

UNIX Intro.

90

Hello World in C #include <stdio.h>

Program mostly a collection of functions “main” function special: the entry point “void” qualifier indicates function does not return anything

void main() { printf(“Hello, world!\n”); I/O performed by a library } function: not included in the language

UNIX Intro.

91

Euclid’s algorithm in C “New Style” function int gcd(int m, int n) { int r; while ( (r = m % n) != 0) { m = n; n = r; } return n; } UNIX Intro.

declaration lists number and type of arguments

Originally only listed return type. Generated code did not care how many arguments were actually passed. Arguments are callby-value

92

Euclid’s algorithm in C Automatic variable

int gcd(int m, int n) { int r; while ( (r = m % n) != 0) { Excess arguments m = n; simply n = r; n ignored m }Frame pointer n; ret. addr. Stack return r pointer } UNIX Intro.

Storage allocated on stack when function entered, released when it returns. All parameters, automatic variables accessed w.r.t. frame pointer. Extra storage needed while evaluating large expressions also placed on the stack

93

Euclid’s algorithm in C int gcd(int m, int n) { int r; while ( (r = m % n) != 0) { m = n; n = r; } return n; } UNIX Intro.

Expression: C’s basic type of statement. Arithmetic and logical Assignment (=) returns a value, so can be used in expressions % is remainder != is not equal

94

Euclid’s algorithm in C int gcd(int m, int n) { int r; control-flow while ( (r = m % n) != High-level 0) { statement. Ultimately function m = n; Each becomes a conditional returns a single n = r; value, usually an branch. integer. Returned } through a specific Supports “structured programming” return n;register by convention. } UNIX Intro.

95

Euclid Compiled on PDP-11 .globl _gcd r0-r7 .text PC is r7, SP is r6, FP is r5 _gcd: jsr r5,rsave save sp in frame pointer r5 L2:mov 4(r5),r1 r1 = n sxt r0 sign extend div 6(r5),r0 m / n = r0,r1 mov r1,-10(r5) r=m%n jeq L3 mov 6(r5),4(r5) m = n mov -10(r5),6(r5) n = r jbr L2 L3:mov 6(r5),r0 return n in r0 jbr L1 L1:jmp rretrn restore sp ptr, return

UNIX Intro.

int gcd(int m, int n) { int r; while ( (r = m % n) != 0) { m = n; n = r; } return n; }

96

Euclid Compiled on PDP-11 Very natural mapping from C into PDP-11 instructions.

.globl _gcd .text _gcd: jsr r5,rsave L2:mov 4(r5),r1 sxt r0 div 6(r5),r0 mov r1,-10(r5) jeq L3 mov 6(r5),4(r5) mov -10(r5),6(r5) jbr L2 L3:mov 6(r5),r0 jbr L1 L1:jmp rretrn

UNIX Intro.

Complex addressing modes make frame-pointer-relative accesses easy. Another idiosyncrasy: registers were memory-mapped, so taking address of a variable in a register is straightforward.

97

Pieces of C ❖

Types and Variables – Definitions of data in memory

❖

Expressions – Arithmetic, logical, and assignment operators in an infix notation

❖

Statements – Sequences of conditional, iteration, and branching instructions

❖

Functions – Groups of statements and variables invoked recursively

UNIX Intro.

98

C Types ❖ ❖

Basic types: char, int, float, and double Meant to match the processor’s native types – Natural translation into assembly – Fundamentally nonportable

❖ ❖ ❖

UNIX Intro.

Declaration syntax: string of specifiers followed by a declarator Declarator’s notation matches that in an expression Access a symbol using its declarator and get the basic type back

99

C Type Examples Integer j: pointer to integer, int k

int i; ch: pointer to unsigned char int *j, k; Array of 10 floats unsigned char *ch; 2-arg function float f[10]; of three arrays of five … char nextChar(int, Array char*); function returning int * int a[3][5][10]; int *func1(float); pointer to function returning int int (*func2)(void);

UNIX Intro.

100

C Typedef ❖ ❖

❖

UNIX Intro.

Type declarations recursive, complicated. Name new types with typedef Instead of int (*func2)(void) use typedef int func2t(void); func2t *func2;

101

C Structures ❖

A struct is an object with named fields:

struct { char *name; int x, y; int h, w; } box; ❖

Accessed using “dot” notation: box.x = 5; box.y = 2;

UNIX Intro.

102

Struct bit-fields ❖

Way to aggressively pack data in memory

struct { unsigned int baud : 5; unsigned int div2 : 1; unsigned int use_external_clock : 1; } flags; ❖ Compiler will pack these fields into words ❖ Very implementation dependent: no guarantees of ordering, packing, etc. ❖ Usually less efficient – Reading a field requires masking and shifting UNIX Intro.

103

C Unions ❖

Can store objects of different types at different times

union { int ival; float fval; char *sval; }; ❖ ❖ ❖

Useful for arrays of dissimilar objects Potentially very dangerous Good example of C’s philosophy – Provide powerful mechanisms that can be abused

UNIX Intro.

104

Alignment of data in structs Most processors require n-byte objects to be in memory at address n*k ❖ Side effect of wide memory busses 1 a 32-bit memory bus ❖ E.g., ❖ Read from address 3 3requires two accesses, 4 2 shifting ❖

4 UNIX Intro.

3

2

1

105

Alignment of data in structs ❖ ❖

Compilers add “padding” to structs to ensure proper alignment, especially for arrays Pad to ensure alignment of largest object (with biggest requirement) a

struct { char a; int b; char c; } ❖

UNIX Intro.

Moral: rearrange to save memory

b

b

b

b c

Pad b

b

b

a b c

106

C Storage Classes #include <stdlib.h>

Linker-visible. Allocated at fixed location Visible within file. Allocated at fixed location.

int global_static; static int file_static; Visible within func. Allocated at fixed location.

void foo(int auto_param) { static int func_static; int auto_i, auto_a[10]; double *auto_d = malloc(sizeof(double)*5); } UNIX Intro.

107

C Storage Classes #include <stdlib.h> int global_static; static int file_static;

Space allocated on stack by caller.

Space allocated on void foo(int auto_param) stack by function. { static int func_static; int auto_i, auto_a[10]; double *auto_d = malloc(sizeof(double)*5); Space allocated on heap by library routine. } UNIX Intro.

108

malloc() and free() ❖

Library routines for managing the heap

int *a; a = (int *) malloc(sizeof(int) * k); a[5] = 3; free(a); ❖

UNIX Intro.

Allocate and free arbitrary-sized chunks of memory in any order

109

malloc() and free() ❖ ❖

More flexible than automatic variables (stacked) More costly in time and space – malloc() and free() use complicated non-constant-time algorithms – Each block generally consumes two additional words of memory ◆ ◆

❖

Common source of errors – – – –

UNIX Intro.

Pointer to next empty block Size of this block

Using uninitialized memory Using freed memory Not allocating enough Neglecting to free disused blocks (memory leaks)

110

malloc() and free() ❖

❖ ❖ ❖

UNIX Intro.

Memory usage errors so pervasive, entire successful company (Pure Software) founded to sell tool to track them down Purify tool inserts code that verifies each memory access Reports accesses of uninitialized memory, unallocated memory, etc. Publicly-available Electric Fence tool does something similar

111

Dynamic Storage Allocation What are malloc() and free() actually doing? ❖ Pool ofFree memory segments: ❖

malloc(

UNIX Intro.

)

112

Dynamic Storage Allocation ❖

Rules: – Each segment contiguous in memory (no holes) – Segments do not move once allocated

❖

malloc() – Find memory area large enough for segment – Mark that memory is allocated

❖

free() – Mark the segment as unallocated

UNIX Intro.

113

Dynamic Storage Allocation ❖

Three issues:

❖

How to maintain information about free memory

❖

The algorithm for locating a suitable block

❖

The algorithm for freeing an allocated block

UNIX Intro.

114

Simple Dynamic Storage Allocation ❖

Three issues:

❖

How to maintain information about free memory – Linked list

❖

The algorithm for locating a suitable block – First-fit

❖

The algorithm for freeing an allocated block – Coalesce adjacent free blocks

UNIX Intro.

115

Simple Dynamic Storage Allocation Next Size

Next

Size Size Free block Allocated block malloc(

)

First large-enough free block selected Free block divided into two Previous next pointer updated Newly-allocated region begins with a size value

UNIX Intro.

116

Simple Dynamic Storage Allocation free(a)

Appropriate position in free list identified Newly-freed region added to adjacent free regions

UNIX Intro.

117

Dynamic Storage Allocation Many, many variants ❖ Other “fit” algorithms ❖ Segregation of objects by sizes ❖

– 8-byte objects in one region, 16 in another, etc. ❖

UNIX Intro.

More intelligent list structures

118

Memory Pools ❖

An alternative: Memory pools Separate management policy for each pool

❖

Stack-based pool: can only free whole pool at once

❖

– Very cheap operation – Good for build-once data structures (e.g., compilers) ❖

Pool for objects of a single size – Useful in object-oriented programs

❖ UNIX Intro.

Not part of the C standard library

119

Arrays ❖ Array: sequence of identical ❖

objects in memory int a[10]; means space for ten integers

Filippo Brunelleschi, Ospdale degli Innocenti, Firenze, Italy, 1421

 By itself, a is the address of the first integer  *a and a[0] mean the same thing  The address of a is not stored in memory: the compiler inserts code to compute it when it appears  Ritchie calls this interpretation the biggest conceptual jump from BCPL to C

UNIX Intro.

120

Multidimensional Arrays Array declarations read right-to-left ❖ int a[10][3][2]; ❖ 3“an array 3 of ten arrays 3of three arrays of two ints” ... ❖ In memory ❖

2 2 2

2 2 2

2 2 2

10

UNIX Intro.

Seagram Building, Ludwig Mies van der Rohe,1957 121

Multidimensional Arrays ❖

Passing a multidimensional array as an argument requires all but the first dimension

int a[10][3][2]; void examine( a[][3][2] ) { … } ❖

Address for an access such as a[i][j][k] is

a + k + 2*(j + 3*i) UNIX Intro.

122

Multidimensional Arrays Use arrays of pointers for variable-sized multidimensional arrays ❖ You need to allocate space for and initialize the arrays of pointers int ***a int ***a; ❖ a[3][5][4] expands to The value *(*(*(a+3)+5)+4) ❖

int ** UNIX Intro.

int *

int

123

C Expressions ❖

Traditional mathematical expressions

y = a*x*x + b*x + c; Very rich set of expressions ❖ Able to deal with arithmetic and bit manipulation ❖

UNIX Intro.

124

C Expression Classes ❖ ❖ ❖ ❖ ❖ ❖ ❖ ❖ ❖ ❖

UNIX Intro.

arithmetic: + – * / % comparison: == != < <= > >= bitwise logical: & | ^ ~ shifting: << >> lazy logical: && || ! conditional: ? : assignment: = += -= increment/decrement: ++ -sequencing: , pointer: * -> & []

125

Bitwise operators ❖ ❖

and: & or: | xor: ^ not: ~ left shift: << right shift: >> Useful for bit-field manipulations

#define MASK 0x040 if (a & MASK) { … } /* Check bits */ c |= MASK; /* Set bits */ c &= ~MASK; /* Clear bits */ d = (a & MASK) >> 4; /* Select field */

UNIX Intro.

126

Lazy Logical Operators ❖

“Short circuit” tests save time

if ( a == 3 && b == 4 && c == 5 ) { … } equivalent to if (a == 3) { if (b ==4) { if (c == 5) { … } } } ❖

Evaluation order (left before right) provides safety

if ( i <= SIZE && a[i] == 0 ) { … } UNIX Intro.

127

Conditional Operator ❖

c = a < b ? a + 1 : b – 1;

❖

Evaluate first expression. If true, evaluate second, otherwise evaluate third.

❖

Puts almost statement-like behavior in expressions.

❖

BCPL allowed code in an expression:

a := 5 + valof{ int i, s = 0; for (i = 0 ; i < 10 ; i++) s += a[I]; return s; } UNIX Intro.

128

Side-effects in expressions Evaluating an expression often has sideeffects a++ increment a afterwards a=5 changes the value of a a = foo() function foo may have sideeffects ❖

UNIX Intro.

129

Pointer Arithmetic From BCPL’s view of the world ❖ Pointer arithmetic is natural: everything’s an integer int *p, *q; *(p+5) equivalent to p[5] ❖ If p and q point into same array, p – q is number of elements between p and q. ❖ Accessing fields of a pointed-to structure has a shorthand: p->field means (*p).field ❖

UNIX Intro.

130

C Statements ❖ ❖

Expression Conditional – if (expr) { … } else {…} – switch (expr) { case c1: case c2: … }

❖

Iteration – – –

❖

Jump – – – –

UNIX Intro.

while (expr) { … } zero or more iterations do … while (expr) at least one iteration for ( init ; valid ; next ) { … } goto label continue; go to start of loop break; exit loop or switch return expr; return from function

131

The Switch Statement tmp = expr; ❖ Performs multi-way branches if (tmp == 1) goto L1 else if (tmp == 5) goto L5 switch (expr) { else if (tmp == 6) goto L6 case 1: … else goto Default; break; L1: … case 5: goto Break; case 6: … L5:; break; L6: … default: … goto Break; break; Default: … } goto Break; Break: UNIX Intro.

132

Switch Generates Interesting Code ❖

Sparse case labels tested sequentially

if (e == 1) goto L1; else if (e == 10) goto L2; else if (e == 100) goto L3; ❖

Dense cases use a jump table

table = { L1, L2, Default, L4, L5 }; if (e >= 1 and e <= 5) goto table[e]; ❖

UNIX Intro.

Clever compilers may combine these

133

setjmp/longjmp ❖ ❖

A way to exit from deeply nested functions Space for a return A hack now a formal part of the standard library and registers address

#include <setjmp.h> jmp_buf jmpbuf;

(including stack pointer, frame pointer) Stores context, returns 0

void top(void) { switch (setjmp(jmpbuf)) { case 0: child(); break; case 1: /* longjmp called */ break; Returns to context, making it }}

appear setjmp() returned 1

void deeplynested() { longjmp(jmpbuf, 1); } UNIX Intro.

134

The Macro Preprocessor ❖

Relatively late and awkward addition to the language

❖

Symbolic constants #define PI 3.1415926535

❖

Macros with arguments for emulating inlining #define min(x,y) ((x) < (y) ? (x) : (y))

❖

Conditional compilation #ifdef __STDC__

❖

File inclusion for sharing of declarations #include “myheaders.h”

UNIX Intro.

135

Macro Preprocessor Pitfalls ❖ ❖

❖

Header file dependencies usually form a directed acyclic graph (DAG) How do you avoid defining things twice? Convention: surround each header (.h) file with a conditional:

#ifndef __MYHEADER_H__ #define __MYHEADER_H__ /* Declarations */ #endif UNIX Intro.

136

Macro Preprocessor Pitfalls ❖

Macros with arguments do not have function call semantics

❖

Function Call: – Each argument evaluated once, in undefined order, before function is called

❖

Macro: – Each argument evaluated once every time it appears in expansion text

UNIX Intro.

137

Macro Preprocessor pitfalls ❖

Example: the “min” function

int min(int a, int b) { if (a < b) return a; else return b; } #define min(a,b) ((a) < (b) ? (a) : (b)) ❖ ❖

Identical for min(5,x) Different when evaluating expression has side-effect: min(a++,b) – min function increments a once – min macro may increment a twice if a < b

UNIX Intro.

138

Macro Preprocessor Pitfalls ❖

Text substitution can expose unexpected groupings

#define mult(a,b) a*b mult(5+3,2+4) ❖ Expands to 5 + 3 * 2 + 4 ❖ Operator precedence evaluates this as 5 + (3*2) + 4 = 15 not (5+3) * (2+4) = 48 as intended ❖ Moral: By convention, enclose each macro argument in parenthesis: #define mult(a,b) (a)*(b) UNIX Intro.

139

Nondeterminism in C ❖

Library routines – malloc() returns a nondeterministically-chosen address – Address used as a hash key produces nondeterministic results

❖

Argument evaluation order – myfunc( func1(), func2(), func3() ) – func1, func2, and func3 may be called in any order

❖

Word sizes int a; a = 1 << 16; a = 1 << 32;

UNIX Intro.

/* Might be zero */ /* Might be zero */

140

Nondeterminism in C ❖

Uninitialized variables – Automatic variables may take values from stack – Global variables left to the whims of the OS

❖

Reading the wrong value from a union – union { int a; float b; } u; u.a = 10; printf(“%g”, u.b);

❖

Pointer dereference – *a undefined unless it points within an allocated array and has been initialized – Very easy to violate these rules – Legal: int a[10]; a[-1] = 3; a[10] = 2; a[11] = 5; – int *a, *b; a - b only defined if a and b point into the same array

UNIX Intro.

141

Nondeterminism in C ❖

How to deal with nondeterminism? – Caveat programmer

❖

Studiously avoid nondeterministic constructs – Compilers, lint, etc. don’t really help

❖ ❖

Philosophy of C: get out of the programmer’s way “C treats you like a consenting adult” – Created by a systems programmer (Ritchie)

❖

“Pascal treats you like a misbehaving child” – Created by an educator (Wirth)

❖

“Ada treats you like a criminal” – Created by the Department of Defense

UNIX Intro.

142

Summary ❖ ❖ ❖ ❖

C evolved from the typeless languages BCPL and B Array-of-bytes model of memory permeates the language Original weak type system strengthened over time C programs built from – – – –

UNIX Intro.

Variable and type declarations Functions Statements Expressions

143

Summary of C types ❖ ❖ ❖ ❖ ❖ ❖ ❖

Built from primitive types that match processor types char, int, float, double, pointers Struct and union aggregate heterogeneous objects Arrays build sequences of identical objects Alignment restrictions ensured by compiler Multidimensional arrays Three storage classes – – –

UNIX Intro.

global, static (address fixed at compile time) automatic (on stack) heap (provided by malloc() and free() library calls)

144

Summary of C expressions ❖

Wide variety of operators – – – – – – –

❖ UNIX Intro.

Arithmetic + - * / Logical && || (lazy) Bitwise & | Comparison < <= Assignment = += *= Increment/decrement ++ -Conditional ? :

Expressions may have side-effects

145

Summary of C statements ❖ ❖

Expression Conditional – if-else switch

❖

Iteration – while do-while for(;;)

❖

Branching – goto break continue return

❖

UNIX Intro.

Awkward setjmp, longjmp library routines for nonlocal goto

146

Summary of C ❖

Preprocessor – – – –

❖

symbolic constants inline-like functions conditional compilation file inclusion

Sources of nondeterminsm – library functions, evaluation order, variable sizes

UNIX Intro.

147

The Main Points ❖

Like a high-level assembly language

❖

Array-of-cells model of memory

❖

Very efficient code generation follows from close semantic match

❖

Language lets you do just about everything Very easy to make mistakes

❖ UNIX Intro.

148

Object Oriented Programming

UNIX Intro.

149

Problem Description ❖

UNIX Intro.

“ …customers are allowed to have different types of bank accounts, deposit money, withdraw money and transfer money between accounts”

150

Procedural Approach bool MakeDeposit(int accountNum,float amount); float Withdraw(int accountNum,float amount);

struct Account { char *name; int accountNum; float balance; char accountType; };

UNIX Intro.

151

Procedural Approach cont’d Focus is on procedures ❖ All data is shared: no protection ❖ More difficult to modify ❖ Hard to manage complexity ❖

UNIX Intro.

152

Procedural vs. Object-Oriented ❖

Procedural

❖

Object Oriented

Withdraw, deposit, transfer

Customer, money, account UNIX Intro.

153

Mapping the world to software ❖

Objects in the problem domain are mapped to objects in software

011101

0110100 010101

10011 1110101

11101

11010 10101 UNIX Intro.

154

Object Oriented ❖

Data and operations are grouped together

Account Withdraw

Interface: Set of available operations

Deposit Transfer

UNIX Intro.

155

Data Encapsulation class Account { public: float withdraw(); void deposit(float amount); private: float balance; );

UNIX Intro.

156

Advantages of Encapsulation ❖ ❖ ❖

UNIX Intro.

Protection Consistency Allows change

157

Objects and Classes ❖

Classes reflect concepts, objects reflect instances that embody those concepts. object

Jodie UNIX Intro.

class

Daria

Jane

girl

Brittany

158

Objects and Classes cont’d A class captures the common properties of the objects instantiated from it ❖ A class characterizes the common behavior of all the objects that are its instances ❖

UNIX Intro.

159

Objects and Classes cont’d Class BankAccount Balance InterestYTD Owner Account_number Balance 500 InterestYTD Owner Account_number UNIX Intro.

Operations MakeDesposit Transfer WithDraw GetBalance

Balance 10,000 InterestYTD Owner Account_number

160

Objects as instances of Classes ❖ ❖

The world conceptually consists of objects Many objects can be said to be of the same type or class – My bank account, your bank account, Bill Gates’ bank account …

❖

UNIX Intro.

We call the object type a class

161

Instantiation ❖

An Object is instantiated from a Class BankAccount myAccount; myAccount = new BankAccount;

UNIX Intro.

162

Objects and Classes ❖

Class – Visible in source code – The code is not duplicated

UNIX Intro.

❖

Object – – – –

Own copy of data Active in running program Occupies memory Has the set of operations given in the class

163

Classification Animal Mammal Rodent Mouse

UNIX Intro.

Reptile

Primate Squirel

Cats Rabbit

164

Classification Account Checking Account Value First

UNIX Intro.

Select Access

Savings Account First Interest

165

Inheritance A class which is a subtype of a more general class is said to be inherited from it. ❖ The sub-class inherits the base class’ data members and member functions ❖

UNIX Intro.

166

Inheritance cont’d A sub-class has all data members of its base-class plus its own ❖ A sub-class has all member functions of its base class (with changes) plus its own ❖ Inheritance is meant to implement subtyping (don’t abuse it) ❖

UNIX Intro.

167

Abstraction ❖ ❖

Management of complexity Hierarchical classification: is-a relationship: inheritance has-a relationship: containment

UNIX Intro.

168

Polymorphism ❖ ❖ ❖ ❖

UNIX Intro.

One interface Multiple implementations Inheritance Method overloading

169

What is a good class ? A class abstracts objects ❖ A class should be non-trivial in the context of the program (has data structures and operations different from other classes) ❖

UNIX Intro.

170

Summary What is Object Oriented Programming? ❖ Object-oriented programming is a method of implementation in which programs are organized as cooperative collections of objects, each of which represents an instance of some class, and whose classes are all members of one or more hierarchy of classes united via inheritance relationships ❖

UNIX Intro.

171