Bài giảng Hệ điều hành - Phan Xuân Huy
Chương 1: Tổng quan vềHĐH
Chương 2: Hệthống quảnlýtập tin
Chương 3: Hệthống quảnlýxuấtnhập
Chương 4: Quảnlýtiếntrình
Chương 5: Quảnlýbộnhớ
Tóm tắt nội dung Bài giảng Hệ điều hành - Phan Xuân Huy, để xem tài liệu hoàn chỉnh bạn click vào nút "TẢI VỀ" ở trên
paging work? Locality model Process migrates from one locality (working set) to another Why does thrashing occur? Σ size of working sets > total memory size 12/16/2007 Trần Hạnh Nhi 45 Nguyeân nhaân Thrashing Chæ coù theå kieåm soaùt thrashing do nguyeân nhaân 3. 1. Tieán trình khoâng taùi söû duïng boä nhôù (quaù khöù != töông lai) 2. Tieán trình taùi söû duïng boä nhôù, nhöng vôùi kích thöôc lôùn hôn 3. Quaù nhieàu tieán trình trong heä thoáng 12/16/2007 Trần Hạnh Nhi 46 Working set (1968, Denning) Working set: Working set = taäp hôïp caùc trang tieán trình ñang truy xuaát taïi 1 thôøi ñieåm Caùc pages ñöôïc truy xuaát trong Δ laàn cuoái cuøng seõ naèm trong working set cuûa tieán trình Δ : working set parameter Kích thöôùc cuûa WS thay ñoåi theo thôøi gian tuøy vaoø locality cuûa tieán trình 12/16/2007 Trần Hạnh Nhi 47 Working-Set Model Δ ≡ working-set window ≡ soá laàn truy caäp VD: 10,000 instruction 2 6 1 5 7 7 7 7 5 1 6 2 3 4 1 2 3 4 4 4 3 4 3 4 4 4 1 3 2 3 Δ=10 WS(t1) = {1,2,5,6,7}, WS(t2) = {3,4} WSSi (working set of Process Pi) = toång soá trang ñöôïc truy caäp trong Δ laàn gaàn ñaây nhaát D = ΣWSSi ≡ Toång caùc frame caàn cho N tieán trình trong heä thoáng if D > m⇒ Thrashing if D > m, choïn moä/moät soá tieán trình ñeå ñình chæ taïm thôøi. 12/16/2007 Trần Hạnh Nhi 48 Giaûi quyeát thrasing vôùi moâ hình Working set Söû duïng Working set Cache partitioning: Caáp cho moãi tieán trình soá frame ñuû chöùa WS cuûa noù Page replacement: öu tieân swap out caùc non-WS pages. Scheduling: chæ thi haønh tieán trình khi ñuû choã ñeå naïp WS cuûa noù 12/16/2007 Trần Hạnh Nhi 1 BAØI GIẢNG 8 : LIEÂN LAÏC GIÖÕA CAÙC TIEÁN TRÌNH CÔ CHEÁÁ ? VAÁÁN ÑEÀÀ ?TRAO ÑOÅÅI THOÂNG TIN GIÂ ÖÕA CAÕ ÙÙC TIEÁÁN TRÌNH GÆAI PHAÙÙP ? 12/16/2007 Trần Hạnh Nhi 2 Nhu Caàu Lieân Laïc Q LP Chia seû thoâng tin R Phoái hôïp xöû lyù P JOB R1 R2 L Q 12/16/2007 Trần Hạnh Nhi 3 Caùc cô cheá lieân laïc Chia seû taøi nguyeân chung Signal Pipe Shared Memory Trao ñoåi thoâng ñieäp Message Socket 12/16/2007 Trần Hạnh Nhi 4 IPC theo nguyeân taéc chia seû taøi nguyeân chung User Process User Process OS - Kernel shared resources Caùc tieán trình chia seû Memory File System Space Communication Facilities, Common communication protocol 12/16/2007 Trần Hạnh Nhi 5 Signal Signal Meaning Handler Ñònh nghóa tröôùc khi thöïc hieän lieân laïc SIGINT, SIGSTOP… SIGUSR1, SIGUSER2 Hoã trôï lieân laïc Kernel vôùi User Process Process Error Timer Child Process keát thuùc… User process vôí nhau Terminate Process Suspend, Resume… OS Process Signal handler Signal Action Signal Name Value Function SIGHUP 1 Terminal hangup SIGINT 2 Interrupt by user: generated by SIGQUIT 3 Quit by user: generated by SIGFPE 8 Floating point error such as divide by zero SIGKILL 9 Kill the process SIGUSR1 10 User defined signal 1 SIGSEGV 11 Segment violation: process has tried to access memory not assigned to it SIGUSR2 12 User defined signal 2 SIGALRM 14 Timer set with alarm() function has timed out SIGTERM 15 Termination request SIGCHLD 17 Child process termination signal SIGCONT 18 Continue after a SIGSTOP or SIGSTP signal SIGSTOP 19 Stop the process SIGTSTP 20 Terminal stop: generated by SIGWINCH 28 Change of window size 12/16/2007 Trần Hạnh Nhi 7 Nhaän xeùt Signals Lieân laïc khoâng ñoàng boä Khoâng bieát tröôùc thôøi ñieåm Thieáu tin caäy Khoâng cho pheùp trao ñoåi döõ lieäu Sig Result L Q SH L Q Quiz : OK ? A B 12/16/2007 Trần Hạnh Nhi 8 Pipes Pipe Kernel buffer (File) coù kích thöôùc giôùi haïn (4K, 8K…) HÑH cung caáp haøm WritePipe & ReadPipe WritePipe khi Pipe ñaày ? ReadPipe khi Pipe roãng ? Phaûiù xeùt ñeán caùc khaû naêng ñoàng boä Hoã trôï lieân laïc (UNIX original ) Giöõa 2 tieán trình Cha - Con Moät chieàu Khoâng caáu truùc (byte transfer) WritePipe() ReadPipe() LQ B……….AAB AB 12/16/2007 Trần Hạnh Nhi 9 Nhaän xeùt Pipe Öu ñieåm : Cho pheùp trao ñoåi döõ lieäu khoâng caáu truùc Khuyeát ñieåm Chi phí thöïc hieän cao (system call) Lieân laïc giöõa 2 tieán trình Lieân laïc moät chieàu Pipe trong caùc HÑH hieän ñaïi : Anomynous Pipe : This… Named Pipe : Unix , Windows NT… Truyeàn döõ lieäu coù caáu truùc Lieân laïc 2 chieàu 12/16/2007 Trần Hạnh Nhi 10 Shared Memory Shared Memory: Laø moät phaàn khoâng gian nhôù khoâng thuoäc sôû höõu cuûa tieán trình naøo Ñöôïc HÑH taïo ra Caùc tieán trình coù theå aùnh xaï ñòa chæ vaøo khoâng gian chia seû naøy ñeå truy xuaát döõ lieäu (nhö ñoái vôùi khoâng gian noäi boä) Khoâng giôùi haïn soá löôïng tieán trình, chieàu trao ñoåi, vaø thöù töï truy caäp Maâu thuaãn truy xuaát - > nhu caàu ñoàng boä 12/16/2007 Trần Hạnh Nhi 11 IPC theo nguyeân taéc trao ñoåi thoâng ñieäp User Process OS-Kernel User Process OS-Kernel Network Khoâng coù boä nhôù chung Caàn coù ñöôøng keát noái giöõa caùc maùy tính 12/16/2007 Trần Hạnh Nhi 12 Message Message Döõ lieäu coù caáu truùùc Caáu truùc vaø thoâng dòch msg ñöôïc thoûa thuaän giöõa 2 tieán trình lieân laïc HÑH cung caáp 2 primitive chính send(destination, message) receive(source, message) Caùc vaán ñeà quan taâm : Direct or indirect addressing Blocking or non-blocking communication Reliable or unreliable communication Buffered or un-buffered communication 12/16/2007 Trần Hạnh Nhi 13 Ñònh daïng Message 12/16/2007 Trần Hạnh Nhi 14 Nhaän xeùt message Laø cô cheá IPC toång quaùt Hoã trôï lieân laïc giöõa caùc tieán trính treân cuøng maùy Hoã trôï lieän laïc giöõa caùc tieán trính trong heä thoáng phaân taùn Lieân laïc giöõa caùc heä thoáng khoâng ñoàng nhaát ? 12/16/2007 Trần Hạnh Nhi 15 Máy A (UNIX) Máy B (Windows) Lieân laïc giöõa caùc heä thoáng khoâng ñoàng nhaát P1 P2 Send( ) //UNIX Receive( ) //WIN 12/16/2007 Trần Hạnh Nhi 16 Socket Endpoint cuûa moät keát noái 2 chieàu Töông ñöông vôùi moät network interface (hardware) Cho pheùp caùc öùng duïng “plug in” vaøo maïng moät caùch aån duï Laø moät giao dieän laäp trình maïng Cho pheùp caùc tieán trình lieân laïc 2 chieàu vôùi nhau Thieát laäp lieân laïc : taïo 2 socket, keát noái chuùng vôùi nhau Socket description Söû duïng moät transport protocol Caàn ñaëc taû IPaddress vaø port keát noái Ñöôïc hoã trôï ñaàu tieân trong Berkeley socket Laø söï môû roäng cuûa nhaäp xuaát file tröøu töôïng Hieän nay ñöôïc hoã trôï trong haàu heát HÑH hieän ñaïi 12/16/2007 Trần Hạnh Nhi 17 12/16/2007 Trần Hạnh Nhi 18 Socket Communication 12/16/2007 Trần Hạnh Nhi 19 Máy A (UNIX) Máy B (Windows) Lieân laïc giöõa caùc heä thoáng khoâng ñoàng nhaát P1 P2 Send( ) Receive( ) Socket Socket 12/16/2007 Trần Hạnh Nhi 20 Lieân laïc thoâng qua Socket Hoã trôï 2 phöông thöùc lieân laïc Connection-oriented (TCP/IP) Stream Reliable Bi-directional communication Connectionless (UDP/IP) Datagram Unreliable Bi-directional communication Cho pheùp lieân laïc giöõa caùc tieán trình treân caùc maïng khoâng ñoàng nhaát 12/16/2007 Trần Hạnh Nhi 21 Phöông thöùc Connection-Oriented Thöïc hieän treân TCP (Transmission Control Protocol.) Phaûi thöïc hieän keát noái giöõa 2 tieán trình tröôùc khi trao ñoåi döõ lieäu Töông töï heä thoáng ñieän thoaïi Döõ lieäu ñöôïc phaân phoái in sequence. guaranteed. Keát noái keát thuùc khi lieân laïc chaám döùt 2 modes: Iterative (synchronous) Concurrent (asynchronous) 12/16/2007 Trần Hạnh Nhi 22 Phöông thöùc Connectionless Thöïc hieän treân UDP (User Datagram Protocol) Khoâng yeâu caàu keát noái toàn taïi tröôùc khi truyeàn döõ lieäu Töông töï heä thoáng thö tín Döõ lieäu truyeàn coù theå bò maát maùt hay khoâng ñuùng traät töï 2 modes: Iterative (synchronous) Concurrent (asynchronous) 12/16/2007 Trần Hạnh Nhi 23 Caáu truùc ñòa chæ Socket Generic socket address structure: struct sockaddr { sa_family_t sa_family; /* address family */ char sa_data[14]; /* socket address */ }; A popular BSD-derived implementation: struct sockaddr_in { sa_family_t sin_family; /* address family */ in_port_t sin_port; /* protocol port number */ struct in_addr sin_addr; /* IP addr in NW byte order */ char sin_zero[8]; /* unused, set to zero */ }; 12/16/2007 Trần Hạnh Nhi 24 Port Numbers Port laø 1 khaùi nieäm tröøu töôïng ñöôïc TCP/UDP söû duïng ñeå phaân bieät caùc öùng duïng treân moät maùy chuû Moät port ñöôïc xaùc ñònh baèng 1 soá nguyeân 16 bit laø port number. 3 mieàn giaù trò ñöôc daønh cho Well-known ports (0-1023) Registered ports (1024-49151) Dynamic ports (49512 – 65535) 12/16/2007 Trần Hạnh Nhi 25 Some Well-Known Ports 12/16/2007 Trần Hạnh Nhi 26 Socket Types Socket types: SOCK_STREAM Stream socket (TCP) SOCK_DGRAM Datagram socket (UDP) SOCK_RAW Raw socket (talk to IP directly) 12/16/2007 Trần Hạnh Nhi 27 Socket Primitives Keát thuùc keát noáiClose Nhaän döõ lieäu qua keát noái ñaõ thieát laäpReceive Gôûi döõ lieäu qua keát noái ñaõ thieát laäpSend Chuû ñoäng thöïc hieän keát noáiConnect Khoaù caller ñeán khi coù 1 yeâu caàu keát noáiAccept Thoâng baùo saün saøng “laéng nghe” (tieáp nhaän keát noái)Listen Keát buoäc moät local address vôùi 1 socketBind Taïo 1 communication endpointSocket YÙ nghóaPrimitive 12/16/2007 Trần Hạnh Nhi 28 TCP System Calls bind() listen() socket() socket() accept() read() write() connect() write() read() blocks until connection from client process request Server Client close() close() 12/16/2007 Trần Hạnh Nhi 29 UDP System Calls socket() bind() recvfrom() sendto() socket() recvfrom() sendto() blocks until data received from a client process request data(request) data(reply) Server Client close()
File đính kèm:
- Bài giảng Hệ điều hành - Phan Xuân Huy.pdf