25 0 5MB
Hệ điều hành (Operating System) PHAN Xuân Huy {[email protected]}
1
Thông tin giới thiệu
Bố cục môn học: 45 LT + 30 TH Hình thức thi:
Lý thuyết: 7 điểm (Không sử dụng tài liệu) Thực hành: 3 điểm (Theo qui định của GVHDTH)
Các thắc mắc vui lòng liên hệ: Phan Xuân Huy – [email protected] Giáo trình môn học:
Hệ điều hành – Lê Khắc Nhiên Ân – ĐHKHTN Tp.HCM Hệ điều hành nâng cao - Trần Hạnh Nhi – ĐHKHTN Tp.HCM
2
Mục tiêu của môn học: Cung cấp
Các kiến thức cơ bản về HĐH đa nhiệm Hiểu rõ mô hình tổ chức, nguyên lý hoạt động, của các thành phần cơ sở của một HĐH hiện đại Biết cách sử dụng/quản trị các HĐH thông dụng, khai thác tốt các dịch vụ của HĐH.
3
Thảo luận – 1CPU vs nhiều Chương trình
Nhu cầu: Người dùng luôn thích sử dụng HĐH cho phép chạy vài chương trình đồng thời
Hệ điều hành như thế gọi là gì?
Thực tế: Hầu hết các máy tính chỉ có một bộ vi xử lý (các máy có >1 CPU rất đắt tiền)
Làm sao thỏa mãn được nhu cầu người dùng?
Một CPU rõ ràng chỉ có thể chạy được một chương trình Không thể chia CPU làm nhiều phần như chia bánh được
4
Thảo luận – Chia sẻ bộ nhớ
Các chương trình muốn có thể chạy thì trước hết cần phải được nạp vào trong bộ nhớ chính (RAM). Khi có nhiều chương trình cùng sử dụng bộ nhớ thì HĐH sẽ thực hiện việc chia sẻ cho mỗi chương trình không gian nhớ riêng. Vấn đề: bộ nhớ RAM thì có hạn (ví dụ 64MB), vậy khi chạy nhiều chương trình thì ra sao ??? Ví dụ:
Windows XP (lõi) Windows Media Player Visual Studio .NET
60MB 12MB 30MB
Làm cách nào mà Windows vẫn chạy được? 5
Thảo luận – Chia sẻ card sound
Khi đang nghe nhạc, nếu Windows gặp lỗi, ta có nghe được tiếng báo lỗi?
Vậy HĐH đã sử dụng giải pháp nào?
Chỉ có các hệ điều hành như ME, 2000, XP, … Luân phiên? Tuần tự? Chia bánh? Giải pháp khác?
☺Về nhà bạn thử làm cho Windows phát 2 bài nhạc khác nhau trên 2 loa xem? Có được không? 6
Nội dung môn học: gồm 5 chương
Chương 1: Tổng quan về HĐH Chương 2: Hệ thống quản lý tập tin Chương 3: Hệ thống quản lý xuất nhập Chương 4: Quản lý tiến trình Chương 5: Quản lý bộ nhớ
7
Chương 1: Tổng quan về HĐH
Nội dung chương:
Vai trò của Hệ điều hành Các thành phần của HĐH Một số kiến trúc HĐH Quá trình phát triển của HĐH Một số HĐH hiện đại
8
Vai trò của HĐH
Quản trị tài nguyên Tài nguyên: CPU, RAM, HDD, printer… Đối tượng sử dụng tài nguyên: Chương trình ƯD Nhiệm vụ: Cung cấp giải thuật cấp phát, quản trị tài nguyên cho các đối tượng hoạt động. Mục tiêu:Cấp phát đầy đủ, công bằng, hiệu quả
Điều khiển thiết bị
Nhiệm vụ: Che dấu các chi tiết phần cứng, tạo môi trường dễ làm việc hơn cho NSD. Mục tiêu: Tạo sự độc lập thiết bị. Ví dụ: Làm sao để MS.Word có thể in được với nhiều loại máy in khác nhau như in kim, laser, phun của nhiều hãng khác nhau 9
HĐH và các thành phần của hệ thống
10
HĐH và các thành phần của hệ thống
11
Các dịch vụ của hệ thống Nạp và thi hành chương trình (load & run) Các thao tác xuất nhập (I/O Operations) Các thao tác truy xuất/cập nhật hệ thống tập tin (file system) Các cơ chế liên lạc/trao đổi thông tin giữa các tác vụ Phát hiện/chỉnh sửa lỗi … Æ Giao tiếp giữa các chương trình ứng dụng và HĐH được thực hiện phần lớn thông qua các lời gọi hệ thống (System Call)
12
Các thành phần của HĐH
Quản lý tài nguyên là vai trò quan trọng nhất của HĐH, do đó cần có một số thành quản lý CPU, quản lý bộ nhớ, …
CPU : quản lý tiến trình(bao gồm quản lý CPU) RAM : quản lý bộ nhớ chính Input/Output : quản lý nhập/xuất (thấy rõ ở DOS) Hệ thống tập tin : Quản lý tập tin Hệ thống bảo vệ Quản lý mạng Shell (giao tiếp người dùng) 13
Các thành phần của HĐH
Quaûn lyù tieán trình Heä thoáng taäp tin
Quaûn lyù boä nhôù phuï Quaûn lyù nhaääp xuaát Quaûn lyù boä nhôù chính Heä thoáng baûo veä
Boä thoâng dòch leänh
Giao tieáp maïng
14
Kiến trúc HĐH
Kiến trúc đơn giản Kiến trúc phân lớp Kiến trúc máy ảo Kiến trúc client/server
15
1. Kiến trúc đơn giản Ứng dụng
Tiện ích thường trú
Hệ điều hành (DOS)
Phần cứng (BIOS, port)
Ví dụ với HĐH DOS
Ví dụ điển hình cho kiến trúc này là DOS, trong đó HĐH chỉ làm một số nhiệm vụ quản lý còn khá đơn giản và cung cấp thêm một số dịch vụ. HĐH = Thư viện hàm. UD của người dùng vẫn có thể truy cập trực tiếp đến phần cứng thông qua BIOS, cổng phần cứng Không hỗ trợ đa nhiệm. Đánh giá khi chương trình treo? 16
2. Kiến trúc phân lớp
Æ
Æ
HĐH phân thành nhiều lớp.Mỗi lớp phụ trách 1 chức năng đặc thù. Lớp bên trên sử dụng chức năng do các lớp bên dưới cung cấp. Khó xác định số lượng lớp, thứ tự lớp !!! Chi phí truyền tham số xuyên các lớp !!! 17
3. Kiến trúc máy ảo (1/4)
Có nghe đến máy ảo bao giờ? Ví dụ? Do mục tiêu của HĐH là chạy được nhiều chương trình đồng thời trên một máy tính nên cách tốt nhất là tạo ra nhiều máy tính ảo từ một máy tính thật để các chương trình chạy riêng trên các máy ảo. Về nguyên tắc các chương trình không biết mình đang chạy trên máy ảo, cũng không biết mình đang phải chia sẻ tài nguyên với các chương trình khác. Ví dụ:
CPU ảo: mỗi chương trình* sở hữu một CPU ảo Bộ nhớ ảo: mỗi chương trình một không gian nhớ riêng 18
3.Kiến trúc máy ảo (2/4)
Non-virtual Machine
Virtual Machine 19
3.Kiến trúc máy ảo (3/4)- Ví dụ
Java Virtual Machine Java program Java OS Java VM Process Operating System Hardware
•
Process
Độc lập với Platform 20
3. Kiến trúc máy ảo (4/4)
Ưu điểm:
Môi trường thuận lợi cho sự tương thích Tăng tính an toàn cho hệ thống do các VM độc lập Dễ phát triển các HĐH đơn nhiệm cho các VM độc lập.
Khuyết điểm
Phức tạp trong việc giả lập.
21
4. Kiến trúc client/server
Các dịch vụ của HĐH được chia thành 2 phần:
Server: phần hạt nhân, lệ thuộc phần cứng Client: các tiện ích hệ thống, sử dụng dịch vụ do server cung cấp
22
Giới thiệu các dòng HĐH hiện đại
Dòng HĐH Windows
Quá trình phát triển Các phiên bản chính
Dòng HĐH Unix/Linux
Quá trình phát triển Các distro chính
23
Dòng HĐH Windows
Phát triển bởi Microsoft. Hiện đang chiếm 80% Æ 90% thị trường HĐH. Số lượng dòng mã chương trình:
WinNT: 4 triệu Win2000: 35 triệu WinXP: 40 triệu
24
Quá trình phát triển của dòng HĐH Windows (1/4)
Windows 1.0 – Phát hành 12/1985 Windows 2.0
Phát hành 1987 Chỉ hổ trợ bộ vi xử lý Intel 8086 hoặc 8088 Có thể truy cập 1MB bộ nhớ
Windows 3.0
Phát hành 05/1990 Có thể truy cập 16MB bộ nhớ
25
Quá trình phát triển của dòng HĐH Windows (2/4)
Windows 3.1
Phát hành 04/1992 Hỗ trợ TrueType fonts/ Multimedia
Windows NT
Phát hành 07/1993 Hỗ trợ chíp Intel 386, 486 và các chíp khác không của Pentium Là hệ điều hành dòng server đầu tiên Là HĐH đầu tiên hỗ trợ các ỨD 32 bits 26
Quá trình phát triển của dòng HĐH Windows (2/4)
Windows 95
Windows 98
Phát hành 08/1995 Cũng hỗ trợ các ứng dụng 32-bit (nhưng vẫn tương thích với các ƯD 16 bits Phát hành 06/1998 Tăng cường về mặt hiệu năng và hỗ trợ phần cứng tốt hơn Tích hợp các tính năng Internet
Windows Millennium
Phát hành 12/2000 Là phiên bản destop hỗ trợ tốt multimedia. 27
Quá trình phát triển của dòng HĐH Windows (4/4)
Windows 2000
Phát hành 01/2000 Hỗ trợ tính đa xử lý đối xứng : 2-32 CPU. Hỗ trợ đầy đủ tính năng đa ngôn ngữ (UNICODE) Tính hợp đầy đủ các chồng giao thức mạng thông dụng Thuộc dòng HĐH server chuyên dụng. Các dòng sản phẩm: Windows 2000 Professional, Windows 2000 Server, Windows 2000 Advanced Server, Windows 2000 Datacenter Server
Windows 2003 Windows Longhorn
Hỗ trợ ƯD 64 bits
28
Quá trình phát triển của dòng HĐH Linux (1/2)
1969: UNIX, Thompson & Ritchie (AT&T Bell Lab) 1987: Minix, Andy Tanenbaum 1991: birth of Linux
1994: Linux 1.0
Minix-like OS by Linus Torvard limited devices, no networking only single-processor i386 networking (Internet) enhanced file system (ext2)
1995: Linux 1.2
more hardware 8086 mode (DOS emulation) included Support other architecture:Sparc, Alpha, MIPS 29
Quá trình phát triển của dòng HĐH Linux (2/2)
1996: Linux 2.0
1999: Linux 2.2 2001: Linux 2.4
multiple architectures, multiple processors threads, memory management …
ISA PnP, USB,…
12/2003: Linux 2.6
30
Các distro chính của HĐH Linux
Mandrake Fedora/Redhat Debian SUSE Gentoo …
31
Các đặc điểm chính của Linux
Là HĐH tương tự Unix. Là HĐH mã nguồn mở Bao gồm khoảng 6 triệu dòng mã (kernel v2.6) Tăng trưởng khoảng 25%/năm từ năm 2003 Chiếm khoảng 10% thị trường HĐH.
32
Chương 2: Quản lý xuất nhập
Nhiệm vụ của bộ phận quản lý xuất nhập Các thiết bị xuất nhập Mô hình phân lớp trong quản lý xuất nhập Bộ điều khiển thiết bị (device controller) Trình điều khiển thiết bị (device driver) Cơ chế DMA Quản lý lỗi và bảo vệ quá trình xuất nhập
1
Nhiệm vụ
Mục tiêu của bộ phận quản lý xuất nhập Giới thiệu lớp trừu tượng và độc lập thiết bị
Che giấu các chi tiết kỹ thuật của các thiết bị phần cứng. Quản lý và sửa lỗi.
Làm cho các thiết bị phần cứng đơn giản và dễ dùng. Cho phép chia sẻ các thiết bị phần cứng Xây dựng các cơ chế bảo vệ các thiết bị được chia sẻ. Điều phối thiết bị để phục vụ cho cùng lúc nhiều nhu cầu sử dụng.
2
Ví dụ về các thiết bị xuất nhập
Các thiết bị giao tiếp:
Các thiết bị chỉ nhập : bàn phím, chuột, joystick… Các thiết bị chỉ xuất : màn hình, máy in Các thiết bị vừa nhập vừa xuất: card mạng.
Các thiết bị lưu trữ Thiết bị vừa xuất, vừa nhập: đĩa (cứng/mềm), băng từ Thiết bị chỉ xuất: CD-ROM.
3
Phân loại các thiết bị nhập xuất
Phân loại theo mục đích sử dụng:
Các thiết bị giao tiếp:
Các thiết bị chỉ nhập : bàn phím, chuột, joystick… Các thiết bị chỉ xuất : màn hình, máy in Các thiết bị vừa nhập vừa xuất: card mạng.
Các thiết bị lưu trữ Thiết bị vừa xuất, vừa nhập: đĩa (cứng/mềm), băng từ Thiết bị chỉ xuất: CD-ROM
Phân loại theo phương pháp truy xuất:
Thiết bị khối:
Tổ chức theo từng khối riêng biệt và truy xuất ngẫu nhiên.
Thiết bị tuần tự
Gởi nhận theo chuỗi bít và phải truy xuất tuần tự.
4
Phân loại các thiết bị nhập xuất (tt)
HĐH phải gom nhóm các thiết bị khác nhau thành những nhóm cơ bản để dễ dàng quản lý:
Storage Hard drives, Tapes, CDROM Networking Ethernet, radio, serial line Multimedia DVD, Camera, microphones
HĐH phải cung cấp các phương thức nhất quán để truy cập các nhóm đối tượng trên. Nếu không, lập trình sẽ rất khó khăn 5
Các phương thức truy cập IO
Sử dụng chung thư viện giao tiếp cho nhiều thiết bị khác nhau Ví dụ , với HĐH Unix, sử dụng 4 phương thức chính:
open() close() read() write()
Các phương thức này là các system calls được cung cấp bởi HĐH để cho phép các ứng dụng chúng tương tác với các thiết bị xuất nhập. 6
Các phương thức IO của Unix
fileHandle = open(pathName, flags, mode)
filehandle: là một số nguyên, dùng để thao tác với tập tin hay thiết bị pathname: tên trong hệ thống file. Trong Unix, các thiết bị đặt dưới thư mục /dev. E.g. /dev/ttya là serial port đầu tiên, /dev/sda: là SCSI drive đầu tiên flags: blocking hoặc là non-blocking … mode: read only, read/write, append …
errorCode = close(fileHandle)
Kernel sẽ giải phóng các biến lưu trữ cho thiết bị 7
Các phương thức IO của Unix (tt)
byteCount = read(fileHandle, byte [] buf, count)
Đọc count bytes từ thiết bị và lưu trong buffer buf. Chương trình người dùng phải kiểm tra byteCount để biết số byte thật sự đọc được. byteCount < 0 thì là báo lỗi (xem mã lỗi)
byteCount = write(fileHandle, byte [] buf, count)
Ghi count byte từ buf vào thiết bị Số byte thật sự ghi được lưu trong byteCount byteCount âm là bị lỗi
8
Các đặc tính xuất nhập
Ba đặc tính khác nhau cần xem xét khi xử lý 1 thao tác nhập xuất:
blocking vs. non-blocking buffered vs. unbuffered synchronous vs. asynchronous
9
Blocking vs. Non-Blocking I/O
Blocking – ứng dụng dừng lại cho đến khi số count bytes được đọc hoặc ghi
Ví dụ: Trong thiết bị mạng, nếu muốn ghi 1000 bytes, thì HĐH ghi tất cả các byte cho đến khi ghi hoàn tất. Nếu thiết bị không thể thực hiện lệnh ghi được (ví dụ hỏng dây nối), làm sao? Thì sẽ kết thúc và trả về số bytes đã ghi được.
Nonblocking – HĐH đọc và ghi các bytes khi có thể, không cần ứng dụng phải dừng lại.
10
Buffered vs. Unbuffered I/O
Trong trường hợp buffer dữ liệu của thiết bị quá nhỏ, để không phải chờ quá lâu khi thực hiện IO
buffered I/O cho phép kernel copy lại dữ liệu Bên write(): cho phép ứng dụng tiếp tục ghi dữ liệu Bên read(): khi thiết bị báo có dự liệu đến, kernel chép dữ liệu vào buffer. Khi tiến trình gọi read(), kernel chỉ việc copy từ buffer.
Khuyết điểm buffered I/O?
Thêm chi phí để thực hiện copy Chậm trễ việc gửi dữ liệu
11
Synchronous vs. Asynchronous I/O
Synchronous I/O: các xử lý khác của ứng dụng của người dùng cuối sẽ dừng lại để chờ các thao tác xuất nhập của nó hoàn tất. Asynchronous I/O: các xử lý khác của ứng dụng có thể thực thi song song với các thao tác xuất nhập
12
Các loại thiết bị xuất nhập Hầu hết HĐH chia thành 3 nhóm thiết bị: Thiết bị đọc theo kí tự (character device)
Thiết bị mạng
Dùng cho các thiết bị tuần tự (v.d. USB port, bàn phím, modem) Dùng cho các card mạng (v.d. Ethernet card)
Thiết bị theo block:
Dùng cho các bộ lưu trữ lớn (v.d.ổ đĩa và CDROM) Phương thức read/write sẽ khác nhau với từng loại
13
Thiết bị xuất nhập theo kí tự
HĐH đọc và ghi theo chuỗi các byte
System call write() sẽ ghi từng byte ra thiết bị System call read() sẽ đọc từng byte ra thiết bị
Không có điều khiển tỉ lệ read/write, bên gửi có thể gọi system
call write() 1 lần 1000 bytes, bên nhận có thể gọi read 1000 lần, mỗi lần đọc 1 byte.
14
Thiết bị mạng
Unix và Windows đều dùng khái niệm socket để cho việc truyền, nhận dữ liệu trên mạng
Mỗi write() hoặc là gửi cả block, kích thước của block có giới hạn tùy hệ thống. Bên nhận, read() trả về tất cả các byte trong block.
15
Thiết bị đọc theo block
HĐH đọc và ghi thiết bị theo các block Mỗi block kích thước xác định (thông thường 1KB - 8KB) Người dùng chỉ có thể read/write các block cùng kích thước Không giống thiết bị khác, thiết bị đọc ghi theo block hỗ trợ random access Chúng ta có thể đọc/ghi bất cứ block nào trên thiết bị, không cần phải ‘đọc tất cả các bytes’ trước Làm sao xác định vị trí của block thứ n?
16
Con trỏ file
Một con trỏ file được gán vào một file đang mở, nếu như thiết bị đang mở thuộc loại đọc theo block Con trỏ file sẽ trỏ tới vị trí hiện hành trên file cho lệnh đọc/ghi kế tiếp Đơn vị của con trỏ file là byte, chứ không phải block Di chuyển con trỏ file: absoluteOffset = lseek(fileHandle, offset, whence); whence xác định vị trí cột mốc, đầu file, cuối file… Vị trí hiện hành được trả về, khoâng coù söï trao ñoåi thoâng tin hieån nhieân.. Excel winword
Visual C
CDplayer
OS 10/20/2007
Trần Hạnh Nhi
16
Ví duï moâ hình ña tieán trình Giôø thi lyù thuyeát moân Heä Ñieàu haønh Moãi sinh vieân laø moät tieán trình : Cuøng laøm baøi => Hoaït ñoäng ñoàng haønh Coù baøi thi , buùt, giaáy…rieâng => Taøi nguyeân rieâng bieät Ñoäc laäp => Khoâng trao ñoåi (veà nguyeân taéc)
Thöïc haønh moân Heä Ñieàu haønh 2 sinh vieân/nhoùm Hôïp taùc ñoàng haønh Nhu caàu trao ñoåi Duøng taøi nguyeân chung 10/20/2007
Trần Hạnh Nhi
17
Moâ hình ña tieåu trình (MultiThreads) Nhieàu tình huoáng caàn coù nhieàu doøng xöû lyù ñoàng thôøi cuøng hoaït ñoäng trong moät khoâng gian ñòa chæ => cuøng chia seû taøi nguyeân (server, OS, caùc chöông trình tính toaùn song song : nhaân ma traän…) alta vista
Khaùi nieäm môùi : tieåu trình (thread) 10/20/2007
Trần Hạnh Nhi
18
Ví duï Moâ hình ña tieåu trình Thöïc haønh moân Heä Ñieàu haønh Moãi nhoùm 2 sinh vieân laø moät tieán trình : Moãi sinh vieân laø moät tieåu trình Cuøng laøm baøi => Hoaït ñoäng ñoàng haønh Coùù baøi thöïc haønh chung => Taøi nguyeân chung Trao ñoåi vôùi nhau
10/20/2007
Trần Hạnh Nhi
19
Khaùc bieät giöõa Tieåu trình & Tieán trình Tieåu trình : 1 doøng xöû lyù Tieán trình :
P1
1 khoâng gian ñòa chæ 1 hoaëc nhieàu tieåu trình
T1
Caùc tieán trình laø ñoäc laäp Caùc tieåu trình trong cuøng 1 tieán trình khoâng coù söï baûo veä laãn nhau (caàn thieát ? ).
10/20/2007
Trần Hạnh Nhi
T2
T 3
int a;
20
Tieåu trình haït nhaân (Kernel thread) T1
T2
User mode
System call Kernel mode
Kernel Thread
Khaùi nieäm tieåu trình ñöôïc xaây döïng beân trong haït nhaân Ñôn vò xöû lyù laø tieåu trình Ví duï : Windows 95/98/NT/2000 Solaris, Tru64 UNIX, BeOS, 10/20/2007
Linux
Trần Hạnh Nhi
21
Phaân chia CPU ? 1 CPU vaät lyù : laøm theá naøo ñeå taïo aûo giaùc moãi tieán trình sôû höõu CPU rieâng cuûa mình ? Luaân chuyeån CPU giöõa caùc tieán trình 2 thaønh phaàn ñaûm nhieäm vai troø ñieàu phoái: Scheduler choïn 1 tieán trình Dispatcher chuyeån CPU cho tieán trình ñöôïc choïn
10/20/2007
Trần Hạnh Nhi
CPU
22
Caùc danh saùch tieán trình
Ready List Waiting Lists
P4
R1
P2
P7
R2
P3
P10
R3 10/20/2007
P1
P5
P6 Trần Hạnh Nhi
23
Scheduler - Nhieäm vuï Ra quyeát ñònh choïn moät tieán trình ñeå caáp phaùt CPU : ÖÙng cöû vieân = {Caùc tieán trình ready list} 0 tieán trình : CPU raûnh roãi (idle)! 1 tieán trình : khoâng caàn suy nghó nhieàu, ñuùng khoâng ? >1 : choïn ai baây giôø ? Döïa vaøo caùc thuaät toaùn ñieàu phoái
Ready List
10/20/2007
P1
Trần Hạnh Nhi
P4
P5
24
Dispatcher - Nhieäm vuï Nhieäm vuï cuûa Dispatcher: Chuyeån ñoåi ngöõ caûnh Xeùt ví duï Tieán trình A ñang duøng CPU 1 chuùt thì bò HÑH thu hoài CPU HÑH caáp CPU cho B duøng 1 chuùt, HÑH thu hoài laïi CPU. HÑH caáp CPU trôû laïi cho A. Giaù trò caùc thanh ghi giöõa nhöõng laàn chuyeån ñoåi CPU ?
Kòch baûn : Löu ngöõ caûnh tieán trình hieän haønh Naïp ngöõ caûnh tieán trình ñöôïc choïn keá tieáp
10/20/2007
Trần Hạnh Nhi
25
10/20/2007
Trần Hạnh Nhi
26
Dispatcher - Thaûo luaän Baûn thaân HÑH cuõng laø 1 phaàn meàm, nghóa laø cuõng söû duïng CPU ñeå coù theå chaïy ñöôïc. Caâu hoûi: Khi tieán trình A ñang chieám CPU, laøm theá naøo HÑH coù theå thu hoài CPU laïi ñöôïc ? (vì luùc naøy HÑH khoâng giöõ CPU) EÙp buoäc NSD thænh thoaûng traû CPU laïi cho HÑH ? Coù khaû thi ? Maùy tính phaûi coù 2 CPU, 1 daønh rieâng cho HÑH ? HÑH söû duïng ngaét ñoàng hoà (ngaét ñieàu phoái) ñeå kieåm soaùt heä thoáng Moãi khi coù ngaét ñoàng hoà, HÑH kieåm tra xem coù caàn thu hoài CPU töø 1 tieán trình naøo ñoù laïi hay khoâng ? HÑH chæ thu hoài CPU khi coù ngaét ñoàng hoà phaùt sinh. Khoaûng thôøi gian giöõa 2 laàn ngaét ñieàu phoái goïi laø chu kyø ñoàng hoà (toái thieåu laø 18.2 laàn / giaây) 10/20/2007
Trần Hạnh Nhi
27
Löïa choïn tieán trình ? Taùc vuï cuûa Scheduler Muïc tieâu ? Söû duïng CPU hieäu quaû Ñaûm baûo taát caû caùc tieán trình ñeàu tieán trieån xöû lyù
Tieâu chuaån löïa choïn ? Taát caû caùc tieán trình ñeàu nhö nhau ? Ñeà xuaát moät ñoä öu tieân cho moãi tieán trình ?
Thôøi ñieåm löïa choïn ? (Thôøi ñieåm kích hoaït Scheduler())
10/20/2007
Trần Hạnh Nhi
28
Muïc tieâu ñieàu phoái Hieäu quûa (Efficiency) ª Thôøi gian ª Ñaùùp öùng (Response time) ª Hoaøn taát (Turnaround Time = Tquit -Tarrive): ª Chôø (Waiting Time = T in Ready ) :
© Thoâng löôïng (Throughput = # jobs/s ) © Hieäu suaát Taøi nguyeân ª Chi phí chuyeån ñoåi
Coâng baèng ( Fairness) : Taát caû caùc tieán trình ñeàu coù cô hoäi nhaän CPU 10/20/2007
Trần Hạnh Nhi
29
Thôøi ñieåm ra quyeát ñònh ñieàu phoái Ñieàu phoái ñoäc quyeàn (non-preemptive scheduling): tieán trình ñöôïc choïn coù quyeàn ñoäc chieám CPU Caùc thôøi ñieåm kích hoaït Scheduler P cur keát thuùc P cur : running ->blocked
Ñieàu phoái khoâng ñoäc quyeàn (preemptive scheduling): tieán trình ñöôïc choïn coù theå bò cöôùp CPU bôûi tieán trình coù ñoä öu tieân cao hôn Caùc thôøi ñieåm kích hoaït Scheduler P cur keát thuùc P cur : Running -> Blocked Q : Blocked / New -> Ready
10/20/2007
Trần Hạnh Nhi
30
Hai nguyeân taéc ñieàu phoái CPU Ñoäc quyeàn while (true) { save state Pcur Scheduler.NextP() load state pnext resume Pnext wait for Pnext }
10/20/2007
Pnext
Khoâng ñoäc quyeàn while (true) { interrupt Pcur save state Pcur Scheduler.NextP() load state pnext resume Pnext } Trần Hạnh Nhi
Pnext
31
Ñaùnh giaù chieán löôïc ñieàu phoái Söû duïng 2 ñaïi löôïng ño : Turn- around time = Tquit –Tarrive: töø luùc vaøo HT ñeán khi hoaøn taát Waiting time = T in Ready
Xeùt tröôøng hôïp trung bình
N tieán trình Avg Turn- around time = (Σ Turn- around time Pi )/N Avg Waiting time = (Σ Waiting time Pi )/N
10/20/2007
Trần Hạnh Nhi
32
Caùc chieán löôïc ñieàu phoái FIFO (FCFS) Xoay vòng (Round Robin) Theo độ ưu tiên Công việc ngắn nhất (SJF) Nhiều mức độ ưu tiên
10/20/2007
Trần Hạnh Nhi
33
FCFS (First comes first served)
Ready List
C
B
A
CPU
B
CPU
C
CPU
Tieán trình vaøo RL laâu nhaát ñöôïc choïn tröôùc Theo thứ tự vaøo RL Độc quyền
Ready List
C Ready List
10/20/2007
Trần Hạnh Nhi
34
Minh hoïa FCFS P
TarriveRL
CPU burst
P
TT
WT
P1
0
24
P1
24
0
P2
1
3
P2
27-1
24-1
P3
2
3
P3
30-2
27-2
AvgWT = (23+25)/3 = 16 P1
P2
0
24
0:00 P1 P1 0:01 P2 0:02 P3
10/20/2007
vào RL dùng CPU vào RL vào RL
0:24 P1 P2 0:27 P2 P3
Trần Hạnh Nhi
kết thúc dùng CPU kết thúc dùng CPU
P3 27
35
Nhaän xeùt FCFS Ñôn giaûn Chòu ñöïng hieän töôïng tích luõy thôøi gian chôø Tieán trình coù thôøi gian xöû lyù ngaén ñôïi tieán trình coù thôøi gian xöû lyù daøi Öu tieân tieán trình cpu-bounded
Coù theå xaûy ra tình traïng ñoäc chieám CPU
10/20/2007
Trần Hạnh Nhi
36
Ñieàu phoái Round Robin (RR)
Quantum/ Time slice
Ñieàu phoái theo nguyeân taéc FCFS Moãi tieán trình chæ söû duïng moät löôïng q cho moãi laàn söû duïng CPU Ready List
C
B
A
CPU
B
CPU
B được giao quyền sử dụng CPU trong q ms kế tiếp
C
CPU
C được giao quyền sử dụng CPU trong q ms kế tiếp
A chỉ chiếm CPU trong q ms
Ready List
A
C
Ready List
B
A
10/20/2007
Trần Hạnh Nhi
37
Minh hoïa RR, q=4 P
TarriveRL
CPU burst
P
TT
WT
P1
0
24
P1
30
0+(10-4)
P2
1
3
P2
7-1
4-1
P3
2
3
P3
10-2
7-2
AvgWT = (6+3+5)/3 = 4.66 P1 0
P2 4
P3 7
P1 10
P1 14
P1 18
P1 22
P1 26
30
0:00 P1 vào, P1 dùng CPU
0:07 P2 dừng, P3 dùng CPU
0:01 P2 vào (đợi)
0:10 P3 dừng, P1 dùng CPU
0:02 P3 vào (đợi)
0:14 P1 vẫn chiếm CPU …
0:04 P1 hết lượt, P2 dùng CPU
10/20/2007
Trần Hạnh Nhi
38
Minh hoïa RR, q=4 P
TarriveRL
CPU burst
P1
0
24
P2
4
3
P3
12
3
P1 0
P1 4
RL 0:00 P1 0:04
?
10/20/2007
P2 8
Tranh chaáp vò trí trong RL : “Chung thuûy” 1. P : running -> ready 2. P : blocked -> ready 3. P: new ->ready Khoâng phaûi luoân luoân coù thöù töï ñieàu phoái P1 P2 P3 P4P1 P2 P3 P4...
P1 11
P3 15
P1 18
P1 22
P1 26
0:04 P1 P2
“Chung thuûy”
0:04 P2 P1
“Coù môùi nôùi cuõ”
Trần Hạnh Nhi
30
0:8 P2 P1 0:11 P1 0:15 P3 P1 0:18 P139
RR : Khi naøo keát thuùc 1 löôït söû duïng CPU Heát thôøi löôïng q ms (quantum) cho pheùp Tieán trình keát thuùc Tieán trình bò khoùa Chờ Rs Chờ biến cố
10/20/2007
Trần Hạnh Nhi
40
Nhaän xeùt RR Söû duïng cô cheá khoâng ñoäc quyeàn Moãi tieán trình khoâng phaûi ñôïi quaù laâu Loaïi boû hieän töôïng ñoäc chieám CPU Hieäu quaû ?
Phuï thuoäc vaøo vieäc choïn löïa quantum q q quaùù lớn ??? q quaù nhỏ ???
Bao laâu ? Giaûm tíùnh töông taùc
Taêng chi phí chuyeån ñoåi ngöõ caûnh Tröôøng hôïp xaáu nhaát cuûa RR ? 10/20/2007
Trần Hạnh Nhi
41
Ñieàu phoái vôùi ñoä öu tieân Phân biệt tiến trình quan trọng >< tiến trình bình thường?
WinAmp
WinWord
độ ưu tiên: cao (-3)
Độ ưu tiên
độ ưu tiên: trung bình (0)
Outlook
độ ưu tiên: thấp (3)
Tieán trình coù ñoä öu tieân cao nhaát ñöôïc choïn caáp CPU tröôùc 10/20/2007
Trần Hạnh Nhi
42
Ví duï: Ñoä öu tieân cuûa HÑH WinNT WinNT gaùn cho moãi tieán trình ñoä öu tieân coù giaù trò giöõa 0 & 31 0 (ñoä öu tieân nhoû nhaát): daønh rieâng cho traïng thaùi system idle
Ñoä öu tieân ñöôïc phaân theo nhoùm: Realtime : (16 - 31)
Thích hôïp cho caùc tieán trình thôøi gian thöïc Daønh rieâng cho caùc tieán trình cuûa ngöôøi quaûn trò heä thoáng
Dynamic : (0 - 15)
Thích hôïp cho caùc tieán trình cuûa ngöôøi duøng thöôøng
Chia thaønh 3 möùc : high (11 - 15) normal (6 - 10) idle (2 - 6) 10/20/2007
Trần Hạnh Nhi
43
Bieåu ñoà phaân boá ñoä öu tieân cuûa WinNT realtime time-critical
31
highest (+2) above normal (+1) normal (0) below normal (-1) lowest (-2)
realtime
realtime 24
levels 16-31
realtime idle dynamic time-critical
high
16 15 13
dynamic
normal idle
8
levels 1-15 4 dynamic idle system idle
10/20/2007
1 0
Trần Hạnh Nhi
44
Nguyeân taéc ñieàu phoái Độc quyền Lượt sử dụng CPU kết thuùc khi: tiến trình kết thuùc, tiến trình bị khoùa
Khoâng độc quyền Lượt sử dụng CPU kết thuùc khi: tiến trình kết thuùc, tiến trình bị khoùa, coùtiến trình vôùi độ ưu tieân cao hơn vaøo RL
10/20/2007
Trần Hạnh Nhi
45
Minh hoïa ñoä öu tieân (khoângñoäc quyeàn) P
TRL
Priority
CPU burst
P
TT
WT
P1
0
2
24
P1
30
0+(7-1)
P2
1
0
3
P2
4-1
0
P3
2
1
3
P3
7-2
4-2
AvgWT = (6+0+2)/3 = 2.66 P1 P2 0
1
P2
2
P3 4
P1 7
0:00 P1 vào, P1 dùng CPU 0:01 P2 vào (độ ưu tiên cao hơn P1) P2 dành quyền dùng CPU 0:02 P3 vào (độ ưu tiên thấp hơn P2) P3 không 10/20/2007
30 0:4 P2 kết thúc, P3 dùng CPU 0:7 P3 dừng, P1 dùng CPU 0:30 P1 dừng
dành được quyền Trần dùng CPU Hạnh Nhi
46
Nhaän xeùt Caùch tính ñoä öu tieân ? Heä thoáng gaùn : CPU times… starvation Ngöôøi duøng gaùn töôøng minh Tính chaát ñoä öu tieân : Tónh Ñoäng Soá phaän tieán trình coù ñoä öu tieân thaáp ? Aging : taêng ñoä öu tieân Chôø laâu, laâu, laâu ... cho nhöõng tieán trình chôø laâu trong heä thoáng 10/20/2007
Trần Hạnh Nhi
47
Shortest Job First (SJF) Ready List P2
(cần 3 chu kỳ)
Ng
ắn
P1
(cần 5 chu kỳ)
nhấ
t
CPU
P3
(cần 7 chu kỳ)
Là một dạng độ ưu tiên đặc biệt với độ ưu tiên
pi = thời_gian_còn_lại(Processi) Có thể cài đặt độc quyền hoặc không độc quyền 10/20/2007
Trần Hạnh Nhi
48
Minh hoïa SJF (ñoäc quyeàn)(1) P
TarriveRL
CPU burst
P
TT
WT
P1
0
24
P1
24
0
P2
1
3
P2
27
24-1
P3
2
3
P3
30
27-2
AvgWT = (23+25)/3 = 16 P1
P2
0
24
0:00 P1 vào, P1 dùng CPU
P3 27
30
0:01 P2 vào RL
0:24 P1 kết thúc, P2 dùng CPU 0:27 P2 dừng, P3 dùng CPU
0:02 P3 vào RL
0:30 P3 dừng
10/20/2007
Trần Hạnh Nhi
49
Minh hoïa SJF (ñoäc quyeàn)(2) P
TarriveRL
CPU burst
P
TT
WT
P1
0
24
P1
24
0
P2
1
3
P2
29
26-1
P3
1
2
P3
26
24-2
AvgWT = (24+22)/3 = 15.33 P1
P3
0
24
0:00 P1 vào, P1 dùng CPU
P2 26
29
0:01 P2 vào
0:24 P1 kết thúc, P3 dùng CPU 0:26 P3 dừng, P2 dùng CPU
0:01 P3 vào
0:29 P2 dừng
10/20/2007
Trần Hạnh Nhi
50
Minh hoïa SJF (khoângñoäc quyeàn) (1) P
TarriveRL
CPU burst
P
TT
WT
P1
0
24
P1
30
0+(7-1)
P2
1
3
P2
4-1
0
P3
2
3
P3
7-2
4-2
AvgWT = (6+0+2)/3 = 2.66 P1 0
P2
1
P3 4
P1 7
30
0:00 P1 vào, P1 dùng CPU 0:01 P2 vào (độ ưu tiên cao hơn P1) P2 dành quyền dùng CPU 10/20/2007
0:4 P2 kết thúc, P3 dùng CPU 0:7 P3 dừng, P1 dùng CPU 0:30 P1 dừng
Trần Hạnh Nhi
51
Minh hoïa SJF (khoângñoäc quyeàn) (2) P
TarriveRL
CPU burst
P
TT
WT
P1
0
24
P1
33
0+(10-1)
P2
1
5
P2
6
0
P3
3
4
P3
10
6-3
AvgWT = (9+0+3)/3 = 4 P1 P2 0
1
3
P2
P3 6
P1 10
33
0:00 P1 vào, P1 dùng CPU 0:01 P2 vào (độ ưu tiên cao hơn P1) P2 dành quyền dùng CPU 0:03 P3 vào (độ ưu tiên < P2) P2 dành 10/20/2007
quyền dùng CPU
0:6 P2 kết thúc, P3 dùng CPU 0:9 P3 dừng, P1 dùng CPU 0:33 P1 dừng
Trần Hạnh Nhi
52
Minh hoïa SJF (nhieàu chu kyø CPU) P
TarriveRL
CPU1 burst
IO1 R
IO1 T
CPU2 burst
IO2 R
IO2 T
P1
0
5
R1
2
2
R2
2
P2
2
1
R1
10
1
R1
4
P3
10
8
R2
1
0
Null
0
CPU
P1 P2 0
2
P1
3
P3 6
10
P2 13
P2
R1 3
P3 14
P1 15
P1 13
P3 17
21
P2 15
19
R2
P1 10/20/2007
Trần Hạnh Nhi
17
P3 19
21
53
22
Nhaän xeùt SJF Toái öu thôøi gian chôø Chöùng minh ?
Khoâng khaû thi Laøm sao bieát CPU burst ?
P1
P2
P3
a
b
c
AvgWT = (3a+2b+c) Min AvgWT ? a traïng thaùi ñoái phöông khoâng khoaù mình ñöôïc
Bounded Wait : interest[i] vaø turn ñeàu coù thay ñoåi giaù trò
Khoâng theå môû roäng cho N tieán trình
11/10/2007
Trần Hạnh Nhi
34
Nhaän xeùt chung veà caùc giaûi phaùp phaàn meàm trong nhoùm Busy-Waiting Khoâng caàn söï hoã trôï cuûa heä thoáng Deã...sai, Khoù môû roäng Giaûi phaùp 1 neáu coù theå ñöôïc hoã trôï atomicity thì seõ toát... Nhôø ñeán phaàn cöùng ?
11/10/2007
Trần Hạnh Nhi
35
Nhoùm Busy-Waiting - Caùc giaûi phaùp phaàn cöùng Caùc giaûi phaùp Busy Waiting Caùc giaûi phaùp phaàn meàm Giaûi phaùp bieán côø hieäu Giaûi phaùp kieåm tra luaân phieân Giaûi phaùp Peterson
Caùc giaûi phaùp phaàn cöùng Caám ngaét Test&Set lock Instruction
11/10/2007
Trần Hạnh Nhi
36
Nhoùm Busy-Waiting - Giaûi phaùp phaàn cöùng 1: Caám ngaét NonCS; Disable Interrupt;
CS; Enable Interrupt;
NonCS; Disable Interrupt : Caám moïi ngaét, keå caû ngaét ñoàng hoà Enable Interrupt : Cho pheùp ngaét 11/10/2007
Trần Hạnh Nhi
37
Giaûi phaùp phaàn cöùng 1: Caám ngaét Thieáu thaän troïng Neáu tieán trình bò khoaù trong CS ? System Halt
Cho pheùp tieán trình söû duïng moät leänh ñaëc quyeàn Quaù ...lieàu !
Maùy coù N CPUs ? Khoâng baûo ñaûm ñöôïc Mutual Exclusion
11/10/2007
Trần Hạnh Nhi
38
Nhoùm Busy-Waiting - Giaûi phaùp phaàn cöùng 2: chæ thò TSL() CPU hoã trôï primitive Test and Set Lock Traû veà giaù trò hieän haønh cuûa 1 bieán, vaø ñaët laïi giaù trò True cho bieán Thöïc hieän moät caùch khoâng theå phaân chia TSL (boolean &target) { TSL = target; target = TRUE; }
11/10/2007
Trần Hạnh Nhi
39
Aùp duïng TSL int lock = 0 Pi
NonCS;
while (TSL(lock)); // wait
CS; lock = 0;
NonCS; 11/10/2007
Trần Hạnh Nhi
40
Nhaän xeùt chung caùc giaûi phaùp phaàn cöùng trong nhoùm BusyWaiting Caàn ñöôïc söï hoã trôï cuûa cô cheá phaàn cöùng Khoâng deã, nhaát laø treân caùc maùy coù nhieàu boä xöû lyù
Deã môû roäng cho N tieán trình
11/10/2007
Trần Hạnh Nhi
41
Nhaän xeùt chung cho caùc giaûi phaùp trong nhoùm Busy Waiting Söû duïng CPU khoâng hieäu quaû Lieân tuïc kieåm tra ñieàu kieän khi chôø vaøo CS
Khaéc phuïc Khoaù caùc tieán trình chöa ñuû ñieàu kieän vaøo CS, nhöôøng CPU cho tieán trình khaùc Phaûi nhôø ñeán Scheduler Wait and See...
11/10/2007
Trần Hạnh Nhi
42
Caùc giaûi phaùp ñoàng boä hoaù Nhoùm giaûi phaùp Busy Waiting Phaàn meàm
Söû duïng caùc bieán côø hieäu Söû duïng vieäc kieåm tra luaân phieân Giaûi phaùp cuûa Peterson
Phaàn cöùng
Caám ngaét Chæ thò TSL
Nhoùm giaûi phaùp Sleep & Wakeup Semaphore Monitor Message 11/10/2007
Trần Hạnh Nhi
43
Caùc giaûi phaùp “Sleep & Wake up” if (chöa coù quyeàn) Sleep() ; CS;
Wakeup( somebody); Töø boû CPU khi chöa ñöôïc vaøo CS Khi CS troáng, seõ ñöôïc ñaùnh thöùc ñeå vaøo CS Caàn ñöôïc Heä ñieàu haønh hoã trôï Vì phaûi thay ñoåi traïng thaùi tieán trình
11/10/2007
Trần Hạnh Nhi
44
YÙ töôûng Heä Ñieàu haønh hoã trôï 2 primitive : Sleep() : Tieán trình goïi seõ nhaän traïng thaùi Blocked WakeUp(P): Tieán trình P nhaän traïng thaùi Ready
AÙp duïng Sau khi kieåm tra ñieàu kieän seõ vaøo CS hay goïi Sleep() tuøy vaøo keát quaû kieåm tra Tieán trình vöøa söû duïng xong CS seõ ñaùnh thöùc caùc tieán trình bò Blocked tröôùc ñoù
11/10/2007
Trần Hạnh Nhi
45
AÙp duïng Sleep() and Wakeup() int busy; int blocked; if (busy) { }
// busy ==0 : CS troáng // ñeám soá tieán trình bò Blocked chôø vaøo CS blocked = blocked + 1; Sleep();
else busy = 1;
CS; busy = 0;
if(blocked) { }
11/10/2007
WakeUp(P); blocked = blocked - 1; Trần Hạnh Nhi
46
Vaán ñeà vôùi Sleep & WakeUp P2
P1 if (busy) { blocked = blocked + 1; Sleep(); } else busy = 1;
CS; busy = 0; if(blocked) { WakeUp(P); blocked = blocked - 1; }
WakeUp bò “laïc”
P1 blocked vónh vieãn
if (busy) { blocked = blocked + 1; Sleep(); } else busy = 1;
CS; busy = 0; if(blocked) { WakeUp(P); blocked = blocked - 1; }
Nguyeân nhaân : Vieäc kieåm tra ñieàu kieän vaø ñoäng taùc töø boû CPU coù theå bò ngaét quaõng Baûn thaân caùc bieán côø hieäu khoâng ñöôïc baûo veä 11/10/2007 Trần Hạnh Nhi
47
Caøi ñaët caùc giaûi phaùp Sleep & WakeUp ? Heä ñieàu haønh caàn hoã trôï caùc cô cheá cao hôn Döïa treân Sleep&WakeUp Keát hôïp caùc yeáu toá kieåm tra Thi haønh khoâng theå phaân chia
Nhoùm giaûi phaùp Sleep & Wakeup Semaphore Monitor Message
11/10/2007
Trần Hạnh Nhi
48
Giaûi phaùp Sleep & Wakeup 1: Semaphore Ñöôïc ñeà nghò bôûi Dijkstra naêm 1965 Caùc ñaëc tính : Semaphore s; Semaphore s; // s >=0 Coù 1 giaù trò Chæ ñöôïc thao taùc bôûi 2 primitives : Down(s) Up(s)
Caùc primitive Down vaø Up ñöôïc thöïc hieän khoâng theå phaân chia
11/10/2007
Trần Hạnh Nhi
49
Caøi ñaët Semaphore (Sleep & Wakeup) typedef struct { int value; struct process* L; } Semaphore ;
Giaù trò beân trong cuûa semaphore
Danh saùch caùc tieán trình ñang bò block ñôïi semaphore nhaän giaù trò döông
Semaphore ñöôïc xem nhö laø moät resource
Caùc tieán trình “yeâu caàu” semaphore : goïi Down(s)
Neáu khoâng hoaøn taát ñöôïc Down(s) : chöa ñöôïc caáp resource Blocked, ñöôïc ñöa vaøo s.L
Caàn coù söï hoã trôï cuûa HÑH Sleep() & Wakeup()
11/10/2007
Trần Hạnh Nhi
50
Caøi ñaët Semaphore (Sleep & Wakeup)
Down (S) { S.value --; if S.value < 0 { Add(P,S.L); Sleep(); } }
11/10/2007
Up(S) { S.value ++; if S.value ≤ 0 { Remove(P,S.L); Wakeup(P); } }
Trần Hạnh Nhi
51
Söû duïng Semaphore Toå chöùc “ñoäc quyeàn truy xuaát”
Pi
Semaphore s = ?1
Down (s) CS; Up(s)
Toå chöùc “hoø heïn”
Semaphore s = ?0
11/10/2007
P1 : Job1; Up(s) Trần Hạnh Nhi
P2: Down (s); Job2; 52
Nhaän xeùt Semaphores Laø moät cô cheá toát ñeå thöïc hieän ñoàng boä Deã duøng cho N tieán trình
Nhöng yù nghóa söû duïng khoâng roõ raøng MutualExclusion : Down & Up Rendez-vous : Down & Up Chæ phaân bieät qua moâ hình
Khoù söû duïng ñuùng Nhaàm laãn
11/10/2007
Trần Hạnh Nhi
53
Giaûi phaùp Sleep & Wakeup 2: Monitor Ñeà xuaát bôûi Hoare(1974) & Brinch (1975) Laø cô cheá ñoàng boä hoaù do NNLT cung caáp Hoã trôï cuøng caùc chöùc naêng nhö Semaphore Deã söû duïng vaø kieåm soaùt hôn Semaphore Baûo ñaûm Mutual Exclusion moät caùch töï ñoäng Söû duïng bieán ñieàu kieän ñeå thöïc hieän Synchronization
11/10/2007
Trần Hạnh Nhi
54
Monitor : Ngöõ nghóa vaø tính chaát(1) Monitor M Share variable: i,j;
Laø moät module chöông trình ñònh nghóa Caùc CTDL, ñoái töôïng duøng chung Caùc phöông thöùc xöû lyù caùc ñoái töôïng naøy Baûo ñaûm tính encapsulation
MethodA MethodB i=0MethodC prinf(j) i=5
11/10/2007
Caùc tieán trình muoán truy xuaát döõ lieäu beân trong monitor phaûi duøng caùc phöông thöùc cuûa monitor : P1 : M.C() // i=5 P2: M.B() // printf(j)
Trần Hạnh Nhi
55
Monitor : Ngöõ nghóa vaø tính chaát(2) Entry queue Share variable: i,j;
P6
P7
P8
Töï ñoäng baûo ñaûm Mutual Exclusion Taïi 1 thôøi ñieåm chæ coù 1 tieán trình ñöôïc thöïc hieän caùc phöông thöùc cuûa Monitor Caùc tieán trình khoâng theå vaøo Monitor seõ ñöôïc ñöa vaøo Entry queue cuûa Monitor
Ví duï
MethodA MethodB i=0 MethodC printf(i) i=5
P1 : M.A(); P6 : M.B(); P7 : M.A(); P8 : M.C();
P1 11/10/2007
Trần Hạnh Nhi
56
Monitor : Ngöõ nghóa vaø tính chaát(3) Entry queue Share variable: i,j; Condition variable: C1: P2
P4
C2: P3
P5
P1
MethodA MethodB i=0; MethodC signal(c1) P1 wait(C1); i=5 signal(C2 ); 11/10/2007
P6
P7
P8
Hoã trôï Synchronization vôùi caùc condition variables Wait(c) : Tieán trình goïi haøm seõ bò blocked Signal(c): Giaûi phoùng 1 tieán trình ñang bò blocked treân bieán ñieàu kieän c C.queue : danh saùch caùc tieán trình blocked treân c
Traïng thaùi tieán trình sau khi goïi Signal? Blocked. Nhöôøng quyeàn vaøo monitor cho tieán trình ñöôïc ñaùnh thöùc Tieáp tuïc xöû lyù heát chu kyø, roài blocked Trần Hạnh Nhi
57
Söû duïng Monitor Toå chöùc “ñoäc quyeàn truy xuaát” Monitor M RC; Function AccessMutual CS; // access RC
Pi
M.AccessMutual(); //CS
Toå chöùc “hoø heïn” Monitor M Condition c; Function F1 Job1; Signal(c); Function F2 Wait(c); Job2;
11/10/2007
P1 : M.F1(); Trần Hạnh Nhi
P2: M.F2(); 58
Giaûi phaùp Sleep & Wakeup 3: Message Ñöôïc hoã trôï bôûi HÑH Ñoàng boä hoùa treân moâi tröôøng phaân taùn 2 primitive Send & Receive Caøi ñaët theo mode blocking 1. Send Request
Server
3. Send Finish
P
2. Receive Accept 11/10/2007
Trần Hạnh Nhi
59
Noäi dung baøi giaûng Xöû lyù ñoàng haønh vaø caùc vaán ñeà:
Vaán ñeà tranh ñoaït ñieàu khieån (Race Condition) Vaán ñeà phoái hôïp xöû lyù
Baøi toaùn ñoàng boä hoùa
Yeâu caàu ñoäc quyeàn truy xuaát (Mutual Exclusion) Yeâu caàu phoái hôïp xöû lyù (Synchronization)
Caùc giaûi phaùp ñoàng boä hoaù Busy waiting Sleep & Wakeup
Caùc baøi toaùn ñoàng boä hoaù kinh ñieån Producer – Consumer Readers – Writers Dinning Philosophers
11/10/2007
Trần Hạnh Nhi
60
Baøi toaùn ñoàng boä kinh ñieån 1: Producer - Consumer (Bounded-Buffer Problem) Moâ taû : 2 tieán trình P vaø C hoaït ñoäng ñoàng haønh P saûn xuaát haøng vaø ñaët vaøo Buffer C laáy haøng töø Buffer ñi tieâu thuï Buffer coù kích thöôùc giôùi haïn
Tình huoáng
P
P vaø C ñoàng thôøi truy caäp Buffer ? P theâm haøng vaøo Buffer ñaày ? C laáy haøng töø Buffer troáng ?
Buffer Buffer (N) (N)
C
P khoâng ñöôïc ghi döõ lieäu vaøo buffer ñaõ ñaày (Rendez-vous) C khoâng ñöôïc ñoïc döõ lieäu töø buffer ñang troáng (Rendez-vous) P vaø C khoâng ñöôïc thao taùc treân buffer cuøng luùc (Mutual Exclusion) 11/10/2007
Trần Hạnh Nhi
61
Producer – Consummer : Giaûi phaùp Semaphore Caùc bieán duøng chung giöõa P vaø C BufferSize = N; // soá choã trong boä ñeäm semaphore mutex = 1 ; // kieåm soaùt truy xuaát ñoäc quyeàn semaphore empty = BufferSize; // soá choã troáng semaphore full = 0; // soá choã ñaày int Buffer[BufferSize]; // boä ñeäm duøng chung
11/10/2007
Trần Hạnh Nhi
62
Producer – Consummer : Giaûi phaùp Semaphore Producer() {
Consumer() {
int item;
int item;
while (TRUE)
while (TRUE)
{
{ produce_item(&item);
down(&full);
down(&empty);
down(&mutex);
down(&mutex)
remove_item(&item,Buffer);
enter_item(item,Buffer);
up(&mutex);
up(&mutex);
up(&empty);
up(&full);
consume_item(item);
} }
11/10/2007
} }
Trần Hạnh Nhi
63
P&C - Giaûi phaùp Semaphore: Thinking... Producer() {
Consumer() {
int item;
int item;
while (TRUE)
while (TRUE)
{
{ produce_item(&item);
down(&mutex);
down(&mutex)
down(&full);
down(&empty);
remove_item(&item,Buffer);
enter_item(item,Buffer);
up(&mutex);
up(&mutex);
up(&empty);
up(&full);
consume_item(item);
} }
11/10/2007
} }
Trần Hạnh Nhi
64
Producer – Consummer : Giaûi phaùp Monitor monitor ProducerConsumer
procedure remove();
condition full, empty;
{
int Buffer[N], count;
if (count == 0)
procedure enter();
wait(empty)
{
remove_item(&item,Buffer); if (count == N)
count --;
wait(full);
if (count == N-1)
enter_item(item,Buffer);
signal(full);
count ++;
}
if (count == 1)
count = 0;
signal(empty);
end monitor;
} 11/10/2007
Trần Hạnh Nhi
65
Producer – Consummer : Giaûi phaùp Monitor Producer()
Consumer();
{
{
int item;
int item;
while (TRUE)
while (TRUE)
{
{ produce_item(&item);
ProducerConsumer.remove;
ProducerConsumer.enter; } }
11/10/2007
consume_item(item); } }
Trần Hạnh Nhi
66
Producer – Consummer : Giaûi phaùp Message Producer()
Consumer();
{
{
int item; message m;
int item;
Coi chöøng Deadlock
message m; for(0 to N) send(producer, Request);
while (TRUE)
while (TRUE)
{
{ produce_item(&item);
receive(producer, &m);
receive(consumer, Request);
remove_item(&m,&item);
create_message(&m, item);
send(producer, Request);
send(consumer,&m);
consumer_item(item);
} } 11/10/2007
} }
Trần Hạnh Nhi
67
Baøi toaùn ñoàng boä hoaù kinh ñieån 2: Readers & Writers R2
Moâ taû : N tieán trình Ws vaø Rs hoaït ñoäng ñoàng haønh Rs vaø Ws chia seû CSDL W caäp nhaät noäi dung CSDL Rs truy caäp noäi dung CSDL
R3
R1 W1
Tình huoáng Caùc Rs cuøng truy caäp CSDL ? W ñang caäp nhaät CSDL thì caùc Rs truy caäp CSDL ? Caùc Rs ñang truy caäp CSDL thì W muoán caäp nhaät CSDL ?
W2
Database
W khoâng ñöôïc caäp nhaät döõ lieäu khi coù ít nhaát moät R ñang truy xuaát CSDL (ME) Rs khoâng ñöôïc truy caäp CSDL khi moät W ñang caäp nhaät noäi dung CSDL (ME) Taïi moät thôøi ñieåm , chæ cho pheùp moät W ñöôïc söûa ñoåi noäi dung CSDL (ME)
11/10/2007
Trần Hạnh Nhi
68
Readers-Writers vôùi “active readers”
11/10/2007
Trần Hạnh Nhi
69
Readers-writers vôùi moät “active writer”
11/10/2007
Trần Hạnh Nhi
70
Öu tieân ai hôn ñaây ?
11/10/2007
Trần Hạnh Nhi
71
Readers & Writers W ñoäc quyeàn truy xuaát CSDL W hieän taïi keát thuùc caäp nhaät CSDL : ai vaøo ? Cho W khaùc vaøo, caùc Rs phaûi ñôïi Öu tieân Writer, Reader coù theå starvation
Cho caùc Rs vaøo, Ws khaùc phaûi ñôïi Öu tieân Reader, Writer coù theå starvation
11/10/2007
Trần Hạnh Nhi
72
Readers & Writers : Giaûi phaùp Semaphore Caùc bieán duøng chung giöõa Rs vaø Ws semaphore db = 1; // Kieåm tra truy xuaát CSDL
11/10/2007
Trần Hạnh Nhi
73
R&W : Giaûi phaùp Semaphore (1) Reader() {
Writer() {
down(&db);
down(&db);
read-db(Database);
write-db(Database);
up(&db);
up(&db);
}
}
Chuyeän gì xaûy ra ? Chæ coù 1 Reader ñöôïc ñoïc CSDL taïi 1 thôøi ñieåm !
11/10/2007
Trần Hạnh Nhi
74
R&W : Giaûi phaùp Semaphore (2) Reader() {
Writer() {
rc = rc +1;
down(&db);
if (rc ==1)
write-db(Database);
down(&db); read-db(Database); rc = rc – 1; if (rc == 0) up(&db); }
11/10/2007
up(&db); }
Ñuùng chöa ? rc laø bieán duøng chung giöõa caùc Reader... CS ñoù Trần Hạnh Nhi
75
Readers & Writers : Giaûi phaùp Semaphore Caùc bieán duøng chung giöõa Rs vaø Ws semaphore db = 1; // Kieåm tra truy xuaát CSDL Caùc bieán duøng chung giöõa Rs int rc; // Soá löôïng tieán trình Reader semaphore mutex = 1; // Kieåm tra truy xuaát rc
11/10/2007
Trần Hạnh Nhi
76
R&W : Giaûi phaùp Semaphore (3) Reader() {
Writer() {
down(&mutex);
down(&db);
rc = rc +1;
write-db(Database);
if (rc ==1)
up(&db);
down(&db);
}
up(mutex); read-db(Database);
Ai ñöôïc öu tieân ?
down(mutex); rc = rc – 1; if (rc == 0) up(&db); up(mutex); }
11/10/2007
Trần Hạnh Nhi
77
R&W : Giaûi phaùp Semaphore (Thinking...) Reader() {
Writer() {
down(&mutex);
down(&db);
rc = rc +1;
write-db(Database);
up(mutex);
up(&db);
if (rc ==1)
}
down(&db); read-db(Database);
??? heâ, heâ, heâ ☺
down(mutex); rc = rc – 1; up(mutex); if (rc == 0) up(&db); }
11/10/2007
Trần Hạnh Nhi
78
R&W: Giaûi phaùp Monitor monitor ReaderWriter
procedure W1();
Database;
{
procedure R1();
}
? { }
procedure R...();
procedure W...(); { }
{ } 11/10/2007
Trần Hạnh Nhi
79
monitor ReaderWriter condition OKWrite, OKRead; int rc = 0; Boolean busy = false; procedure BeginRead() { if (busy) wait(OKRead); rc++; signal(OKRead); } procedure FinishRead() { rc--; if (rc == 0) signal(OKWrite); }
procedure BeginWrite() { if (busy || rc != 0) wait(OKWrite); busy = true; } procedure FinishWrite() { busy = false; if (OKRead.Queue) signal(OKRead); else signal(OKWrite); } end monitor;
Reader&Writer : Giaûi phaùp Monitor Reader()
Writer();
{
{ RW.BeginRead();
RW.BeginWrite();
Read-db(Database);
Write-db(Database);
RW.FinishRead();
RW.FinishWrite();
}
11/10/2007
}
Trần Hạnh Nhi
81
Baøi toaùn ñoàng boä hoaù kinh ñieån 3: Böûa aên cuûa caùc Trieát gia (Dining Philosophers) Naêm trieát gia ngoài chung quanh baøn aên moùn spaghetti (yum..yum)
Treân baøn coù 5 caùi nóa ñöôïc ñaët giöõa 5 caùi ñóa (xem hình) Ñeå aên moùn spaghetti moãi ngöôøi caàn coù 2 caùi nóa
Trieát gia thöù i: Thinking... Eating...
Chuyeän gì coù theå xaûy ra ? 11/10/2007
Trần Hạnh Nhi
82
Dining Philosophers : Tình huoáng nguy hieåm 2 trieát gia “giaønh giaät” cuøng 1 caùi nóa Tranh chaáp
Caàn ñoàng boä hoaù hoaït ñoäng cuûa caùc trieát gia
11/10/2007
Trần Hạnh Nhi
83
Dining Philosophers : Giaûi phaùp ñoàng boä semaphore fork[5] = 1; Philosopher (i) { while(true) { down(fork[i]); down(fork[i+1 mod 5]) eat; up(fork[i]); up(fork[i+1 mod 5]); think; } 11/10/2007
Deadlock Trần Hạnh Nhi
84
Dining Philosophers : Thaùch thöùc Caàn ñoàng boä sao cho: Khoâng coù deadlock Khoâng coù starvation
11/10/2007
Trần Hạnh Nhi
85
Baøi giaûng 6 :
Quaûn lyù boä nhôù
Toång quan
Nhu caàu boä nhôù cuûa tieán trình Caùc vaán ñeà veà boä nhôù
Chuyeån ñoåi ñòa chæ
Caùc coâng ñoaïn Caùc moâ hình chuyeån ñoåi ñòa chæ
Vai troø Quaûn lyù boä nhôù cuûa HÑH Caùc yeâu caàu
Caùc moâ hình toå chöùc boä nhôù Moâ hình Lieân tuïc Moâ hình Khoâng lieân tuïc
4/6/2008
Trần Hạnh Nhi
1
Toång quan : Nhu caàu veà boä nhôù cuûa tieán trình Chöông trình caàn ñöôïc naïp vaøo Boä nhôù chính ñeå thi haønh CPU chæ coù theå truy xuaát tröïc tieáp Main Memory Chöông trình khi ñöôïc naïp vaoø BNC seõ ñöôïc toå chöùc theo caáu truùc cuûa tieán trình töông öùng Ai caáp phaùt BNC cho tieán trình ?
Chöông trình nguoàn söû duïng ñòa chæ symbolic Tieán trình thöïc thi truy caäp ñiaï chæ thöïc trong BNC Ai chuyeån ñoåi ñòa chæ ?
HÑH Boä phaän Quaûn lyù Boä nhôù Moâ hình toå chöùc ? 4/6/2008
Cô cheá hoã trôï Trần Hạnh Nhi
Chieán löôïc thöïc hieän 2
Toång quan : Caùc vaán ñeà veà Boä nhôù Caáp phaùt Boä nhôù : Uniprogramming : Khoâng khoù Multiprogramming : BNC giôùi haïn, N tieán trình ? Baûo veä ? Chia seû ?
Tieán trình thay ñoåi kích thöôùc ? Tieán trình lôùn hôn BNC ? Chuyeån ñoåi ñòa chæ tieán trình Thôøi ñieåm chuyeån ñoåi ñòa chæ ? Coâng thöùc chuyeån ñoåi ?
Phuï thuoäc vaøo Moâ hình toå chöùc BNC ? Caàn söï hoã trôï cuûa phaàn cöùng ?
Tieán trình thay ñoåi vò trí trong BNC ? 4/6/2008
Trần Hạnh Nhi
3
Ví duï OS
Moâi tröôøng ña nhieäm
gcc nachos emacs
0x9000 0x7000 0x4000 0x3000 0x0000
Neáu nachos caàn theâm khoâng gian ? Neáu nachos coù loãi vaø thöïc hieän thao taùc ghi vaøo ñòa chæ 0x7100? Khi naøo gcc bieát raèng noù thöôøng truù taïi 0x4000? Neáu emacs caàn nhieàu boä nhôù hôn dung löôïng vaät lyù hieän coù? 4/6/2008
Trần Hạnh Nhi
4
Caùc böôùc chuyeån ñoåi chöông trình C program: test.c Compiler Object:test.o Linker
lib.o
Executable: test.exe Loader Memory 4/6/2008
Trần Hạnh Nhi
5
Caùc böôùc chuyeån ñoåi source program -> .exe
A.C int x; int y; x = 12; y = 5; F();
A.O 0 // x 2 // y 4 // [0] = 12; 5 // [2] = 5; 6 // jmp F //external // object
B.C
F() { printf(“Hi”); }
B.O 0 -2 // F() …
0 3 5 7 8 9
// F() // x // y // [3] = 12; // [5] = 5; // jmp 0
Test.exe
OS
? // F() ? // x ? // y ? // [?] = 12; ? // [?] = 5; ? // jmp ?
Thuaät ngöõ Ñòa chæ logic – coøn goïi laø ñòa chæ aûo , laø taát caû caùc ñòa chæ do boä xöû lyù taïo ra Ñòa chæ physic - laø ñòa chæ thöïc teá maø trình quaûn lyù boä nhôù nhìn thaáy vaø thao taùc Khoâng gian ñòa chæ – laø taäp hôïp taát caû caùc ñòa chæ aûo phaùt sinh bôûi moät chöông trình Khoâng gian vaät lyù – laø taäp hôïp taát caû caùc ñòa chæ vaät lyù töông öùng vôùi caùc ñòa chæ aûo
4/6/2008
Trần Hạnh Nhi
8
Nhu caàu boä nhôù cuûa tieán trình low address
code segment
read from program file by exec usually read-only can be shared
data segment
system data segment (PCB) … 8048314 : 8048314:
push
%ebp
8048315:
mov
%esp,%ebp
8048317:
mov
0xc(%ebp),%eax
804831a:
add
0x8(%ebp),%eax
804831d:
pop
%ebp
804831e:
ret
initialized global variables (0 / NULL) 804831f : 804831f: push uninitialized global variables 8048320: mov heap dynamic memory 8048325: e.g., allocated using malloc grows against higher addresses 8048328: 8048322:
stack segment
initialized variables uninitialized variables data segment process A
%ebp %esp,%ebp
sub
$0x18,%esp
and
$0xfffffff0,%esp
mov
$0x0,%eax
804832d:
sub
%eax,%esp
804832f:
movl
$0x0,0xfffffffc(%ebp)
8048336:
movl
$0x2,0x4(%esp,1)
variables in a function 804833e: 8048345: stored register states (e.g. calling function EIP) 804834a: 804834d: grows against lower addresses 804834e:
804834f: system data segment (PCB)
segment pointers pid program and stack pointers …
code segment
movl
$0x4,(%esp,1)
call
8048314
mov
%eax,0xfffffffc(%ebp)
heap
s nu “u
leave ret nop
” ed
m
em
y or
...
… …
Stack cho các thread 4/6/2008
data segment
Tiến trình gồm có:
stack possible stacks for more threads
Trần Hạnh Nhi
high address
9
Logical and Physical Address Spaces
4/6/2008
Trần Hạnh Nhi
10
Truy xuaát boä nhôù Ñòa chæ cuûa Instruction vaø data trong program source code laø symbolic: goto errjmp; X = A + B;
Nhöõng ñòa chæ symbolic naøy caàn ñöôïc lieân keát (bound) vôùi caùc ñòa chæ thöïc trong boä nhôù vaät lyù tröôùc khi thi haønh code Address binding: aùnh xaï ñòa chæ töø khoâng gian ñòa chæ (KGÑC) naøy vaøo KGÑC khaùc Thôøi ñieåm thöïc hieän address binding ? compile time load time execution time.
4/6/2008
Trần Hạnh Nhi
11
Thôøi ñieåm keát buoäc ñòa chæ ? Coù theå thöïc hieän vieäc keát buoäc ñòa chæ taïi 1 trong 3 thôøi ñieåm : Compile-time:
Phaùt sinh ñòa chæ tuyeät ñoái Phaûi bieát tröôùc vò trí naïp chöông trình Phaûi bieân dòch laïi chöông trình khi vò trí naïp thay ñoåi
Load-time:
Khi bieân dòch chæ phaùt sinh ñòa chæ töông ñoái Khi naïp, bieát vò trí baét ñaàu seõ tính laïi ñòa chæ tuyeät ñoái Phaûi taùi naïp khi vò trí baét ñaàu thay ñoåi
Execution-time:
Khi bieân dòch,naïp chæ phaùt sinh ñòa chæ tuong ñoái Trì hoaõn thôøi ñieåm keât buoäc ñòa chæ tuyeät ñoái ñeán khi thi haønh Khi ñoù ai tính toaùn ñòa chæ tuyeät ñoái ? Phaàn cöùng : MMU
4/6/2008
Trần Hạnh Nhi
12
Chuyeån ñoåi ñòa chæ
MMU
gcc Load Store CPU
Translation box virtual address
data
4/6/2008
legal addr? Illegal?
Physical address
Physical memory
error
Trần Hạnh Nhi
13
CPU, MMU and Memory
4/6/2008
Trần Hạnh Nhi
14
Yeâu caàu quaûn lyù boä nhôù Taêng hieäu suaát söû duïng CPU Caàn hoã trôï Multiprogramming Löu tröõ cuøng luùc nhieàu tieán trình trong BNC ?
Caùc yeâu caàu khi toå chöùc löu tröõ tieán trình: 1. 2. 3. 4. 5.
4/6/2008
Relocation Protection Sharing Logical Organization Physical Organization
Trần Hạnh Nhi
15
Taùi ñònh vò (Relocation) Khoâng bieát tröôùc chöông trình seõ ñöôïc naïp vaøo BN ôû vò trí naøo ñeå xöû lyù. Moät tieán trình coù theå ñöôïc di dôøi trong boä nhôù sau khi ñaõ naïp C Tieán trình taêng tröôûng ? HÑH saép xeáp laïi caùc tieán trình ñeå coù theå söû duïng BNC hieäu quûa hôn.
4/6/2008
Trần Hạnh Nhi
16
Baûo veä (Protection) Khoâng cho pheùp tieán trình truy caäp ñeán caùc vò trí nhôù ñaõ caáp cho tieán trình khaùc (khi chöa coù pheùp). Khoâng theå thöïc hieän vieäc kieåm tra hôïp leä taïi thôøi ñieåm bieân dòch hay naïp, vì chöông trình coù theå ñöôïc taùi ñònh vò. Thöïc hieän kieåm tra taïi thôøi ñieåm thi haønh Caàn söï hoã trôï cuûa phaàn cöùng.
4/6/2008
Trần Hạnh Nhi
17
Chia seû (Sharing) Caàn cho pheùp nhieàu tieán trình tham chieáu ñeán cuøng moät vuøng nhôù maø khoâng toån haïi ñeán tính an toaøn heä thoáng : Tieát kieäm choå löu tröõ cho caùc module duøng chung. Cho pheùp caùc tieán trình coäng taùc coù khaû naêng chia seû döõ lieäu.
4/6/2008
Trần Hạnh Nhi
18
Toå chöùc logic (Logical Organization) Ngöôøi duøng vieát chöông trình goàm nhieàu module, vôùi caùc yeâu caàu baûo veä cho töøng module coù theå khaùc nhau: instruction modules : execute-only. data modules : read-only hay read/write. moät soá module laø private, soá khaùc coù theå laø public.
OS caàn hoã trôï caùc cô cheá coù theå phaûn aùnh moâ hình logic cuûa chuông trình
4/6/2008
Trần Hạnh Nhi
19
Toå chöùc vaät lyù (Physical Organization) Caáp phaùt vuøng nhôù vaät lyù sao cho hieäu quaû Vaø deã daøng chuyeån ñoåi chöông trình qua laïi giöõa BNC vaø BNP
4/6/2008
Trần Hạnh Nhi
20
Caùc moâ hình toå chöùc boä nhôù Caáp phaùt Lieân tuïc (Contigous Allocation) Linker – Loader Base & Bound
Caáp phaùt Khoâng lieân tuïc (Non Contigous Allocation) Segmentation Paging
4/6/2008
Trần Hạnh Nhi
21
Caáp phaùt Lieân tuïc (Contigous Allocation) Nguyeân taéc : Chöông trình ñöôïc naïp toaøn theå vaøo BNC ñeå thi haønh Caàn moät vuøng nhôù lieân tuïc, ñuû lôùn ñeå chöùa Chöông trình
Khoâng gian ñòa chæ : lieân tuïc Khoâng gian vaät lyù : coù theå toå chöùc Fixed partition Variable partition
2 moâ hình ñôn giaûn Linker – Loader Base & Bound 4/6/2008
Trần Hạnh Nhi
22
Fixed Partitioning Phaân chia KGVL thaønh caùc partitions Coù 2 caùch phaân chia partitions : kích thöôùc baèng nhau kích thöôùc khaùc nhau
Moãi tieán trình seõ ñöôïc naïp vaøo moät partition ñeå thi haønh Chieán löôïc caáp phaùt partition ?
4/6/2008
Trần Hạnh Nhi
23
Chieán löôïc caáp phaùt partitions cho tieán trình Kích thöôùc partition baèng nhau khoâng coù gì phaûi suy nghó !
Kích thöôùc partition khoâng baèng nhau : Söû duïng nhieàu haøng ñôïi Caáp cho tieán trình partition vôùi kích thöôùc beù nhaát (ñuû lôùn ñeå chöùa tieân trình) Khuyeát ñieåm : phaân boá caùc tieán trình vaøo caùc partition khoâng ñeàu, moät soá tieán trình phaûi ñôïi trong khi coù partition khaùc troáng 4/6/2008
Trần Hạnh Nhi
24
Chieán löôïc caáp phaùt partitions cho tieán trình Kích thöôùc partition khoâng baèng nhau :
Söû duïng 1 haøng ñôïi Caáp cho tieán trình partition töï do vôùi kích thöôùc beù nhaát (ñuû lôùn ñeå chöùa tieân trình) Caàn duøng moät CTDL ñeå theo doõi caùc partition töï do
4/6/2008
Trần Hạnh Nhi
25
Nhaän xeùt Fixed Partitioning Söû duïng BN khoâng hieäu quaû
internal fragmentation : kích thöôùc chöông trình khoâng ñuùng baèng kích thöôùc partition
Möùc ñoä ña chöông cuûa heä thoáng (Soá tieán trình ñöôïc naïp) bò giôùi haïn bôûi soá partitions P1 (2M) internal frag
P2 (4M)
3M
8M
internal frag 4/6/2008
Trần Hạnh Nhi
26
Dynamic Partitioning BNC khoâng ñöôïc phaân chia tröôùc
Caùc partition coù kích thöôùc tuøy yù, seõ hình thaønh trong quaù trình naïp caùc tieán trình vaøo heä thoáng
P1 (2M) P2 (4M)
Moãi tieán trình seõ ñöôïc caáp phaùt ñuùng theo kích thöôùc yeâu caàu khoâng coøn internal fragmentation
4/6/2008
Trần Hạnh Nhi
27
Dynamic Partitioning: tình huoáng P1 (2M) P2 (4M)
external fragmentation
P4 (1.5M) P3 (8M) 2M Choïn löïa partition ñeå caáp phaùt cho tieán trình ?
Ñoàng thôøi coù nhieàu partition töï do ñuû lôùn ñeå chöùa tieán trình Dynamic Allocation problem
Tieán trình vaøo sau khoâng laáp ñaày choã troáng tieán trình tröôùc ñeå laïi external fragmentation
Ví duï Dynamic Partitioning
4/6/2008
Trần Hạnh Nhi
29
Ví duï Dynamic Partitioning
4/6/2008
Trần Hạnh Nhi
30
Giaûi quyeát vaán ñeà Dynamic Allocation Caùc chieán löôïc thoâng duïng ñeå choïn partition:
First-fit: choïn partition töï do ñaàu tieân Best-fit: choïn partition töï do nhoû nhaát ñuû chöùa tieán trình Worst-fit: choïn partition töï do lôùn nhaát ñuû chöùa tieán trình
2M
First Fit
P1 P3 (1M) 8M
Worst Fit
P2 1.5M 4/6/2008
Trần Hạnh Nhi
Best Fit 31
Memory Compaction (Garbage Collection) Giaûi quyeát vaán ñeà External Fragmentation :
Doàn caùc vuøng bò phaân maûnh laïi vôùi nhau ñeå taïo thaønh partition lieân tuïc ñuû lôùn ñeå söû duïng Chi phí thöïc hieän cao
2M P1
External fragmentations
1M P2 1.5M 4/6/2008
Trần Hạnh Nhi
32
Caùc moâ hình chuyeån ñoåi ñòa chæ Fixed/Dynamic partition laø moâ hình toå chöùc naïp tieán trình vaøo KGVL Caàn coù moâ hình ñeå chuyeån ñoåi ñòa chæ töø KGÑC vaøo KGVL Linker Loader Base & Bound
4/6/2008
Trần Hạnh Nhi
33
Moâ hình Linker-Loader test.exe
OS 0x4000
test.exe jump 0x5000
jump 0x2000
0x0000
0x7000 0x3000 (base)
Taïi thôøi ñieåm Link, giöõ laïi caùc ñòa chæ logic Vò trí base cuûa tieán trình trong boä nhôù xaùc ñònh ñöôïc vaøo thôøi ñieåm naïp : ñòa chæ physic = ñòa chæ logic + base 4/6/2008
Trần Hạnh Nhi
34
Nhaän xeùt moâ hình Linker-Loader Khoâng caàn söï hoã trôï phaàn cöùng ñeå chuyeån ñoåi ñòa chæ Loader thöïc hieän
Baûo veä ? Khoâng hoã trôï
Dôøi chuyeån sau khi naïp ? Khoâng hoã trôï taùi ñònh vò Phaûi naïp laïi !
4/6/2008
Trần Hạnh Nhi
35
Moâ hình Base & Bound OS
Test.exe 0x4000
Test.exe jump 0x2000
jump 0x2000
0x0000
Bound 0x7000 Base 0x3000
Taïi thôøi ñieåm Link, giöõ laïi caùc ñòa chæ logic Vò trí base , bound ñöôïc ghi nhaän vaøo 2 thanh ghi: Keát buoäc ñòa chæ vaøo thôøi ñieåm thi haønh => taùi ñònh vò ñöôïc : ñòa chæ physic = ñòa chæ logic + base register Baûo veä : ñòa chæ hôïp leä ⊆ [base, bound] 4/6/2008
Trần Hạnh Nhi
36
Nhaän xeùt moâ hình Base & Bound Keát buoäc ñòa chæ taïi thôøi ñieåm thi haønh => caàn hoã trôï cuûa phaàn cöùng physical addrs
logical addrs CPU
MMU + base reg
memory
Hoã trôï Baûo veä Taùi ñònh vò
4/6/2008
Trần Hạnh Nhi
37
Khuyeát ñieåm cuûa caáp phaùt lieân tuïc Khoâng coù vuøng nhôù lieân tuïc ñuû lôùn ñeå naïp tieán trình ? Boù tay ... Söû duïng BNC khoâng hieäu qua”! 1M P1 P3 (9M) 8M P2 1M 4/6/2008
Trần Hạnh Nhi
38
Caùc moâ hình toå chöùc boä nhôù Caáp phaùt Lieân tuïc (Contigous Allocation) Linker – Loader Base & Bound
Caáp phaùt Khoâng lieân tuïc (Non Contigous Allocation) Segmentation Paging
4/6/2008
Trần Hạnh Nhi
39
Caùc moâ hình caáp phaùt khoâng lieân tuïc Cho pheùp naïp tieán trình vaøo BNC ôû nhieàu vuøng nhôù khoâng lieân tuïc Khoâng gian ñòa chæ : phaân chia thaønh nhieàu partition Segmentation Paging
Khoâng gian vaät lyù : coù theå toå chöùc Fixed partition : Paging Variable partition : Segmentation
4/6/2008
Trần Hạnh Nhi
40
Segmentation Laäp trình vieân : chöông trình laø moät taäp caùc segments Moät segment laø moät ñôn vò chöông trình goàm caùc ñoái töôïng coù cuøng nhoùm ngöõ nghóa Ví duï : main program, procedure, function, local variables, global variables,common block,stack, symbol table, arrays... Caùc segment coù theå coù kích thöôùc khaùc nhau
Moâ hình Segmentation : KGÑC : phaân chia thaønh caùc segment KGVL : toå chöùc thaønh dynamic partitions Naïp tieán trình : Moãi segment caàn ñöôïc naïp vaøo moät partition lieân tuïc, töï do, ñuû lôùn cho segment partition naøo ? ...Dynamic Allocation !
4/6/2008
Caùc segment cuûa cuøng 1 chöông trình coù theå ñöôïc naïp vaøo nhöõng partition khoâng lieân tuïc Trần Hạnh Nhi
41
Moâ hình Segmentation int m;
heap
main () { F1(m); } F1(int x) { x = 9; }
stack data (m) code (main,F1)
Quaûn lyù KGDC ñòa chæ ? 4/6/2008
KGVL Trần Hạnh Nhi
42
Toå chöùc Segmentation Ñiaï chæ logic :
Ñòa chæ physic : Chuyeån ñoåi ñòa chæ :
Chuyeån ñoåi ñòa chæ vaøo thôøi ñieåm thi haønh
MMU thi haønh Söû duïng Segment Table (baûng phaân ñoaïn) ñeå löu thoâng tin caáp phaùt BNC, laøm cô sôû thöïc hieän aùnh xaï ñòa chæ Moãi tieán trình coù moät Segment Table
Sâegment Table:
Soá phaàn töû cuûa Segment Table = Soá Segment cuûa chöông trình Moãi phaàn töû cuûa Segment Table moâ taû cho 1 segment, vaø coù caáu truùc : base: ñòa chæ vaät lyù trong BNC cuûa partition chöùa segment limit : kích thöôùc segment
Löu tröõ Segment Table ?
Cache : neáu ñuû nhoû BNC : Segment-table base register (STBR), Segment-table length register (STLR)
4/6/2008
Trần Hạnh Nhi
43
Chuyeån ñoåi ñòa chæ trong moâ hình Segmentation
Logical Addr 3
no ?
128
Seg# offset
fault yes
Seg table base
limit
+
mem 0x1000
seg
128
0 1 2
3
4/6/2008
0x1000 512
Trần Hạnh Nhi
44
Logical-to-Physical Address Translation in segmentation
4/6/2008
Trần Hạnh Nhi
45
Nhaän xeùt Moâ hình Segmentation Caáp phaùt khoâng lieân tuïc => taän duïng boä nhôù hieäu quaû Hoã trôï taùi ñònh vò Töøng Segment
Hoã trôï Baûo veä vaø Chia seû ñöôïc ôû möùc module YÙ nghóa cuûa “möùc module” ?
Chuyeån ñoåi ñòa chæ phöùc taïp ☺ Ñaõ coù MMU...
Söû duïng dynamic partition : chòu ñöïng Dynamic Allocation : choïn vuøng nhôù ñeå caáp cho moät segment ☺ First fit, Best fit, Worst fit
External Fragmentation : Memory Compaction : chi phí cao 4/6/2008
Trần Hạnh Nhi
46
Sharing of Segments: Text Editor
4/6/2008
Trần Hạnh Nhi
47
Paging Hoã trôï HÑH khaéc phuïc baøi toaùn caáp phaùt boä nhôù ñoäng, vaø loaïi boû external fragmentation Moâ hình Paging : KGÑC : phaân chia chöông trình thaønh caùc page coù kích thöôùc baèng nhau Khoâng quan taâm ñeán ngöõ nghóa cuûa caùc ñoái töôïng naèm trong page
KGVL : toå chöùc thaønh caùc fixed partitions coù kích thöôùc baèng nhau goïi laø frame page size = frame size Naïp tieán trình : Moãi page caàn ñöôïc naïp vaøo moät frame töï do Caùc pages cuûa cuøng 1 chöông trình coù theå ñöôïc naïp vaøo nhöõng frames khoâng keá caän nhau. Tieán trình kích thöôùc N pages -> caàn N frame töï do ñeå naïp
4/6/2008
Trần Hạnh Nhi
48
Moâ hình Paging int m;
int m;
main ()
main ()
{
F1(int x) F1(m);
}
stack
F1(int x) { x = 9;
heap
}
KGDC Quaûn lyù ñòa chæ ? 4/6/2008
KGVL Trần Hạnh Nhi
49
Toå chöùc Paging Ñiaï chæ logic :
Ñòa chæ physic : Chuyeån ñoåi ñòa chæ :
Chuyeån ñoåi ñòa chæ vaøo thôøi ñieåm thi haønh
MMU thi haønh Söû duïng Page Table ñeå löu thoâng tin caáp phaùt BNC, laøm cô sôû thöïc hieän aùnh xaï ñòa chæ Moãi tieán trình coù moät Page Table
Page Table
Soá phaàn töû cuûa Page Table = Soá Page trong KGÑC cuûa chöông trình Moãi phaàn töû cuûa baûng Page Table moâ taû cho 1 page, vaø coù caáu truùc : frame: soá hieäu frame trong BNC chöùa page
Löu tröõ Page Table ?
Cache : khoâng ñuû BNC : Page-table base register (PTBR), Page-table length register (PTLR)
4/6/2008
Trần Hạnh Nhi
50
Chuyeån ñoåi ñòa chæ trong moâ hình Paging Logical addr CPU
p
Physical addr
d
f
d
KGVL f
Page table 4/6/2008
Trần Hạnh Nhi
51
Logical-to-Physical Address Translation in Paging
4/6/2008
Trần Hạnh Nhi
52
Nhaän xeùt Moâ hình Paging Loaïi boû Dynamic Allocation External Fragmentation
“Trong suoát” vôùi LTV Hoã trôï Baûo veä vaø Chia seû ôû möùc page Internal Fragmentation Löu tröõ Page Table trong boä nhôù Toán choã Taêng thôøi gian chuyeån ñoåi ñòa chæ
4/6/2008
Trần Hạnh Nhi
53
Löu tröõ Page Table Giaû söû heä thoáng söû duïng m bit ñòa chæ Size of KGÑC = 2m
Kích thöôùc page Treân nguyeân taéc tuøy yù, thöïc teá choïn pagesize = 2n Taïi sao ?
Soá trang trong KGÑC: #pages = 2m / 2n = 2m-n Ví duï : 32-bits ñòa chæ, pagesize = 4K KGÑC = 232 -> #pages= 232-212 = 220 = 1.000.000 pages ! #pages = #entry trong PT
Ñiaï chæ logic : Page Table
4/6/2008
p
(m-n)
d
n
Moãi tieán trình löu 1 Page Table Soá löôïng phaàn töû quaù lôùn -> Löu BNC Moãi truy xuaát ñòa chæ seõ toán 2 laàn truy xuaát BNC Trần Hạnh Nhi
54
Löu tröõ Page Table : Tieát kieäm khoâng gian Söû duïng baûng trang ña caáp Chia baûng trang thaønh caùc phaàn nhoû, baûn thaân baûng trang cuõng seõ ñöôïc phaân trang Chæ löu thöôøng tröïc baûng trang caáp 1, sau ñoù khi caàn seõ naïp baûng trang caáp nhoû hôn thích hôïp... Coù theå loaïi boû nhöõng baûng trang chöùa thoâng tin veà mieàn ñòa chæ khoâng söû duïng Söû duïng Baûng trang nghòch ñaûo Moâ taû KGVL thay vì moâ taû KGÑC -> 1 IPT cho toaøn boä heä thoáng
4/6/2008
Trần Hạnh Nhi
55
Baûng trang ña caáp
p
d
0 1
Baûng trang tuyeán tính Söû duïng page-number laøm chæ muïc ñeán Page Table Phaûi löu taát caû caùc phaàn töû moâ taû taát caû caùc trang trong KGÑC Nhöõng page khoâng söû duïng : laõng phí Naïp toaøn boä PT vaøo BNC : toán choã
5 16
2 3 ... p
f
... 7 8
2
9 10 11 12 13 14 15
4/6/2008
Trần Hạnh Nhi
9 56
Baûng trang ña caáp
0
0 1 2 3
Page Table caáp 2
4 5 0 1
6 7
2
8
3
9
Page Table caáp 1
Page Table caáp 2
10 11
Page Table caáp 2
12 13 14 15
Page Table caáp 2
1 0 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 12 13 13 14 14 15 15
Moâ hình baûng trang 2 caáp
4/6/2008
Trần Hạnh Nhi
58
Ví duï moâ hình baûng trang 2 caáp Moät maùy tính söû duïng ñòa chæ 32bít vôùi kích thöôùc trang 4Kb. Ñòa chæ logic ñöôïc chia thaønh 2 phaàn: Soá hieäu trang : 20 bits. Offset tính töø ñaàu moãi trang :12 bits.
Vì baûng trang laïi ñöôïc phaân trang neân soá hieäu trang laïi ñöôïc chia laøm 2 phaàn: Soá hieäu trang caáp 1. Soá hieäu trang caáp 2.
4/6/2008
Trần Hạnh Nhi
59
Ví duï moâ hình baûng trang 2 caáp Vì theá, ñòa chæ logic seõ coù daïng nhö sau: page number page offset
4/6/2008
pi
p2
d
10
10
12
Trần Hạnh Nhi
60
Baûng trang ña caáp 1
2
100
0
0 1
1
2
2
3
Page Table caáp 2
0
5
1 0 1
2 3
2
0
3
1
Page Table caáp 1
6
Page Table caáp 2
7 8 9 10
2 3
3 4
Page Table caáp 2
11 12 13
0
14
1
15
2 3
Page Table caáp 2
16 17
Baûng trang nghòch ñaûo (Inverted Page Table) Söû duïng duy nhaát moät baûng trang nghòch ñaûo cho taát caû caùc tieán trình Moãi phaàn töû trong baûng trang nghòch ñaûo moâ taû moät frame, coù caáu truùc : soá hieäu page maø frame ñang chöùa ñöïng : id cuûa tieán trình ñang ñöôïc sôõ höõu trang
Moãi ñòa chæ aûo khi ñoù laø moät boä ba Khi moät tham khaûo ñeán boä nhôù ñöôïc phaùt sinh, moät phaàn ñòa chæ aûo laø ñöôïc ñöa ñeán cho trình quaûn lyù boä nhôù ñeå tìm phaàn töû töông öùng trong baûng trang nghòch ñaûo, neáu tìm thaáy, ñòa chæ vaät lyù seõ ñöôïc phaùt sinh
4/6/2008
Trần Hạnh Nhi
62
Kieán truùc baûng trang nghòch ñaûo
4/6/2008
Trần Hạnh Nhi
63
Löu tröõ Page table : Tieát kieäm thôøi gian Moãi truy caäp BNC caàn truy xuaát BNC 2 laàn : Tra cöùu Page Table ñeå chuyeån ñoåi ñòa chæ Tra cöu baûn thaân data
Laøm gì ñeå caûi thieän : Tìm caùch löu PT trong cache Cho pheùp tìm kieám nhanh
PT lôùn, cache nhoû : laøm sao löu ñuû ? Löu 1 phaàn PT... Phaàn naøo ? Caùc soá hieäu trang môùi truy caäp gaàn ñaây nhaát...
4/6/2008
Trần Hạnh Nhi
64
Translation Lookaside Buffer (TLB) Vuøng nhôù Cache trong CPU ñöôïc söû duïng ñeå löu taïm thôøi moät phaàn cuûa PT ñöôïc goïi laø Translation Lookaside Buffer (TLB) Cho pheùp tìm kieám toác ñoä cao Kích thöôùc giôùi haïn (thöôøng khoâng quaù 64 phaàn töû)
Moãi entry trong TLB chöùa moät soá hieäu page vaø frame töông öùng ñang chöùa page Khi chuyeån ñoåi ñòa chæ, truy xuaát TLB tröôùc, neáu khoâng tìm thaáy soá hieäu page caàn thieát, môùi truy xuaát vaøo PT ñeå laáy thoâng tin frame. 4/6/2008
Trần Hạnh Nhi
65
Translation Lookaside Buffer
4/6/2008
Trần Hạnh Nhi
66
Chuyeån ñoåi ñòa chæ vôùi Paging virtual address CPU
p
d
f physical address f
d d
TLB p
f Memory
f f 4/6/2008
PT
Trần Hạnh Nhi
67
Söû duïng TBL
4/6/2008
Trần Hạnh Nhi
68
Baûo veä vaø chia seû trong Segmentation vaø Paging Baûo veä Segmentation : moãi phaàn töû trong ST ñöôïc gaén theâm caùc bit baûo veä Moãi segment coù theå ñöôïc baûo veä tuøy theo ngöõ nghóa cuûa caùc ñoái töôïng beân trong segment
Paging : moãi phaàn töû trong PT ñöôïc gaén theâm caùc bit baûo veä Moãi page khoâng nhaän thöùc ñöôïc ngöõ nghóa cuûa caùc ñoái töôïng beân trong page, neân baûo veä chæ aùp duïng cho toaøn boä trang, khoâng phaân bieät.
Chia seû: Cho nhieàu phaàn töï trong KGÑC cuøng troû ñeán 1 vò trí trong KGVL Segmentation : chia seû möùc module chöông trình Paging : chia seû caùc trang 4/6/2008
Trần Hạnh Nhi
69
Sharing Pages: A Text Editor
Sharing Pages: A Text Editor
ed 3 + data 1
ed 3 + data 2
ed 3 + data 3
Chia seû Page 2 = Chia seû caû code vaø data !
Ñaùnh giaù caùc moâ hình chuyeån ñoåi ñòa chæ Giaû söû coù: tm : thôøi gian truy xuaát BNC tc : thôøi gian truy xuaát cache hit-ration : tæ leä tìm thaáy moät soá hieäu trang p trong TLB
Coâng thöùc tính thôøi gian truy caäp thöïc teá (Time Effective Acess) ñeán moät ñoái töôïng trong BNC bao goàm thôøi gian chuyeån ñoåi ñòa chæ vaø thôøi gian truy xuaát döõ lieäu TEA = (time biding add + time acces memory)
4/6/2008
Trần Hạnh Nhi
72
Linker-Loader TEA = tm
(data)
Base + Bound
TEA = (tc + tc)
(Base & Bound)
Segmentation TEA =
tc
(ST trong cache)
Paging
+
+
Khoâng söû duïng TLB : TEA = tm
tm
(data)
tm
(data)
+
(PT trong mem)
tm
(data)
Coù söû duïng TLB : TEA = hit-ratio ( tc + tm ) + (1- hit-ratio)( tc + tm + tm ) (TLB) (data)
(TLB) (PT) (data)
Baøi giaûng 7 : Boä nhôù AÛo VaÁn ñeà vôùi Real Memory YÙ töôûng Virtual Memory Thöïc hieän Virtual Memory Caùc chieán löôïc cuûa Virtual Memory Chieán löôïc naïp Chieán löôïc thay theá trang Chieán löôïc caáp phaùt khung trang
Hieän töôïng thrashing Nguyeân nhaân Giaûi phaùp 12/16/2007
Trần Hạnh Nhi
1
Caùc caáp boä nhôù Cho ñeán nay : Naïp toaøn boä tieán trình vaøo boä nhôù roài thöïc hieän noù... Neáu kích thöôùc tieán trình lôùn hôn dung löông boä nhôù chính ? Memory Cache Registers
12/16/2007
Trần Hạnh Nhi
2
Giaûi phaùp Taïi moät thôøi ñieåm chæ coù 1 chæ thò ñöôïc thi haønh Taïi sao phaûi naïp taát caû tieán trình vaøo BNC cuøng 1 luùc ?
YÙ töôûng Cho pheùp naïp vaø thi haønh töøng phaàn tieán trình Ai ñieàu khieån vieäc thay ñoåi caùc phaàn ñöôïc naïp vaø thi haønh ?
Taïi moät thôøi ñieåm chæ giöõ trong BNC caùc chæ thò vaø döõ lieäu caàn thieát taïi thôøi ñieåm ñoù Caùc phaàn khaùc cuûa tieán trình naèm ôû ñaâu ?
Giaûi phaùp
12/16/2007
Boä nhôù aûo (virtual memory)
Trần Hạnh Nhi
3
Virtual Memory Neáu coù moät Virtual Memory vôùi dung löôïng raát raát lôùn cho LTV laøm vieäc... Hoan hoâ ! Virtual Memory Memory Cache Registers
12/16/2007
Trần Hạnh Nhi
4
YÙ töôûng Taùch bieät KGÑC vaø KGVL
LTV : moãi tieán trình laøm vieäc vôùi KGÑC 2m cuûa mình (ñòa chæ töø 0 – (2m -1)) HÑH : chòu traùch nhieäm naïp caùc KGÑC vaøo moät KGVL chung
Giaûi phaùp cuûa HÑH : Naïp töøng phaàn tieán trình Phaân chia KGÑC thaønh caùc phaàn ? Paging/Segmentation
Môû roäng BNC ñeå löu tröõ caùc phaàn cuûa tieán trình chöa ñöôïc naïp Duøng BNP(disk) ñeå môû roäng BNC
Nhaän bieát phaàn naøo cuûa KGÑC chöa ñöôïc naïp ?
Boå sung bit côø hieäu ñeå nhaän daïng tình traïng cuûa moät page/segment laø ñaõ ñöôïc naïp vaøo BNC hay chöa
Cô cheá chuyeån ñoåi qua laïi caùc phaàn cuûa tieán trình giöõa BNC vaø BNP Swapping...
12/16/2007
Trần Hạnh Nhi
5
Virtual Memory vôùi cô cheá phaân trang (Paging) Phaân chia KGÑC thaønh caùc page Duøng BNP(disk) ñeå môû roäng BNC, löu tröõ caùc phaàn cuûa tieán trình chöa ñöôïc naïp Boå sung bit côø hieäu trong Page Table ñeå nhaän daïng tình traïng moät page ñaõ ñöôïc naïp vaøo BNC hay chöa .
12/16/2007
Caáu truùc moät phaàn töû trong Page Tables Trần Hạnh Nhi
6
Löu tröõ KGÑC ôû ñaâu ? Söû duïng boä nhôù phuï ñeå löu tröõ taïm thôøi caùc trang chöa söû duïng P
DISK
RAM
12/16/2007
Trần Hạnh Nhi
7
Virtual Memory
virtual address space
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
4
13
2
18 3
physical memory
7
1
5
3
12/16/2007
Trần Hạnh Nhi
8
Memory Lookup present bit Page table
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
000 000 000 000 111 000 101 000 000 000 011 100 000 110 001 010
0 0 0 0 1 0 1 0 0 0 1 1 1 1 1 1
Incoming virtual address (0x2004, 8196) 12/16/2007
Outgoing physical address 1 1 0
(0x6004, 24580)
4-bit index into page table virtual page = 0x0010 = 2
12-bit offset
0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0
Trần Hạnh Nhi
9
Memory Lookup present bit Page table
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
000 000 000 000 111 000 101 000 000 000 011 100 000 110 001 010
0 0 0 0 1 0 1 0 0 0 1 1 1 0 1 1
Incoming virtual address (0x2004, 8196) 12/16/2007
Outgoing physical address
PAGE FAULT 4-bit index into page table virtual page = 0x0010 = 2
12-bit offset
0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0
Trần Hạnh Nhi
10
Demand Paging int i,j;
i
emacs
main () {
j
ji
i = 5; j = 2; }
i=5
gcc
j=2
KGDC Khi naïp moät tieán trình môùi, chæ naïp vaøo BNC page chöùa entry code Khi truy xuaát ñeán moät chæ thò hay döõ lieäu, page töông öùng môùi ñöôïc naïp vaøo BNC 12/16/2007
Trần Hạnh Nhi
code KGVL 11
Swapping
12/16/2007
Trần Hạnh Nhi
12
Demand Paging + Swapping int i,j; main () { i = 5; j = 2; }
i
emacs j
ji i=5
gcc
j=2
KGDC 12/16/2007
code Trần Hạnh Nhi
KGVL
13
Boä nhôù aûo = “True lie“ Ngöôøi duøng : sôû höõu boä nhôù “voâ haïn”, “rieâng bieät” Heä ñieàu haønh : “thaàm laëng” thöïc hieän quaù trình swapping # of references
10% RAM + 90% DISK Memory address
DISK
RAM 12/16/2007
Trần Hạnh Nhi
14
Thöïc hieän Boä nhôù aûo Baûng trang : theâm 1 bit valid/invalid ñeå nhaän dieän trang ñaõ hay chöa ñöôïc naïp vaøo RAM Frame 17 4183 177 5721
valid/invalid 1 0 1 0
Disk Mem
Truy xuaát ñeán moät trang chöa ñöôïc naïp vaøo boä nhôù : loãi trang (page fault)
12/16/2007
Trần Hạnh Nhi
15
Page Tables
Xöû lyù loãi trang 3
OS
xaùc ñònh vò trí löu trang treân ñóa loãi trang 2
truy xuaát
swap out trang naïn nhaân
1
naïp M
Boä nhôù aûo
12/16/2007
i 6
taùi kích hoaït tieán trình
Page Table
3’
M
frame troáng
5
caäp nhaät baûng trang
4
Boä nhôù vaät lyù
Trần Hạnh Nhi
mang trang caàn truy xuaát vaøo boä nhôù
17
Caùc böôùc xöû lyù loãi trang 1. 2.
3. 4.
Kieåm tra truy xuaát ñeán boä nhôù laø hôïp leä hay baát hôïp leä Neáu truy xuaát baát hôïp leä : keát thuùc tieán trình Ngöôïc laïi : ñeán böôùc 3 Tìm vò trí chöùa trang muoán truy xuaát treân ñóa. Tìm moät khung trang troáng trong boä nhôù chính : a. b.
5.
6.
Neáu tìm thaáy : ñeán böôùc 5 Neáu khoâng coøn khung trang troáng, choïn moät khung trang naïn nhaân ñeå swap out, caäp nhaät baûng trang töông öùng roài ñeán böôùc 5
Chuyeån trang muoán truy xuaát töø boä nhôù phuï vaøo boä nhôù chính : naïp trang caàn truy xuaát vaøo khung trang troáng ñaõ choïn (hay vöøa môùi laøm troáng ) ; caäp nhaät noäi dung baûng trang, baûng khung trang töông öùng. Taùi kích hoaït tieán trình ngöôøi söû duïng.
12/16/2007
Trần Hạnh Nhi
18
Caùc caâu hoûi 1.
Choïn trang naøo ñeå naïp ? => Chieán löôïc naïp Demand Paging / Prepageing
2.
Choïn trang naïn nhaân ? => Chieán löôïc thay theá trang FIFO / OPTIMAL/LRU
3.
Caáp phaùt khung trang => Chieán löôïc caáp phaùt khung trang Coâng baèng/ Tyû leä...
12/16/2007
Trần Hạnh Nhi
19
Chieán löôïc naïp Quyeát ñònh thôøi ñieåm naïp moät/nhieàu page vaøo BNC Naïp tröôùc : laøm sao bieát ? =>prepaging Naïp sau : taàn suaát loãi trang cao ? => pure demand paging
Prepaging : Naïp saün moät soá trang caàn thieát vaøo BNC tröôùc khi truy xuaát chuùng
Demand paging : Chæ naïp trang khi ñöôïc yeâu caàu truy xuaát ñeán trang ñoù
ld init pages
ld page
ld page
ld page
init pages = 12/16/2007
Trần Hạnh Nhi
...
? 20
Chieán löôïc thay theá trang (Page Replacement) Muïc tieâu : thay theá trang sao cho taàn suaát xaûy ra loãi trang thaáp nhaát Ñaùnh giaù Söû duïng soá frame cuï theå Giaû söû coù moät chuoãi truy xuaát cuï theå adresse : 0100, 0432, 0101, 0612, 0102, 0103, 0104, 0611 # page : 1, 4, 1, 6, 1, 1, 1, 6,
Thöïc hieän moät thuaät toaùn thay theá trang treân chuoãi truy xuaát naøy Ñeám soá loãi trang phaùt sinh Chuoãi truy xuaát 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 3 frames 12/16/2007
Trần Hạnh Nhi
21
Chieán löôït thay theá trang FIFO Optimal LRU (Least Recently Used)
12/16/2007
Trần Hạnh Nhi
22
Chieán löôïc thay theá trang FIFO Nguyeân taéc : Naïn nhaân laø trang “giaø” nhaát Ñöôïc naïp vaøo laâu nhaát trong heä thoáng
victim
add
Thöïc hieän
Löu thôøi ñieåm naïp, so saùnh ñeå tìm min Chi phí cao
Toå chöùc FIFO caùc trang theo thöù töï naïp Trang ñaàu danh saùc laø naïn nhaân
Nhaän xeùt
Ñôn giaûn Coâng baèng ? Khoâng xeùt ñeán tính söû duïng !
Trang ñöôïc naïp vaøo laâu nhaát coù theå laø trang caàn söû duïng thöôøng xuyeân !
12/16/2007
Trần Hạnh Nhi
23
Ví duï : FIFO
7
0
1
2
0
3
0
4
2
3
0
3
2
1
2
0
7
7
7
7 2
2
2
2
4 2
4
4
4 0
0
0
0
0
0
0
0
0
0
0 3
3
3
32
2
2
2
2
2 1
1
1
1
1
1
1
1 0
0
0
0 3
3
3
3
3
2 3
2
*
*
*
*
*
*
*
*
*
*
*
*
12/16/2007
Trần Hạnh Nhi
...
24
FIFO vaø hieäu öùng Belady Söû duïng caøng nhieàu frame...caøng coù nhieàu loãi trang !
12/16/2007
Trần Hạnh Nhi
25
Chieán löôïc thay theá trang : Optimal Nguyeân taéc : Naïn nhaân laø trang laâu söû duïng ñeán nhaát trong töông lai Laøm sao bieát ?
Nhaän xeùt Baûo ñaûm taàn suaát loãi trang thaáp nhaát Khoâng khaû thi !
12/16/2007
Trần Hạnh Nhi
victim AGBDCABCABCGABC Cur page
26
Ví duï : Optimal
7
0
1
2
0
3
0
4
2
3
7
7
7
7 2
2
2
2
2
2
2
0
0
0
0
0
0
0 4
4
1
1
1
3 1
3
3
3
*
*
*
*
12/16/2007
*
3
2
1
2
0
2
2
2
2
2
0
4
0 4
0
0
0
0
1
3
3
3
3
1 3
1
2
*
0
*
Trần Hạnh Nhi
...
*
27
Chieán löôïc thay theá trang : LRU Nguyeân taéc : Naïn nhaân laø trang laâu nhaát chöa söû duïng ñeán trong quaù khöù Nhìn lui : ñuû thoâng tin
victim
Nhaän xeùt Xaáp xæ Optimal Thöïc hieän ?
AGBDCABCABCGABC Cur page
12/16/2007
Trần Hạnh Nhi
28
Ví duï : LRU
0
1
2
0
3
0
4
7
7
7
7 2
2
2
2
2 4
4
4
0
0
0
0
0
0
0
0
1
1
1
3 1
3
3
*
*
*
*
12/16/2007
*
*
2
3
7
3
2
1
2
0
0 4
0
0
0 1
1
1
3 0
3
3
3
3
3
3 0
3 2
2
2
2
2
2
2
2
*
*
*
Trần Hạnh Nhi
0
*
...
*
29
Thöïc hieän LRU Söû duïng boä ñeám: Theâm tröôøng reference time cho moãi phaàn töû trong baûng trang Theâm vaøo caáu truùc cuûa CPU moät boä ñeám counter. moãi laàn coù söï truy xuaát ñeán moät trang trong boä nhôù giaù trò cuûa counter taêng leân 1. giaù trò cuûa counter ñöôïc ghi nhaän vaøo reference time cuûa trang töông öùng.
thay theá trang coù reference time laø min .
Söû duïng stack: toå chöùc moät stack löu tröõ caùc soá hieäu trang moãi khi thöïc hieän moät truy xuaát ñeán moät trang, soá hieäu cuûa trang seõ ñöôïc xoùa khoûi vò trí hieän haønh trong stack vaø ñöa leân ñaàu stack. trang ôû ñænh stack laø trang ñöôïc truy xuaát gaàn nhaát, vaø trang ôû ñaùy stack laø trang laâu nhaát chöa ñöôïc söû duïng.. 12/16/2007
Trần Hạnh Nhi
30
Thöïc hieän LRU vôùi stack
12/16/2007
Trần Hạnh Nhi
31
Thöïc hieän LRU : thöïc teá Heä thoáng ñöôïc hoã trôï phaàn cöùng hoaøn chænh ñeå caøi ñaët LRU ? Ñöøng coù mô !
Heä thoáng chæ ñöôïc trang bò theâm moät bit reference : gaén vôùi moät phaàn töû trong baûng trang. ñöôïc khôûi gaùn laø 0 ñöôïc phaàn cöùng ñaët giaù trò 1 moãi laàn trang töông öùng ñöôïc truy caäp ñöôïc phaàn cöùng gaùn trôû veà 0 sau töøng chu kyø qui ñònh tröôùc.
Bit reference chæ giuùp xaùc ñònh nhöõng trang coù truy caäp, khoâng xaùc ñònh thöù töï truy caäp Khoâng caøi ñaët ñöôïc LRU Xaáp xæ LRU...
reference
12/16/2007
modify
frame
Trần Hạnh Nhi
protect
32
4-53
Xaáp xæ LRU : Söû duïng caùc bits History thôøi gian 0 0 0 0 0
0 1 0 1 0
bit reference
1 0 1 1 0
0 1 0 1 0
1 1 0 0 0
caùc bits history
söû duïng theâm N bit history phuï trôï Sau töøng chu kyø, bit reference seõ ñöôïc cheùp laïi vaøo moät bit history tröôùc khi bi reset N bit history seõ löu tröõ tình hình truy xuaát ñeán trang trong N chu kyø cuoái cuøng. 12/16/2007
Trần Hạnh Nhi
33
Thôøi gian
0
0
0
1
0
0
0
1
0
0
0 1 0 1 0
Thôøi gian
0
0
1
0
1
0
0
0
1
0
1
1
0
0
0
1
0
0
1
1
0
1
1
0
0
Thôøi gian
0
0
1
0
0
1
0
1
0
0
1
0
0
1
1
1
0
0
0
0
0
1
0
1
0
1
0
1
0
1
1
1
0
0
0
Thôøi gian
0
0
1
0
1
0
1
0
1
1
0
0
1
0
0
0
1
1
1
0
0
0
0
0
0
1
0
1
0
1
1
0
1
0
0
1
0
0
1
1
1
0
0
0
0
Xaáp xæ LRU : Cô hoäi thöù 2 (Clock algorithme) Söû duïng moät bit reference duy nhaát. Choïn ñöôïc trang naïn nhaân theo FIFO Kieåm tra bit reference cuûa trang ñoù : Neáu reference = 0, ñuùng laø naïn nhaân roài ☺ Neáu reference = 1, cho trang naøy moät cô hoäi thöù hai reference = 0 thôøi ñieåm vaøo Ready List ñöôïc caäp nhaät laïi laø thôøi ñieåm hieän taïi.
Choïn trang FIFO tieáp theo... Nhaän xeùt : Moät trang ñaõ ñöôïc cho cô hoäi thöù hai seõ khoâng bò thay theá tröôùc khi heä thoáng ñaõ thay theá heát nhöõng trang khaùc. Neáu trang thöôøng xuyeân ñöôïc söû duïng, bit reference cuûa noù seõ duy trì ñöôïc giaù trò 1, vaø trang haàu nhö khoâng bao giôø bò thay theá. 12/16/2007
Trần Hạnh Nhi
38
Xaáp xæ LRU : Cô hoäi thöùc 2 (Clock algorithme)
12/16/2007
0
page#
0
page#
Trang FIFO
10
page#
Trang FIFO
10 1
page#
Naïn nhaân
00
page#
10 1
page#
10 1
page#
Trần Hạnh Nhi
4-55
39
Xaáp xæ LRU : NRU Söû duïng 2 bit Reference vaø Modify Vôùi hai bit naøy, coù theå coù 4 toå hôïp taïo thaønh 4 lôùp sau : (0,0) khoâng truy xuaát, khoâng söûa ñoåi (0,1) khoâng truy xuaát gaàn ñaây, nhöng ñaõ bò söûa ñoåi (1,0) ñöôïc truy xuaát gaàn ñaây, nhöng khoâng bò söûa ñoåi (1,1) ñöôïc truy xuaát gaàn ñaây, vaø bò söûa ñoåi
Priority
R
M
4
0
0
3
0
1
2
1
0
1
1
1
Choïn trang naïn nhaân laø trang coù ñoä öu tieân cao nhaát khi keát hôïp bit R vaø bit M 12/16/2007
Trần Hạnh Nhi
40
Chieán löôïc caáp phaùt frame Soá frame caàn caáp phaùt cho moãi tieán trình ? Giaûi söû coù m frame vaø n process Caáp phaùt coâng baèng: #frame(Pi) = m/n Coâng baèng ???
Caáp phaùt theo tyû leä: #frame(pi) = (si / (Σ si ))* m si = kích thöôùc cuûa boä nhôù aûo cho tieán trình pi Loãi trang xaûy ra tieáp theo, caáp phaùt theâm frame cho tieán trình nhö theá naøo ? Tuøy thuoäc chieán löôïc thay theá trang Cuïc boä : chæ choïn trang naïn nhaân trong taäp caùc trang cuûa tieán trình phaùt sinh loãi trang -> soá frame khoâng taêng Toaøn cuïc: ñöôïc choïn baát kyø trang naïn nhaân naøo (duø cuûa tieán trình khaùc) > soá frame coù theå taêng, loãi trang lan truyeàn
12/16/2007
Trần Hạnh Nhi
41
Thay theá trang toaøn cuïc vaø...keát cuïc bi thaûm !
Running
IO
CPU
P1, error
P1
P2, error
P1 P2
P3, error
P3
P1, swap out P2, swap out
P1
Taát caû caùc tieán trình baän roän thay theá trang ! 12/16/2007
Trần Hạnh Nhi
42
Thrashing Taát caû tieán trình ñaàu baän roän xöû lyù loãi trang ! IO hoaït ñoäng 100 %, CPU raûnh ! Heä thoáng ngöøng treä P1
P2
P3
Real mem
Virtual Memory = Tha hoà xaøi boä nhôù Thrashing = aûo töôûng suïp ñoå ! Caùc tieán trình trong heä thoáng yeâu caàu boä nhôù nhieàu hôn khaû naêng cung caáp cuûa heä thoáng ! 12/16/2007
Trần Hạnh Nhi
43
Thrashing Diagram
Why does 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
44
Nguyeân nhaân Thrashing 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
Chæ coù theå kieåm soaùt thrashing do nguyeân nhaân 3.
12/16/2007
Trần Hạnh Nhi
45
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
46
Working-Set Model Δ ≡ working-set window ≡ soá laàn truy caäp VD: 10,000 instruction 261577775162341234443434441323 Δ=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
47
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
48
BAØI GIẢNG 8 : LIEÂN LAÏC GIÖÕA CAÙC TIEÁN TRÌNH
CÔ CHEÁ ? TRAO ÑOÅI THOÂNG TIN GIÖÕA CAÙC TIEÁN TRÌNH VAÁN ÑEÀ ? GÆAI PHAÙP ?
12/16/2007
Trần Hạnh Nhi
1
Nhu Caàu Lieân Laïc Q
Chia seû thoâng tin P Phoái hôïp xöû lyù
L
R
JOB P R1
Q 12/16/2007
Trần Hạnh Nhi
R2
L 2
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
3
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
4
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…
Terminate Process Suspend, Resume…
12/16/2007
Signal Signal handler
Signal Action
User process vôí nhau
OS
Process Trần Hạnh Nhi
5
Name
Value
Function
SIGHUP
1
Terminal hangup
SIGINT
2
Interrupt by user: generated by < CTRL C >
SIGQUIT
3
Quit by user: generated by < CTRL \ >
SIGFPE
8
Floating point error such as divide by zero
SIGKILL
9
Kill the process
SIGUSR1
10
User defined signal 1
SIGSEGV
11
SIGUSR2
12
Segment violation: process has tried to access memory not assigned to it 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 < CTRL Z >
SIGWINCH
28
Change of window size
Nhaän xeùt Signals
L
Lieân laïc khoâng ñoàng boä
SH
Khoâng bieát tröôùc thôøi ñieåm Thieáu tin caäy
Q
Quiz : OK A
Sig
B Khoâng cho pheùp trao ñoåi döõ lieäu
Q 12/16/2007
?
Result
L Trần Hạnh Nhi
7
Pipes AB
Q
B……….A
WritePipe()
AB
L
ReadPipe()
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) 12/16/2007
Trần Hạnh Nhi
8
Nhaän xeùt Pipe
Öu ñieåm :
Khuyeát ñieåm
Cho pheùp trao ñoåi döõ lieäu khoâng caáu truùc 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
9
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
10
IPC theo nguyeân taéc trao ñoåi thoâng ñieäp User Process
User Process
OS-Kernel
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
11
Message
Message
HÑH cung caáp 2 primitive chính
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 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
12
Ñònh daïng Message
12/16/2007
Trần Hạnh Nhi
13
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
14
Lieân laïc giöõa caùc heä thoáng khoâng ñoàng nhaát Máy A P1
Send( ) //UNIX Receive( ) //WIN
(UNIX)
Máy B P2 (Windows)
12/16/2007
Trần Hạnh Nhi
15
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
Socket description
Thieát laäp lieân laïc : taïo 2 socket, keát noái chuùng vôùi nhau
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
16
12/16/2007
Trần Hạnh Nhi
17
Socket Communication
12/16/2007
Trần Hạnh Nhi
18
Lieân laïc giöõa caùc heä thoáng khoâng ñoàng nhaát Máy A P1 (UNIX) Receive( )
12/16/2007
Socket
Socket
Trần Hạnh Nhi
Send( )
P2
Máy B
(Windows)
19
Lieân laïc thoâng qua Socket
Hoã trôï 2 phöông thöùc lieân laïc
Connection-oriented (TCP/IP)
Connectionless (UDP/IP)
Stream Reliable Bi-directional communication 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
20
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
Döõ lieäu ñöôïc phaân phoái
Töông töï heä thoáng ñieän thoaï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
21
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
22
Caáu truùc ñòa chæ Socket
Generic socket address structure:
struct sockaddr { sa_family_t sa_family; char sa_data[14]; };
/* address family */ /* 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
23
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
24
Some Well-Known Ports
12/16/2007
Trần Hạnh Nhi
25
Socket Types
Socket types:
SOCK_STREAM
SOCK_DGRAM
Stream socket (TCP) Datagram socket (UDP)
SOCK_RAW
Raw socket (talk to IP directly)
12/16/2007
Trần Hạnh Nhi
26
Socket Primitives Primitive Socket Bind Listen Accept Connect Send Receive Close
12/16/2007
YÙ nghóa Taïo 1 communication endpoint Keát buoäc moät local address vôùi 1 socket Thoâng baùo saün saøng “laéng nghe” (tieáp nhaän keát noái) Khoaù caller ñeán khi coù 1 yeâu caàu keát noái Chuû ñoäng thöïc hieän keát noái Gôûi döõ lieäu qua keát noái ñaõ thieát laäp Nhaän döõ lieäu qua keát noái ñaõ thieát laäp Keát thuùc keát noái
Trần Hạnh Nhi
27
TCP System Calls
Server socket() bind()
Client
listen()
socket()
accept() blocks until connection from client
connect() write()
read() process request
12/16/2007
write()
read()
close()
close()
Trần Hạnh Nhi
28
UDP System Calls
Server
socket() bind()
Client
recvfrom()
socket() blocks until data received from a client
sendto()
data(request) process request sendto()
data(reply)
recvfrom() close()
12/16/2007
Trần Hạnh Nhi
29