RUSTで学ぶマルチプロセッサプログラミングアート

退屈するたびにCRUST OF RUSTの講座を見ます.信頼に関する授業があまりない現実では、信頼の基礎を知ってから、もっと勉強するために、このような授業はないと思います.ただ、最近の『Lock-Free to Wait-free Simulation in Rust』を聞いたとき、私はこの授業についていけないような気がしました.よく考えてみると、理由は今まで「A in Rust」の授業で、Aという概念について私が以前学んだテーマ、今回のテーマLock-free to Wait-freeは私が深く学んだことのない分野であり、テーマ自体に対する理解が不足しているからです.そこで、パラレルプログラミングを再学習し、「マルチプロセッサプログラミングアート」を学ぶことにしました.現在の計画では週に少なくとも1つの章を勉強するので、せいぜい18週間ぐらいかかります.もちろんその前に終わるように努力します
Art of Multiprogrammingは、すべてのコードをJavaまたはCに構成します.そこで、各章の練習問題と中間サンプルコードをRUSTに整理し、同時にRUSTを勉強したいと思います.このシリーズは章順に並べられ、章の内容を簡単に整理し、練習問題を解く方法で組織されます.シリーズにすべてのコードをアップロードするよりも、コードフラグメントを主とする方が毒性の向上に役立つので、コード自体はhttps://github.com/DonghunLouisLee/Art_of_Multiprocessor_Programming_rustに置く~
現在のシリーズは次のとおりです.

Introduction

.中でも今日はIntroductionおもしろく読んでください~

Theory

マルチプロセッサプログラミングとは、単一スレッドではなくマルチスレッド上でプログラミングを行うことを意味します.現代のハードウェアの発展に伴い、一般的なコンピュータには複数のCPUがあり、プログラミング時にこれらのCPUをどのように効率的に使用するかは性能に大きな影響を及ぼす.本書では,マルチプロセッサ環境においてどのように安全かつ迅速にプログラミングするかを理論と実践の2つの部分に分けて詳細に説明する.第2章から第6章まで理論を議論し,第7章から第18章までは前に学習した理論に基づいて,マルチプロセッサプログラミングのためのアルゴリズムとデータ型の実践を実際に実現することを議論する.本章では,正式に理論部分に入る前に,「単純」で使用する用語をまとめた.

Shared Object and Synchronization
=>複数のスレッドで共通に使用されるデータを表します.これらのスレッドは、同じタスク(同じ関数を処理)を処理したり、まったく異なるタスクを処理したりすることができます.しかし、重要なのは、複数のスレッドを処理するときに、共通のデータにアクセスする必要がある場合があります.この場合、1つの共通のデータを共有オブジェクトと呼び、複数のスレッドがどのように共有オブジェクトにアクセスするかの原則(順序)を同期と呼ぶ.最終的に、マルチプロセッサプログラミングの核心は、この共有オブジェクトをどのように同期するかです.同期を実施するには、次の原則に従います.

Mutual Exclusion:複数のスレッドの共有オブジェクトを同時に変更することはできません.すなわち、1つのスレッドが共有オブジェクトを変更しようとすると、他のスレッドは共有オブジェクトにアクセスできません.

Deadlock-freedom:2つのスレッドが共有オブジェクトにアクセスしようとすると、合計1つのスレッドがアクセスできる必要があります.スレッドが共有オブジェクトにアクセスできない場合は、デッドロックと呼ばれます.

起動-フリー:任意のスレッドが共有オブジェクトにアクセスしようとすると、すべてのスレッドが最終的に共有オブジェクトにアクセスできる必要があります(時間がかかる場合でも).2つのスレッドが共有オブジェクトにアクセスしようとすると、1つのスレッドだけがアクセスを継続し、もう1つのスレッドがアクセスできない場合は、飢餓の自由の原則に違反します.

Waiting:2つ以上のスレッドが共有オブジェクトにアクセスしようとすると、1つのスレッドがアクセス権限を返さずに実行を停止すると、別のスレッドは無限待機状態になります.これを他のスレッドがWaitingしていると表現します.

本書では、複数の同期プロトコルについて説明します.プロトコルの違いを理解するには、これらのプロトコルがどのような原則を満たしているかを理解する必要があります.

Amdahl's law
=>マルチプロセッサは、タスクをどれだけ速く処理できるかを示す式です.

pは、タスク全体で並列に処理できるタスクの割合です.

Nは、使用可能なプロセッサの合計数です.

例をあげましょう私のコンピュータに2つのプロセッサがあり、タスク全体の1/3が並列に処理できる場合、speedu=1/(1-1/3)+(1/3)/2)=6/5です.これは、2つのプロセッサを使用すると、1つのプロセッサを使用するよりもタスクを処理する速度が1.2倍速くなることを意味します.

Exercises

多くの質問がありますが、これは私が符号化に関連する部分についてTrustで書いた答えです.

Exercise1

質問:5人の哲学者は上のテーブルで食事をしたいと思っています.食卓には食べ物を盛る皿が5つあり、皿ごとに箸が1本入っています.哲学者たちが食事をできるようにアルゴリズムを作成します

哲学者たちの位置は指定されている.

哲学者は食事に箸(2本)が必要で、自分の席の左右の箸しか使えない.

哲学者たちはそれぞれ、お腹が空いたときに箸で食べ物を食べることを考えていた.一口食べて箸を元に戻して考え直す

use std::sync::{Arc, Mutex};

use rand::Rng;

//philosopher 0 can only use chopstick 0,1
//philosopher 1 can only use chopstick 1,2
//philosopher 2 can only use chopstick 2,3
//philosopher 3 can only use chopstick 3,4
//philosopher 4 can only use chopstick 4,0
fn main() {
    println!("question1 answer is starting");
    let count = 5; //number of philosophers = number of chopsticks
    let mut chopsticks = vec![];
    for i in 0..count {
        println!("created {}th chopstick", i);
        let chopstick = Arc::new(Mutex::new(true)); //true me
        chopsticks.push(chopstick);
    }
    for i in 0..count {
        let left = i;
        let mut right = i + 1;
        if i == count - 1 {
            right = 0;
        }
        let left_lock = chopsticks.get_mut(left as usize).unwrap().clone();
        let right_lock = chopsticks.get_mut(right as usize).unwrap().clone();
        let _ = std::thread::spawn(move || {
            println!("created philosopher_{:?}", i);
            loop {
                println!("philosopher_{:?} is currently thinking", i);
                let mut rng = rand::thread_rng();
                let ran = rng.gen_range(0..3);
                std::thread::sleep(std::time::Duration::from_secs(ran)); //think
                println!("philosopher_{:?} now wants to eat something", i);
                loop {
                    //first check if philosopher can get both locks
                    let _left = left_lock.lock().unwrap();
                    let _right = right_lock.lock().unwrap();
                    //got both locks
                    //eat
                    println!("philosopher_{:?} is currently eating", i);
                    std::thread::sleep(std::time::Duration::from_secs(1)); //eat
                    break;
                }
                println!("philosopher_{:?} is done eating", i);
            }
        });
    }

    //run a loop so that this program doesn't end
    loop {
        std::thread::sleep(std::time::Duration::from_secs(1)); //eat for 1 second
    }
}

Exercise4

質問:刑務所のP人の囚人に対して、刑務官は以下の質問をしました:成功すればすべて釈放し、失敗すれば死刑です.囚人を釈放できるアルゴリズムを制定する.

今日囚人たちは集まって戦略を議論することができます.しかし、明日からは全員が各部屋に隔離され、コミュニケーションが取れない.

刑務官は「スイッチルーム」を手配し、この部屋にはスイッチしか入れられないスイッチがある.

刑務官は明日から囚人をランダムに選んでこのスイッチルームに入る.囚人はスイッチルームでスイッチ(スイッチやスイッチ)を入れてもいいし、何もしなくてもいいです.

すべての囚人は、いつか少なくとも1回交換部屋を訪問します.

いかなる囚人

も、すべての囚人が少なくとも1回スイッチルームを訪問したと確信すれば、刑務官に自分の考えを伝えることができる.この主張が本当なら全員釈放、偽物なら全員死刑.

use rand::Rng;

fn main() {
    //core of this program is to designate a prisoner("leader") that will count how many prisoners have visited 			the cell
    //for simplicity, we will designate prisoner 1 as the leader
    let mut count = 0;
    let mut switch = true;
    let number_of_prisoners = 100;
    let mut rng = rand::thread_rng();
    while count < number_of_prisoners {
        //first prisoner is chosen
        let ran = rng.gen_range(1..number_of_prisoners + 1);
        println!("prisoner_{} is selected", ran);
        //if chosen prisoner is the leader,
        if ran == 1 {
            if switch == true {
                count += 1;
            }
            switch = false;
        } else {
            if switch == false {
                switch = true;
            }
        }
    }
    println!("this is the final count: {}", count);
}

終わりの時。

このセクションではIntroductionについて簡単に説明します.Execisesの问题は少し多くて、すべて解答することができなくて、もし解答したい问题があるならば、伝言を残して私达に教えてもらって、私达はできるだけ早く解答します.ありがとうございます

Reference

http://cs.ipm.ac.ir/asoc2016/Resources/Theartofmulticore.pdf