Pertanyaan wawancara sinkronisasi multithreading: Temukan n kata yang diberikan utas

Apakah ada cara masalah ini dapat mengambil manfaat dari solusi dengan beberapa utas, bukan satu utas?

Dalam sebuah wawancara, saya diminta untuk memecahkan masalah menggunakan beberapa utas. Tampak bagi saya bahwa banyak utas tidak menguntungkan.

Inilah masalahnya:

Anda diberi paragraf, yang berisi n jumlah kata, Anda diberikan m utas. Yang perlu Anda lakukan adalah, setiap utas harus mencetak satu kata dan memberikan kontrol ke utas berikutnya, dengan cara ini setiap utas akan terus mencetak satu kata, jika ada utas terakhir, ia harus mengaktifkan utas pertama. Pencetakan akan diulang sampai semua kata dicetak dalam paragraf. Akhirnya semua utas harus keluar dengan anggun. Jenis sinkronisasi apa yang akan digunakan?

Saya sangat merasa kami tidak dapat memanfaatkan utas di sini, tetapi percaya pewawancara sedang mencoba mengukur kemampuan sinkronisasi saya. Apakah saya melewatkan sesuatu dalam masalah ini yang akan membuat banyak utas bernilai?

Tidak perlu kode, cukup masukkan beberapa pemikiran. Saya akan menerapkannya sendiri.

Kedengarannya bagi saya seperti mereka memimpin Anda menuju solusi semafor. Semaphores digunakan untuk memberi sinyal utas lain bahwa giliran mereka. Mereka digunakan jauh lebih jarang daripada mutex, yang saya kira adalah mengapa mereka pikir itu pertanyaan wawancara yang bagus. Itu juga mengapa contoh itu tampaknya dibuat-buat.

Pada dasarnya, Anda akan membuat msemaphores. Setiap utas xmenunggu di semaphore xkemudian memposting ke semaphore x+1setelah melakukan tugasnya. Dalam pseudocode:

loop:
    wait(semaphore[x])
    if no more words:
        post(semaphore[(x+1) % m])
        exit
    print word
    increment current word pointer
    post(semaphore[(x+1) % m])

Menurut pendapat saya, ini adalah pertanyaan wawancara yang luar biasa - setidaknya dengan asumsi (1) kandidat diharapkan memiliki pengetahuan yang mendalam tentang threading, dan (2) pewawancara juga memiliki pengetahuan yang mendalam dan menggunakan pertanyaan untuk menyelidiki kandidat. Selalu mungkin pewawancara mencari jawaban spesifik dan sempit, tetapi pewawancara yang kompeten harus mencari yang berikut:

• Kemampuan untuk membedakan konsep abstrak dari implementasi konkret. Saya melemparkan yang satu ini terutama sebagai meta-komentar pada beberapa komentar. Tidak, tidak masuk akal untuk memproses satu daftar kata dengan cara ini. Namun, konsep abstrak dari pipeline operasi, yang dapat menjangkau beberapa mesin dengan kemampuan berbeda, adalah penting.
• Dalam pengalaman saya (hampir 30 tahun aplikasi terdistribusi, multi-proses, dan multi-berulir), mendistribusikan pekerjaan bukanlah bagian yang sulit. Mengumpulkan hasil dan mengoordinasikan proses independen adalah tempat sebagian besar bug threading terjadi (sekali lagi, menurut pengalaman saya). Dengan menyaring masalah ke rantai sederhana, pewawancara dapat melihat seberapa baik kandidat berpikir tentang koordinasi. Selain itu, pewawancara memiliki kesempatan untuk mengajukan segala macam pertanyaan lanjutan, seperti "OK, bagaimana jika setiap utas harus mengirimkan kata-katanya ke utas lain untuk rekonstruksi."
• Apakah kandidat berpikir tentang bagaimana model memori prosesor dapat memengaruhi implementasi? Jika hasil dari satu operasi tidak pernah dihapus dari cache L1, itu bug bahkan jika tidak ada konkurensi yang jelas.
• Apakah kandidat memisahkan threading dari logika aplikasi?

Poin terakhir ini, menurut saya, yang paling penting. Sekali lagi, berdasarkan pengalaman saya, secara eksponensial menjadi lebih sulit untuk men-debug kode berulir jika threading dicampur dengan logika aplikasi (lihat saja semua pertanyaan Swing di atas pada SO untuk contoh). Saya percaya bahwa kode multi-thread terbaik ditulis sebagai kode single-threaded mandiri, dengan handoff yang jelas.

Dengan mengingat hal ini, pendekatan saya adalah memberi masing-masing utas dua antrian: satu untuk input, satu untuk output. Thread memblokir saat membaca antrian input, mengambil kata pertama dari string, dan meneruskan sisa string ke antrian outputnya. Beberapa fitur dari pendekatan ini:

• Kode aplikasi bertanggung jawab untuk membaca antrian, melakukan sesuatu terhadap data, dan menulis antrian. Tidak peduli apakah multi-threaded atau tidak, atau apakah antrian adalah antrian di memori pada satu mesin atau antrian berbasis TCP antara mesin yang hidup di sisi berlawanan dari dunia.
• Karena kode aplikasi ditulis seolah-olah single-threaded, itu dapat diuji secara deterministik tanpa perlu banyak perancah.
• Selama fase eksekusi, kode aplikasi memiliki string yang sedang diproses. Tidak perlu peduli tentang sinkronisasi dengan utas yang menjalankan secara bersamaan.

Yang mengatakan, masih ada banyak daerah abu-abu yang dapat diselidiki oleh pewawancara yang kompeten:

• "OK, tapi kami ingin melihat pengetahuanmu tentang primitif konkurensi; bisakah kamu menerapkan antrian pemblokiran?" Jawaban pertama Anda, tentu saja, adalah bahwa Anda akan menggunakan antrian pemblokiran yang sudah dibangun sebelumnya dari platform pilihan Anda. Namun, jika Anda memahami utas, Anda dapat membuat implementasi antrian di bawah selusin baris kode, menggunakan sinkronisasi apa pun yang primitif dukung platform Anda.
• "Bagaimana jika satu langkah dalam proses itu membutuhkan waktu yang sangat lama?" Anda harus berpikir tentang apakah Anda ingin antrian output terbatas atau tidak terbatas, bagaimana Anda dapat menangani kesalahan, dan efek pada throughput keseluruhan jika Anda memiliki penundaan.
• Bagaimana cara efisien enqueue string sumber. Tidak perlu masalah jika Anda berurusan dengan antrian di memori, tetapi bisa menjadi masalah jika Anda berpindah antar mesin. Anda juga dapat menjelajahi pembungkus read-only di atas array byte yang mendasarinya.

Akhirnya, jika Anda memiliki pengalaman dalam pemrograman bersamaan, Anda mungkin berbicara tentang beberapa kerangka kerja (misalnya, Akka untuk Java / Scala) yang sudah mengikuti model ini.

Pertanyaan wawancara terkadang adalah pertanyaan tipuan, yang dimaksudkan untuk membuat Anda berpikir tentang masalah yang Anda coba selesaikan. Mengajukan pertanyaan tentang pertanyaan adalah bagian integral dari pendekatan masalah apa pun , apakah itu di dunia nyata atau dalam sebuah wawancara. Ada sejumlah video yang beredar di internet tentang cara mendekati pertanyaan dalam wawancara teknis (lihat khususnya untuk Google dan mungkin Microsoft).

"Coba jawab, dan keluarlah dari sana .."

Mendekati wawancara dengan pola pikir ini akan membuat Anda membom wawancara apa pun untuk perusahaan apa pun yang layak bekerja.

Jika Anda tidak berpikir bahwa Anda mendapatkan banyak (jika ada sesuatu dari threading), katakan itu. Katakan kepada mereka mengapa Anda tidak berpikir ada manfaatnya. Berdiskusi dengan mereka. Wawancara teknis dimaksudkan sebagai platform diskusi terbuka. Anda mungkin akhirnya belajar sesuatu tentang bagaimana itu bisa bermanfaat. Jangan hanya terus maju mencoba menerapkan sesuatu yang diwawancarai pewawancara Anda.

• Pertama-tama tokenize paragraf dengan pembatas yang sesuai dan tambahkan kata-kata ke Antrian.

• Buat N jumlah utas dan simpan di kumpulan utas.

• Iterasi di atas kumpulan utas dan mulai utas dan tunggu
  utas bergabung. Dan mulai utas berikutnya setelah utas pertama berakhir dan seterusnya.

• Setiap Thread seharusnya hanya mengumpulkan antrian dan mencetaknya.

• Setelah semua utas digunakan dalam kumpulan utas, mulailah dari awal pool.

Seperti yang Anda katakan, saya tidak berpikir skenario ini sangat bermanfaat, jika sama sekali dari threading. Kemungkinan besar lebih lambat dari implementasi threaded tunggal.

Namun, jawaban saya adalah meminta setiap utas dalam satu lingkaran ketat mencoba mengakses kunci yang mengontrol akses ke indeks susunan kata. Setiap utas mengambil kunci, mendapatkan indeks, mendapatkan kata yang sesuai dari array, mencetaknya, menambah indeks lalu melepaskan kunci. Thread keluar saat indeks berada di akhir array.

Sesuatu seperti ini:

while(true)
{
    lock(index)
    {
        if(index >= array.length())
          break;
        Console.WriteLine(array[index]);
        index++;
    }
}

Saya pikir ini harus mencapai satu utas setelah persyaratan lain, tetapi pemesanan utas tidak dijamin. Saya penasaran mendengar solusi lain juga.

Gunakan API tunggu / sinyal kondisi untuk mengatasi masalah ini.

Katakanlah utas pertama mengambil 1 kata dan sementara itu semua utas lainnya sedang menunggu sinyal. 1 utas mencetak kata 1 dan menghasilkan sinyal ke utas berikutnya dan kemudian utas 2 mencetak kata kedua dan menghasilkan sinyal ke utas ke-3 dan seterusnya.

#include <iostream>
#include <fstream>
#include <pthread.h>
#include <signal.h>
pthread_cond_t cond[5] = {PTHREAD_COND_INITIALIZER,};
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

using namespace std;

string gstr;

void* thread1(void*)
{
    do {
    pthread_mutex_lock(&mutex);
    pthread_cond_wait(&cond[0],&mutex);
    cout <<"thread1 :"<<gstr<<endl;
    pthread_mutex_unlock(&mutex);
    }while(1);
}

void* thread2(void*)
{
    do{
    pthread_mutex_lock(&mutex);
    pthread_cond_wait(&cond[1],&mutex);
    cout <<"thread2 :"<<gstr<<endl;
    pthread_mutex_unlock(&mutex);
    }while(1);
}

void* thread3(void*)
{
    do{
    pthread_mutex_lock(&mutex);
    pthread_cond_wait(&cond[2],&mutex);
    cout <<"thread3 :"<<gstr<<endl;
    pthread_mutex_unlock(&mutex);
    }while(1);
}

void* thread4(void*)
{
    do{
    pthread_mutex_lock(&mutex);
    pthread_cond_wait(&cond[3],&mutex);
    cout <<"thread4 :"<<gstr<<endl;
    pthread_mutex_unlock(&mutex);
    }while(1);
}

void* thread5(void*)
{
    do{
    pthread_mutex_lock(&mutex);
    pthread_cond_wait(&cond[4],&mutex);
    cout <<"thread5 :"<<gstr<<endl;
    pthread_mutex_unlock(&mutex);
    }while(1);
}

int main()
{
    pthread_t t[5];
    void* (*fun[5])(void*);
    fun[0]=thread1;
    fun[1]=thread2;
    fun[2]=thread3;
    fun[3]=thread4;
    fun[4]=thread5;

    for (int i =0 ; i < 5; ++i)
    {
        pthread_create(&t[i],NULL,fun[i],NULL);
    }
    ifstream in;
    in.open("paragraph.txt");
    int i=0;
    while(in >> gstr)
    {

        pthread_cond_signal(&cond[i++]);
        if(i == 5)
            i=0;
        usleep(10);
    }
    for (int i =0 ; i < 5; ++i)
    {
        int ret = pthread_cancel(t[i]);
        if(ret != 0)
            perror("pthread_cancel:");
        else
            cout <<"canceled\n";
    }
    pthread_exit(NULL);
}

[Istilah yang digunakan di sini mungkin khusus untuk utas POSIX]

Seharusnya dimungkinkan untuk menggunakan mutasi FIFO juga untuk menyelesaikan masalah ini.

Tempat menggunakan:

Asumsikan dua utas T1 dan T2 sedang mencoba untuk mengeksekusi bagian kritis. Keduanya tidak memiliki banyak pekerjaan di luar bagian penting ini dan menahan kunci untuk waktu yang baik. Jadi, T1 dapat mengunci, menjalankan dan membuka kunci dan memberi sinyal T2 untuk bangun. Tapi sebelum T2 bisa bangun dan mendapatkan kunci, T1 meminta kunci dan mengeksekusi. Dengan cara ini, T2 mungkin harus menunggu sangat lama sebelum benar-benar mendapatkan kunci atau mungkin tidak.

Bagaimana cara kerjanya / Bagaimana menerapkan:

Miliki mutex untuk dikunci. Initialize Thread Specific Data (TSD) untuk setiap utas ke simpul yang berisi utas id dan semaphore. Juga, memiliki dua variabel - dimiliki (BENAR atau SALAH atau -1), pemilik (id utas pemilik). Selain itu, buat antrian pelayan dan penunjuk pelayan. Terakhir menunjuk ke simpul terakhir dalam antrian pelayan.

operasi kunci:

node = get_thread_specific_data(node_key);
lock(mutex);
    if(!owned)
    {
        owned = true;
        owner = self;
        return success;
    }

    node->next = nullptr;
    if(waiters_queue == null) waiters_queue = node;
    else waiters_last->next = node;

    waiters_last = node;
unlock(mutex);
sem_wait(node->semaphore);

lock(mutex);
    if(owned != -1) abort();
    owned = true;
    owner = self;
    waiters_queue = waiters_queue->next;
 unlock(mutex);

buka kunci operasi:

lock(mutex);
    owner = null;
    if(waiters_queue == null)
    {
        owned = false;
        return success;
    }
    owned = -1;
    sem_post(waiters_queue->semaphore);
unlock(mutex);

Pertanyaan menarik. Ini solusi saya di Java menggunakan SynchronousQueue untuk membuat saluran pertemuan di antara utas:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.concurrent.SynchronousQueue;

public class FindNWordsGivenMThreads {

    private static final int NUMBER_OF_WORDS = 100;
    private static final int NUMBER_OF_THREADS = 5;
    private static final Stack<String> POISON_PILL = new Stack<String>();

    public static void main(String[] args) throws Exception {
        new FindNWordsGivenMThreads().run();
    }

    private void run() throws Exception {
        final Stack<String> words = loadWords();
        SynchronousQueue<Stack<String>> init = new SynchronousQueue<Stack<String>>();
        createProcessors(init);
        init.put(words);
    }

    private void createProcessors(SynchronousQueue<Stack<String>> init) {
        List<Processor> processors = new ArrayList<Processor>();

        for (int i = 0; i < NUMBER_OF_THREADS; i++) {

            SynchronousQueue in;
            SynchronousQueue out;

            if (i == 0) {
                in = init;
            } else {
                in = processors.get(i - 1).getOut();
            }

            if (i == (NUMBER_OF_THREADS - 1)) {
                out = init;
            } else {
                out = new SynchronousQueue();
            }

            Processor processor = new Processor("Thread-" + i, in, out);
            processors.add(processor);
            processor.start();

        }

    }

    class Processor extends Thread {

        private SynchronousQueue<Stack<String>> in;
        private SynchronousQueue<Stack<String>> out;

        Processor(String name, SynchronousQueue in, SynchronousQueue out) {
            super(name);
            this.in = in;
            this.out = out;
        }

        @Override
        public void run() {

            while (true) {

                Stack<String> stack = null;
                try {
                    stack = in.take();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }

                if (stack.empty() || stack == POISON_PILL) {
                    System.out.println(Thread.currentThread().getName() + " Done!");
                    out.offer(POISON_PILL);
                    break;
                }

                System.out.println(Thread.currentThread().getName() + " " + stack.pop());
                out.offer(stack);
            }
        }

        public SynchronousQueue getOut() {
            return out;
        }
    }

    private Stack<String> loadWords() throws Exception {

        Stack<String> words = new Stack<String>();

        BufferedReader reader = new BufferedReader(new FileReader(new File("/usr/share/dict/words")));
        String line;
        while ((line = reader.readLine()) != null) {
            words.push(line);
            if (words.size() == NUMBER_OF_WORDS) {
                break;
            }
        }
        return words;
    }
}

Saya akan mengatakan bahwa pertanyaan semacam ini sangat sulit dijawab, karena pertanyaan itu menanyakan cara terbaik untuk melakukan sesuatu yang benar-benar bodoh. Otak saya tidak berfungsi seperti itu. Tidak dapat menemukan solusi untuk pertanyaan bodoh. Otak saya akan segera mengatakan bahwa dalam kondisi ini, menggunakan beberapa utas tidak ada gunanya, jadi saya akan menggunakan satu utas.

Saya kemudian akan meminta mereka untuk memberikan pertanyaan dunia nyata tentang threading, atau untuk memberi saya contoh dunia nyata dari beberapa threading serius.