Bài giảng Hệ điều hành - Phan Xuân Huy

 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()