sistem operasi

1

Sistem Operasi

Perkenalan

2

Identitas Mata Kuliah

• Nama Mata Kuliah : Sistem Operasi

• Kode Mata Kuliah : 0953333203

• SKS Mata Kuliah : 3 (Teori : 2 dan Praktikum : 1)

• Jurusan Informatika, Semester III (2014 / 2015)

• Ruang Kuliah : B.404

• Ruang Praktikum : Laboratorium Pusat Komputer UNS

• Jadwal Kuliah : Jumat jam 07:30 – 09:15 WIB

• Jadwal Praktikum : Selasa jam 09:20 – 11:05 WIB

• Dosen Pengampu : Meiyanto Eko Sulistyo, S.T., M.Eng.

3

Peraturan Perkuliahan

1. Mahasiswa/i wajib menjaga kerapian diri seperti

menggunakan sepatu, baju berkerah, celana

panjang tidak sobek, tidak merokok, tidak

berbusana yang terlihat aurat, tidak berbusana

ketat, tidak berbusana transparan, tidak berkaca

mata gelap, tidak bermake-up berlebihan, dll.

2. Mahasiswa/i yang tidak hadir kuliah, praktikum,

kuis, dan ujian KD harus bisa menunjukkan

surat keterangan sakit/ijin keperluan keluarga.

3. Ujian Remidi wajib bagi mahasiswa/i yang tidak

hadir Ujian KD dengan keterangan, hadir Ujian

KD, dan nilai KD < 60.

4

Standar Kompetensi

Mahasiswa mampu mengenali dan

mengoperasikan beberapa sistem operasi,

kemudian mampu menjelaskan konsep,

cara kerja dan membandingkan antar sistem

operasi serta mengembangkan sebuah

sistem operasi.

5

Referensi

1. Abraham Silberschatz, 2004, Operating System Concept with

Java, John Wiley & Sons Inc.

2. Sri Kusumadewi, 2000, Sistem Operasi, J & J Learning.

Yogyakarta.

3. A. S. Tanenbaum, 1992, Modern Operating System, Prentice-

Hall, Inc.

4. Bambang Hariyanto, 2000, Sistem Operasi, Informatika.

Bandung.

5. A. S. Tanenbaum, Albert S. Woodhull, 2006, Operating

Systems Design and Implementation. Third Edition. Prentice-

Hall.

6. A. S. Tanenbaum, Albert S. Woodhull, 2004, Operating

Systems Design and Implementation. Second Edition.

Prentice-Hall.

6

Sub Pokok Bahasan Pertemuan Materi

1 Pengenalan Sistem Operasi

2 Struktur Sistem Komputer

3 Proses

4 Ujian Kompetensi Dasar 1

5 Thread

6 Penjadual CPU

7 Sinkronisasi


9 Deadlock

10 Memory

11 Virtual Memory


13 Sistem File

14 Input / Output

15 Sistem Penyimpanan Disk


7

Bobot Nilai Akhir Semester

KD1 = ({[(K1+K2+K3)/3]x5%}+{[(P1+P2+P3)/3]x5%}+{UKD1x15%})/25%

KD2 = ({[(K5+K6+K7)/3]x5%}+{[(P4+P5+P6)/3]x5%}+{UKD2x15%})/25%

KD3 = ({[(K9+K10+K11)/3]x5%}+{[(P7+P8+P9)/3]x5%}+{UKD3x15%})/25%

KD4 = ({[(K13+K14+K15)/3]x5%}+{[(P10+P11+P12)/3]x5%}+{UKD4x15%})/25%

Nilai Akhir = (KD1+KD2+KD3+KD4)/4

7

8


(next…) K1 = Nilai Kuis/Tugas Pertemuan ke-1

K2 = Nilai Kuis/Tugas Pertemuan ke-2


UKD1 = Ujian Kompetensi Dasar 1












UKD4 = Ujian Kompetensi Dasar 4 8

9


(next…) P1 = Nilai Laporan Praktikum Pertemuan ke-1

P2 = Nilai Laporan Praktikum Pertemuan ke-2











9

10

Nilai Akhir Semester

10

No. Rentang Nilai Nilai Huruf Bobot Arti

1. 80 – 100 A 4 Sangat Baik

2. 70 – 79,9 B 3 Baik

3. 60 – 69,9 C 2 Cukup

4. 40 – 59,9 D 1 Kurang

5. 0 – 39,9 E 0 Gagal

Next…

11

1

Sistem Operasi

Pengenalan Sistem Operasi

2

Apa itu Sistem Operasi?

Perangkat lunak yang bertindak sebagai

perantara antara pemakai komputer dan

perangkat keras

3

Sasaran Sistem Operasi

– Menjalankan program-program dari

user dan membantu user dalam

menggunakan komputer

– Menyediakan sarana sehingga

pemakaian komputer menjadi mudah

(convenient)

– Memanfaatkan perangkat keras

komputer yang terbatas secara efisien

(resource manager)

4

Komponen Sistem Komputer

1. Hardware menyediakan “basic computing resources”

(CPU, memory, I/O devices).

2. Operating system mengendalikan/mengkoordinasikan

penggunaan hardware diantara berbagai

aplikasi/program dari user.

3. Applications programs menggunakan sistem resource

yang digunakan untuk menyelesaikan masalah

komputasi dari user (compilers, database systems, video

games, business programs).

4. Users (people, machines, other computers).

5

Abstraksi Komponen Sistem

6

Definisi Sistem Operasi

• Resource allocator – mengatur resource (sumber daya komputer)

– mengalokasikan dan mengontrol pemakaian resources dari/oleh berbagai program/aplikasi.

• Control program – Mengendalikan eksekusi program user dan

pemakaian sistem resource (contoh : operasi pada I/O device) => handal, reliable, terlindung.

• Kernel – Sistem program yang berjalan (“ada) terus

menerus selama komputer aktif`.

– Kontras dengan aplikasi yang di “load”, eksekusi dan terminasi .

7

Evolusi Sistem Operasi

• OS sederhana

– Program tunggal, satu user, satu mesin

komputer (CPU) : komputer generasi

pertama, awal mesin PCs, controller: lift,

Playstation etc.

– No problems, no bad people, no bad

programs => interaksi sederhana

– Problem: terbatas pemakaiannya;

8

Simple Batch System

• Memakai seorang operator

– User ≠ operator

• Menambahkan card reader

• Mengurangi waktu setup: batch jobs yang mirip/sama

• Automatic job sequencing secara otomatis kontrol akan di transfer dari satu job ke job yang lain.

– Hal tersebut merupakan bentuk OS primitif

• Salah satu bentuk system batch Resident monitor

– Fungsi monitor: awal (initial) melakukan kontrol

– Transfer control ke job (pertama)

– Setelah job selesai, control kembali ke monitor

• Control cards: mengatur batch jobs

9

Multiprogrammed Batch Systems

Beberapa jobs disimpan di memori pada saat

bersamaan, dan CPU melakukan multiplexing ke

jobs-jobs tersebut

10

Fitur OS yang Dibutuhkan dalam

Multiprogramming

• I/O rutin dikendalikan dan diatur oleh sistem

• Memory management sistem harus mengalokasikan memori untuk beberapa jobs sekaligus

• CPU scheduling sistem harus memilih jobs mana yang telah siap akan dijalankan

• Alokasi dari I/O devices untuk jobs dan proteksi bagi I/O devices tersebut

Sistem menjadi kompleks

– Bagaimana kalau program “loops terus menerus”,going mad etc. proteksi

11

Time-Sharing Systems-Interactive Computing

• CPU melakukan multiplex pada beberapa jobs yang

berada di memory (dan disk)

• CPU hanya dialokasikan kepada jobs yang telah siap dan

berada di memori

• Besar memori masih sangat terbatas:

– Pada job dilakukan swapped in dan out dari memory ke

disk.

• Komunikasi on-line (interaktif) antara user dan sistim: jika

OS telah selesai mengeksekusi satu perintah, menunggu

perintah berikut bukan dari “card reader”, tapi dari

terminal user

– On-line system harus tersedia bagi user yang akan

mengakses data dan kode

12

Desktop Systems

• Personal computers sistim komputer yang

dirancang khusus untuk single user

• I/O devices keyboards, mice, display screens,

small printers.

• User mendapatkan kemudahan dalam penyesuaian.

• Fungsi dasar mirip (adopsi) dari OS pada sistim yang

besar

– Sederhana: tidak terlalu fokus pada utilisasi CPU

dan proteksi

– Contoh: MS-DOS untuk PC banyak mengambil

features dari UNIX, minus proteksi dan CPU

scheduler yang rumit.

13

Parallel Systems

• Sistem multiprosesor: lebih dari satu CPU yang

terhubung secara dekat satu sama lain

• Symmetric multiprocessing (SMP)

– Setiap prosesor menjalankan “identical copy”

dari OS

– Banyak proses dapat berjalan serentak murni

dengan menggunakan resources pada masing-

masing CPU

– Banyak modern operating systems

mendukung SMP

14

Parallel Systems

(next…)

• Asymmetric multiprocessing

– Setiap prosesor telah ditentukan

untuk menjalankan task tertentu

– Master processor mengontrol,

menjadwalkan dan mengalokasikan

task ke slave processors

– Banyak digunakan oleh sistem yang

besar (main-frame)

15

Real-Time Systems

• Digunakan sebagai control device untuk

aplikasi khusus (misalkan medical imaging

systems, industrial control process dll).

• Kemampuan untuk beroperasi, response

dalam batasan “waktu tertentu” OS

harus sederhana, cepat, dan dapat

memenuhi jadwal task (scheduling dll).

16

Real-Time Systems

(next…)

Hard real-time system.

– Secondary storage sangat terbatas atau

tidak ada (menggunakan ROM, flash RAM).

– Task dapat diprediksi/ditentukan: waktu

selesai dan response.

• Soft real-time system

– Lebih leluasa batasan waktu dari “hard real-

time system”.

– Lebih umum digunakan di industri, aplikasi

multimedia (video streaming, virtual reality).

17

Distributed Systems

• Distribusikan kemampuan komputasi dan

“resources” ke berbagai komputer di

jaringan.

• Loosely coupled system

– Setiap prosessor memiliki lokal memori

– Komunikasi prosessor satu dengan yang lain

melalui beragam jalur komunikasi, contoh :

high-speed buses dan jalur telepon.

18

Distributed Systems

(next…)

• Manfaat distributed systems.

– Resources Sharing

– Waktu komputasi cepat– load sharing

– Reliability

– Komunikasi

• Membutuhkan Infrastruktur jaringan.

• Local Area Networks (LAN) atau Wide Area Networks (WAN)

• Sistem bisa berbentuk client-server atau peer-to-peer .

19

Struktur Umum Client-Server

20

Clustered Systems

• Clustering memungkinkan dua atau lebih

sistem melakukan share strorage

• Memiliki realibilitas yang tinggi.

• Asymmetric clustering: satu server

menjalankan aplikasi sementara server

lain dalam keadaan standby.

• Symmetric clustering: semual N host

menjalankan aplikasi.

21

Handheld Systems

• Personal Digital Assistants (PDAs)

• Telepon seluler

• Issues:

– Memori yang terbatas

– Prosessor yang lambat

– Display screen yang kecil.

22

Migrasi Sistem Operasi vs.

Sistem Komputer

23

Lingkungan Komputasi

• Komputasi Tradisional

• Komputasi berbasis Web (Web-Based

Computing)

• Komputasi pada Embedded System

(Embedded Computing)

24

Struktur Sistem Operasi

• Komponen Sistem

• Layanan Sistem Operasi

• System Calls

• Program System

• Struktur System

• Virtual Machines

• System Design dan Implementation

• System Generation

25

Komponen Sistem Umum

• Manajemen Proses

• Manajemen Main Memory

• Manajemen File

• Manajaemen I/O System

• Manajemen Secondary Storage

• Command-Interpreter System

Proc

Caches Processor-Memory Bus

Memory

I/O Devices:

Controllers

adapters

Disks

Displays

Keyboards Networks

Semua komponen memiliki organisasi & antar-muka

I/O Bus


(next…)

27

Manajemen Proses

• Proses adalah sebuah program yang sedang dijalankan

(eksekusi).

– Suatu proses memerlukan resources pada saat

ekesekusi: CPU time, memory, files dan I/O devices

• Sistim operasi bertanggung jawab terhadap aktifitas

yang berhubungan dengan manajemen proses:

– Process creation & deletion.

– Process suspension (block) & resumption.

– Mekanisme:

• Sinkronisasi antar proses

• Komunikasi antar proses

28

Manajemen Main-Memory

• Memori sebagai tempat penyimpanan instruksi/data dari

program

– Storage yang cepat sehingga dapat mengimbangi kecepatan

eksekusi instruksi CPU

– Terdiri dari “array of words/bytes” yang besar

– Address digunakan untuk mengakses data (shared oleh CPU dan

I/O devices)

• Umumnya main memory bersifat “volatile” – tidak permanent.

Isinya akan hilang jika komputer di matikan.

• Manajemen memori:

– Melacak pemakaian memori (siapa dan berapa besar?).

– Memilih program mana yang akan diload ke memori.

– Alokasi dan De-alokasi memori fisik untuk program.

29

Manajemen Secondary-Storage

• Secondary Storage: penyimpanan permanen

– Kapasitas harus besar untuk menyimpan semua

program dan data.

– Secondary storage dapat dijadikan “backup” storage

main memory supaya dapat menjalankan banyak

program.

– Umumnya menggunakan “magnetic disks” (hard

disk).

• OS bertanggung jawab untuk manajemen disk:

– Manajemen ruang kosong

– Alokasi storage

– Penjadualan disk

30

Manajemen I/O System

• Sering disebut device manager

– Menyediakan “device driver” yang umum sehingga operasi

I/O dapat seragam (open, read, write, close)

• Contoh: user menggunakan operasi yang sama untuk

read file pada hard disk, CD-ROM dan floppy disk

sama.

• Komponen OS untuk sistim I/O:

– Buffer: menampung sementarai data dari/ke I/O devices

– Spooling: melakukan scheduling pemakaian I/O sistim

supaya lebih efisien (antrian dsb)

– Menyediakan “driver” untuk dapat melakukan operasi “rinci”

(detail) untuk hardware I/O tertentu.

31

Manajemen File

• File: kumpulan informasi yang berhubungan (sesuai

dengan tujuan pembuat file tsb).

– File dapat mempunya struktur yang bersifat hirarkis

(direktori, volume dll).

• OS bertanggung jawab:

– Membuat dan menghapus file.

– Membuat dan menghapus directory.

– Dukungan primitif untuk manipulasi file dan directory.

– Pemetaan file ke dalam secondary storage.

– Backup file ke media storage yang stabil (nonvolatile).

32

Command-Interpreter System

• OS: menunggu instruksi dari user (command driven)

• Program yang membaca instruksi dan mengartikan

keinginal user (lebih dari sejenis).

– Contoh:

• control-card interpreter

• command-line interpreter

• shell (in UNIX)

– Sangat bervariasi dari satu OS ke OS yang lain dan

disesuaikan dengan tujuan, teknologi I/O devices yang ada.

• CLI, Windows, Pen-based (touch) etc.

33

Layanan Sistem Operasi

• Eksekusi Program – Kemampuan sistim untuk “load” program ke memori dan

menjalankan program.

• Operasi I/O – User tidak dapat secara langsung mengakses H/W

resources, OS harus menyediakan mekanisme untuk melakukan operasi I/O atas nama user

• Manipulasi File-system – Kemampuan program untuk operasi pada file (to read,

write, create, and delete files).

34

Layanan Sistem Operasi

(next…) • Komunikasi

– Pertukaran data/informasi antar dua atau lebih proses yang

berada pada satu komputer (atau lebih).

• Deteksi Error

– Menjaga kestabilan sistim dengan mendeteksi “error”:

hardware maupun operasi.

• Penggunaan System yang Efisien

– Proteksi : menjamin akses ke system resources dikendalikan

(user dikontrol akses ke sistim).

– Accounting: merekam kegiatan users, jatah pemakaian

resources (fairness atau policy).

35

System Call

• System call:

– Menyediakan interface antara program (user program yang berjalan) dan bagian OS.

• System call menjadi jembatan antara proses dan OS.

– System call ditulis dalam assembly language (machine specific) atau bahasa tingkat tinggi yang dapat mengendalikan mesin (C).

– Contoh: UNIX menyediakan system call: read, write => operasi I/O untuk file.

36

System Call : Passing Parameter

• Sering user program harus memberikan data

(parameter) ke rutin OS yang akan dipanggil.

– UNIX: read(buffer, max_size, file_id);

• Tiga cara memberikan parameter dari program ke

sistim operasi:

– Melalui registers (resources di CPU).

– Menyimpan parameter pada data struktur (table) di

memory, dan alamat table tsb ditunjuk oleh pointer yang

disimpan di register.

– Push (store) melalui “stack” pada memori dan OS

mengambilnya melalui pop pada stack tsb.

37

Tabel Passing Parameter

38

Tipe System Calls

• Kontrol Proses

• Manipulasi File

• Managemen Device

• Informasi Lingkungan

• Komunikasi

39

Kontrol Proses

• Mengakhiri (end) dan membatalkan (abort)

• Mengambil (load) dan eksekusi (execute)

• Membuat dan mengakhiri proses

• Menentukan dan mengeset atribut proses

• Wait for time

• Wait event, signal event

• Mengalokasikan dan membebaskan

memori

40

Eksekusi MS-DOS

At System Start-up Running a Program

41

UNIX Menjalankan Multiple Program

42

Manipulasi File

• Membuat dan menghapus file

• Membuka dan menutup file

• Membaca, menulis dan mereposisi file

• Menentukan dan mengeset atribut file

43

Manajemen Device

• Meminta dan membebaskan device

• Membaca, menulis dan mereposisi device

• Menentukan dan mengeset atribut device

44

Informasi Lingkungan

• Mengambil atau mengeset waktu atau

tanggal

• Mengambil atau mengeset sistem data

• Mengambil atau mengeset proses, file

atau atribut-atribut device

45

Komunikasi

• Membuat dan mengahpus sambungan

komunikasi

• Mengirim dan menerima pesan

• Mentransfer status informasi

46

Komunikasi

(next…)

Message Passing Shared Memory

Komunikasi dilakukan dengan

melewatkan pesan atau sharing

memori

47

Program Sistem

• Program sistem menyediakan kemudahan

pembangunan program dan eksekusi.

– Manipulasi File

– Informasi status

– Modifikasi File

– Dukungan bahasa pemrograman

– Loading dan eksekusi program

– Komunikasi

– Aplikasi program

• Kebanyakan user memandang sistem operasi

sebagai program sistem, bukan sebagai

“actual system calls”.

48


• Struktur Sistem Operasi

– Metode untuk mengorganisasi dan membangun sistem operasi

• Contoh: MS-DOS

– Saat dirancang kemampuan PC sangat minimal

• Prosesor: 8086 (10 MHz), Max. memory: 640 Kb

– MS-DOS – dibuat dengan menyediakan “fungsional” dari OS sebanyak mungkin pada resources yang sangat terbatas (memori)

– Tidak dalam bentuk modul => monolithic (satu kesatuan):

• MS-DOS menjadi satu kesatuan besar tanpa batasan jelas – fungsional dan interface

• Terdapat struktur yang sangat sederhana dan “proteksi” yang longgar (single user system)

49

Struktur Layer MS-DOS

50

Struktur Monolithic

• Tidak terstuktur secara jelas

– Kumpulan program yang menggunakan langsung resources hardware

– Terdapat program-program yang mewakili fungsi OS: processor management, memory management

• OS awal: satu kesatuan proses, dimana kontrol berpindah dari program-program tersebut (“procedure calls)

• Program user (proses): menjadi satu bagian rutin dari (loop) program utama jika tidak melakukan fungsi OS

• User program dijalankan “call” dari OS => eksekusi pada user mode akan berhenti:

– timeout (timer interrupt)

– kembali ke OS (service)

– Interrupt (hardware)

51

Pendekatan Sederhana (Kernel)

• Struktur terbatas pada dua layer

– Systems programs: bagian OS yang dibangun di atas kernel – extended machine

– Kernel

• Operasi vital yang penting dan melindungi resources hardware

• Semua service untuk user proses melalui mekanisme system call

• Tugas utama kernel menyediakan fasilitas untuk: multiprogramming/multitasking – dimana proses-proses dapat berjalan serentak (concurrent) dan terpisah

• UNIX (1978)

– Menggunakan pendekatan rancangan sederhana dengan dukungan H/W yang terbatas (PDP-11)

52

Struktur Sistem UNIX

53

Pendekatan Berlapis

(layer approach) • Susunan berlapis:

– OS dibagi atas sejumlah (lebih dari 2) layer

– Setiap layer melingkupi layer di bawahnya (kendali, akses)

– Layer paling bawah (0) => hardware

– Layer paling atas (N) => user interface

• Rancangan moduler:

– Layer disusun sehingga setiap fungsi/operasi layer atas akan menggunakan “services” pada layer bawah.

54

Sistem Operasi Berlapis

55

Struktur Berlapis OS/2

56

Virtual Machines

• Misalkan terdapat system program => control program yang mengatur pemakaian resources hardware.

• Control program = trap system call + hardware acces.

• Trap suatu software yang memberikan interrupt krn ada error

• Control program memberikan fasilitas ke proses user

– Mendapatkan jatah CPU dan memori.

– Menyediakan interface “identik” dengan apa yang disediakan oleh hardware => sharing devices untuk berbagai proses.

• Virtual machine => control program yang minimal

– VM memberikan ilusi multitasking: seolah-olah terdapat prosesor dan memori ekslusif digunakan (virtual machine).

– VM memilah fungsi multitasking dan implementasi extended machine (tergantung user proses) => flexible dan lebih mudah untuk maintained (proteksi).

57

Model Sistem Virtual Machines

Non-virtual Machine Virtual Machine

Virtual Machines

(next…)

58

Virtual Machines

(next…) • Jika setiap user diberikan satu virtual machine =>user

bebas untuk menjalankan OS (kernel) yang diinginkan pada VM tersebut.

– Potensi lebih dari satu OS dalam satu komputer.

– Contoh:

• IBM VM370: menyediakan VM untuk berbagai OS: CMS (interaktif), MVS, CICS, dll.

– Problem:

• Sharing disk => setiap OS mempunyai file system yang mungkin berbeda.

• IBM: virtual disk (minidisk) yang dialokasikan untuk user melalui VM.

59

Java Virtual Machine

• Program Java dikompile pada platform-

neutral bytecodes yang dieksekusi oleh

Java Virtual Machine (JVM)

• JVM terdiri dari :

- class loader

- class verifier

- runtime interpreter

• Kompiler Just-In-Time (JIT) meningkatkan

kinerja

60

Java Virtual Machine

(next…)

61

Model Client-Server

• Implementasi fungsi OS (extended machine) dapat menjadi bagian dari user proses (client)

– Request service ke server proses (kernel).

– Kernel: terdiri dari server (file, memory, I/O dll) yang melayani request dari client proses.

– Akses ke hardware harus melalui server proses dari kernel yang mengontrol hardware tersebut.

• Proses : partisi dan struktur yang sangat jelas (interface dan fungsional).

• Konsekuensi : lambat (komunikasi antar client dan server), tidak efisien dalam menggunakan resources.

62

Windows NT Client-Server

Structure

63

Perancangan Sistem

Tujuan Perancangan Sistem

• Tujuan User – sistem operasi mudah

digunakan, mudah dipelajari, handal,

aman dan cepat

• Tujuan Sistem – sistem operasi mudah

didisain, diimplementasikan dan dikelola,

memiliki fleksibilitas, handal, bebas

kesalahan dan efisien

64

Implementasi Sistem

• Secara tradisional ditulis dalam bahasa assemby,

saat ini sistem operasi dapat ditulis dalam bahasa

tingkat tinggi.

• Kode yang ditulis dalam bahasa tingkat tinggi :

• Code written in a high-level language:

– Dapat ditulis secara cepat.

– Lebih compact.

– Lebih mudah dipahami dan debug.

• Sistem operasi jauh lebih mudah untuk di port

(dipindahkan ke hardware lain) jika ditulis dalam

bahasa tingkat tinggi)

65

System Generation (SYSGEN)

• Sistem operasi didisain untuk dijalankan pada

berbagai kelas mesin. Sistem harus dikonfirgurasi

untuk setiap komputer secara spesifik

• Program SYSGEN memiliki informasi dalam

mengkonfigurasi sistem hardware secara spesifik

• Booting –awal komputer diaktifkan dengan

melakukan loading kernel.

• Bootstrap program – kode yang disimpan di ROM

yang dapat ditempatkan pada kernel, di load ke

memori dan memulai eksekusi.

Next…

66

1

Sistem Operasi

Struktur Sistem Komputer

2

Arsitektur Sistem Komputer

3

Operasi Sistem Komputer

• CPU devices dan I/O dapat beroperasi secara serentak

(concurrent)

– TujuanyaEfisiensi pemakaian CPU

• Semua request ke I/O dikendalikan oleh I/O systems:

– Setiap device terdapat controller yang mengendalikan device

tertentu, misalkan video display => video card, disk => disk

controller.

– Setiap device controller mempunyai local buffer.

• CPU memindahkan data dari/ke memory ke/dari local buffer.

– Setelah itu controller akan mengirimkan data dari local buffer ke

device.

• Bagaimana mekanisme I/O supaya CPU dapat melakukan

switch dari satu job ke job lain???

4

Operasi Sistem Komputer

(next…)

• Ilustrasi:

– Instruksi CPU dalam orde: beberapa mikro-detik

– Operasi read/write dari disk: 10 – 15 mili-detik

– Ratio: CPU ribuan kali lebih cepat dari operasi I/O

• Jika CPU harus menunggu (idle) sampai data transfer

selesai, maka utilisasi CPU sangat rendah (lebih kecil

1%).

• Solusi: operasi CPU dan I/O harus overlap

– Concurrent: CPU dapat menjalankan beberapa I/O device

sekaligus

– CPU tidak menunggu sampai operasi I/O selesai tapi

melanjutkan tugas yang lain

– Bagaimana CPU mengetahui I/O telah selesai?

5

Programmed I/O

• Programmed I/O

– Mekanisme CPU yang bertanggung jawab

memindahkan data dari/ke memori ke/dari controller

(local buffer)

• CPU bertanggung jawab untuk jenis operasi I/O

– Transfer data dari/ke buffer

• Controller melakukan detil operasi I/O

– Jika telah selesai memberikan informasi ke CPU

flag

• Bagaimana CPU mengetahui operasi telah selesai?

– Apakah menguji flag? Seberapa sering?

6

Programmed I/O

(next…)

• CPU harus mengetahui jika I/O telah selesai

hardware flag (controller)

• Polling: CPU secara periodik menguji flag (true or

false)

– Menggunakan instruksi khusus untuk menguji flag

– Masalah: seberapa sering? “wasted CPU time !”?

Antar I/O device berbeda “speed”!

• Interrupt:

– Bantuan hardware – melakukan interupsi pada

CPU jika flag tersebut telah di-set (operasi I/O telah

selesai)

7

Interrupt

• Interrupt:

– CPU transfer control ke “interrupt service routine”, address dari

service routine yang diperlukan untuk device tsb.

– Interrupt handler: menentukan aksi/service yang diperlukan

• Struktur interrupt harus menyimpan address dari instruksi yang

sedang dikerjakan oleh CPU (interrupted).

– CPU dapat resume ke lokasi tersebut jika service routine telah

selesai dikerjakan

• Selama CPU melakukan service interrupt, maka interrupt

selanjutnya tidak akan dilayani “disabled”, karena CPU tidak

dapat melayani interrupt (lost).

• Pengoperasian sistem tersebut menggunakan interrupt driven.

Proses Interrupt

8

9

Interrupt Handling

• Hardware dapat membedakan devices mana yang

melakukan interupsi.

– Jenis interupsi :

• polling

• vectored interrupt system

• Tugas sistim operasi menyimpan status CPU (program

counter, register dll)

– Jika service routine telah selesai CPU dapat

melanjutkan instruksi terakhir yang dikerjakan

– Sistem operasi akan “load” kembali status CPU

tersebut.

10

Struktur I/O

• User request I/O:

– CPU: load instruksi ke register controller

– Controller: menjalankan instruksi

• Setelah I/O mulai, control kembali ke program user jika operasi I/O telah selesai

– Instruksi khusus: wait CPU menunggu sampai ada interrupt berikutnya dari I/O tersebut.

– Paling banyak hanya mempunyai satu I/O request.

– Keuntungan: CPU mengetahui secara pasti device mana yang melakukan interrupt (operasi I/O selesai).

– Kerugian: operasi I/O tidak dapat serentak untuk semua device

11

I/O Interrupt

• Pilihan lebih baik: asynchronous I/O dibandingkan synchronous

• Setelah I/O mulai, kendali langsung kembali ke user program tanpa menunggu I/O selesai

– CPU dapat melanjutkan operasi I/O untuk device yang lain

– User program dapat menjalankan program tanpa menunggu atau harus menunggu sampai I/O selesai.

– System call – request ke OS untuk operasi I/O dan menunggu sampai I/O selesai.

• Potensi lebih dari satu device

– User hanya dapat menggunakan I/O melalui system call

– Device-status table memuat informasi untuk setiap I/O device: tipe, alamat, status dll

– OS mengatur tabel ini dan mengubah isinya sesuai dengan status device (interrupt)

12

Dua Metode I/O

Synchronous Asynchronous

13

Device-Status Table

14

Direct Memory Access (DMA)

• Jika I/O devices sangat cepat (“high-speed”),beban

CPU menjadi besar harus mengawasi transfer data

dari controller ke memory dan sebaliknya.

• Hardware tambahan => DMA controller dapat

memindahkan blok data dari buffer langsung ke

memory tanpa menggangu CPU.

– CPU menentukan lokasi memory dan jika DMA controller

telah selesai => interrupt ke CPU

– Hanya satu interrupt ke CPU untuk sekumpulan data

(blok).

15

Struktur Storage

• Main memory

– Media penyimpanan, dimana CPU dapat melakukan akses

secara langsung

• Secondary storage

– Tambahan dari main memory yang memiliki kapasitas

besar dan bersifat nonvolatile

• Magnetic disks

– Metal keras atau piringan yang terbungkus material

magnetik

– Permukaan disk terbagi secara logikal dalam track, yang

masing-masing terbagi lagi dalam sector

– Disk controller menentukan interaksi logikal antara device

dan komputer

16

Mekanisme Pergerakan Head-Disk

17

Hirarki Storage

• Hirarki sistem storage, diorganisasikan

dalam bentuk :

– Kecepatan

– Biaya

– Volatilitas

• Caching

– Penduplikasian informasi ke dalam sistem

storage yang cepat dapat dilakukan melalui

cache pada secondary storage

18

Hirarki Storage-Device

19

Caching

• Menggunakan memori berkecepatan tinggi

untuk menangani akses data saat itu juga

(yang terbaru)

• Membutuhkan manajemen cache.

• Caching mengenalkan tingkatan lain

dalam hirarki storage, dimana data secara

serentak disimpan pada lebih dari satu

tingkatan secara konsisten

20

Migrasi dari Disk ke Register

21

Proteksi Hardware

• Dual-Mode Operation

• Proteksi I/O

• Proteksi Memory

• Proteksi CPU

22

Dual-Mode Operation

• Penggunaan resource sharing membutuhkan

sistem operasi yang menjamin suatu program

yang salah tidak menyebabkan program lain tidak

terpengaruh

• Menyediakan dukungan hardware yang dibedakan

ke dalam dua mode operasi :

1. User mode – eksekusi dilakukan untuk

kepentingan user.

2. Monitor mode (disebut juga kernel mode atau

system mode) – eksekusi dilakukan untuk

kepentingan sistem operasi.

23

Dual-Mode Operation

(next…) • Mode bit ditambahkan pada computer hardware (CPU)

untuk indikasi mode sekarang: monitor (0) atau user

(1).

• Jika terjadi interrupt/fault/error hardware mengubah

mode ke monitor

Instruksi Privileged hanya dapat diberikan dalam mode monitor

monitor user

Interrupt/fault

set user mode

24

Proteksi I/O

• Semua instruksi I/O adalah instruksi privileged:

– Hanya dapat dilakukan melalui OS

– OS dapat mencegah “request” ke I/O dengan

melihat mode saat ini.

• OS menjaga supaya program user tidak dapat

menjadi “monitor mode” untuk mencegah user

program melakukan:

– Menangani interrupt: dengan mengubah alamat

interrupt vector.

– Mengubah status dan data pada “device table”

25

Penggunaan System Call untuk

Pengoperasian I/O

26

Proteksi Memory

• Melindungi memori terutama untuk isi:

– interrupt vector dan interrupt service routines.

• Cara umum adalah setiap user program hanya dapat

mengakses lokasi memori yang telah dibatasi

(disediakan untuk program tsb).

– Range address – alamat yang valid

– Base register – menyimpan alamat terkecil memori

secara fisik

– Limit register – besarnya jangkauan memori yang

diijinkan

• Memori diluar range tersebut tidak dapat diakses oleh

user program tsb.

27

Penggunaan Base dan Limit

Register

28

Proteksi Alamat Hardware

Ketika eksekusi pada mode monitor, OS dapat mengakses semua

lokasi memori.

Pemuatan instruksi ke base dan limit register tergantung instruksi

privileged

29

Proteksi CPU

• Timer

– Interupsi secara berkala oleh

hardware:transfer control ke OS.

– Nilai timer akan berkurang sesuai “clock tick”

dari hardware komputer.

– Saat nilai timer menjadi 0, interrupt terjadi

– Housekeeping: melakukan CPU scheduling

(jatah CPU), status device table dll.

• Timer digunakan untuk system time.

Next…

30

1

Sistem Operasi

Proses

2

Konsep Proses

• Sistem operasi menjalankan banyak dan beragam program :

– Batch system jobs

– Time-shared systems user programs atau tasks

– Istilah pada buku teks: job, task dan process (dapat diartikan

sama)

• Proses adalah program yang dieksekusi ;

– Aktif (prosesmemori) vs pasif (program file)

– Instruksi pada program (code) akan dieksekusi secara berurut

(sekwensial) sesuai dengan “line code” (stored program

concept).

• Proses lebih dari “program code yang aktif”:

– Melacak posisi instruksi (sequential execution): program counter

– Menyimpan data sementara var., parameter, return value: stack

– Menyimpan data (initial, global variable dll): data section

– Menyimpan status proses (contoh, aktif, wait I/O request dll.)

3

Status Proses

• Saat-saat proses dijalankan (executed) maka status dari

proses akan berubah

– Status proses tidak selamanya aktif menggunakan CPU).

– Sering proses menunggu I/O complete status wait, maka

sebaiknya CPU diberikan kepada proses yang lain.

– Mendukung multi-tasking utilisasi CPU dan I/O

• Status proses (antara lain):

– New proses dibuat.

– Running instruksi dieksekusi.

– Waiting proses menunggu beberapa event yang akan terjadi

– Ready proses menunggu jatah waktu dari prosessor

– Terminated proses selesai dieksekusi.

4

Diagram Status Proses

5

Informasi Proses

Dimanakah informasi proses disimpan?

• Struktur Data dari OS dalam bentuk table :

– Satu entry table/linked list struktur data untuk menampung

informasi satu proses (array of structure).

– Setiap entry pada tabel proses menyimpan satu proses. Contoh:

MINIX (src/kernel/proc.h) => struct proc { … };

• Informasi yang disimpan:

– Process State new, ready, running, waiting, terminate.

– Program counter Menunjuk alamat berikutnya yang akan

dieksekusi oleh proses tersebut.

– CPU Registeracumulator, index register, stack pointer,

general purpose register.

– Informasi Penjadwalan CPUberisi prioritas dari proses, pointer

ke antrian penjadwalan, dan parameter penjadwalan lainnya.

Informasi Proses

(next…) • Informasi manajemen memoryberisi nilai (basis)

dan limit register, page table atau segmen table.

• Informasi acountingberisi jumlah CPU dan real

time yang digunakan, time limit acount number,

jumlah job/proses.

• Informasi status I/Oberisi deretan I/O device

yang dialokasikan untuk proses, daftar file yang

terbuka, dll.

6

Process Control Block (PCB)

• Masing-masing proses

direpresentasikan oleh

sistem operasi dengan

menggunakan PCB

7

8

CPU Switch Dari Satu Proses ke Proses

Lainnya

9

Penjadualan Proses

• Apakah tujuan dari multiprogramming?

– “Maximize” pemakaian CPU secara efisien (jadwal dan giliran

pemakaian CPU).

CPU digunakan oleh proses-proses terus menerus

• Apakah tujuan dari “time-sharing”?

– Pemakaian CPU dapat di switch dari satu proses ke proses lain

(concurrent process execution)

sesering mungkin, user dapat berinteraksi dengan sistim

• Bagaimana jika sistim prosesor tunggal?

– “Hanya ada satu proses yang dapat dijalankan”

– Proses lain menunggu sampai CPU dapat dijadwalkan (schedule) ke

proses tsb

10

Ready Queue dan I/O Device Queues

11

Penjadualan Proses

• Proses dapat berubah status dan berpindah dari satu antrian ke

antrian yang lain

– Proses dengan status “ready” berada di ReadyQueue

• Menunggu giliran/dipilih oleh scheduler menggunakan

CPU

– Selama eksekusi (status “run”) events yang dapat terjadi:

• I/O request I/O wait berada pada DeviceQueue

• Create “child” proses Jalankan proses “child”, tunggu

sampai proses selesai (wait)

• Time slice expired Waktu pemakaian CPU habis, interrupt

oleh scheduler, proses akan berpindah ke ReadyQueue

12

Representasi Penjadualan Proses

13

Penjadual / Schedulers

• Bagaimana schedulers memilih proses atau program

(decision)?

– Lebih dari satu proses atau program yang akan dijalankan?

• Long-term scheduler (or job scheduler) memilih

proses/program yang mana yang akan di load dan berada di

ready queue.

– Kemungkinan terdapat proses atau job baru.

– Kemungkinan proses dipindahkan dari memori ke disk (swap

out).

• Short-term scheduler (or CPU scheduler) memilih proses

yang mana yang berada di ready queue akan “run”

(mendapatkan jatah CPU).

14

Penjadualan Jangka Menengah


(next…)

15


(next…) • Long-term scheduler tidak sering (proses baru) (seconds,

minutes) (may be slow).

– The long-term scheduler controls the degree of

multiprogramming berapa banyak proses yang dapat aktif

(berada di memori)

• Short-term scheduler dijalankan sangat sering (milliseconds)

giliran pemakaian CPU dari proses- proses yang siap

– Pada saat terjadi penggantian alokasi CPU dari satu proses ke

proses lain:

• Menyimpan informasi internal CPU dari proses yang akan

digantikan (SAVE).

• Meload kembali informasi internal CPU dari proses yang akan

menggantikan.

– Dikenal dengan istilah: context switch proses.

16

Alih Konteks / Context Switch

• Jika Scheduler switch ke proses lain, maka sistim

harus menyimpan “informasi” proses sekarang

(supaya dapat dijalankan kembali)

• Load “informasi” dari proses baru yang berada di

PCB

• Waktu Context-switch adalah overhead; sistem tidak

melakukan pekerjaan saat terjadi switch.

– Sangat tergantung pada waktu di hardware

– OS modern mencari solusi untuk mengurangi overhead

waktu switch proses

17

Pembuatan Proses

• Umumnya proses dapat membuat proses baru (child

process).

– Child process dapat membuat proses baru.

– Terbentuk “tree” dari proses.

• Pilihan hubungan antara parent dan child proses:

– Resource sharing

• Parent dan child berbagi resource

• Children berbagi subset dari resource milik parents.

• Parent dan child tidak berbagi resource.

– Execution

• Parent dan children melakukan eksekusi secara

serempak.

• Parent menunggu hingga children selesai.

18

Pembuatan Proses

(next...) • Address space

– Child menduplikasi parent.

– Child memiliki program yang di load ke dalamnya.

• Contoh UNIX :

– fork system call membuat proses baru

– execve (EXEC) :

• menjalankan program spesifik yang lain

• nama program tersebut menjadi parameter dari system call

• EXEC (sering di load sesudah menjalankan fork).

– Tahapan pembuatan proses baru:

• Periksa apakah masih terdapat ruang pada PCB.

• Mencoba mengalokasikan memori untuk proses baru.

• Mengisi informasi untuk proses baru: nama proses, id, copy data dari parent dll.

• Mencantumkan informasi proses ke kernel OS.

19

Proses Tree pada Sistem

UNIX

20

Terminasi Proses

• Proses dapat berakhir:

– Eksekusi instruksi terakhir (atau keluar: exit system call).

– OS yang akan melakukan dealokasi (memory, file

resources).

• UNIX (MINIX):

– Output signal dari child ke parent

– Jika parent tidak menunggu (via wait system call), proses

akan terminate tapi belum di release dari PCB (status:

ZOMBIE).

– Proses dengan status ZOMBIE (parent telah terminate), akan

menjadi child dari proses “init”.

• Parent dapat menghentikan eksekusi proses child secara paksa.

– Parent dapat mengirim signal (abort, kill system call).

21

Kerjasama Proses

• Proses independent tidak mempengaruhi

eksekusi proses yang lain

• Kerjasama proses dapat mempengaruhi atau

dipengaruhi oleh eksekusi proses yang lain

• Keuntungan kerjasama proses :

– Sharing informasi

– Meningkatkan kecepatan komputasi

– Modularitas

– Kemudahan

22

Masalah Producer-Consumer

• Paradigma kerjasama proses – proses Producer menghasilkan informasi yang akan dikonsumsi oleh proses Consumer

– Unbounded-buffer – tidak menggunakan batasan ukuran di buffer.

• Consumer selalu dapat meminta item baru dan Producer selalu dapat menghasilkan item-item baru.

– Bounded-buffer – menggunakan buffer dengan ukuran tertentu

• Consumer harus menunggu jika buffer kosong dan Producer harus menunggu jika buffer penuh

23

Bounded-Buffer – Solusi dari Shared Memory

• Shared data #define BUFFER_SIZE 10

Typedef struct {

. . .

} item;

item buffer[BUFFER_SIZE];

int in = 0;

int out = 0;

• Solution is correct, but can only use

BUFFER_SIZE-1 elements

24

Bounded-Buffer – Proses Producer

item nextProduced;

while (1) {

while (((in + 1) % BUFFER_SIZE) == out)

; /* do nothing */

buffer[in] = nextProduced;

in = (in + 1) % BUFFER_SIZE;

}

25

Bounded-Buffer – Proses Consumer

item nextConsumed;

while (1) {

while (in == out)

; /* do nothing */

nextConsumed = buffer[out];

out = (out + 1) % BUFFER_SIZE;

}

26

Interprocess Communication (IPC)

• Mekanisme proses untuk komunikasi dan sinkronisasi aksi

• Sistem Pesan – komunikasi proses satu dengan yang lain

dapat dilakukan tanpa perlu pembagian data.

• IPC menyediakan dua operasi :

– send(message) – pesan berukuran pasti atau variabel

– receive(message)

• Jika P dan Q melakukan komunikasi, maka keduanya

memerlukan :

– Membangun jalur komunikasi diantara keduanya

– Melakukan pertukaran pesan melaui send/receive

• Implementasi jalur komunikasi

– physical (shared memory, hardware bus)

– logical (logical properties)

27

Komunikasi Langsung

• Proses harus diberi nama secara jelas :

– send (P, message) – kirim pesan ke proses P

– receive(Q, message) – terima pesan dari

proses Q

• Properti jalur komunikasi

– Jalur dibangun secara otomatis

– Setiap jalur memiliki pasangan masing-masing

dalam proses komunikasi

– Jalur komunikasi tersebut biasanya directional

28

Komunikasi Tidak Langsung

• Pesan dikirim dan diterima melalui mailboxes

(yang ditunjuk sebagai port)

– Proses

– Processes can communicate only if they share

a mailbox.

• Properti jalur komunikasi

– Jalur komunikasi hanya dibangun jika proses

di-share dalam mailbox

– Jalur merupakan gabungan beberapa proses

– Setiap pasangan proses dibagi ke dalam

beberapa jalur komunikasi.

29


(next…) • Operasi

– Membuat mailbox baru

– Mengirim dan menerima pesan melalui

mailbox

– Menghapus/memusnahkan mailbox

• Primitive didefinisikan :

send(A, message) – kirim pesan ke mailbox A

receive(A, message) – terima pesan dari

mailbox A

30


(next…) • Mailbox sharing

– P1, P2, dan P3 berbagi (share) mailbox A.

– P1, send; P2 and P3 receive.

– Siapa yang mendapat pesan ?

• Solusi

– Memperbolehkan suatu jalur yang merupakan

gabungan lebih dari dua proses

– Hanya meperbolehkan satu proses pada suatu waktu

untuk mengeksekusi operasi receive .

– Memperbolehkan sistem untuk memilih receiver.

Sender diberitahu siapa yang menjadi receiver.

31

Sinkronisasi

• Pesan yang disampaikan dapat di blok atau

tidak (non-blocking)

• Blocking dikenal dengan synchronous.

• Non-blocking dikenal dengan

asynchronous

32

Buffering

• Antrian pesan yang dihubungkan dalam suatu jalur, diimplementasikan dengan tiga jalan :

1. Zero capacity – tidak ada pesan - Sender harus menunggu receiver.

2. Bounded capacity – memiliki panjang yang terbatas (finite length) dari n pesan. - Sender menunggu pada saat jalur penuh.

3. Unbounded capacity – memiliki panjang tidak terbatas (infinite length) - Sender tidak pernah menunggu.

33

Komunikasi Client-Server

• Sockets

• Remote Procedure Calls (RPC)

• Remote Method Invocation (Java)

34

Sockets

• Suatu socket didefinisikan sebagai titik

akhir (endpoint) komunikasi

• A socket is defined as an endpoint for

communication.

• Gabungan IP address dan port

• Socket 161.25.19.8:1625 mengacu pada

port 1625 pada host 161.25.19.8

• Komunikasi berada diantara pasangan

socket

35

Komunikasi Socket

36

Remote Procedure Calls (RPC)

• Remote Procedure Call (RPC) adalah abstraksi

pemanggilan prosedur diantara proses pada sistem

jaringan

• Stubs – proxy sisi client untuk prosedur aktual pada server

• Stub sisi client ditempatkan di server dengan parameter

marshalls.

• Marshalling proses untuk mengambil koleksi data dan

menyusunnya ke dalam sebuah bentuk yang bisa

dilakukan transmisi

• Stub sisi server menerima pesan, membongkarnya dengan

parameter marshall dan menjalankan prosedur pada

server.

37

Eksekusi RPC

38

Remote Method Invocation (RMI)

• Remote Method Invocation (RMI) adalah mekanisme pada

JAVA yang hampir sama dengan RPC

• RMI membolehkan program JAVA pada satu mesin untuk

menggunakan metode untuk melakukan remote objek.

39

Parameter Marshall

Next…

40

1

Sistem Operasi

Deadlock

2

Masalah Deadlock

• Sekumpulan proses sedang blocked karena setiap

proses sedang menunggu (antrian) menggunakan

“resources” yang sedang digunakan (hold) oleh

proses lain.

• Contoh:

– OS hanya mempunyai akes ke 2 tape drives.

– P1 dan P2 memerlukan 2 tape sekaligus untuk

mengerjakan task (copy).

– P1 dan P2 masing-masing hold satu tape drives dan

sedang blocked, karena menunggu 1 tape drives

“available”.

3

Contoh Persimpangan Jalan

• Hanya terdapat satu jalur

• Mobil digambarkan sebagai proses yang sedang menuju

sumber daya.

• Untuk mengatasinya beberapa mobil harus preempt

(mundur)

Sangat memungkinkan untuk terjadinya starvation

(kondisi proses tak akan mendapatkan sumber daya).

4

Resource-Allocation Graph

Sekumpulan vertex V dan sekumpulan edge E

• V dipartisi ke dalam 2 tipe

– P = {P1, P2, …, Pn}, terdiri dari semua proses dalam sistem.

– R = {R1, R2, …, Rm}, terdiri dari semua sumberdaya dalam

sistem

• request edge/permintaan edge : arah edge P1 Rj

• assignment edge/penugasan edge – arah edge Rj Pi

5


(next…) • Process

• Resource Type with 4 instances

• Pi requests instance of Rj

• Pi is holding an instance of Rj

Pi

Rj

Pi

Rj

6


(next…)

7

Graf Resource Allocation Dengan Deadlock

8

Graf Resource Allocation dengan Cycle Tanpa Deadlock

9

Kondisi yang Diperlukan untuk Terjadinya Deadlock

• Mutual Exclusion

– Serially-shareable resources (mis. Buffer)

– Contoh: Critical section mengharuskan mutual

exclusion (termasuk resource), sehingga

potensi proses akan saling menunggu

(blocked).

• Hold & wait :

– Situasi dimana suatu proses sedang hold

suatu resource secara eksklusif dan ia

menunggu mendapatkan resource lain (wait).

10

Kondisi yang Diperlukan untuk Terjadinya Deadlock

(next…)

• No-Preemption Resource :

– Resource yang hanya dapat dibebaskan secara

sukarela oleh proses yang telah mendapatkannya

– Proses tidak dapat dipaksa (pre-empt) untuk

melepaskan resource yang sedang di hold

• Circular wait

– Situasi dimana terjadi saling menunggu antara

beberapa proses sehingga membentuk waiting chain

(circular)

– Misalkan proses (P0, P1, .. Pn) sedang blok menunggu

resources: P0 menunggu P1, P1 menunggu P2, .. dan Pn

menunggu P0.

11

Metode Penanganan Deadlock

• Deadlock Prevention: Pencegahan

adanya faktor-faktor penyebab deadlock

• Deadlock Avoidance: Menghindari dari

situasi yang potensial dapat mengarah

menjadi deadlock

• Deadlock Detection: Jika deadlock

ternyata tidak terhindari maka bagaimana

mendeteksi terjadinya deadlock, dilanjutkan

dengan penyelamatan (recovery).

12

Deadlock Prevention

• Pencegahan: Faktor-faktor penyebab deadlock

yang harus dicegah untuk terjadi

• 4 faktor yang harus dipenuhi untuk terjadi

deadlock:

– Mutual Exclusion: pemakaian resources.

– Hold and Wait: cara menggunakan resources.

– No preemption resource: otoritas/hak.

– Circular wait: kondisi saling menunggu.

• Jika salah satu bisa dicegah maka deadlock pasti

tidak terjadi!

13

Deadlock Prevention

(next…) • Tindakan preventif:

– Batasi pemakaian resources

– Masalah: sistim tidak efisien, tidak feasible

• Mutual Exclusion:

– tidak diperlukan untuk shareable resources

– read-only files/data : deadlock dapat dicegah dengan tidak membatasi akses (not mutually exclusive)

– tapi terdapat resource yang harus mutually exclusive (printer)

14

Deadlock Prevention

(next…) • Hold and Wait

– Request & alokasi dilakukan saat proses start

(dideklarasikan dimuka program)

– Request hanya bisa dilakukan ketika tidak

sedang mengalokasi resource lain; alokasi

beberapa resource dilakukan sekaligus dalam

satu request

– Simple tapi resource akan dialokasi walau

tidak selamanya digunakan (low utilization)

serta beberapa proses bisa mengalami

starvation

15

Deadlock Prevention

(next…) • Mencegah Circulair Wait

– Pencegahan: melakukan total ordering terhadap semua jenis resource

– Setiap jenis resource mendapatkan index yang unik dengan bilangan natural: 1, 2, . .

• Contoh: tape drive=1, disk drive=5, printer=12

– Request resource harus dilakukan pada resource-resource dalam urutan menaik (untuk index sama - request sekaligus)

– Jika Pi memerlukan Rk yang berindeks lebih kecil dari yang sudah dialokasi maka ia harus melepaskan semua resource Rj yang berindeks ≥ Rk

16

Deadlock Prevention

(next…) • Mencegah No-Preemption

– Jika proses telah mengalokasi resource

dan ingin mengalokasi resource lain –

tapi tidak diperoleh (wait) : maka ia

melepaskan semua resource yang telah

dialokasi.

– Proses akan di-restart kelak untuk

mecoba kembali mengambil semua

resources

17

Deadlock Avoidance

• Pencegahan:

– Apabila di awal proses; OS bisa mengetahui resource mana saja yang akan diperlukan proses.

– OS bisa menentukan penjadwalan yang aman (“safe sequence”) alokasi resources.

• Model:

– Proses harus menyatakan max. jumlah resources yang diperlukan untuk selesai.

• Algoritma “deadlock-avoidance” secara dinamik akan memeriksa alokasi resource apakah dapat mengarah ke status (keadaan) tidak aman (misalkan terjadi circulair wait condition)

• Jadi OS, tidak akan memberikan resource (walaupun available), kalau dengan pemberian resource ke proses menyebakan tidak aman (unsafe).

18

Safe, unsafe, deadlock state

19

Safe state

• Prasyarat:

– Proses harus mengetahui max. resource yang diperlukan (upper bound) => asumsi algoritma.

– Proses dapat melakukan hold and wait, tapi terbatas pada sekump lan resource yang telah menjadi “kreditnya”.

• Setiap ada permintaan resource, OS harus memeriksa

– “jika resource diberikan”, dan terjadi “worst case” semua proses melakukan request “max. resource”

– Terdapat “urutan yang aman” dari resources yang available, untuk diberika ke proses, sehingga tidak terjadi deadlock.

20

Kondisi Safe

• Resources: 12 tape drive.

A (Available): 12 - 10 = 2

Safe sequnce:

2 tape diberikan ke U2,

U2 selesai => Av = 6,

Berikan 3 tape ke U1,

Berikan 3 tape ke U3.

No deadlock.

21

Kondisi Unsafe

• Resources: 12 tape drive.

A (Available): 12 - 11 = 1

Terdapat 1 tape available,

sehingga dapat terjadi

Deadlock.

22

Algoritma Banker’s

• Proses harus “declare” max. kredit resource yang diinginkan.

• Proses dapat block (pending) sampai resource diberikan.

• Banker’s algorithm menjamin sistim dalam keadaan safe state.

• OS menjalankan Algoritma Banker’s,

– Saat proses melakukan request resource.

– Saat proses terminate atau release resource yang digunakan => memberikan resource ke proses yang pending request.

23


(next…) • Metode :

1. Scan tabel baris per baris untuk

menemukan job yang akan diselesaikan

2. Tambahkan pada job terakhir dari

sumberdaya yang ada dan berikan nomor

yang available

– Ulangi 1 dan 2 hingga :

• Tidak ada lagi job yang diselesesaikan

(unsafe) atau

• Semua job telah selesai (safe)

24


(next…) • Misakan terdapat: n proses dan m resources.

• Definisikan:

– Available: Vector/array dengan panjang m.

If available [j] = k, terdapat k instances resouce jenis Rj yang dapat digunakan.

– Max: matrix n x m.

If Max [i,j] = k, maka proses Pi dapat request paling banyak k instances resource jenis Rj.

– Allocation: matrix n x m.

If Allocation[i,j] = k maka Pi saat ini sedang menggunakan

(hold) k instances Rj.

– Need: matrix n x m.

If Need[i,j] = k, maka Pi palaing banyak akan membutuhkan

instance Rj untuk selesai.

– Need [i,j] = Max[i,j] – Allocation [i,j].

25

Algoritma Safety

• Let Work and Finish be vectors of length m and n,respectively. Initialize:

Work := Available // resource yang free

Finish [i] = false for i = 1,3, …, n.

• Find and i such that both: // penjadwalan alokasi resource

(a) Finish [i] = false // asume, proses belum complete

(b) Needi £ Work // proses dapat selesai, ke step 3

If no such i exists, go to step 4.

• Work := Work + Allocationi // proses dapat selesai

Finish[i] := true

go to step 2.

• If Finish [i] = true for all i, then the system is in a safe state.

26

Algoritma Safety

(next…) • Terdapat 3 proses: n = 3, 1 resource: m = 1

• Jumlah resource m = 12.

• Snapshot pada waktu tertentu:

27

Algoritma Safety

(next…)

Let Need[3]; Max[3]; Aloc[3]; Finish[3]; Work [1];

1. Work = Available; // Work = 2;

Finish[0]=false, Finish[1]=false, Finish[3]=false;

2. do { FlagNoChange = false;

for I=0 to 2 {

if ((Finish[I] == false)) && (Need[I] <= Work) {

Finis[I] = true;

Work = Work + Aloc[I]; FlagNoChange = true;

}

} until (FlagNoChange);

28

Deadlock Detection

• Mencegah dan menghidari dari deadlock sulit

dilakukan:

– Kurang efisien dan utilitas sistim

– Sulit diterapkan: tidak praktis, boros resources

• Mengizinkan sistim untuk masuk ke “state deadlock”

– Gunakan algoritma deteksi (jika terjadi deadlock)

• Deteksi: melihat apakah penjadwalan pemakaian resource

yang tersisa masih memungkinkan berada dalam safe

state (variasi “safe state”).

– Skema recovery untuk mengembalikan ke “safe state”

29

Single Instance

• Gunakan: resource allocation graph

– Node mewakili proses, arcus mewakili

request dan hold dari resources.

– Dapat disederhanakan dalam “wait-for-graph”

• Pi Pj if Pi is waiting for Pj.

– Secara periodik jalankan algoritma yang

mencari cycle pada graph:

• Jika terdapat siklus (cycle) pada graph

maka telah terjadi deadlock.

30

Recovery dari Deadlock

• Batalkan semua proses deadlock

• Batalkan satu proses pada satu waktu hingga siklus

deadlock dapat dihilangkan

• Proses mana yang dapat dipilih untuk dibatalkan ?

– Proses dengan prioritas

– Proses dengan waktu proses panjang

– Sumberdaya proses yang telah digunakan

– Sumberdaya proses yang lengkap

– Banyak proses yang butuh untuk ditunda

– Apakah proses tersebut interaktif atau batch

31

Recovery dari Deadlock

(next…) • Pilih proses – meminimasi biaya

• Rollback – kembali ke state safe, mulai

lagi proses dari state tersebut

• Starvation – proses yang sama selalu

diambil sebagai pilihan, termasuk rollbak

dalam faktor biaya

32

Pendekatan Kombinasi

• Kombinasi dari tiga pendekatan dasar

– prevention

– avoidance

– detection

• Pemisahan sumberdaya ke dalam hirarki

kelas

Next…

33

1

Sistem Operasi

Memory

2

Memory Management

• Latar Belakang

• Swapping

• Contiguous Allocation

• Paging

• Segmentation

• Segmentation dengan Paging

3

Latar Belakang

Untuk dieksekusi program harus berada dalam

memori

Eksekusi: proses

Alokasi resources memori: ruang (tempat storage) untuk

menyimpan data, instruksi, stack dll.

Problem: Memori secara fisik (besarnya storage)

sangat terbatas ukurannya,

Manajemen storage: alokasi dan dealokasi untuk proses-

proses

Utilisasi: optimal dan efisien

4

alamat Binding

• Sebalum eksekusi program berada di

dalam disk, dan saat dieksekusi ia perlu

berada pada suatu lokasi dalam memori

fisik

• alamat binding adalah menempatkan

alamat relatif ke dalam adress fisik memori

yang dapat berlangsung dalam di salah

satu tahapan: kompilasi, load, atau

eksekusi

5

Tahapan Running Program

• Tahapan kompilasi: source program

(source code) dikompilasi menjadi object

module (object code)

• Tahapan link & load: object module di-link

dengan object module lain menjadi load

module (execution code) kemudian di-load

ke memori untuk dieskekusi

• Tahapan eksekusi: mungkin juga

dilakukan dynamic linking dengan

resident library

6

Alamat Binding: Saat Kompilasi

Jika lokasi dari proses sudah diketahui

sebelumnya maka saat kompilasi alamat-

alamat instruksi dan data ditentukan

dengan alamat fisik

jika terjadi perubahan pada lokasi tersebut

maka harus direkompilasi

7

Alamat Binding: Saat Load

Code hasil kompilasi masih menunjuk

alamat-alamat secara relatif, saat di-load

alamat-alamat disubstitusi dengan alamat

fisik berdasar relokasi proses yang

diterima

Jika terjadi perubahan relokasi maka code

di-load ulang

8

Alamat Binding: Saat Eksekusi

• Binding bisa dilakukan ulang selama

proses

– hal ini untuk memungkinkan pemindahan

proses dari satu lokasi ke lokasi lain selama

run

• Perlu adanya dukungan hardware untuk

pemetaan adress

– contoh: base register dan limit register

9

Tahapan Pemrosesan User rogram

10

Ruang Alamat Logik vs. Fisik

• Konsep ruang alamat logik terhadap ruang alamat

fisik adalah hal pokok dalam manajemen memori

• alamat logik: alamat yang di-generate oleh CPU

(disebut juga virtual alamat)

– Berdasarkan eksekusi program

– Note: Besarnya alamat program dapat lebih besar dari

kapasitas memori fisik.

• alamat fisik: alamat yang dikenal oleh unit memory

– alamat sebenarnya yang digunakan untuk mengakses

memori.

• Perlu ada penerjemahan (translasi) dari alamat logik

ke alamat fisik.

11

Memory-Management Unit

(MMU) • Perangkat Hardware yang memetakan alamat logik

(virtual) ke alamat fisik.

• Dalam skema MMU

– Menyediakan perangkat register yang dapat di set oleh

setiap CPU: setiap proses mempunyai data set register tsb

(disimpan di PCB).

• Base register dan limit register.

– Harga dalam register base/relokasi ditambahkan ke setiap

address proses user pada saat run di memori

– Program user hanya berurusan dengan addressaddress

logik saja

12

Relokasi Dinamik menggunakan

Register Relokasi

13

Dynamic Loading

• Rutin tidak akan di load jika tidak dipanggil (execute).

• Pro’s: utilisasi memory-space, rutin yang tidak dieksekusi

tidak akan dipanggil (program behaviour: 70-80% dari code).

– Handling execption, error, atau pilihan yang jarang

digunakan.

• Tidak perlu dukungan khusus dari OS:

– Overlay: memori terbatas dan program lebih besar dari

memori.

– Disusun berdasarkan hirarkis dalam bentuk tree: root –

branch dan leaves (misalkan root harus ada di memory,

sedangkan yang lain dapat di load bergantian).

– Tidak dilakukan otomatis tapi harus dirancang oleh

programmer (user).

14

Dynamic Linking

• Linking ditunda sampai saat eksekusi

– code menjadi berukuran kecil.

• Program-program user tidak perlu menduplikasi

system library

– system library dipakai bersama

– Mengurangi pemakaian space: satu rutin library di

memory digunakan secara bersama oleh sekumpulan

proses.

– Contoh: DLL (dynamic linking library) Win32

• Mekanisme menggunakan skema Stub

– stub: suatu potongan kecil code menggantikan referensi

rutin (dan cara meload rutin tsb)

15

Overlay

• Overlay membagi program yang besar menjadi

bagian-bagian yang lebih kecil dan daat dimuat

dalam memori utama.

• Dibutuhkan ketika proses yang ada lebih besar

dibandingkan memori yang tersedia

• Diimplementasikan oleh user, tidak ada dukungan

khusus dari sistem operasi, disain program pada

struktrur overlay cukup kompleks.

16

Overlay pada Two-Pass Assembler

17

Swapping

• Suatu proses dapat di-swap secara temporary keluar dari memori dan dimasukkan ke backing store, dan dapat dimasukkan kembali ke dalam memori pada eksekusi selanjutnya.

• Backing store –disk cepat yang cukup besar untuk mengakomodasi copy semua memori image pada semua user; menyediakan akses langsung ke memori image.

• Roll out, roll in – varian swapping yang digunakan dalam penjadualan prioritas; proses dengan prioritas rendah di-swap out, sehingga proses dengan prioritas tinggi dapat di-load dan dieksekusi.

• Bagian terbesar dari swap time adalah transfer time, total transfer time secara proporsional dihitung dari jumlah memori yang di swap.

• Modifikasi swapping dapat ditemukan pada sistem UNIX, Linux dan Windows.

18

Skema Swapping

19

Contiguous Allocation

• Memori utama biasanya terbagi dalam dua bagian:

– Resident operating system, biasanya tersimpan di alamat

memori rendah termasuk interrupt vector .

– User proces menggunakan memori beralamat tinggi/besar.

• Single-partition allocation

– Relokasi register digunakan untuk memproteksi masing-

masing user proses dan perubahan kode sistem operasi

dan data.

– Relokasi register terdiri dari alamat fisik bernilai rendah;

limit register terdiri dari rentang/range alamat logik, setiap

alamat logik harus lebih kecil dari limit register.

20

Dukungan Hardware untuk Relokasi dan Limit

Register

21

Multiple-Partition Allocation

• Partisi Fixed-Sized (MFT) – Memori dibagi menjadi beberapa blok dengan ukuran

tertentu yang seragam

– Jumlah proses yang bisa running max hanya sejumlah blok yang disediakan(misal IBM OS/360)

• Partisi Variabel-Size (MVT) – Pembagian memori sesuai dengan request dari proses-

proses yang ada.

• Lebih rumit karena ukuran alokasi (partisi) memori dapat bervariasi

– Peranan memori manajemen semakin penting: list dari partisi yang digunakan, free dll.

22

Contoh: Multiple Allocation

23

Masalah pada Dynamic Storage-

Allocation

Bagaimana agar proses berukuran n dapat menempati

hole yang bebas

• First-fit: Mengalokasikan proses pada hole pertama

yang ditemui yang besarnya mencukupi

• Best-fit: Mengalokasikan proses pada hole dengan

besar paling cocok (fragmentasinya kecil).

• Worst-fit: Mengalokasikan proses pada hole dengan

fragmentasi terbesar.

First-fit dan best-fit lebih baik dibandingkan worst-fit dalam

hal kecepatan dan pemanfaatan storage.

24

Fragmentasi (issue)

• External (masalah variable sized partition):

– Ruang memori free, namun tidak contiguous.

– Hole-hole ada di antara proses-proses berturutan.

– Tidak dapat digunakan karena proses terlalu

besar untuk menggunakannya.

• Internal (masalah fixed size):

– Sifat program dinamis (alokasi dan dealokasi).

– Memori yang teralokasi mungkin lebih besar

dari memori yang diminta (wasted).

25

Paging

• Membagi memori fisik ke dalam blok (page, frame)

dengan ukuran tertentu (fixed) yang seragam.

– Memudahkan manajemen free memory (hole) yang dapat

bervariasi.

– Tidak perlu menggabungkan hole menjadi blok yang besar

seperti pada variable partition (compaction).

– OS lebih sederhana dalam mengontrol (proteksi dan

kebijakan) pemakaian memori untuk satu proses.

• Standard ukuran blok memori fisik yang

dialokasikan (de-alokasi) untuk setiap proses.

– Ukuranya (tergantung OS): 512 byte s/d 16 KB.

26

Page Allocation

• Alokasi:

– Terdapat “free list” yang menyimpan informasi “frame” di

memori fisik yang tidak digunakan

– Tergantung besarnya proses => memerlukan n pages

– Alokasi frame diberikan sesuai dengan permintaan

(demand, expand).

• Implikasi:

– User’s (program) view (logical address): memori

dialokasikan secara sinambung (contiguous)

– Fakta (physical address): memori fisik tersebar

(noncontiguous) sesuai dengan frame yang dialokasikan.

27

Skema Paging

• Bagaimana menjembatani antara “user’s view” dan alokasi memori sebenarnya? – Penerjemahan (translasi) alamat logical ke alamat fisik =>

tugas dari OS (user/program “transparant”).

– Perlu dukungan hardware (CPU) => address translation.

• Setiap proses mempunyai informasi “pages” yang dialokasikan oleh OS – Mapping setiap alamat logical ke alamat fisik

– Issue: mekanisme mudah, cepat dan efisien.

– Page table: berisi “base address” (alamat fisik) dari frame yang telah dialokasikan ke proses tsb.

28

Page table

• Setiap OS mempunyai cara menyimpan page table

untuks setiap proses

• Page table bagian dari setiap proses.

– Page table berada di memori, saat proses tersebut

dieksekusi.

– Informasi page table disimpan oleh PCB: pointer ke page

table dari proses tersebut.

– Setiap kali terjadi context switch => informasi page table

untuk proses yang baru harus di restore (misalkan

referensi/pointer lokasi page table tsb. di memori).

29

Page table (h/w support)

• Menggunakan “fast register” – Contoh: DEC PDP11 : 16 bit address (logical 216 ): 64K, page size

8K (213 ).

– Memerlukan page table dengan: 8 entry (dapat diterapkan pada hardware register, hanya 3 bit)

• Untuk komputer modern sulit menggunakan fast register – Pentium : 32 bit address logical (total: 4 GB), page size (8K), maka

mempunyai potensi entry: 524.288 entry.

– Page table disimpan pada memori (bagian program) dengan menggunakan page table base register

– Page-table base register (PTBR) : pointer ke page-table di memori.

– Page-table length register (PTLR) : besarnya ukuran page table (karena tidak semua proses memerlukan ukuran page tabel max.)

30

Paging: translation

• Address logik dari CPU dianggap terdiri atas dua

bagian:

– Page number (p): merupakan indeks dalam tabel yang

berisi base address dari tiap page dalam memori fisik

– Page offset (d): menunjukkan lokasi address memori

berdasarkan “base address” pada page tersebut.

31

Address: hardware support

32

Contoh Paging

33

Model Paging

34

Contoh :

• Misalkan LA: 4 bits (max. logical addres:

16 lokasi)

– Page size => 4 bytes (ditentukan oleh

designerOS).

• 2 bits: menunjuk ke alamat dari masing-masing

byte dalam setiap page tersebut.

– Page table: tersisa 2 bits

• Max. 4 entry

• Jadi setiap proses max. akan menggunakan 4

pages => mencakup seluruh alamat logical.

35

Contoh (2)

36

Contoh (3) :

• Logical address: 11 10 (program view: 14 desimal => “o”)

• Page translation (physical memory allocation):

– Bagian: p (index page) => base address dari frame.

Binary 11 => 3 (index = 3 dari page table)

=> berisi base address untuk frame 2 di memori.

– Bagian offset: d (displacement)

Binary 10 => 2

– Alamat fisik:

base address frame 2 : 2 * 4 => 8;

=> 8 + 2 = 10 (berisi “o”).

37

Frame table

• OS harus mempunyai informasi “frame” dari memori fisik:

– Berapa banyak frame yang bebas?

– Mana saja frame yang bebas (identifikasi) => frame table (list)

– Informasi hubungan antara satu frame dengan page mana dari proses yang aktif

– List ini akan terus di-update, misalkan jika proses terminate maka semua frame yang dialokasikan akan di kembalikan ke free list.

38

Frame Bebas

Before allocation After allocation

39

Page size

• Fragmentasi internal pada page terakhir – Tidak ada fragmentasi eksternal

– Fragmentasi internal bisa terjadi

– Worst-case: • Untuk proses yang memerlukan n page + 1 byte

• bila ukuran page = 4096 byte maka akan terbuang 4095 byte / process

– Besarnya ukuran pages • Independent dari program/proses (system wide)

• Intuitif: small pages preferable – Apakah keuntungan ukuran pages kecil?

• Page table entry dapat dikurangi dengan memperbesar ukuran pages – Apakah keuntungan ukuran pages besar?

• Umumnya page disesuaikan dengan kapasitas memori (tipikal) pada sistim (range: 2 – 8 Kbytes)

40

Implementasi Page Table

• Page table disimpan di main memory.

• Page-table base register (PTBR) menunjuk ke page table.

• Page-table length register (PRLR) mengindikasikan ukuran

page table.

• Pada skema ini, setiap akses data/instruksi membutuhkan

dua memori akses. Satu untuk page table dan satu untuk

data/instruksi.

• Masalah yang ada pada dua akses memori dapat

diselesaikan dengan menggunakan cache memori

berkecepatan tinggi yang disebut associative memory or

translation look-aside buffers (TLBs)

41

Paging Hardware dengan TLB

42

Multilevel Paging

• Address logical besar => page table menjadi besar.

– Misalkan: LA => 32 bits, dan ukuran page frame: 12 bits,

maka page table: 20 bits (2^20 => 1 MB).

– Page table dapat dipisah dalam bentuk pages juga,

sehingga tidak semua page table harus berada di memori.

• Address lojik terdiri atas: section number s, page

number p, offset d

– s indeks ke dalam outer page table dan p displacement

dalam page table

43

Two level page table

44

Translation: multilevel

45

Proteksi Memory

• Proteksi memori diimplementasikan dengan

asosiasi proteksi bit pada setiap frame

• Valid-invalid bit ditambahkan/dimasukkan

pada page table :

– Bit akan diset valid jika page yang bersangkutan

ada pada area ruang alamat logika

– Bit akan diset “invalid” jika page yang

bersangkutan berada di luar area ruang alamat

logika.

46

Valid (v) or Invalid (i) Bit pada

Page Table

47

Inverted Page Table

• Satu masukan untuk setiap real page dari

memori

• Masukan dari alamat virtual disimpan

pada lokasi real memori, dengan informasi

proses pada page

• Penurunan memori dibutuhkan untuk

menyimpan setiap page table, tetapi

setiap kenaikan waktu dibutuhkan untuk

mencari tabel saat pager refference

dilakukan

48

Arsitektur Inverted Page Table

49

Shared Pages

• Shared code

– Satu copy kode read-only (reentrant) dibagi diantara

proses (contoh text editor, compiler, window system).

– Shared code harus dimunculkan pada lokasi yang sama

pada alamat logik semua proses.

• Private code dan data

– Setiap proses menyimpan sebagian copy kode dan data.

– Page untuk kode private dan data dapat ditampilkan

dimana saja pada ruang alamat logik.

50

Contoh Shared Pages

51

Segmentasi

• Skema pengaturan memori yang mendukung user untuk melihat memori tersebut..

• Sebuah program merupakan kumpulan dari segment. Sebuah segement berisi unit logik seperti: main program,

procedure,

function,

method,

object,

local variables, global variables,

common block,

stack,

symbol table, arrays

52

User View Program

53

Pandangan Logik Segmentasi

1

3

2

4

1

4

2

3

user space physical memory space

54

Arsitektur Segmentasi

• Alamat logik terdiri dari dua tuple:

<segment-number, offset>,

– Harus diset oleh programmer atau compiler untuk

menyatakan berapa besar segment tersebut

– Implikasi: segment bervariasi besarnya (bandingkan

dengan page table: fixed dan single/flat address space =>

hardware yang menentukan berapa size)

• Segment table – mapping dari LA ke PA

– base table – berisi lokasi awal dari physical address

dimana segment berada di memori.

– limit table – berisi panjang (besar) dari segmen tersebut.

55

Arsitektur Segmentasi (Cont.)

• Relokasi.

– Dynamic

– Melalui segment table

• Sharing.

– Shared segments

– Nomor segment yang sama

• Alokasi.

– first fit/best fit

– external fragmentation

56

Segmentasi Hardware

57

Contoh Segmentasi

58

Sharing of Segments

59

Segmentasi Paging

• Intel 386

– Logical address (32 bits) dibagi atas 2:

• Selector: Segment: S (13 bits), Descriptor Table (1 bit:

Local or Global); Protection ( 2 bits)

• Offset: 16 bits

– Melalui Descriptor table

• Selector menentukan entry pada table, melihat

protection, dan menguji limit (tabel berisi informasi limit)

• Menghasilkan linear address: Base address segment +

offset

– Logical Linear address: paging (besar page: 4 K), 2 level

(10 bits untuk direktori dan 10 bits untuk page number),

offset: 12 bits.

60

Alamat Translasi Intel 30386

Next…

61

1

Sistem Operasi

Virtual Memory

2

Latar Belakang

• Manajemen memori: – Alokasi “space” memori fisik kepada program yang

diekesekusi (proses).

– Pendekatan: Alokasi space sesuai dengan kebutuhan “logical address” => seluruh program berada di memori fisik.

• Kapasitas memori harus sangat besar untuk mendukung “multiprogramming”.

– Bagaimana jika kapasitas memori terbatas?

– Pendekatan: Teknik Overlay (programming) dapat memanfaatkan kapasitas kecil untuk program yang besar.

• Batasan (tidak transparant, cara khusus): program sangat spesifik untuk OS tertentu.

3

Latar Belakang

(next…) • Q: Apakah sesungguhnya diperlukan seluruh

program harus berada di memori? – Mayoritas kode program untuk menangani “exception”,

kasus khusus dll. (sering tidak dieksekusi).

– Deklarasi data (array, etc) lebih besar dari yang digunakan oleh program.

• IDEA: – Sebagian saja program (kode yang sedang dieksekusi)

berada di memori, tidak harus serentak semua program berada di memori.

– Jika kode program diperlukan maka OS akan mengatur dan mengambil page yang berisi program tersebut dari “secondary storage” ke “main memory”.

4

Latar Belakang

(next…) • Pro’s (jika OS yang melakukan “overlay”)

– Programmer dapat membuat program sesuai dengan

kemampuan “logical address” (virtual address) tanpa

harus menyusun modul mana yang harus ada di memori.

• Fungsi OS sebagai “extended machine”: memberikan ilusi

seolah-olah memori sangat besar, memudahkan

penulisan program dan eksekusi program.

– Proses dapat dieksekusi tanpa memerlukan memori fisik

yang besar => banyak proses.

• Fungsi OS sebagai “resource manager”: menggunakan

utilitas memori yang terbatas untuk dapat menjalankan

banyak proses.

5

Latar Belakang

(next…) • Konsep Virtual Memory:

– Pemisahan antara “user logical memory” (virtual) dengan “physical memory”.

– Logical address space (program) dapat lebih besar dari alokasi memori fisik yang diberikan.

– Hanya sebagian kecil dari program yang harus berada di memori untuk eksekusi.

– Terdapat mekanisme untuk melakukan alokasi dan dealokasi page (swapped out dan in) sesuai dengan kebutuhan (referensi program).

– Terdapat bagian dari disk menyimpan sisa page (program) yang sedang dijalankan di memori.

• Virtual memory dapat diimplementasikan melalui : – Demand paging

– Demand segmentation

6

Virtual Memory Lebih Besar daripada

Memori Fisik

7

Demand Paging

• Umumnya basis VM => paging.

• Demand (sesuai dengan kebutuhan): – Ambil/bawa page ke memory hanya jika diperlukan.

– Umumnya program memerlukan page sedikit (one by one).

– Less I/O & less memory (more users).

– Transfer cepat (faster response).

• Kapan page dibutuhkan? – Saat ekesekusi proses dan terjadi referensi logical address ke

page tersebut. • invalid reference abort

• not-in-memory bring to memory

– Page table menyimpan daftar page frame yang telah dialokasikan untuk proses tersebut.

8

Transfer Page Memory ke

Contiguous Disk Space

9

Valid-Invalid Bit

• Setiap entry pada page table terdapat bit: Valid dan Invalid mengenai keberadaan page di memori fisik (1 in-memory, 0 not-in-memory)

• Saat awal: page belum berada di memori maka bit adalah 0 (not in memory).

• Jika terjadi referensi dan page frame yang akan diakses bit Valid-Invalid 0 => page fault.

10

Page Table Ketika beberapa Page Tidak

Berada di Main Memory

11

Page Fault (OS tasks)

• Saat pertama kali referensi ke page, trap ke OS => page fault.

• OS melakukan evaluasi, apakah alamat logical tersebut “legal”? OK, tapi belum berada di memori.

1. Get empty frame (frame free list).

2. Swap page into frame.

3. Reset tables, validation bit = 1.

4. Restart instruction: yang terakhir eksekusi belum selesai, mis.

• block move

12

Tahap Penanganan Page Fault

13

Tidak ada Frame yang bebas ?

• Jika terdapat banyak proses, maka memori akan

penuh (tidak ada page frame yang free).

• Page replacement (penggantian)

– Mencari kandidat “page” untuk diganti di memori dan

“kemungkinan tidak digunakan” (allocate but not in used).

– Swap page tersebut dengan page yang baru.

– Algoritma: efisien dan mencapai min. jumlah page faults

(karena kemungkinan page yang diganti harus di swap in

lagi).

• Page yang sama akan masuk ke memori pada

waktu mendatang.

14

Memory-Mapped File

• Memory-mapped file I/O membolehkan file I/O diperlakukan sebagai

rutin akses memori yang dipetakan sebagai blok disk ke dalam page

memori

• Suatu file diinisialisasikan menggunakan demand pagin. Suatu

bagian page file dibaca dari file sistem ke page fisik. Subsequent

membaca/menulis ke/dari file yang diperlakukan dalam urutan

memori akses.

• Secara sederhana file akses memperlakukan file I/O melalui memori

melalui read() write() system calls.

• Beberapa proses juga dapat dipetakan pada fiel yang sama pada

memori yang di-share.

15

Memory Mapped Files

16

Page Replacement

• Mencegah alokasi yang berlebihan dari memori dengan memodifikasi layanan rutin page-fault melalui page

• Menggunakan modify bit untuk mengurangi overhead transfer page – hanya modifikasi page yang ditulis di disk.

• Page replacement melengkapi pemisahan antara

memori logik dan memori fisik – virtual memori yang

besar dapat memenuhi kebutuhan memori fisik yang

kecil.

17

Kebutuhan Page Replacement

18

Basic Page Replacement

1. Tentukan lokasi yang diminta page pada disk.

2. Tentuka frame bebas :

Jika tersedia frame bebas, maka dapat digunakan

Jika tidak tersedia frame bebas, gunakan algoritma penggantian

untuk memilih kandidat frame.

3. Baca page yang dituju ke dalam frame bebas (yang baru). Update page dan frame table.

4. Restart process.

19

Page Replacement

20

Algoritma Page Replacement

• Pilih page fault terendah.

• Evaluasi algoritma dengan menjalankan

particular string dari memori acuan

(reference string) dan menghitung jumlah

page fault dari string.

• Contoh, reference string sebagai berikut :

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

21

Graph Page Faults vs. Jumlah Frame

22

FIFO

• FIFO

– Mengganti page yang terlama berada di

memori.

– Data struktur FIFO queue yang menyimpan

kedatangan pages di memori.

– Masalah: menambah page frame => page

fault tidak berkurang.

23

Algoritma FIFO

• Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

• 3 frames (3 page yang dapat berada di memori pada suatu

waktu per proses)

• 4 frames

24

FIFO Page Replacement

25

Ilustrasi Anomali Belady pada FIFO

26

Optimal (Prediction)

• OPT (optimal)

– Mengganti page yang tidak digunakan dalam

waktu dekat (paling lama tidak diakses).

– Menggunakan priority lists page mana yang

tidak akan diakses (“in the near future”).

– Sulit diterapkan (prediksi): terbaik dan

“benchmark” untuk algoritma yang lain.

27

Algoritma Optimal

• Algoritma Optimal

– Mengganti page yang tidak digunakan untuk periode waktu

yang lama.

– Contoh 4 frame

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

28

Optimal Page Replacement

29

Least Recently Used

• LRU (least recently used)

– Mengganti page yang paling lama tidak

digunakan/diakses.

– Asumsi page yang diakses sekarang =>

kemungkinan besar akan diakses lagi

(predict?).

– Masalah: mendeteksi (memelihara) LRU

semua page => bantuan hardware yang

cukup rumit.

30

Algoritma LRU

• Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

31

LRU Page Replacement

32

Algoritma Aproksimasi LRU

• Reference bit – Setiap page berasosiasi dengan satu bit, inisialisasinya =

0

– Ketika page dengan reference bit di set 1

– Ganti satu dengan 0 (jika ada satu)

• Second chance – Membutuhkan reference bit.

– Jika page diganti (pada urutan clock) dengan reference bit = 1, maka

• set reference bit 0.

• Tinggalkan page di memori (berikan kesempatan kedua).

• Ganti next page (dalam urutan clock) , subjek disamakan aturannya.

33

Algoritma Second-Chance (clock)

Page-Replacement Algorithm

34

Alokasi Frame

• Setiap proses membutuhkan minimum sejumlah

pages.

• Contoh : IBM 370 – 6 page untuk menangani

instruksi SS MOVE :

– instruksi 6 bytes, membutuhkan 2 pages.

– 2 pages untuk menangani from.

– 2 untuk menangani to.

• Dua skema besar alokasi :

– fixed allocation

– priority allocation

35

Fixed Allocation

• Equal allocation – contoh jika 100 frame

dan 5 proses, masing-masing 20 page.

• Proportional allocation – mengalokasikan

sesuai ukuran yang cocok dari proses

36

Priority Allocation

• Menggunakan skema alokasi yang

proporsional dengan mengedepankan

menggunakan prioritas dibandingkan

ukuran.

• Jika proses Pi di-generate sebagai page

fault,

– Pilih satu replacement frame

– Pilih replacement frame dari proses dengan

prioritas terendah.

37

Alokasi Global vs. Local

• Global replacement – mengijinkan suatu

proses untuk menyeleksi suatu frame

yang akan fireplace dari sejumlah frame.

• Local replacement –proses hanya

diijinkan menyeleksi frame-frame yang

dialokasikan untuknya.

38

Thrashing

• Jika suatu proses tidak mempunyai page yang cukup, tingkat page fault menjadi tinggi If a process does not have “enough” pages, the page-fault rate is very high. Hal tersebut dapat dilihat dari : – Sistem operasi meningkatkan multiprogramming.

– Utilisasi CPU meningkat sejalan dengan bertambahnya multiprogramming

– Proses lain ditambahkan ke dalam sistem.

• Thrashing suatu proses yang sibuk melakukan swap page in dan out.

39

Thrashing

• Mengapa paging dapat bekerja ?

Model Lokalitas

– Proses pemindahan dari satu lokasi ke lokasi lain.

– Terjadi overlap lokalitas.

• Mengapa thrashing terjadi ?

ukuran lokalitas > total ukuran memory

40

Lokalitas pada Pola

Memory-Reference Pattern

41

Working-Set Model

• jendela working-set fixed number pada page references

Contoh : 10,000 instruksi

• WSSi (working set pada proses Pi) =

jumlah page reference pada saat akhir (beragam waktu)

– jika terlalu kecil akan mencakup seluruh lokalitas

– jika terlalu besar akan mencakup sebagian lokalitas.

– jika = akan mencakup seluruh program

• D = WSSi total permintaan frames

• if D > m Thrashing

• Kebijakan, jika D > m, maka menahan satu proses .

42

Working-set model

43

Pertimbangan Lain

• Prepaging

• Page size selection

– fragmentation

– table size

– I/O overhead

– locality

Next…

44

sistem operasi

Education