Cấp hệ điều hành

Caáp heä ñieàu haønh

Muïc tieâu:

- Tìm hieåu kyõ thuaät boä nhôù aûo (Virtual Memory)

- Caùc chæ thò I/O aûo

- Kyõ thuaät xöû lyù tieán trình song song

Caáp heä ñieàu haønh

Cấu trúc chƣơng trình Cấu trúc Overlay

Trong cấu trúc Overlay, các module chƣơng trình sau khi biên dịch đƣợc chia thành các mức: Mức 0: mức chứa module gốc dùng để nạp chƣơng trình Mức 1: chứa các module đƣợc gọi bởi mức 0 Mức 2: chứa các module đƣợc gọi bởi mức 1 ………. Mức i: chứa các module đƣợc gọi bởi mức i-1 Bộ nhớ dành cho chƣơng trình cũng đƣợc chia thành các mức tƣơng ứng với các mức chƣơng trình. Kích thƣớc mỗi mức trong bộ nhớ bằng kích thƣớc module lớn nhất của mức chƣơng trình tƣơng ứng.

CPU

Mức 0: 80Kb

M0 (80Kb)

Mức 1: 90Kb

M1 (50Kb)

M2 (90Kb)

Mức 2: 100Kb

M3 (50Kb)

M4 (100Kb)

M5 (70Kb)

Caáp heä ñieàu haønh

Cấu trúc chƣơng trình

Cấu trúc Overlay

* Ƣu điểm: - Cấu trúc Overlay có tính chất định vị động  cho phép sử dụng bộ nhớ nhiều hơn phần bộ nhớ mà hệ thống dành cho chƣơng trình. Cấu trúc chƣơng trình mang tính chất tĩnh, không thay đổi trong tất cả các lần thực hiện chƣơng trình.

- So với cấu trúc động, cấu trúc Overlay đòi hỏi cung cấp thông tin đơn

giản, không gắn cấu trúc vào chƣơng trình nguồn

- Với sơ đồ Overlay tốt và các module độ dài không quá lớn thì hiệu quả

không kém so với cấu trúc động

* Nhƣợc điểm: hiệu qủa tiết kiệm bộ nhớ phụ thuộc cách tổ chức, bố trí các module chƣơng trình

Caáp heä ñieàu haønh

Boä nhôù aûo

Khoù khaên: - Boä nhôù coù dung löôïng nhoû vaø giaù thaønh raát cao - Laäp trình vieân phaûi maát nhieàu thôøi gian ñeå xöû lyù kích thöôùc

chöông trình - Khoù söû duïng caùc giaûi thuaät toát ñoøi hoûi khoâng gian boä nhôù lôùn

Giaûi phaùp truyeàn thoáng: - Chia chöông trình thaønh caùc maûng nhoû (overlay) coù theå ñaët vöøa boä nhôù - Chöông trình thöïc thi laàn löôït caùc overlay

- Taùch chöông trình - Quyeát ñònh vò trí caát overlay trong boä nhôù phuï - Saép xeáp chuyeån ñoåi overlay giöõa boä nhôù chính vaø phuï

Nhöôïc ñieåm: Ngöôøi laäp trình töï thao taùc baèng tay caùc coâng vieäc: Khaéc phuïc: Phöông phaùp töï ñoäng hoùa toaøn boä quaù trình overlay

 Phöông phaùp boä nhôù aûo

Caáp heä ñieàu haønh

Boä nhôù aûo

* Kyõ thuaät phaân trang

- Taùch rieâng khoâng gian ñòa chæ vaø caùc vò trí oâ nhôù - Ví duï: maùy tính vôùi tröôøng ñòa chæ 16 bit trong caùc chæ thò vaø 4096 töø

nhôù  Chöông trình maùy tính ñòa chæ hoùa 216 = 65536 töø nhôù

1. Noäi dung boä nhôù chính ñöôïc caát vaøo boä nhôù phuï

2. Caùc töø nhôù ñöôïc ñaët töø 4096 ñeán 8191

64K khoâng gian ñòa chæ 4K boä nhôù chính

0 Ñòa chæ 0 4096

4095 8191 12287

3. Caùc töø nhôù töø 4096 ñeán 8191 naïp vaøo boä nhôù chính

4. Aùnh xaï ñòa chæ töø 4096 ñeán 8191 leân caùc vò trí nhôù töø 0 ñeán 4095

Aùnh xaï ñòa chæ töø khoâng gian ñòa chæ leân boä nhôù chính

65535

Caáp heä ñieàu haønh

Boä nhôù aûo

* Kyõ thuaät phaân trang

+ Baûn sao chöông trình trong boä nhôù phuï laø baûn goác + Caùc maûng chöông trình mang vaøo boä nhôù chính ôõ nhöõng thôøi ñieåm khaùc nhau laø baûn sao

+ Khoâng gian ñòa chæ aûo taùch thaønh nhieàu trang kích thöôùc baèng nhau vaø luoân laø luõy thöøa cuûa 2 + Khoâng gian ñòa chæ vaät lyù cuõng taùch thaønh töøng maûng coù kích

- Yeâu caàu: Boä nhôù phuï coù theå chöùa ñöôïc toaøn boä chöông trình - Khaùi nieäm: - Thieát keá: thöôùc baèng kích thöôùc caùc trang vaø caát vaøo khung trang

Caáp heä ñieàu haønh

Boä nhôù aûo

* Kyõ thuaät phaân trang

Ví duï:

32K khoâng gian vaät lyù 64K khoâng gian ñòa chæ aûo 0 0 4K 4K Page 0 0-4095 Page 0 0-4095 4096 4096

Page 1

4096-8191

Page 1

4096-8191

8192 8192 Page 2 8192-12287 Page 2 8192-12287 12288 12288 Page 3 12288-16383 Page 3 12288-16383 16384 16384 Page 4 .... Page 4 .... 20480 20480 Page 5 .... Page 5 .... 24576 24576 Page 6 24576-28671 Page 6 .... 28672 28672 Page 7 28672-32767 Page 7 .... 32768 Page 8 .... 36864 Page 9 .... 40960

0 0 1 1 0 0 0 0 0 0 0 1 0 1 1 0

Page 10 .... 45056 Page 11 .... 49152 Page 12 .... 53248 Page 13 .... 57344

4 bit Soâ trang aûo = 3

Page 14 57344-61139

12 bit Ñòa chæ choïn treân trang aûo = 22 (12310)

61140

Page 15 61140-65536

Caáp heä ñieàu haønh

Boä nhôù aûo

* Kyõ thuaät phaân đoạn

+ Kỹ thuật phaân trang: Neáu kích thöôùc chöông trình/döõ lieäu khoâng baèng ñuùng moät trang Khoaûng troáng khoâng duøng ñeán  Hieän töôïng phaân maûnh  Hao phí boä nhôù

* Taïo caùc khoâng gian ñòa chæ ñoäc laäp (goïi laø segment) * Moãi segment coù chieàu daøi khaùc nhau vaø coù theå thay ñoåi theo thôøi gian thöïc * Ñeå xaùc ñònh ñòa chæ trong boä nhôù phaân ñoaïn, chöông trình cung caáp ñòa chæ coù 2 phaàn: soá segment vaø ñòa chæ trong segment

+ Kỹ thuật phaân ñoaïn: - Thieát keá: - Öu ñieåm:

* Ñôn giaûn hoùa vieäc quaûn lyù caáu truùc döõ lieäu * Deã daøng duøng chung döõ lieäu cho caùc chöông trình * Tieát kieäm boä nhôù

Caáp heä ñieàu haønh

Boä nhôù aûo

* Kyõ thuaät phaân đoạn

Segment 0 (4K) Segment 0 (4K) Segment 0 (4K) Segment 0 (4K)

Segment 1 (8K) Segment 7 (5K) Segment 7 (5K) Segment 7 (5K)

(3K) (3K) (3K)

Segment 2 (5K) Segment 2 (5K) Segment 2 (5K) Segment 2 (5K)

Segment 3 (8K) Segment 3 (8K) Segment 3 (8K) Segment 6 (4K)

(4K)

Segment 4 (7K) Segment 4 (7K) Segment 5 (4K) Segment 5 (4K)

(3K) (3K)

- Nhöôïc ñieåm: Boä nhôù ñöôïc chia, moät soá chöùa segment vaø moät soá chöùa loã troáng  Hieän töôïng baøn côø  laõng phí boä nhôù

Caáp heä ñieàu haønh

Boä nhôù aûo

* Kyõ thuaät phaân đoạn: khaéc phuïc hieän töôïng baøn côø

Phöông phaùp 1: Moãi laàn xuaát hieän loã troáng, di chuyeån segment veà vò trí 0 cuûa boä nhôù

Segment 0 (4K) Segment 0 (4K) Segment 0 (4K) Segment 0 (4K) Segment 0 (4K)

Segment 1 (8K) Segment 7 (5K) Segment 7 (5K) Segment 7 (5K) Segment 7 (5K)

(3K) Segment 2 (5K) Segment 2 (5K) Segment 2 (5K)

Segment 2 (5K) Segment 2 (5K) Segment 3 (8K) Segment 6 (4K) Segment 6 (4K)

Segment 3 (8K) Segment 3 (8K)

(4K) Segment 4 (7K)

Segment 4 (7K) Segment 4 (7K)

Segment 4 (7K) Segment 4 (7K) (7K)

(3K) (3K)

Toán nhieàu thôøi gian ñeå di chuyeån

Caáp heä ñieàu haønh

Boä nhôù aûo

* Kyõ thuaät phaân đoạn: khaéc phuïc hieän töôïng baøn côø

Phöông phaùp 2 (Best Fit): Choïn phaàn troáng vöøa khít nhaát vôùi segment caàn ñöa vaøo

Segment 0 (4K) Segment 0 (4K) Segment 0 (4K) Segment 0 (4K)

Segment 1 (8K) Segment 7 (5K) Segment 7 (5K) Segment 7 (5K)

(3K) (3K) Segment 8 (3K) 3K

Segment 2 (5K) Segment 2 (5K) Segment 2 (5K) Segment 2 (5K)

Segment 8 (3K) Segment 3 (8K) Segment 3 (8K) Segment 6 (4K) Segment 6 (4K)

(4K) 4K (4K)

Segment 4 (7K) Segment 4 (7K) Segment 4 (7K) Segment 4 (7K)

Caáp heä ñieàu haønh

Boä nhôù aûo

* Kyõ thuaät phaân đoạn: khaéc phuïc hieän töôïng baøn côø

Phöông phaùp 3 (First Fit): Queùt voøng troøn danh saùch caùc phaàn troáng vaø choïn phaàn troáng ñaàu tieân ñuû lôùn vöøa vôùi segment caàn ñöa vaøo

Segment 0 (4K) Segment 0 (4K) Segment 0 (4K) Segment 0 (4K)

Segment 1 (8K) Segment 7 (5K) Segment 7 (5K) Segment 7 (5K)

(3K) (3K) Segment 8 (3K) 1

Segment 2 (5K) Segment 2 (5K) Segment 2 (5K) Segment 2 (5K)

Segment 8 (3K) Segment 3 (8K) Segment 3 (8K) Segment 6 (5K) Segment 6 (4K)

(4K) (3K) 2

Segment 4 (7K) Segment 4 (7K) Segment 4 (7K) Segment 4 (7K)

Caáp heä ñieàu haønh

Boä nhôù aûo

SƠ ĐỒ KẾT HỢP PHÂN TRANG VÀ PHÂN ĐOẠN

* Vì sao cần kết hợp?:

Sơ đồ phân trang đảm bảo hiệu quả sử dụng bộ nhớ mà không phụ thuộc vào cấu trúc chƣơng trình của ngƣời sử dụng, điều khiển trang thuận tiện, đơn giản. Tuy nhiên khi chƣơng trình có kích thƣớc lớn thì kích thƣớc bảng PCB cũng lớn theo  lãng phí bộ nhớ. Nếu kích thƣớc trang quá nhỏ  kích thƣớc PCb lớn  tăng khả năng nạp đi nạp lại trang  giảm hiệu quả sử dụng bộ nhớ.

Sơ đồ phân đoạn linh hoạt hơn về độ dài các đoạn nhƣng vì độ dài các đoạn khác nhau  phức tạp trong vấn đề thực hiện và cấp phát bộ nhớ

 Để phát huy ƣu điểm và hạn chế nhƣợc điểm của các sơ đồ trên, ngƣời ta thƣờng sử dụng sơ đồ kết hợp phân trang và phân đoạn

Caáp heä ñieàu haønh

Boä nhôù aûo

SƠ ĐỒ KẾT HỢP PHÂN TRANG VÀ PHÂN ĐOẠN

Trong sơ đồ này, chƣơng trình đƣợc biên dịch theo sơ đồ phân đoạn và có một bảng quản lý SCB. Mỗi đoạn chƣơng trình lại đƣợc biên tập theo sơ đồ phân trang và tạo ra từng bảng PCB riêng cho mỗi đoạn.

Khi chƣơng trình đƣợc nạp vào hệ thống, hệ điều hành sẽ cấp phát cho chƣơng trình các trang cần thiết để chứa đủ các đoạn chƣơng trình

Caáp heä ñieàu haønh

Boä nhôù aûo

SƠ ĐỒ KẾT HỢP PHÂN TRANG VÀ PHÂN ĐOẠN

Gọi trƣờng địa chỉ A của phần tử thứ I trong SCB với SCB là nơi chứa bảng quản lý trang thứ I (PCBi) có trƣờng độ dài L chứa độ dài của PCBi

Khi thực hiện, bảng PCB đƣợc nạp vào bộ nhớ và địa chỉ đầu của nó đƣợc ghi vào thanh ghi quản lý đoạn Rs. Địa chỉ truy nhập dữ liệu đƣợc biểu diễn bởi bộ ba (s,p,d), trong đó:

s: số hiệu đoạn cần truy nhập trong SCB - - p: số hiệu trang cần truy nhập trong PCB - d: địa chỉ tƣơng đối tính từ đầu trang

Caáp heä ñieàu haønh

Boä nhôù aûo

SƠ ĐỒ KẾT HỢP PHÂN TRANG VÀ PHÂN ĐOẠN

Để truy nhập tới dữ liệu, hệ thống trải qua 3 bƣớc:

* Bƣớc 1: Lấy nội dung thanh ghi Rs cộng với s và truy nhập tới phần tử thứ s trong SCB

* Bƣớc 2: Nếu D=0 thì thực hiện thủ tục nạp PCB tƣơng ứng vào bộ nhớ và cập nhật nội dung trƣờng A. Khi nạp xong PCB, hệ thống cộng nội dung trƣờng A với p để truy nhập tới phần tử thứ p trong PCB

* Bƣớc 3: Khi tìm thấy phần tử p trong PCB, hệ thống sẽ ghép nội dung của Ap (tƣơng ứng phần tử thứ p) với d để tìm ra địa chỉ đọc/ghi dữ liệu

Caáp heä ñieàu haønh

Caùc chæ thò I/O aûo

- Phöông phaùp toå chöùc I/O aûo: laø töôûng töôïng döõ lieäu ñoïc/ghi laø moät

chuoãi caùc baûn ghi logic

- Moät baûn ghi logic laø moät ñôn vò thoâng tin - Moät chuoãi caùc baûn ghi logic ñöôïc goïi laø taäp tin - Caùc baûn ghi trong taäp tin khoâng caàn coù ñoä daøi baèng nhau

- Caùc loaïi taäp tin tuaàn töï: löu tröõ treân baêng töø, ñóa töø meàm, CD,..

- Caùc loaïi chæ thò I/O aûo:

* Chæ thò nhaäp aûo (ñoïc taäp tin) * Chæ thò xuaát aûo (ghi taäp tin) * Chæ thò môû taäp tin

Caáp heä ñieàu haønh

Caùc chæ thò I/O aûo

Caùc taäp tin truy xuaát tuaàn töï

Höôùng di chuyeån cuûa taäp tin

1

2. Chæ thò READ tuaàn töï laáy baûn ghi logic lieân tieáp vaø ghi leân vuøng ñeäm

2

3

Soá caùc baûn ghi logic

4

Boä nhôù chính

5

Chæ thò nhaäp aûo cô baûn: Chæ thò phaûi xaùc ñònh ñöôïc thoâng tin: - Taäp tin ñöôïc ñoïc - Ñòa chæ boä nhôù chính

6

löu giöõ baûn ghi

Vuøng ñeäm

Baûn ghi logic

7

1. Cung caáp chæ thò OPEN ñeå môû taäp tröôùc khi söû duïng

8

9

10

11

12

...

Caáp heä ñieàu haønh

Caùc chæ thò I/O aûo

Caùc taäp tin truy xuaát tuaàn töï

Höôùng di chuyeån cuûa taäp tin

Chæ thò xuaát aûo cô baûn:

1

2

2. Chæ thò REWIND xaùc ñònh vò trí baûn ghi logic seõ ñöôïc ghi ñaàu tieân

3

Soá caùc baûn ghi logic

4

Boä nhôù chính

5

1. Cung caáp chæ thò OPEN ñeå môû taäp tröôùc khi söû duïng

6

Vuøng ñeäm

Baûn ghi logic

7

Xaùc ñònh vò trí baûn ghi logic keá tieáp ñöôïc ghi

3. Chæ thò WRITE tuaàn töï lieân tieáp taïo caùc baûn ghi lieân tieáp leân taäp tin

Maát nhieàu thôøi gian ñeå ñoïc tuaàn töï töø ñaàu

Caáp heä ñieàu haønh

Caùc chæ thò I/O aûo

Caùc taäp tin truy xuaát ngaãu nhieân

Höôùng di chuyeån cuûa taäp tin

1

2

Soá caùc baûn ghi logic

3

4

Boä nhôù chính

5

Chæ thò xuaát aûo cô baûn: Chæ thò phaûi xaùc ñònh ñöôïc thoâng tin: - Taäp tin ñöôïc ñoïc - Ñòa chæ boä nhôù chính

1. Cung caáp chæ thò OPEN ñeå môû taäp tröôùc khi söû duïng

löu giöõ baûn ghi

6

- Vò trí baûn ghi logic

Vuøng ñeäm

Baûn ghi logic

7

trong taäp tin

2. Chæ thò aûo ñoïc baûn ghi logic n

3. Chæ thò WRITE ghi baûn ghi leân taäp tin

Caáp heä ñieàu haønh

Toå chöùc caùc chæ thò I/O aûo Taäp tin ñöôïc caáp phaùt lieân tieáp

Ñôn vò caáp phaùt laø SECTOR: 1 sector daønh cho taäp tin vaø caùc sector khaùc treân cuøng track daønh cho caùc taäp tin khaùc

Heä ñieàu haønh caàn bieát: - Vò trí baét ñaàu cuûa taäp tin - Kích thöôùc caùc baûn ghi

vaät lyù

 Tính toaùn vò trí caùc baûn ghi logic

Ñôn vò caáp phaùt laø TRACK: toaøn boä track daønh cho taäp tin, caùc track khaùc treân cuøng cylinder daønh cho caùc taäp tin khaùc

vò

caáp

phaùt

toaøn

laø boä

Track 0

Ñôn CYLINDER: cylinder daønh cho 1 taäp tin

Track 4

Höôùng ñoïc ñóa

Caáp heä ñieàu haønh

Toå chöùc caùc chæ thò I/O aûo Taäp tin khoâng ñöôïc caáp phaùt lieân tieáp

Ñeå ñònh vò baûn ghi:

- Phöông phaùp 1: Söû duïng baûng chæ soá taäp tin cho bieát ñòa chæ treân ñóa töøng baûn ghi

1 1

- Phöông phaùp 2: Toå chöùc taäp tin nhö moät danh saùch lieân keát:Ñôn vò caáp phaùt chöùa ñòa chæ ñôn vò keá tieáp

Track 0

Track 4

Höôùng ñoïc ñóa

Caáp heä ñieàu haønh

Toå chöùc caùc chæ thò I/O aûo Caáp phaùt khoâng gian cho taäp tin

- Phöông phaùp 1: Söû duïng danh saùch troáng

Track Sector

Soá sector troáng

0

0

12

1

0

10

2

3

2

2

7

1

2

10

2

3

0

3

3

4

7

4

1

9

4

11

1

- Öu ñieåm: deã quaûn lyù - Nhöôïc ñieåm: Khoù khaên khi

coù söï bieán ñoäng

Caáp heä ñieàu haønh

Toå chöùc caùc chæ thò I/O aûo Caáp phaùt khoâng gian cho taäp tin

- Phöông phaùp 2: Söû duïng baûn ñoà Bit

Sector

Track 0 1 2 3 4 5 6 7 8 9 10 11

0

0 0 0 0 0 0 0 0 0 0 0 0

1

0 0 0 0 0 0 0 0 0 0 1 1

2

1 1 1 0 0 1 1 0 1 1 0 0

3

0 0 0 1 0 0 0 0 0 0 1 0

4

1 0 0 0 0 0 0 0 0 0 1 0

- Öu ñieåm: deã quaûn lyù, khi coù bieán ñoäng chæ ñôn giaûn laø thay ñoåi 1 bit

- Nhöôïc ñieåm: Tìm moät khoái coù kích thöôùc cho tröôùc seõ khoù khaên

Caáp heä ñieàu haønh

Xöû lyù song song

Tieán trình 3 ñang chôø

Tieán trình 3

CPU 3

Tieán trình 2

CPU 2

Tieán trình 1

CPU 1

CPU

Time

Time

Tieán trình 1 ñang chaïy

Xöû lyù song song vôùi nhieàu CPU

Xöû lyù song song vôùi moät CPU

Caáp heä ñieàu haønh

Xöû lyù song song Phƣơng pháp khóa trong

THUẬT TOÁN DEKKER: Dùng thêm một biến khóa TT để xác định độ ƣu tiên của các tiến trình khi cả hai tiến trình cùng muốn vào đoạn tới hạn (TT=1 hoặc TT=2)

Tiến trình 1

Tiến trình 2

K1:=1; While K2=1 do if TT=2 then Begin K1:=0; While TT=2 do Skip; K1:=1; End; {Tiến trình 1 vào đoạn tới hạn} K1:=0;TT=2; {Phần còn lại của tiến trình 1}

K2:=1; While K1=1 do if TT=1 then Begin K2:=0; While TT=1 do Skip; K2:=1; End; {Tiến trình 2 vào đoạn tới hạn} K2:=0;TT=1; {Phần còn lại của tiến trình 2}

Repeat Until False;

Repeat Until False;

Caáp heä ñieàu haønh

Xöû lyù song song

Phƣơng pháp khóa trong

Nhận xét: Thuật toán Dekker giải quyết bài toán đoạn tới hạn hợp lý trong mọi trƣờng hợp cho dù tốc độ thực hiện của các tiến trình khác nhau. Ƣu điểm: Phƣơng pháp khóa trong không đòi hỏi công cụ đặc biệt, do đó có thể tổ chức bằng một ngôn ngữ bất kỳ và thực hiện trên mọi hệ thống. Nhƣợc điểm: - Độ phức tạp của thuật toán sẽ tăng khi số tiến trình nhiều hoặc số lƣợng đoạn tới hạn trong các tiến trình lớn. - Các tiến trình phải chờ đợi trong trạng thái tích cực

Caáp heä ñieàu haønh

Xöû lyù song song

Phƣơng pháp đèn hiệu

1. Nguyên tắc chung: Đèn hiệu S là một biến nguyên mà chỉ có hai phép xử lý WAIT và SIGNAL mới thay đổi đƣợc giá trị của nó. Định nghĩa phép WAIT(S): S:=S-1 Nếu S>=0  tiếp tục thực hiện tiến trình Nếu S<0  đƣa tiến trình vào hàng đợi Định nghĩa phép SIGNAL(S): S:=S+1 Nếu S<=0  đƣa tiến trình trong hàng đợi vào đoạn tới hạn

Chú ý: + Phép WAIT và SIGNAL không bị phân chia trong tiến trình thực hiện. + Nếu ban đầu S=1 và cả hai tiến trình đều đƣa ra phép WAIT(S) thì chỉ có một tiến trình đƣợc phép vào đoạn tới hạn, tiến trình còn lại sẽ đƣợc đƣa vào hàng đợi.

Caáp heä ñieàu haønh

Xöû lyù song song Phƣơng pháp đèn hiệu

Trình bày thuật toán (Bài toán 2 tiến trình)

Tiến trình 1

Tiến trình 2

{Tiến trình 1 vào đoạn tới hạn} SIGNAL(S); {Phần còn lại của tiến trình 1}

WAIT(S); {Tiến trình 2 vào đoạn tới hạn} SIGNAL(S); {Phần còn lại của tiến trình 2}

Repeat WAIT(S); Until False;

Repeat Until False;

* Ƣu điểm: Mỗi tiến trình chỉ cần kiểm tra quyền 1 lần

* Nhƣợc điểm: Phép WAIT và SIGNAL phải tổ chức hàng đợi