Hệ điều hành (Operating System)

1Hệ điều hành (Operating System) PHAN Xuân Huy {pxhuy@fit.hcmuns.edu.vn} 2Thô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 – pxhuy@fit.hcmuns.edu.vn „ 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 3Mụ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. 4Thả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 5Thả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) 60MB „ Windows Media Player 12MB „ Visual Studio .NET 30MB „ Làm cách nào mà Windows vẫn chạy được? 6Thả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? „ Chỉ có các hệ điều hành nhưME, 2000, XP, „ Vậy HĐH đã sử dụng giải pháp nào? „ 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? 7Nộ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ớ 8Chươ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 9Vai 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 10 HĐH và các thành phần của hệ thống 11 HĐH và các thành phần của hệ thống 12 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) 13 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) 14 Các thành phần của HĐH Quaûn lyù tieán trình Quaûn lyù boä nhôù chính Quaûn lyù nhaääp xuaát Quaûn lyù boä nhôù phuï Heä thoáng taäp tin Heä thoáng baûo veä Giao tieáp maïngBoä thoâng dòch leänh 15 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 16 1. Kiến trúc đơn giản „ 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? Ứng dụng Hệ điều hành (DOS) Phần cứng (BIOS, port) Tiện ích thường trú Ví dụ với HĐH DOS 17 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 !!! 18 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 19 3.Kiến trúc máy ảo (2/4) Non-virtual Machine Virtual Machine 20 3.Kiến trúc máy ảo (3/4)- Ví dụ „ Java Virtual Machine Java OS Java VM Operating System Hardware Process Process Java program • Độc lập với Platform 21 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. 22 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 23 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 24 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 25 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ớ 26 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 27 Quá trình phát triển của dòng HĐH Windows (2/4) „ Windows 95 „ 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 „ Windows 98 „ 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. 28 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 29 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 „ Minix-like OS by Linus Torvard „ limited devices, no networking „ 1994: Linux 1.0 „ 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 30 Quá trình phát triển của dòng HĐH Linux (2/2) „ 1996: Linux 2.0 „ multiple architectures, multiple processors „ threads, memory management „ 1999: Linux 2.2 „ 2001: Linux 2.4 „ ISA PnP, USB, „ 12/2003: Linux 2.6 31 Các distro chính của HĐH Linux „ Mandrake „ Fedora/Redhat „ Debian „ SUSE „ Gentoo „ 32 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. 1Chươ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 2Nhiệ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. 3Ví 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. 4Phâ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ự. 5Phâ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 6Cá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. 7Cá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ị 8Cá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 9Cá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 10 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. 11 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 12 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 13 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) „ Dùng cho các thiết bị tuần tự (v.d. USB port, bàn phím, modem) „ Thiết bị mạng „ 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 14 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. 15 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. 16 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? 17 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ề, <0 là lỗi „ Vị trí hiện hành là 1 số nguyên tính theo byte, có thể là bội số của block. 18 Thiết bị xuất nhập „ Màn hình: Thiết bị xuất chuẩn: „ Ký tự hay đồ hoạ „ Khả năng hiển thị: „ Độ phân giải: „ Ví dụ : 25 x 80 ký tự hay 800 x 600 x 256 màu. „ Độ làm tươi: „ 30-60 lần/giây. 19 Thiết bị xuất nhập „ Bàn phím: Thiết bị nhập chuẩn „ Bố trí theo cấu trúc “QWERTY” „ Tốc độ nhập dữ liệu chậm (<10 ký tự/giây) „ Thiết bị trỏ/định vị: Thiết bị nhập chuẩn „ Chuột (quang, cơ) „ Trackball „ Joystick „ Tốc độ nhập dữ liệu chậm (vài trăm bytes/giây) 20 Thiết bị xuất nhập „ Máy in „ Máy in dòng, máy in điểm, máy in phun, in laser. „ Tốc độ đẩy dữ liệu chậm „ Hướng ký tự „ Máy quét „ Số hoá các tài liệu in thành các dữ liệu số dưới dạng ảnh bitmap. „ Tốc độ quét chậm 21 Thiết bị xuất nhập „ Đĩa từ : Đĩa mềm (floppy disk), đĩa cứng (hard disk): „ Thiết bị xuất nhập theo khối (sector). „ Dung lượng tuỳ thuộc vào số head,track,sector. „ Tốc độ truy cập phụ thuộc vào tốc độ quay và mật độ dữ liệu trên đĩa. „ Băng từ: „ Thiết bị truy cập tuần tự dung lượng lớn. „ Tốc độ truy cập ~2Mb/s „ CDROM/DVD: „ Tốc độ truy cập nhanh. „ Dung lượng ngày càng lớn và giá thành ngày càng rẻ. 22 Thiết bị xuất nhập „ Thiết bị giao tiếp mạng „ Card mạng „ Cài đặt các giao thức mạng khác nhau để hỗ trợ cho quá trình truyền nhận các luồng/gói dữ liệu. „ Modem „ Chuyển đổi giữa tín hiệu tuần tự và tín hiệu số trên đường truyền thoại. „ Luồng dữ liệu truyền là các dãy bít được gom nhóm thành các ký tự. „ Đồng hồ hệ thống (clock) và bộ định giờ (timer) „ Cung cấp thời gian hệ thống để giúp đồng bộ hoá các hoạt động trên máy tính. 23 Bộ điều khiển thiết bị „ Mỗi đơn vị nhập xuất thường gồm 2 thành phần: „ Thành phần cơ: Bản thân thiết bị „ Thành phần điện: bộ điều khiển (controller) „ Bộ điều khiển: „ Chức năng: Trung gian giao tiếp giữa thiết bị và HĐH. „ Phương tiện giao tiếp: Thông qua bus - hệ thống mạch truyền dẫn. „ Công việc: „ Nhận lệnh từ HĐH để thực hiện và báo hiệu cho HĐH khi tác vụ hoàn tất. „ Chuyển đổi dãy bit thành các byte và đặt chúng vào trong bộ đệm (buffer) của bộ điều khiển. 24 Các thiết bị xuất nhập và bus hệ thống 25 Địa chỉ giao tiếp thiết bị „ HĐH giao tiếp với thiết bị thông qua địa chỉ xuất nhập của bộ điều khiển: 26 Mô hình phân lớp trong quản lý xuất nhập „ Hệ thống xuất nhập được tổ chức theo từng lớp, mỗi lớp có 1 chức năng nhất định và có sự hỗ trợ liên hoàn lẫn nhau: 27 Phần mềm độc lập thiết bị „ Chức năng: „ Tạo ra giao tiếp chung cho tất cả các thiết bị. „ Bảo vệ thiết bị „ Cung cấp khối dữ liệu độc lập thiết bị „ Cung cấp bộ đệm (buffer) để hỗ trợ cho quá trình đồng bộ hoá hoạt động của hệ thống. „ Định vị trí lưu trữ trên các khối thiết bị. „ Cấp phát và giải phóng thiết bị. „ Thông báo lỗi cho người dùng (nếu có). 28 Trình điều khiển thiết bị „ Chức năng: „ Nhận yêu cầu từ phía lớp phần mềm độc lập thiết bị. „ Chuyển đổi yêu cầu trừu tượng này thành cụ thể. „ Điều phối yêu cầu này cho bộ điều khiển thiết bị (device controller). „ Giám sát thực hiện yêu cầu. „ Ví dụ: „ HĐH muốn đọc tập tin io.sys trên đĩa ở thư mục C:\. „ Trình điều khiển đĩa phải hiểu là cần đọc khối nào. „ Trình điều khiển đĩa chuyển yêu cầu này cho bộ điều khiển đĩa. „ Bộ điều khiển đĩa phải kiểm tra hoạt động của motor đĩa, xác định đầu đọc đã đúng vị trí chưa. 29 Trình điều khiển thiết bị 30 Bộ kiểm soát ngắt (interrupt handler) „ Tương tác giữa HĐH và các thiết bị phần cứng đều được thực hiện thông qua cơ chế ngắt (interrupt). „ Bộ kiểm soát ngắt sẽ tiếp nhận các ngắt từ HĐH và ứng dụng của người dùng cuối. „ Dựa trên bảng “Interrupt vector” để phân phối các ngắt đến các bộ điều khiển thiết bị tương ứng. „ Quản lý và giám sát quá trình thực hiện ngắt. „ Nhận ngắt thông báo quá trình xuất nhập hoàn tất hoặc có lỗi xảy ra trong quá trình xuất nhập từ bộ điều khiển thiết bị để chuyển lên cho HĐH. 31 Bộ kiểm soát ngắt (interrupt handler) 32 Cơ chế truy cập bộ nhớ trực tiếp DMA (Direct Memory Access) „ Xét quá trình đọc đĩa không có DMA: „ HĐH chuyển yêu cầu đọc đĩa cho bộ điều khiển đĩa. „ Bộ điều khiển đọc tuần tự các khối trên đĩa. „ Đọc từng bit cho đến khi các khối được đưa vào bộ đệm của bộ điều khiển đĩa. „ Bộ điều khiển đĩa tạo ngắt để báo qua CPU biết quá trình đọc đĩa hoàn tất. „ CPU lần lượt lấy từng byte dữ liệu từ bộ đệm của bộ điều khiển đĩa để chuyển về bộ nhớ chính để thao tác. „ Nhận xét: „ Lãng phí thời gian xử lý của CPU để chuyển dữ liệu từ bộ đệm của bộ điều khiển đĩa về bộ nhớ chính 33 Cơ chế DMA „ Cơ chế DMA giúp CPU không bị lãng phí bằng cách: „ HĐH gởi cho bộ điều khiển đĩa các thông số gồm: các khối cần đọc + vị trí lưu trữ các khối này bên trong bộ nhớ chính (địa chỉ DMA) + số byte cần đọc. „ Bộ điều khiển đĩa đọc các khối cần thiết lưu vào trong bộ đệm của nó. „ Sau khi đọc xong, bộ điều khiển chuyển lần lượt từng byte từ bộ đệm của nó về địa chỉ DMA – nơi cần lưu trữ dữ liệu cần thiết bên trong bộ nhớ chính. „ Bộ điều khiển đĩa tạo 1 ngắt để thông báo cho CPU biết quá trình chuyển dữ liệu đã hoàn tất. 34 Cơ chế DMA 35 Quản lý lỗi & bảo vệ xuất nhập thiết bị „ Quá trình xử lý của người dùng cuối hay HĐH có thể vô tình hay cố ý thực hiện các lệnh/thao tác xuất nhập bất hợp pháp gây hại cho hệ thống và thiết bị. „ Cần định nghĩa trước và gán đặc quyền cho các lệnh xuất nhập của hệ thống dưới dạng các lời gọi hệ thống (system call). „ Giám sát quá trình xuất nhập của người dùng cuối. „ Tất cả quá trình xuất nhập của ƯD phải được thực hiện thông qua các lời gọi hệ thống. 36 Quản lý lỗi & bảo vệ xuất nhập thiết bị „ Khi gặp lỗi trong quá trình xuất nhập, các bộ điều khiển thiết bị sẽ trả về cho HĐH mã lỗi tương ứng „ HĐH diễn dịch mã lỗi trả về để có phương án giải quyết thích hợp. „ HĐH cũng diễn dịch và lưu vào nhật ký hệ thống (system log) các lỗi tương ứng để giúp người quản trị hệ thống giám sát lỗi và phục hồi. 1Chương 3: Hệ thống quản lý tập tin „ Nội dung chương: „ Các khái niệm cơ bản về hệ thống tập tin „ Cài đặt hệ thống quản lý tập tin „ Mô hình tổ chức và quản lý tập tin của các HĐH thông dụng. „ Truy xuất hệ thống quản lý tập tin. 2Hệ thống lưu trữ trong máy tính „ Bộ nhớ trong „ RAM, ROM, Register, Cache „ Bộ nhớ ngoài „ HD (Hard Disk) „ FD (Floppy Disk) „ CD (Compact Disk) „ DVD (Digital Video Disk) „ USB disk „ cache Bộ nhớ chính Bộ nhớ phụ (đĩa) Bộ nhớ thứ cấp (băng từ) T ố c đ ộ D u n g l ư ợ n g G i á t h à n h 3Các khái niệm cơ bản „ RAM không có khả năng lưu trữ dữ liệu lâu dài. „ Máy tính phải sử dụng các thiết bị có khả năng lưu trữ lâu dài vì: „ Chứa lượng thông tin lớn. „ Thông tin được lưu trữ trước khi xử lý. „ Nhiều ứng dụng muốn truy cập cùng lúc. Æ Phải sử dụng các thiết bị lưu trữ ngoài gọi là bộ nhớ ngoài với các đơn vị lưu trữ được tổ chức thành: „ Tập tin „ Thư mục 4Tổ chức dữ liệu trên đĩa từ „ Cấu trúc vật lý của đĩa từ: „ Hình tròn, gồm nhiều mặt gọi là head. „ Mỗi mặt có nhiều đường tròn đồng tâm gọi là track hay cylinder. „ Trên các đường tròn (track) được chia thành các cung tròn gọi là sector. „ Mỗi cung tròn chứa 4096 điểm từ (~ 4096 bit = 512 bytes). „ Mỗi mặt có 1 đầu đọc để đọc ghi dữ liệu „ Mỗi lần đọc/ghi ít nhất 1 cung tròn (512B). 5Cấu trúc đĩa từ Head 0 Head 2 6Cấu trúc đĩa từ read-write head track sectors cylinder 7Cấu trúc đĩa từ 8Tổ chức dữ liệu trên đĩa từ (tt) „ Mỗi lần đọc hay ghi đĩa có thể thực hiện N sector liên tiếp (N>=1). „ Vị trí của mỗi sector trong đĩa được thể hiện bằng 3 tham số : {sector, track, head}. „ Head được đánh số từ trên xuống bắt đầu từ 0. „ Track được đánh số từ ngoài vào bắt đầu từ 0. „ Sector được đánh số bắt đầu từ 1 theo chiều ngược với chiều quay của đĩa. 9Tổ chức đĩa logic „ Thay vì phải dùng đến 3 tham số dựa trên cấu trúc đĩa vật lý nên khái niệm đĩa logic được đưa ra để dễ thao tác và tính toán hơn. „ Đĩa logic là một dãy sector được đánh số bắt đầu từ 0. „ Mỗi sector trên đĩa logic tương ứng với 1 sector duy nhất trên đĩa vật lý sao cho khi truy xuất sector K thì khi truy xuất tiếp sang sector K+1 là nhanh nhất. N-143210 10 Dung lượng đĩa „ Kích thước đĩa phụ thuộc vào các yếu tố sau: „ Số mặt từ (platter) „ Số track trên mỗi mặt từ „ Số sector trên mỗi track „ Kích thước (byte) trên mỗi track. 11 Ví dụ cách tổ chức đĩa mềm „ Các thông số trên đĩa mềm 1.44MB: „ Đĩa có 2 head, 80 track/head, 18 sector/track. „ Dung lượng đĩa = 2 head/disk *80 track/head *18 sector/track = 2880 sector/disk = 0.5 KB/sector * 2880 sector/disk = 1440 KB/disk (~ 1.4MB) „ Các sector logic có chỉ số từ 0 đến 2879 và tương ứng với các sector vật lý như sau: „ Sector 0..17 tương ứng với sector vật lý (1,0,0)..(18,0,0) „ Sector 18..35 tương ứng với sector vật lý (1,0,1)..(18,0,1) „ „ Sector 2879 tương ứng với sector vật lý (18,79,1). 12 Mặt đĩa Tay quay Đầu đọc Thời gian truy cập đĩa „ Disk access time = Seek Time + Latency Time + Transfer Time 13 Các thuật toán đọc đĩa „ First-Come-First-Serve (FCFS) „ SCAN, C-SCAN „ Shortest Seek Time First (SSTF) „ Look 14 First Come First Serve (FCFS) „ Phục vụ theo thứ tự yêu cầu „ Đơn giản nhưng không đáp ứng tốt dịch vụ t i m e cylinder number 1 5 10 15 20 25 12 Các khối cần đọc (đầu đọc hiện tại tại vị trí 11): 14 2 7 21 8 24 scheduling queue 24 8 21 7 2 14 12 15 SCAN „ Di chuyển đầu đọc về 1 phía của đĩa đến block xa nhất sau đó di chuyển về phía kia. „ Còn gọi là thuật toán thang máy. t i m e cylinder number 1 5 10 15 20 25 12 14 2 7 21 8 24 scheduling queue Các khối cần đọc (đầu đọc hiện tại tại vị trí 11): 16 SCAN vs. FCFS „ Trong trường hợp này, SCAN tốt hơn FCFS vì hạn chế sự di chuyển của đầu đọc đĩa cylinder number 1 5 10 15 20 25 t i m e t i m e 17 C-SCAN „ Nguyên tắc: „ Tương tự thuật toán SCAN. „ Chỉ khác khi di chuyển đến 1 đầu của đĩa thì trở về vị trí bắt đầu của đĩa. 18 C-SCAN 19 LOOK „ Nhận xét: „ Hai thuật toán lập lịch SCAN và C-SCAN luôn luôn di chuyển đầu đọc của đĩa từ đầu này sang đầu kia nhưng thông thường thì đầu đọc chỉ di chuyển đến khối xa nhất ở mỗi hướng chứ không đến cuối. „ Nguyên tắc: „ Giống SCAN và C-SCAN nhưng chỉ di chuyển đầu đọc đến khống xa nhất chứ không đến cuối. 20 LOOK 21 SSTF „ SSTF = Shortest Seek Time First „ Nguyên tắc: „ Di chuyển đầu đọc đến các khối cần thiết theo vị trí lần lượt gần với vị trí hiện hành của đầu đọc nhất 22 SSTF 23 Lập trình tương tác với đĩa „ Các truy xuất đĩa trực tiếp trong C: „ Đọc nội dung sector trên đĩa logic: hàm absread. „ Ghi nội dung vào sector logic: abswrite. „ Thực hiện thao tác trên đĩa vật lý: biosdisk. „ Cú pháp: „ int absread(int drive, int nsects, long lsect, void *buffer). „ int abswrite (int drive, int nsects, long lsect, void *buffer); „ int biosdisk (int cmd, int drive, int head, int track, int sector, int nsects, void *buffer); 24 Tập tin (1/4) „ Tập tin (file) là đơn vị lưu trữ thông tin trên bộ nhớ ngoài. „ Thông tin chứa trong tập tin là bền vững (không bị mất đi khi bị mất điện). „ Tên tập tin: „ Là cơ chế trừu tượng để quản lý tập tin. „ Có thể phân biệt chữ hoa và thường (tuỳ HĐH cụ thể) „ Hỗ trợ tên tập tin theo định dạng 8.3 (gồm tên và phần mở rộng) hay tên dài (Long File Name). „ Ví dụ: baitap.cpp hay “bai tap lap trinh.cpp” 25 Tập tin (2/4) Các thuộc tính của tập tin: „ Người sở hữu/nhóm sở hữu „ Chỉ đọc (Read-only) „ Ẩn (Hidden) „ Hệ thống (System) „ Lưu trữ (Archive) „ Ngày giờ tạo. „ Ngày giờ truy cập cuối cùng „ Ngày giờ thay đổi cuối cùng „ Kích thước 26 Tập tin (3/4) „ Tạo „ Xoá „ Mở „ Đóng „ Đọc „ Ghi Các thao tác trên tập tin: „ Thêm „ Tìm „ Lấy thuộc tính „ Thiết lập thuộc tính „ Đổi tên 27 Tập tin (4/4) „ Các loại tập tin: „ Tập tin văn bản (text file): chứa các dòng văn bản, cuối dùng có ký hiệu kết thúc dòng (end line) „ Tập tin nhị phân (binary file): là tập tin có cấu trúc. „ Các truy xuất trên tập tin: „ Tuần tự: Phải đọc từ đầu tập tin đến vị trí mong muốn. „ Ngẫu nhiên: Có thể di chuyển nhanh (SEEK) đến đúng vị trí cần đọc. 28 Khối điều khiển tập tin 29 Thư mục „ Giúp cho việc quản lý các tập tin dễ dàng hơn. „ Giúp định vị các tập tin 1 cách nhanh chóng. „ Gom nhóm các tập tin vào trong các thư mục theo ý nghĩa và mục đích sử dụng của người dùng. root bob sue www fun3013 30 Thư mục Ví dụ 1 cấu trúc cây thư mục phân cấp 31 Thư mục - Đường dẫn (Path) „ Dùng để xác định vị trí lưu tập tin khi hệ thống được tổ chức thành cây thư mục: „ Đường dẫn tuyệt đối: „ Ví dụ: “C:\Downloads\software\baigiang.doc” „ Đường dẫn tương đối: „ Ví dụ: “software\baigiang.doc” nếu thư mục hiện hành là “C:\Downloads\” „ Các thư mục đặc biệt: „ Thư mục hiện hành (.) „ Thư mục cha (..) 32 Thư mục „ Các thao tác trên thư mục: „ Tạo Xoá Đổi tên „ Mở Đóng „ Tìm kiếm Liệt kê „ Liên kết: Cho phép 1 tập tin có thể xuất hiện trong nhiều thư mục khác nhau. „ Bỏ liên kết: Nếu tập tin chỉ có 1 liên kết với 1 thư mục, nó sẽ bị loại bỏ hoàn toàn, ngược lại nó sẽ bị giảm chỉ số liên kết 33 Cấp phát vùng nhớ chứa tập tin „ Các khối (block) đĩa sẽ được cấp phát để lưu trữ nội dung tập tin theo các cơ chế cấp phát: „ Cấp phát liên tục „ Cấp phát bằng danh sách liên kết „ Cấp phát bằng danh sách liên kết sử dụng chỉ mục (index). „ Cấp phát bằng I-node 34 Cấp phát liên tục „ Cấp phát 1 số block liên tục trên đĩa để lưu trữ nội dung tập tin „ Nhận xét: „ Đơn giản: chỉ cần quản lý số hiệu khối bắt đầu và tổng số block chiếm bởi tập tin. „ Truy cập nội dung tập tin nhanh chóng vì các block nằm kề nhau. „ Gây lãng phí bộ nhớ. „ Khó khăn khi tập tin mở rộng kích thước. 35 Cấp phát liên tục (tt) 36 Cấp phát bằng danh sách liên kết „ Nội dung tập tin được lưu trữ ở những block không cần liên tục. Các block này được xâu chuỗi tạo thành 1 danh sách liên kết để quản lý. „ Nhận xét: „ Đơn giản: Chỉ cần quản lý block bắt đầu. „ Tận dụng hiệu quả không gian đĩa. „ Truy cập tập tin lâu hơn vì đầu đọc phải di chuyển nhiều giữa các khối không liên tiếp. „ Khối dữ liệu bị thu hẹp lại vì mỗi khối phải dùng 1 phần để lưu phần liên kết đến khối kế tiếp. 37 Cấp phát bằng danh sách liên kết (tt) 38 Cấp phát bằng danh sách liên kết sử dụng chỉ mục (index) „ Tương tự như phương pháp cấp phát bằng danh sách liên kết nhưng thay vì sử dụng 1 phần nhỏ của mỗi block để lưu chuỗi liên kết thì sử dụng 1 block riêng để lưu toàn bộ chuỗi liên kết. „ Æ Các block chỉ chứa dữ liệu. 39 Cấp phát bằng danh sách liên kết sử dụng chỉ mục (index) (tt) 40 Cấp phát bằng I-node „ Mỗi I-node gồm 2 phần: „ Các thuộc tính của tập tin „ Địa chỉ của các khối dữ liệu: gồm 13 phần tử „ 10 phần tử đầu tiên: Địa chỉ của các khối dữ liệu trực tiếp. „ Phần tử thứ 11: Địa chỉ của các khối dữ liệu gián tiếp đơn (single indirect): gồm 1 khối trỏ đến 210 phần tử chứa địa chỉ của các khối dữ liệu. „ Phần tử thứ 12: Địa chỉ của các khối dữ liệu gián tiếp đôi (double indirect): chứa địa chỉ của các khối single indirect. „ Phần tử thứ 13: Địa chỉ của các khối dữ liệu gián tiếp ba (triple indirect) 41 Cấp phát bằng I-node (tt) 42 Cài đặt hệ thống tập tin của các HĐH cụ thể „ MS-DOS „ Windows „ Unix 43 Tổ chức quản lý hệ thống tập tin trên đĩa từ 0 1 2 3 .. Đĩa từ bao gồm danh sách các sector có kích thước 512Bytes Kích thước đĩa (bytes) = (tổng số sector) x (512 bytes/sector) 44 Phân vùng đĩa (Disk Partition) „ Toàn bộ vùng lưu trữ của đĩa được phân thành các vùng logic không chồng lên nhau gọi là phân vùng đĩa. Partition #1 Partition #2 Partition #3 unused 45 Master Boot Record „ Một phần nhỏ đầu tiên của đĩa được dành riêng cho các thông tin quản lý đĩa. „ Sector logic thứ 0 của đĩa (CHS = 001) là Master Boot Record chứa thông tin mô tả cấu trúc vật lý của đĩa và thông tin về các phân vùng logic của đĩa. MBR 0 1 2 partition #1 46 MBR „ Thông tin chứa trong MBR bao gồm: „ Đoạn chương trình để giúp khởi động hệ thống „ Bảng mô tả thông tin các phân vùng logic „ Thông tin nhận diện MBR signature (2 bytes) Partition Table (64 bytes) Bootstrap Loader (446 bytes)512 bytes 47 Bảng mô tả các phân vùng „ MBR có thể mô tả cho tối đa 4 phân vùng logic được chia trên đĩa trong đó thường có 1 phân vùng ở trạng thái “Active” Starting sector ID-number Partition length (in sectors) S T A T U S T Y P E16 bytes Some fields contain ‘obsolete’ information 48 Primary Partition vs Extended Partition Reserved Reserved Reserved Reserved Reserved Reserved Reserved MBR Reserved Reserved Reserved Reserved Reserved Reserved Reserved Partition Table Primary Partition Extended Partition 49 „ Phân vùng “active” là phân vùng chứa HĐH sẽ được nạp mặc định khi máy tính khởi động. Bảng mô tả các phân vùng (tt) 50 Trường TYPE-ID trong bảng mô tả phân vùng „ Ý nghĩa của trường Type-ID trong mỗi phân vùng „ TYPE-ID = 0x07 : Phân vùng chứa “Windows” „ TYPE-ID = 0x83 : Phân vùng chứa “Linux” „ TYPE-ID = 0x00 : Phân vùng không sử dụng. 51 Quá trình khởi động hệ thống và nạp HĐH dựa trên thông tin các phân vùng „ B1: POST (Power-On Self-Test) „ B2: Tải MBR để đọc thông tin bảng phân vùng. „ B3: Tìm phân vùng “active”. „ B4: Chuyển quyền điều khiển về cho đoạn mã chương trình nằm trong Boot Record của phân vùng “active” „ B5: Tải HĐH tại phân vùng “active”. 52 Tổ chức tập tin trên Windows: FAT (12,16,32) 53 Tổ chức tập tin trên Windows: FAT (12,16,32) (tt) „ FAT: File Allocation Table „ Các phiên bản của FAT: FAT12, FAT16, FAT32 „ 12,16,32: Số bít dùng để đánh STT các khối (212,216,232) „ FAT12: 212 (khối) x 512 bytes/khối = 2MB „ FAT16: 216 (khối) x 512 bytes/khối = 32MB „ FAT32: 232 (khối) x 512 bytes/khối = 4GB Boot sector FAT1 FAT2 (backup) Root directory Other directories and files 0000 0003 0004 FFFF 0006 0008 FFFF FFFF 0000 empty File1 File1empty File2File1 File3File2 emptyFile2 empty empty emptyempty empty empty empty empty 0000 0001 0002 0003 0004 0005 0006 0007 0008 0009 0000 0001 0002 0003 0004 0005 0006 0007 0008 0009 0010 0011 0012 0013 0014 0015 0016 0017 54 Tổ chức tập tin trên Windows: NTFS „ Nhóm các sector liên tiếp nhau lại để tạo thành các Cluster. 55 Tổ chức tập tin trên Windows: NTFS „ NTFS không sử dụng khái niệm FAT và Root Dir để quản lý các tập tin lưu trên đĩa mà sử dụng khái nhiệm MFT (Master File Table). „ MFT là 1 Metadata file bao gồm 1 danh sách các trường chứa thông tin về mỗi tập tin lưu trữ trên đĩa. „ Thông tin trong MFT có thể giúp thiết lập các thuộc tính bảo vệ, phục hồi, tìm kiếm, thiết lập quota cho từng tập tin, thư mục trên đĩa. 56 Tổ chức tập tin trên Unix/Linux: I-node mode owner Direct block 0 Direct block 1 Direct block 10 Direct block 11 Single indirect Double indirect Triple indirect Data block Data block Data block Data block index Data block Data block Data block Data block index index indexindex indexindex Data block Data block Data block Data block index index Data block I-node Data block 10/20/2007 Trần Hạnh Nhi 1 Chöông 4: Quaûn lyù tieán trình „ Moâ hình Tieán trình „ Traïng thaùi tieán trình „ Thoâng tin quaûn lyù tieán trình „Quaù trình ñieàu phoái tieán trình „Caùc thuaät toaùn ñieàu phoái 10/20/2007 Trần Hạnh Nhi 2 Khaùi nieäm : Ña nhieäm vaø ña chöông ??? „ Vì sao muoán xöû lyù ñoàng thôøi nhieàu coâng vieäc treân maùy tính ? IO CPU IOCPU Job 1 CPU Job 1 CPU IO IO CPU IO CPU Job 2 CPU CPU Æ Xöû lyù ñoàng thôøi ñeå taêng hieäu suaát söû duïng CPU 10/20/2007 Trần Hạnh Nhi 3 „ Vì sao muoán xöû lyù ñoàng thôøi nhieàu coâng vieäc treân maùy tính ? Æ Xöû lyù ñoàng thôøi ñeå taêng toác ñoä xöû lyù Khaùi nieäm : Ña nhieäm vaø ña chöông ??? „ Job : kq = a*b + c*d; CPU #1 CPU #1 CPU #2 x = a * b y = c * d kq = x+y x = a * b 1 y = c *d 2 kq = x+y 3 Xöù lyù tuaàn töï Xöûù lyù ñoàng haønh 10/20/2007 Trần Hạnh Nhi 4 Ña nhieäm vaø ña chöông „ Multitasking (ña nhieäm) : cho pheùp nhieàu taùc vuï/ coâng vieäc ñöôïc xöû lyù ñoàng thôøi „ Ngöôøi duøng luoân mong muoán 1 HÑH ña nhieäm „ Nhöng: Maùy tính thöôøng chæ coù 1 CPU? „ Multiprogramming (ña chöông) : kyõ thuaät cho pheùp nhieàu chöông trình ñöôïc thöïc hieän ñoàng thôøi (treân 1 CPU) „ Giaû laäp nhieàu CPU aûo töø 1 CPU thaät ñeå cho pheùp thi haønh nhieàu chöông trình ñoàng thôøi. „ AÛo hoaù baèng caùch naøo ? Xaây döïng caùc thuaät toaùn ñeå luaân chuyeån CPU giöõa caùc chöông trình öùng duïng. 10/20/2007 Trần Hạnh Nhi 5 Xöû lyù ñoàng haønh, nhöõng khoù khaên ? HÑH : “ Giaûi quyeát nhieàu coâng vieäc ñoàng thôøi, ñaâu coù deã ! “ - Taøi nguyeân giôùi haïn, öùng duïng “voâ haïn” - Nhieàu hoaït ñoäng ñan xen ??? Phaân chia taøi nguyeân ? ??? Chia seû taøi nguyeân ? ??? Baûo veä? Excel Visual C++ CDplayer Winword 10/20/2007 Trần Hạnh Nhi 6 Giaûi phaùp HÑH : “ Ai cuõng coù phaàn khi ñeán löôït maø ! ” -“Chia ñeå trò”, coâ laäp caùc hoaït ñoäng. - Moãi thôøi ñieåm chæ giaûi quyeát 1 yeâu caàu. - Aûo hoaù taøi nguyeân : bieán ít thaønh nhieàu Winword CDPlayer Visual C ++ Excel 10/20/2007 Trần Hạnh Nhi 7 Giaûi phaùp CPU 10/20/2007 Trần Hạnh Nhi 8 Khaùi nieäm tieán trình (Process) „ Tieán trình laø moät chöông trình ñang trong quaù trình thöïc hieän „ Moãi tieán trình sôû höõu „ Moät CPU (aûo) rieâng „ Moät khoâng gian nhôù rieâng „ Chieám giöõ 1 soá taøi nguyeân cuûa heä thoáng „ Vd: Moät chöông trình Word coù theå ñöôïc chaïy 2 laàn seõ taïo ra 2 tieán trình khaùc nhau: „ Microsoft Word – [Bai tap1.doc] „ Microsoft Word – [Bai tap2.doc] 10/20/2007 Trần Hạnh Nhi 9 Hai phaàn cuûa tieán trình int a; int a; P1 P2 Doøng xöû lyù Khoâng gian ñòa chæ 10/20/2007 Trần Hạnh Nhi 10 Traïng thaùi tieán trình ? „ Taïi 1 thôøi ñieåm, tieán trình ôû moät trong caùc traïng thaùi sau: ready ☺ Rs / CPU running ☺ Rs ☺ CPU blocked / Rs / CPU Nhaän CPU Traû CPU Chôø R Nhaän R 10/20/2007 Trần Hạnh Nhi 11 Khoái quaûn lyù tieán trình - PCB (Process Control Block) „ Định danh (Process ID) „ Trạng thaùi tiến trình „ Ngữ cảnh tiến trình „ Trạng thaùi CPU „ Bộ xử lyù (cho maùy nhiều CPU) „ Bộ nhớ chính „ Taøi nguyeân sử dụng/tạo lập „ Thoâng tin giao tiếp „ Tiến trình cha, tiến trình con „ Độ ưu tieâên „ Thoâng tin thống keâ pid State (State, details) Context (IP, Mem, Files) Scheduling statistic Relatives ( Dad, children) Process control Block PCB 10/20/2007 Trần Hạnh Nhi 12 Ví duï: Khoái quaûn lyù tieán trình cuûa HÑH MachOS „ typedef struct machpcb { „ char mpcb_frame[REGOFF]; „ struct regs mpcb_regs; // user's saved registers „ struct rwindow mpcb_wbuf[MAXWIN]; //user window save buffer „ char *mpcb_spbuf[MAXWIN]; //sp's for each wbuf „ int mpcb_wbcnt; //number of saved windows in pcb_wbuf „ struct v9_fpu *mpcb_fpu; // fpu state „ struct fq mpcb_fpu_q[MAXFPQ]; // fpu exception queue „ int mpcb_flags; // various state flags „ int mpcb_wocnt; // window overflow count „ int mpcb_wucnt; // window underflow count „ kthread_t *mpcb_thread; // associated thread „ } machpcb_t; 10/20/2007 Trần Hạnh Nhi 13 Caùc thao taùc treân tieán trình „ Taïo laäp tieán trình „ Keát thuùc tieán trình „ Thay ñoåi traïng thaùi tieán trình : „ Assign() „ Block() „ Awake() „ Suspend() „ Resume() 10/20/2007 Trần Hạnh Nhi 14 Taïo laäp tieán trình „ Caùc tình huoáng : „ Khôûi ñoäng batch job „ User logs on „ Kích hoaït 1 service (print...) „ Process goïi haøm taïo moät tieán trình khaùc „ Caùc tieán trình coù theå taïo tieán trình con, hình thaønh caây tieán trình trong heä thoáng „ Caùc tieán trình môùi ñöôïc taïo coù theå thöøa höôûng taøi nguyeân töø cha, hay ñöôïc caáp taøi nguyeân môùi 10/20/2007 Trần Hạnh Nhi 15 Keát thuùc tieán trình „ Tình huoáng : „ Tieán trình xöû lyù xong leänh cuoái cuøng hay goïi exit () „ Keát thuùc Batch job , Halt instruction „ User logs off „ Do loãi chöông trình „ Moät tieán trình coù theå keát thuùc 1 tieán trình khaùc neáu coù ID (ñònh danh) cuûa tieán trình kia. „ Ví duï: kill –-s SIGKILL 1234: huyû tieán trình coù ID laø 1234 10/20/2007 Trần Hạnh Nhi 16 Moâ hình ña tieán trình (MultiProcesses) „ Heä thoáng laø moät taäp caùc tieán trình hoaït ñoäng ñoàng thôøi „ Caùc tieán trình ñoäc laäp vôùi nhau => khoâng coù söï trao ñoåi thoâng tin hieån nhieân.. winword Visual C CDplayer Excel OS 10/20/2007 Trần Hạnh Nhi 17 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áyrieâ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 18 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) „ Khaùi nieäm môùi : tieåu trình (thread) alta vista 10/20/2007 Trần Hạnh Nhi 19 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 20 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 : „ 1 khoâng gian ñòa chæ „ 1 hoaëc nhieàu tieåu trình „ 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 ? ). P1 int a; T1 T2 T 3 10/20/2007 Trần Hạnh Nhi 21 Tieåu trình haït nhaân (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, Linux T1 T2 Kernel Thread System call User mode Kernel mode 10/20/2007 Trần Hạnh Nhi 22 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 CPU 10/20/2007 Trần Hạnh Nhi 23 Caùc danh saùch tieán trình Ready List P1 P4 P5 Waiting Lists R1 P7P2 P10P3 P6 R2 R3 10/20/2007 Trần Hạnh Nhi 24 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 P1 P4 P5 10/20/2007 Trần Hạnh Nhi 25 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 26 10/20/2007 Trần Hạnh Nhi 27 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 28 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 29 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 30 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 31 Hai nguyeân taéc ñieàu phoái CPU Khoâng ñoäc quyeàn while (true) { interrupt Pcur save state Pcur Scheduler.NextP() Æ Pnext load state pnext resume Pnext } Ñoäc quyeàn while (true) { save state Pcur Scheduler.NextP() Æ Pnext load state pnext resume Pnext wait for Pnext } 10/20/2007 Trần Hạnh Nhi 32 Ñ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 33 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 34 FCFS (First comes first served) „ Tieán trình vaøo RL laâu nhaát ñöôïc choïn tröôùc „ Theo thứ tự vaøo RL „ Độc quyềnABC CPU Ready List CPUBC Ready List CPUC Ready List 10/20/2007 Trần Hạnh Nhi 35 Minh hoïa FCFS 32P3 31P2 240P1 CPU burstTarriveRLP 0:00 P1 vào RL P1 dùng CPU 0:01 P2 vào RL 0:02 P3 vào RL 0:24 P1 kết thúc P2 dùng CPU AvgWT = (23+25)/3 = 16 0:27 P2 kết thúc P3 dùng CPU 27-230-2P3 24-127-1P2 024P1 WTTTP P1 P2 P3 0 24 27 10/20/2007 Trần Hạnh Nhi 36 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 37 Ñieàu phoái Round Robin (RR) ABC CPU Ready List A chỉ chiếm CPU trong q ms BCA CPU Ready List B được giao quyền sử dụng CPU trong q ms kế tiếp CAB CPU Ready List C được giao quyền sử dụng CPU trong q ms kế tiếp ƒ Ñ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 Quantum/ Time slice 10/20/2007 Trần Hạnh Nhi 38 Minh hoïa RR, q=4 32P3 31P2 240P1 CPU burstTarriveRLP AvgWT = (6+3+5)/3 = 4.66 7-210-2P3 4-17-1P2 0+(10-4)30P1 WTTTP P1 P2 P3 P1 P1 P1 P1 P1 0 4 7 10 14 18 22 26 30 0:00 P1 vào, P1 dùng CPU 0:01 P2 vào (đợi) 0:02 P3 vào (đợi) 0:04 P1 hết lượt, P2 dùng CPU 0:07 P2 dừng, P3 dùng CPU 0:10 P3 dừng, P1 dùng CPU 0:14 P1 vẫn chiếm CPU 10/20/2007 Trần Hạnh Nhi 39 Minh hoïa RR, q=4 312P3 34P2 240P1 CPU burstTarriveRLP P1 P1 P2 P1 P3 P1 P1 P1 0 4 8 11 15 18 22 26 30 RL 0:00 P1 0:04 0:8 P2 P1 ? ƒ 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... 0:11 P1 0:15 P3 P1 0:18 P1 0:04 P1 P2 0:04 P2 P1 “Chung thuûy” “Coù môùi nôùi cuõ” 10/20/2007 Trần Hạnh Nhi 40 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 41 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ỏ ??? „ Tröôøng hôïp xaáu nhaát cuûa RR ? Bao laâu ? Giaûm tíùnh töông taùc Taêng chi phí chuyeån ñoåi ngöõ caûnh 10/20/2007 Trần Hạnh Nhi 42 Ñ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 độ ưu tiên: cao (-3) Outlook độ ưu tiên: thấp (3) WinWord độ ưu tiên: trung bình (0) Đ ộ ưu tiên ƒ 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 43 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 44 Bieåu ñoà phaân boá ñoä öu tieân cuûa WinNT 24 realtime 13 high 8 normal system idle dynamic idle dynamic time-critical realtime idle realtime time-critical 0 1 15 dynamic levels 1-15 16 31 realtime levels 16-31 lowest (-2) below normal (-1) normal (0) above normal (+1) highest (+2) 4 idle 10/20/2007 Trần Hạnh Nhi 45 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 46 Minh hoïa ñoä öu tieân (khoângñoäc quyeàn) 1 0 2 Priority 32P3 31P2 240P1 CPU burstTRLP AvgWT = (6+0+2)/3 = 2.66 4-27-2P3 04-1P2 0+(7-1)30P1 WTTTP 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:4 P2 kết thúc, P3 dùng CPU 0:7 P3 dừng, P1 dùng CPU 0:30 P1 dừng P1 P3 P1 0 30 P2 41 7 P2 2 0:02 P3 vào (độ ưu tiên thấp hơn P2) P3 không dành được quyền dùng CPU 10/20/2007 Trần Hạnh Nhi 47 Nhaän xeùt „ Caùch tính ñoä öu tieân ? „ Heä thoáng gaùn : CPU times „ 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 ? „ Chôø laâu, laâu, laâu ... starvation Aging : taêng ñoä öu tieân cho nhöõng tieán trình chôø laâu trong heä thoáng 10/20/2007 Trần Hạnh Nhi 48 Shortest Job First (SJF) P3 (cần 7 chu kỳ) P1 (cần 5 chu kỳ) P2 (cần 3 chu kỳ) Ngắn nhất Ready List CPU pi = thời_gian_còn_lại(Processi) Là một dạng độ ưu tiên đặc biệt với độ ưu tiên Î Có thể cài đặt độc quyền hoặc không độc quyền 10/20/2007 Trần Hạnh Nhi 49 Minh hoïa SJF (ñoäc quyeàn)(1) 32P3 31P2 240P1 CPU burstTarriveRLP AvgWT = (23+25)/3 = 16 27-230P3 24-127P2 024P1 WTTTP 0:00 P1 vào, P1 dùng CPU 0:01 P2 vào RL 0:02 P3 vào RL 0:24 P1 kết thúc, P2 dùng CPU 0:27 P2 dừng, P3 dùng CPU 0:30 P3 dừng P1 P2 P3 0 24 27 30 10/20/2007 Trần Hạnh Nhi 50 Minh hoïa SJF (ñoäc quyeàn)(2) 21P3 31P2 240P1 CPU burstTarriveRLP AvgWT = (24+22)/3 = 15.33 24-226P3 26-129P2 024P1 WTTTP 0:00 P1 vào, P1 dùng CPU 0:01 P2 vào 0:01 P3 vào 0:24 P1 kết thúc, P3 dùng CPU 0:26 P3 dừng, P2 dùng CPU 0:29 P2 dừng P1 P3 P2 0 24 26 29 10/20/2007 Trần Hạnh Nhi 51 Minh hoïa SJF (khoângñoäc quyeàn) (1) 32P3 31P2 240P1 CPU burstTarriveRLP AvgWT = (6+0+2)/3 = 2.66 4-27-2P3 04-1P2 0+(7-1)30P1 WTTTP 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:4 P2 kết thúc, P3 dùng CPU 0:7 P3 dừng, P1 dùng CPU 0:30 P1 dừng P1 P3 P1 0 30 P2 41 7 10/20/2007 Trần Hạnh Nhi 52 Minh hoïa SJF (khoângñoäc quyeàn) (2) 43P3 51P2 240P1 CPU burstTarriveRLP AvgWT = (9+0+3)/3 = 4 6-310P3 06P2 0+(10-1)33P1 WTTTP 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:6 P2 kết thúc, P3 dùng CPU 0:9 P3 dừng, P1 dùng CPU 0:33 P1 dừng P1 P3 P1 0 33 P2 61 10 P2 3 0:03 P3 vào (độ ưu tiên < P2) P2 dành quyền dùng CPU 10/20/2007 Trần Hạnh Nhi 53 Minh hoïa SJF (nhieàu chu kyø CPU) 0 4 2 IO2 T 1 10 2 IO1 T Null R1 R2 IO2 R 8 1 5 CPU1 burst R2 R1 R1 IO1 R 010P3 12P2 20P1 CPU2 burst TarriveRLP P1 P3 0 21 P2 62 10 P1 3 CPU P1 P2 13 1913 15 P2 3 R1 P1 P3 221917 21 R2 P2 14 P3 15 P1 17 P3 10/20/2007 Trần Hạnh Nhi 54 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 ? AvgWT = (3a+2b+c) Min AvgWT ? a<b<c P1 a P2 b P3 c past historyrelative weightmost recent information ( ) nnn t ταατ −+=+ 1 1 length of the nth CPU burst predicted value for the nth CPU burst0<= α <=1 10/20/2007 Trần Hạnh Nhi 55 Ñieàu phoái vôùi nhieàu möùc öu tieân „ Toå chöùc N RL öùng vôùi nhieàu möùc öu tieân „ Moãi RLi aùp duïng moät chieán löôïc ñieàu phoái thích hôïp „ Giöõa caùc RL aùp duïng ñieàu phoái theo ñoä öu tieân : „ RLi roãng môùi ñieàu phoái RLi +1 Độ ưu tiên 1 2 n C P U Kết hợp nhiều chiến lược 10/20/2007 Trần Hạnh Nhi 56 Ñieàu phoái vôùi nhieàu möùc öu tieân – Thöïc teá „ Toå chöùc N RL öùng vôùi nhieàu möùc öu tieân „ Moãi RLi aùp duïng RR „ Giöõa caùc RL aùp duïng ñieàu phoái theo ñoä öu tieân : „ RLi roãng môùi ñieàu phoái RLi +1 Độ ưu tiên 1 2 n C P U Kết hợp nhiều chiến lược 10/20/2007 Trần Hạnh Nhi 57 Khuyeát ñieåm „ Starvation !!! „ Giaûi phaùp Aging : „ Chôø laâu quaù : chuyeån leân RL vôùi ñoä öu tieân cao hôn „ Chieám CPU laâu quaù : chuyeån xuoáng RL vôùi ñoä öu tieân thaáp hôn / /2 / ☺ ☺1 ☺ CPU Chờ lâu quá Khi naøo thöïc hieän aging ? Aging tieán trình naøo ? 10/20/2007 Trần Hạnh Nhi 58 Null00R220311P4 R232R15610P3 R152R2812P2 Null01R1580P1 Thieát bò Thôøi gian Thieát bò Thôøi gian IO laàn 2 CPU2 IO laàn 1 CPU1 Thôøi ñieåm vaøo Ready list Tieán trình Bài tập: Hãy điều phối CPU: SJF không độc quyền. R1,R2: FIFO 11/10/2007 Trần Hạnh Nhi 1 Chöông 5 Ñoàng boä hoaù tieán trình 11/10/2007 Trần Hạnh Nhi 2 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 3 Nhieàu tieán trình “chung soáng hoaø bình” trong heä thoáng ? „ ÑÖØNG HY VOÏNG „ An toaøn khi caùc tieán trình hoaøn toaøn ñoäc laäp „ Laøm sao coù ñöôïc ?? „ Thöïc teá „ Caùc tieán trình chia seû taøi nguyeân chung ( file system, CPU...) „ Concurrent access => bugs. „ Ví duï : Deâ con qua caàu „ Xöû lyù ñoàng haønh = ...nhöùc ñaàu 11/10/2007 Trần Hạnh Nhi 4 Caùc vaán ñeà „ Tranh chaáp „ Nhieàu tieán trình truy xuaát ñoàng thôøi moät taøi nguyeân mang baûn chaát khoâng chia seû ñöôïc Æ Xaûy ra vaán ñeà tranh ñoaït ñieàu khieån (Race Condition) „ Keát quaû ? „ Khoù bieát , thöôøng laø ...sai „ Luoân luoân nguy hieåm ? „ ...Khoâng, nhöng ñuû ñeå caân nhaéc kyõ caøng „ Phoái hôïp „ Caùc tieán trình khoâng bieát töông quan xöû lyù cuûa nhau ñeå ñieàu chænh hoaït ñoäng nhòp nhaøng ÆCaàn phoái hôïp xöû lyù (Rendez-vous) „ Keát quaû : khoù bieát, khoâng baûo ñaûm aên khôùp 11/10/2007 Trần Hạnh Nhi 5 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 6 Tranh ñoaït ñieàu khieån (Race condition) - Ví duï hits = hits +1; hits = hits + 1; P1 P2 hits = 0 Keát quaû cuoái cuøng laø bao nhieâu ? ƒ Ñeám soá ngöôøi vaøo Altavista : duøng 2 threads caäp nhaät bieán ñeám hits=> P1 vaø P2 chia seû bieán hits 11/10/2007 Trần Hạnh Nhi 7 Tranh ñoaït ñieàu khieån (Race condition) - Ví duï (4)hits = 0 + 1 (1) read hits (0) (3) hits = 0 + 1 (2)read hits (0) P1 P2 hits = 1 hits = 0 time 11/10/2007 Trần Hạnh Nhi 8 Tranh ñoaït ñieàu khieån (Race condition) - Ví duï (4) hits = 1 + 1 (1) read hits (0) (2) hits = 0 + 1 (3) read hits (1) P1 P2 hits = 2 hits = 0 time 11/10/2007 Trần Hạnh Nhi 9 „ Ai thaéng ? „ Coù baûo ñaûm raèng seõ coù ngöôøi thaéng ? „ Neáu moãi tieán trình xöû lyù treân 1 CPU thì sao ? Tranh ñoaït ñieàu khieån (Race condition) - Ví duï (tt) Thread b: while(i > -10) i = i - 1; print “B won!”; Thread a: while(i < 10) i = i +1; print “A won!”; i=0; 11/10/2007 Trần Hạnh Nhi 10 Tranh ñoaït ñieàu khieån (Race condition)-Nhaän xeùt ƒ Keát quaû thöïc hieän tieán trình phuï thuoäc vaøo keát quaû ñieàu phoái ƒ Cuøng input, khoâng chaéc cuøng output ƒ Khoù debug loãi sai trong xöû lyù ñoàng haønh ƒ Xöû lyù ƒ Laøm lô ƒ Deã , nhöng coù phaûi laø giaûi phaùp ƒ Khoâng chia seû taøi nguyeân chung : duøng 2 bieán hits1,hits2; xaây caàu 2 lane... ƒ Neân duøng khi coù theå, nhöng khoâng bao giôø coù theå ñaûm baûo ñuû taøi nguyeân, vaø cuõng khoâng laø giaûi phaùp ñuùng cho moïi tröôøng hôïp ƒ Giaûi phaùp toång quaùt : coù hay khoâng ? ƒ Lyù do xaûy ra Race condition ? Æ Bad interleavings : moät tieán trình “xen vaøo” quaù trình truy xuaát taøi nguyeân cuûa moät tieán trình khaùc ƒ Giaûi phaùp : baûo ñaûm tính atomicity cho pheùp tieán trình hoaøn taát troïn veïn quaù trình truy xuaát taøi nguyeân chung tröôùc khi coù tieán trình khaùc can thieäp 11/10/2007 Trần Hạnh Nhi 11 Atomicity : loaïi boû Race Condition read hits(1) hits = 1 + 1 P1 P2 hits = 2 hits = 0 time read hits (0) hits = 0 + 1 11/10/2007 Trần Hạnh Nhi 12 Mieàn gaêng (Critical Section) & Khaû naêng ñoäc quyeàn (Mutual Exclusion) hits = hits + 1 printf(“Welcome”); hits = hits + 1 printf(“Welcome”); P1 P2 CSCS ƒ Mieàn gaêng (CS) laø ñoaïn chöông trình coù khaû naêng gaây ra hieän töôïng race condition (Hoã trôï Atomicity : Caàn baûo ñaûm tính “ñoäc quyeàn truy xuaát” (Mutual Exclusion) cho mieàn gaêng (CS) printf(“Bye”); printf(“Bye”); 11/10/2007 Trần Hạnh Nhi 13 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 14 Phoái hôïp hoaït ñoäng (1) Send(“Anh”); P1 (2) Send(“yeâu”); P2 (3) Send(“em”); P3 (4) Send(“Khoâng”); P4 Chuyeän gì ñaõ xaûy ra ? (1) Send(“Anh”); P1 (2) Send(“yeâu”); P2 (3) printf(“em”); P3 (4) Send(“Khoâng”); P4 (1)Send(“Anh”); P1 (2) Send(“yeâu”); P2 (3) Send(“em”); P3 (4) Send(“Khoâng”); P4 11/10/2007 Trần Hạnh Nhi 16 Phoái hôïp xöû lyù ƒ Laøm theá naøo baûo ñaûm trình töï thöïc hieän Job1 - Job2 ? ƒ P1 vaø P2 thöïc hieän “heïn hoø” (Rendez-vous) vôùi nhau ƒ Hoã trôï Rendez-vous : Baûo ñaûm caùc tieán trình phoái hôïp vôùi nhau theo 1 trình töï xöû lyù ñònh tröôùc. P1 P2 Job1; Job2; 11/10/2007 Trần Hạnh Nhi 17 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 18 Baøi toaùn ñoàng boä hoaù (Synchronization) „ Nhieàu tieán trình chia seû taøi nguyeân chung ñoàng thôøi : „ Tranh chaápÖRace Condition Æ Nhu caàu “ñoäc quyeàn truy xuaát” (Mutual Exclusion) „ Caùc tieán trình phoái hôïp hoaït ñoäng : „ Töông quan dieãn tieán xöû lyù ? Æ Nhu caàu “hoø heïn” (Rendez-vous) „ Thöïc hieän ñoàng boä hoaù : „ Laäp trình vieân ñeà xuaát chieán löôïc „ Caùc tieán trình lieân quan trong baøi toaùn phaûi toân troïng caùc luaätñoàng boä „ Giaûi phaùp söû duïng caùc cô cheá ñoàng boä : „ Do laäp trình vieân /phaàn cöùng / HÑH / NNLT cung caáp 11/10/2007 Trần Hạnh Nhi 19 Moâ hình ñaûm baûo Mutual Exclusion Kieåm tra vaø daønh quyeàn vaøo CS CS; Töø boû quyeàn söû duïng CS ƒ Nhieäm vuï cuûa laäp trình vieân: ƒ Theâm caùc ñoaïn code ñoàng boä hoùa vaøo chöông trình goác ƒ Theâm theá naøo : xem moâ hình sau ... 11/10/2007 Trần Hạnh Nhi 20 Moâ hình toå chöùc phoái hôïp giöõa hai tieán trình P1 P2 Job1; Chôø ; Baùo hieäu ; Job2; ƒ Nhieäm vuï cuûa laäp trình vieân: ƒ Theâm caùc ñoaïn code ñoàng boä hoùa vaøo 2 chöông trình goác ƒ Theâm theá naøo : xem moâ hình sau ... ƒ Nhieàu tieán trình hôn thì sao ? ƒ Khoâng coù moâ hình toång quaùt ƒ Tuøy thuoäc baïn muoán heïn hoø ra sao☺ 11/10/2007 Trần Hạnh Nhi 21 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 wating „ 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 22 Giaûi phaùp ñoàng boä hoaù Moät phöông phaùp giaûi quyeát toát baøi toaùn ñoàng boä hoaù caàn thoaû maûn 4 ñieàu kieän sau: „ Mutual Exclusion : Khoâng coù hai tieán trình cuøng ôû trong mieàn gaêng cuøng luùc. „ Progess : Moät tieán trình taïm döøng beân ngoaøi mieàn gaêng khoâng ñöôïc ngaên caûn caùc tieán trình khaùc vaøo mieàn gaêng „ BoundedWaiting : Khoâng coù tieán trình naøo phaûi chôø voâ haïn ñeå ñöôïc vaøo mieàn gaêng. „ Khoâng coù giaû thieát naøo ñaët ra cho söï lieân heä veà toác ñoä cuûa caùc tieán trình, cuõng nhö veà soá löôïng boä xöû lyù trong heä thoáng. 11/10/2007 Trần Hạnh Nhi 23 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 24 Caùc giaûi phaùp “Busy waiting” While (chöa coù quyeàn) donothing() ; CS; Töø boû quyeàn söû duïng CS ƒ Tieáp tuïc tieâu thuï CPU trong khi chôø ñôïi vaøo mieàn gaêng ƒ Khoâng ñoøi hoûi söï trôï giuùp cuûa Heä ñieàu haønh 11/10/2007 Trần Hạnh Nhi 25 Nhoùm giaûi phaùp Busy-Waiting „ 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 „ Phaàn cöùng „ Caám ngaét „ Chæ thò TSL 11/10/2007 Trần Hạnh Nhi 26 while (lock == 1); // wait lock = 1; CS; lock = 0; int lock = 0 NonCS; NonCS; P0 while (lock == 1); // wait lock = 1; CS; lock = 0; NonCS; NonCS; P1 Giaûi phaùp phaàn meàm 1: Söû duïng bieán côø hieäu 11/10/2007 Trần Hạnh Nhi 27 while (lock == 1); // wait lock = 1; CS; lock = 0; int lock = 0 NonCS; NonCS; P0 while (lock == 1); // wait lock = 1; CS; lock = 0; NonCS; NonCS; P1 Giaûi phaùp phaàn meàm 1: Tình huoáng 11/10/2007 Trần Hạnh Nhi 28 Nhaän xeùt Giaûi phaùp phaàn meàm 1: Bieán côø hieäu „ Coù theå môû roäng cho N tieán trình „ Khoâng baûo ñaûm Mutual Exclusion „ Nguyeân nhaân ? „ Baûn thaân ñoaïn code kieåm tra vaø daønh quyeàn cuõng laø CS ! while ( lock == 1); // wait lock = 1;Bò ngaét xöû lyù Taøi nguyeân duøng chung CS ! 11/10/2007 Trần Hạnh Nhi 29 Giaûi phaùp phaàn meàm 2 : Kieåm tra luaân phieân while (turn !=0); // wait CS; turn = 1; int turn = 1 NonCS; NonCS; P0 while (turn != 1); // wait CS; turn = 0; NonCS; NonCS; P1 11/10/2007 Trần Hạnh Nhi 30 Giaûi phaùp phaàn meàm 2 : Tình huoáng int turn = 1 turn ==1 Wait... CS; turn = 1 NonCS; CS ? (turn ==1) P0 CS; turn = 0; NonCS... P1 P0 khoâng vaøo ñöôïc CS laàn 2 khi P1 döøng trong NonCS ! 11/10/2007 Trần Hạnh Nhi 31 Nhaän xeùt Giaûi phaùp 2: Kieåm tra luaân phieân „ Chæ daønh cho 2 tieán trình „ Baûo ñaûm Mutual Exclusion „ Chæ coù 1 bieán turn, taïi 1 thôøi ñieåm chæ cho 1 tieán trình turn vaøo CS „ Khoâng baûo ñaûm Progress „ Nguyeân nhaân ? „ “Môø cuûa” cho ngöôøi = “Ñoùng cöûa” chính mình ! 11/10/2007 Trần Hạnh Nhi 32 „ Keát hôïp yù töôûng cuûa 1 & 2, caùc tieán trình chia seû: „ int turn; //ñeán phieân ai „ int interest[2] = FALSE; //interest[i] = T : Pi muoán vaøo CS Giaûi phaùp phaàn meàm 3 : Peterson’s Solution j = 1 – i; interest[i] = TRUE; turn = j; while (turn==j && interest[j]==TRUE); CS; interest[i] = FALSE; NonCS; NonCS; Pi 11/10/2007 Trần Hạnh Nhi 33 Giaûi phaùp phaàn meàm 3 : Peterson i = 1 – j; interest[j] = TRUE; turn = i; while (turn==i && interest[i]==TRUE); CS; interest[j] = FALSE; NonCS; NonCS; Pj 11/10/2007 Trần Hạnh Nhi 34 „ Laø giaûi phaùp phaàn meàm ñaùp öùng ñöôïc caû 3 ñieàu kieän „ Mutual Exclusion : „ Pi chæ coù theå vaøo CS khi: interest[j] == F hay turn == i „ Neáu caû 2 muoán veà thì do turn chæ coù theå nhaän giaù trò 0 hay 1 neân chæ coù 1 tieán trình vaøo CS „ Progress „ Söû duïng 2 bieán interest[i] rieâng bieät => 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 Nhaän xeùt giaûi phaùp phaàn meàm 3: Peterson 11/10/2007 Trần Hạnh Nhi 35 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 36 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 37 Nhoùm Busy-Waiting - Giaûi phaùp phaàn cöùng 1: Caám ngaét Disable Interrupt; CS; Enable Interrupt; NonCS; 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 38 „ 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 Giaûi phaùp phaàn cöùng 1: Caám ngaét 11/10/2007 Trần Hạnh Nhi 39 „ 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 Nhoùm Busy-Waiting - Giaûi phaùp phaàn cöùng 2: chæ thò TSL() TSL (boolean &target) { TSL = target; target = TRUE; } 11/10/2007 Trần Hạnh Nhi 40 Aùp duïng TSL while (TSL(lock)); // wait CS; lock = 0; NonCS; NonCS; Pi int lock = 0 11/10/2007 Trần Hạnh Nhi 41 „ 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 Nhaän xeùt chung caùc giaûi phaùp phaàn cöùng trong nhoùm Busy- Waiting 11/10/2007 Trần Hạnh Nhi 42 „ 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... Nhaän xeùt chung cho caùc giaûi phaùp trong nhoùm Busy Waiting 11/10/2007 Trần Hạnh Nhi 43 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 44 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 45 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 46 AÙp duïng Sleep() and Wakeup() „ int busy; // busy ==0 : CS troáng „ int blocked; // ñeám soá tieán trình bò Blocked chôø vaøo CS if (busy) { blocked = blocked + 1; Sleep(); } else busy = 1; busy = 0; if(blocked) { WakeUp(P); blocked = blocked - 1; } CS; 11/10/2007 Trần Hạnh Nhi 47 Vaán ñeà vôùi Sleep & WakeUp if (busy) { blocked = blocked + 1; Sleep(); } else busy = 1; busy = 0; if(blocked) { WakeUp(P); blocked = blocked - 1; } CS; if (busy) { blocked = blocked + 1; Sleep(); } else busy = 1; busy = 0; if(blocked) { WakeUp(P); blocked = blocked - 1; } CS; „ 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ä P1 P2 P1 blocked vónh vieãn WakeUp bò “laïc” 11/10/2007 Trần Hạnh Nhi 48 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 49 Giaûi phaùp Sleep & Wakeup 1: Semaphore Semaphore s; // s >=0 „ Ñöôïc ñeà nghò bôûi Dijkstra naêm 1965 „ Caùc ñaëc tính : Semaphore s; „ 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 50 Caøi ñaët Semaphore (Sleep & Wakeup) „ 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() 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 11/10/2007 Trần Hạnh Nhi 51 Caøi ñaët Semaphore (Sleep & Wakeup) Down (S) { S.value --; if S.value < 0 { Add(P,S.L); Sleep(); } } Up(S) { S.value ++; if S.value ≤ 0 { Remove(P,S.L); Wakeup(P); } } 11/10/2007 Trần Hạnh Nhi 52 Söû duïng Semaphore ƒ Toå chöùc “ñoäc quyeàn truy xuaát” Pi Down (s) CS; Up(s) ƒ Toå chöùc “hoø heïn” P1 : Job1; Up(s) P2: Down (s); Job2; Semaphore s = ?1 Semaphore s = ?0 11/10/2007 Trần Hạnh Nhi 53 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 54 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 55 Monitor : Ngöõ nghóa vaø tính chaát(1) „ 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 „ 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) MethodA i=0 MethodB prinf(j) MethodC i=5 Share variable: i,j; Monitor M 11/10/2007 Trần Hạnh Nhi 56 Monitor : Ngöõ nghóa vaø tính chaát(2) „ 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ï „ P1 : M.A(); „ P6 : M.B(); „ P7 : M.A(); „ P8 : M.C(); MethodA i = 0 MethodB printf(i) MethodC i=5 P1 P8P7P6 Entry queue Share variable: i,j; 11/10/2007 Trần Hạnh Nhi 57 Monitor : Ngöõ nghóa vaø tính chaát(3) „ 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 MethodA i=0; signal(c1) MethodB MethodC wait(C1); i=5 signal(C2 ); C1: C2: P5 P4 P1 P3 P2 P8P7P6 Entry queue Share variable: i,j; Condition variable: P1 11/10/2007 Trần Hạnh Nhi 58 Söû duïng Monitor ƒ Toå chöùc “ñoäc quyeàn truy xuaát” Pi M.AccessMutual(); //CS ƒ Toå chöùc “hoø heïn” P1 : M.F1(); P2: M.F2(); Monitor M RC; Function AccessMutual CS; // access RC Monitor M Condition c; Function F1 Job1; Signal(c); Function F2 Wait(c); Job2; 11/10/2007 Trần Hạnh Nhi 59 ƒÑöôï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 Server P 1. Send Request 2. Receive Accept 3. Send Finish Giaûi phaùp Sleep & Wakeup 3: Message 11/10/2007 Trần Hạnh Nhi 60 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 61 Baøi toaùn ñoàng boä kinh ñieån 1: Producer - Consumer (Bounded-Buffer Problem) P C Buffer (N) ( ) „ 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 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 ? ƒ 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 62 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 63 Producer – Consummer : Giaûi phaùp Semaphore Producer() { int item; while (TRUE) { produce_item(&item); down(&empty); down(&mutex) enter_item(item,Buffer); up(&mutex); up(&full); } } Consumer() { int item; while (TRUE) { down(&full); down(&mutex); remove_item(&item,Buffer); up(&mutex); up(&empty); consume_item(item); } } 11/10/2007 Trần Hạnh Nhi 64 P&C - Giaûi phaùp Semaphore: Thinking... Producer() { int item; while (TRUE) { produce_item(&item); down(&mutex) down(&empty); enter_item(item,Buffer); up(&mutex); up(&full); } } Consumer() { int item; while (TRUE) { down(&mutex); down(&full); remove_item(&item,Buffer); up(&mutex); up(&empty); consume_item(item); } } 11/10/2007 Trần Hạnh Nhi 65 Producer – Consummer : Giaûi phaùp Monitor monitor ProducerConsumer condition full, empty; int Buffer[N], count; procedure enter(); { if (count == N) wait(full); enter_item(item,Buffer); count ++; if (count == 1) signal(empty); } procedure remove(); { if (count == 0) wait(empty) remove_item(&item,Buffer); count --; if (count == N-1) signal(full); } count = 0; end monitor; 11/10/2007 Trần Hạnh Nhi 66 Producer – Consummer : Giaûi phaùp Monitor Producer() { int item; while (TRUE) { produce_item(&item); ProducerConsumer.enter; } } Consumer(); { int item; while (TRUE) { ProducerConsumer.remove; consume_item(item); } } 11/10/2007 Trần Hạnh Nhi 67 Producer – Consummer : Giaûi phaùp Message Producer() { int item; message m; while (TRUE) { produce_item(&item); receive(consumer, Request); create_message(&m, item); send(consumer,&m); } } Consumer(); { int item; message m; for(0 to N) send(producer, Request); while (TRUE) { receive(producer, &m); remove_item(&m,&item); send(producer, Request); consumer_item(item); } } Coi chöøng Deadlock 11/10/2007 Trần Hạnh Nhi 68 Baøi toaùn ñoàng boä hoaù kinh ñieån 2: Readers & Writers „ 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 „ 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 ? ƒ 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) Database R1 R2 R3 W1 W2 11/10/2007 Trần Hạnh Nhi 69 Readers-Writers vôùi “active readers” 11/10/2007 Trần Hạnh Nhi 70 Readers-writers vôùi moät “active writer” 11/10/2007 Trần Hạnh Nhi 71 Öu tieân ai hôn ñaây ? 11/10/2007 Trần Hạnh Nhi 72 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 73 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 74 R&W : Giaûi phaùp Semaphore (1) Reader() { down(&db); read-db(Database); up(&db); } Writer() { down(&db); write-db(Database); 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 75 R&W : Giaûi phaùp Semaphore (2) Reader() { rc = rc +1; if (rc ==1) down(&db); read-db(Database); rc = rc – 1; if (rc == 0) up(&db); } Writer() { down(&db); write-db(Database); up(&db); } ƒ Ñuùng chöa ? ƒ rc laø bieán duøng chung giöõa caùc Reader... ƒ CS ñoù/ 11/10/2007 Trần Hạnh Nhi 76 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 77 R&W : Giaûi phaùp Semaphore (3) Reader() { down(&mutex); rc = rc +1; if (rc ==1) down(&db); up(mutex); read-db(Database); down(mutex); rc = rc – 1; if (rc == 0) up(&db); up(mutex); } Writer() { down(&db); write-db(Database); up(&db); } Ai ñöôïc öu tieân ? 11/10/2007 Trần Hạnh Nhi 78 R&W : Giaûi phaùp Semaphore (Thinking...) Reader() { down(&mutex); rc = rc +1; up(mutex); if (rc ==1) down(&db); read-db(Database); down(mutex); rc = rc – 1; up(mutex); if (rc == 0) up(&db); } Writer() { down(&db); write-db(Database); up(&db); } ??? heâ, heâ, heâ ☺ 11/10/2007 Trần Hạnh Nhi 79 R&W: Giaûi phaùp Monitor monitor ReaderWriter ? Database; procedure R1(); { } procedure R...(); { } procedure W1(); { } procedure W...(); { } 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; 11/10/2007 Trần Hạnh Nhi 81 Reader&Writer : Giaûi phaùp Monitor Reader() { RW.BeginRead(); Read-db(Database); RW.FinishRead(); } Writer(); { RW.BeginWrite(); Write-db(Database); RW.FinishWrite(); } 11/10/2007 Trần Hạnh Nhi 82 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 83 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 84 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; } Deadlock 11/10/2007 Trần Hạnh Nhi 85 Dining Philosophers : Thaùch thöùc „ Caàn ñoàng boä sao cho: „ Khoâng coù deadlock „ Khoâng coù starvation 4/6/2008 Trần Hạnh Nhi 1 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 2 „ 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æ ? Toång quan : Nhu caàu veà boä nhôù cuûa tieán trình HÑH Boä phaän Quaûn lyù Boä nhôù Moâ hình toå chöùc ? Cô cheá hoã trôï Chieán löôïc thöïc hieän 4/6/2008 Trần Hạnh Nhi 3 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 4 Ví duï „ 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ù? OS nachos gcc emacs 0x0000 0x4000 0x3000 0x7000 0x9000 Moâi tröôøng ña nhieäm 4/6/2008 Trần Hạnh Nhi 5 C program: test.c Executable: test.exe Compiler Linker Loader Memory Object:test.o lib.o Caùc böôùc chuyeån ñoåi chöông trình Caùc böôùc chuyeån ñoåi source program -> .exe int x; int y; x = 12; y = 5; F(); A.C F() { printf(“Hi”); } B.C 0 // x 2 // y 4 // [0] = 12; 5 // [2] = 5; 6 // jmp F //external // object A.O B.O 0 -2 // F() 0 // F() 3 // x 5 // y 7 // [3] = 12; 8 // [5] = 5; 9 // jmp 0 ? // F() ? // x ? // y ? // [?] = 12; ? // [?] = 5; ? // jmp ? OS Test.exe 4/6/2008 Trần Hạnh Nhi 8 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 9 Nhu caàu boä nhôù cuûa tieán trình „ Tiến trình gồm có: „ code segment „ read from program file by exec „ usually read-only „ can be shared „ data segment „ initialized global variables (0 / NULL) „ uninitialized global variables „ heap „ dynamic memory „ e.g., allocated using malloc „ grows against higher addresses „ stack segment „ variables in a function „ stored register states (e.g. calling function EIP) „ grows against lower addresses „ system data segment (PCB) „ segment pointers „ pid „ program and stack pointers „ „ Stack cho các thread process A low address high address ... 8048314 : 8048314: push %ebp 8048315: mov %esp,%ebp 8048317: mov 0xc(%ebp),%eax 804831a: add 0x8(%ebp),%eax 804831d: pop %ebp 804831e: ret 804831f : 804831f: push %ebp 8048320: mov %esp,%ebp 8048322: sub $0x18,%esp 8048325: and $0xfffffff0,%esp 8048328: mov $0x0,%eax 804832d: sub %eax,%esp 804832f: movl $0x0,0xfffffffc(%ebp) 8048336: movl $0x2,0x4(%esp,1) 804833e: movl $0x4,(%esp,1) 8048345: call 8048314 804834a: mov %eax,0xfffffffc(%ebp) 804834d: leave 804834e: ret 804834f: nop code segment system data segment (PCB) data segment initialized variables uninitialized variables d a t a s e g m e n t heap stack “ u n u s e d ” m e m o r y possible stacks for more threads 4/6/2008 Trần Hạnh Nhi 10 Logical and Physical Address Spaces 4/6/2008 Trần Hạnh Nhi 11 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 12 „ 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 Thôøi ñieåm keát buoäc ñòa chæ ? 4/6/2008 Trần Hạnh Nhi 13 Chuyeån ñoåi ñòa chæ gcc virtual address Load Store error data Translation box CPU legal addr? Illegal? Physical memory Physical address MMU 4/6/2008 Trần Hạnh Nhi 14 CPU, MMU and Memory 4/6/2008 Trần Hạnh Nhi 15 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. Relocation 2. Protection 3. Sharing 4. Logical Organization 5. Physical Organization 4/6/2008 Trần Hạnh Nhi 16 „ 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. Taùi ñònh vò (Relocation) 4/6/2008 Trần Hạnh Nhi 17 „ 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. Baûo veä (Protection) 4/6/2008 Trần Hạnh Nhi 18 „ 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. Chia seû (Sharing) 4/6/2008 Trần Hạnh Nhi 19 „ 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 Toå chöùc logic (Logical Organization) 4/6/2008 Trần Hạnh Nhi 20 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 21 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 22 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 23 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 24 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 25 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 26 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 3M 8M P1 (2M) P2 (4M) internal frag internal frag 4/6/2008 Trần Hạnh Nhi 27 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 „ 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 P1 (2M) P2 (4M) Dynamic Partitioning: tình huoáng „ 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 P1 (2M) P2 (4M) P3 (8M) 2M P4 (1.5M) external fragmentation 4/6/2008 Trần Hạnh Nhi 29 Ví duï Dynamic Partitioning 4/6/2008 Trần Hạnh Nhi 30 Ví duï Dynamic Partitioning 4/6/2008 Trần Hạnh Nhi 31 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 P1 8M P3 (1M) P2 1.5M Worst Fit First Fit Best Fit 4/6/2008 Trần Hạnh Nhi 32 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 1M External fragmentations P2 1.5M 4/6/2008 Trần Hạnh Nhi 33 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 34 Moâ hình Linker-Loader „ 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 0x0000 test.exe 0x4000 0x3000 test.exe jump 0x2000 jump 0x5000 0x7000 OS (base) 4/6/2008 Trần Hạnh Nhi 35 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 36 Moâ hình Base & Bound 0x0000 Test.exe 0x4000 Base 0x3000 OS Test.exe jump 0x2000 jump 0x2000 Bound 0x7000 „ 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 37 Nhaän xeùt moâ hình Base & Bound „ Hoã trôï ƒ Baûo veä ƒ Taùi ñònh vò MMU + base reg logical addrs memory physical addrs CPU „ 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 4/6/2008 Trần Hạnh Nhi 38 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 8M P3 (9M) P2 1M 4/6/2008 Trần Hạnh Nhi 39 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 40 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 41 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 ! „ 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 4/6/2008 Trần Hạnh Nhi 42 Moâ hình Segmentation KGVL int m; main () { F1(m); } F1(int x) { x = 9; } code (main,F1) data (m) stack heap KGDCQuaûn lyù ñòa chæ ? 4/6/2008 Trần Hạnh Nhi 43 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 44 Chuyeån ñoåi ñòa chæ trong moâ hình Segmentation Logical Addr Seg# offset 3 128 Seg table base limit 3 0x1000 512 mem seg 128 + 0x1000? yes no fault 0 1 2 4/6/2008 Trần Hạnh Nhi 45 Logical-to-Physical Address Translation in segmentation 4/6/2008 Trần Hạnh Nhi 46 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 47 Sharing of Segments: Text Editor 4/6/2008 Trần Hạnh Nhi 48 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 49 Moâ hình Paging KGVL int m; main () { F1(m); } F1(int x) { x = 9; } KGDC Quaûn lyù ñòa chæ ? int m; main () F1(int x) stack heap 4/6/2008 Trần Hạnh Nhi 50 Toå chöùc Paging „ Ñiaï chæ logic : „ Ñòa chæ physic : „ Chuyeån ñoåi ñ