Opteron Dual Core: il lancio tra alcune settimane

[xeal]

Originariamente inviato da cdimauro
A mio avviso bloccare le linee di cache non è generalmente conveniente, perché:[...]

Infatti intendevo dire che può essere più conveniente "buttare a mare" anche tutto il contenuto della cache e ripristinarlo quando necessario, piuttosto che impelagarsi in algoritmi vari per ottimizzarne l'uso per tutti i processi (ammesso che sia possibile), aumentando l'overhead di context switch (ho posizionato male quella frase nel discorso )

A mio avviso il problema della "sistemazione" dei processi/thread non dovrebbe essere delegato al s.o., ma all'applicazione, nel caso in cui questa abbia la possibilità di gestire più CPU per smistare loro il suo lavoro.

Questo perché chi ha scritto l'applicazione è la persona più indicata per stabilire, a seconda del sistema su cui gira (SMP "classico", SMP multi core, SMP multi core con HT, SMP multicore NUMA), in che modo da smistare il lavoro per trarne il maggior beneficio.

Invece un s.o. / scheduler ha una visione "statica", prestabilita da chi l'ha scritto, e le scelte che fa non sono valide e "ottimali" per tutti i casi.

Tutto questo IMHO, chiaramente..

Da un certo punto di vista hai perfettamente ragione. Però temo che si rischierebbe di produrre dei conflitti con gli altri processi, ragion per cui lo scheduler è comunque necessario, e se avesse pochi poteri rispetto alle scelte operate a monte da chi ha sviluppato l'applicazione SMP si potrebbero verificare situazioni poco auspicabili, non so, magari un gruppo di thread si aspetta di essere eseguito su di un solo processore (con 4 core) ma per ragioni contingenti (per evitare starvation di altri processi) perde l'uso del suo core, e a motivo delle scelte fatte a monte dal programmatore (e dello spostamento del problema dallo scheduling alla gestione diretta da parte dell'applicazione) rimane in attesa invece di essere spostato su di un altro processore (anch'esso multicore), cosa che ne peggiorerebbe le prestazioni rispetto a quanto previsto dal progettista, ma sarebbe meglio dell'attendere inutilmente, tanto l'efficienza del raggruppamento sarebbe saltata comunque per motivi contingenti non previsti a priori. In questo senso, se è vero che lo sviluppatore ha una visione più "dinamica" (nel senso di più aderente alle caratteristiche e necessità effettive) della sua applicazione, è anche vero che non può conoscere a priori il contesto in cui il programma verrà eseguito, mentre lo scheduler del s.o., operando a runtime, ha una visione "statica" e generica di tutti i software in esecuzione, ma conosce meglio la dinamica contingente del sistema, ragion per cui, in un certo senso, forse, delegare il compito di smistare il lavoro alle varie cpu (e in genere la gestione delle risorse) alle singole applicazioni potrebbe essere un po' estrema, o comunque estremizzabile all'atto pratico, fino a renderla analoga a quella operata da itanium nei confronti dell'ordinamento delle istruzioni effettuato dal compilatore, il quale conosce a priori benissimo (e sicuramente meglio di qualunque unità per il riordino) le caratteristiche del codice che sta producendo, ma non ha idea di quale sia il contesto reale nel quale il codice verrà eseguito, rendendo di fatto preferibile, come tu stesso mi insegni, la logica out-of-order, specie se affiancata a un codice ben ordinato, da adeguare con poco sforzo al contesto (poi, magari, intendevi qualcosa di diverso e ho frainteso io ).

Si potrebbe cercare una via di mezzo, ovvero creare un threading model che preveda (anche come opzionale) delle indicazioni, nella struttura dei thread, circa le caratteristiche da tenere in considerazione nella loro schedulazione, come la tendenza a compiere frequenti accessi in memoria, oppure frequenti operazioni di i/o o lunghe operazioni sui dati caricati mediante prefetching, fino ai raggruppamenti migliori per sfruttare al meglio un certo tipo di sistema (ed eventualmente alla possibilità di richiedere l'esecuzione forzata su un solo core/cpu fisica/logica per ottenere un software adattativo al sistema e al tipo di licenza scelta dall'utente, non ricordo se parlavi tu o qualcun altro di una soluzione del genere al problema delle licenze per il multi core); in questo modo lo scheduler avrebbe una cognizione migliore e dell'applicazine singola, e del contesto generale, potendo gestire in maniera ottimale (o comunque meglio ottimizzata) l'allocazione delle risorse (le cpu in particolare) ai vari processi/thread.

Imho, ovviamente

[cionci]

Su Windows e anche sugli ultimi Linux si può già assegnare un thread ad un determinato processore...e non solo...in XP a 64 bit ci sono sia le API per identificare i processori logici (HT) e che il supporto all'architettura NUMA per calcolarsi la composizione dei vari nodi...

[cdimauro]

Originariamente inviato da cionci

In effetti non avevo pensato al fatto che anche la cache trasferisce a blocchi...quindi il doppio canale viene praticamente usato sempre

Esatto: a prescindere da ciò che fa il processore...

Comunque di fatto è come avere due canali separati...perchè supponendo che entrambe le cache vogliano leggere + o - contemporaneamente un blocco la somma dei tempi dei trasferimenti di entrambi i blocchi è pari a quello che si avrebbe supponendo di assegnare un canale ad ogni cache.. Anzi...in questo modo una cache finisce prima... Quindi probabilmente l'implementazione più efficiente è questa...

Secondo me no: due canali completamente indipendenti al più posso lavorare esattamente come due canali "unificati", ma non è vero il contrario.

[cdimauro]

Originariamente inviato da xeal

Infatti intendevo dire che può essere più conveniente "buttare a mare" anche tutto il contenuto della cache e ripristinarlo quando necessario, piuttosto che impelagarsi in algoritmi vari per ottimizzarne l'uso per tutti i processi (ammesso che sia possibile), aumentando l'overhead di context switch (ho posizionato male quella frase nel discorso )

Può anche essere che abbia capito male io...
Comunque adesso è chiaro, e sono perfettamente d'accordo.

Da un certo punto di vista hai perfettamente ragione. Però temo che si rischierebbe di produrre dei conflitti con gli altri processi, ragion per cui lo scheduler è comunque necessario, e se avesse pochi poteri rispetto alle scelte operate a monte da chi ha sviluppato l'applicazione SMP si potrebbero verificare situazioni poco auspicabili, non so, magari un gruppo di thread si aspetta di essere eseguito su di un solo processore (con 4 core) ma per ragioni contingenti (per evitare starvation di altri processi) perde l'uso del suo core, e a motivo delle scelte fatte a monte dal programmatore (e dello spostamento del problema dallo scheduling alla gestione diretta da parte dell'applicazione) rimane in attesa invece di essere spostato su di un altro processore (anch'esso multicore), cosa che ne peggiorerebbe le prestazioni rispetto a quanto previsto dal progettista, ma sarebbe meglio dell'attendere inutilmente, tanto l'efficienza del raggruppamento sarebbe saltata comunque per motivi contingenti non previsti a priori.

Ma infatti questa è una cosa che non dovrebbe succedere nel modello di cui parlavo: se ho deciso di piazzare un thread nella CPU logica #3, deve rimanere lì. Se il s.o. s'intromette in questa scelta, è chiaro che non ha più senso nemmeno pensare di sprecare risorse per questo modello...

In questo senso, se è vero che lo sviluppatore ha una visione più "dinamica" (nel senso di più aderente alle caratteristiche e necessità effettive) della sua applicazione, è anche vero che non può conoscere a priori il contesto in cui il programma verrà eseguito, mentre lo scheduler del s.o., operando a runtime, ha una visione "statica" e generica di tutti i software in esecuzione, ma conosce meglio la dinamica contingente del sistema, ragion per cui, in un certo senso, forse, delegare il compito di smistare il lavoro alle varie cpu (e in genere la gestione delle risorse) alle singole applicazioni potrebbe essere un po' estrema, o comunque estremizzabile all'atto pratico, fino a renderla analoga a quella operata da itanium nei confronti dell'ordinamento delle istruzioni effettuato dal compilatore, il quale conosce a priori benissimo (e sicuramente meglio di qualunque unità per il riordino) le caratteristiche del codice che sta producendo, ma non ha idea di quale sia il contesto reale nel quale il codice verrà eseguito, rendendo di fatto preferibile, come tu stesso mi insegni, la logica out-of-order, specie se affiancata a un codice ben ordinato, da adeguare con poco sforzo al contesto (poi, magari, intendevi qualcosa di diverso e ho frainteso io ).

Indubbiamente. Per questo motivo, se il s.o. è in grado di avere informazioni "dinamiche" utili all'attribuzione di un thread a un core piuttosto che a un altro, è bene che le renda disponibili come API alle applicazioni, per metterle quanto meno nelle stesse condizioni, e permettere di operare la scelta migliore, grazie alla "conoscenza intrinseca" che hanno del problema da risolvere...

Si potrebbe cercare una via di mezzo, ovvero creare un threading model che preveda (anche come opzionale) delle indicazioni, nella struttura dei thread, circa le caratteristiche da tenere in considerazione nella loro schedulazione, come la tendenza a compiere frequenti accessi in memoria, oppure frequenti operazioni di i/o o lunghe operazioni sui dati caricati mediante prefetching, fino ai raggruppamenti migliori per sfruttare al meglio un certo tipo di sistema (ed eventualmente alla possibilità di richiedere l'esecuzione forzata su un solo core/cpu fisica/logica per ottenere un software adattativo al sistema e al tipo di licenza scelta dall'utente, non ricordo se parlavi tu o qualcun altro di una soluzione del genere al problema delle licenze per il multi core);

Ne parlavo io...

in questo modo lo scheduler avrebbe una cognizione migliore e dell'applicazine singola, e del contesto generale, potendo gestire in maniera ottimale (o comunque meglio ottimizzata) l'allocazione delle risorse (le cpu in particolare) ai vari processi/thread.

Imho, ovviamente

Così sposteresti troppa complessità sullo scheduler, che verrebbe troppo penalizzato nel caso generico. Invece se è l'applicazione a gestire questa "complessità", perché lei e solo lei ha particolari esigenze, sarebbe meglio. Sempre IMHO.

[cdimauro]

Originariamente inviato da cionci

Su Windows e anche sugli ultimi Linux si può già assegnare un thread ad un determinato processore...e non solo...in XP a 64 bit ci sono sia le API per identificare i processori logici (HT) e che il supporto all'architettura NUMA per calcolarsi la composizione dei vari nodi...

Ottimo. Non ero a conoscenza di questa caratteristica: grazie!

[xeal]

Originariamente inviato da cdimauro
Ma infatti questa è una cosa che non dovrebbe succedere nel modello di cui parlavo: se ho deciso di piazzare un thread nella CPU logica #3, deve rimanere lì. Se il s.o. s'intromette in questa scelta, è chiaro che non ha più senso nemmeno pensare di sprecare risorse per questo modello...

Temo però che lasciare i processi/thread completamente liberi di spartirsi le risorse possa dare luogo a conflitti difficilmente prevedibili prima dell'esecuzione: l'assegnazione di quel thread alla cpu logica #3 potrebbe essere la scelta migliore in condizioni "ideali" di massima autonomia e libertà d'azione, ma in un particolare contesto d'esecuzione potrebbero esserci, ad esempio, più thread (relativi a processi diversi) che abbiano scelto di usare la #3, perchè magari hanno bisogno di cooperare con i "fratelli" assegnati alle cpu logiche vicine, per cui devono spartirsi le stesse risorse di calcolo, mentre potrebbe essersi liberata nel frattempo la cpu logica x sul processore fisico y, o l'intero processore y, per cui potrebbe essere preferibile, in un dato istante, far migrare uno o più thread/processi su quel processore al fine di mantenere elevato il throughput di sistema. Quindi, più che dire "voglio lavorare su quel core" potrebbe essere interessante mettere il processo in condizioni di dire "voglio/non voglio lavorare vicino a questi altri thread", per ottimizzare il lavoro contemporaneo di un gruppo di thread su una data cpu multicore/multithreaded. Inoltre potrebbe essere necessario interrompere temporaneamente l'esecuzione di un thread/processo per consentire a un altro di lavorare, evitandone la starvation, su una data cpu/core, mentre gli alti previsti per una esecuzione contemporanea (e assegnati "manualmente" ad altre cpu) potrebbero continuare il loro lavoro senza interruzioni (in quel frangente), per cui la scelta aprioristica delle cpu cui assegnare i thread, senza intervento ulteriore del s.o., potrebbe non essere la migliore possibile, a meno di voler privilegiare una schedulazione a medio o lungo termine (ovvero tornare a una schedulazione a job, ma potrebbe non essere sempre la scelta più efficiente, specie per processi interattivi), oppure un modello di multitasking cooperativo, con richieste esplicite di sleep (et similia) da parte dei processi stessi per consentire agli altri di lavorare, senza possibilità di prelazione da parte del so, ma in questo modo temo che al più si avrebbe la scelta migliore del momento in cui sospendere l'esecuzione di un singolo processo, ma non dell'intero gruppo di processi (poichè un singolo thread/processo sa come gestire al meglio le sue operazioni, ma non come coordinarsi con processi di cui ignora l'esistenza o le caratteristiche), e inoltre potrebbero sorgere dei problemi: il processo potrebbe non richiedere affatto la sospensione (ci si affiderebbe alla buona volontà del programmatore) oppure andare in crash, "allooparsi", e in entrambi i casi un qualche intervento da parte del sistema operativo potrebbe rendersi comunque utile o necessario, se non inevitabile. Per questo pensavo di escogitare un modello intermedio, per dare ai processi l'opportunità di gestire le risorse disponibili nel modo più efficiente (studiato a priori) e al s.o. la possibilità di intervenire (alla meno peggio o alla "quasi meglio", a seconda del compromesso tra leggerezza dell'intervento ed efficienza scelto) laddove il contesto di esecuzione rendesse preferibile arrangiare diversamente l'assegnazione delle risorse.

Indubbiamente. Per questo motivo, se il s.o. è in grado di avere informazioni "dinamiche" utili all'attribuzione di un thread a un core piuttosto che a un altro, è bene che le renda disponibili come API alle applicazioni, per metterle quanto meno nelle stesse condizioni, e permettere di operare la scelta migliore, grazie alla "conoscenza intrinseca" che hanno del problema da risolvere.

Ma in questo modo non si sposta la complessità dello scheduler a ciascun processo? E non ci si affida alla "bontà" del codice eseguito? Cioè, ciascun processo dovrebbe passare una parte del tempo in esecuzione a decidere se è meglio restare nella coda di un certo core o spostarsi altrove e se conviene riordinare le code, secondo le proprie esigenze? Non c'è il rischio che i vari processi si incasinino gli uni con gli altri, sprecando tempo a cercare di creare una situazione generale che il processo successivo scombina appena può?

Io pensavo alla possibilità che fossero i thread a fornire al s.o. informazioni "dinamiche" sulla loro esecuzione, dicendo "su questo sistema, con queste risorse, prevedo di eseguire un tot di operazioni sui dati precaricati nella cache, un tot di accessi alla memoria e un tot di operazioni di input output, e preferirei lavorare con questi thread in esecuzione sullo stesso processore multicore e questi altri nella stessa coda di esecuzione", in modo che il sistema operativo cerchi di rispettare per quanto possibile la gestione prevista dall'applicazione, ripristinandola appena possibile, e avendo contemporaneamente a disposizione delle informazioni per calcolare il giusto "mix" di processi da allocare sulla stessa cpu multicore, presi anche da altre applicazioni.

Così sposteresti troppa complessità sullo scheduler, che verrebbe troppo penalizzato nel caso generico. Invece se è l'applicazione a gestire questa "complessità", perché lei e solo lei ha particolari esigenze, sarebbe meglio. Sempre IMHO.

Beh, si può sempre studiare il problema e cercare un compromesso soddisfacente. Se fosse troppo complicato, ci si potrebbe limitare ad assegnare le risorse ai processi secondo lo schema suggerito dai processi stessi finchè applicabile, per alterare tale schema quando indispensabile (anche nel modo più "classico" ) e quindi ripristinarlo appena possibile. Comunque pensavo ad un sistema che, in fin dei conti, potrebbe non essere troppo complesso. In genere il sistema operativo deve avere una qualche conoscenza delle caratteristiche del sistema per poterle gestire al meglio, per cui, parlando sempre di sistemi con più cpu e più core fisici e/o logici per ciascuna cpu, si potrebbe pensare di definire dei parametri per stabilire se un certo thread da assegnare a un core è compatibile con i thread assegnati al core vicino, pensando cioè (per certi versi) alla cpu multicore come se fosse formata da un unico macrocore e ai thread in esecuzione come facenti parte di un un macrothread, un unico blocco avente però una sua duttilità e fluidità, ovvero con i thread "interni" sostituibili con altri aventi caratteristiche simili (giudicate mediante i parametri di poc'anzi). I parametri potrebbero non essere altro che dei pesi attribuiti a determinate caratteristiche e calcolati dallo sviluppatore (eventualmente mediante profiling o comunque tool di sviluppo appositamente pensati) e comunicati al sistema operativo, mediante le sue api, al momento della creazione. A questo punto il sistema operativo potrebbe decidere o di assegnare le risorse nello stesso modo in cui vengono richieste dall'applicazione, oppure, se ciò non portasse a una buona distribuzione del carico di lavoro in relazione agli altri processi presenti, di alterare la distribuzione dei macrothread alle macrocpu o la composizione stessa dei macrothread (che diventerebbero eterogenei rispetto all'applicazione di appartenenza dei thread "interni" ) sommando i pesi di ciascun parametro con i pesi corrispondenti negli altri thread e calcolando, ad esempio, la media degli scarti rispetto al valore considerato ottimale per un dato parametro (ovvero sommo algebricamente tutti i pesi di un parametro - positivi - e il valore di riferimento - negativo - e faccio la media, eventualemnte azzerando i risultati negativi, su questo si può meditare), per determinare il gruppo di thread/processi da eseguire contemporaneamente su una certa cpu secondo un qualche algoritmo "first fit" (per limitare i calcoli): fissato il primo processo, si procede ad accostare gli altri via via (evitando permutazioni inutili) calcolando la media pesata dei parametri e scegliendo il gruppo che non supera il valore ideale oltre una certa soglia, o quello che supara la soglia per il valore più piccolo. Naturalmente questa dovrebbe essere la strategia generale dell'algoritmo, ma ai fatti, per quanto possibile, la meno frequente (nella forma più genereica che prevede la scelta di tutti i thread): la prima applicazione servita dal sistema operativo riceve le risorse così come le chiede, e così anche le successive, finchè non si ha uno sbilanciamento del carico su qualche cpu; a questo punto si procede allo spostamento di uno o più macrothread sulla cpu che lavora meno, finchè non diventa necessario intervenire all'interno dei macrothread (ad esempio perchè uno o più thread entrano in uno stato di wait e devono lasciare il posto ad altri (molto) prima che termini il time slice); quando questo accade, si sceglie il thread (o i thread) "migliore" per la sostituzione (o quello meno peggiore, il primo buono) tenendo conto delle caratteristiche di quelli ancora in esecuzione, tenendo conto anche di un termine che impedisca di scavalcare troppe volte uno stesso processo. Per quanto riguarda la visione del sistema per macrocpu e macrothread, li immagino come raggruppamenti logici, ovvero ciascun core continuerebbe ad avere una sua propria coda di processi da gestire (quasi) indipendentemente dalle altre, senza un impatto significativo sulla struttura dati usata (potrebbe continuare ad essere una lista, un vettore, una lista di vettori, o qualunque altra cosa già utilizzata; potrebbe essere utile comunque un qualche collegamento tra i "record" relativi ai processi di pari "profondità" nelle code, ma credo non sia strettamente necessario). Nel loro insieme le code relative a una stessa macrocpu potrebbero essere pensate come una sorta di matrice (con una o più righe incomplete) con p (numero di processi/thread in una coda) righe e c (numero di core logici/fisici della macrocpu, ovvero dimensione del macrothread logico) colonne: a intervalli prefissati (più lunghi di un normale time slice) alcuni macrothread potrebbero venire integralmente spostati su altre macrocpu (ed eventualmente essere spezzati o aggregati per adeguarsi a un diverso numero di core, ovvero una diversa dimensione della matrice dei processi, quindi riordinati) per bilanciare il carico. Al naturale scadere di un time slice contemporaneo per tutti i core di una macrocpu si avrebbe un normale context switch parallelo, per cui non verrebbe in alcun modo alterata la composizione già decisa dei macrothread (nessun overhead in questo caso); qualora uno dei thread in esecuzione non potesse proseguire (attende un'operazione di I/O o lo sblocco di un semaforo sui dati di cui necessita) si procederebbe alla sua sostituzione con uno prelevato dalla stessa coda, si determinerebbe (o potrebbe determinarsi, a seconda delle scelte) un'asincronia nei context switch, e in questo caso si dovrebbe scegliere il/i thread sostituto/i ad ogni context switch, ma si potrebbe ovviare con una regola di maggioranza, presupponendo che l'asincronia sia causata dalla minoranza dei thread interni al macrothread (i pesi dovrebbero essere ponderati per ottenere una situazione del genere o una sospensione "prematura" praticamente contemporanea di tutti i thread - se ne potrebbe tenere conto e sostituirli uno ad uno con quelli del macrothread successivo): la maggior parte dei thread porterebbe a termine il proprio quanto contemporaneamente e verrebbe sostituito in blocco, mentre i (pochi) thread, causa dell'asincronia, richiederebbero la ricerca di un sostituto (l'overhead nel context switch interesserebbe pochi core alla volta, non influendo troppo sulle prestazioni del sistema, e trattandosi di un numero limitato di thread da sostituire è probabile che verrebbero scelti tra quelli immediatamente successivi, ripristinando, pur con uno "sfasamento", il macrothread - alla lunga però l'overhead rischierebbe di interessare tutti i core della macrocpu, ma trattandosi di poche somme su dati già noti potrebbe avere un costo tuttosommato basso; inoltre, il termine di un time slice potrebbe implicare l'invio di un "segnale" - messaggio o interrupt vero e proprio - agli altri core, in modo che la ricerca, eventualmente in corso, di un sostituto (o, se conveniente, anche un context switch non completo) si interrompa se il totale dei core in fase di switch è sufficiente da giustificare la sostituzione immediata con i processi successivi nelle code; si può pensare anche ad un'attesa di pochi(ssimi) millisecondi per tentare di risincronizzare i macrothred (o una parte cospicua dei thread interni)). Si potrebbe anche pensare di schedulare, a intervalli più lunghi, per non incidere pesantemente sul throughput di sistema, un riordino globale dei thread nei macrothread della "matrice" associata a una macrocpu, stavolta effettuando spostamenti tra le colonne (le code dei core) e non più solo tra le righe in una stessa colonna, anche con un algoritmo di tipo best fit, o, meglio, bilanciando i risultati. Questo riordino "globale" si potrebbe fare in modo parziale, a blocchi, eventualmente si potrebbero sfruttare gli stati di idle di qualche core (eventualmente provocati da una diversa lunghezza nelle code dei processi all'interno della stessa macrocpu, partendo da un "livellamento" delle code e fermandosi al termine dei quanti negli altri core, per mantenere la sincronia), oppure (ma non necessariamente in alternativa, si potrebbero fare entrambe le cose), sospendendo temporaneamente l'attività della macrocpu per effettuare il riordino globale (credo che l'algoritmo di ricerca dei mix migliori bilanciati, ovvero omogenei, sempre sulla base della media pesata dei parametri, o operazioni semplici similari, si possa parallelizzare senza troppe difficoltà ), ad intervalli se necessario ancora più lunghi, per pochi istanti, facendo ripartire in maniera sincrona il "cronometraggio" dell'esecuzione (risincronizzando temporalmente l'esecuzione dei thread interni al macrothread). Infine, per far si che nel corso dei vari riordini questo algoritmo di scheduling tenda "spontaneamente" a ricostituire l'ordine d'esecuzione dei thread scelto da una certa applicazione, si potrebbe tener conto, tra i parametri, dell'appartenenza o meno dei thread a uno stesso programma e della "predilezione" degli stessi a lavorare in parallelo e sulla stessa macrocpu; per questo potrebbe bastare tener traccia in ciascun thread dell'id di uno degli altri thread facenti parte del gruppo originario - ad esempio il primo conosce l'id del secondo, il secondo quello del terzo... - e pesare in modo opportuno la presenza dei thread "richiesti" nel macrothread che si sta creando (sempre però con scelta di tipo first fit, per non appesantire i calcoli, salvo nei riordini globali).

Credo che un algoritmo del genere, ben implementato, potrebbe essere più semplice e meno oneroso di quanto io non sia riuscito a descrivere . Tutto, ancora, IMHO (di questo passo questa sarà la discussione con più imho di tutti i tempi )

[cdimauro]

ARGH! Ma dove lo trovi il tempo per scrivere questi mallopponi?

Le considerazioni sono ottime, non c'è che dire, ma a mio avviso bisogna puntare l'attenzione sullo scheduler, che è l'elemento su cui alla fine ruota tutta la discussione.

Questo "programma" del s.o. è molto delicato, viene richiamato parecchie volte al secondo (100 volte al secondo su molti s.o.), per cui dev'essere eseguito quanto più velocemente possibile. Infatti sullo scheduler e gli algoritmi di selezione / assegnazione dei task da eseguire c'è parecchia letteratura, ma la tendenza dal punto di vista implementativo è sempre quella perdere il minor tempo possibile; Linux, se non ricordo male, ha motivo di vanto nel suo algoritmo di scheduling che impiega un tempo "costante" (O(1)) per la selezione del task da eseguire.

Un algoritmo che permetta di bilanciare il carico del sistema in base all'attuale situazione in cui versa E alle caratteristiche intrinseche del software sarebbe decisamente troppo pesante, IMHO. Inoltre l'impiego di matrici per memorizzare lo stato e la "relazione" fra i vari thread non è dispendioso in termini di memoria occupata (qualche MB, al più: poca roba rispetto alla quantità di memoria presente anche in PC abbastanza vecchi), ma lo è sicuramente per le operazioni che riguardano questa struttura (inserimento, cancellazione, "spostamento" / aggiornamento dei dati, ecc.).

Per questo motivo pensavo che sarebbe meglio delegare all'applicazione e non allo scheduler il compito di smistare i thread in base al carico attuale del sistema e alle esigenze intrinseche della stessa. Se ci pensiamo bene, il fatto che un programma abbia particolari esigenze rispetto a tutti gli altri, è proprio affar suo: normalmente le politiche di gestione di task vanno più che bene, e finora lo hanno dimostrato.

E' chiaro che la situazione ideale / migliore in assoluto non esiste. Come programmatori quello su cui puntiamo prevalentemente l'attenzione è il caso medio, senza ovviamente trascurare il caso peggiore e il caso migliore: peggiorare il caso medio per migliorare il caso peggiore può andare bene se oggettivamente l'applicazione da far girare è "vitale", ossia quella che deve in assoluto girare meglio anche a spesa di tutte le altre, ma ciò non è sempre vero, anzi.

Chiaramente il tutto sempre IMHO...

[cionci]

Io pensavo alla possibilità che fossero i thread a fornire al s.o. informazioni "dinamiche" sulla loro esecuzione, dicendo "su questo sistema, con queste risorse, prevedo di eseguire un tot di operazioni sui dati precaricati nella cache, un tot di accessi alla memoria e un tot di operazioni di input output, e preferirei lavorare con questi thread in esecuzione sullo stesso processore multicore e questi altri nella stessa coda di esecuzione", in modo che il sistema operativo cerchi di rispettare per quanto possibile la gestione prevista dall'applicazione, ripristinandola appena possibile, e avendo contemporaneamente a disposizione delle informazioni per calcolare il giusto "mix" di processi da allocare sulla stessa cpu multicore, presi anche da altre applicazioni

Come avevo scritto addietro...questo è già possibile... Ci sono API che permettono di selezionare il processore di default di un processo...oppure si da allo scheduler la possibilità di scegliere fra un pool di processi...

[xeal]

Originariamente inviato da cdimauro
ARGH! Ma dove lo trovi il tempo per scrivere questi mallopponi?

Ehm, io già mi sento in colpa perchè non riesco a concentrarmi abbastanza su quello che dovrei fare, adesso non mettertici pure tu! Diciamo che la questione mi ha appassionato...

Questo "programma" del s.o. è molto delicato, viene richiamato parecchie volte al secondo (100 volte al secondo su molti s.o.), per cui dev'essere eseguito quanto più velocemente possibile.

Cioè ogni 10 ms? Credevo meno spesso... Suppongo che gli scheduler attuali impieghino circa 1 ms o meno per effettuare il context switch, onde evitare un degrado delle prestazioni (devo confessare che sull'argomento non so tantissimo, specie sulle implementazioni, se non che un time slice troppo breve rispetto al tempo di intervento dello scheduler peggiora le prestazioni, mentre uno troppo lungo darebbe risultati simili a FCFS, quindi sarebbe poco produttivo, e che un "costo" del 10% rispetto al tempo concesso alle applicazioni dovrebbe essere accettabile).

Un algoritmo che permetta di bilanciare il carico del sistema in base all'attuale situazione in cui versa E alle caratteristiche intrinseche del software sarebbe decisamente troppo pesante, IMHO.

Beh, la mia era solo un'idea: mica ho scritto l'algoritmo e ne ho calcolato la complessità computazionale!

Comunque forse non sono riuscito a esprimere bene quello che avevo in mente (mi stupirei del contrario, visto che mentre scrivevo cercavo di chiarirmi le idee ), che potrebbe essere più semplice di quanto abbia scritto Provo a chiarirlo un po' meglio (sperando di non ripetermi), tanto per confrontarci ancora un po' sull'argomento che, come dicevo, mi ha un po' intrigato. Innanzi tutto, le caratteristiche intrinseche del software il sistema operativo dovrebbe conoscerle e non conoscerle: le conosce perchè il software le comunica appena entra in esecuzione o quando crea un nuovo thread/sottoprocesso (quindi sono dati precalcolati da chi scrive l'applicazione, dei parametri in più da fornire al so passandoli alla funzione "crea_tread"), non le conosce più approfonditamente di così perchè non fa nessun calcolo per valutarle (questa parte della complessità verrebbe "scaricata" sul programmatore, oppure su un linguaggio/ide pensato appositamente per agevolare la suddivisione del lavoro in parallelo fra thread che sfruttano al meglio un dato sistema - ovviamente la parallelizzazione degli algoritmi la fa il programmatore, i tool di sviluppo interverrebbero sull'eseguibile, come un compilatore che produce sezioni diverse per sistemi diversi, ma questi sono altri discorsi, sto divangando ).

Per non complicare troppo il lavoro dello scheduler pensavo a dei parametri interi da sommare e mediare (una media "pesata" degli scarti: sommo tutti i valori di un parametro in tutti i thread che raggruppo e sottraggo il valore "ideale", ripeto per gli altri e calcolo la media confrontandola con un altro valore "ideale", sempre precalcolato per un dato sistema/cpu multicore), trattandosi di somme (in alternativa si potrebbe pensare a qualche operazione logica su maschere di bit) non dovrebbero richiedere un tempo troppo grande (la divisione finale si potrebbe sostituire con uno shift - i risultati finali dovrebbero sempre essere positivi - scegliendo un numero pari di parametri), soprattutto considerando il tempo poi necessario per caricare i dati nella cache (ove necessario, per dei thread magari c'è meno lavoro da fare in questo senso).

La complessità dovrebbe riguardare quindi più il numero di thread da esaminare e le combinazioni da valutare, ma a questo si può ovviare (credo) in qualche modo: innanzitutto, presumo che l'applicazione crei i thread e soprattutto i gruppi di thread con parametri ben bilanciati (inizialmente non ne modifico né composizione, né la destinazione, se non strettamente necessario per bilanciare il carico tra le varie cpu; tutt'al più si potrebbe valutare, progettando l'algoritmo, se non valga la pena di riordinare il gruppo destinato a una cpu multicore per far sì che i thread per i quali si prevede la possibilità che sospendano il lavoro "prima del tempo" finiscano nelle stesse code, ma non credo sia strettamente necessario farlo): se il gruppo (che chiamavo macrothread) è ben bilanciato mi aspetto che pochi thread, tra quelli destinati ai core di una stessa cpu (macrocpu), restino in attesa per un'operazione di input/output o per un semaforo sui dati, gli altri completerebbero il quanto contemporaneamente e verrebbero sostituiti (essendo la maggioranza) direttamente dai successori (un nuovo gruppo ben bilanciato: mi serve trovare il sostituto solo dell'unico/dei pochi thread che hanno "smesso" di lavorare prima degli altri; mi sorge un dubbio: in genere che si fa in questi casi? ciascun core/cpu ha un proprio timer per i processi? e per cpu multicore? e per core logici? l'esecuzione attualmente diventerebbe "asincrona" o si sostituirebbe il processo in stato di attesa in modo da risincronizzarsi con gli altri time slice paralleli? comunque sia, per il momento suppongo che si continui in maniera asincrona).

Supponiamo che l'esecuzione diventi asincrona (cioè risultino non contemporanei gli interventi dello scheduler sulle varie code) per un solo core (alla volta): il problema di trovare il raggruppamento migliore si ridurrebbe (considerando la "disottimizzazione" rispetto al calcolo su tutto il gruppo trascurabile, essendo gli altri thread ben accoppiati) a cercare il miglior sostituto nel gruppo ancora in esecuzione (ovvero il primo che si avvicina al valore ideale -> first fit), e la ricerca si potrebbe condurre su un numero limitato di processi successivi (considerando la lista come circolare), diciamo 4-5 (indicativamente, si dovrebbe valutare il numero in maniera opportuna, progettando l'algoritmo), sia per ridurre i calcoli, sia per evitare starvation - a tal fine i processi in coda avrebbero, tra i parametri caratterizzanti, un numero incrementato e decrementato opportunamente ogni volta che venissero "promossi" (scavalcando gli altri) o "retrocessi" (scavalcati a loro volta): quando si raggiunge il numero massimo previsto il processo non può più essere scavalcato, se non ce n'è uno migliore prima tocca a lui - si potrebbe anche valutare l'opportunità di spendere qualche nanosecondo per verificare quanto tempo manca al termine del time slice "generale" (sempre che, a lungo andare, ne rimanga uno), per decidere se cercare il sostituto nel gruppo attuale (manca molto tempo -> il processo sostituto lavorerà per la maggior parte del suo quanto insieme al gruppo in esecuzione), oppure richiamare direttamente il thread/processo successivo (quasi non c'è asincronia, per cui lavorerà quasi per tutto il quanto insieme ai suoi "fratelli" predestinati); è possibile che si finisca comunque per scegliere il processo successivo, dipenderebbe dalla soglia scelta per considerare accettabile la media degli scarti dalla combinazione migliore e da quanto ben bilanciato era, nel complesso, il gruppo in cui si è verificata l'asincronia.

In questo modo, se i processi che determinano l'asincronia si trovano tutti nella stessa coda (o nelle stesse code), il degrado dovuto alla scelta del successore migliore (che potrebbe anche essere trascurabile) riguarderebbe solo uno/pochi core, e risulterebbe poco rilevante per il sistema nel suo complesso; diversamente, a lungo andare si potrebbe generare un'asincronia generale, per cui l'algoritmo di ricerca del successore sarebbe applicato in ogni context switch, ma, anche in questo caso, potrebbe risultare poco oneroso ed essere eseguito senza troppe preoccupazioni, oppure si potrebbe pensare di risincronizzare tutto in qualche modo, ad esempio sospendendo l'esecuzione dei processi (o semplicemente lasciando che terminino il proprio quanto senza sostituirli per alcuni istanti) e approfittando dell'interruzione per riordinare tutte le code cercando i raggruppamenti migliori (ma si potrebbe decidere di non "sprecare" tempo né per i riordini, né per risincronizzare l'esecuzione dei gruppi, o di effettuare il riordino in altro modo). Questo calcolo sarebbe sicuramente oneroso, ma, nel caso in cui lo si ritenesse utile/necessario (considero il riordino globale un punto la cui opportunità si può sicuramente sindacare, come tutto il resto, naturalmente) potrebbe essere schedulato a intervalli sufficientemente lunghi da non incidere troppo: ad esempio (sparo dei numeri a caso) se per riordinare tutto (parlo della singola cpu multicore) occorresse 1 secondo e il riordino venisse operato ogni 10 secondi, inciderebbe per 1 ms in più ad ogni intervento dello scheduler (nell'ipotesi di 100 interventi al secondo), anzi, ancora meno, in proporzione al numero di core presenti sulla cpu oggetto del riordino (a meno che le altre non restino inoperose nel frattempo, cosa probabile o necessaria, temo); la durata del riordino (quindi il suo peso) risulterebbe minore se poi l'algoritmo adottato (per determinare le combinazioni possibili e calcolare il grado di bilanciamento - con la media di prima - per ciascun raggruppamento) risultasse parallelizzabile e/o venisse eseguito sfruttando qualche stato di idle dei core (ma si potrebbe decidere di non riordinare affatto le intere code).

Inoltre l'impiego di matrici per memorizzare lo stato e la "relazione" fra i vari thread non è dispendioso in termini di memoria occupata (qualche MB, al più: poca roba rispetto alla quantità di memoria presente anche in PC abbastanza vecchi), ma lo è sicuramente per le operazioni che riguardano questa struttura (inserimento, cancellazione, "spostamento" / aggiornamento dei dati, ecc.).

Qui ho combinato un po' di casino io nel malloppone di prima, parlando di matrici e di spostamento di processi tra righe e colonne

In realtà pensavo ad una visione logica, virtuale delle code (implementate mediante liste o qualunque cosa si ritenesse opportuna - qui mi viene in mente ai discorsi che faceva fek tempo fa sull'opportunità di usare dei vettori per velocizzare un eventuale riordino dei processi; in ogni caso, non mi pongo il problema di scegliere una certa struttura dati, e soprattutto non voglio modificare le scelte attuali, mi basta partire da una visione logica "a matrice"), al fine di bilanciare opportunamente (in modo in fondo del tutto simile a quanto fatto oggi, credo) il carico di lavoro tra i core di una stessa cpu e le migrazioni da una (macro)cpu all'altra: considero le code di processi di una cpu multicore come le colonne di una matrice, cercando di mantenerle per quanto possibile della stessa "lunghezza", se possibile pari alla lunghezza delle code sugli altri processori (multicore o single core), per far sì che tutti i core lavorino. Mi spiego meglio (anche perchè così sembra che io stia scoprendo l'uovo di Colombo... e in parte è così ): sulla mia cpu multicore (diciamo, quad-core) ho un certo numero di thread (uguale) per ciascun core (così che le code, nel loro insieme, possano essere immaginate come una matrice); a un certo punto devo creare un nuovo task con due soli thread e li accodo alle prime due code (o nelle code richieste; c'è poco da fare); subito dopo arriva la richiesta per altri due thread, che richiedono entrambi (o uno di essi) di finire in una della coda degli altri due, ma invece di "accontentarli" li raggruppo insieme, in modo da ricostruire la struttura "a matrice", ovvero, con ogni nuovo (gruppo) thread "spaiato" che arriva riempio i buchi e bilancio il carico (potrei anche spezzare un gruppo completo e bilanciato, onde spostare sempre i buchi in coda, nell'ultima riga della matrice virtuale); a questo punto, appena arriva un gruppo di thread di dimensione "idonea", tento un riordino (limitato agli ultimi gruppi) per bilanciare il lavoro in base ai parametri d'esecuzione dichiarati; poichè uso una logica "first fit", appena ottengo un risultato soddisfaciente mi fermo. Analogamente, se devo bilanciare la ripartizione del carico su più cpu (multicore o non) nel sistema (supponendo di avere nel sistema cpu con un diverso numero di core), sposterò un numero congruo di thread, cioè, all'atto pratico, sposterò dalla cpu di partenza una intera riga della sua matrice virtuale dei processi (o più di una, a seconda delle esigenze), ma non dei processi di uno stesso gruppo (se lascio un gruppo incompleto potrei sprecare del tempo per un inutile intervento dello scheduler, ritrovandomi comunque con dei core privi di carico); le righe (macrothread) spostate verrebbero spezzate o accorpate, a seconda del numero di core presenti sulla cpu di destinazione, e in tal caso si effettuerebbe un riordino dei processi in base alle caratteristiche d'esecuzione (sempre mediante la media pesata di prima).

Sostanzialmente, ad ogni suo intervento lo scheduler "ragionerebbe" per gruppi di esecuzione parallela, in "orizzontale", oltre che in "verticale" per gestire ciascuna coda, pur cercando di non impiegare troppo tempo per farlo.

Per questo motivo pensavo che sarebbe meglio delegare all'applicazione e non allo scheduler il compito di smistare i thread in base al carico attuale del sistema e alle esigenze intrinseche della stessa. Se ci pensiamo bene, il fatto che un programma abbia particolari esigenze rispetto a tutti gli altri, è proprio affar suo: normalmente le politiche di gestione di task vanno più che bene, e finora lo hanno dimostrato

Capisco il tuo punto di vista e le ragioni di fondo del tuo ragionamento, però non riesco a togliermi dalla testa il sospetto che i processi rischierebbero di rompersi le uova nel paniere a vicenda (magari mi sbaglio ). Comunque, in maggior lavoro necessario per gestire lo smistamento dei thread verrebbe si sgravato allo scheduler, ma comunque effettuato dall'applicazione (che vedrebbe comunque ridursi il tempo a sua disposizione per l'esecuzione), anche se è probabile che solo poche applicazioni sceglierebbero di farlo e solo in particolari circostanze, per cui il costo complessivo sarebbe minore rispetto a un costante overhead di lavoro per lo scheduler, credo che tu intenda questo.

[quoe]E' chiaro che la situazione ideale / migliore in assoluto non esiste. Come programmatori quello su cui puntiamo prevalentemente l'attenzione è il caso medio, senza ovviamente trascurare il caso peggiore e il caso migliore: peggiorare il caso medio per migliorare il caso peggiore può andare bene se oggettivamente l'applicazione da far girare è "vitale", ossia quella che deve in assoluto girare meglio anche a spesa di tutte le altre, ma ciò non è sempre vero, anzi.[/quote]

Vero, però se con qualche microsecondo in più di calcoli dello scheduler ad ogni intervento si riuscisse in qualche modo a ottimizzare lo sfruttamento di una cpu multicore non sarebbe male. Poi, ripeto, la mia era solo un'idea, magari interessante e da valutare, magari no.

Ecco: ho scritto un altro malloppone, non sono riuscito a contenerlo... Comunque mi sembra che manchi qualcosa...
Ah, già: IMHO
(ma non erano vietati dal regolamento i vari imo, condo, erzo... )

[xeal]

Originariamente inviato da cionci
Come avevo scritto addietro...questo è già possibile... Ci sono API che permettono di selezionare il processore di default di un processo...oppure si da allo scheduler la possibilità di scegliere fra un pool di processi...

Ma il pool di processi riguarda una singola coda (ovvero un certo core) oppure può riguardare tutti i core? Come dicevo prima, questo tipo di operazione è "orizzontale" o "verticale"? Io pensavo a una qualche modifica delle strategie attuali in senso "orizzontale", tenendo conto, cioè, dell'esecuzione contemporanea di più thread, in modo da bilanciare il carico sulle cpu multicore, visto che, stando ai progetti attuali, sembrano destinate a sostituire le single core, ovvero il multicore sembra dover diventare la "struttura" base di una cpu fisica, per cui mi domandavo se non fosse possibile studiare un'algoritmo di scheduling che, ad esempio, eviti che troppi thread/processi eseguiti contemporaneamente si contendano le stesse risorse a disposizione della singola (macro)cpu, come un eventuale MCH integrato. Poi, può darsi che qualcosa del genere si faccia già... e in tal caso, evita di rispondermi: "è già possibile", tanto non ammetterò mai di aver scoperto l'acqua calda a costo di fare sfacciatamente del

Scherzi a parte, se sto scoprendo l'acqua calda ditemelo, così evito di spremermi le meningi...

Bye.

[cionci]

Intendevo "pool di processori" per un dato thread...
Guarda l'API SetThreadAffinityMask (mi sembra)...

Come ti dicevo...questa strategia (anzi, qualsiasi strategia) è già applicabile dal lato utente in Win XP 64 e Win Server 2003... E' già possibile identificare la composizione georafica della struttura NUMA...e di conseguenza sapere quali core stanno sulla stessa CPU...

Se questi SO usano particolari strategie di scheduling non lo so...ma suppongo che mettendo a disposizione quelle API il kernel stesso si crei una struttura statica che contiene lo schema fisico... Per verificare non resta che fare delle prove

[cdimauro]

Come avevo già scritto, anche cercando di limitare al minimo il numero di thread da esaminare, si perderebbe comunque troppo tempo: impossibile pensare anche soltanto di avvicinarsi a un O(1) dello scheduler di Linux, ad esempio.

Peggio ancora pensando di utilizzare un qualche algoritmo di ordinamento (a meno di non fare delle assunzioni e utilizzare altri algoritmo di ordinamento non basati sulla selezione, ma che comunque richiedono un tempo lineare per essere eseguiti).

Utilizzare delle liste anziché delle matrici comporterebbe non pochi problemi (attualmente Linux utilizza un vettore per memorizzare gli ID dei processi, di dimensione fissa), e aumenterebbe il tempo di esecuzione nel caso si volesse utilizzare un algoritmo di ordinamento.

Quanto al timer, nel sistema ce n'è soltanto uno che viene usato per segnalare il context-switch, e viene assegnato / usato da un solo processore, che fa da "master"...

A mio avviso l'idea di spostare la complessità dell'algoritmo dallo scheduler all'applicazione "particolare" consente di risolvere il problema, non pesando assolutamente sullo scheduler, e quindi su tutto il sistema: è una cosa non da poco.
Basti pensare al numero di processi / thread che girano su un sistema moderno: sono davvero tanti, e praticamente nessuno ha esigenze particolari. Se lo scheduler dovesse pensare a risolvere il problema del bilanciamento, per quanto bene fosse implementato l'algoritmo, "peserebbe" comunque su tutti i processi / thread, anche quando non sarebbe assolutamente necessario (che il caso più frequente).

[xeal]

x cionci: si, la funzione è quella, ho dato un'occhiata sul sito msdn . Sostanzialmente si scelgono i processori sui quali si desidera eseguire un certo thread, in maniera vincolante, però è sconsigliato farlo perchè potrebbe peggiorare le prestazioni del sistema (impedendo allo scheduler di spostare il thread su un altro processore per bilanciare il carico), a meno che non serva per sfruttare l'architettura NUMA: in tal caso potrebbe servire o ad assegnare i thread che condividono risorse su uno stesso nodo o a distribuirli su più nodi.

Oltre a pool di processori si possono creare pool di thread, ma non ho ben capito a cosa serva: sembrerebbe simile alla strategia master-worker o ad agenda (o meglio, la base per tali architetture) o forse serve a notificare più rapidamente (mediante dei thread che fanno da monitor) la possibilità di uscire dallo stato di wait a dei thread che si contendono delle risorse, un po' come succede chiamando notifyAll() in Java, ma non ho capito bene (anche perchè non ho approfondito le api per la sincronizzazione)...

Credo comunque che potrebbe essere interessante avere qualche "grado di libertà" in più potendo indicare quali e quanti thread si vorrebbero far eseguire in parallelo (ragionando, come dicevo, in "orizzontale") senza doverli vincolare a un certo processore (per non "interferire" con il bilanciamento del carico fatto dal processore, poi, magari, le api ci sono e non le ho notate io ; pensandoci, forse un risultato parzialmente simile si può ottenere con SetThreadIdealProcessor, ma sarebbe comunque diverso). Sarebbe interessante poter specificare (in maniera vincolante) quanti thread al massimo si vogliono far eseguire in parallelo, ovvero quanti processori si vogliono far usare al massimo da un'applicazione, per ottenere un comportamento diverso in base al tipo di licenza a prescindere dal numero max di cpu presenti sul sistema (l'idea di Cesare) senza vincolarne l'esecuzione su cpu specifiche (laddove non necessario).

x cidimauro: come già detto, era solo un'idea, che mi sembra sempre meno fattibile, perchè a prescindere dal tempo d'esecuzione dello scheduler, sarebbe un caso limite l'avere a disposizione il "giusto" numero di thread con certe caratteristiche (non troppi che accedono spesso in memoria, non troppi che eseguono I/O, non troppi che devono sospendere l'esecuzione prima del context switch successivo...) da assegnare a un certo processore multicore. Comunque, speravo che effettuare qualche somma e una divisione, da ripetere al più un numero limitato di volte (e fisso, non variabile con il numero totale di thread) non comportasse un overhead significativo. Per l'ordinamento, pensavo di ottenere un risultato accettabile spalmando il tempo d'esecuzione su un numero sufficientemente grande di context switch (ovvero, eseguendolo una volta ogni n context switch). Non butterei via la possibilità di spostare i thread a blocchi, ovvero poter decidere quali evitare (se possibile) di schedulare sullo stesso processore, senza doverli vincolare a cpu specifiche, se non strettamente necessario.

Utilizzare delle liste anziché delle matrici comporterebbe non pochi problemi (attualmente Linux utilizza un vettore per memorizzare gli ID dei processi, di dimensione fissa), e aumenterebbe il tempo di esecuzione nel caso si volesse utilizzare un algoritmo di ordinamento.

Sei sicuro che Linux usi un vettore? Ricordavo che in una discussione (mi pare si parlasse dei pro e dei contro dell'uso del C o del C++ per scrivere un kernel, ma eravamo fortemente OT) si era detto (ilsensine? mi pare che inizialmente discutesse lui con fek della cosa) che linux usasse delle liste per ciascun processore, con interventi "programmati" per spostare un processo da una coda all'altra, riuscendo comunque a garantire ai processi accesso alle risorse in un tempo O(1). Forse però ricordo male... Comunque intendevo che, ai fini dell'algoritmo che pensavo, la struttura dati effettiva sarebbe stata secondaria, da non modificare rispetto alle scelte già fatte, volevo solo mettere in evidenza un modo di vedere i thread per "gruppi di esecuzione parallela", che poi sia fattibile o meno è un'altro discorso .

Quanto al timer, nel sistema ce n'è soltanto uno che viene usato per segnalare il context-switch, e viene assegnato / usato da un solo processore, che fa da "master"...

Thank you very much In tal caso, se un processo sospende l'esecuzione prima del termine del time slice come si procede? Come si coordina tutto?

A mio avviso l'idea di spostare la complessità dell'algoritmo dallo scheduler all'applicazione "particolare" consente di risolvere il problema, non pesando assolutamente sullo scheduler, e quindi su tutto il sistema: è una cosa non da poco.
Basti pensare al numero di processi / thread che girano su un sistema moderno: sono davvero tanti, e praticamente nessuno ha esigenze particolari. Se lo scheduler dovesse pensare a risolvere il problema del bilanciamento, per quanto bene fosse implementato l'algoritmo, "peserebbe" comunque su tutti i processi / thread, anche quando non sarebbe assolutamente necessario (che il caso più frequente).

Avevo intuito che intendevi questo. Per le api che ho visto, forse qualcosa del genere in Windows si può fare con i fiber, anche se in tal caso lo scheduling sarebbe totalmente a carico dell'applicazione e comunque la libertà d'azione limitata all'esecuzione del thread che li genera, senza possibilità di scegliere i processori. Forse, utilizzandoli con un thread genitore con un'elevata priorità si otterrebbe qualcosa di simile a quello che intendi, sempre che convenga farlo in questo modo, oltretutto mi pare di aver capito che non siano particolarmente consigliati, salvo fare il porting di qualche applicazione pensata per gestire autonomamente i propri thread.

Ciao

[cdimauro]

Originariamente inviato da xeal

come già detto, era solo un'idea, che mi sembra sempre meno fattibile, perchè a prescindere dal tempo d'esecuzione dello scheduler, sarebbe un caso limite l'avere a disposizione il "giusto" numero di thread con certe caratteristiche (non troppi che accedono spesso in memoria, non troppi che eseguono I/O, non troppi che devono sospendere l'esecuzione prima del context switch successivo...) da assegnare a un certo processore multicore.

Infatti il problema della scheduling in generale è NP-Completo, se la memoria non m'inganna: funzionano bene soluzioni semplici e ben collaudate, ma all'aumentare delle variabili da tenere in considerazione la complessità aumenta inesorabilmente...

Comunque, speravo che effettuare qualche somma e una divisione, da ripetere al più un numero limitato di volte (e fisso, non variabile con il numero totale di thread) non comportasse un overhead significativo.

Qualche somma e divisione non sono un problema, se effettivamente sono limitate in numero e non dipendono dalla quantità di thread: in questo caso rientrebbero come costante nel calcolo della complessità dell'algoritmo di scheduling.

Per l'ordinamento, pensavo di ottenere un risultato accettabile spalmando il tempo d'esecuzione su un numero sufficientemente grande di context switch (ovvero, eseguendolo una volta ogni n context switch).

Sarebbe comunque troppo lento: O(n log2 n) è troppo. Infatti la situazione sarebbe la seguente:
1) farlo ogni n context switch comporterebbe un tempo di calcolo (ammortizzato) comunque troppo elevato (O(log2(n)));
2) farlo ogni n log2 n context switch comporterebbe un tempo di calcolo (ammortizzato) interessante (O(1)).

Per fare un esempio, supponendo di avere n = 1000 processi & thread e che il context switch avvenga 100 volte al secondo, l'operazione verrebbe effettuata:
1) ogni 10 secondi circa (ma al prezzo di O(10) per ogni context switch);
2) ogni 100 secondi circa (al prezzo di O(1) per ogni context switch).

Nel primo caso, l'aggiornamento ogni 10 secondi potrebbe essere un buon compromesso, ma il prezzo da pagare sarebbe abbastanza salato in termini computazionali.
Nel secondo caso computazionalmente saremmo davanti al caso migliore, ma in 100 secondi le condizioni del sistema potrebbero essere cambiate troppe (anche in 10 secondi, ma "reagirebbe" più velocemente).

Non butterei via la possibilità di spostare i thread a blocchi, ovvero poter decidere quali evitare (se possibile) di schedulare sullo stesso processore, senza doverli vincolare a cpu specifiche, se non strettamente necessario.

E' sicuramente interessante. Bisognerebbe valutare quanto inciderebbe sullo scheduler.

Sei sicuro che Linux usi un vettore? Ricordavo che in una discussione (mi pare si parlasse dei pro e dei contro dell'uso del C o del C++ per scrivere un kernel, ma eravamo fortemente OT) si era detto (ilsensine? mi pare che inizialmente discutesse lui con fek della cosa) che linux usasse delle liste per ciascun processore, con interventi "programmati" per spostare un processo da una coda all'altra, riuscendo comunque a garantire ai processi accesso alle risorse in un tempo O(1). Forse però ricordo male...

Il thread era lo stesso, ma abbiamo dei ricordi diametralmente opposti. Vediamo se interviene ilsensine a chiarire la questione...

Comunque intendevo che, ai fini dell'algoritmo che pensavo, la struttura dati effettiva sarebbe stata secondaria, da non modificare rispetto alle scelte già fatte, volevo solo mettere in evidenza un modo di vedere i thread per "gruppi di esecuzione parallela", che poi sia fattibile o meno è un'altro discorso .

OK, è chiaro.

Thank you very much In tal caso, se un processo sospende l'esecuzione prima del termine del time slice come si procede? Come si coordina tutto?

Come sempre: il context switch avviene indifferentemente a causa dell'interrupt del timer o della chiamata di API che provoca la sospensione del processo.

[xeal]

Originariamente inviato da cdimauro
Infatti il problema della scheduling in generale è NP-Completo, se la memoria non m'inganna: funzionano bene soluzioni semplici e ben collaudate, ma all'aumentare delle variabili da tenere in considerazione la complessità aumenta inesorabilmente...

Già. Per questo pensavo ad una qualche analisi fatta a priori per determinare dei parametri "statici" da utilizzare in un certo sistema, o meglio, la presupponevo, dandola praticamente per scontato, per potermi focalizzare sulla "visione d'insieme" dei thread per blocchi che ne potrebbe derivare.

In pratica pensavo di stabilire a priori per un certo processore multicore quante richieste di accesso alla memoria "contemporanee" si potrebbero gestire per non ridurre troppo la banda verso la ram, quante operazioni di i/o, ecc. in relazione al tipo di bus (con o senza memory controller integrato, con o senza hyper transport), al tipo di comunicazione interna tra i core e alla presenza o meno di feature come hyper threading in ogni processore, per poter individuare un certo numero di parametri (non troppi) di cui tener conto e da misurare su una certa scala (la più piccola possibile) di valori interi (ad esempio: da 0 a X per il numero di accessi in memoria previsti su dati non presenti in cache, da 0 a X per determinare la tendenza a lavorare sui dati precaricati nella cache, da 0 a X per quantificare la necessità di fare più o meno spesso operazioni di I/O, dei parametri per determinare se i processi hanno necessità di comunicare mentre sono in esecuzione contemporanea o se devono contendere delle risorse per cui è meglio eseguirli sequenzialmente...): fatto questo, "basterebbe" (lo so, la "faccio facile" ) determinare il valore ideale per la somma dei parametri di uno stesso tipo, in modo da poterli sommare sottraendo il valore ideale e poi calcolare la media degli scarti tra tutti i parametri e confrontarla con un valore di "soglia" precalcolato, anch'esso "ideale".

In questo modo si potrebbe rendere possibile una visione dei thread per gruppi da eseguire in parallelo (mi sono un po' fissato con il termine macrothread ) e semplificare la ricerca di un sostituto in un gruppo (i valori dei parametri li dovrebbe determinare l'applicazione, non lo scheduler, il quale si limiterebbe a sommare, mediare - possibilmente con uno shift a sinistra - e accettare o scartare il thread). Però rimarrebbe il problema di fondo: quanto spesso nella realtà si presenterebbero applicazioni che producono thread ben raggruppati/raggruppabili, ovvero, fino a che punto sarebbe possibile affiancare a thread che fanno spesso I/O altri che fanno pochi accessi alla memoria e altri che ne fanno molti nel giusto numero, e questo non ad opera dello scheduler, ma già dell'applicazione e dello sviluppatore che sceglie gli algoritmi per risolvere un certo problema...

Qualche somma e divisione non sono un problema, se effettivamente sono limitate in numero e non dipendono dalla quantità di thread: in questo caso rientrebbero come costante nel calcolo della complessità dell'algoritmo di scheduling.

Pensavo alle somme di prima da ripetere un numero finito di volte, onde evitare problemi di starvtion: fissato il numero k dei thread da "esaminare" (calcolando la media pesata di cui parlavo prima, sui valori noti dei parametri), se tra i primi k - 1 non c'è un risultato migliore del k-esimo e il k-esimo non è un buon sostituto (la media degli "scarti" supera la soglia ideale), non si procede oltre nella ricerca e si sceglie proprio il k-esimo (in altri termini, un processo/thread non dovrebbe essere scavlacato più di k volte, con k << n, n numero dei thread in coda, salvo ovviamente ci siano pochi processi/thread in esecuzione - essendo k una costante). In realtà il calcolo dovrebbe essere fatto su una combinazione di thread, dipendente dal numero di thread da sostituire (<= c, numero dei core per processore), comunque in numero (massimo) finito e non dipendente dal numero totale dei thread (in ciascuna coda o in quella più lunga); le combinazioni possibili (da valutare) sarebbero poi limitate nel numero lasciando i thread nella propria coda (ovvero, se devo sostituire due thread valuterò le accoppiate che posso formare prendendo un thread da ciascuna delle code in cui si trovavano i thread non più pronti per l'esecuzione, non prenderò mai entrambi dalla stessa coda). Inoltre, mi aspetterei che il sistema dei parametri sia tale da far sì che in un "buon" raggruppamento (inizialmente i raggruppamenti verrebbero scelti dall'applicazione che li genera e lasciati invariati finchè non ve ne sia la necessità - cioè fino a quando alcuni thread del gruppo sospendano l'esecuzione oppure alcuni gruppi debbano essere spezzati o accorpati) sia "calibrato" (dall'applicazione, quindi dal programmatore) in modo tale che pochi thread, all'interno del gruppo, non siano in grado di portare a termine il time slice (i sostituti, se i parametri da valutare sono scelti, nella definizione di questo algoritmo, fossero accurati in tal senso, tenderebbero generalmente a ripristinare questa caratteristica). Naturalmente sempre che ciò abbia un senso...

Sarebbe comunque troppo lento[...]

E allora semplicemente rinunciamo al riordino, oppure facciamo delle assunzioni per renderlo più veloce, effettuandolo (eventualmente) in maniera parziale. Ad esempio, tenendo conto tra i parametri di scelta (i soliti da sommare, ecc., oppure inserendo un parametro da valutare a parte, o da far rientrare nella media solita assegnandogli un valore di volta in volta) di un id "di gruppo" (che determini l'appartenenza di un thread ad un certo gruppo, così come è stato generato da un'applicazione), ed eventualmente del numero di thread presenti nel gruppo, ci si potrebbe limitare a ripristinare i raggruppamenti originari (eventualmente senza scavalcare troppi thread), eseguendo al più un algoritmo di ordinamento "classico" su un numero (più o meno relativamente) piccolo di thread (eventualmente fissato, in modo da ridurre la complessità ) in presenza di raggruppamenti misti (con thread appartenenti a processi diversi). Sempre, ovviamente, che ne valga la pena.

Il thread era lo stesso, ma abbiamo dei ricordi diametralmente opposti. Vediamo se interviene ilsensine a chiarire la questione...

Sono riuscito a ripescare la discussione :

ilsensine ha scritto:
Linux non ordina in base al tempo di cpu occupato, ma in base a fattori di priorità dinamici. Usa una struttura a liste circolari collegate (orrore? ) per accorpare i processi con simile priorità. La struttura è alquanto complicata (soprattutto in ambiente smp, dove esistono varie runqueue per i diversi processori, e dove bisogna decidere "quando/se/perché spostare un task da una runqueue all'altra"), ma garantisce un accesso O(1) al nuovo task da mandare in esecuzione.

Ma torniamo al nostro discorso:

Come sempre: il context switch avviene indifferentemente a causa dell'interrupt del timer o della chiamata di API che provoca la sospensione del processo.

Il tempo non sfruttato dal processo/thread che entra in attesa viene recuperato in qualche modo (ovvero assegnato a un altro fino al successivo context switch "naturale" ) oppure la cpu entra in stato di idle (a questo punto, sospetto che avvenga proprio questo)?

In ogni caso, si potrebbe valutare la possibilità di far rientrare il processo, una volta tornato pronto per l'esecuzione, esattamente nel punto da cui era uscito dalla coda, ovvero fargli perdere, una volta terminata l'attesa, un "turno" intero, nel trattare i thread per gruppi d'esecuzione parallela potrebbe avere senso al fine di sfruttare i vantaggi che lo sviluppatore dell'applicazione di cui il thread fa parte avesse individuato nel far eseguire contemporaneamente proprio quei thread (sempre che gli altri non abbiano nel frattempo portato a termine la propria esecuzione); si potrebbe anche dare all'applicazione facoltà di scegliere se e per quali gruppi di thread seguire questa politica e per quali un'altra. Naturalmente bisognerebbe valutarne bene l'opportunità (non ho riflettuto su tutte le possibili implicazioni/conseguenze/controindicazioni, è solo un'idea che butto giù così ). Nell'ipotesi di implementare l'algoritmo di scheduling con il quale ho rotto finora (), ciò potrebbe rendere superfluo, almeno in parte, il riordino dei thread (nella versione "ridota" di prima).

Ciao

[cdimauro]

Nonostante tutti i casi che hai prospettato, trovo che ci siano sempre troppe variabili da tenere in considerazione per determinare il miglior bilanciamento dei thread per le varie CPU disponibili. Per me più variabili -> aumento della complessità della "scelta", con tutte le conseguenze che ciò si porta dietro per un compito delicato qual è lo scheduling.

Il tempo non sfruttato viene semplicemente assegnato a un altro thread, fino al verificarsi della successiva condizione che porti a un context switch.
Non credo che sia semplice né gestibile il fatto di far rientrare il processo/thread esattamente nella stessa posizione della coda da cui era stato rimosso: le condizioni cambiano troppo velocemente e ciò richiederebbe l'aggiunta di ulteriori controlli che complicherebbero (nuovamente! ) l'operazione di scheduling...

[xeal]

Originariamente inviato da cdimauro
Nonostante tutti i casi che hai prospettato, trovo che ci siano sempre troppe variabili da tenere in considerazione per determinare il miglior bilanciamento dei thread per le varie CPU disponibili.

Può darsi, in fondo era un'idea buttata giù così. Speravo di poter "appioppare" in parte il lavoro di scelta del bilanciamento delle variabili agli sviluppatori e del sistema operativo (scelta delle variabili, della scala e dei valori ideali), e dell'applicazione (assegnazione di un valore a ciascuna variabile), in modo che lo scheduler si limitasse a sommare e confrontare dei valori già noti. Potrebbe comunque rivelarsi una soluzione inefficiente sia per il "peso" dei calcoli, sia per la staticità della valutazione delle variabili...

Non credo che sia semplice né gestibile il fatto di far rientrare il processo/thread esattamente nella stessa posizione della coda da cui era stato rimosso: le condizioni cambiano troppo velocemente e ciò richiederebbe l'aggiunta di ulteriori controlli che complicherebbero (nuovamente! ) l'operazione di scheduling...

Una mezza idea ce l'avrei, ma temo che l'implementazione sarebbe lenta, avendo come obiettivo operazioni di scheduling in un tempo O(1) (ad occhio e croce direi che il reinserimento potrebbe costare O(N) nel caso peggiore, con molti thread "adiacenti" in stato di wait; poi, bisognerebbe vedere in che modo ciascun os gestisce il passaggio da wait a ready - verifica affidata al thread in questione, che eventualmente esegue un tentativo di accesso alla sezione critica, eventualmente a intervalli prefissati; notifica da parte del thread che ha bloccato le risorse agli altri che le contendono; interrupt, specie per le operazioni di I/O - e confesso di avere qualche lacuna in merito, ma dovresti essertene già accorto ).

Bye.

[cdimauro]

Generalmente alla fine di un'operazione di I/O la periferica in questione lancia un interrupt, però è una cosa che non può fare un thread nei confronti degli altri.