sjo200 - CS 대학원 수업 정리 블로그

 주의: 이 게시물에는 뇌피셜이 많습니다.

1. 개념 

 이때까지 consensus에 목매달고 공부했던건 왜인지 다시 생각해보자. multi-core architecture에서 여러 프로세서가 한 자원에 접근할 때 누가 첫 번째로 접근해서 내가 못했는지 아는 것이 parallel programming에 있어서 중요한 요소이다. 이때 hardware가 지원하는 operation으로 최대 몇개의 프로세서가 한 자원에 접근할 때 누가 첫 번째로 접근했는지 알 수 있는지가 consensus number이다. 

2. hardware에서 지원하는 atomic operation들의 consensus number

 FetchAndIncrement, GetAndSet, ... 은 2이다. 왜냐하면 읽고 써버리기 때문에 세 번째 쓰레드가 첫 번째 쓰레드의 값을 받지 못하기 때문이다. 그렇기 때문에, CompareAndSet로 -1을 비교해서 옳다면 쓰레드 넘버를 기록하고, 다음부터 그 수를 반환하게 하면 consensus number가 무한이 된다. CAS의 구현이 지역마다 다른 것 같은데, 누구는 비교해서 옳았을 때 마지막으로 true를 리턴한다는 사람도 있고, 내가 배운 것은 비교해서 틀리면 마지막으로 이전 값을 리턴하는 것이다. 전자면 다른 쓰레드들이 승자를 모르기 때문에 엄밀히 따지면 잘못 구현한 것이라고 할 수 있지 않을까? 정확히는 모르겠다.

 (추가: multiple assignment는 앞 게시물에서 2n-2라고 밝혔다.)

3. lock-free 구현

 CAS는 앞으로 많이 사용될 것이므로 기억해두자. CAS는 consensus number가 무한이기 때문에, 어떤 implementation이든 lock을 걸고 하던 시행을 모두 그냥 CAS로 바꿔버리면 lock-free가 된다. 근데, 잘 생각해야할게 꼭 그렇지만은 않다. 한 번씩 CAS를 동시에 두번 수행해야 될때도 있기 때문에, java의 util에는 그런것들이(AtomicMarkableReference 등) 구현되어 있다.

4. wait-free 구현

 wait-free는 lock-free로 구현해본 다음, 생각해야 할 것이다. 쉽게 생각하면 aging의 구현을 추가하는 것인데, aging해서 모든 쓰레드가 finite step안에 끝나는 것을 보장하도록 구현해야한다. 나중에 concurrent structure를 여럿 배워도 wait-free 구현은 안나온다... 아마 구현해야될 양도 많아지고 빡치니까 그렇지 않을까...

출처: http://www.codemiles.com/c-opengl-examples/drawing-teapot-using-opengl-t9010.html

#include <GL\glut.h>

GLfloat xRotated, yRotated, zRotated;
GLdouble size=1;


void display(void)
{

    glMatrixMode(GL_MODELVIEW);
    // clear the drawing buffer.
    glClear(GL_COLOR_BUFFER_BIT);
    // clear the identity matrix.
    glLoadIdentity();
    // traslate the draw by z = -4.0
    // Note this when you decrease z like -8.0 the drawing will looks far , or smaller.
    glTranslatef(0.0,0.0,-4.5);
    // Red color used to draw.
    glColor3f(0.8, 0.2, 0.1); 
    // changing in transformation matrix.
    // rotation about X axis
    glRotatef(xRotated,1.0,0.0,0.0);
    // rotation about Y axis
    glRotatef(yRotated,0.0,1.0,0.0);
    // rotation about Z axis
    glRotatef(zRotated,0.0,0.0,1.0);
    // scaling transfomation 
    glScalef(1.0,1.0,1.0);
    // built-in (glut library) function , draw you a Teapot.
    glutSolidTeapot(size);
    // Flush buffers to screen
     
    glFlush();        
    // sawp buffers called because we are using double buffering 
   // glutSwapBuffers();
}

void reshapeFunc(int x, int y)
{
    if (y == 0 || x == 0) return;  //Nothing is visible then, so return
    //Set a new projection matrix
    glMatrixMode(GL_PROJECTION);  
    glLoadIdentity();
    //Angle of view:40 degrees
    //Near clipping plane distance: 0.5
    //Far clipping plane distance: 20.0
     
    gluPerspective(40.0,(GLdouble)x/(GLdouble)y,0.5,20.0);
 
    glViewport(0,0,x,y);  //Use the whole window for rendering
}

void idleFunc(void)
{
 
     yRotated += 0.01;
     
    display();
}


int main (int argc, char **argv)
{
    //Initialize GLUT
    glutInit(&argc, argv);
    //double buffering used to avoid flickering problem in animation
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);  
    // window size
    glutInitWindowSize(400,350);
    // create the window 
    glutCreateWindow("Teapot Rotating Animation");
    glPolygonMode(GL_FRONT_AND_BACK,GL_LINE);
    xRotated = yRotated = zRotated = 30.0;
     xRotated=33;
     yRotated=40;
    glClearColor(0.0,0.0,0.0,0.0);
    //Assign  the function used in events
    glutDisplayFunc(display);
   glutReshapeFunc(reshapeFunc);
    glutIdleFunc(idleFunc);
    //Let start glut loop
    glutMainLoop();
    return 0;
}

  - See more at: http://www.codemiles.com/c-opengl-examples/drawing-teapot-using-opengl-t9010.html#sthash.voAavc8k.dpuf

1. 개념

consensus는 쓰레드간의 경쟁이다. 쓰레드가 하나만 실행되어야 할 때, 순위를 정해 최상위 쓰레드 하나를 정하는 것이다. 그런데 wait-free하게 정해야 한다. 따라서, mutex는 사용할 수 없다. 또한 fault-tolerance 해야한다.

2. queue with multiple dequeuers 

쓰레드가 순서를 정하려면, 큐에 각 순서를 넣어서 dequeue하면 된다. 하지만 최상위 하나의 쓰레드가 가진 값을 모든 쓰레드가 알아햐 하는데, 이것은 queue에서 구현이 불가능하다. (2 threads solution만 가능하다.)

3. multiple assignment with shared registers

두 쓰레드가 a[3] 이라는 공간에 두칸씩 쓴다. 그럼 겹치는 한칸에 무엇이 쓰였는지와 상대방만이 쓴 칸을 보면 상대방이 먼저 썼는지, 나중에 썼는지, 아무것도 하지 않는지 알 수 있다. 따라서 먼저 쓴 사람을 알 수 있다. 또한, 8개의 레지스터와 3 assignment를 사용하면 4개의 쓰레드에 대해 실행할 수 있다. 둘(1,2)과 나머지 둘(3,4)을 토너먼트식으로 진행하고 아래 그림과 같이 각각의 둘을 팀으로 맺어 이긴 자의 수를 쓰게하면 된다.

왜 그냥 토너먼트식으로 이긴 자 둘에 대해 3개의 레지스터에 2 assignment를 하면 안되냐 할 수도 있지만, 그것은 fault-tolerance 하지 않으므로 적합하지 않다. 예를 들어, 1, 3이 토너먼트 승자이고, 1, 3만을 consensus한다면, 위 표에서 나온 14, 23, 24가 실행되지 않는 것이다.

그래서 n multiple assignment로 구현할 수 있는 consensus number는 2n-2이다.

4. RMW(Read-Modify-Write) objects

getAndIncrement, getAndAdd, getAndSet과 같이 읽고 쓰는 atomic operation은 consensus number(consensus 가능한 수)가 2이다. 하지만 compareAndSet과 같이 비교하고 돌려주는 instruction이 있는 atomic operation은 무한이다. 가령 default 값이 -1이고, 가장 먼저 쓴 쓰레드의 값이 x 이면, 다른 쓰레드는 모두 -1로 compare 하지만 x값과 다르므로 x를 return 받을 것이기 때문이다.

추가로, multiple(N) assignment의 consensus number는 2n-2이다.