Dalam sistem komputer manajemen I/O adalah bagian yang sangat diperlukan karena i/o adalah sarana user untuk bisa berkomunikasi dengan komputer. Seperti keyboard, mouse, monitor, speaker, disk drives, networking ports, dll.

Manajemen I/O harus memiliki subsistem yang dapat bersaing dengan dua kecenderungan. yaitu: gravitasi terhadap antarmuka standar untuk berbagai perangkat, sehingga lebih mudah untuk menambahkan perangkat baru yang dikembangkan untuk sistem yang ada, dan pengembangan jenis perangkat yang baru, dimana interface standar yang ada tidak selalu mudah untuk diterapkan. Device driver adalah modul yang dapat dipasang ke OS untuk menangani perangkat tertentu atau kategori perangkat sejenis.

I/O Hardware

  I/O secara kasar dapat dikategorikan sebagai penyimpanan, komunikasi, user-interface dan device yang lainnya. Device tersebut dikendalikan oleh instruksi I/O. Alamat-alamat yang dimiliki device akan digunakan oleh direct I/O instruction dan memory-mapped I/O. Beberapa konsep yang umum digunakan ialah port, bus , dan controller. Port adalah koneksi yang digunakan oleh device untuk berkomunikasi dengan mesin. Sedangkan Bus adalah koneksi yang menghubungkan beberapa device menggunakan kabel-kabel. Dan Controller adalah alat-alat elektronik yang berfungsi untuk mengoperasikan port, bus, dan device.

Application I/O Interface

Merupakan suatu mekanisme untuk mempermudah pengaksesan, sehingga sistem operasi melakukan standarisasi cara pengaksesan peralatan I/O.

Akses pengguna aplikasi untuk berbagai perangkat yang berbeda dilakukan melalui layering, dan melalui enkapsulasi semua kode perangkat yang spesifik ke driver perangkat, sementara lapisan aplikasi disajikan dengan interface umum untuk semua perangkat .

Beberapa hal yang berhubungan dengan Application I/O Interface:

1. Block and Character Devices

• Perangkat blok mengakses blok pada satu waktu, dan ditandai oleh “b” sebagai karakter pertama dalam long listings pada sistem UNIX. Operasi yang didukung termasuk read (), write (), dan seek ().

• File peta memory  I / O dapat berlapis-lapis di atas driver block-device.

• Perangkat karakter yang diakses satu byte pada suatu waktu, dan ditandai oleh “c” di UNIX long listings. Operasi yang didukung termasuk get () dan put (), dengan fungsi yang lebih canggih seperti membaca seluruh lini yang didukung oleh rutinitas higher-level library.

2. Network Devices

Karena akses jaringan secara inheren berbeda dari akses disk lokal, kebanyakan sistem menyediakan antarmuka terpisah untuk perangkat jaringan. Salah satu yang banyak digunakan pada sistem operasi adalah interface socket. Socket bertindak seperti kabel atau pipa yang menghubungkan dua entitas jaringan. Data dapat dimasukkan ke dalam soket di salah satu ujung, dan dibacakan secara berurutan di ujung lain. Soket biasanya full-duplex, yang memungkinkan untuk transfer data.

3. Clocks and Timers

Clock dan timer pada hardware komputer, memiliki tiga fungsi :

• memberi informasi waktu saat ini

• memberi informasi lamanya waktu sebuah proses

• sebagai trigger untuk suatu operasi pada suatu waktu.

Fungsi ini sering digunakan oleh sistem operasi. Akan tetapi, sayangnya operasi waktu ini tidak di-standarisasi pada semua sistem. Programmable interrupt timer dapat digunakan untuk memicu operasi dan mengukur waktu yang berlalu. Hal ini dapat diatur untuk memicu interupsi pada rentang waktu tertentu di masa mendatang, atau untuk memicu interupsi berkala secara teratur. Sayangnya, ini terbatas dalam resolusi dengan frekuensi interupsi dari PIT, dan dapat dikenakan beberapa penyimpangan dari waktu ke waktu. Pendekatan alternatifnya adalah untuk menyediakan akses langsung ke frekuensi tinggi hardware counter, yang menyediakan resolusi dan akurasi yang lebih tinggi, tetapi yang tidak mendukung interupsi.

4. Blocking and Non-blocking I/O

Dengan blocking I / O, proses akan dipindahkan ke antrian ketika menunggu permintaan I / O dibuat, dan pindah kembali ke antrian ready ketika permintaan selesai, sehingga memperbolehkan proses lain berjalan untuk sementara. Dengan non-blocking I / O, I / O mengirimkan permintaan untuk kembali dengan segera, tidak melihat apakah I / O operasi yang diminta telah berjalan atau tidak. Hal ini memungkinkan proses untuk memeriksa data yang tersedia tanpa mendapatkan gangguan sepenuhnya jika data tidak ada disana.

Kernel I/O subsystems

1. I/O Scheduling

Dengan scheduling, kita dapatmeningkatkan kemampuan sistem secara menyeluruh, kita dapat membagi device dengan rata di antara proses-proses, dan dapat mengurangi waktu tunggu rata-rata untuk menyelesaikan I/O. Prioritas juga dapat berperan dalam  scheduling.

2. Buffering

Buffer merupakan area memori yang menyimpan data ketika mereka sedang dipindahkan antara dua device atau antara device dan aplikasi. Buffering dilakukan untuk tiga buah alasan. Pertama adalah perbedaan kecepatan antara dua perangkat. Yang kedua adalah perbedaan ukuran transfer data. Dan yang terakhir untuk mendukung copy semantik.

3. Caching

Caching melputi penjagaan salinan data di lokasi lebih cepat daripada akses dimana data tersebut biasanya disimpan. Buffering dan caching sangat mirip, kecuali buffer dapat memegang satu-satunya salinan item data yang diberikan, sedangkan cache hanya salinan duplikat beberapa data yang disimpan di tempat lain. Buffering dan caching berjalan hand-in-hand, dan seringkali ruang penyimpanan yang sama dapat digunakan untuk kedua tujuan.

4. Spooling dan Device  Reservation

Spool adalah sebuah buffer yang menyimpan output untuk sebuah device, seperti printer, yang tidak dapat menerima interleaved data streams. Jika beberapa proses ingin mencetak pada saat yang sama, mereka masing-masing mengirimkan data cetak mereka ke file yang tersimpan di direktori spool. Ketika setiap file ditutup, maka aplikasi dapat melihat bahwa pekerjaan cetak sudah lengkap, dan scheduler cetak mengirimkan setiap file ke printer yang sesuai satu per satu. Dukungan diberikan untuk melihat antrian spool, menghapus pekerjaan dari antrian, bergerak dari satu pekerjaan antrian ke antrian yang lain, dan dalam beberapa kasus mengubah prioritas pekerjaan di antrian. Antrian Spool dapat bersifat umum atau khusus. OS juga dapat memberikan dukungan untuk proses untuk meminta / mendapatkan akses eksklusif untuk perangkat tertentu, dan / atau menunggu sampai perangkat menjadi tersedia.

5. Error Handling

Permintaan I / O bisa gagal karena berbagai alasan, baik sementara karena buffer overflow atau permanen dikarenakan disk yang crash. Permintaan I / O biasanya mengembalikan kesalahan bit (atau lebih) yang menunjukkan masalah. Sistem UNIX juga mengatur variabel global errno untuk salah satu dari seratus atau lebih nilai yang didefinisikan dengan baik untuk menunjukkan kesalahan tertentu yang telah terjadi. Beberapa perangkat, seperti perangkat SCSI, mampu memberikan banyak informasi lebih rinci tentang kesalahan, dan bahkan menjaga error log on-board yang dapat diminta oleh host.

6. I/O Protection

I / O sistem harus melindungi baik disengaja ataupun tidak disengaja. Aplikasi pengguna tidak diizinkan untuk menjalankan I / O dalam mode user. Semua I / O permintaan yang ditangani melalui panggilan sistem yang harus dilakukan dalam mode kernel. Daerah memori dipetakan dan I / O port harus dilindungi oleh sistem manajemen memori, tetapi untuk akses ke daerah-daerah tidak dapat sepenuhnya ditolak untuk program user. Sebaliknya sistem perlindungan memori membatasi akses sehingga hanya satu proses pada suatu waktu dapat mengakses bagian-bagian tertentu dari memori, seperti bagian dari  layar memori sesuai dengan jendela tertentu.

7. Kernel Data Structure

Kernel mempertahankan sejumlah struktur data penting yang berkaitan dengan sistem I / O, seperti  open file table. Struktur ini adalah object-oriented, dan fleksibel untuk memungkinkan akses ke berbagai perangkat I / O melalui interface umum. Windows NT membawa objek-orientasi satu langkah lebih jauh, melaksanakan I / O sebagai pesan melalui sistem dari sumber melalui berbagai perantara ke perangkat.

I/O Requests to Hardware Operations

Pengguna meminta data menggunakan nama file, yang akhirnya harus dipetakan ke blok data tertentu dari perangkat tertentu yang dikelola oleh driver perangkat tertentu. DOS menggunakan pemisah khusus untuk menentukan perangkat tertentu. UNIX menggunakan mount table untuk memetakan prefiks nama file untuk dipasangkan ke perangkat yang lebih spesifik. Dimana beberapa entri dalam mount table sesuai prefiks yang berbeda dari nama file dipilih salah satu yang cocok dengan awalan terpanjang. UNIX menggunakan file perangkat khusus, biasanya terletak di /dev, untuk mewakili dan mengakses perangkat fisik secara langsung. Serangkaian tabel lookup dan maping membuat akses perangkat yang berbeda menjadi fleksibel, dan agak transparan kepada pengguna.

Manajemen I/O Pada Windows

Dalam windows sistem i/o menyediakan model driver berlapis yang dinamakan stack. Biasanya IRP akan berpindah dari satu driver ke driver lain dalam satu stack yang sama ke fasilitas komunikasi. Misalkan mouse ketika digunakan harus berkomunikasi dengan USB hub, kemudian USB hub harus berkomunikasi dengan USB Host Controller, selanjutnya USB Host Controller harus berkomunikasi melalui PCI bus ke seluruh hardware computer. Maka stack akan berisi mouse driver, USB hub, USB Host Controller, dan PCI bus. Pada windows semua kelas perangkat berbagi driver umum yang disebut “port driver”. Port driver mengimplementasikan operasi standard untuk suatu kelas dan “calls device-spesific routine” yang kemudian mengimplementasikan fungsi “device-spesific”.

i/o manager pada windows mempunyai 2 sub component yaitu: Plug and Play manager and power manager. PnP manager adalah teknologi PnP milik Microsoft yang berfungsi untuk mengenali dan mengadaptasi perubahan pada konfigurasi hardware. Agar Pnp bekerja maka perangkat dan drivernya harus memenuhi standar PnP. Pnp manager secara otomatis mengenali perangkat yang dipasang dan mendeteksi perubahan pada perangkat seiring sistem beroperasi. Pnp manager pun tetap mengawasi sumber daya yang digunakan oleh perangkat, dan juga potensi jika sumber daya tersebut digunakan serta menangani “loading” driver tersebut. Dilain sisi, power manager ikut berperan dalam mengurangi komsumsi tenaga pada perangkat. Sehingga suatu perangkat dapat diset dalam mode “low-power”(sleep mode) ketika tidak digunakan, dan dapat langsung dipakai ketika diperlukan.

Manajemen I/O Pada Linux

Dalam Linux system i/o kurang lebih mirip dengan yang terdapat pada Unix. User dapat membuka saluran akses ke perangkat sama seperti membuka file-perangkat lain yang tampak sebagai objek dalam file sistem. Linux membagi semua perangkat i/o menjadi 3 kelas: “block devices”, “character devices”, dan “network devices”.

“Block devices” yaitu menyimpan, menerima, dan mengirim informasi sebagai blok-blok berukuran tetap yang berukuran 128 sampai 1024 byte dan memiliki alamat tersendiri, sehingga memungkinkan membaca atau menulis blok-blok secara independen, yaitu dapat membaca atau menulis sembarang blok tanpa harus melewati blok-blok lain. Contoh : disk, tape, CD ROM, optical disk. Fungsi “block devices” sendiri didukung oleh 2 sistem component, block buffer cache dan request manager. Block buffer cache bertugas sebagai pool dari buffer i/o aktif dan cache dari “completed i/o”. “Request manager” adalah lapisan software yang mengelola konten read dan write buffer dari dan menuju block-device driver.

“Character devices” yaitu perangkat yang menerima, dan mengirimkan aliran karakter tanpa membentuk suatu struktur blok. Contoh : terminal, line printer, pita kertas, kartu-kartu berlubang, mouse. Perangkat ini tidak memerlukan random access untuk sebuah block data. Akan tetapi, tiap perangkat telah memiliki berbagai fungsi yang telah terdaftar pada kernel yang diimplementasikan pada file operasi i/o.

Sedangkan “network devices” berbeda dengan block atau character devices, user harus berkomunikasi secara tidak langsung dengan cara harus membuka sambungan dengan subsistem jaringan kernel.

References:

1. Abraham Silberschatz, Greg Gagne, and Peter Baer Galvin, “Operating System Concepts, Eighth Edition “, Chapter 13

2. http://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/13_IOSystems.html

1. Fetch Policy

adalah yang menentukan apakah suatu page akan diambil kedalam main memory atau tidak. alternatif yang terkait dengan fetch policy yaitu demand paging dan prepaging.

1. Demand Paging

Dengan demand paging, page akan diambil kedalam main memory ketika ada referensi yang dibuat pada suatu lokasi untuk page tersebut. jika disetujui oleh memory management policy yang lain, maka demand paging akan dilaksanakan.

2. Prepaging

Dengan prepaging, page selain yang digunakan pada demand paging akan diambil kedalam main memory. Prepaging menggunakan karakteristik dari kebanyakan secondary memory device, seperti disk yang memiliki seek time dan rotational latency. Policy ini tidak efektif jika kebanyakan dari extra page page yang diambil tidak memiliki referensi apapun.

2. Placement Policy

Adalah yang menentukan dimana bagian proses akan tersimpan pada memori asli. Pada sistem dengan segmentasi, placement policy menjadi pilihan yang terbaik. Sedangkan dalam sistem paging atau sistem segmentasi yang digabung paging, placement policy menjadi kurang baik karena perangkat keras address translasi dan perangkat keras pengaksesan main memori dapat berfungsi dengan efisiensi yang sama.

3. Replacement Policy

Berdasarkan implementasi memori virtual yaitu konsep demand paging. Ini berarti sistem operasi, dan bukan programmer, mengontrol swapping halaman dalam dan luar dari memori utama karena mereka diwajibkan oleh proses yang aktif. Ketika halaman non-residen yang dibutuhkan oleh proses, sistem operasi harus memutuskan mana halaman yang akan diganti dengan halaman yang diminta. Bagian dari memori virtual yang membuat keputusan ini disebut Replacement Policy.

• Optimal
  Halaman yang diganti adalah salah satu yang tidak akan digunakan untuk periode waktu yang lama. Algoritma ini membutuhkan pengetahuan masa depan tentang string yang tidak selalu tersedia. Dengan demikian, kebijakan ini digunakan untuk studi perbandingan.

• Least Recently Used (LRU)
  Halaman yang diganti adalah salah satu yang belum dirujuk karena yang lainnya telah direferensikan.

• First in first-out (FIFO)
  Halaman yang diganti adalah halaman “tertua” di memori, satu halaman yang dimuat sebelum yang lainnya dimuat.

• Clock
  Dalam algoritma ini, Anda harus mempertahankan daftar link yang melingkar, dengan kepala pointer menunjuk ke halaman kandidat potensial berikutnya untuk penggusuran. Sebagai bagian dari algoritma ini, Anda juga jharus mempertahankan ‘Referensi Bit’ dengan setiap halaman virtual.

4. Resident Set Management

• Biasanya kebijakan alokasi memberikan sejumlah proses halaman pada memori utama untuk dieksekusi.

• Jumlah halaman yang dialokasikan juga dikenal sebagai set penduduk (halaman).

• Dua kebijakan untuk alokasi set penduduk: tetap dan variabel.

• Ketika proses baru dimuat ke memori, mengalokasikan sejumlah page frame berdasarkan jenis aplikasi, atau kriteria lainnya. Prepaging atau permintaan paging digunakan untuk mengisi halaman.

• Ketika kesalahan halaman terjadi, pilih halaman untuk menggantikannya.

5. Cleaning Policy

Berkaitan dengan penentuan waktu saat page yang telah dimodifikasi harus ditulis ke memori sekunder. Alternatif dalam penerapannya meliputi Demand cleaning (page akan ditulis ke memori sekunder ketika page telah terpilih untuk digantikan) dan Precleaning (page ditulis dalam batches).

Sebuah cleaning policy adalah kebalikan dari fetch policy; itu berkaitan dengan penentuan bila halaman dimodifikasi harus ditulis ke memori sekunder. dua alternatif umum adalah membersihkan permintaan dan precleaning. With demand cleaning, sebuah halaman ditulis ke memori sekunder hanya ketika telah dipilih untuk penggantian. Sebuah precleaning policy menulis halaman modifikasi sebelum frame halaman mereka dibutuhkan sehingga bahwa halaman dapat ditulis dalam batch.

Ada bahaya dalam mengikuti kebijakan tersebut secara penuh. Dengan precleaning, sebuah halaman ini ditulis tetapi tetap dalam memori utama sampai algoritma penggantian menyatakan bahwa itu dihapus. Precleaning memungkinkan penulisan halaman dalam batch, tapi masuk akal untuk menulis ratusan atau ribuan halaman hanya untuk menemukan bahwa sebagian dari mereka telah dimodifikasi lagi sebelum mereka diganti. Kapasitas transfer memori sekunder terbatas dan tidak boleh disia-siakan dengan operasi pembersihan yang tidak perlu.

Di sisi lain, dengan membersihkan permintaan, penulisan halaman kotor digabungkan untuk, dan mendahului, membaca di sebuah halaman baru. Teknik ini dapat meminimalkan halaman menulis, tetapi itu berarti bahwa proses yang terdapat kesalahan halaman mungkin harus menunggu selama dua transfer halaman sebelum dapat diblokir. Hal ini dapat menurunkan penggunaan prosesor.

Pendekatan yang lebih baik menggabungkan halaman buffering. Hal ini memungkinkan dengan mengadopsi kebijakan berikut: Bersihkan hanya halaman yang diganti, tapi yang memisahkan operasi pembersihan dan penggantian. Dengan halaman buffering, halaman diganti dapat ditempatkan pada dua daftar: dimodifikasi dan dimodifikasi. Halaman-halaman pada daftar dimodifikasi bisa berkala ditulis dalam batch dan dipindah ke daftar modifikasi.

6. Load Control

Load control berkaitan dengan penentuan jumlah proses yang akan menetap di memori utama, yang telah disebut sebagai tingkat multiprogramming. itu kebijakan pengendalian beban sangat penting dalam manajemen memori yang efektif. Jika terlalu sedikit proses yang resident pada satu waktu, maka akan ada banyak kesempatan ketika semua proses diblokir, dan banyak waktu yang akan dihabiskan dalam swapping. Di sisi lain, jika terlalu banyak proses yang resident, maka, rata-rata, ukuran resident set masing-masing proses akan memadai dan akan sering terjadi patahan. Hasilnya adalah akan buruk.

referensi :

http://cs.gmu.edu/cne/modules/vm/yellow/repol.html

http://www.cse.psu.edu/~anand/473/p3/

http://www.cse.buffalo.edu/~bina/cse421/spring00/LEC78MemMgt/tsld027.htm

Operating System 7th Edition William Stalling

1. Konsep Penjadwalan Proses

Permasalahan  yang  menyebabkan  dibutuhkannya  penjadwalan  adalah  bila terdapat berbagai macam tugas (job) atau proses yang harus dilakukan, sedangkan sumber  daya  (waktu,  bahan  baku,  tenaga  kerja,  mesin,  modal,  dan  sebagainya) yang  dibutuhkan  untuk  menyelesaikan  tugas-tugas  atau  proses  tersebut  terbatas sehingga  diperlukan  suatu  pengaturan  atas  pelaksanaan  tugas-tugas  atau  prosesproses  tersebut.  Conway (1967)   mendefinisikan  penjadwalan  sebagai  berikut:

”Scheduling is the task of assigning each operation  to a specific position or the time  scale  of  the  specific  machine”.  Sedangkan  Fogarty (1991)  mengatakan bahwa  penjadwalan  mencakup  dua hal,  yaitu  scheduling dan  sequencing yang masing-masing didefinisisikan sebagai berikut:

”Scheduling  is  the  assigning  of  starting  and  completion  times  orders  (job)  and frequently  includes  the  times  when  orders  are  to  arrive  and  leave  each department”.

Scheduling (penjadwalan)  merupakan  proses  penugasan  kapan  pekerjaan  harus dimulai dan diselesaikan, sedangkan  sequencing  (pengurutan) merupakan proses pengaturan  urutan  atas  pekerjaan-pekerjaan  yang  harus  diselesaikan  tersebut. Karena  eratnya  hubungan  diantara  kedua  istilah  ini, maka  biasanya  dalam penggunaan kata scheduling (penjadwalan), pengertian sequencingsudah tercakup didalamnya.

Pada sistem komputer terdapat beberapa bentuk dari penjadwalan, admission (pintu masuk ke system), memory, dan CPU scheduler coba lihat gambar scheduler dari batch system berikut:

Pada sistem multiprogramming, selalu akan terjadi beberapa proses berjalan dalam suatu waktu. Sedangkan pada uniprogramming hal ini tidak akan terjadi, karena hanya ada satu proses yang berjalan pada saat tertentu. Sistem multiprogramming diperlukan untuk memaksimalkan utilitas CPU. Pada saat proses dijalankan terjadi siklus eksekusi CPU dan menunggu I/O yang disebut dengan siklus CPU-I/O burst. Eksekusi proses dimulai dengan CPU burst dan dilanjutkan dengan I/O burst, diikuti CPU burst lain, kemudian I/O burst lain dan seterusnya seperti pada gambar berikut:

Pada saat suatu proses dieksekusi, terdapat banyak CPU burst yang pendek dan terdapat sedikit CPU burst yang panjang. Program yang I/O bound biasanya sangat pendek CPU burst nya, sedangkan program yang CPU bound kemungkinan CPU burst nya sangan lama. Hal ini dapat digambarkan dengan grafik yang eksponensial atau hiper eksponensial seperti pada gambar. Oleh karena itu sangat penting pemilihan algoritma penjadwalan CPU.

CPU Scheduler

Pada saat CPU menganggur, maka sistem operasiharus menyeleksi proses-proses yang ada di memori utama (ready queue) untuk dieksekusi dan mengalokasikan CPU untuk salah satu dari proses tersebut. Seleksi semacam ini disebut dengan shortterm scheduler (CPU scheduler).

Keputusan untuk menjadwalkan CPU mengikuti empat keadaan di bawah ini :

1)  Apabila proses berpindah dari keadaan running ke waiting;

2)  Apabila proses berpindah darikeadaan running ke ready;

3)  Apabila proses berpindah dari keadaan waiting ke ready;

4)  Apabila proses berhenti.

Apabila model penjadwalan yang dipilih menggunakan keadaan 1 dan 4, maka penjadwakan semacam ini disebut non-peemptive. Sebaliknya, apabila yang digunakan adalah keadaan 2 dan 3, maka disebut dengan preemptive. Pada non-preemptive, jika suatu proses sedang menggunakan CPU, maka proses tersebut akan tetap membawa CPU sampai proses tersebut melepaskannya (berhenti atau dalam keadaan waiting). Preemptive scheduling memiliki kelemahan, yaitu biaya yang dibutuhkan sangat tinggi. Antara lain, harus selalu dilakukan perbaikan data. Hal ini terjadi jika suatu proses ditinggalkan dan akan segera dikerjakan proses yang lain.

Dispatcher

Dispatcher adalah suatu modul yang akan memberikan kontrol pada CPU terhadap penyeleksian proses yang dilakukan selama short-term scheduling. Fungsi-fungsi yang terkandung di dalamnya meliputi:

1.  Switching context;

2.  Switching ke user-mode;

3.  Melompat ke lokasi tertentu pada user program untuk memulai program. Waktu yang

diperlukan oleh dispatcher untuk menghentikan suatu proses dan  memulai untuk

menjalankan proses yang lainnya disebut dispatch latency.

2. Perbedaan Penjadwalan Long Term, Medium Term, dan Short Term.

Short term scheduler : Mempunyai tugas untuk menjadwalkan alokasi pemroses di antara proses ready di memori utama. Penjadwalan dijalankan setiap terjadi di pengalihan proses untuk memilih proses berikut yang harus dijalankan.

– Di dalam short term ini digunakan untuk memilih diantara proses – proses yang siap dieksekusi & satu diantaranya dialokasikan ke CPU.

– Penjadwalan short term biasa digunakan untuk CPU, proses dieksekusi dan hanya beberapa milidetik saja sebelum menunggu I/O.

Medium term scheduler: Aktivitas pemindahan proses yang tertunda dari memori utama ke memori sekunder yang disebut swapping. Proses ini mempunyai kepentingan kecil saat itu sebagai proses yang tertunda. Tetapi, begitu kondisi yang membuatnya tertunda hilang dan proses dimasukkan kembali ke memori utama dan ready.

– Dalam penjadwalan medium term ini, beberapa OS seperti contoh time-sharing harus membutuhkan penjadwalan dengan level tambahan.

Long term scheduler: Penjadwalan ini bekerja terhadap antrian batch dan memilih batch berikutnya yang harus dieksekusi. Batch biasanya adalah proses-proses dengan penggunaan sumber daya yang intensif, program ini berprioritas rendah, digunakan sebagai pengisi selama periode aktivitas job-job interaktif rendah.

– Jika pada long term ini tiding sering mengeksekusi, dan digunakan jika proses meninggalkan suatu sistem.

– Digunakan untuk memilih suatu proses dari pool & menyimpan pada memori.

3. Parameter Dalam Penjadwalan Proses

Algoritma penjadwalan CPU yang berbeda akan memiliki perbedaan properti. Sehingga untuk memilih algoritma ini harus dipertimbangkan dulu properti-properti algoritma tersebut. Ada beberapa parameter yang digunakan untuk melakukan pembandingan algoritma penjadwalan CPU, antara lain:

1. CPU utilization: Diharapkan agar CPU selalu dalam keadaan sibuk. Utilitas CPU dinyatakan dalam bentuk prosen yaitu 0-100%. Namun dalam kenyataannya hanya berkisar antara 40-90%.

2. Throughput: throughput Adalah banyaknya proses yang selesai dikerjakan dalam satu satuan waktu. Cara untuk mengekspresikan throughput adalah dengan jumlah proses user yang dapat dieksekusi dalam interval waktu tertentu. Sasaran penjadwalan adalah memaksimalkan jumlah proses yang dilayani per satu interval waktu. Lebih tinggi waktu throughput maka lebih banyak kerja yang dilakukan sistem. Kriteria-kriteria tersebut saling tergantung dan dapat saling bertentangan sehingga tidak dimungkinkan optimasi semua criteria secara simultan Contoh:

Untuk memberikan waktu tanggap kecil umumnya memerlukan penjadwalan yang sering beralih-alih di antara proses-proses yang ada. Cara ini meningkatkan overhead sistem sehingga menurunkan efisiensi. Kebijaksanaan perancangan penjadwalan melibatkan kompromi di antara kebutuhan-kebutuhan yang saling bertentangan. Kompromi ini tergantung sifat dan penggunaan sistem komputer.

3. Turnaround time: Banyaknya waktu yang diperlukan untuk mengeksekusi proses, dari mulai menunggu untuk meminta tempat di memori utama, menunggu di ready queue, eksekusi oleh CPU, dan mengerjakan I/O  sampai semua proses-proses tersebut diselesaikan. Waktu yang dimaksud adalah waktu yang dihabiskan proses berada di sistem, atau juga bisa diekspresikan sebagai penjumlahan waktu eksekusi (waktu pelayanan proses) dan waktu menunggu dari porses tersebutatau bisa dirumuskan seperti:

Turn arround time = waktu eksekusi + waktu tunggu. Sasaran dari penjadwalan adalah meminimalkan turn arround time.

4. Waiting time: Waktu yang diperlukan oleh suatu proses untuk menunggu di ready queue. Waiting time ini tidak mempengaruhi eksekusi proses dan penggunaan I/O.

5. Response time: Waktu yang dibutuhkan oleh suatu proses dari minta dilayani hingga ada respon pertama yang menanggapi permintaan tersebut. Respon time berbeda untuk sistem interaktif dan sistem waktu nyata.

• Respon time sistem interaktif: respon time dalam sistem interkatif didefinisikan sebagai waktu yang dihabiskan dari saat karakter terakhir dari perintah dimasukan oleh program atau transaksi sampai hasil pertama muncul di perangkat output seperti layar (terminal)

• Respon time sistem waktu nyata: pada sistem waktu nyata (real time), respon didefinisikan sebagai waktu dari saat kemunculan suatu kejadian (internal atau eksternal) sampai instruksi pertama rutin layanan terhadap kejadian dieksekusi.

6. Fairness: adil adalah menyakinkan proses-proses diperlakukan sama yaitu mendapat jatah waktu layanan CPU yang sama dan tidakada proses yang tidak kebagian layanan CPU sehingga mengalai starvation. Starvation merupakan suatu kondisi bahwa proses tidak pernah berjalan tidak dijadwalkan untuk berjalan.

4. Konsep Penjadwalan Berdasarkan Prioritas

Penjadwalan prioritas adalah tiap proses diberi prioritas dan proses yang berprioritas tertinggi mendapat jatah waktu lebih dulu (running). Berasumsi bahwa masing-masing proses memiliki prioritas tertentu, sehingga akan dilaksanakan berdasar prioritas yang dimilikinya. Ilustrasi yang dapat memperjelas prioritas tersebut adalah dalam komputer militer, dimana proses dari jendral berprioritas 100, proses dari kolonel 90, mayor berprioritas 80, kapten berprioritas 70, letnan berprioritas 60 dan seterusnya. Prioritas suatu proses dapat ditentukan melalui beberapa karakteristik antara lain:

a. Batas waktu

b. Kebutuhan Memori

c. Akses file

d. Perbandingan antara I/O Burst dengan CPU Burst

e. Tingkat kepentingan proses

Proses-proses yang sangat banyak operasi masukan/keluaran menghabiskan kebanyakan waktu menunggu selesainya operasinya masukan/keluaran. Proses-proses ini diberi prioritas sangat tinggi sehingga begitu proses Memerlukan pemroses segera diberikan, proses akan segera memulai permintaan masukan/keluaran berikutnya sehingga menyebabkan proses blocked menunggu selesainya operasi masukan/keluaran. Dengan demikian pemroses dapat dipergunakan proses-proses lain. Proses-proses I/O berjalan paralel bersama proses-proses lain yang benar-benar memerlukan pemroses, sementara proses-proses I/O itu menunggu selesainya operasi DMA. Proses-proses yang sangat banyak operasi I/O-nya, kalau harus menunggu lama untuk memakai pemroses (karena prioritas rendah) hanya akan membebani memori, karena harus disimpan tanpa perlu proses-proses itu dimemori karena tidak selesai-selesai menunggu operasi masukan dan menunggu jatah pemroses.

Penjadwalan  dengan  pendekatan  heuristic menggunakan  aturan  pengurutan  atau priority  dispatching,  pada  priority  dispatching ditentukan  aturan  prioritasnya untuk memilih suatu operasi diantara operasi-operasi yang mengalami gangguan. Penentuan prioritas bergantung pada tujuan  yang ingin dicapai. Beberapa aturan prioritas menutur Fogarty(1991), adalah:

1.  Random (R)

Pemilihan  operasi  secara  random  artinya  setiap  pekerjaan  yang  akan dikerjakan  diurutkan  secara  random (tiap  job mempunyai  kemungkinan yang sama untuk dipilih)

2.  Most Working Remaining (MWR)

Prioritas tertinggi diberikan pada operasi dengan sisa waktu proses terlama.

Aturan  prioritas  ini  cocok  digunakan  untuk  menghasilkan  jadwal  dengan

makespan terpendek.

3.  Least Working Remaining (LWR)

Prioritas  tertinggi  diberikan  pada  operasi  dengan  sisa  waktu  proses terpendek. Aturan ini biasanya meminimasi flow timerata-rata.

4.  Most Operation Remaining (MOR)

Prioritas tertinggi diberikan pada operasi dengan successor terbanyak.

5.  Fewest Operation (FO)

Prioritas tertinggi diberikan pada produk dengan sisa operasi paling sedikit. Aturan ini biasanya mengurangi WIP, waktu penyelesaian produk, dan rata-rata waktu keterlambatan.

6.  Shortest Processing Time (SPT)

Prioritas  tertinggi  diberikan  pada  operasi  dengan  waktu  proses  terpendek, aturan  ini  biasanya  meminimasi  WIP,  rata-rata  keterlambatan  (mean latenes) dan waktu penyelesaian rata-rata (mean flow time) produk.

7.  First Come First Serve (FCFS)

Prioritas tertinggi diberikan pada operasi yang masuk St (stasiun ke-t) lebih dahulu. Aturan  ini  cocok  untuk  tipe  organisasi  dimana  konsumen mementingkan waktu pelayanan.

8.  Earliest Due Date (EDD)

Prioritas  tertinggi  diberikan  pada  produk  dengan  due  date (batas  waktu penyelesaian) terpendek. Aturan ini berjalan dengan baik bila waktu proses job-job relatif sama.

9.  Critical Ratio (CR)

Urutkan job berdasarkan CR terkecil (mengurangi lateness)

10.  Slack Time (ST)

       Merupakan variasi dari EDD.

11.  Slack Per Remaining Operation (S/OPN)

   Merupakan variasi dari ST, urutkan job berdasarkan S/OPN terkecil (aturan ini mengurangi lateness).

12.  Least Setup (LSU)

Urutkan  job berdasarkan  waktu  setup  terkecil  (aturan  ini  mengurangi makespan).

Referensi

• http://journal.amikom.ac.id/index.php/KIDA/article/view/3308

• http://andrigumilar.ilearning.me/2013/04/30/soal-sistem-operasi/

• http://elib.unikom.ac.id/download.php?id=18579

Anggota yang berkontribusi:

1. Rhesa Fauzan H (1103120102)

2. M. Taufik Wahdiat (1103120104)

3. Rakhmad Indra Permadi (1103121281)

DEFINITION

A thread of execution is the smallest sequence of programmed instructions that can be managed independently by a scheduler (typically as part of an operating system). The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is a component of a process. Multiple threads can exist within the same process and share resources such as memory, while different processes do not share these resources. In particular, the threads of a process share the latter’s instructions (its code) and its context (the values that its variables reference at any given moment).

On a single processor, multithreading is generally implemented by time-division multiplexing (as in multitasking): the processor (CPU) switches between different hardware threads. This context switching generally happens frequently enough that the user perceives the threads or tasks as running at the same time. On a multiprocessor or multi-core system, threads can be truly concurrent, with every processor or core executing a separate thread simultaneously. The operating system uses hardware threads to implement multi processing. Hardware threads are different from the software threads mentioned earlier. Software threads are a pure software construct. The CPU has no notion of software threads, and is unaware of their existence.

Many modern operating systems directly support both time-sliced and multiprocessor threading with a process scheduler. The kernel of an operating system allows programmers to manipulate threads via the system call interface. Some implementations are called a kernel thread, whereas a lightweight process (LWP) is a specific type of kernel thread that shares the same state and information.

Programs can have user-space threads when threading with timers, signals, or other methods to interrupt their own execution, performing a sort of ad hoc time-slicing.

DIFFERENCES BETWEEN THREAD AND PROCESS

Threads differ from traditional multitasking operating system processes in that:

• processes are typically independent, while threads exist as subsets of a process

• processes carry considerably more state information than threads, whereas multiple threads within a process share process state as well as memory and other resources

• processes have separate address spaces, whereas threads share their address space

• processes interact only through system-provided inter-process communication mechanisms

• context switching between threads in the same process is typically faster than context switching between processes.

Systems such as Windows NT and OS/2 are said to have “cheap” threads and “expensive” processes; in other operating systems there is not so great a difference except the cost of address space switch which implies a TLB flush.

MULTITHREADING

Multithreading is mainly found in multitasking operating systems. Multithreading is a widespread programming and execution model that allows multiple threads to exist within the context of a single process. These threads share the process’s resources, but are able to execute independently. The threaded programming model provides developers with a useful abstraction of concurrent execution. Multithreading can also be applied to a single process to enable parallel execution on a multiprocessing system.

Multi-threaded applications have the following advantages:

• Responsiveness: Multi-threading has the ability for an application to remain responsive to input. In a single-threaded program, if the main execution thread blocks on a long-running task, the entire application can appear to freeze. By moving such long-running tasks to a worker thread that runs concurrently with the main execution thread, it is possible for the application to remain responsive to user input while executing tasks in the background. On the other hand, in most cases multithreading is not the only way to keep a program responsive, with non-blocking I/O and/or Unix signals being available for gaining similar results.

• Faster Execution: This advantage of a multithreaded program allows it to operate faster on computer systems that have multiple or multi-core CPUs, or across a cluster of machines, because the threads of the program naturally lend themselves to truly concurrent execution.

• Less Resource Intensive: Using threads, an application can serve multiple clients concurrently using less resource than it would need when using multiple process copies of itself. For example, the Apache HTTP server, which uses a pool of listener and server threads for listening to incoming requests and processing these requests.

• Better System Utilization: Multi-threaded applications can also utilize the system better. For example, a file-system using multiple threads can achieve higher throughput and lower latency since data in faster mediums like the cache can be delivered earlier while waiting for a slower medium to retrieve the data.

• Simplified Sharing and Communication: Unlike processes, which require message passing or shared memory to perform inter-process communication, communication between threads is very simple. Threads automatically share the data, code and files and so, communication is vastly simplified.

• Parallelization: Applications looking to utilize multi-core and multi-CPU systems can use multi-threading to split data and tasks into parallel sub-tasks and let the underlying architecture manage how the threads run, either concurrently on a single core or in parallel on multiple cores. GPU computing environments like CUDA and OpenCL use the multi-threading model where dozens to hundreds of threads run in parallel on a large number of cores.

Multi-threading has the following drawbacks:

• Synchronization: Since threads share the same address space, the programmer must be careful to avoid race conditions and other non-intuitive behaviors. In order for data to be correctly manipulated, threads will often need to rendezvous in time in order to process the data in the correct order. Threads may also require mutually exclusive operations (often implemented using semaphores) in order to prevent common data from being simultaneously modified or read while in the process of being modified. Careless use of such primitives can lead to deadlocks.

• Thread crashes Process: An illegal operation performed by a thread crashes the entire process and so, one misbehaving thread can disrupt the processing of all the other threads in the application.

Issues with multithreading

There are few known issues with multithreading

1. when a thread execute a fork system call to create a new proccess, does the child process duplicate all thread from the parent or just the thread ?

2. how does a multithread process handle its signal ? is a signal delivered to a process receive by any thread, a few particular thread or all of thr thread ?

3. how thread are scheduled ? at what level they scheduled, the user level or the kernel level ?

Operating systems schedule threads in one of two ways:

1. Preemptive multitasking is generally considered the superior approach, as it allows the operating system to determine when a context switch should occur. The disadvantage of preemptive multithreading is that the system may make a context switch at an inappropriate time, causing lock convoy, priority inversion or other negative effects, which may be avoided by cooperative multithreading.

2. Cooperative multithreading, on the other hand, relies on the threads themselves to relinquish control once they are at a stopping point. This can create problems if a thread is waiting for a resource to become available.

Threads, called tasks, made an early appearance in OS/360 Multiprogramming with a Variable Number of Tasks (MVT) in 1967.

Until the late 1990s, CPUs in desktop computers did not have much support for multithreading, although threads were still used on such computers because switching between threads was generally still quicker than full-process context switches. Processors in embedded systems, which have higher requirements for real-time behaviors, might support multithreading by decreasing the thread-switch time, perhaps by allocating a dedicated register file for each thread instead of saving/restoring a common register file. In the late 1990s, the idea of executing instructions from multiple threads simultaneously, known as simultaneous multithreading, had reached desktops with Intel’s Pentium 4 processor, under the name hyper-threading. It has been dropped from Intel Core and Core 2 architectures, but later was re-instated in the Core i7 architectures and some Core i3 and Core i5 CPUs.

THREAD MODELS

1:1 (Kernel-level threading)

Threads created by the user are in 1-1 correspondence with schedulable entities in the kernel. This is the simplest possible threading implementation. Win32 used this approach from the start. On Linux, the usual C library implements this approach (via the NPTL or older LinuxThreads). The same approach is used by Solaris, NetBSD and FreeBSD.

N:1 (User-level threading)

An N:1 model implies that all application-level threads map to a single kernel-level scheduled entity; the kernel has no knowledge of the application threads. With this approach, context switching can be done very quickly and, in addition, it can be implemented even on simple kernels which do not support threading. One of the major drawbacks however is that it cannot benefit from the hardware acceleration on multi-threaded processors or multi-processor computers: there is never more than one thread being scheduled at the same time. For example: If one of the threads needs to execute an I/O request, the whole process is blocked and the threading advantage cannot be utilized. The GNU Portable Threads uses User-level threading, as does State Threads.

M:N (Hybrid threading)

M:N maps some M number of application threads onto some N number of kernel entities, or “virtual processors.” This is a compromise between kernel-level (“1:1”) and user-level (“N:1”) threading. In general, “M:N” threading systems are more complex to implement than either kernel or user threads, because changes to both kernel and user-space code are required. In the M:N implementation, the threading library is responsible for scheduling user threads on the available schedulable entities; this makes context switching of threads very fast, as it avoids system calls. However, this increases complexity and the likelihood of priority inversion, as well as suboptimal scheduling without extensive (and expensive) coordination between the userland scheduler and the kernel scheduler.

Hybrid implementation examples

• Scheduler activations used by the NetBSD native POSIX threads library implementation (an M:N model as opposed to a 1:1 kernel or userspace implementation model)

• Marcel from the PM2 project.

• The OS for the Tera/Cray MTA

• Microsoft Windows 7

• The Haskell compiler GHC uses lightweight threads which are scheduled on operating system threads.

Fiber implementation examples

Fibers can be implemented without operating system support, although some operating systems or libraries provide explicit support for them.

• Win32 supplies a fiber API (Windows NT 3.51 SP3 and later)

• Ruby as Green threads

• Netscape Portable Runtime (includes a user-space fibers implementation)

• ribs2

References

1. Pat Villani: Advanced WIN32 Programming: Files, Threads, and Process Synchronization, Harpercollins Publishers

2. Bill Lewis: Threads Primer: A Guide to Multithreaded Programming, Prentice Hall

3. http://www.dmoz.org//Computers/Programming/Threads/

4. http://www.futurechips.org/tips-for-power-coders/parallel-programming.html

5. Sibsankar Haldar, Alex Alagarsamy Aravind: Operating System