30 gambar yang memperincikan ringkasan sistem pengendalian!

1. Gambaran Keseluruhan

Ciri -ciri Basak

1. Concurrency

Concurrency merujuk kepada keupayaan untuk menjalankan pelbagai program pada masa yang sama dalam pengertian makroskopik, sementara paralelisme merujuk kepada keupayaan untuk menjalankan berbilang program pada masa yang sama pada masa yang sama.

Paralelisme memerlukan sokongan perkakasan, seperti berbilang saluran paip, pemproses berbilang teras atau sistem pengkomputeran teragih.

Sistem pengendalian membolehkan program berjalan serentak dengan memperkenalkan proses dan rangkaian.

2. Perkongsian

Perkongsian bermakna sumber dalam sistem boleh digunakan oleh pelbagai proses serentak.

Terdapat dua kaedah perkongsian: perkongsian eksklusif dan perkongsian serentak.

Sumber perkongsian yang saling eksklusif dipanggil sumber kritikal, seperti pencetak, dsb., hanya satu proses dibenarkan untuk mengaksesnya pada masa yang sama dan mekanisme penyegerakan diperlukan untuk mencapai akses eksklusif bersama.

3. Maya

Teknologi maya menukar entiti fizikal kepada berbilang entiti logik.

Terdapat terutamanya dua teknologi maya: teknologi pemultipleksan pembahagian masa (masa) dan teknologi pemultipleksan pembahagian ruang (ruang).

Berbilang proses boleh dilaksanakan serentak pada pemproses yang sama menggunakan teknologi pemultipleksan pembahagian masa, membenarkan setiap proses untuk menduduki pemproses secara bergilir-gilir, melaksanakan hanya sekeping masa yang kecil setiap kali dan bertukar dengan cepat.

Memori maya menggunakan teknologi pemultipleksan pembahagian ruang, yang mengabstraksi memori fizikal ke dalam ruang alamat, dan setiap proses mempunyai ruang alamat sendiri. Halaman dalam ruang alamat dipetakan ke memori fizikal Tidak semua halaman dalam ruang alamat perlu berada dalam ingatan fizikal Apabila halaman yang tidak berada dalam memori fizikal digunakan, algoritma penggantian halaman dilaksanakan untuk menggantikan halaman ke dalam memori.

4. Asynchronous

Asynchronous bermaksud proses itu tidak dilaksanakan serentak, tetapi berhenti dan pergi, memajukan pada kelajuan yang tidak diketahui.

Fungsi asas

1. Pengurusan proses

Kawalan proses, penyegerakan proses, komunikasi proses, pengendalian kebuntuan, penjadualan pemproses, dll.

2. Pengurusan memori

Peruntukan memori, pemetaan alamat, perlindungan dan perkongsian memori, ingatan maya, dsb.

3. Pengurusan fail

Pengurusan ruang storan fail, pengurusan direktori, pengurusan dan perlindungan baca dan tulis fail, dsb.

4. Pengurusan peranti

Melengkapkan permintaan I/O pengguna, memudahkan pengguna menggunakan pelbagai peranti dan meningkatkan penggunaan peranti.

Terutamanya termasuk pengurusan penimbal, peruntukan peranti, pemprosesan peranti, peranti maya, dsb.

Panggilan sistem

Jika proses perlu menggunakan fungsi keadaan kernel dalam mod pengguna, ia akan membuat panggilan sistem dan jatuh ke dalam kernel, dan sistem pengendalian akan melengkapkannya bagi pihaknya.

Panggilan sistem Linux terutamanya termasuk yang berikut:

Inti besar dan mikrokernel

yang besar sistem pengendalian berfungsi sebagai a tutup Gabungan keseluruhan dimasukkan ke dalam kernel.

Memandangkan setiap modul berkongsi maklumat, ia mempunyai prestasi tinggi.

2. Mikrokernel

Memandangkan sistem pengendalian terus menjadi lebih kompleks, beberapa fungsi sistem pengendalian dialih keluar dari kernel, dengan itu mengurangkan kerumitan kernel. Bahagian yang dikeluarkan dibahagikan kepada beberapa perkhidmatan berdasarkan prinsip lapisan, yang bebas antara satu sama lain.

Di bawah struktur mikrokernel, sistem pengendalian dibahagikan kepada modul kecil yang ditakrifkan dengan baik Hanya modul mikrokernel berjalan dalam mod kernel, dan modul lain berjalan dalam mod pengguna.

Oleh kerana anda perlu kerap menukar antara mod pengguna dan mod teras, akan berlaku kehilangan prestasi tertentu.

Klasifikasi sampukan

11 Gangguan luaran

disebabkan oleh peristiwa selain daripada arahan pelaksana CPU, seperti I/O pelengkapan yang menunjukkan penyiapan input. telah selesai dan pemproses boleh menghantar permintaan input/output Seterusnya. Di samping itu, terdapat gangguan jam, gangguan konsol, dll.

2. Pengecualian

disebabkan oleh peristiwa dalaman apabila CPU melaksanakan arahan, seperti opcode haram, alamat di luar sempadan, limpahan aritmetik, dsb.

3. Terjerumus ke dalam

menggunakan panggilan sistem dalam program pengguna.

2. Pengurusan Proses

Proses dan Benang

1. Proses

Proses ialah unit asas peruntukan sumber.

Process Control Block (PCB) menerangkan maklumat asas dan status berjalan proses Yang dipanggil proses penciptaan dan pembatalan merujuk kepada operasi pada PCB.

Gambar di bawah menunjukkan bahawa 4 atur cara mencipta 4 proses, dan 4 proses ini boleh dilaksanakan secara serentak.

2. Benang

Benang ialah unit asas penjadualan bebas.

Boleh terdapat berbilang utas dalam satu proses, dan mereka berkongsi sumber proses.

QQ dan penyemak imbas adalah dua proses Terdapat banyak utas dalam proses penyemak imbas, seperti utas permintaan HTTP, utas tindak balas acara, utas pemaparan, dll. Pelaksanaan urutan serentak membolehkan mengklik pautan baharu dalam penyemak imbas untuk memulakan urutan. Permintaan HTTP Penyemak imbas juga boleh bertindak balas kepada acara lain daripada pengguna.

3. Perbezaan

Ⅰ Memiliki sumber

Proses ialah unit asas peruntukan sumber, tetapi benang tidak memiliki sumber, dan benang boleh mengakses sumber kepunyaan proses. .

Ⅲ Sistem overhed

Memandangkan apabila membuat atau membatalkan proses, sistem mesti memperuntukkan atau mengitar semula sumber, seperti ruang memori, peranti I/O, dsb., overhed yang ditanggung adalah jauh lebih besar daripada overhed apabila mencipta atau membatalkan benang. Begitu juga, apabila menukar proses, ia melibatkan penjimatan persekitaran CPU proses yang sedang dilaksanakan dan menetapkan persekitaran CPU bagi proses berjadual baharu Walau bagaimanapun, apabila menukar benang, hanya sebilangan kecil kandungan daftar perlu disimpan dan ditetapkan, dan overhead adalah sangat kecil.

Ⅳ Dari segi komunikasi

Thread boleh berkomunikasi secara terus membaca dan menulis data dalam proses yang sama, tetapi komunikasi proses memerlukan penggunaan IPC.

Penukaran status proses

• Status sedia (sedia): menunggu untuk dijadualkan

  Keadaan menyekat (menunggu) : Semasa menunggu sumber

• anda harus memberi perhatian kepada perkara berikut:

• Hanya keadaan sedia dan keadaan berjalan boleh ditukar kepada satu sama lain, dan yang lain adalah penukaran sehala. Proses dalam keadaan sedia memperoleh masa CPU melalui algoritma penjadualan dan berubah kepada keadaan berjalan manakala proses dalam keadaan berjalan akan berubah kepada keadaan sedia selepas kepingan masa CPU yang diperuntukkan kepadanya habis, menunggu penjadualan seterusnya; .

Keadaan menyekat ialah kekurangan sumber yang diperlukan dan ditukar daripada keadaan berjalan, tetapi sumber ini tidak termasuk masa CPU Kekurangan masa CPU akan menukar daripada keadaan berjalan kepada keadaan sedia.

Algoritma Penjadualan Proses

Algoritma penjadualan dalam persekitaran yang berbeza mempunyai matlamat yang berbeza, jadi algoritma penjadualan perlu dibincangkan untuk persekitaran yang berbeza.

1. Sistem pemprosesan kelompok

Sistem pemprosesan kelompok tidak mempunyai terlalu banyak operasi pengguna Dalam sistem ini, matlamat algoritma penjadualan adalah untuk memastikan masa pemprosesan dan penyelesaian (masa dari penyerahan hingga penamatan).

1.1 First-come first-server (FCFS)

Algoritma penjadualan bukan preemptif yang menjadualkan mengikut urutan permintaan.

Ia bagus untuk kerja yang panjang, tetapi tidak bagus untuk kerja yang singkat, kerana kerja yang pendek mesti menunggu untuk kerja yang lama sebelum ini selesai sebelum ia boleh dilaksanakan, dan kerja yang panjang perlu dilaksanakan untuk masa yang lama, mengakibatkan pendek. pekerjaan menunggu terlalu lama.

1.2 Kerja paling singkat dahulu (SJF)

Algoritma penjadualan bukan preemptif yang menjadualkan dalam susunan anggaran masa berjalan terpendek.

Kerja yang panjang mungkin mati kelaparan dan berada dalam keadaan menunggu kerja yang singkat untuk disiapkan. Kerana jika selalu ada pekerjaan pendek yang datang, maka pekerjaan yang panjang tidak akan pernah dijadualkan.

1.3 Baki masa terpendek seterusnya (SRTN)

Versi awalan kerja terpendek dahulu, dijadualkan mengikut urutan baki masa berjalan. Apabila kerja baharu tiba, keseluruhan masa berjalannya dibandingkan dengan baki masa proses semasa. Jika proses baharu memerlukan lebih sedikit masa, proses semasa digantung dan proses baharu dijalankan. Jika tidak proses baru menunggu.

2. Sistem interaktif

Sistem interaktif mempunyai bilangan interaksi pengguna yang besar, dan matlamat algoritma penjadualan dalam sistem ini adalah untuk bertindak balas dengan cepat.

2.1 Putaran kepingan masa

Susun semua proses sedia ke dalam baris gilir mengikut prinsip FCFS Setiap kali ia dijadualkan, masa CPU diperuntukkan kepada proses ketua baris gilir, yang boleh melaksanakan kepingan masa. Apabila potongan masa habis, gangguan jam dikeluarkan oleh pemasa, dan penjadual menghentikan pelaksanaan proses dan menghantarnya ke penghujung baris gilir sedia, sambil terus memperuntukkan masa CPU kepada proses di kepala barisan.

Kecekapan algoritma putaran kepingan masa mempunyai hubungan yang hebat dengan saiz kepingan masa:

• Oleh kerana penukaran proses mesti menyimpan maklumat proses dan memuatkan maklumat proses baharu, jika kepingan masa terlalu kecil, ia akan menyebabkan penukaran proses Terlalu kerap dan terlalu banyak masa akan dihabiskan untuk menukar proses.

• Dan jika potongan masa terlalu panjang, maka prestasi masa nyata tidak boleh dijamin.

2.2 Penjadualan Keutamaan

Tetapkan keutamaan kepada setiap proses dan jadualkannya mengikut keutamaan.

Untuk mengelakkan proses keutamaan rendah daripada tidak menunggu penjadualan, anda boleh meningkatkan keutamaan proses menunggu dari semasa ke semasa.

2.3 Barisan maklum balas pelbagai peringkat

Satu proses perlu melaksanakan 100 kepingan masa Jika algoritma penjadualan putaran kepingan masa digunakan, 100 pertukaran diperlukan.

Baris gilir berbilang peringkat dipertimbangkan untuk proses yang perlu melaksanakan beberapa keping masa secara berterusan Ia menyediakan berbilang baris gilir, dan setiap baris gilir mempunyai saiz kepingan masa yang berbeza, seperti 1,2,4,8,... Jika proses tidak selesai melaksanakan dalam baris gilir pertama, ia akan dialihkan ke baris gilir seterusnya. Dengan cara ini, proses sebelumnya hanya perlu ditukar sebanyak 7 kali.

Setiap barisan mempunyai keutamaan yang berbeza, dan yang teratas mempunyai keutamaan tertinggi. Oleh itu, proses pada baris gilir semasa boleh dijadualkan hanya jika tiada proses dalam baris gilir sebelumnya.

Algoritma penjadualan ini boleh dianggap sebagai gabungan algoritma penjadualan putaran kepingan masa dan algoritma penjadualan keutamaan.

3. Sistem masa nyata

Sistem masa nyata memerlukan permintaan dijawab dalam masa tertentu.

牛逼啊！接私活必备的 N 个开源项目！赶快收藏吧...

dibahagikan kepada masa nyata keras dan masa nyata lembut yang pertama mesti memenuhi tarikh akhir mutlak, dan yang terakhir boleh bertolak ansur dengan tamat masa tertentu.

Penyegerakan Proses

1. Bahagian Kritikal

Kod yang mengakses sumber kritikal dipanggil bahagian kritikal.

Untuk mempunyai akses yang saling eksklusif kepada sumber kritikal, setiap proses perlu diperiksa sebelum memasuki bahagian kritikal.

// entry section
// critical section;
// exit section

2. Penyegerakan dan pengecualian bersama

• Penyegerakan: Berbilang proses mempunyai hubungan pelaksanaan berurutan tertentu disebabkan oleh hubungan sekatan langsung yang disebabkan oleh kerjasama.

• Pengecualian bersama: Hanya satu proses berbilang proses boleh memasuki bahagian kritikal pada masa yang sama.

3

信号量（Semaphore）是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 P 和 V 操作。

• down   : 如果信号量大于 0 ，执行 -1 操作；如果信号量等于 0，进程睡眠，等待信号量大于 0；

• up  ：对信号量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作。

down 和 up 操作需要被设计成原语，不可分割，通常的做法是在执行这些操作的时候屏蔽中断。

如果信号量的取值只能为 0 或者 1，那么就成为了   互斥量（Mutex）  ，0 表示临界区已经加锁，1 表示临界区解锁。

typedef int semaphore;
semaphore mutex = 1;
void P1() {
    down(&mutex);
    // 临界区
    up(&mutex);
}

void P2() {
    down(&mutex);
    // 临界区
    up(&mutex);
}

使用信号量实现生产者-消费者问题

问题描述：使用一个缓冲区来保存物品，只有缓冲区没有满，生产者才可以放入物品；只有缓冲区不为空，消费者才可以拿走物品。

因为缓冲区属于临界资源，因此需要使用一个互斥量 mutex 来控制对缓冲区的互斥访问。

为了同步生产者和消费者的行为，需要记录缓冲区中物品的数量。数量可以使用信号量来进行统计，这里需要使用两个信号量：empty 记录空缓冲区的数量，full 记录满缓冲区的数量。其中，empty 信号量是在生产者进程中使用，当 empty 不为 0 时，生产者才可以放入物品；full 信号量是在消费者进程中使用，当 full 信号量不为 0 时，消费者才可以取走物品。

注意，不能先对缓冲区进行加锁，再测试信号量。也就是说，不能先执行 down(mutex) 再执行 down(empty)。如果这么做了，那么可能会出现这种情况：生产者对缓冲区加锁后，执行 down(empty) 操作，发现 empty = 0，此时生产者睡眠。消费者不能进入临界区，因为生产者对缓冲区加锁了，消费者就无法执行 up(empty) 操作，empty 永远都为 0，导致生产者永远等待下，不会释放锁，消费者因此也会永远等待下去。

#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void producer() {
    while(TRUE) {
        int item = produce_item();
        down(&empty);
        down(&mutex);
        insert_item(item);
        up(&mutex);
        up(&full);
    }
}

void consumer() {
    while(TRUE) {
        down(&full);
        down(&mutex);
        int item = remove_item();
        consume_item(item);
        up(&mutex);
        up(&empty);
    }
}

4. 管程

使用信号量机制实现的生产者消费者问题需要客户端代码做很多控制，而管程把控制的代码独立出来，不仅不容易出错，也使得客户端代码调用更容易。

c 语言不支持管程，下面的示例代码使用了类 Pascal 语言来描述管程。示例代码的管程提供了 insert() 和 remove() 方法，客户端代码通过调用这两个方法来解决生产者-消费者问题。

monitor ProducerConsumer
    integer i;
    condition c;

    procedure insert();
    begin
        // ...
    end;

    procedure remove();
    begin
        // ...
    end;
end monitor;

管程有一个重要特性：在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。

管程引入了   条件变量   以及相关的操作：wait() 和 signal() 来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞，把管程让出来给另一个进程持有。signal() 操作用于唤醒被阻塞的进程。

使用管程实现生产者-消费者问题

// 管程
monitor ProducerConsumer
    condition full, empty;
    integer count := 0;
    condition c;

    procedure insert(item: integer);
    begin
        if count = N then wait(full);
        insert_item(item);
        count := count + 1;
        if count = 1 then signal(empty);
    end;

    function remove: integer;
    begin
        if count = 0 then wait(empty);
        remove = remove_item;
        count := count - 1;
        if count = N -1 then signal(full);
    end;
end monitor;

// 生产者客户端
procedure producer
begin
    while true do
    begin
        item = produce_item;
        ProducerConsumer.insert(item);
    end
end;

// 消费者客户端
procedure consumer
begin
    while true do
    begin
        item = ProducerConsumer.remove;
        consume_item(item);
    end
end;

经典同步问题

生产者和消费者问题前面已经讨论过了。

1. 哲学家进餐问题

五个哲学家围着一张圆桌，每个哲学家面前放着食物。哲学家的生活有两种交替活动：吃饭以及思考。当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，并且一次只能拿起一根筷子。

下面是一种错误的解法，如果所有哲学家同时拿起左手边的筷子，那么所有哲学家都在等待其它哲学家吃完并释放自己手中的筷子，导致死锁。

#define N 5

void philosopher(int i) {
    while(TRUE) {
        think();
        take(i);       // 拿起左边的筷子
        take((i+1)%N); // 拿起右边的筷子
        eat();
        put(i);
        put((i+1)%N);
    }
}

为了防止死锁的发生，可以设置两个条件：

• 必须同时拿起左右两根筷子；

• 只有在两个邻居都没有进餐的情况下才允许进餐。

#define N 5
#define LEFT (i + N - 1) % N // 左邻居
#define RIGHT (i + 1) % N    // 右邻居
#define THINKING 0
#define HUNGRY   1
#define EATING   2
typedef int semaphore;
int state[N];                // 跟踪每个哲学家的状态
semaphore mutex = 1;         // 临界区的互斥，临界区是 state 数组，对其修改需要互斥
semaphore s[N];              // 每个哲学家一个信号量

void philosopher(int i) {
    while(TRUE) {
        think(i);
        take_two(i);
        eat(i);
        put_two(i);
    }
}

void take_two(int i) {
    down(&mutex);
    state[i] = HUNGRY;
    check(i);
    up(&mutex);
    down(&s[i]); // 只有收到通知之后才可以开始吃，否则会一直等下去
}

void put_two(i) {
    down(&mutex);
    state[i] = THINKING;
    check(LEFT); // 尝试通知左右邻居，自己吃完了，你们可以开始吃了
    check(RIGHT);
    up(&mutex);
}

void eat(int i) {
    down(&mutex);
    state[i] = EATING;
    up(&mutex);
}

// 检查两个邻居是否都没有用餐，如果是的话，就 up(&s[i])，使得 down(&s[i]) 能够得到通知并继续执行
void check(i) {         
    if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) {
        state[i] = EATING;
        up(&s[i]);
    }
}

2. 读者-写者问题

允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生。另外，搜索公众号顶级算法后台回复“算法”，获取一份惊喜礼包。

一个整型变量 count 记录在对数据进行读操作的进程数量，一个互斥量 count_mutex 用于对 count 加锁，一个互斥量 data_mutex 用于对读写的数据加锁。

typedef int semaphore;
semaphore count_mutex = 1;
semaphore data_mutex = 1;
int count = 0;

void reader() {
    while(TRUE) {
        down(&count_mutex);
        count++;
        if(count == 1) down(&data_mutex); // 第一个读者需要对数据进行加锁，防止写进程访问
        up(&count_mutex);
        read();
        down(&count_mutex);
        count--;
        if(count == 0) up(&data_mutex);
        up(&count_mutex);
    }
}

void writer() {
    while(TRUE) {
        down(&data_mutex);
        write();
        up(&data_mutex);
    }
}

以下内容由 @Bandi Yugandhar 提供。

The first case may result Writer to starve. This case favous Writers i.e no writer, once added to the queue, shall be kept waiting longer than absolutely necessary(only when there are readers that entered the queue before the writer).

int readcount, writecount;                   //(initial value = 0)
semaphore rmutex, wmutex, readLock, resource; //(initial value = 1)

//READER
void reader() {
<ENTRY Section>
 down(&readLock);                 //  reader is trying to enter
 down(&rmutex);                  //   lock to increase readcount
  readcount++;                 
  if (readcount == 1)          
   down(&resource);              //if you are the first reader then lock  the resource
 up(&rmutex);                  //release  for other readers
 up(&readLock);                 //Done with trying to access the resource

<CRITICAL Section>
//reading is performed

<EXIT Section>
 down(&rmutex);                  //reserve exit section - avoids race condition with readers
 readcount--;                       //indicate you&#39;re leaving
  if (readcount == 0)          //checks if you are last reader leaving
   up(&resource);              //if last, you must release the locked resource
 up(&rmutex);                  //release exit section for other readers
}

//WRITER
void writer() {
  <ENTRY Section>
  down(&wmutex);                  //reserve entry section for writers - avoids race conditions
  writecount++;                //report yourself as a writer entering
  if (writecount == 1)         //checks if you&#39;re first writer
   down(&readLock);               //if you&#39;re first, then you must lock the readers out. Prevent them from trying to enter CS
  up(&wmutex);                  //release entry section

<CRITICAL Section>
 down(&resource);                //reserve the resource for yourself - prevents other writers from simultaneously editing the shared resource
  //writing is performed
 up(&resource);                //release file

<EXIT Section>
  down(&wmutex);                  //reserve exit section
  writecount--;                //indicate you&#39;re leaving
  if (writecount == 0)         //checks if you&#39;re the last writer
   up(&readLock);               //if you&#39;re last writer, you must unlock the readers. Allows them to try enter CS for reading
  up(&wmutex);                  //release exit section
}

We can observe that every reader is forced to acquire ReadLock. On the otherhand, writers doesn’t need to lock individually. Once the first writer locks the ReadLock, it will be released only when there is no writer left in the queue.

From the both cases we observed that either reader or writer has to starve. Below solutionadds the constraint that no thread shall be allowed to starve; that is, the operation of obtaining a lock on the shared data will always terminate in a bounded amount of time.

int readCount;                  // init to 0; number of readers currently accessing resource

// all semaphores initialised to 1
Semaphore resourceAccess;       // controls access (read/write) to the resource
Semaphore readCountAccess;      // for syncing changes to shared variable readCount
Semaphore serviceQueue;         // FAIRNESS: preserves ordering of requests (signaling must be FIFO)

void writer()
{ 
    down(&serviceQueue);           // wait in line to be servicexs
    // <ENTER>
    down(&resourceAccess);         // request exclusive access to resource
    // </ENTER>
    up(&serviceQueue);           // let next in line be serviced

    // <WRITE>
    writeResource();            // writing is performed
    // </WRITE>

    // <EXIT>
    up(&resourceAccess);         // release resource access for next reader/writer
    // </EXIT>
}

void reader()
{ 
    down(&serviceQueue);           // wait in line to be serviced
    down(&readCountAccess);        // request exclusive access to readCount
    // <ENTER>
    if (readCount == 0)         // if there are no readers already reading:
        down(&resourceAccess);     // request resource access for readers (writers blocked)
    readCount++;                // update count of active readers
    // </ENTER>
    up(&serviceQueue);           // let next in line be serviced
    up(&readCountAccess);        // release access to readCount

    // <READ>
    readResource();             // reading is performed
    // </READ>

    down(&readCountAccess);        // request exclusive access to readCount
    // <EXIT>
    readCount--;                // update count of active readers
    if (readCount == 0)         // if there are no readers left:
        up(&resourceAccess);     // release resource access for all
    // </EXIT>
    up(&readCountAccess);        // release access to readCount
}

进程通信

进程同步与进程通信很容易混淆，它们的区别在于：

• 进程同步：控制多个进程按一定顺序执行；

• 进程通信：进程间传输信息。

进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

1. 管道

管道是通过调用 pipe 函数创建的，fd[0] 用于读，fd[1] 用于写。

#include <unistd.h>
int pipe(int fd[2]);

它具有以下限制：

• 只支持半双工通信（单向交替传输）；

• 只能在父子进程或者兄弟进程中使用。

2. FIFO

也称为命名管道，去除了管道只能在父子进程中使用的限制。

#include <sys/stat.h>
int mkfifo(const char *path, mode_t mode);
int mkfifoat(int fd, const char *path, mode_t mode);

FIFO 常用于客户-服务器应用程序中，FIFO 用作汇聚点，在客户进程和服务器进程之间传递数据。

3. Baris Mesej

Berbanding dengan FIFO, baris gilir mesej mempunyai kelebihan berikut:

• Baris gilir mesej boleh wujud secara bebas dan dengan itu mengelakkan proses pembacaan dan penyegerakan paip dalam FIFO Kemungkinan kesukaran semasa menutup; jenis, tidak seperti FIFO hanya boleh menerima secara lalai.

• 4. Semaphore

Ia adalah kaunter yang digunakan untuk menyediakan berbilang proses dengan akses kepada objek data yang dikongsi.

• 5. Storan kongsi

membenarkan berbilang proses untuk berkongsi kawasan storan tertentu. Oleh kerana data tidak perlu disalin antara proses, ini adalah jenis IPC terpantas.

Anda perlu menggunakan semaphore untuk menyegerakkan akses kepada storan kongsi. Berbilang proses boleh memetakan fail yang sama ke dalam ruang alamat mereka untuk mencapai memori bersama. Selain itu, memori kongsi XSI tidak menggunakan fail, tetapi menggunakan segmen memori tanpa nama.

6

Tidak seperti mekanisme komunikasi lain, ia boleh digunakan untuk proses komunikasi antara mesin yang berbeza.

3. Pengurusan Memori

Memori Maya

Tujuan ingatan maya adalah untuk mengembangkan memori fizikal kepada ingatan logik yang lebih besar, supaya atur cara boleh memperoleh lebih banyak memori yang tersedia.

Untuk mengurus memori dengan lebih baik, sistem pengendalian mengabstrakkan memori ke dalam ruang alamat. Setiap program mempunyai ruang alamat sendiri, yang dibahagikan kepada beberapa blok, setiap blok dipanggil halaman. Halaman dipetakan ke dalam ingatan fizikal, tetapi tidak perlu dipetakan ke dalam ingatan fizikal bersebelahan, begitu juga semua halaman tidak perlu dalam ingatan fizikal. Apabila program merujuk halaman yang tiada dalam memori fizikal, perkakasan melaksanakan pemetaan yang diperlukan, memuatkan bahagian yang hilang ke dalam memori fizikal dan melaksanakan semula arahan yang gagal.

Seperti yang dapat dilihat dari huraian di atas, memori maya membenarkan atur cara untuk tidak memetakan setiap halaman dalam ruang alamat ke memori fizikal, yang bermaksud bahawa program tidak perlu dimuatkan ke dalam memori untuk dijalankan, yang menjadikan terhad memori Ia adalah mungkin untuk menjalankan program besar. Contohnya, jika komputer boleh menjana alamat 16-bit, maka julat ruang alamat program ialah 0~64K. Komputer hanya mempunyai 32KB memori fizikal, dan teknologi memori maya membolehkan komputer menjalankan program 64K.

Pemetaan alamat sistem paging

Unit pengurusan memori (MMU) menguruskan penukaran ruang alamat dan memori fizikal, dan jadual halaman (Jadual halaman) menyimpan halaman (ruang alamat program) dan bingkai halaman (ruang ingatan fizikal) jadual pemetaan.

Alamat maya terbahagi kepada dua bahagian, satu bahagian menyimpan nombor halaman dan bahagian lain menyimpan offset.

下图的页表存放着 16 个页，这 16 个页需要用 4 个比特位来进行索引定位。例如对于虚拟地址（0010 000000000100），前 4 位是存储页面号 2，读取表项内容为（110 1），页表项最后一位表示是否存在于内存中，1 表示存在。后 12 位存储偏移量。这个页对应的页框的地址为 （110 000000000100）。

页面置换算法

在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。

页面置换算法和缓存淘汰策略类似，可以将内存看成磁盘的缓存。在缓存系统中，缓存的大小有限，当有新的缓存到达时，需要淘汰一部分已经存在的缓存，这样才有空间存放新的缓存数据。

页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。

1. 最佳

OPT, Optimal replacement algorithm

所选择的被换出的页面将是最长时间内不再被访问，通常可以保证获得最低的缺页率。

是一种理论上的算法，因为无法知道一个页面多长时间不再被访问。

举例：一个系统为某进程分配了三个物理块，并有如下页面引用序列：

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

开始运行时，先将 7, 0, 1 三个页面装入内存。当进程要访问页面 2 时，产生缺页中断，会将页面 7 换出，因为页面 7 再次被访问的时间最长。

2. 最近最久未使用

LRU, Least Recently Used

虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。

为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。

因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。

4，7，0，7，1，0，1，2，1，2，6

3. 最近未使用

NRU, Not Recently Used

每个页面都有两个状态位：R 与 M，当页面被访问时设置页面的 R=1，当页面被修改时设置 M=1。其中 R 位会定时被清零。可以将页面分成以下四类：

R=0，M=0
R=0，M=1
R=1，M=0
R=1，M=1

当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出。

NRU 优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）。

4. Mula-mula masuk, keluar dahulu

FIFO, Mula-mula Masuk Dahulu

Halaman yang dipilih untuk ditukar adalah halaman yang dimasukkan dahulu.

Algoritma ini akan menukar halaman yang kerap diakses, mengakibatkan peningkatan dalam kadar kerosakan halaman.

5. Algoritma Peluang Kedua

Algoritma FIFO boleh menggantikan halaman yang kerap digunakan Untuk mengelakkan masalah ini, buat pengubahsuaian mudah pada algoritma:

Apabila halaman diakses (dibaca atau ditulis) ), tetapkan. R bit halaman ke 1. Apabila penggantian diperlukan, semak bit R halaman tertua. Jika bit R ialah 0, maka halaman itu sudah lama dan tidak digunakan dan boleh digantikan serta-merta jika ia adalah 1, kosongkan bit R kepada 0, letakkan halaman itu pada penghujung senarai terpaut, dan ubah suai masa pemuatannya supaya; Ia bertindak seolah-olah ia baru dimuatkan dan terus mencari dari kepala senarai.

6. Jam

Jam

Algoritma peluang kedua perlu mengalihkan halaman dalam senarai terpaut, yang mengurangkan kecekapan. Algoritma jam menggunakan senarai pautan bulat untuk menyambung halaman, dan kemudian menggunakan penunjuk untuk menghala ke halaman tertua.

Segmentasi

Memori maya menggunakan teknologi halaman, yang bermaksud ruang alamat dibahagikan kepada halaman bersaiz tetap, dan setiap halaman dipetakan dengan memori.

Gambar di bawah menunjukkan berbilang jadual yang dibuat oleh pengkompil semasa proses penyusunan Empat daripada jadual berkembang secara dinamik Jika ruang alamat satu dimensi sistem paging digunakan, ciri pertumbuhan dinamik akan membawa kepada masalah liputan.

Kaedah segmentasi adalah untuk membahagikan setiap jadual kepada segmen, dan setiap segmen membentuk ruang alamat bebas. Setiap segmen boleh berbeza panjang dan boleh berkembang secara dinamik.

Paging segmen

Ruang alamat program dibahagikan kepada berbilang segmen dengan ruang alamat bebas, dan ruang alamat pada setiap segmen dibahagikan kepada halaman yang sama saiz. Ini bukan sahaja mempunyai perkongsian dan perlindungan sistem bersegmen, tetapi juga mempunyai fungsi memori maya sistem paging.

Perbandingan paging dan segmentasi

• Ketelusan kepada pengaturcara: Paging adalah telus, tetapi segmentasi memerlukan pengaturcara membahagikan setiap segmen secara eksplisit.

• Dimensi ruang alamat: Paging ialah ruang alamat satu dimensi dan pembahagian adalah dua dimensi.

• Sama ada saiz boleh ditukar: saiz halaman tidak boleh diubah dan saiz segmen boleh ditukar secara dinamik.

• Sebab penampilan: Paging digunakan terutamanya untuk melaksanakan memori maya untuk mendapatkan ruang alamat yang lebih besar terutamanya supaya program dan data boleh dibahagikan kepada ruang alamat bebas secara logik dan memudahkan perkongsian dan perlindungan.

4. Pengurusan Peranti

Struktur Cakera

• Pinggan: Cakera mempunyai berbilang cakera

• ; kawasan jalur, tin cakera mempunyai berbilang trek;

• Sektor Trek: segmen arka pada trek, trek boleh mempunyai pelbagai sektor, ia adalah unit storan fizikal terkecil, pada masa ini Terutamanya tersedia dalam dua saiz: 512 bait dan 4 K;

Kepala: sangat dekat dengan permukaan cakera, mampu menukar medan magnet pada permukaan cakera kepada isyarat elektrik (membaca), atau menukar isyarat elektrik kepada medan magnet pada permukaan cakera (Tulis); mencari akaun awam Linux, ini adalah cara anda harus belajar membalas "Linux" di latar belakang untuk mendapatkan pakej hadiah kejutan.
Lengan penggerak: digunakan untuk menggerakkan kepala magnet di antara trek

• Spindle: Membuat keseluruhan cakera berputar.

Algoritma penjadualan cakera

Faktor yang mempengaruhi masa membaca dan menulis blok cakera ialah:

• masa putaran cakera sektor yang bersesuaian) )

• Cari masa (pergerakan lengan brek, menyebabkan kepala bergerak ke trek yang sesuai)

• Masa pemindahan data sebenar

  mencari masa

adalah antaranya paling lama, jadi Matlamat utama penjadualan cakera adalah untuk meminimumkan purata masa pencarian cakera.

1. First come first serve

FCFS, First Come First Served

Penjadualan dilakukan mengikut urutan permintaan cakera.

Kelebihan adalah keadilan dan kesederhanaan. Kelemahannya juga jelas, kerana tiada pengoptimuman telah dilakukan untuk mencari, jadi purata masa pencarian mungkin lebih lama.

.

Walaupun purata masa pencarian agak rendah, ia tidak cukup adil. Jika permintaan trek yang baru tiba sentiasa lebih dekat daripada permintaan trek menunggu, maka permintaan trek menunggu akan menunggu selama-lamanya, iaitu, kebuluran berlaku. Khususnya, permintaan trek di kedua-dua hujung lebih terdedah kepada kelaparan. Lihat sistem kawalan jauh itu, ia sangat elegan (kod sumber dilampirkan)!

3. Algoritma Lif

SCAN

Lif sentiasa berjalan ke satu arah sehingga tiada permintaan ke arah itu, dan kemudian menukar arah larian.

Algoritma lif (algoritma imbasan) adalah serupa dengan proses operasi lif Ia sentiasa menjadualkan cakera dalam satu arah sehingga tiada permintaan cakera tertunggak ke arah itu, dan kemudian menukar arah.

Oleh kerana arah pergerakan dipertimbangkan, semua permintaan cakera akan dipenuhi, menyelesaikan masalah kebuluran SSTF.

五、链接

编译系统

以下是一个 hello.c 程序：

#include <stdio.h>

int main()
{
    printf("hello, world\n");
    return 0;
}

在 Unix 系统上，由编译器把源文件转换为目标文件。

gcc -o hello hello.c

这个过程大致如下：

预处理阶段：处理以 # 开头的预处理命令；

编译阶段：翻译成汇编文件；

汇编阶段：将汇编文件翻译成可重定位目标文件；

链接阶段：将可重定位目标文件和 printf.o 等单独预编译好的目标文件进行合并，得到最终的可执行目标文件。

静态链接

静态链接器以一组可重定位目标文件为输入，生成一个完全链接的可执行目标文件作为输出。链接器主要完成以下两个任务：

• Leraian simbol: Setiap simbol sepadan dengan fungsi, pembolehubah global atau pembolehubah statik Tujuan peleraian simbol adalah untuk mengaitkan setiap rujukan simbol dengan definisi simbol.

• Penempatan Semula: Penyambung mengaitkan setiap definisi simbol dengan lokasi memori, dan kemudian mengubah suai semua rujukan kepada simbol ini supaya ia menghala ke lokasi memori ini.

Fail sasaran

• Fail sasaran boleh laksana: boleh dilaksanakan terus dalam ingatan

• : fail jadual semula

; digabungkan dengan sasaran lain yang boleh dipindahkan Fail digabungkan semasa fasa pemautan untuk mencipta fail objek boleh laku;
• Perpustakaan statik mempunyai dua masalah berikut:

Apabila perpustakaan statik dikemas kini, keseluruhan program mesti dipautkan semula

Untuk perpustakaan fungsi standard seperti printf, jika setiap program perlu mempunyai kod, ia akan menjadi pembaziran sumber yang besar.

Pustaka dikongsi direka untuk menyelesaikan dua masalah perpustakaan statik ini Ia biasanya diwakili oleh akhiran .so pada sistem Linux dan ia dipanggil DLL pada sistem Windows. Ia mempunyai ciri-ciri berikut:

• Hanya terdapat satu fail untuk pustaka dalam sistem fail tertentu Fail ini dikongsi oleh semua fail objek boleh laku yang merujuk pustaka Ia tidak akan disalin ke fail boleh laku yang merujuk ia. ;

• Dalam ingatan, salinan bahagian .teks perpustakaan kongsi (kod mesin atur cara yang disusun) boleh dikongsi oleh proses berjalan yang berbeza.

6. Jalan buntu

Syarat yang perlu

• Pengecualian bersama: Setiap sumber sama ada telah diperuntukkan kepada proses atau tersedia.

• Cukup dan tunggu: Proses yang telah memperoleh sumber boleh meminta sumber baharu.

• Tidak boleh didahulukan: Sumber yang telah diperuntukkan kepada proses tidak boleh didahulukan secara paksa, ia hanya boleh dikeluarkan secara eksplisit oleh proses yang mendudukinya.

• Gelung menunggu: Terdapat dua atau lebih proses membentuk gelung, dan setiap proses dalam gelung sedang menunggu sumber yang diduduki oleh proses seterusnya.

Kaedah pemprosesan

Terdapat terutamanya empat kaedah:

• strategi burung unta

• Pencegahan kebuntuan

Kebuntuan Mengelak

🎜Strategi Oostrich🎜🎜🎜Tenggelamkan kepala dalam pasir dan buat-buat tiada masalah langsung. 🎜

Oleh kerana kos untuk menyelesaikan masalah kebuntuan sangat tinggi, strategi burung unta, yang tidak mengambil langkah tugas, akan mencapai prestasi yang lebih tinggi.

Apabila kebuntuan berlaku, ia tidak akan memberi banyak kesan kepada pengguna, atau kebarangkalian kebuntuan adalah sangat rendah, anda boleh menggunakan strategi burung unta.

Kebanyakan sistem pengendalian, termasuk Unix, Linux dan Windows, menangani masalah kebuntuan hanya dengan mengabaikannya.

Pengesanan Kebuntuan dan Pemulihan Kebuntuan

tidak cuba mengelakkan kebuntuan, tetapi mengambil langkah untuk pulih apabila kebuntuan dikesan.

1. Pengesanan kebuntuan satu sumber bagi setiap jenis

Gambar di atas ialah gambarajah peruntukan sumber, di mana kotak mewakili sumber dan bulatan mewakili proses. Sumber yang menunjuk kepada proses bermakna sumber telah diperuntukkan kepada proses, dan proses yang menunjuk kepada sumber bermakna proses meminta untuk mendapatkan sumber.

Gelung boleh diekstrak daripada rajah a, seperti yang ditunjukkan dalam rajah b, yang memenuhi keadaan menunggu gelung, jadi kebuntuan akan berlaku.

Algoritma pengesanan jalan buntu untuk setiap jenis sumber dilaksanakan dengan mengesan sama ada terdapat kitaran dalam graf yang diarahkan, bermula dari nod, melakukan carian mendalam-pertama, dan menandakan nod yang dilawati, jika nod yang ditanda dilawati. Menunjukkan bahawa terdapat kitaran dalam graf yang diarahkan, iaitu kejadian kebuntuan dikesan.

2. Pengesanan kebuntuan untuk pelbagai sumber bagi setiap jenis

Dalam gambar di atas, terdapat tiga proses dan empat sumber Maksud setiap data adalah seperti berikut:

• E vektor: jumlah sumber

• Sebuah vektor: baki jumlah sumber

• Matriks C: Bilangan sumber yang dimiliki oleh setiap proses Setiap baris mewakili bilangan sumber yang dimiliki oleh matriks R: Bilangan sumber yang diminta oleh proses P1 dan P2 sumber berpuas hati. Hanya proses P3 boleh membiarkan P3 dilaksanakan dan kemudian melepaskan sumber yang dimiliki oleh P3 Pada masa ini, A = (2 2 2 0). P2 boleh dilaksanakan, dan sumber yang dimiliki oleh P2 dikeluarkan selepas pelaksanaan, A = (4 2 2 1). P1 juga boleh dilaksanakan. Semua proses dilaksanakan dengan lancar tanpa kebuntuan.

  Algoritma diringkaskan seperti berikut:
• Setiap proses tidak ditanda pada permulaan, dan proses pelaksanaan mungkin ditanda. Apabila algoritma tamat, sebarang proses yang tidak ditandakan adalah proses buntu.

  Cari proses Pi yang tidak bertanda yang sumber yang diminta adalah kurang daripada atau sama dengan A.

  Jika proses sedemikian ditemui, kemudian tambahkan vektor baris ke-i matriks C ke A, tandakan proses tersebut dan tukar kembali ke 1.

Jika tiada proses sedemikian, algoritma ditamatkan.

3. Pemulihan kebuntuan

Gunakan pemulihan preemption

Gunakan pemulihan balik

• Pemulihan dengan Proses Pembunuhan

Pencegahan Kebuntuan

Cegah kebuntuan sebelum program berjalan.

1. Melanggar syarat pengecualian bersama

Sebagai contoh, teknologi pencetak kili membenarkan beberapa proses untuk dikeluarkan pada masa yang sama, dan satu-satunya proses yang sebenarnya meminta pencetak fizikal ialah daemon pencetak.

2. Pemusnahan pemilikan dan keadaan menunggu

Salah satu cara untuk mencapai ini adalah dengan menyatakan bahawa semua proses meminta semua sumber yang diperlukan sebelum memulakan pelaksanaan.

3. Musnahkan keadaan tidak boleh didahulukan

4. Hancurkan gelung menunggu

Jumlah sumber secara seragam, dan proses hanya boleh meminta sumber dalam susunan berangka.

Mengelakkan Kebuntuan

Elakkan kebuntuan semasa program sedang berjalan.

1. Status keselamatan

Lajur kedua Mempunyai dalam Rajah a mewakili bilangan sumber yang telah dimiliki, lajur ketiga Maks mewakili jumlah sumber yang diperlukan, dan Percuma mewakili bilangan sumber yang boleh digunakan. Bermula dari gambar a, mula-mula biarkan B mempunyai semua sumber yang diperlukan (gambar b Selepas operasi selesai, lepaskan B. Pada masa ini, Percuma menjadi 5 (gambar c); supaya semua proses Kedua-duanya boleh berjalan dengan jayanya, jadi keadaan yang ditunjukkan dalam Rajah a boleh dikatakan selamat.

Definisi: Jika tiada kebuntuan berlaku, dan walaupun semua proses tiba-tiba meminta permintaan maksimum untuk sumber, masih terdapat susunan penjadualan yang membolehkan setiap proses berjalan hingga selesai, maka keadaan itu dikatakan selamat.

Pengesanan keadaan selamat adalah serupa dengan pengesanan kebuntuan, kerana keadaan selamat mesti memerlukan kebuntuan tidak boleh berlaku. Algoritma jurubank berikut sangat serupa dengan algoritma pengesanan kebuntuan dan boleh digabungkan untuk rujukan dan perbandingan.

2. Algoritma Jurubank untuk Sumber Tunggal

Seorang jurubank di sebuah bandar kecil menjanjikan jumlah tertentu kepada sekumpulan pelanggan adalah untuk menentukan sama ada kepuasan permintaan akan memasuki keadaan yang tidak selamat . Jika ya, tolak permintaan itu;

C dalam rajah di atas adalah keadaan tidak selamat, jadi algoritma akan menolak permintaan sebelumnya untuk mengelak daripada memasuki keadaan dalam Rajah c.

3. Algoritma Jurubank untuk pelbagai sumber

Terdapat lima proses dan empat sumber dalam gambar di atas. Gambar di sebelah kiri mewakili sumber yang telah diperuntukkan, dan gambar di sebelah kanan mewakili sumber yang masih perlu diperuntukkan. E, P dan A yang paling kanan mewakili masing-masing: jumlah sumber, sumber yang diperuntukkan dan sumber yang tersedia Sila ambil perhatian bahawa ketiga-tiga ini adalah vektor, bukan nilai tertentu Contohnya, A=(1020), yang bermaksud 1/4 sumber masing-masing. 0/2/0.

Algoritma untuk menyemak sama ada keadaan selamat adalah seperti berikut:

• Cari sama ada terdapat baris dalam matriks di sebelah kanan yang kurang daripada atau sama dengan vektor A. Jika tiada baris sedemikian wujud, sistem akan menemui jalan buntu dan keadaan tidak selamat.

• Jika garisan sedemikian ditemui, tandakan proses itu sebagai ditamatkan dan tambah sumber yang diperuntukkan kepada A.

• Ulang dua langkah di atas sehingga semua proses ditanda sebagai ditamatkan, maka statusnya selamat.

Jika sesebuah negeri tidak selamat, anda perlu menolak untuk memasuki negeri ini.

Atas ialah kandungan terperinci 30 gambar yang memperincikan ringkasan sistem pengendalian!. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!