Test-and-set
En informàtica, la instrucció de prova i configuració és una instrucció que s'utilitza per escriure (establir) 1 a una ubicació de memòria i retornar el seu valor antic com una única operació atòmica (és a dir, no interrompuda). Aleshores, la persona que truca pot "provar" el resultat per veure si la trucada ha canviat l'estat. Si diversos processos poden accedir a la mateixa ubicació de memòria i si un procés està realitzant una prova i un conjunt, cap altre procés pot iniciar una altra prova i un conjunt fins que s'acabi la prova i conjunt del primer procés. Una unitat de processament central (CPU) pot utilitzar una instrucció de prova i configuració que ofereix un altre component electrònic, com ara la RAM de dos ports; una CPU mateixa també pot oferir una instrucció de prova i configuració.
Es pot construir un pany mitjançant una instrucció de prova i configuració atòmica [1] de la següent manera:
Aquest codi suposa que la ubicació de la memòria es va inicialitzar a 0 en algun moment abans de la primera prova i configuració. El procés de trucada obté el bloqueig si el valor antic era 0, en cas contrari, el bucle while gira esperant per adquirir el bloqueig. Això s'anomena spinlock. En qualsevol moment, el titular del bloqueig pot simplement tornar a establir la ubicació de la memòria a 0 per alliberar el bloqueig per a l'adquisició per part d'un altre; això no requereix cap maneig especial, ja que el titular "és el propietari" d'aquesta ubicació de memòria. " Prova i prova i configura" és un altre exemple.
Maurice Herlihy (1991) va demostrar que test-and-set (comparació d'1 bit) té un nombre de consens finit i pot resoldre el problema de consens sense espera per a com a màxim dos processos concurrents.[2] En canvi, compare-and-swap (comparació de 32 bits) ofereix una solució més general a aquest problema, i en algunes implementacions compare-i-swap (comparació de 64 bits) també està disponible per a una utilitat ampliada.
Implementació de maquinari de test-and-set[modifica]
Les instruccions de prova i configuració de DPRAM poden funcionar de moltes maneres. Aquí hi ha dues variacions, ambdues descriuen una DPRAM que proporciona exactament 2 ports, permetent l'accés de 2 components electrònics separats (com 2 CPU) a cada ubicació de memòria de la DPRAM.
Implementació de programari de test-and-set[modifica]
Alguns conjunts d'instruccions tenen una instrucció de llenguatge màquina de prova i establiment atòmic. Alguns exemples inclouen x86 [3] i IBM System/360 i els seus successors (incloent z/Architecture).[4] Els que no ho fan encara poden implementar una prova i un conjunt atòmics mitjançant una instrucció de lectura, modificació, escriptura o comparació i intercanvi.
Referències[modifica]
- ↑ Anderson, T. E. IEEE Transactions on Parallel and Distributed Systems, 1, 1, 01-01-1990, pàg. 6–16. DOI: 10.1109/71.80120. ISSN: 1045-9219.
- ↑ Herlihy, Maurice ACM Trans. Program. Lang. Syst., 13, 1, January 1991, pàg. 124–149. DOI: 10.1145/114005.102808 [Consulta: 20 maig 2007].
- ↑ «BTS—Bit Test and Set» (en anglès). www.felixcloutier.com. [Consulta: 21 novembre 2016].
- ↑ «IBM Knowledge Center» (en anglès). www.ibm.com. [Consulta: 21 novembre 2016].