elementair shell programmeren

In dit artikel wordt de shell geprogrammeerd met behulp van script files. Moderne shells bezitten bovendien de mogelijkheid om korte macro's te definiëren met de alias opdracht bijv. alias l='ls -alg '

Aliassen kunnen ingewikkelde commando's vervangen door eenvoudiger te onthouden namen. Ze worden vaak gedefinieerd in ~/.profile, een shell script dat elke keer als iemand inlogt wordt uitgevoerd. Met unalias wordt de definitie weer verwijderd.

variabelen

De werking van de shell is vrij ingewikkeld. Er zijn verschillende manieren waarop de shell reeksen tekens zal vervangen door andere. Een daarvan is de expansie van aliassen: het kommando l ~/*/a* kan worden uitgeschreven tot bijvoorbeeld /bin/ls -alg /home/gast/agf/aardappel /home/gast/agf/aardbei /home/gast/agf/appel /home/gast/autos/audi

De alias kwamen we zojuist tegen; aan 'ls' is hier het pad toegevoegd. De tilde staat voor de home directory, waarop de gebruiker `gast' inlogt; de uitdrukking `a*' wordt door de shell vervangen door een lijst van filenamen die met een a beginnen.

Een variabele is een naam, die door de shell aan een reeks tekens wordt gekoppeld met bijv. L='ls -alg '

Het kommando set zonder argumenten geeft een lijst van alle op dat moment gedefinieerde variabelen met hun waarden. De shell heeft zelf een aantal ingebouwde variabelen en andere variabelen worden bij het inloggen gedefinieerd, zoals $HOME, de home directory van de gebruiker en $PWD, de huidige directory.

We zijn ook al de variabele $PATH tegengekomen, ook wel het zoekpad genoemd. De waarde van $PATH is een lijst van directory's, gescheiden door dubbele punten. Als een commando dat geen slash (/) in de naam heeft, niet is ingebouwd in de shell of als alias is gedefinieerd, wordt gezocht of het commando overeenkomt met de naam van een file in een van deze directory's.

Hetzelfde kunt u doen met het which commando, dat echter niet op alle Unix systemen bestaat, of waarvoor soms een alternatief whence voor bestaat. Voorbeeld: which find

De shell zal een dollarteken gevolgd door de naam van een variabele vervangen door de waarde van de betreffende variabele. Nu kunnen we hetzelfde effekt als voorheen krijgen met $L.

Hadden we echter L de waarde `l' gegeven, dan zou het resultaat geweest zijn: l: command not found Bash en ksh brengen ons in dit geval verder met eval $L Hiermee wordt de uitdrukking `l' nog eens geëvalueerd, nadat de shell de waarde van L heeft gesubstitueerd. Een opdrachtregel als $apenkool zal niets doen en ook geen foutmelding opleveren als de betreffende variabele niet gedefinieerd is.

We krijgen de waarde van de variabele L terug met echo $L. Het dollarteken maakt eigenlijk geen deel uit van de naam. Als we nu een script of ander programma aanroepen waarin de waarde van variabele L gebruikt wordt, zal die echter ongedefinieerd zijn, tenzij we eerst de opdracht export L geven om een lokale variabele te exporteren naar de programma-omgeving. Echo en export zijn ingebouwde functies van de shell.

aanhaling

In de vorige paragraaf werd de waarde die aan L werd toegewezen omgeven door enkele aanhalingstekens. Deze zijn nodig om van de uitdrukking één woord te maken, inclusief de spaties. Dubbele aanhalingstekens hadden ook voldaan. Het verschil is, dat binnen dubbele aanhalingstekens de variabelen nog steeds worden vervangen door hun waarde, en alleen tekst tussen enkele aanhalingstekens letterlijk wordt overgenomen.

Tussen dubbele aanhalingstekens bestaat nog de mogelijkheid om aan te geven dat een enkel teken exact moet worden gekopiëerd; dit gebeurt door er een backslash voor te zetten als escape symbool.

De programmeertaal C definieert een aantal escape symbolen, die ook in de shell kunnen worden gebruikt.

\a (alert)

<BELL> (laat een pieptoon horen)

\b (backspace)

<BS> verplaatst de cursor een stap terug. (`x\bx' kan worden gebruikt om een x vet af te drukken.)

\f (formfeed)

<FF> geeft een nieuwe pagina

\n (newline)

<LF> geeft een nieuwe regel

\r (carriage return)

<CR> verplaatst de cursor terug naar het begin van de regel

\t (tabulator)

<TAB> verplaatst de cursor naar de volgende tab-stop

\t (vertical tab)

<VT> verplaatst de cursor een stap omlaag

Verder kunnen ASCII tekens worden aangeduid in octale notatie, bijvoorbeeld \007 (ook \a) voor het <BELL> teken.

Hierbij zij aangetekend dat de echo opdracht van de shell van zichzelf een <LF> (regeleinde) toevoegt, tenzij er echo -n is gebruikt; gebruikers van bash moeten echo de -e vlag meegeven om de escapes te laten werken. Het resultaat kan verschillen als er oktale codes boven 0200 worden gebruikt.

Een speciale functie van de shell is de commando substitutie, aangegeven door achterwaartse aanhalingstekens, bijv. L=`l` Hier wordt een aparte subshell gestart, waarin het commando ls -alg wordt uitgevoerd; het resultaat is weer te zien met echo "$L"

Probeer nu maar eens wat er gebeurt als de dubbele aanhalingstekens worden weggelaten. Een alternatieve notatie is om de te substitueren opdracht tussen $( en ) te zetten. Daarmee kunnen gesubstitueerde processen bovendien genesteld worden. Let op het verschil tussen de notaties $( lijst;van;commando's) en (lijst;van;commando's): beide voeren de opgegeven opdrachten uit in een aparte subshell, maar waar de uitvoer van de tweede variant gewoon tussen de standaard uitvoer verschijnt, wordt de uitvoer in het eerste geval een deel van de opdrachtregel.

Om een variabele af te scheiden van de rest van de tekst kan deze worden omgeven door dubbele aanhalingtekens of door accolades, zodat de volgende uitdrukkingen alle de waarde van de variabele L evalueren en er de letters `OVE' achter plakken.

echo "$L"OVE
echo ${L}OVE
echo "${L}OVE"							

De beperkingen van de shell als programmeertaal worden duidelijk als je bij de variabele i 1 wilt optellen. Rekenen is mogelijk met behulp van het hulpprogramma expr, bijv. i=$(expr $i + 1) Let erop dat de shell spaties nodig heeft om de woorden te onderscheiden.

parameters

We hebben inmiddels enkele manieren gezien waarop de shell ingevoerde tekens bewerkt, zoals de substitutie van variabelen en verwijderen van aanhalingstekens. Vervolgens wordt een commando in woorden opgeknipt, waarbij witruimte de scheiding tussen de woorden aangeeft. De variabele IFS bevat de tekens die hierbij als scheidingsteken worden gebruikt, standaard zijn dit <SP>, <TAB> en <LF>. Let erop dat een uitdrukking tussen enkele of dubbele aanhalingstekens altijd als een woord wordt gezien, ook al bevat ze spaties. Twee aanhalingstekens direkt achter elkaar tellen als een woord met lengte nul (0).

In een shell script zijn de parameters (c.q. argumenten en vlaggen) beschikbaar via de speciale variabelen $0 t/m $9 (en zonodig ook ${10} en hoger). $0 is de naam van het programma zelf. Daarmee is het mogelijk om bijvoorbeeld gunzip een link naar gzip te laten zijn en het programma verschillend te laten werken afhankelijk van de naam waarmee het is aangeroepen.

De shell kent nog een aantal speciale parameters; we zijn $? al tegengekomen, dat telkens de exit status van het laatste uitgevoerde commando krijgt. $$ bevat het Unix proces nummer van de shell die uw script draait. Dit kan ook handig zijn om unieke filenamen te maken voor tijdelijke bestanden.

De parameters $* en $@ leveren de complete parameterlijst op, met uitzondering van $0. Tussen dubbele aanhalings tekens gezet zal "$*" een woord opleveren dat overeenkomt met "$1 $2 $3…", terwijl "$@" een reeks woorden "$1" "$2" "$3"… geeft. De variabele $# geeft het aantal argumenten.

Hieronder volgt een scriptje om met het gebruik van parameters door de shell te experimenteren. De shift opdracht gooit de eerste parameter weg en schuift de rest een positie op, met uitzondering van $0. De regel met while wordt nader toegelicht in paragraaf herhalingen.

#!/bin/sh

echo "Script $0 aangeroepen met $# parameters:"

while [ $# -gt 0 ]
do 
  echo -n "\"$1\" "
  shift
done
echo
exit 								

Het verwerken van de parameterlijsten kan nog wat ingewikkelder worden. Zo kan met de notatie ${parameter:-woord} een standaardwaarde (default) worden aangegeven voor een weggelaten parameter of met {$parameter:?woord} een foutmelding worden gegeven als de parameter verplicht is, bijvoorbeeld

cp ${1:?"De eerste parameter is verplicht"} \
   ${2:-"."}							

Zoals gezegd wordt een opdracht beëindigd door een puntkomma of regeleinde. Hier is een backslash gebruikt om aan te geven dat de opdracht nog niet afgelopen is.

als-dan

De meest elementaire programma-constructie laat één of meer opdrachten al of niet uitvoeren, afhankelijk van de uitkomst van een test, bijvoorbeeld:

if /usr/bin/test "A" = "a"
then
  echo "Gelijk"
else 
  echo "Verschillend"
fi						

Eerst wordt de opdracht achter if uitgevoerd. Er wordt dan gekeken welke exit status die opdracht oplevert. De meeste programma's geven standaard 0 terug, en 1 of een andere foutcode als er problemen zijn, /bin/true of : is altijd 0, en /bin/false altijd 1. echo 1 zal weliswaar 1 als output geven, maar het resultaat is 0.

De opdracht(en) achter then worden enkel uitgevoerd als de if-opdracht 0 oplevert, anders wordt het deel achter else uitgevoerd, maar het opnemen van een else-tak is niet verplicht. De if-constructie wordt pas uitgevoerd als het sleutelwoord fi is gelezen. In een interactieve shell krijg je een prompt string te zien om aan te geven dat de shell op de volgende opdracht wacht. Deze prompt wordt bepaald door de variabele PS1. Als een opdracht niet afgesloten is, krijgt u de prompt string PS2 te zien. De voorwaardelijke opdrachtregels worden hier ingesprongen om de leesbaarheid te verbeteren.

De Bourne shell is een vrij beperkt programma. Voor eenvoudige berekeningen kan het hulpprogramma expr worden gebruikt en test voor testen en vergelijken. Moderne shells als ksh, bash of tcsh hebben deze faciliteiten vaak ingebouwd. In plaats van de notatie test expressie gebruiken ze [ expressie ]. De shell wil spaties zien tussen de verschillende onderdelen van een expressie, terwijl in de opdracht variabele=waarde juist geen spaties voor of na het =-teken mogen komen. Voor uitgebreidere informatie zie paragraaf expr en paragraaf test.

Bovenstaand voorbeeld zal aangeven dat de strings "A" en "a" verschillend zijn. Hetzelfde geldt voor test "1" = "01" terwijl test "1" -eq "01" moet opleveren dat beide uitdrukkingen hetzelfde getal voorstellen. De opdracht test -e "$file" komt op hetzelfde neer als ls "$file" >/dev/null 2>&1. Zet variabelen tussen dubbele aanhalingstekens, anders zal het fout gaan als de variabele niet bestaat of leeg is.

Er bestaan nog twee beknopte voorwaardelijke opdrachten: commando1 && commando2 en commando1 || commando2 . In beide gevallen wordt eerst commando1 uitgevoerd. In het eerste geval wordt commando2 alleen uitgevoerd als het eerste exit status 0 (nul) oplevert, in het tweede geval als het resultaat van commando1 ongelijk is aan nul. Het resultaat is dus true als commando1 en c.q. of commando2 true opleveren.

meerkeuze tests

Om de waarde van een uitdrukking in de standaard uitvoer te krijgen wordt de echo opdracht gebruikt. Om een waarde van de standaard invoer te lezen en toe te kennen aan een of meer variabelen wordt read naam1 naam2 gebruikt. De variabelen krijgen dan elk een woord van de invoer als waarde. Als er geen variabelen worden opgegeven, wordt er een regel gelezen en in z'n geheel toegekend aan REPLY.

De if constructie kan met meerdere tests worden uitgebreid:

if test1 
then
  commando1 
else 
  if test2
  then 
     commando2
  elsefi
fi						

Dit kan ook korter worden genoteerd.

  
if test1 
then
  commando1 
elif test2
then 
  commando2
elsefi						

Om de inhoud van een variabele met meerdere waarden te vergelijken gebruiken we de case constructie, zoals in het volgende voorbeeld.

echo -n $vraag		# variabele moet gedefinieerd zijn
read antwoord
antwoord=$(expr substr "$antwoord" 1 1 | tr \
  "[a-z]" "[A-Z]")
case $antwoord in
[YJDOS] )
  exit 0 ;;
N )
  exit 1 ;;
* )
  echo "Ongeldig antwoord!" 1>&2
  exit 2 ;;
esac						

Hier wordt een vraag gesteld en een antwoord van de gebruiker ingelezen, waarvan de eerste letter wordt genomen en kleine letters in hoofdletters vertaald. De case constructie vergelijkt antwoord met een aantal patronen en voert de reeks bijbehorende opdrachten uit, die wordt afgesloten met een dubbele puntkomma.

Y (yes), J (ja), D (da), O (oui) of S (si) retourneren exit status 0 (true), N (nein of njet) retourneren 1 (false) en alle andere invoer komt overeen met de asterisk en resulteert in 2 met bijbehorende foutmelding op het standard error kanaal.

Een variant hierop is de select constructie, die niet in de originele Bourne shell voorkomt, waarmee eenvoudige menu's kunnen worden gemaakt.

echo -n $vraag 
select woord in ja nee
do 
  if /usr/bin/test "$woord" != "" 
  then 
    break
  fi
done							

Hier wordt de keuze van de gebruiker beperkt tot 1 (ja) of 2 (nee). Let op dat "$woord" hier tussen aanhalingstekens moet staan omdat de vergelijking anders niet goed gaat als de waarde van de variabele een lege string is (gebruiker heeft ongeldige invoer gepleegd).

herhalingen

In het voorbeeld hierboven wordt de invoer zo lang herhaald, totdat de gebruiker een geldige waarde heeft ingevoerd. Een meer algemene herhaling wordt geschreven als

while test
do 
  opdracht1opdrachtn
done						

Hierin wordt telkens de opdracht achter while herhaald en zo lang als het resultaat 0 of true oplevert wordt de reeks opdrachten tussen do en done herhaald, wat dus ook nul keer het geval kan zijn en de test (inderdaad is dat vaak het test commando) wordt altijd een keer meer uitgevoerd dan de opdrachten. Een voorbeeld van het gebruik van while zagen we in paragraaf parameters.

De until constructie lijkt hier sterk op. Hierin wordt de lijst van opdrachten herhaald zolang als het resultaat ongelijk is aan 0. De uitvoering van het script gaat dan verder met de opdracht na `done'.

until test
do 
  opdracht1opdrachtn
done						

De for constructie wordt ook vaak gebruikt.

for variabele in lijst 
do 
  opdracht1 
  …
  opdrachtn
done						

Achter for staat de naam van een variabele zonder dollarteken. Bij elke doorgang krijgt de variabele de waarde van het volgende woord in de lijst. We geven enkele voorbeelden.

for file in * 
do 
  if [ -f "$file" ] 
  then 
    wc "$file"
  fi
done							

Hier wordt voor elke file in de huidige directory het commando wc uitgevoerd, dat het aantal regels, woorden en tekens in het bestand telt. Gebruik van wc * is niet zo netjes omdat dan ook directory's en speciale files worden meegenomen.

for i in 1 2 3 4 5 6 7 8 9 10
do 
  for j in 1 2 3 4 5 6 7 8 9 10
  do 
    echo -n $( expr $i '*' $j) " "
  done
  echo
done						

Herhalingsopdrachten kunnen prima genest worden zoals in bovenstaand voorbeeld, dat de tafels van vermenigvuldiging afdrukt. Let op de enkele aanhalingstekens rond het sterretje. Er staat -n achter echo om de tafels op één regel te houden en er wordt een spatie tussenruimte ingevoegd.

Als het woord in en de volgende lijst afwezig zijn dan krijgt de variabele achtereenvolgens de parameters toegewezen waarmee het script werd aangeroepen, zodat we het programma van paragraaf parameters kunnen herschrijven als

echo "Programma $0 is aangeroepen met $# parameters"
for i
do
  echo $i
done						

Een while lus kan oneindig doorlopen als voor de test : of /bin/true wordt ingevuld. Een lus kan voortijdig worden verlaten met de break opdracht; met break 2 wordt in geval van twee geneste lussen de buitenste verlaten, enzovoorts. De opdracht continue zorgt ervoor dat de lijst opdrachten niet verder wordt afgewerkt en het script verder gaat met de test.

samenstellingen

Tot de samengestelde commando's behoren if, case, select, while, for, until en de functies, die verderop aan bod komen. Het simpelste samengestelde commando is

{
  opdracht1 
  …
  opdrachtn 
}								

Het groep commando zal de commando's in de groep na elkaar uitvoeren. De exit status van de laatste opdracht is tevens het resultaat van de groep. Zo kan bijvoorbeeld een pijplijn als een opdracht worden behandeld met { opdracht1 | opdracht2; }.

Als een lijst commando's in plaats van accolades tussen ronde haken () wordt gezet, worden die binnen een aparte subshell uitgevoerd. Dit geldt ook voor $( lijst ). In het laatste geval wordt de uitvoer van de lijst als deel van het script gebruikt.

functies

De definitie van een functie bestaat uit diens naam met een paar haken erachter, doorgaans gevolgd door een lijst commando's.

functie-naam()
{
  opdracht1 
  …
  opdrachtn 
}								

Een functieaanroep bestaat uit de naam van de functie gevolgd door de eventuele argumenten gescheiden door spaties. De betreffende commando's worden dan één voor één in de huidige shell uitgevoerd, waarna het script verder gaat waar het gebleven was. Binnen de functie zijn de argumenten beschikbaar als $1 …

De uitvoering van de functie stopt bij de afsluitende accolade of na een return opdracht, die bij voorkeur de laatste opdracht binnen de functie vormt. Achter return kan eventueel een exit status volgen, die aan het aanroepende script beschikbaar komt in $?. De exit status is altijd een geheel getal. Als een string als resultaat gewenst is, kan dat resultaat bijvoorbeeld met echo worden uitgevoerd en de functie via commando substitutie worden aangeroepen. In plaats van for i in 1 2 3 4 5 6 7 8 9 10 kan for i in `range 1 10` worden geschreven met de volgende functie:

range()
{ typeset i i

  i=$1
  while [ "$i" -le "$2" ]
  do
    echo $i
    i=`expr "$i" + 1`
  done
  unset i
}								

Het kan handig zijn om functiedefinities in een apart bestand functies te zetten en die met ./functies of source functies in te lezen. Bash zal een naam eerst proberen te koppelen aan een alias, dan een functie en als laatste een bestand met dezelfde naam gaan zoeken in zijn pad.

Binnen de functie zijn dezelfde variabelen als in de rest van het script te gebruiken en gewijzigde waarden blijven ook na afloop bestaan. In de Korn en Bash shell kunnen ook lokale variabelen worden gedeclareerd met de typeset opdracht, die alleen binnen de functiecontekst bestaat. In Bash kan hetzelfde ook met local worden bereikt. Een lokale variabele maskeert een eventuele globale variabele met dezelfde naam.

enkele voorbeelden

Het volgende voorbeeldprogramma geeft de namen van de ingelogde gebruikers. Na een tweetal functiedefinities volgt het hoofdprogramma, dat bestaat uit een pijp van vijf segmenten.

word()
{ if [ "$#" -gt 1 ]
  then
    i=0; n=$1; shift
    for j in $@
    do
      if [ $i = $n ]
      then
        echo "$j"
        break
      else
        i=$(expr $i + 1)
      fi
    done
  fi
} 

item()
{ OFS=$IFS; IFS=":"
  NR=$1; shift

  word $NR "$@" 
  IFS=$OFS
}

# het hoofdprogramma 
who \
| while read LINE1
  do 
    while read LINE2 
    do
      if [ "$(word 0 "$LINE1")" = 
           "$(item 0 "$LINE2")" ]
      then
        echo -e "$(item 0 "$LINE2")\011$(item 4
          "$LINE2")"
      fi
    done </etc/passwd
  done \
| sort \
| uniq -c							

De functie word retourneert het 1e argument, dat wordt gebruikt om een regel in woorden te splitsen; handiger dan daar awk voor te gebruiken. De functie item maakt handig gebruik van de ingebouwde shell variabele IFS om de dubbele punt in plaats van de spatie als scheidingsteken te gebruiken. Het hoofdprogramma doet niets anders dan uit de uitvoer van who de username te knippen en die te vergelijken met het corresponderende veld uit /etc/passwd. De uitvoer wordt dan gesorteerd en dubbele regels verwijderd.

Deze functies worden ook weer gebruikt in het volgende script voor systemen die niet over een which commando beschikken (zie paragraaf variabelen). Dit script houdt echter geen rekening met aliassen en ingebouwde functies van de shell.

which_p()
{ f=0
  while :
  do
    f=`expr $f + 1`
    dir=`item "$f" "$PATH"`
    if [ "$dir" = "" ]
    then
      break
    fi
    path=$dir/$1
    if [ -f "$path" ]
    then
      echo "$path"
      break
   fi
done
}

# het hoofdprogramma `which'
if [ `expr match "$1" '.*/.*` -gt 0 ]
then
  if [ -f "$1" ]
  then
    echo "$1"
  fi
else
  echo `which_p "$1"`
fi								

Het volgende programma toont verschillen tussen twee bestanden, maar het is een stuk beperkter dan het diff commando. Hier wordt zoals uitgelegd in paragraaf processen en hun in- en uitvoer het standaard invoerkanaal omgeleid naar het bestand dat als eerste argument op de commandoregel is meegegeven en er het tweede bestand wordt gekoppeld aan het derde invoerkanaal.

doit()
{ LINE=0
  while read EEN<&0
  do
    LINE=`expr $LINE + 1`
    read TWEE<&3
    if [ "$EEN" != "$TWEE" ]
    then
      echo "$LINE""c""$LINE"
      echo "< $EEN"
      echo "---"
      echo "> $TWEE"
    fi
  done
}

# hoofdprogramma					
if [ "$#" -ne 2 ]
  then
  echo "Usage: $0 file1 file2"
  exit 1
fi
if [ -r "$1" -a -r "$2" ]
then
  doit 0<$1 3<$2
  exit 0
else
  echo "Invoerbestand(en) onleesbaar"
  exit 1
fi 								

een voorbeeld van een recursieve functie

Een functie mag ook zichzelf aanroepen (recursie), waarbij je moet voorkomen dat dat proces oneindig doorgaat. In onderstaand voorbeeld voor bash en ksh vindt de recursie alleen plaats als $1 > 0 en wordt het argument verlaagd om te zorgen dat na een aantal stappen $1 gelijk wordt aan 0.

Hanoi()
{ typeset i aantal

  if [ "$1" -gt "0" ]
  then
    aantal=$(expr $1 - 1)
    Hanoi "$aantal" "$2" "$4" "$3"
    echo "Verplaats een schijf van $2 naar $3"
    Hanoi "$aantal" "$4" "$3" "$2"
  fi
}
# Aanroepen met: 
Hanoi 4 "A" "B" "C"						

Voor wie het spel de Torens van Hanoi nog niet kent: je hebt een toren van 4 (of 64, maar dan duurt het spel erg lang) gouden schijven van verschillende diameter, die je één voor één van stapel A naar B moet verplaatsen, waarbij nooit een grotere schijf bovenop een kleinere mag komen te liggen. De optimale oplossing is om de bovenste drie schijven eerst recursief van A naar C te verplaatsen, waarna de onderste schijf van A naar B kan worden verplaatst en de rest weer recursief van C naar B.

Om te bewijzen dat een recursief algorithme korrekt is, is inductie nodig. Het is triviaal in te zien dat het algorithme een stapel van nul schijven van A naar B verplaatst door niets te doen. Voor n > 0 verplaats je eerst de bovenliggende (n - 1) schijven van A naar C en na het verschuiven van de ne, weer van C naar B. Als we mogen aannemen dat het verplaatsen van (n - 1) schijven korrekt wordt uitgevoerd, dan gaat werkt het op deze manier ook voor een toren van n schijven.

De inductieregel stelt, dat aangezien het algorithme het gewenste effekt heeft voor n = 0 en dat voor elke n ⩾ 0 geldt, dat als het goed gaat voor n, ook een toren van (n + 1) schijven korrekt wordt verwerkt. Op dezelfde manier is te bewijzen dat als elke schijf groter is dan de schijf erboven, het algorithme nooit een grotere schijf bovenop een kleinere zal leggen: de toren van (n - 1) schijven is altijd kleiner dan de onderste en de onderste schijf komt nooit ergens bovenop te liggen.

Uit het algorithme volgt een recurrente betrekking voor het aantal verplaatsingen:

V(0) = 0
V(n) = 2 × V(n-1) + 1

Door een tabel te maken van de waarden voor verschillende n zie je al snel dat dit overeenkomt met V(n) = 2n-1, wat vervolgens geverifiëerd kan worden.

V(0) = 20-1 = 0
V(n) = 2 × (2n-1-1) + 1 = 2n - 1

Bewijzen dat er geen snellere weg bestaat, is moeilijker. Het kritieke pad is het verplaatsen van de onderste schijf van A naar B. Voor dat het zover is, moeten de schijven erboven eerst op één of andere manier naar C worden verplaatst en daarna weer naar B. Een van de weinige alternatieven is om eerst van A naar C te verplaatsen, en daarna van C naar B, maar dat maakt het enkel langer. Welke keuze je ook maakt, het heeft geen invloed op het verplaatsen van de resterende schijven.

signalen

We hebben al gezien hoe we processen in de achtergrond kunnen starten en kennis gemaakt met een manier om de manier om twee processen te coördineren door middel van een pijp: het eerste proces mag zolang in de pijp schrijven totdat de kleine buffer vol is; dan zal Unix het stoppen totdat er weer voldoende ruimte vrij is. Het lezende proces wordt telkens als de pijp leeg is in de wacht gezet.

De meeste vormen van interprocescommunicatie vergen een hogere programmeertaal. Voor de shell programmeur zijn de signalen het belangrijkst. Unix heeft twintig tot dertig voorgedefinieerde signalen plus twee vrij definieerbare. Met de opdracht kill signaal proces stuur je een signaal naar het opgegeven proces. De nummers van de processen zijn met ps te achterhalen. Het nummer van het proces zelf is te vinden in de variabele $$ en in bash zit het ouderproces in $PPID. De nummers van de signalen verschillen enigszins per Unix versie; de signalen kunnen ook met symbolische namen worden aangeduid; voor bash beginnen die met de letters SIG, maar in de korn shell moet dit voorvoegsel worden weggelaten.

Het effekt van een signaal is in de meeste gevallen dat het opgegeven programma onmiddellijk wordt beeindigd. Voor SIGKILL (9) is dit altijd het geval. Het ligt voor de hand dat alleen root het recht heeft om andermans processen te doden. Het besturingssysteem kan zelf besluiten een proces een signaal te geven. Als een programma stopt met segmentation violation, bus error, floating point exception of illegal instruction duidt dat meestal op een programmeerfout; shell scripts veroorzaken deze fouten zelden.

De gebruiker heeft een snellere manier om signalen naar het proces op de voorgrond te sturen. Deze kunnen vrij worden veranderd met het commando stty. Met stty -a krijg je een lijst van de ingestelde waarden, bijvoorbeeld Ctrl-D voor SIGHUP, Ctrl-C of Del voor SIGINT, Ctrl-\ SIGQUIT. Met Ctrl-Z wordt een lopend programma tijdelijk onderbroken. Onder bash kan een script zichzelf onderbreken met de suspend opdracht. De ingebouwde opdrachten met fg en bg zetten een onderbroken job voort in de voor- resp. achtergrond.

Met de opdracht sleep seconden wordt een programma tijdelijk onderbroken en zal het na het opgegeven aantal seconden met SIGALRM worden gewekt. De wait opdracht onderbreekt een proces zolang totdat het van Unix het signaal SIGCHLD krijgt dat het opgegeven kind proces of job in de achtergrond beëindigd is. Wait zonder argumenten wacht totdat alle kinderen afgestorven zijn. Als een proces in de voorgrond gestart is, wacht de ouder zonder expliciet wait commando.

Een proces kan ervoor kiezen bepaalde signalen gewoon te negeren, met uitzondering van SIGKILL en SIGSTOP. Het SIGHUP signaal dat aangeeft dat een terminalgebruiker de (telefoon)verbinding heeft opgehangen wordt genegeerd met nohup commando&. De standaard uitvoer en error kanalen worden dan omgeleid naar het bestand nohup.out.

Signalen worden asynchroon verwerkt, onafhankelijk van waar een proces mee bezig was en na afloop gaat het programma verder waar het gebleven was, tenzij het beëindigd is.

Met het commando trap commando signa(a)l(en) wordt aangegeven dat een bepaald commando moet worden uitgevoerd als het volgende signaal c.q. één van de signalen wordt ontvangen. Dit zal vaak de naam van de functie zijn die het betreffende signaal moet afhandelen. Als een script voortijdig moet worden afgebroken zal zo'n functie bijvoorbeeld tijdelijke bestanden verwijderen.

Trap heeft geen effekt op kind processen. Als het commando - luidt of ontbreekt, dan wordt de oorspronkelijke handelwijze hersteld. Als het commando een lege string is, dan zal de lijst van signalen door het script worden genegeerd.