Menerapkan Aliran Kooperatif Sederhana di C

Halo, Habr!



Terima kasih atas perhatian Anda pada postingan terjemahan kami sebelumnya di REST . Hari ini kami mengusulkan untuk melihat topik desain sistem dari sudut yang sedikit berbeda dan menerbitkan terjemahan artikel oleh Stephen Brennan, seorang termasyhur Linux, yang berbicara tentang penerapan multitaskingnya sendiri di ruang pengguna dan bagaimana hal itu dapat berguna.



Multitasking, seperti banyak kemampuan lain yang disediakan oleh sistem operasi, kami tidak hanya menerima begitu saja, tetapi juga melihatnya sebagai sesuatu yang biasa. Dengan komputer dan ponsel cerdas kami yang kuat, gagasan tentang komputer yang tidak dapat menangani ratusan proses tampak aneh. Saya pikir ini adalah salah satu kemungkinan yang membuat komputer sangat berguna, tetapi karena itulah mereka begitu rumit, terkadang tampak seperti sihir.



Sulit untuk mencoba-coba kode yang mengimplementasikan multitasking, dan tidak selalu jelas dalam hal mana lebih baik menerapkannya sendiri, sehingga Anda tidak perlu menulis seluruh sistem operasi. Saya cukup yakin bahwa tidak mungkin untuk sepenuhnya memahami fenomena tersebut sampai Anda menyadarinya sendiri. Oleh karena itu, saya memutuskan untuk menulis artikel di mana saya akan memberi tahu Anda bagaimana Anda dapat bermain dengan implementasi threading sederhana. Pada artikel ini, kami akan menerapkan aliran sederhana dalam

program C biasa (bukan sistem operasi).

Penyimpangan lirik tentang setjmp dan longjmp

Penjadwal akan sangat bergantung pada fungsi setjmp()dan longjmp(). Mereka tampak sedikit ajaib, jadi pertama-tama saya akan menjelaskan apa yang mereka lakukan, dan kemudian saya akan meluangkan sedikit waktu dan memberi tahu Anda caranya.



Fungsi ini setjmp()memungkinkan Anda untuk merekam informasi tentang pada tahap apa program dijalankan, sehingga nanti Anda dapat kembali ke titik ini. Variabel tipe diteruskan ke sana jmp_buf, di mana kami akan menyimpan informasi ini. Pertama kali kembali, fungsi setjmp()mengembalikan 0.



Nanti, Anda dapat menggunakan fungsi longjmp(jmp_buf, value)untuk langsung melanjutkan eksekusi dari titik pemanggilannya setjmp(). Dalam program Anda, situasi ini akan terlihat seperti setjmp()kembali untuk kedua kalinya. Argumennya akan kembali kali inivaluebahwa Anda lulus longjmp()- akan lebih mudah untuk membedakan pengembalian kedua dari yang pertama. Berikut adalah contoh untuk menggambarkan hal ini:

#include <stdio.h>
#include <setjmp.h>

jmp_buf saved_location;
int main(int argc, char **argv)
{
    if (setjmp(saved_location) == 0) {
        printf("We have successfully set up our jump buffer!\n");
    } else {
        printf("We jumped!\n");
        return 0;
    }

    printf("Getting ready to jump!\n");
    longjmp(saved_location, 1);
    printf("This will never execute...\n");
    return 0;
}

Jika kita mengkompilasi dan menjalankan program ini, kita mendapatkan hasil sebagai berikut:

We have successfully set up our jump buffer!
Getting ready to jump!
We jumped!

Wow! Ini seperti pernyataan goto, tetapi dalam kasus ini bahkan dapat digunakan untuk melompat keluar dari suatu fungsi. Ini juga lebih sulit untuk dibaca daripada gotoyang sebenarnya karena ini terlihat seperti pemanggilan fungsi normal. Jika kode Anda digunakan dalam kelimpahan setjmp()dan longjmp(), maka akan sangat sulit untuk dibaca bagi siapa pun (termasuk anda).



Seperti kasusnya goto, umumnya dianjurkan untuk menghindari setjmp()dan longjmp(). Tapi sukagoto, fungsi di atas dapat berguna jika digunakan dengan hemat dan konsisten. Penjadwal harus dapat mengganti konteks, jadi kami akan menggunakan fitur ini secara bertanggung jawab. Yang terpenting, kami akan menggunakan fungsi-fungsi ini dari API kami sehingga pengguna perencana kami tidak harus berurusan dengan kerumitan semacam ini.



Setjmp dan longjmp tidak akan menyimpan stack

True, functions, setjmp()danlongjmp()tidak dimaksudkan untuk mendukung segala jenis lompatan. Mereka dirancang untuk kasus praktis yang sangat spesifik. Bayangkan Anda melakukan beberapa operasi kompleks, seperti membuat permintaan HTTP. Dalam kasus ini, sekumpulan panggilan fungsi yang kompleks akan dilibatkan, dan jika salah satu dari panggilan tersebut gagal, Anda harus mengembalikan kode kesalahan khusus dari masing-masing panggilan tersebut. Kode tersebut akan terlihat seperti dalam daftar berikut, di mana pun Anda memanggil fungsi (mungkin puluhan kali):

int rv = do_function_call();
if (rv != SUCCESS) {
    return rv;
}

Arti setjmp()dan longjmp()apa yang setjmp()membantu untuk mengintai tempat sebelum memulai tugas sangat sulit. Kemudian Anda dapat memusatkan semua penanganan kesalahan Anda di satu tempat:

int rv;
jmp_buf buf;
if ((rv = setjmp(buf)) != 0) {
    /*    */
    return;
}
do_complicated_task(buf, args...);

Jika ada fungsi yang terlibat gagal do_complicated_task(), itu terjadi begitu saja longjmp(buf, error_code). Artinya, setiap fungsi dalam komposisi do_complicated_task()dapat mengasumsikan bahwa pemanggilan fungsi apa pun berhasil, yang berarti Anda tidak dapat meletakkan kode ini untuk menangani kesalahan dalam setiap pemanggilan fungsi (dalam praktiknya hal ini hampir tidak pernah dilakukan, tetapi ini adalah topik untuk artikel terpisah) ...



Ide dasarnya di sini adalah bahwa longjmp()ini hanya memungkinkan Anda untuk keluar dari fungsi yang sangat bertingkat. Anda tidak bisa melompat ke fungsi yang sangat bertingkat yang Anda lompati sebelumnya. Seperti inilah tampilan tumpukan saat Anda keluar dari fungsi. Tanda bintang (*) berarti penunjuk tumpukan di mana ia disimpan setjmp().

  | Stack before longjmp    | Stack after longjmp
      +-------------------------+----------------------------
stack | main()              (*) | main()
grows | do_http_request()       |
down  | send_a_header()         |
 |    | write_bytes()           |
 v    | write()  - fails!       |

Seperti yang Anda lihat, Anda hanya dapat bergerak mundur di stack, jadi tidak ada bahaya kerusakan data. Di sisi lain, bayangkan seperti apa jadinya jika Anda ingin berpindah-pindah tugas. Jika Anda menelepon setjmp()dan kemudian kembali, melakukan beberapa hal lain dan mencoba melanjutkan pekerjaan yang telah Anda lakukan sebelumnya, maka masalah akan muncul:

      | Stack at setjmp() | Stack later      | Stack after longjmp()
      +-------------------+------------------+----------------------
stack | main()            | main()           | main()
grows | do_task_one()     | do_task_two()    | do_stack_two()
down  | subtask()         | subtask()        | subtask()
 |    | foo()             |                  | ???
 v    | bar()         (*) |              (*) | ???               (*)

Penunjuk tumpukan yang disimpan setjmp()akan mengarah ke bingkai tumpukan yang sudah tidak ada lagi dan mungkin telah ditimpa oleh data lain di beberapa titik waktu. Jika kita mencoba untuk longjmp()melompat kembali ke fungsi yang kita kembalikan dengan bantuan , maka hal-hal yang sangat aneh akan dimulai yang mungkin akan menyebabkan runtuhnya seluruh program.



Moral: Jika Anda akan menggunakan setjmp()dan longjmp()beralih di antara tugas-tugas kompleks seperti ini, Anda harus memastikan bahwa setiap tugas memiliki tumpukan terpisah. Dalam kasus ini, masalah benar-benar teratasi, karena ketika longjmp()penunjuk tumpukan di-reset, program itu sendiri akan mengganti tumpukan dengan yang diinginkan, dan tidak ada penghapusan tumpukan yang akan terjadi.

Mari kita tulis API penjadwal

Penyimpangan ini agak panjang, tetapi dipersenjatai dengan apa yang telah kita pelajari, sekarang kita dapat menerapkan aliran ruang pengguna. Untuk memulainya, saya perhatikan bahwa sangat berguna untuk mendesain API sendiri untuk menginisialisasi, membuat, dan memulai utas. Jika kita melakukan ini sebelumnya, kita akan memiliki pemahaman yang jauh lebih baik tentang apa yang sebenarnya kita coba bangun!

void scheduler_init(void);
void scheduler_create_task(void (*func)(void*), void *arg);
void scheduler_run(void);

Fungsi-fungsi ini akan digunakan untuk menginisialisasi penjadwal, menambahkan tugas, dan akhirnya memulai tugas di penjadwal. Setelah diluncurkan, ini scheduler_run()akan berjalan sampai semua tugas selesai. Tugas yang sedang berjalan akan memiliki API berikut:

void scheduler_exit_current_task(void);
void scheduler_relinquish(void);

Fungsi pertama bertanggung jawab untuk keluar dari tugas. Keluar dari tugas juga dimungkinkan saat kembali dari fungsinya, jadi konstruksi ini hanya ada untuk kenyamanan. Fungsi kedua menjelaskan bagaimana utas kami akan memberi tahu penjadwal bahwa tugas lain harus berjalan untuk sementara waktu. Ketika sebuah tugas memanggil scheduler_relinquish(), tugas tersebut dapat ditangguhkan sementara saat tugas lain sedang berjalan; tetapi pada akhirnya fungsi tersebut akan kembali dan tugas pertama dapat dilanjutkan.



Demi contoh konkret, mari pertimbangkan kasus penggunaan hipotetis untuk API kita, yang dengannya kita akan menguji penjadwal:

#include <stdlib.h>
#include <stdio.h>

#include "scheduler.h"

struct tester_args {
    char *name;
    int iters;
};

void tester(void *arg)
{
    int i;
    struct tester_args *ta = (struct tester_args *)arg;
    for (i = 0; i < ta->iters; i++) {
        printf("task %s: %d\n", ta->name, i);
        scheduler_relinquish();
    }
    free(ta);
}

void create_test_task(char *name, int iters)
{
    struct tester_args *ta = malloc(sizeof(*ta));
    ta->name = name;
    ta->iters = iters;
    scheduler_create_task(tester, ta);
}

int main(int argc, char **argv)
{
    scheduler_init();
    create_test_task("first", 5);
    create_test_task("second", 2);
    scheduler_run();
    printf("Finished running all tasks!\n");
    return EXIT_SUCCESS;
}

Dalam contoh ini, kami membuat dua tugas yang menjalankan fungsi yang sama, tetapi mengambil argumen yang berbeda; dengan demikian, implementasinya dapat dilacak secara terpisah. Setiap tugas melakukan sejumlah iterasi. Pada setiap iterasi, ini mencetak pesan dan kemudian membiarkan tugas lain berjalan. Kami berharap untuk melihat sesuatu seperti output dari program:

task first: 0
task second: 0
task first: 1
task second: 1
task first: 2
task first: 3
task first: 4
Finished running all tasks!

Mari kita terapkan API penjadwal

Untuk mengimplementasikan API, kita membutuhkan semacam representasi internal dari tugas tersebut. Jadi, mari kita mulai bisnis; mari kumpulkan bidang yang kita butuhkan:

struct task {
    enum {
        ST_CREATED,
        ST_RUNNING,
        ST_WAITING,
    } status;

    int id;

    jmp_buf buf;

    void (*func)(void*);
    void *arg;

    struct sc_list_head task_list;

    void *stack_bottom;
    void *stack_top;
    int stack_size;
};

Mari kita bahas masing-masing bidang ini secara terpisah. Semua tugas yang dibuat harus dalam keadaan "dibuat" sebelum eksekusi. Saat tugas mulai dijalankan, statusnya "berjalan", dan jika tugas perlu menunggu beberapa operasi asinkron, statusnya "menunggu". Bidang idhanyalah pengenal unik untuk suatu tugas. Ini bufberisi informasi tentang kapan longjmp()tugas akan dijalankan untuk dilanjutkan. Bidang funcdan argditeruskan ke scheduler_create_task()dan diperlukan untuk memulai tugas. Bidang ini task_listdiperlukan untuk menerapkan daftar semua tugas yang tertaut ganda. Bidang stack_bottom, stack_topdan stack_sizesemua milik tumpukan terpisah yang didedikasikan khusus untuk tugas ini. Bawah adalah alamat yang dikembalikan olehmalloc()tetapi "top" adalah penunjuk ke alamat yang berada tepat di atas wilayah tertentu dalam memori. Karena tumpukan x86 tumbuh ke bawah, Anda perlu menyetel penunjuk tumpukan ke sebuah nilai stack_top, bukan stack_bottom.



Dalam kondisi seperti itu, Anda dapat mengimplementasikan fungsi scheduler_create_task():

void scheduler_create_task(void (*func)(void *), void *arg)
{
    static int id = 1;
    struct task *task = malloc(sizeof(*task));
    task->status = ST_CREATED;
    task->func = func;
    task->arg = arg;
    task->id = id++;
    task->stack_size = 16 * 1024;
    task->stack_bottom = malloc(task->stack_size);
    task->stack_top = task->stack_bottom + task->stack_size;
    sc_list_insert_end(&priv.task_list, &task->task_list);
}

Dengan menggunakan static int, kami menjamin bahwa setiap kali fungsi dipanggil, bidang id bertambah, dan ada nomor baru. Segala sesuatu yang lain harus jelas tanpa penjelasan, kecuali untuk fungsi sc_list_insert_end()yang hanya menambah struct taskdaftar global. Daftar global disimpan di dalam struktur kedua yang berisi semua data pribadi penjadwal. Di bawah ini adalah struktur itu sendiri, serta fungsi inisialisasinya:

struct scheduler_private {
    jmp_buf buf;
    struct task *current;
    struct sc_list_head task_list;
} priv;

void scheduler_init(void)
{
    priv.current = NULL;
    sc_list_init(&priv.task_list);
}

Field task_listdigunakan untuk merujuk ke daftar tugas (tidak mengherankan). Bidang currentmenyimpan tugas yang sedang dijalankan (atau null, jika tidak ada tugas seperti itu sekarang). Yang terpenting, field bufakan digunakan untuk melompat ke dalam kode scheduler_run():

enum {
    INIT=0,
    SCHEDULE,
    EXIT_TASK,
};

void scheduler_run(void)
{
    /*     ! */
    switch (setjmp(priv.buf)) {
    case EXIT_TASK:
        scheduler_free_current_task();
    case INIT:
    case SCHEDULE:
        schedule();
        /*       ,    */
        return;
    default:
        fprintf(stderr, "Uh oh, scheduler error\n");
        return;
    }
}

Segera setelah fungsi dipanggil scheduler_run(), kami mengatur buffer setjmp()sehingga kami selalu dapat kembali ke fungsi itu. Pertama kali, 0 (INIT) dikembalikan dan kami segera menelepon schedule(). Selanjutnya, kita dapat meneruskan konstanta SCHEDULE atau EXIT_TASK di longjmp(), yang akan memicu perilaku yang berbeda. Untuk saat ini, abaikan kasus EXIT_TASK dan langsung ke penerapan schedule():

static void schedule(void)
{
    struct task *next = scheduler_choose_task();

    if (!next) {
        return;
    }

    priv.current = next;
    if (next->status == ST_CREATED) {
        /*
         *     .   
         * ,        .
         */
        register void *top = next->stack_top;
        asm volatile(
            "mov %[rs], %%rsp \n"
            : [ rs ] "+r" (top) ::
        );

        /*
         *   
         */
        next->status = ST_RUNNING;
        next->func(next->arg);

        /*
         *     ,    .   – ,   
         *   
         */
        scheduler_exit_current_task();
    } else {
        longjmp(next->buf, 1);
    }
    /*   */
}

Pertama, kita memanggil fungsi bagian dalam untuk memilih tugas berikutnya yang akan dijalankan. Penjadwal ini akan bekerja seperti carousel biasa, jadi ini hanya akan memilih tugas baru dari daftar. Jika fungsi ini mengembalikan NULL, maka kita tidak memiliki tugas lagi untuk dilakukan, dan kita kembali. Jika tidak, kita harus memulai eksekusi tugas (jika dalam status ST_CREATED), atau melanjutkan eksekusinya.



Untuk menjalankan tugas yang dibuat, kami menggunakan instruksi assembly untuk x86_64 untuk menetapkan bidang ke stack_topregister rsp(penunjuk tumpukan). Kemudian kami mengubah status tugas, menjalankan fungsi dan keluar. Catatan: setjmp()baik longjmp()menyimpan dan mengatur ulang stack pointer, jadi di sini kita hanya perlu menggunakan assembler untuk mengubah stack pointer.



Jika tugas sudah dimulai, maka bidang bufharus berisi konteks yang kita butuhkan longjmp()untuk melanjutkan tugas, jadi itulah yang kita lakukan.

Selanjutnya, mari kita lihat fungsi pembantu yang memilih tugas berikutnya untuk dijalankan. Ini adalah inti dari penjadwal, dan seperti yang saya katakan sebelumnya, penjadwal ini bekerja seperti korsel:

static struct task *scheduler_choose_task(void)
{
    struct task *task;

    sc_list_for_each_entry(task, &priv.task_list, task_list, struct task)
    {
        if (task->status == ST_RUNNING || task->status == ST_CREATED) {
            sc_list_remove(&task->task_list);
            sc_list_insert_end(&priv.task_list, &task->task_list);
            return task;
        }
    }

    return NULL;
}

Jika Anda tidak terbiasa dengan implementasi daftar tertaut saya (diambil dari kernel Linux), bukan masalah besar. Fungsi sc_list_for_each_entry()adalah makro yang memungkinkan Anda mengulang semua tugas di daftar tugas. Tugas pertama yang dapat dipilih (tidak dalam status menunggu keputusan) yang kami temukan dihapus dari posisinya saat ini dan dipindahkan ke akhir daftar tugas. Ini memastikan bahwa saat berikutnya kita menjalankan penjadwal, kita akan mendapatkan tugas yang berbeda (jika ada). Kami mengembalikan tugas pertama yang tersedia untuk dipilih, atau NULL jika tidak ada tugas sama sekali.



Terakhir, mari kita lanjutkan ke implementasi scheduler_relinquish()untuk melihat bagaimana tugas dapat menghilangkan dirinya sendiri:

void scheduler_relinquish(void)
{
    if (setjmp(priv.current->buf)) {
        return;
    } else {
        longjmp(priv.buf, SCHEDULE);
    }
}

Ini adalah kasus penggunaan lain untuk fungsi setjmp()di penjadwal kami. Pada dasarnya, opsi ini mungkin tampak sedikit membingungkan. Saat tugas memanggil fungsi ini, kami menggunakannya setjmp()untuk menyimpan konteks saat ini (termasuk penunjuk tumpukan aktual). Kemudian kita menggunakannya longjmp()untuk memasukkan penjadwal (lagi-lagi scheduler_run()) dan melewatkan fungsi JADWAL; jadi kami meminta Anda untuk memberikan tugas baru.



Saat tugas dilanjutkan, fungsi setjmp()kembali dengan nilai bukan nol, dan kami keluar dari tugas apa pun yang mungkin telah kami lakukan sebelumnya!

Terakhir, inilah yang terjadi ketika sebuah tugas keluar (ini dilakukan baik secara eksplisit, dengan memanggil fungsi keluar, atau dengan kembali dari fungsi tugas yang sesuai):

void scheduler_exit_current_task(void)
{
    struct task *task = priv.current;
    sc_list_remove(&task->task_list);
    longjmp(priv.buf, EXIT_TASK);
    /*   */
}

static void scheduler_free_current_task(void)
{
    struct task *task = priv.current;
    priv.current = NULL;
    free(task->stack_bottom);
    free(task);
}

Ini adalah proses dua bagian. Fungsi pertama dikembalikan langsung oleh tugas itu sendiri. Kami menghapus entri yang sesuai dengan yang ini dari daftar tugas, karena tidak akan lagi ditugaskan. Kemudian, menggunakan, longjmp()kami kembali ke fungsi scheduler_run(). Kali ini kami menggunakan EXIT_TASK. Ini adalah cara kami memberi tahu penjadwal apa yang harus dipanggil sebelum menetapkan tugas baru scheduler_free_current_task(). Jika Anda kembali ke deskripsi scheduler_run(), Anda akan melihat bahwa memang seperti inilah fungsinya scheduler_run().



Kami melakukan ini dalam dua langkah, sejak kapanscheduler_exit_current_task(), ini secara aktif menggunakan tumpukan yang terdapat dalam struktur tugas. Jika Anda membebaskan tumpukan dan terus menggunakannya, ada kemungkinan bahwa fungsi tersebut masih dapat mengakses memori tumpukan yang sama dengan yang baru saja kita bebaskan! Untuk memastikan bahwa ini tidak terjadi, kami harus longjmp()kembali ke penjadwal menggunakan tumpukan terpisah dengan bantuan . Kemudian kami dapat dengan aman merilis data yang terkait dengan tugas tersebut.



Jadi kami telah menganalisis seluruh implementasi penjadwal sepenuhnya. Jika kami mencoba mengkompilasinya dengan menambahkan implementasi daftar tertaut saya dan program utama di atasnya, kami akan mendapatkan penjadwal yang berfungsi penuh! Agar tidak mengganggu Anda dengan copy-paste, saya arahkan Anda ke repositori di github , yang berisi semua kode untuk artikel ini.

Apa gunanya pendekatan yang dijelaskan?

Jika Anda sudah membaca sejauh ini, saya rasa tidak perlu meyakinkan Anda bahwa contoh ini menarik. Tapi pada pandangan pertama, ini mungkin tidak terlalu berguna. Bagaimanapun, Anda dapat menggunakan utas "nyata" di C, yang dapat berjalan secara paralel dan tidak harus menunggu satu sama lain sampai salah satu dari mereka memanggil scheduler_relinquish().



Namun, saya melihat ini sebagai titik awal untuk serangkaian implementasi menarik dari fitur berguna. Kita dapat berbicara tentang tugas-tugas I / O yang berat, tentang mengimplementasikan aplikasi asynchronous single-threaded, dengan cara yang sama seperti utilitas async baru di Python bekerja. Generator dan coroutine juga dapat diimplementasikan menggunakan sistem seperti itu. Akhirnya, dengan kerja keras, sistem ini juga dapat berteman dengan utas "nyata" dari sistem operasi untuk menyediakan konkurensi tambahan jika diperlukan. Sebuah proyek yang menarik tersembunyi di balik masing-masing ide ini, dan saya menyarankan Anda untuk mencoba menyelesaikan salah satunya sendiri, pembaca yang budiman.

Itu aman?

Saya pikir itu lebih mungkin tidak daripada ya! Kode perakitan sebaris yang mempengaruhi penunjuk tumpukan tidak dapat dianggap aman. Jangan mengambil risiko menggunakan hal-hal ini dalam produksi, tetapi pastikan untuk mengutak-atik mereka dan penelitian!



Implementasi yang lebih aman dari sistem seperti itu dapat dibangun menggunakan API "non-kontekstual" (lihat man getcontext), yang memungkinkan Anda untuk beralih di antara jenis "aliran" ruang pengguna ini tanpa menyematkan kode assembly. Sayangnya, API semacam itu tidak tercakup oleh standar (telah dihapus dari spesifikasi POSIX). Tapi itu masih bisa digunakan sebagai bagian dari glibc.

Bagaimana mekanisme seperti itu dapat dibuat bergeser?

Penjadwal ini, seperti yang disajikan di sini, hanya berfungsi jika utas secara eksplisit mentransfer kontrol kembali ke penjadwal. Ini tidak baik untuk program umum, misalnya, untuk sistem operasi, karena utas yang dibuat dengan buruk dapat memblokir eksekusi semua yang lain (meskipun ini tidak mencegah penggunaan multitasking kooperatif di MS-DOS!) Saya tidak berpikir bahwa ini membuat multitasking kooperatif jelas buruk; itu semua tergantung aplikasinya.



Saat menggunakan API "di luar konteks" non-standar, sinyal POSIX akan menyimpan konteks kode yang sebelumnya dieksekusi. Dengan menyetel pengatur waktu ke bunyi bip berkala, penjadwal ruang pengguna memang dapat menyediakan versi kerja multitasking preemptive! Ini adalah proyek keren lainnya yang membutuhkan artikel terpisah.