File Goc 770002 [PDF]

Zitiervorschau

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