INF1060 - H?st 2015

Obligatorisk oppgave 2 i INF1060:


ifish - en kommandotolker for Linux

Utlevering: 14. oktober 2015
Innlevering: 28. oktober 2015, kl. 20:00
Vedlegg: 1. safefork.c

 

 

Intro

For ? sende kommandoer til operativsystemet (OSet) og for OSet ? gi respons tilbake bruker vi ofte et shell - ogs? kalt en kommandotolker. Unix-systemer har ikke noe innebygget vindu-basert grensesnitt, men antar et enkelt tegnbasert grensesnitt hvor en bruker skriver inn strenger av tegn (tekst) og avslutter med ENTER eller RETURN.

Denne oppgaven g?r ut p? ? programmere et slikt shell i programmeringsspr?ket C for Linux á la sh, csh eller bash, men i en sterkt forenklet utgave (programmet skal kunne kj?res p? IFIs standard Linux-maskiner som de p? termstua eller Linux-clusteret - ssh linux). Det skal kunne eksekvere vanlige kommandoer med parametere samt at det skal ha noen innebygde kommandoer i likhet med de vanlige kommandotolkerene.

 

 

Oppgaven

Dette er en omfattende oppgave, og det kan v?re lurt ? ta den stegvis. Resten av oppgaveteksten er derfor skrevet slik. Videre er en del av oppgaven ? skrive ut debug-informasjon ved hjelp av fprintf (se man fprintf) til 'stderr' (ettersom en utskrift sendt til 'stderr' er ubufret, skulle man se utskrift p? skjermen selv om programmet skulle kr?sje. Utskrifter som g?r til 'stdout' kan derimot "forsvinne" i en kr?sj p? grunn av bufring. Se man stderr).

Debug utskriftene kan for eksempel gj?res slik:

 

#ifdef DEBUG 
fprintf(stderr,...);
#endif

Denne printf-kommandoen blir bare eksekvert hvis DEBUG er definert, for eksempel ved at programmet er kompilert med -DDEBUG opsjonen eller ? ha en #define DEBUG i C-filen. Det kan i tillegg til de "obligatoriske" debug-utskriftene, som er spesifisert under og som bare skrives ut i "debug modus", v?re lurt ? legge inn mange testutskrifter underveis p? samme m?te for ? f? oversikt over hva som skjer. Sjekk spesielt om alle tekstoperasjonene fungerer.

 

Kompilering av koden

For ? kompilere koden skal du lage en Makefile (se man make) slik at man kan skrive make i katalogen hvor filene er lagret for ? kompilere programmet. Koden som gis ut i safefork.c skal ikke inkluderes i samme fil som resten av koden, men forbli slik den er utgitt - Makefilen skal passe p? at den kompileres inn. Det kan ogs? v?re lurt (og det er et pluss) ? legge noen av de andre funksjonene (for eksempel de innebygde funksjonene) i egne filer. Makefilen skal ogs? leveres inn og gir poeng.

 

Lese kommando fra tastaturet

Kommandotolkeren skal g? i evig l?kke og hente kommandoer fra brukeren. Det vil si at for hver runde skal den kunne lese inn en kommando fra tastaturet. ifish skal:

 

 

Dele opp den innleste linjen i ord - kommando med parametere

For at kommandotolkeren skal kunne eksekvere en kommando, m? linjen vi leste inn over deles opp i ord skilt av blanke tegn. Det vil si at vi etter ? ha lest inn en linje i oppgaven over skal kunne:

 

 

Utf?re kommandoer

Fra stegene over skulle vi n? ha et program som leser input fra brukeren, deler denne strengen opp i ord og legger disse inn i vektoren param. Neste steg er da ? f? kommandotolkeren til ? tolke disse ordene som kommandoer og tilh?rende parametere, for deretter ? utf?re disse kommandoene ved ? opprette en barneprosess. Vi antar at f?rste ord p? linjen (param[0]) inneholder kommandonavnet og at de etterf?lgende ordene er parametere:

 

 

 

Innebygde kommandoer

Som andre shell skal ifish ha enkelte innebygde kommandoer (i tillegg til exit og quit). Hvis man for eksempel i et vanlig shell pr?ver ? finne hvilken versjon av cd man bruker ved ? utf?re kommandoen type cd f?r man beskjed at dette er en innebygget kommando i shellet:

[vizzini] 1 > type cd 
cd is a shell builtin

Du skal derfor legge inn de innebygde kommandoene som er spesifisert under i shellet -- det vil si h (history) (cd skal ikke implementeres). Disse skal ikke forkes ut eller eksekveres med execve().

h - eksekveringshistorie

En vanlig innebygget kommando er h, som er et alias for history. Denne viser en oversikt over de siste kommandoene (inkludert parametere) shellet har utf?rt. Du skal legge inn h som en innebygget kommando i ifish hvor shellet skal kunne holde de n siste kommandoene. Antallet n skal kunne variere avhengig av hvor mye minne som brukes per kommando (se under). Hvis brukeren s? utf?rer h skal en liste over de siste kommandoene skrives ut hvor eldste kommando ligger ?verst og den nyeste nederst (som vil v?re h) - a la:

paalh@ifish 10 > h

History list of the last 10 commands:
  10: cd 
   9: ls
   8: cd oblig
   7: make
   6: man gcc
   5: man getenv
   4: h
   3: more ifish.c
   2: ifish
   1: h

H?ndtering av minne for history

For ? lagre kommandoene for h, skal du implementere et system som holdes i prim?rminnet. Dette skal v?re et kontinuerlig minne som skal ha plass til 64 8-byte blokker samt en bitmap som skal indikere hvilke blokker som er i bruk og ikke - det vil si at bit-verdiene skal v?re henholdsvis 0 hvis blokkene er ledig og 1 hvis blokker er opptatt. Et eksempel p? hvordan minnet skal allokeres og deles opp er vist i figuren under.

 

Siden en kommando er antatt ? v?re av vilk?rlig lengde, men som nevnt over ikke overstige 120 tegn, kan en enkelt kommando trenge flere slike 8-byte blokker (á la pages i minnet eller diskblokker p? disken). Disse blokkene trenger ikke n?dvendigvis ligge etterhverande. N?r en ny kommando skrives (utf?res av shellet), skal systemet lete etter ledige blokker i bitmapen, allokere de som trengs (sette bittene) og bruke de tilsvarende blokkene for ? lagre kommandoen i disse minneblokkene. Hvis det ikke er nok ledige blokker for ? lagre kommandoen i history, skal systemet kaste ut den eldste kommandoen fra listen, frigj?re dens allokerte datablokker, og igjen pr?ve ? legge inn den nye (evt. gjenta for ? skaffe tilstrekkelig nok plass). N?r en kommando slettes fra listen, skal dens datablokker ogs? slettes, dvs. fjerne innholdet i dem (HINT: Bruk for eksempel bzero).

Metadatastruktur

I tillegg trenger du en type metadatablokk for hver kommando som lagres i history. Metadataene skal legges inn i en struktur som i allefall m? inneholde id-ene til datablokkene som brukes til ? lagre kommandoen. Her kan man gjerne bruke "direktepekere" (her vil det si indekser til bitmapen og datablokk-minnet). Man trenger da 15 slike for ? kunne lagre en kommando p? opptil 120 tegn. I tillegg trenger man et "lengde" felt for ? lagre informasjon om hvor lang kommandoen er. Videre skal metadatablokkene organiseres ved ? bruke en lenket liste - den nyeste kommandoen skal ligge f?rst i listen, og den eldste (og den som eventuelt skal fjernes for ? frigj?re plass) skal ligge sist. Det vil si at datastrukturen ogs? trenger en nestepeker til neste metadatablokk. (Hvis du trenger andre elementer i strukturen skal dette beskrives og argumenteres for.) Et eksempel p? en slik liste er vist under.

 

 

DEBUG 1:Som debug-informasjon skal programmet skrive ut innholdet av bitmapen hvor du skriver ut 0-ere og 1-ere. Hver linje skal v?re p? 32 tegn.

     DEBUG - BITMAP:

     10101010101010111100011001100111
     11000110011001111010101010101011

DEBUG 2:Som debug-informasjon skal programmet skrive ut innholdet av datablokkene. Hver datablokk skal v?re avskilt med to "#" (dvs, "##"). Hver linje skal skrive ut 4 8-byte blokker. (Merk at blokkene som er markert i bitmapen i eksempelet over IKKE stemmer med hvilke blokker som er brukt i eksempelet under).

     DEBUG - DATABLOCKS:

     ##more ifi##sh.c    ##        ##cd oblig##
     ##gcc -DDE##BUG -o m##y_perfec##t_ifish ##
     ##        ##        ##        ##        ##
     ##ifish.c ##        ##        ##        ##
     ##        ##        ##        ##        ##
     ##h -d 5  ##        ##ls -al *##        ##
     ##.pdf    ##        ##        ##man gete##
     ##nv      ##        ##        ##        ##
     
     . . . .

     ##h       ##h 5     ##make    ##        ##

Oppsummert vil dette bety at n?r en kommando skrives inn, skal shellet opprette en metadatablokk og legge denne inn i den listen. Lengden p? kommandoen m? regnes ut og ledige data blokker m? allokeres, sette bittene i bitmapen og legge indeksene til datablokkene inn i "direktepekerene" i strukturen. Tilslutt m? man ikke glemme og lagre kommandoen i datablokkene. Tilsvarende, n?r en kommando m? slettes fra history, skal b?de datablokkene og metadatablokken frigj?res.

h i - utf?r den i'te yngste historiekommandoen

Du skal utvide funksjonaliteten til h slik at hvis et tall i sendes som argument skal, ikke en liste skrives ut, men den i'te yngste kommandoen utf?res. For eksempel, h 3 vil i eksempelet over medf?re at kommandoen more ifish.c blir utf?rt.

h -d i - slette oppf?ring i kommandohistorien

Du skal utvide funksjonaliteten til h med opsjonen -d slik at hvis opsjonen -d oppgis med et tall i, skal den i'te yngste kommandoen slettes fra historien. For eksempel, h -d 3 vil i eksempelet over medf?re at kommandoen more ifish.c blir slettet. Pass p? at resten av listen holdes inntakt selv om en kommando blir slettet.

 

Innlevering

Besvarelsen skal best? av den godt kommenterte kildekoden til programmet og en makefile for kompilering. Under finner dere instruksjoner p? hvordan dere skal levere inn, og ved ? levere inn oppgaven samtykker dere p? at dere overholder reglene for innleveringen.

 

Elektronisk innlevering

Oppgaven skal leveres elektronisk, dvs. at ingen papirkopi er n?dvendig. Dere skal opprette en katalog med deres brukernavn som navn. Denne katalogen skal inneholde alle filer som skal leveres (kode og makefile). Denne katalogen lager dere en tar-ball (tar) av og komprimerer med gzip. Tar-ballen skal navngis med brukernavnet og med postfix .tgz - for eksempel paalh.tgz - og lastes opp p? Devilry f?r tidsfristen utl?per.

 

Regler for innlevering og bruk av kode

Ved alle p?lagte innleveringer av oppgaver ved Ifi enten det dreier seg om obligatoriske oppgaver, hjemmeeksamen eller annet forventes det at arbeidet er et resultat av studentens egen innsats. ? utgi andres arbeid for sitt eget er uetisk og kan medf?re sterke reaksjoner fra Ifis side. Derfor gjelder f?lgende:

  1. Deling (b?de i elektronisk- og papirform) eller kopiering av hele eller deler av l?sningen utviklet i forbindelse med de obligatoriske og karaktergivende oppgavene i kurset er ikke tillatt.

     

  2. Deling/distribuering av kode og oppgavetekst med personer som ikke er eksamensmeldt i inf1060 dette semesteret, med unntak av kursledelsen og gruppel?rere, er ikke tillatt.

     

  3. Hente kode fra annet hold, f.eks. fra andre ``open source'' prosjekter eller kode funnet p? nettet er ikke tillatt.

     

  4. Det er greit ? f? generelle hint om hvorledes en oppgave kan l?ses, men dette skal eventuelt brukes som grunnlag for egen l?sning og ikke kopieres uendret inn.

     

  5. Kursledelsen kan innkalle studenter til samtale om deres innlevering.

Reglene om kopiering betyr ikke at Ifi frar?der 澳门葡京手机版app下载. Tvert imot, Ifi oppfordrer studentene til ? utveksle faglige erfaringer om det meste. Vi oppfordrer til at studentene skal kunne l?re av hverandre, men, som sagt, man skal ikke dele/distribuere/kopiere noen form for kode. Det som kreves er som nevnt at man kan st? inne for det som leveres. Hvis du er i tvil om hva som er lovlig 澳门葡京手机版app下载, kan du kontakte gruppel?rer eller fagl?rer.

Se ellers IFIs retningslinjer


 

Lykke til!
    Michael, Tor og P?l

 






 

Vedlegg 1: safefork.c

#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
#include <sys/errno.h>

extern int errno;

#define MAX_PROCESSES 6

static int n_processes(void)
{
  return system("exit `/bin/ps | /store/bin/wc -l`")/256;
}


pid_t safefork(void)
{
  static int n_initial = -1;

  if (n_initial == -1)  /* F?rste gang funksjonen kalles: */
    n_initial = n_processes();
  else if (n_processes() >= n_initial+MAX_PROCESSES) {
    sleep(2);
    errno = EAGAIN;  return (pid_t)-1;
  }

  return fork();
}

NOTE: Stien til programmene ps og wc kan v?re forskjellig. Sjekk dette med kommandoen which ps eller which wc.