markdown:
# Giáo Trình Hệ Điều Hành - Chương 4: ĐỊNH THỜI BIỂU CPU
Chia sẻ: TRẦN THỊ THANH HẰNG | Ngày: | Loại File: PDF | Số trang:22
lượt xem 36
download
![](http://image1.tailieu.vn/document/thumbnail/2010/20100724/hangkute_1/80x100/chuong4_dinh_thoi_bieu_cpu_2221.jpg)
##
Giáo Trình Hệ Điều Hành - Chương 4: ĐỊNH THỜI BIỂU CPU
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static1.tailieu.vn/b2013az/templates/version1/default/images/down16x21.png)
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 ĐỊNH THỜI BIỂU CPU I Mục tiêu Sau khi học xong chương này, người học nắm được những kiến thức sau: • Hiểu các khái niệm cơ bản về định thời • Hiểu các giải thuật định thời biểu CPU • Vận dụng một giải thuật định thời cho một hệ thống cụ thể II Giới thiệu Định thời biểu là cơ sở của các hệ điều hành đa chương. Bằng cách chuyển đổi CPU giữa các quá trình, hệ điều hành có thể làm máy tính...
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
##
Nội dung Text: Giáo Trình Hệ Điều Hành - Chương 4: ĐỊNH THỜI BIỂU CPU
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 ĐỊNH THỜI BIỂU CPU I Mục tiêu Sau khi học xong chương này, người học nắm được những kiến thức sau: • Hiểu các khái niệm cơ bản về định thời • Hiểu các giải thuật định thời biểu CPU • Vận dụng một giải thuật định thời cho một hệ thống cụ thể II Giới thiệu Định thời biểu là cơ sở của các hệ điều hành đa chương. Bằng cách chuyển đổi CPU giữa các quá trình, hệ điều hành có thể làm máy tính hoạt động nhiều hơn. Trong chương này, chúng ta giới thiệu các khái niệm định thời cơ bản và trình bày các giải thuật định thời biểu CPU khác nhau. Chúng ta cũng xem xét vấn đề chọn một giải thuật cho một hệ thống xác định. III Các khái niệm cơ bản Mục tiêu của đa chương là có nhiều quá trình chạy cùng thời điểm để tối ưu hóa việc sử dụng CPU. Trong hệ thống đơn xử lý, chỉ một quá trình có thể chạy tại một thời điểm; bất cứ quá trình nào khác đều phải chờ cho đến khi CPU rảnh và có thể được định thời lại. Ý tưởng của đa chương là tương đối đơn giản. Một quá trình được thực thi cho đến khi nó phải chờ yêu cầu nhập/xuất hoàn thành. Trong một hệ thống máy tính đơn giản thì CPU sẽ rảnh rỗi; tất cả thời gian chờ này là lãng phí. Với đa chương, chúng ta cố gắng dùng thời gian này để CPU có thể phục vụ cho các quá trình khác. Nhiều quá trình được giữ trong bộ nhớ tại cùng thời điểm. Khi một quá trình phải chờ, hệ điều hành lấy CPU từ quá trình này và cấp CPU tới quá trình khác. Định thời biểu là chức năng cơ bản của hệ điều hành. Hầu hết tài nguyên máy tính được định thời biểu trước khi dùng. Dĩ nhiên, CPU là một trong những tài nguyên máy tính ưu tiên. Do đó, định thời biểu là trọng tâm trong việc thiết kế hệ điều hành. III.1 Chu kỳ CPU-I/O Sự thành công của việc định thời biểu CPU phụ thuộc vào thuộc tính được xem xét sau đây của quá trình. Việc thực thi quá trình chứa một chu kỳ (cycle) thực thi CPU và chờ đợi nhập/xuất. Các quá trình chuyển đổi giữa hai trạng thái này. Sự thực thi quá trình bắt đầu với một chu kỳ CPU (CPU burst), theo sau bởi một chu kỳ nhập/xuất (I/O burst), sau đó một chu kỳ CPU khác, sau đó lại tới một chu kỳ nhập/xuất khác khác,..Sau cùng, chu kỳ CPU cuối cùng sẽ kết thúc với một yêu cầu hệ thống để kết thúc việc thực thi, hơn là với một chu kỳ nhập/xuất khác, được mô tả như hình IV.1. Một chương trình hướng nhập/xuất (I/O-bound) thường có nhiều chu kỳ CPU ngắn. Một chương trình hướng xử lý (CPU-bound) có thể có một nhiều chu Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 56
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 kỳ CPU dài. Sự phân bổ này có thể giúp chúng ta chọn giải thuật định thời CPU hợp lý. Hình 0-1-Thay đổi thứ tự của CPU và I/O burst III.2 Bộ định thời CPU Bất cứ khi nào CPU rảnh, hệ điều hành phải chọn một trong những quá trình trong hàng đợi sẳn sàng để thực thi. Chọn quá trình được thực hiện bởi bộ định thời biểu ngắn (short-term scheduler) hay bộ định thời CPU. Bộ định thời này chọn các quá trình trong bộ nhớ sẳn sàng thực thi và cấp phát CPU tới một trong các quá trình đó. Hàng đợi sẳn sàng không nhất thiết là hàng đợi vào trước, ra trước (FIFO). Xem xét một số giải thuật định thời khác nhau, một hàng đợi sẳn sàng có thể được cài đặt như một hàng đợi FIFO, một hàng đợi ưu tiên, một cây, hay đơn giản là một danh sách liên kết không thứ tự. Tuy nhiên, về khái niệm tất cả các quá trình trong hàng đợi sẳn sàng được xếp hàng chờ cơ hội để chạy trên CPU. Các mẫu tin trong hàng đợi thường là khối điều khiển quá trình của quá trình đó. III.3 Định thời biểu trưng dụng Quyết định định thời biểu CPU có thể xảy ra một trong 4 trường hợp sau: • Khi một quá trình chuyển từ trạng thái chạy sang trạng thái chờ (thí dụ: yêu cầu nhập/xuất, hay chờ kết thúc của một trong những quá trình con). • Khi một quá trình chuyển từ trạng thái chạy tới trạng thái sẳn sàng (thí dụ: khi một ngắt xảy ra) • Khi một quá trình chuyển từ trạng thái chờ tới trạng thái sẳn sàng (thí dụ: hoàn thành nhập/xuất) Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 57
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 • Khi một quá trình kết thúc Trong trường hợp 1 và 4, không cần chọn lựa loại định thời biểu. Một quá trình mới (nếu tồn tại trong hàng đợi sẳn sàng) phải được chọn để thực thi. Tuy nhiên, có sự lựa chọn loại định thời biểu trong trường hợp 2 và 3. Khi định thời biểu xảy ra chỉ trong trường hợp 1 và 4, chúng ta nói cơ chế định thời không trưng dụng (nonpreemptive); ngược lại, khi định thời biểu xảy ra chỉ trong trường hợp 2 và 3, chúng ta nói cơ chế định thời trưng dụng (preemptive). Trong định thời không trưng dụng, một khi CPU được cấp phát tới một quá trình, quá trình giữ CPU cho tới khi nó giải phóng CPU hay bởi kết thúc hay bởi chuyển tới trạng thái sẳn sàng. Phương pháp định thời biểu này được dùng bởi các hệ điều hành Microsoft Windows 3.1 và bởi Apple Macintosh. Phương pháp này chỉ có thể được dùng trên các nền tảng phần cứng xác định vì nó không đòi hỏi phần cứng đặc biệt (thí dụ, một bộ đếm thời gian) được yêu cầu để định thời biểu trưng dụng. Tuy nhiên, định thời trưng dụng sinh ra một chi phí. Xét trường hợp 2 quá trình chia sẻ dữ liệu. Một quá trình có thể ở giữa giai đoạn cập nhật dữ liệu thì nó bị chiếm dụng CPU và một quá trình thứ hai đang chạy. Quá trình thứ hai có thể đọc dữ liệu mà nó hiện đang ở trong trạng thái thay đổi. Do đó, những kỹ thuật mới được yêu cầu để điều phối việc truy xuất tới dữ liệu được chia sẻ. Sự trưng dụng cũng có một ảnh hưởng trong thiết kế nhân hệ điều hành. Trong khi xử lý lời gọi hệ thống, nhân có thể chờ một hoạt động dựa theo hành vi của quá trình. Những hoạt động như thế có thể liên quan với sự thay đổi dữ liệu nhân quan trọng (thí dụ: các hàng đợi nhập/xuất). Điều gì xảy ra nếu quá trình bị trưng dụng CPU ở trong giai đoạn thay đổi này và nhân (hay trình điều khiển thiết bị) cần đọc hay sửa đổi cùng cấu trúc? Sự lộn xộn chắc chắn xảy ra. Một số hệ điều hành, gồm hầu hết các ấn bản của UNIX, giải quyết vấn đề này bằng cách chờ lời gọi hệ thống hoàn thành hay việc nhập/xuất bị nghẽn, trước khi chuyển đổi ngữ cảnh. Cơ chế này đảm bảo rằng cấu trúc nhân là đơn giản vì nhân sẽ không trưng dụng một quá trình trong khi các cấu trúc dữ liệu nhân ở trong trạng thái thay đổi. Tuy nhiên, mô hình thực thi nhân này là mô hình nghèo nàn để hỗ trợ tính toán thời thực và đa xử lý. Trong trường hợp UNIX, các phần mã vẫn là sự rủi ro. Vì các ngắt có thể xảy ra bất cứ lúc nào và vì các ngắt này không thể luôn được bỏ qua bởi nhân, nên phần mã bị ảnh hưởng bởi ngắt phải được đảm bảo từ việc sử dụng đồng thời. Hệ điều hành cần chấp nhận hầu hết các ngắt, ngược lại dữ liệu nhập có thể bị mất hay dữ liệu xuất bị viết chồng. Vì thế các phần mã này không thể được truy xuất đồng hành bởi nhiều quá trình, chúng vô hiệu hóa ngắt tại lúc nhập và cho phép các ngắt hoạt động trở lại tại thời điểm việc nhập kết thúc. Tuy nhiên, vô hiệu hóa và cho phép ngắt tiêu tốn thời gian, đặc biệt trên các hệ thống đa xử lý. III.4 Bộ phân phát Một thành phần khác liên quan đến chức năng định thời biểu CPU là bộ phân phát (dispatcher). Bộ phân phát là một module có nhiệm vụ trao điều khiển CPU tới quá trình được chọn bởi bộ định thời biểu ngắn (short-term scheduler). Chức năng này liên quan: • Chuyển ngữ cảnh • Chuyển chế độ người dùng • Nhảy tới vị trí hợp lý trong chương trình người dùng để khởi động lại quá trình Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 58
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Bộ phân phát nên nhanh nhất có thể, và nó được nạp trong mỗi lần chuyển quá trình. Thời gian mất cho bộ phân phát dừng một quá trình này và bắt đầu chạy một quá trình khác được gọi là thời gian trễ cho việc điều phối (dispatch latency). IV Các tiêu chuẩn định thời Các giải thuật định thời khác nhau có các thuộc tính khác nhau và có xu hướng thiên vị cho một loại quá trình hơn một quá trình. Trong việc chọn giải thuật nào sử dụng trong trường hợp nào, chúng ta phải xét các thuộc tính của các giải thuật khác nhau. Nhiều tiêu chuẩn được đề nghị để so sánh các giải thuật định thời biểu. Những đặc điểm được dùng để so sánh có thể tạo sự khác biệt quan trọng trong việc xác định giải thuật tốt nhất. Các tiêu chuẩn gồm: • Việc sử dụng CPU: chúng ta muốn giữ CPU bận nhiều nhất có thể. Việc sử dụng CPU có thể từ 0 đến 100%. Trong hệ thống thực, nó nên nằm trong khoảng từ 40% (cho hệ thống được nạp tải nhẹ) tới 90% (cho hệ thống được nạp tải nặng). • Thông lượng: nếu CPU bận thực thi các quá trình thì công việc đang được thực hiện. Thước đo của công việc là số lượng quá trình được hoàn thành trên một đơn vị thời gian gọi là thông lượng (throughput). Đối với các quá trình dài, tỉ lệ này có thể là 1 quá trình trên 1 giờ; đối với các giao dịch ngắn, thông lượng có thể là 10 quá trình trên giây. • Thời gian hoàn thành: từ quan điểm của một quá trình cụ thể, tiêu chuẩn quan trọng là mất bao lâu để thực thi quá trình đó. Khoảng thời gian từ thời điểm gởi quá trình tới khi quá trình hoàn thành được gọi là thời gian hoàn thành (turnaround time). Thời gian hoàn thành là tổng các thời gian chờ đưa quá trình vào bộ nhớ, chờ hàng đợi sẳn sàng, thực thi CPU và thực hiện nhập/xuất. • Thời gian chờ: giải thuật định thời CPU không ảnh hưởng lượng thời gian quá trình thực thi hay thực hiện nhập/xuất; nó ảnh hưởng chỉ lượng thời gian một quá trình phải chờ trong hàng đợi sẳn sàng. Thời gian chờ (waiting time) là tổng thời gian chờ trong hàng đợi sẳn sàng. • Thời gian đáp ứng: trong một hệ thống giao tiếp, thời gian hoàn thành không là tiêu chuẩn tốt nhất. Thông thường, một quá trình có thể tạo ra dữ liệu xuất tương đối sớm và có thể tiếp tục tính toán các kết quả mới trong khi các kết quả trước đó đang được xuất cho người dùng. Do đó, một thước đo khác là thời gian từ lúc gởi yêu cầu cho tới khi đáp ứng đầu tiên được tạo ra. Thước đo này được gọi là thời gian đáp ứng (response time), là lượng thời gian mất đi từ lúc bắt đầu đáp ứng nhưng không là thời gian mất đi để xuất ra đáp ứng đó. Thời gian hoàn thành thường bị giới hạn bởi tốc độ của thiết bị xuất. Chúng ta muốn tối ưu hóa việc sử dụng CPU và thông lượng, đồng thời tối thiểu hóa thời gian hoàn thành, thời gian chờ, và thời gian đáp ứng. Trong hầu hết các trường hợp, chúng ta tối ưu hóa thước đo trung bình. Tuy nhiên, trong một vài trường hợp chúng ta muốn tối ưu giá trị tối thiểu hay giá trị tối đa hơn là giá trị trung bình. Thí dụ, để đảm bảo rằng tất cả người dùng nhận dịch vụ tốt, chúng ta muốn tối thiểu thời gian đáp ứng tối đa. Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 59
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Đối với những hệ thống tương tác (như các hệ thống chia thời), một số nhà phân tích đề nghị rằng sự thay đổi trong thời gian đáp ứng quan trọng hơn tối thiểu hóa thời gian đáp ứng trung bình. Một hệ thống với thời gian đáp ứng phù hợp và có thể đoán trước được quan tâm nhiều hơn hệ thống chạy nhanh hơn mức trung bình nhưng biến đổi cao. Tuy nhiên, gần như không có công việc nào được thực hiện trên các giải thuật định thời biểu CPU để tối thiểu hóa các thay đổi. Khi chúng ta thảo luận các giải thuật định thời biểu CPU khác nhau, chúng ta muốn hiển thị các hoạt động của chúng. Một hình ảnh chính xác nên thông báo tới nhiều quá trình, mỗi quá trình là một chuỗi của hàng trăm chu kỳ CPU và I/O. Để đơn giản việc hiển thị, chúng ta xem chỉ một chu kỳ CPU (trong mili giây) trên quá trình trong các thí dụ của chúng ta. Thước đo của việc so sánh là thời gian chờ đợi trung bình. V Các giải thuật định thời Định thời biểu CPU giải quyết vấn đề quyết định quá trình nào trong hàng đợi sẳn sàng được cấp phát CPU. Trong phần này chúng ta mô tả nhiều giải thuật định thời CPU đang có. V.1 Định thời đến trước được phục vụ trước Giải thuật định thời biểu CPU đơn giản nhất là đến trước, được phục vụ trước (first-come, first-served-FCFS). Với cơ chế này, quá trình yêu cầu CPU trước được cấp phát CPU trước. Việc cài đặt chính sách FCFS được quản lý dễ dàng với hàng đợi FIFO. Khi một quá trình đi vào hàng đợi sẳn sàng, PCB của nó được liên kết tới đuôi của hàng đợi. Khi CPU rảnh, nó được cấp phát tới một quá trình tại đầu hàng đợi. Sau đó, quá trình đang chạy được lấy ra khỏi hàng đợi. Mã của giải thuật FCFS đơn giản để viết và hiểu. Tuy nhiên, thời gian chờ đợi trung bình dưới chính sách FCFS thường là dài. Xét tập hợp các quá trình sau đến tại thời điểm 0, với chiều dài thời gian chu kỳ CPU được cho theo mini giây. Quá trình Thời gian xử lý P1 24 P2 3 P3 3 Nếu các quá trình đến theo thứ tự P1, P2, P3 và được phục vụ theo thứ tự FCFS, chúng ta nhận được kết quả được hiển thị trong lưu đồ Gantt như sau: 24 27 30 Thời gian chờ là 0 mili giây cho quá trình P1, 24 mili giây cho quá trình P2 và 27 mili giây cho quá trình P3. Do đó, thời gian chờ đợi trung bình là (0+24+27)/3=17 mili giây. Tuy nhiên, nếu các quá trình đến theo thứ tự P2, P3, P1 thì các kết quả được hiển thị trong lưu đồ Gannt như sau: Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 60
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 0 3 6 30 Thời gian chờ đợi trung bình bây giờ là (6+0+3)/3=3 mili giây. Việc cắt giảm này là quan trọng. Do đó, thời gian chờ đợi trung bình dưới chính sách FCFS thường không là tối thiểu và có sự thay đổi rất quan trọng nếu các thời gian CPU dành cho các quá trình khác nhau rất lớn. Ngoài ra, xét năng lực của định thời FCFS trong trường hợp động. Giả sử chúng ta có một quá trình hướng xử lý (CPU-bound) và nhiều quá trình hướng nhập/xuất (I/O bound). Khi các quá trình đưa đến quanh hệ thống, ngữ cảnh sau có thể xảy ra. Quá trình hướng xử lý sẽ nhận CPU và giữ nó. Trong suốt thời gian này, tất cả quá trình khác sẽ kết thúc việc nhập/xuất của nó và chuyển vào hàng đợi sẳn sàng, các thiết bị nhập/xuất ở trạng thái rảnh. Cuối cùng, quá trình hướng xử lý kết thúc chu kỳ CPU của nó và chuyển tới thiết bị nhập/xuất. Tất cả các quá trình hướng xử lý có chu kỳ CPU rất ngắn sẽ nhanh chóng thực thi và di chuyển trở về hàng đợi nhập/xuất. Tại thời điểm này CPU ở trạng thái rảnh. Sau đó, quá trình hướng xử lý sẽ di chuyển trở lại hàng đợi sẳn sàng và được cấp CPU. Một lần nữa, tất cả quá trình hướng nhập/xuất kết thúc việc chờ trong hàng đợi sẳn sàng cho đến khi quá trình hướng xử lý được thực hiện. Có một tác dụng phụ (convoy effect) khi tất cả các quá trình khác chờ một quá trình lớn trả lại CPU. Tác dụng phụ này dẫn đến việc sử dụng thiết bị và CPU thấp hơn nếu các quá trình ngắn hơn được cấp trước. Giải thuật FCSF là giải thuật định thời không trưng dụng CPU. Một khi CPU được cấp phát tới một quá trình, quá trình đó giữ CPU cho tới khi nó giải phóng CPU bằng cách kết thúc hay yêu cầu nhập/xuất. Giải thuật FCFS đặc biệt không phù hợp đối với hệ thống chia sẻ thời gian, ở đó mỗi người dùng nhận được sự chia sẻ CPU với những khoảng thời gian đều nhau. V.2 Định thời biểu công việc ngắn nhất trước Một tiếp cận khác đối với việc định thời CPU là giải thuật định thời công việc ngắn nhất trước (shortest-job-first-SJF). Giải thuật này gán tới mỗi quá trình chiều dài của chu kỳ CPU tiếp theo cho quá trình sau đó. Khi CPU sẳn dùng, nó được gán tới quá trình có chu kỳ CPU kế tiếp ngắn nhất. Nếu hai quá trình có cùng chiều dài chu kỳ CPU kế tiếp, định thời FCFS được dùng. Chú ý rằng thuật ngữ phù hợp hơn là chu kỳ CPU kế tiếp ngắn nhất (shortest next CPU burst) vì định thời được thực hiện bằng cách xem xét chiều dài của chu kỳ CPU kế tiếp của quá trình hơn là toàn bộ chiều dài của nó. Chúng ta dùng thuật ngữ SJF vì hầu hết mọi người và mọi sách tham khảo tới nguyên lý của loại định thời biểu này như SJF. Thí dụ, xét tập hợp các quá trình sau, với chiều dài của thời gian chu kỳ CPU được tính bằng mili giây: Quá trình Thời gian xử lý P1 6 P2 8 P3 7 P4 3 Dùng định thời SJF, chúng ta định thời biểu cho các quá trình này theo lưu đồ Gannt như sau: Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 61
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 0 3 9 16 24 Thời gian chờ đợi là 3 mili giây cho quá trình P1, 16 mili giây cho quá trình P2, 9 mili giây cho quá trình P3, và 0 mili giây cho quá trình P4. Do đó, thời gian chờ đợi trung bình là (3+16+9+0)/4 = 7 mili giây. Nếu chúng ta dùng cơ chế định thời FCFS thì thời gian chờ đợi trung bình là 10.23 mili giây. Giải thuật SJF có thể là tối ưu, trong đó nó cho thời gian chờ đợi trung bình nhỏ nhất cho các quá trình được cho. Bằng cách chuyển một quá trình ngắn trước một quá trình dài thì thời gian chờ đợi của quá trình ngắn giảm hơn so với việc tăng thời gian chờ đợi của quá trình dài. Do đó, thời gian chờ đợi trung bình giảm. Khó khăn thật sự với giải thuật SJF là làm thế nào để biết chiều dài của yêu cầu CPU tiếp theo. Đối với định thời dài trong hệ thống bó, chúng ta có thể dùng chiều dài như giới hạn thời gian xử lý mà người dùng xác định khi gởi công việc. Do đó, người dùng được cơ động để ước lượng chính xác giới hạn thời gian xử lý vì giá trị thấp hơn có nghĩa là đáp ứng nhanh hơn. Định thời SJF được dùng thường xuyên trong định thời dài. Mặc dù SJF là tối ưu nhưng nó không thể được cài đặt tại cấp định thời CPU ngắn vì không có cách nào để biết chiều dài chu kỳ CPU tiếp theo. Một tiếp cận là khác gần đúng định thời SJF được thực hiện. Chúng ta có thể không biết chiều dài của chu kỳ CPU kế tiếp nhưng chúng ta có đoán giá trị của nó. Chúng ta mong muốn rằng chu kỳ CPU kế tiếp sẽ tương tự chiều dài những chu kỳ CPU trước đó. Do đó, bằng cách tính toán mức xấp xỉ chiều dài của chu kỳ CPU kế tiếp, chúng ta chọn một quá trình với chu kỳ CPU được đoán là ngắn nhất. Chu kỳ CPU kế tiếp thường được đoán như trung bình số mũ của chiều dài các chu kỳ CPU trước đó. Gọi tn là chiều dài của chu kỳ CPU thứ n và gọi Tn+1 giá trị được đoán cho chu kỳ CPU kế tiếp. Thì đối với α, với 0 ≤ α ≤ 1, định nghĩa Tn+1 = α tn + (1- α) Tn Công thức này định nghĩa một giá trị trung bình số mũ. Giá trị của tn chứa thông tin mới nhất; Tn lưu lịch sử quá khứ. Tham số α điều khiển trọng số liên quan giữa lịch sử quá khứ và lịch sử gần đây trong việc đoán. Nếu α=0 thì Tn+1=Tn và lịch sử gần đây không có ảnh hưởng (điều kiện hiện hành được đảm bảo là ngắn); nếu α =1 thì Tn+1=tn và chỉ chu kỳ CPU gần nhất có ảnh hưởng (lịch sử được đảm bảo là cũ và không phù hợp). Thông dụng hơn, α=1/2 thì lịch sử gần đây và lịch sử quá khứ có trọng số tương đương. Giá trị khởi đầu T0 có thể được định nghĩa như một hằng số hay như toàn bộ giá trị trung bình hệ thống. Hình IV.2 dưới đây hiển thị giá trị trung bình dạng mũ với α=1/2 và T0=10. Để hiểu hành vi của giá trị trung bình dạng mũ, chúng ta có thể mở rộng công thức cho Tn+1 bằng cách thay thế Tn để tìm Tn+1=α tn+(1-α) α tn-1+…+(1-α)j α tn-j+…+(1-α)n - 1T0 Vì cả hai α và (1- α) là nhỏ hơn hay bằng 1, mỗi số hạng tiếp theo có trọng số nhỏ hơn số hạng trước đó. Giải thuật SJF có thể trưng dụng hoặc không trưng dụng CPU. Chọn lựa này phát sinh khi một quá trình mới đến tại hàng đợi sẳn sàng trong khi một quá trình trước đó đang thực thi. Một quá trình mới có thể có chu kỳ CPU tiêp theo ngắn hơn chu kỳ CPU được để lại của quá trình thực thi hiện tại. Giải thuật SJF trưng dụng sẽ trưng dungj CPU của quá trình đang thực thi hiện tại, trong khi giải thuật SJF không trưng dụng sẽ cho phép quá trình đang thực thi kết thúc chu kỳ CPU của nó. Định thời Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 62
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 SJF trưng dụng còn được gọi là định thời thời gian còn lại ngắn nhất trước (shortest-remaining-time-first). Hình 0-2 Đoán chiều dài của chu kỳ CPU kế tiếp Thí dụ, xét 4 quá trình sau với chiều dài của thời gian chu kỳ CPU được cho tính bằng mili giây Quá trình Thời gian đến Thời gian xử lý P1 0 8 P2 1 4 P3 2 9 P4 3 5 Nếu các quá trình đi vào hàng đợi sẳn sàng tại những thời điểm và cần thời gian xử lý được hiển thị trong bảng trên thì thời biểu SJF trưng dụng được mô tả trong lưu đồ Gannt như sau: P1 P2 P3 0 1 5 10 17 26 Quá trình P1 được bắt đầu tại thời điểm 0, vì nó là quá trình duy nhất trong hàng đợi. Quá trình P2 đến tại thời điểm 1. Thời gian còn lại cho P1 (7 mili giây) là lớn hơn thời gian được yêu cầu bởi quá trình P2 (4 mili giây) vì thế quá trình P1 bị trưng dụng CPU và quá trình P2 được định thời biểu. Thời gian chờ đợi trung bình cho thí dụ này là: ((10-1) + (1-1) + (17-2) + (5-3))/4 = 6.5 mili giây. Định thời SJF không trưng dụng cho kết quả thời gian chờ đợi trung bình là 7.75 mili giây. V.3 Định thời theo độ ưu tiên Giải thuật SJF là trường hợp đặc biệt của giải thuật định thời theo độ ưu tiên (priority-scheduling algorithm). Độ ưu tiên được gán với mỗi quá trình và CPU được cấp phát tới quá trình với độ ưu tiên cao nhất. Quá trình có độ ưu tiên bằng nhau được định thời trong thứ tự FCFS. Giải thuật SJF là giải thuật ưu tiên đơn giản ở đó độ ưu tiên p là nghịch đảo với chu kỳ CPU được đoán tiếp theo. Chu kỳ CPU lớn hơn có độ ưu tiên thấp hơn và ngược lại. Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 63
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Bây giờ chúng ta thảo luận định thời có độ ưu tiên cao và thấp. Các độ ưu tiên thường nằm trong dãy số cố định, chẳng hạn 0 tới 7 hay 0 tới 4,095. Tuy nhiên, không có sự thoả thuận chung về 0 là độ ưu tiên thấp nhất hay cao nhất. Một vài hệ thống dùng số thấp để biểu diễn độ ưu tiên thấp; ngược lại các hệ thống khác dùng các số thấp cho độ ưu tiên cao. Sự khác nhau này có thể dẫn đến sự lẫn lộn. Trong giáo trình này chúng ta dùng các số thấp để biểu diễn độ ưu tiên cao. Thí dụ, xét tập hợp quá trình sau đến tại thời điểm 0 theo thứ tự P1, P2,…, P5 với chiều dài thời gian chu kỳ CPU được tính bằng mili giây: Quá trình Thời gian xử lý Độ ưu tiên P1 10 3 P2 1 1 P3 2 4 P4 1 5 P5 5 2 Sử dụng định thời theo độ ưu tiên, chúng ta sẽ định thời các quá trình này theo lưu đồ Gannt như sau: P2 P5 P1 P3 P4 0 1 6 16 18 19 Thời gian chờ đợi trung bình là 8.2 mili giây. Độ ưu tiên có thể được định nghĩa bên trong hay bên ngoài. Độ ưu tiên được định nghĩa bên trong thường dùng định lượng hoặc nhiều định lượng có thể đo để tính toán độ ưu tiên của một quá trình. Thí dụ, các giới hạn thời gian, các yêu cầu bộ nhớ, số lượng tập tin đang mở và tỉ lệ của chu kỳ nhập/xuất trung bình với tỉ lệ của chu kỳ CPU trung bình. Các độ ưu tiên bên ngoài được thiết lập bởi các tiêu chuẩn bên ngoài đối với hệ điều hành như sự quan trọng của quá trình, loại và lượng chi phí đang được trả cho việc dùng máy tính, văn phòng hỗ trợ công việc, .. Định thời biểu theo độ ưu tiên có thể trưng dụng hoặc không trưng dụng CPU. Khi một quá trình đến hàng đợi sẳn sàng, độ ưu tiên của nó được so sánh với độ ưu tiên của quá trình hiện đang chạy. Giải thuật định thời theo độ ưu tiên trưng dụng sẽ chiếm CPU nếu độ ưu tiên của quá trình mới đến cao hơn độ ưu tiên của quá trình đang thực thi. Giải thuật định thời theo độ ưu tiên không trưng dụng sẽ đơn giản đặt quá trình mới tại đầu hàng đợi sẳn sàng. Vấn đề chính với giải thuật định thời theo độ ưu tiên là nghẽn không hạn định (indefinite blocking) hay đói CPU (starvation). Một quá trình sẳn sàng chạy nhưng thiếu CPU có thể xem như bị nghẽn-chờ đợi CPU. Giải thuật định thời theo độ ưu tiên có thể để lại nhiều quá trình có độ ưu tiên thấp chờ CPU không hạn định. Trong một hệ thống máy tính tải cao, dòng đều đặn các quá trình có độ ưu tiên cao hơn có thể ngăn chặn việc nhận CPU của quá trình có độ ưu tiên thấp.. Thông thường, một trong hai trường hợp xảy ra. Cuối cùng, một quá trình sẽ được chạy (lúc 2 a.m chủ nhật là thời điểm cuối cùng hệ thống nạp các quá trình nhẹ), hay cuối cùng hệ thống máy tính sẽ đổ vỡ và mất tất cả các quá trình có độ ưu tiên thấp chưa được kết thúc. Một giải pháp cho vấn đề nghẽn không hạn định này là sự hoá già (aging). Hóa già là kỹ thuật tăng dần độ ưu tiên của quá trình chờ trong hệ thống một thời gian dài. Thí dụ, nếu các độ ưu tiên nằm trong dãy từ 127 (thấp) đến 0 (cao), chúng ta giảm độ ưu tiên của quá trình đang chờ xuống 1 mỗi 15 phút. Cuối cùng, thậm chí một quá Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 64
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 trình với độ ưu tiên khởi đầu 127 sẽ đạt độ ưu tiên cao nhất trong hệ thống và sẽ được thực thi. Thật vậy, một quá trình sẽ mất không quá 32 giờ để đạt được độ ưu tiên từ 127 tới 0. V.4 Định thời luân phiên Giải thuật định thời luân phiên (round-robin scheduling algorithm-RR) được thiết kế đặc biệt cho hệ thống chia sẻ thời gian. Tương tự như định thời FCFS nhưng sự trưng dụng CPU được thêm vào để chuyển CPU giữa các quá trình. Đơn vị thời gian nhỏ được gọi là định mức thời gian (time quantum) hay phần thời gian (time slice) được định nghĩa. Định mức thời gian thường từ 10 đến 100 mili giây. Hàng đợi sẳn sàng được xem như một hàng đợi vòng. Bộ định thời CPU di chuyển vòng quanh hàng đợi sẳn sàng, cấp phát CPU tới mỗi quá trình có khoảng thời gian tối đa bằng một định mức thời gian. Để cài đặt định thời RR, chúng ta quản lý hàng đợi sẳn sàng như một hàng đợi FIFO của các quá trình. Các quá trình mới được thêm vào đuôi hàng đợi. Bộ định thời CPU chọn quá trình đầu tiên từ hàng đợi sẳn sàng, đặt bộ đếm thời gian để ngắt sau 1 định mức thời gian và gởi tới quá trình. Sau đó, một trong hai trường hợp sẽ xảy ra. Quá trình có 1 chu kỳ CPU ít hơn 1 định mức thời gian. Trong trường hợp này, quá trình sẽ tự giải phóng. Sau đó, bộ định thời biểu sẽ xử lý quá trình tiếp theo trong hàng đợi sẳn sàng. Ngược lại, nếu chu kỳ CPU của quá trình đang chạy dài hơn 1 định mức thời gian thì độ đếm thời gian sẽ báo và gây ra một ngắt tới hệ điều hành. Chuyển đổi ngữ cảnh sẽ được thực thi và quá trình được đặt trở lại tại đuôi của hàng đợi sẳn sàng. Sau đó, bộ định thời biểu CPU sẽ chọn quá trình tiếp theo trong hàng đợi sẳn sàng. Tuy nhiên, thời gian chờ đợi trung bình dưới chính sách RR thường là quá dài. Xét một tập hợp các quá trình đến tại thời điểm 0 với chiều dài thời gian CPU-burst được tính bằng mili giây: Quá trình Thời gian xử lý P1 24 P2 3 P3 3 Nếu sử dụng định mức thời gian là 4 mili giây thì quá trình P1 nhận 4 mili giây đầu tiên. Vì nó yêu cầu 20 mili giây còn lại nên nó bị trưng dụng CPU sau định mức thời gian đầu tiên và CPU được cấp tới quá trình tiếp theo trong hàng đợi, quá trình P2. Vì P2 không cần tới 4 mili giây nên nó kết thúc trước khi định mức thời gian của nó hết hạn. Sau đó, CPU được cho tới quá trình kế tiếp, quá trình P3. Một khi mỗi quá trình nhận 1 định mức thời gian thì CPU trả về quá trình P1 cho định mức thời gian tiếp theo. Thời biểu RR là: 0 4 7 10 14 18 22 26 30 Thời gian chờ đợi trung bình là 17/3=5.66 mili giây. Trong giải thuật RR, không quá trình nào được cấp phát CPU cho nhiều hơn 1 định mức thời gian trong một hàng. Nếu chu kỳ CPU của quá trình vượt quá 1 định Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 65
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 mức thời gian thì quá trình đó bị trưng dụng CPU và nó được đặt trở lại hàng đợi sẳn sàng. Giải thuật RR là giải thuật trưng dụng CPU. Nếu có n quá trình trong hàng đợi sẳn sàng và định mức thời gian là q thì mỗi quá trình nhận 1/n thời gian CPU trong các phần, nhiều nhất q đơn vị thời gian. Mỗi quá trình sẽ chờ không dài hơn (n-1)x q đơn vị thời gian cho tới khi định mức thời gian tiếp theo của nó. Thí dụ, nếu có 5 quá trình với định mức thời gian 20 mili giây thì mỗi quá trình sẽ nhận 20 mili giây sau mỗi 100 mili giây. Năng lực của giải thuật RR phụ thuộc nhiều vào kích thước của định mức thời gian. Nếu định mức thời gian rất lớn (lượng vô hạn) thì chính sách RR tương tự như chính sách FCFS. Nếu định mức thời gian là rất nhỏ (1 mili giây) thì tiếp cận RR được gọi là chia sẻ bộ xử lý (processor sharing) và xuất hiện (trong lý thuyết) tới người dùng như thể mỗi quá trình trong n quá trình có bộ xử lý riêng của chính nó chạy tại 1/n tốc độ của bộ xử lý thật. Hình 0-3 Hiển thị một định mức thời gian nhỏ hơn tăng chuyển đổi ngữ cảnh như thế nào Tuy nhiên, trong phần mềm chúng ta cũng cần xem xét hiệu quả của việc chuyển đổi ngữ cảnh trên năng lực của việc định thời RR. Chúng ta giả sử rằng chỉ có 1 quá trình với 10 đơn vị thời gian. Nếu một định mức là 12 đơn vị thời gian thì quá trình kết thúc ít hơn 1 định mức thời gian, với không có chi phí nào khác. Tuy nhiên, nếu định mức là 6 đơn vị thời gian thì quá trình cần 2 định mức thời gian, dẫn đến 1 chuyển đổi ngữ cảnh. Nếu định mức thời gian là 1 đơn vị thời gian thì 9 chuyển đổi ngữ cảnh sẽ xảy ra, việc thực thi của quá trình bị chậm như được hiển thị trong hình IV.3 . Do đó chúng ta mong muốn định mức thời gian lớn đối với thời gian chuyển ngữ cảnh. Nếu thời gian chuyển ngữ cảnh chiếm 10% định mức thời gian thì khoảng 10% thời gian CPU sẽ được dùng cho việc chuyển ngữ cảnh. Thời gian hoàn thành cũng phụ thuộc kích thước của định mức thời gian. Chúng ta có thể thấy trong hình IV.4, thời gian hoàn thành trung bình của tập hợp các quá trình không cần cải tiến khi kích thước định mức thời gian tăng. Thông thường, thời gian hoàn thành trung bình có thể được cải tiến nếu hầu hết quá trình kết thúc chu kỳ CPU kế tiếp của chúng trong một định mức thời gian. Thí dụ, cho 3 quá trình có 10 đơn vị thời gian cho mỗi quá trình và định mức thời gian là 1 đơn vị thời gian, thì thời gian hoàn thành trung bình là 29. Tuy nhiên, nếu định mức thời gian là 10 thì thời gian hoàn thành trung bình giảm tới 20. Nếu thời gian chuyển ngữ cảnh được thêm vào thì thời gian hoàn thành trung bình gia tăng đối với định mức thời gian nhỏ hơn vì các chuyển đổi ngữ cảnh thêm nữa sẽ được yêu cầu. Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 66
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Hình 0-4 Hiển thị cách thời gian hoàn thành biến đổi theo định mức thời gian Ngoài ra, nếu định mức thời gian quá lớn thì người thiết kế việc định thời RR bao gồm chính sách FCFS. Qui tắc là định mức thời gian nên dài hơn 80% chu kỳ CPU. V.5 Định thời biểu với hàng đợi nhiều cấp Một loại giải thuật định thời khác được tạo ra cho những trường hợp mà trong đó các quá trình được phân lớp thành các nhóm khác nhau. Thí dụ: việc phân chia thông thường được thực hiện giữa các quá trình chạy ở chế độ giao tiếp (foreground hay interactive) và các quá trình chạy ở chế độ nền hay dạng bó (background hay batch). Hai loại quá trình này có yêu cầu đáp ứng thời gian khác nhau và vì thế có yêu cầu về định thời biểu khác nhau. Ngoài ra, các quá trình chạy ở chế độ giao tiếp có độ ưu tiên (hay được định nghĩa bên ngoài) cao hơn các quá trình chạy ở chế độ nền. Một giải thuật định thời hàng đợi nhiều cấp (multilevel queue-scheduling algorithm) chia hàng đợi thành nhiều hàng đợi riêng rẻ (hình IV.5). Các quá trình được gán vĩnh viễn tới một hàng đợi, thường dựa trên thuộc tính của quá trình như kích thước bộ nhớ, độ ưu tiên quá trình hay loại quá trình. Mỗi hàng đợi có giải thuật định thời của chính nó. Thí dụ: các hàng đợi riêng rẻ có thể được dùng cho các quá trình ở chế độ nền và chế độ giao tiếp. Hàng đợi ở chế độ giao tiếp có thể được định thời bởi giải thuật RR trong khi hàng đợi ở chế độ nền được định thời bởi giải thuật FCFS. Ngoài ra, phải có việc định thời giữa các hàng đợi, mà thường được cài đặt như định thời trưng dụng với độ ưu tiên cố định. Thí dụ, hàng đợi ở chế độ giao tiếp có độ ưu tiên tuyệt đối hơn hàng đợi ở chế độ nền. Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 67
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Hình 0-5 Định thời hàng đợi nhiều mức Chúng ta xét một thí dụ của giải thuật hàng đợi nhiều mức với năm hàng đợi: • Các quá trình hệ thống • Các quá trình giao tiếp • Các quá trình soạn thảo giao tiếp • Các quá trình bó • Các quá trình sinh viên Mỗi hàng đợi có độ ưu tiên tuyệt đối hơn hàng đợi có độ ưu tiên thấp hơn. Thí dụ: không có quá trình nào trong hàng đợi bó có thể chạy trừ khi hàng đợi cho các quá trình hệ thống, các quá trình giao tiếp và các quá trình soạn thảo giao tiếp đều rỗng. Nếu một quá trình soạn thảo giao tiếp được đưa vào hàng đợi sẳn sàng trong khi một quá trình bó đang chạy thì quá trình bó bị trưng dụng CPU. Solaris 2 dùng dạng giải thuật này. Một khả năng khác là phần (slice) thời gian giữa hai hàng đợi. Mỗi hàng đợi nhận một phần thời gian CPU xác định, sau đó nó có thể định thời giữa các quá trình khác nhau trong hàng đợi của nó. Thí dụ, trong hàng đợi giao tiếp-nền, hàng đợi giao tiếp được cho 80% thời gian của CPU cho giải thuật RR giữa các quá trình của nó, ngược lại hàng đợi nền nhận 20% thời gian CPU cho các quá trình của nó theo cách FCFS. V.6 Định thời hàng đợi phản hồi đa cấp Thông thường, trong giải thuật hàng đợi đa cấp, các quá trình được gán vĩnh viễn tới hàng đợi khi được đưa vào hệ thống. Các quá trình không di chuyển giữa các hàng đợi. Nếu có các hàng đợi riêng cho các quá trình giao tiếp và các quá trình nền thì các quá trình không di chuyển từ một hàng đợi này tới hàng đợi khác vì các quá trình không thay đổi tính tự nhiên giữa giao tiếp và nền. Cách tổ chức có ích vì chi phí định thời thấp nhưng thiếu linh động và có thể dẫn đến tình trạng “đói CPU”. Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 68
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Hình 0-6 Các hàng đợi phản hồi nhiều cấp Tuy nhiên, định thời hàng đợi phản hồi đa cấp (multilevel feedback queue scheduling) cho phép một quá trình di chuyển giữa các hàng đợi. Ý tưởng là tách riêng các quá trình với các đặc điểm chu kỳ CPU khác nhau. Nếu một quá trình dùng quá nhiều thời gian CPU thì nó sẽ được di chuyển tới hàng đợi có độ ưu tiên thấp. Cơ chế này để lại các quá trình hướng nhập/xuất và các quá trình giao tiếp trong các hàng đợi có độ ưu tiên cao hơn. Tương tự, một quá trình chờ quá lâu trong hàng đợi có độ ưu tiên thấp hơn có thể được di chuyển tới hàng đợi có độ ưu tiên cao hơn. Đây là hình thức của sự hóa già nhằm ngăn chặn sự đói CPU. Thí dụ, xét một bộ định thời hàng đợi phản hồi nhiều cấp với ba hàng đợi được đánh số từ 0 tới 2 (như hình IV.6). Bộ định thời trước tiên thực thi tất cả quá trình chứa trong hàng đợi 0. Chỉ khi hàng đợi 0 rỗng nó sẽ thực thi các quá trình trong hàng đợi 1. Tương tự, các quá trình trong hàng đợi 2 sẽ được thực thi chỉ nếu hàng đợi 0 và 1 rỗng. Một quá trình đến hàng đợi 1 sẽ ưu tiên hơn quá trình đến hàng đợi 2. Tương tự, một quá trình đến hàng đợi 0 sẽ ưu tiên hơn một quá trình vào hàng đợi 1. Một quá trình đưa vào hàng đợi sẳn sàng được đặt trong hàng đợi 0. Một quá trình trong hàng đợi 0 được cho một định mức thời gian là 8 mili giây. Nếu nó không kết thúc trong thời gian này thì nó sẽ di chuyển vào đuôi của hàng đợi 1. Nếu hàng đợi 0 rỗng thì quá trình tại đầu của hàng đợi 1 được cho định mức thời gian là 16 mili giây. Nếu nó không hoàn thành thì nó bị chiếm CPU và được đặt vào hàng đợi 2. Các quá trình trong hàng đợi 2 được chạy trên cơ sở FCFS chỉ khi hàng đợi 0 và 1 rỗng. Giải thuật định thời này cho độ ưu tiên cao nhất tới bất cứ quá trình nào với chu kỳ CPU 8 mili giây hay ít hơn. Một quá trình như thế sẽ nhanh chóng nhận CPU, kết thúc chu kỳ CPU của nó và bỏ đi chu kỳ I/O kế tiếp của nó. Các quá trình cần hơn 8 mili giây nhưng ít hơn 24 mili giây được phục vụ nhanh chóng mặc dù với độ ưu tiên thấp hơn các quá trình ngắn hơn. Các quá trình dài tự động rơi xuống hàng đợi 2 và được phục vụ trong thứ tự FCFS với bất cứ chu kỳ CPU còn lại từ hàng đợi 0 và 1. Nói chung, một bộ định thời hàng đợi phản hồi nhiều cấp được định nghĩa bởi các tham số sau: • Số lượng hàng đợi • Giải thuật định thời cho mỗi hàng đợi • Phương pháp được dùng để xác định khi nâng cấp một quá trình tới hàng đợi có độ ưu tiên cao hơn. • Phương pháp được dùng để xác định khi nào chuyển một quá trình tới hàng đợi có độ ưu tiên thấp hơn. Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 69
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 • Phương pháp được dùng để xác định hàng đợi nào một quá trình sẽ đi vào và khi nào quá trình đó cần phục vụ. Định nghĩa bộ định thời biểu dùng hàng đợi phản hồi nhiều cấp trở thành giải thuật định thời CPU phổ biến nhất. Bộ định thời này có thể được cấu hình để thích hợp với hệ thống xác định. Tuy nhiên, bộ định thời này cũng yêu cầu một vài phương tiện chọn lựa giá trị cho tất cả tham số để định nghĩa bộ định thời biểu tốt nhất. Mặc dù một hàng đợi phản hồi nhiều cấp là cơ chế phổ biến nhất nhưng nó cũng là cơ chế phức tạp nhất. VI Định thời biểu đa bộ xử lý Phần trên thảo luận chúng ta tập trung vào những vấn đề định thời biểu CPU trong một hệ thống với một bộ vi xử lý đơn. Nếu có nhiều CPU, vấn đề định thời tương ứng sẽ phức tạp hơn. Nhiều khả năng đã được thử nghiệm và như chúng ta đã thấy với định thời CPU đơn bộ xử lý, không có giải pháp tốt nhất. Trong phần sau đây, chúng ta sẽ thảo luận vắn tắt một số vấn đề tập trung về định thời biểu đa bộ xử lý. Chúng ta tập trung vào những hệ thống mà các bộ xử lý của nó được xác định (hay đồng nhất) trong thuật ngữ chức năng của chúng; bất cứ bộ xử lý nào sẳn có thì có thể được dùng để chạy bất quá trình nào trong hàng đợi. Chúng ta cũng cho rằng truy xuất bộ nhớ là đồng nhất (uniform memory access-UMA). Chỉ những chương trình được biên dịch đối với tập hợp chỉ thị của bộ xử lý được cho mới có thể được chạy trên chính bộ xử lý đó. Ngay cả trong một bộ đa xử lý đồng nhất đôi khi có một số giới hạn cho việc định thời biểu. Xét một hệ thống với một thiết bị nhập/xuất được gán tới một đường bus riêng của một bộ xử lý. Các quá trình muốn dùng thiết bị đó phải được định thời biểu để chạy trên bộ xử lý đó, ngược lại thiết bị đó là không sẳn dùng. Nếu nhiều bộ xử lý xác định sẳn dùng thì chia sẻ tải có thể xảy ra. Nó có thể cung cấp một hàng đợi riêng cho mỗi bộ xử lý. Tuy nhiên, trong trường hợp này, một bộ xử lý có thể rảnh với hàng đợi rỗng, trong khi bộ xử lý khác rất bận. Để ngăn chặn trường hợp này, chúng ta dùng một hàng đợi sẳn sàng chung. Tất cả quá trình đi vào một hàng đợi và được định thời biểu trên bất cứ bộ xử lý sẳn dùng nào. Trong một cơ chế như thế, một trong hai tiếp cận định thời biểu có thể được dùng. Trong tiếp cận thứ nhất, mỗi bộ xử lý định thời chính nó. Mỗi bộ xử lý xem xét hàng đợi sẳn sàng chung và chọn một quá trình để thực thi. Nếu chúng ta có nhiều bộ xử lý cố gắng truy xuất và cập nhật một cấu trúc dữ liệu chung thì mỗi bộ xử lý phải được lập trình rất cẩn thận. Chúng ta phải đảm bảo rằng hai bộ xử lý không chọn cùng quá trình và quá trình đó không bị mất từ hàng đợi. Tiếp cận thứ hai tránh vấn đề này bằng cách đề cử một bộ xử lý như bộ định thời cho các quá trình khác, do đó tạo ra cấu trúc chủ-tớ (master-slave). Một vài hệ thống thực hiện cấu trúc này từng bước bằng cách tất cả quyết định định thời, xử lý nhập/xuất và các hoạt động hệ thống khác được quản lý bởi một bộ xử lý đơn-một server chủ. Các bộ xử lý khác chỉ thực thi mã người dùng. Đa xử lý không đối xứng (asymmetric multiprocessing) đơn giản hơn đa xử lý đối xứng (symmetric multiprocessing) vì chỉ một quá trình truy xuất các cấu trúc dữ liệu hệ thống, làm giảm đi yêu cầu chia sẻ dữ liệu. Tuy nhiên, nó cũng không hiệu quả. Các quá trình giới hạn nhập/xuất có thể gây thắt cổ chai (bottleneck) trên một CPU đang thực hiện tất cả các hoạt động. Điển hình, đa xử lý không đối xứng được cài đặt trước trong một hệ điều hành và sau đó được nâng cấp tới đa xử lý đối xứng khi hệ thống tiến triển. Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 70
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 VII Định thời thời gian thực Trong chương đầu chúng ta đã tìm hiểu tổng quan về hệ điều hành thời thực và thảo luận tầm quan trọng của nó. Ở đây, chúng ta tiếp tục thảo luận bằng cách mô tả các điều kiện thuận lợi định thời cần để hỗ trợ tính toán thời thực trong hệ thống máy tính đa mục đích. Tính toán thời thực được chia thành hai loại: hệ thống thời thực cứng (hardware real-time systems) được yêu cầu để hoàn thành một tác vụ tới hạn trong lượng thời gian được đảm bảo. Thông thường, một quá trình được đưa ra xem xét cùng với khai báo lượng thời gian nó cần để hoàn thành hay thực hiện nhập/xuất. Sau đó, bộ định thời biểu nhận được quá trình, đảm bảo rằng quá trình sẽ hoàn thành đúng giờ hay từ chối yêu cầu khi không thể. Điều này được gọi là đặt trước tài nguyên (resource reservation). Để đảm bảo như thế đòi hỏi bộ định thời biết chính xác bao lâu mỗi loại chức năng hệ điều hành mất để thực hiện và do đó mỗi thao tác phải được đảm bảo để mất lượng thời gian tối đa. Một đảm bảo như thế là không thể trong hệ thống với lưu trữ phụ và bộ nhớ ảo vì các hệ thống con này gây ra sự biến đổi không thể tránh hay không thể thấy trước trong lượng thời gian thực thi một quá trình xác định. Do đó, hệ thống thời thực cứng được hình thành từ nhiều phần mềm có mục đích đặc biệt chạy trên phần cứng tận hiến cho các quá trình tới hạn, và thiếu chức năng đầy đủ của các máy tính và các hệ điều hành hiện đại. Tính toán thời gian thực mềm (soft real-time computing) ít nghiêm khắc hơn. Nó yêu cầu các quá trình tới hạn nhận độ ưu tiên cao hơn các quá trình khác. Mặc dù thêm chức năng thời thực mềm tới hệ chia sẻ thời gian có thể gây ra việc cấp phát tài nguyên không công bằng và có thể dẫn tới việc trì hoãn lâu hơn hay thậm chí đói tài nguyên đối với một số quá trình, nhưng nó ít có thể đạt được. Kết quả là hệ thống mục đích chung cũng có thể hỗ trợ đa phương tiện, đồ họa giao tiếp tốc độ cao, và nhiều tác vụ khác nhưng không hỗ trợ tính toán thời thực mềm. Cài đặt chức năng thời thực mềm đòi hỏi thiết kế cẩn thận bộ định thời biểu và các khía cạnh liên quan của hệ điều hành. Trước tiên, hệ thống phải có định thời trưng dụng và các quá trình thời thực phải có độ ưu tiên cao nhất. Độ ưu tiên của các quá trình thời thực phải không giảm theo thời gian mặc dù độ ưu tiên của các quá trình không thời thực có thể giảm. Thứ hai, độ trễ của việc điều phối phải nhỏ. Một quá trình thời thực nhỏ hơn, nhanh hơn có thể bắt đầu thực thi một khi nó có thể chạy. Quản trị các thuộc tính đã được xem xét ở trên là tương đối đơn giản. Thí dụ, chúng ta có thể không cho phép một quá trình hóa già trên các quá trình thời thực, do đó đảm bảo rằng độ ưu tiên của các quá trình không thay đổi. Tuy nhiên, đảm bảo thuộc tính sau đây phức tạp hơn. Vấn đề là nhiều hệ điều hành gồm hầu hết ấn bản của UNIX bị bắt buộc chờ lời gọi hệ thống hoàn thành hay nghẽn nhập/xuất xảy ra trước khi thực hiện chuyển ngữ cảnh. Độ trễ điều phối trong những hệ thống như thế có thể dài vì một số lời gọi hệ thống phức tạp và một vài thiết bị nhập/xuất chậm. Để giữ độ trễ điều phối chậm, chúng ta cần cho phép các lời gọi hệ thống được trưng dụng. Có nhiều cách để đạt mục đích này. Cách thứ nhất là chèn các điểm trưng dụng (preemption points) trong những lời gọi hệ thống có khoảng thời gian dài, kiểm tra để thấy quá trình ưu tiên cao cần được thực thi hay không. Nếu đúng, thì chuyển ngữ cảnh xảy ra và khi quá trình có độ ưu tiên kết thúc, quá trình bị ngắt tiếp tục với lời gọi hệ thống. Các điểm trưng dụng chỉ có thể được đặt tại vị trí “an toàn” trong nhân- nơi mà những cấu trúc dữ liệu hiện tại không được cập nhật. Ngay cả với độ trễ điều phối trưng dụng có thể lớn vì chỉ một vài điểm trưng dụng có thể được thêm vào nhân trong thực tế. Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 71
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Một phương pháp khác để giải quyết sự trưng dụng là làm toàn bộ nhân có thể trưng dụng. Để đảm bảo các họat động thực hiện đúng, tất cả cấu trúc dữ liệu nhân phải được bảo vệ thông qua việc sử dụng các cơ chế đồng bộ hóa. Với phương pháp này, nhân luôn có thể trưng dụng vì bất cứ dữ liệu nhân được cập nhật được bảo vệ từ việc sửa đổi bởi quá trình có độ ưu tiên cao. Đây là một phương pháp hiệu quả nhất trong việc sử dụng rộng rãi; nó được dùng trong Solaris 2. Hình 0-7 Độ trễ gửi Nhưng điều gì xảy ra nếu quá trình có độ ưu tiên cao cần đọc hay sửa đổi dữ liệu nhân hiện đang được truy xuất bởi quá trình khác có độ ưu tiên thấp hơn? Quá trình có độ ưu tiên cao đang chờ quá trình có độ ưu tiên thấp kết thúc. Trường hợp này được gọi là đảo ngược độ ưu tiên (prioprity inversion). Thật vậy, một chuỗi các quá trình đang truy xuất tài nguyên mà quá trình có độ ưu tiên cao cần. Vấn đề này có thể giải quyết bằng giao thức kế thừa độ ưu tiên (priority-inheritance protocol) trong đó tất cả quá trình này (các quá trình này truy xuất tài nguyên mà quá trình có độ ưu tiên cao cần) kế thừa độ ưu tiên cao cho đến khi chúng được thực hiện với tài nguyên trong câu hỏi. Khi chúng kết thúc, độ ưu tiên của chúng chuyển trở lại giá trị ban đầu của nó. Trong hình IV.7, chúng ta hiển thị sự thay đổi của độ trễ điều phối. Giai đoạn xung đột (conflict phase) của độ trễ điều phối có hai thành phần: • Sự trưng dụng của bất cứ quá trình nào đang chạy trong nhân • Giải phóng tài nguyên các quá trình có độ ưu tiên thấp được yêu cầu bởi quá trình có độ ưu tiên cao Thí dụ, trong Solaris 2 độ trễ điều phối với sự trưng dụng bị vô hiệu hóa khi vượt qua 100 mili giây. Tuy nhiên, độ trễ điều phối với sự trưng dụng được cho phép thường được giảm xuống tới 2 mili giây. Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 72
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 VIII Đánh giá giải thuật Chúng ta chọn một giải thuật định thời CPU cho một hệ thống xác định như thế nào? Có nhiều giải thuật định thời, mỗi giải thuật với các tham số của riêng nó. Do đó, chọn một giải thuật có thể là khó. Vấn đề đầu tiên là định nghĩa các tiêu chuẩn được dùng trong việc chọn một giải thuật. Các tiêu chuẩn thường được định nghĩa trong thuật ngữ khả năng sử dụng CPU, thời gian đáp ứng hay thông lượng. Để chọn một giải thuật, trước hết chúng ta phải định nghĩa trọng số quan trọng của các thước đo này. Tiêu chuẩn của chúng ta có thể gồm các thước đo như: • Khả năng sử dụng CPU tối đa dưới sự ràng buộc thời gian đáp ứng tối đa là 1 giây. • Thông lượng tối đa như thời gian hoàn thành (trung bình) tỉ lệ tuyến tính với tổng số thời gian thực thi. Một khi các tiêu chuẩn chọn lựa được định nghĩa, chúng ta muốn đánh giá các giải thuật khác nhau dưới sự xem xét. Chúng ta mô tả các phương pháp đánh giá khác nhau trong những phần dưới đây VIII.1 Mô hình quyết định Một loại quan trọng của phương pháp đánh giá được gọi là đánh giá phân tích (analytic evaluation). Đánh giá phân tích dùng giải thuật được cho và tải công việc hệ thống để tạo ra công thức hay số đánh giá năng lực của giải thuật cho tải công việc đó. Một dạng đánh giá phân tích là mô hình xác định (deterministic modeling). Phương pháp này lấy tải công việc đặc biệt được xác định trước và định nghĩa năng lực của mỗi giải thuật cho tải công việc đó. Thí dụ, giả sử rằng chúng ta có tải công việc được hiển thị trong bảng dưới. Tất cả 5 quá trình đến tại thời điểm 0 trong thứ tự được cho, với chiều dài của thời gian chu kỳ CPU được tính bằng mili giây. Quá trình Thời gian xử lý P1 10 P2 29 P3 3 P4 7 P5 12 Xét giải thuật định thời FCFS, SJF và RR (định mức thời gian=10 mili giây) cho tập hợp quá trình này. Giải thuật nào sẽ cho thời gian chờ đợi trung bình tối thiểu? Đối với giải thuật FCFS, chúng ta sẽ thực thi các quá trình này như sau: P1 P2 P3 P4 P5 0 10 39 42 49 61 Thời gian chờ đợi là 0 mili giây cho quá trình P1, 32 mili giây cho quá trình P2, 39 giây cho quá trình P3, 42 giây cho quá trình P4 và 49 mili giây cho quá trình P5. Do đó, thời gian chờ đợi trung bình là (0 + 10 + 39 + 42 + 49)/5= 28 mili giây. Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 73
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Với định thời không trưng dụng SJF, chúng ta thực thi các quá trình như sau: P3 P4 P1 P5 P2 0 3 10 20 32 61 Thời gian chờ đợi là 10 mili giây cho quá trình P1, 32 mili giây cho quá trình P2, 0 mili giây cho quá trình P3, 3 mili giây cho quá trình P4, và 20 giây cho quá trình P5. Do đó, thời gian chờ đợi trung bình là (10 + 32 + 0 + 3 + 20)/5= 13 mili giây. Với giải thuật RR, chúng ta thực thi các quá trình như sau: P1 P2 P3 P4 P5 P2 P5 P2 0 10 20 23 30 40 50 52 61 Thời gian chờ đợi là 0 mili giây cho quá trình P1, 32 mili giây cho quá trình P2, 20 mili giây cho quá trình P3, 23 mili giây cho quá trình P4, và 40 mili giây cho quá trình P5. Do đó, thời gian chờ đợi trung bình là (0 + 32 + 20 + 23 + 40)/5 = 23 mili giây. Trong trường hợp này, chúng ta thấy rằng, chính sách SJF cho kết quả ít hơn ½ thời gian chờ đợi trung bình đạt được với giải thuật FCFS; giải thuật RR cho chúng ta giá trị trung gian. Mô hình xác định là đơn giản và nhanh. Nó cho các con số chính xác, cho phép các giải thuật được so sánh với nhau. Tuy nhiên, nó đòi hỏi các số đầu vào chính xác và các trả lời của nó chỉ áp dụng cho những trường hợp đó. Việc dùng chủ yếu của mô hình xác định là mô tả giải thuật định thời và cung cấp các thí dụ. Trong các trường hợp, chúng ta đang chạy cùng các chương trình lặp đi lặp lại và có thể đo các yêu cầu xử lý của chương trình một cách chính xác, chúng ta có thể dùng mô hình xác định để chọn giải thuật định thời. Qua tập hợp các thí dụ, mô hình xác định có thể hiển thị khuynh hướng được phân tích và chứng minh riêng. Thí dụ, có thể chứng minh rằng đối với môi trường được mô tả (tất cả quá trình và thời gian của chúng sẳn dùng tại thời điểm 0), chính sách SJF sẽ luôn cho kết quả thời gian chờ đợi là nhỏ nhất. Tuy nhiên, nhìn chung mô hình xác định quá cụ thể và yêu cầu tri thức quá chính xác để sử dụng nó một cách có ích. VIII.2 Mô hình hàng đợi Các quá trình được chạy trên nhiều hệ thống khác nhau từ ngày này sang ngày khác vì thế không có tập hợp quá trình tĩnh (và thời gian) để dùng cho mô hình xác định. Tuy nhiên, những gì có thể được xác định là sự phân bổ chu kỳ CPU và I/O. Sự phân bổ này có thể được đo và sau đó được tính xấp xỉ hay ước lượng đơn giản. Kết quả là một công thức toán mô tả xác suất của một chu kỳ CPU cụ thể. Thông thường, sự phân bổ này là hàm mũ và được mô tả bởi giá trị trung bình của nó. Tương tự, sự phân bổ thời gian khi các quá trình đến trong hệ thống-phân bổ thời gian đến-phải được cho. Hệ thống máy tính được mô tả như một mạng các server. Mỗi server có một hàng đợi cho các quá trình. CPU là một server với hàng đợi sẳn sàng của nó, như là một hệ thống nhập/xuất với các hàng đợi thiết bị. Biết tốc độ đến và tốc độ phục vụ, chúng ta có thể tính khả năng sử dụng, chiều dài hàng đợi trung bình, thời gian chờ Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 74
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 trung bình,..Lĩnh vực nghiên cứu này được gọi là phân tích mạng hàng đợi (queueing- network analysis). Thí dụ, gọi n là chiều dài hàng đợi trung bình (ngoại trừ các quá trình đang được phục vụ), gọi W là thời gian chờ đợi trung bình trong hàng đợi và λ là tốc độ đến trung bình cho các quá trình mới trong hàng đợi (chẳng hạn 3 quá trình trên giây). Sau đó, chúng ta mong đợi trong suốt thời gian W một quá trình chờ, λ x W các quá trình mới sẽ đến trong hàng đợi. Nếu hệ thống ở trong trạng thái đều đặn thì số lượng quá trình rời hàng đợi phải bằng số lượng quá trình đến. Do đó, n=λxW Công thức này được gọi là công thức Little. Công thức Little là đặc biệt có ích vì nó phù hợp cho bất cứ giải thuật định thời và sự phân bổ các quá trình đến. Chúng ta sử dụng công thức Little để tính một trong ba biến, nếu chúng ta biết hai biến khác. Thí dụ, nếu chúng ta biết có 7 quá trình đến mỗi giây (trung bình) và thường có 14 quá trình trong hàng đợi thì chúng ta có thể tính thời gian chờ đợi trung bình trên mỗi quá trình là 2 giây. Phân tích hàng đợi có thể có ích trong việc so sánh các giải thuật định thời nhưng nó cũng có một số giới hạn. Hiện nay, các loại giải thuật và sự phân bổ được quản lý là tương đối giới hạn. Tính toán của các giải thuật phức tạp và sự phân bổ là rất khó để thực hiện. Do đó, phân bổ đến và phục vụ thường được định nghĩa không thực tế, nhưng dễ hướng dẫn về mặt tính toán. Thông thường cần thực hiện một số giả định độc lập có thể không chính xác. Do đó, để chúng sẽ có thể tính câu trả lời, các mô hình hàng đợi thường chỉ xấp xỉ hệ thống thật. Vì thế, độ chính xác của các kết quả tính toán có thể là sự nghi vấn. VIII.3 Mô phỏng Để đạt được sự đánh giá các giải thuật định thời chính xác hơn, chúng ta có thể dùng mô phỏng (simulations). Mô phỏng liên quan đến lập trình một mô hình hệ thống máy tính. Cấu trúc dữ liệu phần mềm biểu diễn các thành phần quan trọng của hệ thống. Bộ mô phỏng có một biến biểu diễn đồng hồ; khi giá trị của biến này tăng, bộ mô phỏng sửa đổi trạng thái hệ thống để phản ánh các hoạt động của các thiết bị, các quá trình và các bộ định thời. Khi sự mô phỏng thực thi, các thống kê hiển thị năng lực của giải thuật được tập hợp và in ra. Hình 0-8 Đánh giá các bộ định thời CPU bằng mô phỏng Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 75
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Giáo Trình Hệ Điều Hành - Chương 2: CẤU TRÚC HỆ ĐIỀU HÀNH
16 p |
455 |
211
-
Giáo trình Hệ điều hành Linux: Phần 1 - Viện CNTT - ĐH quốc gia Hà Nội
20 p |
376 |
153
-
Giáo Trình Hệ Điều Hành –
12 p |
278 |
147
-
Giáo trình hệ điều hành part 1
14 p |
134 |
56
-
Giáo trình hệ điều hành part 2
14 p |
101 |
37
-
Giáo trình hệ điều hành part 3
14 p |
78 |
32
-
Giáo trình hệ điều hành part 4
14 p |
77 |
32
-
Giáo trình hệ điều hành part 6
14 p |
64 |
29
-
Giáo trình hệ điều hành part 7
14 p |
71 |
28
-
Giáo trình hệ điều hành part 8
14 p |
57 |
26
-
Giáo trình hệ điều hành part 9
14 p |
74 |
26
-
Bài giảng môn Hệ điều hành: Chương 4 - GV. Nguyễn Thị Ngọc Vinh
93 p |
103 |
26
-
Giáo trình hệ điều hành part 5
14 p |
69 |
26
-
Giáo trình hệ điều hành part 10
12 p |
62 |
25
-
Giáo trình Hệ điều hành (Operating system): Phần 1
100 p |
37 |
8
-
Bài giảng Lập trình hệ điều hành: Chương 4 - Hà Duy Anh
44 p |
36 |
6
-
Hệ điều hành - Chương IV: Định thời CPU
43 p |
31 |
4

Set-Cookie: TLDEVNamespace=k3gaa2p7ullfh2prhp7gaf5i16; path=/; domain=.tailieu.vn; HttpOnly


markdown:
# Giới thiệu về thuật toán trong tin học
Chia sẻ: Nguyenhuu Thinh | Ngày: | Loại File: DOC | Số trang:5
lượt xem 119
download
![](http://image.tlvnimg.com/document/thumbnail/2009/20091126/thinh0611/80x100/gioi_thieu_ve_thuat_toan_trong_tin_hoc_5866.jpg)
##
Giới thiệu về thuật toán trong tin học
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static.tlvnimg.com/b2013az/templates/version1/default/images/down16x21.png)
Thuật toán là một hệ thống chặt chẽ và rõ ràng các quy tắc nhằm xác định một dãy các thao tác trên những đối tượng, sao cho sau một số hữu hạn bước thực hiện các thao tác ta đạt được mục tiêu định trước.
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
##
Nội dung Text: Giới thiệu về thuật toán trong tin học
- Giới thiệu về thuật toán trong tin học 1. Khái niệm thuật toán Thuật toán là một hệ thống chặt chẽ và rõ ràng các quy tắc nhằm xác định một dãy các thao tác trên những đối tượng, sao cho sau một số hữu hạn bước thực hiện các thao tác ta đạt được mục tiêu định trước. Để giải các bài toán bằng máy tính chúng ta thường phải có một quan niệm rộng rãi hơn về thuật toán cụ thể là lưu ý đến các đặc điểm sau: a) Không cần xác định toàn bộ lời giải, các thao tác theo từng bước một cách chính xác, đơn vị và rõ ràng.Thay vào đó chỉ cần chỉ ra một cách chuyển từ một bước giải i tới bước giải kế tiếp i+1, và tìm cách cắt nhỏ bài toán thành các bài toán con, đó chính là thuật toán đệ quy rất quan trọng để giải các bài toán tổng quát. b) Có nhiều bài toán không có cách giải đúng, hoặc cách giải đúng không thể chấp nhận được do hạn chế về thời gian chạy và kích thước bộ nhớ. Nhưng nếu ta chấp nhận kết quả gần đúng thì có thể tồn tại nhiều cách giải đỡ phức tạp và có hiệu quả hơn, đó chính là các thuật toán Heuristic để giải các bài toán gần đúng. 2. Khái niệm bài toán: Trong phạm vi tin học ta có thể quan niệm bài toán là một việc nào đó ta muốn máy tính thực hiện. Các bài toán được cấu tạo bởi 2 thành phần cơ bản Input và Output. Thuật toán cũng có thể được hiểu là một dãy các thao tác được sắp xếp theo trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán ta nhận được Output cần tìm. 3. Một số ví dụ: Bài toán 1:Tìm giá trị lớn nhất của một dãy số nguyên Xác định bài toán Input: Số nguyên dương N và dãy N số nguyên a1,a2,...,aN Output: Giá trị lớn nhất Max của dãy số. Ý tưởng: Chọn Max=a1
- Lần lượt với i từ 2 đến N, so sánh ai với a1, nếu ai>a1 thì gán Max=ai Thuật toán giải được mô tả như sau: Nhập N>0 và dãy a1,a2,…,aN. Max a1, i 2; Nếu i > N thì đưa giá trị Max rồi kết thúc; Nếu ai > Max thì Max ai i i + 1 rồi quay lại bước 3. Bài toán 2: Tìm UCLN của hai số nguyên dương m,n. Xác định bài toán: Input : 2 số nguyên dương m,n. Output : UCLN của 2 số. Ý tưởng 01: UCLN(m,n)=UCLN(m,m-n) (Giả sử m>n) Thuật toán giải được mô tả như sau: Nhập 2 số m,n > 0. Nếu m=n thì đưa ra UCLN(m,n)=m; Nếu m > n thì m m-n rồi quay lại bước 2. Nếu n>m thì n n-m rồi quay lại bước 2. Đưa ra kết quả UCLN khi một trong m hoặc n=0 (Nếu m=0 thì UCLN(m,n)=n còn nếu m≠0 thì UCLN(m,n)=m) Ý tưởng 02: UCLN(m,n) = UCLN(n,m mod n) Thuật toán giải 02 : dành cho bạn đọc. Bài toán 3: Cho dãy A gồm N số nguyên a1,a2,…,aN. Sắp xếp các số hạng để dãy A là trở thành dãy không giảm (tức là số hạng sau luôn lớn hơn hoặc bằng số hạng trước) Xác định bài toán: Input: Dãy A gồm N số nguyên a1,a2,…,aN. Output: Dãy A đã được sắp xếp trở thành dãy không giảm Ý tưởng 01: Với mỗi cặp số hạng đứng liền kề nhau trong dãy, nếu số đứng trước lớn hơn số đứng sau thì ta đổi chỗ hai số cho nhau. Quá trình lặp lại cho đến khi không còn sự đổi chỗ xảy ra. Thuật toán giải được mô tả như sau: Nhập N>0 và dãy a1,a2,…,aN. MN Nếu M < 2 thì đưa ra dãy A được sắp xếp rồi kết thúc. Nếu M ≥ 2 thì M M-1, i 0
- i i+1 Nếu i > M thì quay lại bước 3. Nếu ai > ai+1 thì tráo đổi vị trí ai và ai+1 Quay lại bước 5. Ý tưởng 02 : Chia dãy cần sắp xếp thành 2 phần, lấy thành phần giữa X làm chuẩn để so sánh. • Tìm một phần tử A ở dãy trên có giá trị lớn hơn X • Tìm một phần tử B ở dãy dưới có giá trị nhỏ hơn X • Hoán vị A và B. • Tiếp tục như vậy cho đến khi ta đạt được dãy trên chỉ gồm các phần tử nhỏ hơn X, dãy dưới chỉ gồm các phần tử lớn hơn X. • Áp dụng thuật toán trên vào dãy trên và dãy dưới (đệ quy) cho đến khi không chia được nữa. Thuật toán giải 02: bạn thử mô tả xem sao, đây coi như là một bài tập nhỏ cho các bạn yêu thích lập trình. Bài toán 4: Cho dãy A gồm N số nguyên a1,a2,…,aN và một số X. Hãy xác định xem giá trị của X có nằm trong dãy A không? Nếu có thì nằm ở đâu ? Xác định bài toán: Input: dãy A gồm N số nguyên a1,a2,…,aN và số X. Output: X có thuộc A không? Nếu có thì nằm ở vị trí nào? Ý tưởng: So sánh từng phần tử của dãy với X. Nếu có phần tử ai = X thì đưa ra thứ tự của phần tử thứ i thỏa ai = X. Thuật toán giải được mô tả như sau : Nhập N>0 ,dãy a1,a2,…,aN ,và số X i 1. Nếu i > N thì kết thúc và đưa kết quả Nếu i < N thì tiếp tục. Nếu ai = X thì kết thúc và đưa ra thứ tự của X là i . Nếu ai ≠ X thì i i + 1 và quay lại bước 5. Vòng lặp kết thúc khi i > N 4.(nói thêm) Phương pháp tinh chế từng bước trong lập trình:1 1 Trích từ cuốn “Phương pháp giải các bài toán trong tin học” của Thạc sĩ Trần Đức Huyên (NXBGD 2001)
- Ban đầu chương trình được viết bằng những lời tự nhiên (tiếng Việt chẳng hạn) thể hiện sự phân tích tổng thể của người lập trình. Ở từng bước sau, mỗi câu lời được phân tích ra chi tiết hơn bằng nhiều câu lời khác tương ứng với sự phân tích một công việc thành những công việc nhỏ hơn. Mỗi câu lời đó là một sự đặc tả công việc. Ta nói ở mỗi bước ta đã tinh chế những câu lời đó. Sự tinh chế được hướng về phía ngôn ngữ lập trình mà ta sẽ dùng. Nghĩa là, càng ở những bước sau, các câu lời tự nhiên càng được thay nhiều bằng các câu lời của ngôn ngữ lập trình. Một câu lời tự nhiên nếu đơn giản thì ta có thể thay bằng một vài phát biểu, nếu phức tạp thì ta coi nó như một thủ tục và tiếp tục tinh chế nó. Trong qua trình tinh chế đó, ta cần đưa ra những biểu diến dữ liệu, vì dữ liệu là nguyên liệu của máy tính. Như vậy cùng với sự tinh chế các công việc, dữ liệu cũng được tinh chế, phân rã, hay cấu trúc hóa. Điều này có nghĩa là sự tinh chế các dặc tả chương trình và dữ liệu là song song. Phương pháp tinh chế từng bước là một thể hiện của tư duy giải quyết vấn đề từ trên xuống, trong đó sự phát triển của các bước là hướng về phía ngôn ngữ lập trình được dùng. Đáy của sự đi xuống trong hoạt động phân tích là các phát triển và các mô tả dữ liệu viết bằng ngôn ngữ lập trình. Hiểu được phương pháp tinh chế từng bước sẽ giúp người lập trình có được môt định hướng thể hiện sự ngăn nắp trên tờ giấy nháp của mình, tránh khỏi việc phải mò mẫm, thử đi thử lại nhiều lần các chương trình mang tính trực giác.
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Giới thiệu về mạng lan cách bấm dây mạng
10 p |
1590 |
505
-
Những thuật ngữ viết tắt trong tin học
3 p |
298 |
158
-
Giới thiệu về Latex 2ε
161 p |
197 |
102
-
Một số tài liệu ngắn gọn giới thiệu về Latex 2e
161 p |
172 |
57
-
Bài giảng Tin học căn bản: Phần 1
71 p |
158 |
55
-
Bài giảng Tin học chuyên ngành: Giới thiệu giao diện PPT 2010 - ThS. Đào Anh Vũ
35 p |
92 |
29
-
Tin học đại cương part 2 - Phương pháp giải các bài toán trong tin học
0 p |
163 |
21
-
Bài giảng Giới thiệu về máy vi tính - Võ Hà Quang Định
14 p |
71 |
18
-
Bài giảng Tin học ứng dụng trong hóa học: Chương 2 - ĐH Công nghiệp TP.HCM
87 p |
66 |
18
-
Bài giảng Chương trình tin học lớp 10 - Bài 4: Bài toán và thuật toán
22 p |
51 |
15
-
Bài giảng Tin học ứng dụng trong hóa học: Chương 1 - ĐH Công nghiệp TP.HCM
59 p |
57 |
11
-
Bài giảng Tin học đại cương: Phần 1 - Những khái niệm cơ bản trong tin học
37 p |
78 |
10
-
Bài giảng Tin học đại cương: Chương 3 - Hệ soạn thảo văn bản Microsoft Word
32 p |
29 |
5
-
Bài giảng Tin học đại cương: Giải thuật
8 p |
18 |
3
-
Bài giảng Tin học đại cương: Chương 7 - Bài toán và thuật toán
59 p |
27 |
3
-
Bài giảng Tin học đại cương - Chương 7: OpenOffice và in ấn
15 p |
19 |
3
-
Bài giảng Nhập môn Tin học: Chương 1 - Nguyễn Đức Cương
8 p |
28 |
1

WARC-Type: response

Content-Type: application/http; msgtype=response

WARC-Identified-Payload-Type: application/xhtml+xml

Server: Apache/2.2.31 (CentOS)

Connection: close

Pragma: no-cache

Cache-Control: no-store, no-cache, must-revalidate, post-check=0, pre-check=0

Set-Cookie: TLDEVNamespace=3ffingadp0oha8t23h0lt7q3k5; path=/; domain=.tailieu.vn; HttpOnly

Vary: Accept-Encoding

Content-Type: text/html; charset=UTF-8


markdown:
# Hiệp định về khuyến khích và bảo hộ đầu tư giữa Việt Nam và Inđônêxia
Chia sẻ: Nguyễn Thục | Ngày: | Loại File: PDF | Số trang:6
lượt xem 13
download
![](http://image.tlvnimg.com/document/thumbnail/2009/20091017/hienthuc/80x100/954.jpg)
##
Hiệp định về khuyến khích và bảo hộ đầu tư giữa Việt Nam và Inđônêxia
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static.tlvnimg.com/b2013az/templates/version1/default/images/down16x21.png)
Hiệp định về khuyến khích và bảo hộ đầu tư giữa Chính phủ Cộng hoà xã hội chủ nghĩa Việt Nam và Chính phủ nước Cộng hoà Inđônêxia
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
##
Nội dung Text: Hiệp định về khuyến khích và bảo hộ đầu tư giữa Việt Nam và Inđônêxia
- HIỆP ĐỊNH VỀ KHUYẾN KHÍCH VÀ BẢO HỘ ĐẦU TƯ GIỮA CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM VÀ CHÍNH PHỦ CỘNG HOÀ INDONÊXIA Chính phủ Cộng hoà xã hội chủ nghĩa Việt Nam và Chính phủ cộng hoà Indonêxia, sau đây được gọi là "các Bên ký kết"; Thúc đẩy quan hệ hữu nghị và hợp tác giữa hai nước và hai dân tộc; Mong muốn tạo điều kiện thuận lợi cho sự tăng cường hợp tác kinh tế giữa hai nước, đặc biệt, cho đầu tư vốn của các nhà đầu tư của nước này trên lãnh thổ của nước kia trên cơ sở tôn trọng độc lập và chủ quyền của nhau, bình đẳng và cùng có lợi; Nhận thức rằng việc khuyến khích và bảo hộ lẫn nhau đối với đầu tư vốn và đầu tư theo Hiệp định quốc tế góp phần làm tăng sự thịnh vượng ở cả hai nước; Đã thoả thuận như sau: Điều 1: Định nghĩa Theo tinh thần Hiệp định này: 1. Thuật ngữ "đầu tư" có nghĩa là mọi loại tài sản được đầu tư bới các nhà đầu tư của một Bên ký kết trên lãnh thổ Bên ký kết kia phù hợp với luật và quy định của Bên ký kết đó, bao gồm nhưng không chỉ: a. Sở hữu động sản, bất động sản và bất kỳ các quyền khác như quyền thế chấp, cầm cố, thế nợ; b. Cổ phần, cổ phiếu và phiếu nợ của công ty được hợp nhất ở bất kỳ nơi nào hoặc lợi ích phát sinh từ sở hữu của công ty như vậy; c. Những khiếu nại về tiền hoặc về bất kỳ sự thực hiện nào theo hợp đồng có giá trị tài chính; d. Quyền sở hữu trí tuệ, bao gồm bản quyền, nhãn hiệu thương mại, bằng sáng chế, thiết kế công nghiệp, bí quyết, bí mật thương mại, tên thương mại và đặc quyền kế nghiệp; e. Tô nhượng thương mại theo luật hoặc theo hợp đồng bao gồm tô nhượng về nghiên cứu, nuôi trồng, chiết suất hoặc khai thác tài nguyên thiên nhiên; 2. Thuật ngữ "Nhà đầu tư" nghĩa là bất kỳ công ty nào là công dân của một Bên ký kết đã hoặc đang đầu tư trên lãnh thổ của Bên ký kết kia.
- 3. Thuật ngữ "Công ty" nghĩa là, tuỳ theo mỗi Bên ký kết, bất kỳ pháp nhân nào, bao gồm công ty, hãng và xí nghiệp được liên hợp và thành lập theo luật hiện hành của Bên ký kết đó. 4. Thuật ngữ "Công dân" nghĩa là, tuỳ theo mỗi Bên ký kết, bất kỳ thể nhân nào có quốc tịch, phù hợp với luật pháp của Bên ký kết đó. 5. Thuật ngữ "Những khoản thu nhập" hoặc "Thu nhập" nghĩa là những khoản sinh lợi do đầu tư đặc biệt nhưng không chỉ là các khoản sau: lợi nhuận, lãi, lãi vốn, lãi cổ phần, tiền bản quyền hoặc phí. 6. "Lãnh thổ" nghĩa là: a. Đối với Cộng hoà Indonexia: "Lãnh thổ" Cộng hoà Indonexia được xác định theo luật của Indonexia và các vùng lân cận mà Cộng hoà Indonexia có chủ quyền, quyền chủ quyền hoặc tài phán phù hợp với kuật quốc tế; b. Đối với Cộng hoà xá hội chủ nghĩa Việt Nam: "Lãnh thổ" và các vùng biển lân cận mà nước Cộng hoà xã hội chủ nghĩa Việt Nam có chủ quyền hoặc tài phán phù hợp với luật quốc tế. Điều 2: Khuyến khích và bảo hộ đầu tư 1. Mỗi Bên ký kết khuyến khích và tạo điều kiện thuận lợi cho những nhà đầu tư của Bên ký kết kia đầu tư trên lãnh thổ của mình, và sẽ chấp nhận những vốn đầu tư như vậy phù hợp với luật và quy định của mình. 2. Những đầu tư của các nhà đầu tư của mỗi Bên ký kết được đối xử công bằng và thoả đáng trong suốt thời gian đầu tư và được hưởng sự bảo hộ thích đáng và an toàn trên lãnh thổ Bên ký kết kia. Điều 3: Phạm vi áp dụng Hiệp định 1. Lợi ích của Hiệp định này chỉ áp dụng cho những trường hợp đầu tư vốn của các nhà đầu tư của một Bên ký kết trên lãnh thổ của Bên ký kết kia đã được chuẩn y cụ thể bằng văn bản của cơ quan có thẩm quyền của Bên ký kết kia. 2. Các nhà đầu tư của một Bên ký kết phải xin chuẩn y đối với bất kỳ đầu tư vốn nào được tiến hành trước hay sau khi Hiệp định này có hiệu lực. 3. Hiệp định này được áp dụng cho những đầu tư của các nhà đầu tư của Cộng hoà xã hội chủ nghĩa Việt Nam trên lãnh thổ Cộng hoà Indonexia đã được cho phép từ trước, phù hợp với luật số 1 năm 1967 về đầu tư vốn nước ngoài và bất kỳ luật sửa đổi hoặc luật
- thay thế nào và những đầu tư của các nhà đầu tư của Cộng hoà Indonesia trên lãnh thổ Cộng hoà xã hội chủ nghĩa Việt Nam đã được cho phép từ trước phù hợp với luật đầu tư nước ngoài năm 1987 của Việt Nam và bất kỳ luật sửa đổi và thay thế nào. Điều 4: Những quy định về tối huệ quốc 1. Không Bên ký kết nào được đối xử đối với những đầu tư và thu nhập của nhà đầu tư Bên ký kết kia trên lãnh thổ của mình một sự đối xử kém thuận lợi hơn sự đối xử đối với đầu tư và thu nhập của nhà đầu tư bất kỳ nước thứ ba nào. 2. Không Bên ký kết nào được đối xử đối nhà đầu tư của Bên ký kết kia, trên lãnh thổ của mình một sự đối xử kém thuận lợi hơn sự đối xử dành cho nhà đầu tư của bất kỳ nước thứ ba nào trong việc quản lý, sử dụng, thừa hưởng hoặc từ bỏ những đầu tư của họ cũng như bất kỳ hoạt động liên quan tới những đầu tư nói trên. 3. Sự đối xử nói trên sẽ không áp dụng cho bất kỳ những thuận lợi hoặc đặc quyền nào dành cho những nhà đầu tư của nước thứ ba do mỗi Bên ký kết là thành viên của một liên minh thuế quan, thị trường chung, khu thương mại tự do, Hiệp định kinh tế đa phương hay Hiệp định quốc tế hoặc trên cơ sở Hiệp định giữa Bên ký kết đóvới một nước thứ ba về tránh đánh thuế trùng hoặc trên cơ sở thoả thuận thương mại qua biên giới. 4. Tuy có những quy định nói ở các đợn trên đây, những đầu tư do nhà đầu tư của Bên ký kết tiến hành trên lãnh thổ của Bên ký kết kia sẽ được đối xử công bằng và thoả đáng phù hợp với luật và những quy định hiện hành của Bên ký kết đó. Điều 5: Bồi thường do tổn thất hoặc thiệt hại 1. Đầu tư của các nhà đầu tư của một Bên ký kết trên lãnh thổ của Bên ký kết kia bị tổn thất hoặc thiệt hại do chiến tranh hoặc xung đột vũ trang, cách mạng, tình trạng khẩn cấp quốc gia, đảo chính, khởi nghĩa hoặc bạo loạn trên lãnh thổ của Bên ký kết đó, nhà đầu tư có liên quan sẽ được hưởng sự đối xử về đền bù, bồi thường hoặc giải pháp khác phù hợp với luật quốc tế và trong bất kỳ trường hợp nào không kém thuận lợi hơn sự đối xử dành cho các nhà đầu tư của bất kỳ nước thứ ba nào trong những trường hợp tương tự. 2. Không phương hại đến những quy định trên đây của điều này, các nhà đầu tư của một Bên ký kết được hưởng sự đối xử trên lãnh thổ của Bên ký kết kia không kém thuận lợi hơn sự đối xử mà các đầu tư nước thứ ba được hưởng về bất kỳ vấn đề gì có liên quan. Điều 6: Tước đoạt quyền sở hữu 1. Trong bất kỳ trường hợp nào mà đầu tư của các nhà đầu tư một Bên ký kết là đối tượng của biện pháp trưng thu, trực tiếp hoặc gián tiếp các nhà đầu tư có liên quan sẽ được hưởng sự đối xử công bằng và thoả đáng đối với bất kỳ những biện pháp như vậy trên lãnh thổ của Bên ký kết kia. Không một biện pháp nào như vậy được thực hiện trừ khi vì mục đích công và có bồi thường. Việc bồi thường như vậy phảI thoả đáng, thực hiện có hiệu quả và được tự do chuyển và không chậm trễ. Khoản bồi thường như vậy được xác
- định theo giá trị thị trường của đầu tư bị tước đoạt ngay trước thời điểm quyết định tước đoạt quyền sở hữu được công bố hoặc công khai. Khoản bồi thường sẽ được tính theo phương pháp thoả thuận giữa hai bên, phù hợp với phương pháp đánh giá theo tiêu chuẩn quốc tế. 2. Tính hợp pháp của bất kỳ sự tước đoạt quyền sở hữu nào, khoản bồi thường và phương pháp thanh toán bồi thường sẽ được xem xét lại theo thủ tục pháp luật. 3. Khi một Bên ký kết tước đoạt tài sản của một công ty được hợp nhất thành lập theo luật hiện hành trên lãnh thổ của Bên ký kết đó và trong công ty đó nhà đầu tư của Bên ký kết kia có cổ phần, thì Bên trưng thu bảo đảm rằng các quy định của khoản 1, Điều này sẽ được áp dụng trong phạm vi cần thiết để bảo đảm việc bồi thường cho nhà đầu tư của Bên ký kết kia có sở hữu cổ phần. Điều 7: Việc chuyển đầu tư về nước 1. Mỗi Bên ký kết trong phạm vi luật và quy định của mình bảo đảm cho các nhà đầu tư của Bên ký kết kia không có lý do chậm trễ sau khi họ hoàn thành các nghĩa vụ thuế được chuyển: a. Vốn và vốn bổ sung được sử dụng để duy trì và phát triển đầu tư; b. Lợi nhuận ròng bao gồm lãi cổ phần và lãi tương ứng với sở hữu cổ phần của những người nước ngoài tham gia; c. Khoản trả tiền vay và lãi tương ứng, nếu các khoản vay đó có liên quan đến đầu tư; d. Khoản thanh toán về bản quyền và phí dịch vụ nếu các khoản đó có liên quan đến đầu tư; e. Khoản thu từ việc bán các cổ phần do các cổ đông nước ngoài sở hữu; f. Khoản bồi thường tổn thất hoặc thiệt hại; g. Khoản bồi thường do tước đoạt quyền sở hữu; h. Khoản thu của nhà đầu tư trong trường hợp thanh lý i. Thu nhập của công dân của một Bên ký kết được phép làm việc có liên quan đến đầu tư trên lãnh thổ của Bên ký kết kia. 2. Việc trả cho bồi thường nói tại điểm f và g của ĐIều này được thực hiện với phạm vi và điều kiện được hai Bên ký kết thoả thuận, bao gồm việc trả bồi thường làm nhiều lần một cách hợp lý.
- 3. Đối với nhà đầu tư của một Bên ký kết không có sự thoả thuận nào khác với các cơ quan có thẩm quyền của Bên ký kết kia mà trên lãnh thổ đó việc đầu tư được thực hiện, việc chuyển tiền theo quy định của khoản 1, Điều này, sẽ được phép chuyển bằng đồng tiền lúc đầu tư hoặc bằng bất kỳ đồng tiền tự do chuyển đổi nào. Việc chuyển tiền nói trên được thực hiện theo tỷ giá hối đoái hiện hành vào thời điểm chuyển đổi. 4. Tuy có những quy định nói ở trên đây, mỗi Bên ký kết có thể theo các luật và quy định yêu cầu báo cáo việc chuyển tiền. Điều 8: Thế quyền 1. Nếu một Bên ký kết hoặc một tổ chức do Bên đó chỉ định thực hiện thanh toán cho các nhà đầu tư theo chính sách bảo hiểm những rủi ro phi thương mại đối với bất kỳ đầu tư vốn nào hoặc một phần đầu tư trên lãnh thổ của Bên ký kết kia thì Bên ký kết này sẽ công nhận: a. Sự uỷ quyền theo luật hoặc theo một giao dịch pháp luật, về bất kỳ quyền khiếu nại nào của nhà đầu tư đối với Bên ký kết kia hoặc các tổ chức được uỷ quyền; b. Bên ký kết trên hoặc tổ chức được uỷ quyền được thế quyền trong việc thực hiện các quyền và tiến hành những khiếu nại của nhà đầu tư đó. 2. Bên ký kết kia hoặc tổ chức được uỷ quyền vì vậy có quyền đòi, nếu họ muốn về bất cứ quyền và khiếu nại nào như vậy trong phạm vi quyền và khiếu nại của người trước đó trên danh nghĩa. 3. Nếu Bên ký kết trên thu được khoản tiền bằng đồng tiền hợp pháp của Bên ký kết kia hay các khoản tín dụng theo sự uỷ quyền nêu ở điểm (a) khoản 1 của ĐIều này, Bên ký kết được thế quyền sẽ được tự do sử dụng những khoản tiền và tín dụng đó để đáp ứng nhu cầu chi tiêu của mình trên lãnh thổ của Bên ký kết kia. Điều 9: Giải quyết tranh chấp giữa các nhà đầu tư và các Bên ký kết 1. Bất kỳ tranh chấp nào phát sinh giữa một Bên ký kết và nhà đầu tư của Bên ký kết kia sẽ được giải quyết bằng hoà giải. 2. Trong trường hợp việc tranh chấp trên không giải quyết được bằng hoà giải trong thời hạn 6 tháng, kể từ thời điểm nộp đơn, nhà đầu tư có liên quan có thể đưa vụ tranh chấp để giải quyết theo một trong các hình thức sau đây: a. Toà án của Bên ký kết có thẩm quyền phán quyết mọi cấp; b. Toà án trọng tài "Ad hoc" do hai Bên ký kết thành lập; c. Bất kỳ toà án trọng tài nào được sự thoả thuận của hai Bên ký kết.
- 3. Trong quá trình tố tụng tại Toà án hoặc Trọng tài có thể giải quyết tranh chấp nêu trên, hai Bên ký kết sẽ kiềm chế bất kỳ sự can thiệp nào. Điều 10: Giải quyết tranh chấp giữa các Bên ký kết về việc giải thích và áp dụng Hiệp định Các tranh chấp về việc giải thích và thi hành Hiệp định này được giải quyết bằng hoà giải thông qua đàm phán ngoại giao giữa Chính phủ của các Bên ký kết. Điều 11: Áp dụng các điều khoản khác Bất kỳ vấn đề nào được điều chỉnh bởi Hiệp định này và bất kỳ Hiệp định nào khác mà hai Bên đều tham gia thì các điều khoản thuận lợi hơn sẽ được áp dụng cho các nhà đầu tư. Điều 12: Trao đổi ý kiến và sửa đổi 1. Mỗi Bên ký kết có thể yêu cầu trao đổi ý kiến về bất kỳ vấn đề gì do hai Bên ký kết thoả thuận đưa ra. 2. Hiệp định này có thể sửa đổi bất kỳ lúc nào, nếu cần thiết, với sự thoả thuận của hai Bên ký kết. Điều 13: Hiệu lực, thời hạn và kết thúc Hiệu lực này sẽ có hiệu lực sau 30 ngày kể từ ngày các Bên ký kết thông báo cho nhau bằng văn bản đã hoàn thanh các thủ tục cần thiết theo luật pháp. Hiệp định này sẽ có hiệu lực trong thời hạn ban đầu là 10 năm, sau đó, Hiệp định sẽ tiếp tục có hiệu lực không thời hạn. Mỗi Bên ký kết có quyền chấm dứt Hiệp định, sau khi đã thông báo bằng văn bản cho Bên kia trước mười hai tháng sau khi Hiệp định đã thực hiện được chín năm. Tuy nhiên đối với những đầu tư đã được chấp nhận trong khi Hiệp định có hiệu lực, những điều khoản của Hiệp định này vẫn tiếp tục có hiệu lực trong một thời hạn mười năm kể từ ngày kết thúc Hiệp định. Những người có tên dưới đây được Chính phủ của các Bên uỷ quyền ký Hiệp định này. Hiệp định này được làm tại Jakata ngày 25 tháng 10 năm 1991 bằng tiếng Indonesia, tiếng Việt và tiếng Anh, tất cả các bản có giá trị ngang nhau. Trong trường hợp có sự khác nhau về giải thích Hiệp định, sẽ sử dụng văn bản tiếng Anh.
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Luật Chứng Khoán _ Số 70.2006.QH11
66 p |
384 |
257
-
Quyết định số 457/2005/QĐ-NHNN
25 p |
310 |
158
-
Nghị định quy định về Luật chứng khoán
16 p |
267 |
128
-
Giải thích thuật ngữ về Chứng khoán? Môi giới? Đầu tư?
435 p |
192 |
101
-
Hiệp định về khuyến khích và bảo hộ đầu tư giữa Việt Nam và Anh và Bắc Ireland
9 p |
178 |
46
-
Quy định chi tiết thi hành một số điều của Luật Chứng khoán Chính phủ
21 p |
134 |
45
-
Hiệp định về khuyến khích và bảo hộ đầu tư giữa Việt Nam và Italia
9 p |
77 |
16
-
Quyết định 951/2003/QĐ-NHNN về việc ban hành Quy định về việc thành lập và hoạt động của Công ty kiều hối trực thuộc ngân hàng thương mại cổ phần của Nhà nước và Nhân dân do Ngân hàng Nhà nước ban hành
7 p |
134 |
11
-
Thông tư số 37/2000/TT-BTC
12 p |
64 |
7
-
Hiệp định về thúc đẩy và bảo hộ đầu tư giữa Việt Nam và Austraylia
10 p |
67 |
6
-
Quyết định 51/2004/QĐ-BTC
2 p |
52 |
5
-
Quyết định số 310/2005/QĐ-TTg
4 p |
44 |
5
-
Quyết định số 181/2003/QĐ-UB
2 p |
43 |
4
-
Quyết định số 131/1998/QĐ-NHNN1
2 p |
34 |
3
-
Thông báo 36/TB-VPCP
3 p |
57 |
3
-
Quyết định số 135/2001/QĐ-BTC
3 p |
63 |
2
-
Quyết định 428/QĐ-UBCK năm 2013
32 p |
32 |
1

Set-Cookie: TLDEVNamespace=ag79jdhvf2ktdbvqveq89nlf94; path=/; domain=.tailieu.vn; HttpOnly