We all must beware of the yellow pearl Phil Lynott — Yellow Pearl
pr og
ra
ui ke br
ig
m
ge
ar ad
rs
rp
a’
s
besturingssystemen & netwerken
algo r com itmen plex & iteit
s
e ati
Week
m m ee
7
c pli
ap
en
m ste
sy
Parel 110: Besturingssystemen en Netwerken
7.1
Inleiding In deze parel keren we terug naar de computersystemen. In de allereerste parel ging het over de systemen op het laagste niveau van abstractie: de echte hardware. We gaan nu op een wat hoger niveau van abstractie kijken. Ten eerste komen we dan het besturingssysteem tegen: een stuk software dat allerhande beheerstaken op de achtergrond doet, zoals het zorgen dat meerdere programma’s schijnbaar tegelijk (maar eigenlijk in snelle afwisseling) de processor kunnen gebruiken. En ten tweede bekijken we computernetwerken, waarvan het internet het meest bekende voorbeeld is: onderling verbonden computers die wereldwijde communicatie mogelijk maken.
7.1.1 Globale beschrijving parelopdracht In de meeste parels wordt je gevraagd iets te ontwerpen en/of maken (veelal door te programmeren). Bij een technische opleiding op wetenschappelijk niveau hoort echter ook onderzoeken. Dat gaan we in de twee parelopdrachten van deze week doen. We gaan experimenteel onderzoeken hoe twee besturingssystemen zich gedragen als ze meerdere programma’s tegelijk moeten draaien. Verder gaan we observeren hoe een bekend computernetwerk, namelijk het internet, werkt. Je werkt met z’n twee¨en aan de opdrachten.
7.1.2 Studiemateriaal en tools Het studiemateriaal voor deze week is te vinden op blackboard, in de vorm van twee documenten: • Een document over besturingssystemen. • Een document over computernetwerken. De tools die we gaan gebruiken zijn: • Een teksteditor.
80
Week 7 – Parel 110: Besturingssystemen en Netwerken
U 1 2 3 4 6 7 8 9
Ma
Ma W W W W P P P P
1–4 6 7
8–9 Di
1–2 3–4 6–7 8–9
Wo
Di
tts tts hc hc
D∞ D∞ D∞ D∞
hc hc ipr ipr
D∞ D∞ S24 S24
P P P P A A P P
Wo
hc hc ipr ipr
D∞ D∞ S24 S24
wc wc zs zs
D24 D24 N N
P P P P
wc wc zs zs
D24 D24 N N
Do P P P P W W W W
opd2 opd2 opd2 opd2
Vr S∞ S∞ S∞ S∞
zs N zs N wc D24 wc D24
P P P P E E E E
zs zs tts tts
N N D∞ D∞
pj6 pj6 pj6 pj6
D∞ D∞ D∞ D∞
Afk Werkvorm col Colstructie hc Hoorcollege ipr Instructiepracticum opd Opdracht pfb Peer feedback pj Project qa Vragenuur wc Werkcollege tts Toets zs Zelfstudie
Afk P E A W
Onderdeel Parel Eindproject Academ. vaardigh. Wiskunde
Afk Begeleiding D Docent S Studentassistent N Geen
Wiskunde Hoorcollege. In dit hoorcollege maak je kennis met de doelen en werking van besturingssystemen. Film: “Revolution OS”. Deze film gaat over de geschiedenis van het besturingssysteem Linux. Linux is gebaseerd op een geheel andere filosofie dan de meeste commerci¨ele software, namelijk “Open Source” en “Free Software”. In deze film maak je dus ook daarmee kennis, en met een manier van werken die geheel anders is dan je in de parel over requirements engineering hebt geleerd. Begin met het besturingssystemen-deel van de parelopdracht, zie hoofdstuk 7.2.2. Hoorcollege. In dit hoorcollege maak je kennis met de werking van computernetwerken, en dan met name het internet. Begin met het netwerken-deel van de parelopdracht, zie hoofdstuk 7.2.3. Academische vaardigheden Zelfstudie: bestudeer de theorie over besturingssystemen en netwerken, vooral ook met het oog op het werkcollege van morgen.
8–9
Wiskunde vervalt. Werkcollege. We gaan rekenen aan de vertraging die data ondervindt onderweg door het netwerk. De opgaven staan in hoofdstuk 7.2.1. Zelfstudie en/of parelopdrachten.
Do
1–4 6–9
Voltooi de beide parelopdrachten, en lever de verslagen in. Wiskunde.
Vr
1–2 3–4 6–9
Zelfstudie ter voorbereiding op de toets. Toets. Tijd voor het project, of zo nodig om de parelopdrachten af te maken.
1–4 6–7
Week 7 per sessie
7.1.3 Verplichte sessies en deliverables
81
• Python. • Wireshark, waarmee je dataverkeer over het internet zichtbaar kunt maken; dit kun je zelf installeren vanaf http://www.wireshark.org • Traceroute, waarmee je na kunt gaan welk pad je pakketjes door het internet nemen (staat normaliter al op je computer). • Een kant-en-klare Linux installatie die we op USB-sticks ronddelen, samen met het programma virtualbox: dit is een z.g. virtuele machine waarin deze Linux-installatie kan draaien. Maar als je zelf een “echte” Linux-installatie op je laptop hebt, mag je die natuurlijk ook gebruiken.
7.1.3 Verplichte sessies en deliverables Verplichte elementen van deze week zijn: • Deelname bij de Academische Vaardigheden-sessie. • Deelname aan de toets. • Inleveren van de beide parelopdrachten.
7.2
Beschrijving van de opgaven Deze week heeft een set werkcollegeopgaven, en twee parel-deelopdrachten: een over besturingssystemen en een over netwerken.
7.2.1 Werkcollegeopgaven over vertraging in netwerken
+
7.1 Propagation/Transmission delay In this problem, we will explore propagation delay and transmission delay, two central concepts in networking. Consider two hosts, A and B, connected by a single link of rate R bps. Suppose that the length of the link is ` meters, and suppose the propagation speed along the link is v m/s. Host A is to send a packet of size L bits to bost B. (a) Express the propagation delay, dprop , in terms of ` and v. (b) Express the transmission time of the packet, dtrans , in terms of L and R. (c) Suppose bost A begins to transmit a packet at time t = 0. At time t = dtrans , where is the last bit of the packet? (d) Suppose dprop is greater than dtrans . At time t = dtrans , where is the first bit of the packet? (e) Suppose dprop is less than dtrans . At time t = dtrans , where is the first bit of the packet? 2
+
7.2 Circuit, Message and Packet-Switching Consider sending a message (or file) of F bits over a path of Q links. Each link transmits at R bps. The network is lightly loaded so that there are no queuing delays. Also neglect propagation delays and the length of headers. (a) Suppose that the network is a circuit-switched network. Further suppose that the transmission rate of the circuit between source and destination is R bps. How long does it take to send the file? (b) Suppose the network is a “message-switched” network: the entire message (file) is sent as a single, very large, packet. How long does it take to send the file? (c) Finally, suppose the network is a packet-switched network and the F bits are broken up into M packets of L bits each (with M and L such that F = M · L). How long does it take to send the file? Hint: don’t forget that while the first packet travels over the second link, the second packet can already travel over the first link.
82
Week 7 – Parel 110: Besturingssystemen en Netwerken
2
+
7.3 Bandwidth-delay product Suppose two hosts, A and B, are separated by 20 000 kilometers and are connected by a direct link of R = 2 Mbps. Suppose the propagation speed over the link is 2.5 · 108 m/s. (a) Calculate the bandwidth-delay product, R · dprop . (b) Consider sending a file of 800 000 bits from Host A to Host B. Suppose the file is sent continuously as one large message. What is the maximum number of bits that will be in the link at any given time? (c) Provide an interpretation of the bandwidth-delay product. (d) What is the width (in meters) of a bit in the link? Is it longer than a football field? (e) How long does it take to send the file, assuming it is sent continuously? (f) Suppose now the file is broken up into 10 packets with each packet containing 80 000 bits. Suppose that each packet is acknowledged by the receiver and the transmission time of an acknowledgement packet is negligible. Finally, assume that the sender cannot send a packet until the preceding one is acknowledged. How long does it take to send the file? (g) Compare the previous two answers. 2
+
7.4 Statistical Multiplexing Suppose users share a 3 Mbps link. Also suppose each user requires 150 kbps when transmitting, but each user transmits only 10 percent of the time. (a) If circuit switching is used, how many users can be supported? Henceforth, suppose packet switching is used. (b) Find the probability that a given user is transmitting. (c) Suppose there are 120 users. Find the probability that at any given time, exactly n users are transmitting simultaneously. (Hint: Use the binomial distribution.) (d) Find the probability that there are 21 or more users transmitting simultaneously. 2
7.2.2 Parelopdracht besturingssystemen: meten aan multitasking Een multitaskend besturingssysteem moet na elkaar de verschillende jobs (programma’s) uitvoeren. Als geen van de jobs op I/O staat te wachten, wordt dit heen en weer schakelen tussen de jobs periodiek gedaan. Doel van deze opdracht is te meten, bij meerdere besturingssystemen, wat dit tijdsinterval is (“timeout” genoemd in hoofdstuk 2 van het studiemateriaal).
+
7.5 Schrijf een Python-programmaatje dat in een eindeloze lus telkens de klok uitleest vergelijkt met de vorige waarde, en het verschil print als het “groot genoeg” is (hoeveel groot genoeg is, zul je zelf moeten uitproberen terwijl je de volgende opgave doet; zet de drempel voorlopig maar op 1 ms). Het idee hierachter is dat zolang het programma continu draait, er niets geprint wordt. Maar zodra het programma enige tijd niet gedraaid heeft, omdat het besturingssysteem de CPU door een andere programma liet gebruiken, wordt er wel iets geprint, waaruit we kunnen afleiden hoe lang het programma heeft moeten wachten. Hint: je kunt de klok uitlezen met de time() functie uit de module time; of, onder MS-Windows, de clock() functie uit diezelfde module. 2
+
7.6 Onderzoek het schedulingsgedrag van twee besturingssystemen door steeds meer exemplaren van je programmaatje tegelijk te draaien. Probeer te verklaren wat je ziet. Betrek daarbij ook het overzicht van lopende processen dat je besturingssysteem kan tonen (Task Manager onder MS-Windows; top onder Linux), en informatie die je hebt of kunt vinden over het aantal cores van je processor. Indien mogelijk, probeer dan naast MS-Windows ook native Linux1 (dus niet in de virtual box omgeving) 1 Er zullen een paar USB-sticks beschikbaar zijn waarmee je je laptop Ubuntu Linux kunt laten draaien zonder het op de harde schijf te hoeven installeren. Voel je vooral vrij om zelf wat in de Ubuntu-omgeving rond te kijken, maar hier geven we even een paar hints om op gang te komen. Via het bovenste icoontje in de linker balk kom je op wat Ubuntu de ‘Dash’ noemt, waar onder andere recent gebruikte programma’s staan. Als je hier ‘terminal’ intypt, of ‘xterm’, wordt er een terminal gestart. In zo’n terminal kun je bijv. python starten, of gedit
7.2.3 Parelopdracht netwerken: experimenteren met Wireshark en Traceroute
83
uit, of MacOS; we hebben gemerkt dat de nauwkeurigheid van de klok die Python kan aflezen daar veel groter is dan wanneer je in virtualbox werkt. Bespreek je bevindingen met een studentassistent, en beschrijf ze in een kort verslag (ca. 1 A4), waarin je in elk geval aangeeft wat je zag bij de verschillende aantallen simultane programma’s en wat je daaruit concludeert t.a.v. de grootte van de timeout. Lever dit verslag in op Blackboard. 2
7.2.3 Parelopdracht netwerken: experimenteren met Wireshark en Traceroute Kennismakingsopdrachten In deze opdrachten gaan we vooral bezig met de tool Wireshark. Wireshark is een programma dat alle pakketjes laat zien die je computer verzendt en ontvangt via zijn netwerkverbinding (draad of draadloos). Je kunt het downloaden op http://www.wireshark.org.
+
7.7 Download en installeer wireshark, en probeer het uit: start een “capture” (je moet wellicht nog even iets instellen zoals welke netwerk-interface van je computer gebruikt wordt), doe iets op internet (bijv. een webpagina ophalen), stop de capture, en aanschouw het resultaat. Bereken hoeveel pakketten je computer in deze tijd per seconden ontving en verzond. 2 We hebben geleerd dat elke computer in principe een hostname heeft (zoals www.utwente.nl), en een IP-adres (zoals 130.89.3.249).
+
7.8 Onder zowel Windows als Linux kun je nslookup gebruiken om het IP-adres bij een hostname te zoeken, door in een commandprompt nslookup www.utwente.nl in te typen. (a) Open een command window en gebruik het nslookup commando om het IP-adres te vinden van de host telnetw.ewi.utwente.nl . (b) Gebruik Wireshark om te achterhalen wat het IP-adres is van de computer waaraan dit wordt gevraagd (de z.g. nameserver). Oftewel: start Wireshark, start capture, doe dat nslookup-commando, stop capture, en bekijk dan de gecapturede pakketten. (c) Van welk IP-adres is het verzoek afkomstig; oftewel, wat is je eigen IP-adres? 2 We hebben ook geleerd hoe een webpagina wordt opgehaald: eerst wordt er een TCP-verbinding opgezet naar de webserver, daarover wordt een “GET” request gestuurd, en vervolgens stuurt de server de HTMLcode terug die beschrijft hoe de webpagina eruit ziet.
+
7.9 Start capture, ga in een webbrowser naar http://telnetw.ewi.utwente.nl:7701/ , stop capture. Zoek het pakketje waarin het eerste deel van het HTML-antwoord van de server zit, en beantwoord de volgende vragen: (a) Hoeveel bytes zitten er in de IP-header? (b) Hoeveel bytes zitten er in de TCP-header? (c) Hoeveel bytes aan applicatielaagdata zitten er in dit pakket? 2
+
7.10 Beide kanten kunnen meerdere TCP-verbindingen tegelijk hebben, en het onderscheid wordt gemaakt d.m.v. poortnummers. Het poortnummer aan de serverkant is 7701; wat is het poortnummer aan de clientkant? Is dit hetzelfde als je de pagina nogmaals ophaalt? Waarom is dat logisch? 2
+
7.11 Je ziet dat de pakketten allemaal een volgnummer (SEQ) hebben, en een bevestigingsvolgnummer (ACK) waarmee de goede ontvangst van pakketten wordt bevestigd. (a) Tellen de volgnummers pakketten of bytes? (b) Is het bevestigingsvolgnummer het nummer van het laatst ontvangen pakket, of het nummer dat als volgende verwacht wordt? (een teksteditor), of xterm & (een extra terminal), of top (geeft een overzicht van alle processen die draaien; dit verlaat je door op q te drukken).
84
Week 7 – Parel 110: Besturingssystemen en Netwerken
2 Gebruik de tool traceroute (onder windows: tracert) om het pad naar gaia.cs.umass.edu in kaart te brengen.
+
7.12 Hoe loopt dit pad? Kun je zien waar we de UT verlaten, en waar de oceaan wordt overgestoken? 2
Eindopdrachten
+
7.13 Probeer een zo lang (meeste hops) en een zo langzaam (grootste round-trip-tijd) mogelijk pad in het internet te vinden, gerekend vanaf de UT natuurlijk, en documenteer deze met traceroute. 2
+
7.14 Vergelijk het netwerkverkeer in Windows en Linux (of een ander besturingssysteem naar keuze). Kiezen ze de poortnummers op dezelfde manier? En de TTL? En de opties bij het beginnen van een TCPverbinding? Documenteer je bevindingen in een kort (max. 1 A4) verslag dat je inlevert op Blackboard. 2
Bonusopdracht Er zijn in deze parel twee halve bonuspunten te verdienen. Eerste halve bonuspunt: passwords in http
De eerste halve bonuspunt kun je verdienen door te achterhalen wat de username en password zijn die iemand in een (door de docenten op blackboard aangeleverde) trace-file gebruikt om te proberen met gewoon http i.p.v. het versleutelde https in te loggen op een website. Tweede halve bonuspunt: vertraging in wachtrijen simuleren
De vertraging van pakketjes in wachtrijen (“queueing delay”) berekenen is niet zo makkelijk, omdat de lengte van die wachtrijen voortdurend varieert; vandaar dat we die op het werkcollege gemakshalve hebben verwaarloosd. Een manier om er toch iets over te zeggen, is door middel van simulatie: het gedrag van de wachtrij nabootsen in software, en dan kijken hoe lang een pakketje gemiddeld staat te wachten. Overigens is simulatie een veel algemener bruikbare techniek om in de ontwerpfase al na te gaan hoe goed een systeem zal gaan werken. In deze tweede bonusopdracht wordt je gevraagd een simulatieprogramma te schrijven dat dit doet. Neem aan dat er bij een router gemiddeld 0,8 pakketten per seconde aankomen met tussen twee opeenvolgende pakketten telkens een willekeurige tijd, die een z.g. exponenti¨ele verdeling volgt; in Python kun je dit soort willekeurige getallen genereren met random.expovariate(0.8), mits voorafgegaan door import random . Neem verder aan dat alle pakketten even lang zijn, en daardoor dezelfde transmissietijd van precies 1 seconde hebben. Simuleer 100000 dergelijke pakketten; houd van elk pakket bij hoe lang het heeft moeten wachten, en bereken de gemiddelde wachttijd. Bekijk ook ’ns hoe deze gemiddelde wachttijd verandert als er meer of minder dan 0,8 pakketten per seconde aankomen.
Inleveren Doe het inleveren op Blackboard s.v.p. als volgt: • Vul in het tekstvak op Blackboard je eigen naam en studentnummer, en dat van degen met wie je hebt samengewerkt. • Voeg losse files toe, 1 per opdracht, met de volgende namen: – multitasking.pdf voor opdracht 7.6
7.3 Voorbeeldvragen toets
85
– netwerk.pdf voor opdrachten 7.13 en 7.14 – Desgewenst voor de eerste bonusopgave: password.pdf waarin je het gevonden password zet en een korte uitleg hoe je het gevonden hebt – Desgewenst voor de tweede bonusopgave: queueing.pdf waarin je uitleg geeft, en queueing.py met daarin je simulatieprogramma (als het in Python is, anders natuurlijk een andere passende extensie). • Voeg de losse files niet samen in 1 .zip of .rar file, want dat is veel meer werk bij het nakijken.
7.3
Voorbeeldvragen toets Over besturingssystemen: 1. Beschrijf kort, in eigen woorden, wat de functie “procesbeheer” van een besturingssysteem inhoudt. 2. Onder welke omstandigheid gaat een proces van de toestand “executeren” naar “geblokeerd”? Geef hiervan ook een voorbeeld. 3. Is het vertonen van een film een functie van een besturingssysteem of van een applicatieprogramma? Leg uit. Over netwerken: 1. Beschrijf kort, in eigen woorden, wat “protocol-layering” inhoudt. 2. Theorievragen over vertraging zoals opgaven 7.1 t/m 7.4. 3. We hebben gezien dat TCP sequencenummers gebruikt om (bytes in) pakketten te nummeren en te kunnen bevestigen. Waarom zijn die sequencenummers eigenlijk nodig; kunnen we niet volstaan met ongenummerde pakketten en bevestigingen? Leg dit uit door een voorbeeld te geven van hoe het fout zou kunnen gaan zonder sequencenummers. (NB: dit is een vraag waarop je het antwoord niet zomaar in het studiemateriaal vindt, maar zelf zou moeten kunnen beredeneren, na zoveel met Wireshark te hebben gewerkt.)
86
Week 7 – Parel 110: Besturingssystemen en Netwerken
