잠금 없는 다중 스레딩

3권에서 새로 도입된 네트웍 및 멀티플레이어 프로그로그래밍 섹션을 위한 게시판입니다.

Moderator: 류광

Locked
이재식
Posts: 685
Joined: 2002-09-11 03:12

Post by 이재식 »

"Multi-thread 프로그래밍을 함에 있어서 Lock 을 사용하지 않고 동일한 기능을 하는 data design 및program control flow를 제어한다. " <-오 이런게 가능한가요?
저수준의 세마포어나 공유메모리락접근을 하지않고도 이런게 가능한것이라니.. -_-) 어떻게 꾸며야 하는건가요.
역시 나는 삼류 =_=) 열심히 공부해야겠네요.
이재식/전주: 김제에서농사짓습니다.
비회원

Post by 비회원 »

이재식 wrote:"Multi-thread 프로그래밍을 함에 있어서 Lock 을 사용하지 않고 동일한 기능을 하는 data design 및program control flow를 제어한다. " <-오 이런게 가능한가요?
저수준의 세마포어나 공유메모리락접근을 하지않고도 이런게 가능한것이라니.. -_-) 어떻게 꾸며야 하는건가요.
역시 나는 삼류 =_=) 열심히 공부해야겠네요.
그냥 두개의 쓰래드가 동시에 쓰는(write) 부분만 없게 하면 문제 없지 않나요.
약간만 규머가 커지면 그렇게 하기 힘들어서 문제지 -_-;;
zupet
Posts: 2764
Joined: 2003-05-13 03:34
Location: NCSOFT LE팀

Post by zupet »

이재식 wrote:"Multi-thread 프로그래밍을 함에 있어서 Lock 을 사용하지 않고 동일한 기능을 하는 data design 및program control flow를 제어한다. " <-오 이런게 가능한가요?
저수준의 세마포어나 공유메모리락접근을 하지않고도 이런게 가능한것이라니.. -_-) 어떻게 꾸며야 하는건가요.
역시 나는 삼류 =_=) 열심히 공부해야겠네요.
http://www.google.co.kr/search?hl=ko&q= ... memory&lr=

Lock Free 로 검색하면 좀 쓸만한 것들이 나옵니다. 개념은 좀 오래된듯 싶은데 최근 몇년새 멀티 코어류가 활성화 되면서 이런저런 연구가 이뤄지고 있는 것 같네요. 언리얼 엔진 3내의 스크립트 엔진인가? 에서도 쓰였단 얘기가 있고 저희팀에서도 연구를 좀 했었지만 글쎄요..? 저는 좀 더 두고 봐야겠단 생각중이군요. ^__^

p.s.꽤 상세하지만 사람 뽑긴 제곱으로 힘들겠군요.
비회원

Post by 비회원 »

이재식 wrote:"Multi-thread 프로그래밍을 함에 있어서 Lock 을 사용하지 않고 동일한 기능을 하는 data design 및program control flow를 제어한다. " <-오 이런게 가능한가요?
저수준의 세마포어나 공유메모리락접근을 하지않고도 이런게 가능한것이라니.. -_-) 어떻게 꾸며야 하는건가요.
역시 나는 삼류 =_=) 열심히 공부해야겠네요.
이재식 wrote:"Multi-thread 프로그래밍을 함에 있어서 Lock 을 사용하지 않고 동일한 기능을 하는 data design 및program control flow를 제어한다. " <-오 이런게 가능한가요?
저수준의 세마포어나 공유메모리락접근을 하지않고도 이런게 가능한것이라니.. -_-) 어떻게 꾸며야 하는건가요.
역시 나는 삼류 =_=) 열심히 공부해야겠네요.

락 대신 플레그를 이용하면 어떨런지 ,

멀티 쓰레드용 데이타를 사용중이라는 flag 를 둬서
flag 내용이 사용중이면 접근을 하지 않고 ,


사용하지 않으면 flag를 원자적으로 접근 하는 함수[윈도우용 함수가 갑자기 기억이 안나네요]로
flag를 사용중으로 바꾼뒤에 사용하면

쓰레드가 블럭당하는 일 없이 , 또한 락의 오버해드를 좀 비할수 있지 않을까요? ;;;

단지 추측
비회원

Post by 비회원 »

비회원 wrote: 락 대신 플레그를 이용하면 어떨런지 ,

멀티 쓰레드용 데이타를 사용중이라는 flag 를 둬서
flag 내용이 사용중이면 접근을 하지 않고 ,


사용하지 않으면 flag를 원자적으로 접근 하는 함수[윈도우용 함수가 갑자기 기억이 안나네요]로
flag를 사용중으로 바꾼뒤에 사용하면

쓰레드가 블럭당하는 일 없이 , 또한 락의 오버해드를 좀 비할수 있지 않을까요? ;;;

단지 추측
락의 내부 구현이 이런식입니다..
비회원

Post by 비회원 »

Lock Free 로 구글에서 찾은 자료 대부분이 회원제만 접근이 가능하네요.
딱히 그런일을 하는건 아니지만 개인적으로 관심이 가서 보고 싶은데,
어떻게 하면 구할 수 있을까요?
ascalon
Posts: 152
Joined: 2005-05-27 09:47
Contact:

Post by ascalon »

비회원 wrote:Lock Free 로 구글에서 찾은 자료 대부분이 회원제만 접근이 가능하네요.
딱히 그런일을 하는건 아니지만 개인적으로 관심이 가서 보고 싶은데,
어떻게 하면 구할 수 있을까요?
acm이나 ieee에 있는 논문들은 대부분 회원에 가입해야 다운로드할 수 있습니다. 그런데, 논문의 저자가 직접 자신의 웹페이지에 논문을 공개한 경우도 많습니다. 구글에서 논문 제목을 입력하여 다시 검색해보시면 (파일포맷을 pdf나 ps로 하면 더 빨리 찾을 수 있음) Lock-free와 관련된 많은 논문을 받을 수 있습니다.

저는 몇개월 전부터 Lock-Free에 대해 관심을 가지고 몇몇 논문과 책을 보고 있습니다. 아시다시피 멀티코어가 보편화 되면서 멀티프로그래밍에 대한 관심이 높아지고 있습니다. 멀티프로그래밍 혹은 병렬처리 프로그래밍을 연구하던 사람들은 이제 드디어 빛을 보게 되었다고 말하고 있지요.

이건 선전 같지만 최근에 저는 http://www.devnote.net 에 멀티프로그래밍 블로그와 위키를 만들었습니다. 멀티프로그래밍 위키에는 Lock-free에 관련된 내용도 실을 예정입니다. 아직 시작한지 얼마 되지 않아 내용이 별로 없습니다. Lock-Free에 관한 내용을 싣게 되면 이곳에 글 올리겠습니다.
비회원

Post by 비회원 »

Interlocked*** (Increment/Decrement/Exchange/등등) 시리즈를 이용하는 것이 진짜로 Lock-Free라고 할 수 있을지는 모르겠습니다만, 이를 이용해서 기존의 Lock보다 비용이 싼 구현은 가능합니다.

polling 혹은 busy-waiting 이 안좋다 라고 보통 개념상 배우긴 하지만,
멀티스레드에서 접근하는 경우가 드물다라는 가정이 있으면 polling 개념이 훨씬 쌉니다.


Lock-free의 예를 들자면

아래의 예는
single-writer/multi-reader 에서 lock 없이 가능합니다.
Interlocked*** 시리즈를 사용하면 multi-writer 에서도 가능합니다.

reader는 빠르며, interlocked 를 사용하지도 않습니다.
단 add/remove 가 느립니다.

말로 설명하는 것이 힘드(..) 므로 코드를 직접 쓰자면

Code: Select all

object Get(key)
{
    return map[key];
}

Code: Select all

void Set(key, value)
{
    do
    {
        Map newMap(map);
        newMap[key] = value;
    } while(InterlockedExchange(map, newMap) != map);
}
같은 방식으로 쓸 수 있습니다.
류광
Posts: 3805
Joined: 2001-07-25 09:00
Location: GPGstudy
Contact:

Post by 류광 »

( 이 스레드는 viewtopic.php?p=67239#67239 에서 분리되었습니다. )
조성경
Posts: 307
Joined: 2005-12-13 11:50

Post by 조성경 »

락 대신 플레그를 이용하면 어떨런지 ,

멀티 쓰레드용 데이타를 사용중이라는 flag 를 둬서
flag 내용이 사용중이면 접근을 하지 않고 ,


사용하지 않으면 flag를 원자적으로 접근 하는 함수[윈도우용 함수가 갑자기 기억이 안나네요]로
flag를 사용중으로 바꾼뒤에 사용하면

쓰레드가 블럭당하는 일 없이 , 또한 락의 오버해드를 좀 비할수 있지 않을까요? ;;;

단지 추측
Flag는 해결책이 될 수 없습니다. Flag의 값이 바뀌는 순간에 무결성이 깨지게 됩니다.

그러니까 Flag를 비교하는 부분을 지나서 값을 바꾸는 중간에 thread context가 일어났을때

두개 이상의 쓰레드가 동시에 진입하는게 가능합니다.

그래서 Flag를 보호하는 락이 필요하게 되고, 결국 락과 같게되죠.

어떠한 테크닉보다는 구조적인 접근이 필요합니다.

다른 분들이 말씀하신것처럼 여러 연구가 진행중이기도 하구요.

PS: Interlocked..계열의 함수에 관려된 얘기가 있네요.

Interlockedxxx 계열의 함수를 이용해서 Flag를 수정한다고 해도 리턴값을 관리해야

한다는 부담부분에 있어서 락과 다를바가 없습니다. Interlocked..함수의 연산이 Atomic하기는

하지만 여러쓰레드에서 진입이 불가능한게 아니거든요. 그러한것들을 통합해둔 패키지가

lock object들입니다.
더 이상 이 곳에 오지 않습니다.
mastercho
Posts: 587
Joined: 2004-05-09 20:37

Post by mastercho »

neuk wrote:
락 대신 플레그를 이용하면 어떨런지 ,

멀티 쓰레드용 데이타를 사용중이라는 flag 를 둬서
flag 내용이 사용중이면 접근을 하지 않고 ,


사용하지 않으면 flag를 원자적으로 접근 하는 함수[윈도우용 함수가 갑자기 기억이 안나네요]로
flag를 사용중으로 바꾼뒤에 사용하면

쓰레드가 블럭당하는 일 없이 , 또한 락의 오버해드를 좀 비할수 있지 않을까요? ;;;

단지 추측
Flag는 해결책이 될 수 없습니다. Flag의 값이 바뀌는 순간에 무결성이 깨지게 됩니다.

그러니까 Flag를 비교하는 부분을 지나서 값을 바꾸는 중간에 thread context가 일어났을때

두개 이상의 쓰레드가 동시에 진입하는게 가능합니다.

그래서 Flag를 보호하는 락이 필요하게 되고, 결국 락과 같게되죠.

어떠한 테크닉보다는 구조적인 접근이 필요합니다.

다른 분들이 말씀하신것처럼 여러 연구가 진행중이기도 하구요.

PS: Interlocked..계열의 함수에 관려된 얘기가 있네요.

Interlockedxxx 계열의 함수를 이용해서 Flag를 수정한다고 해도 리턴값을 관리해야

한다는 부담부분에 있어서 락과 다를바가 없습니다. Interlocked..함수의 연산이 Atomic하기는

하지만 여러쓰레드에서 진입이 불가능한게 아니거든요. 그러한것들을 통합해둔 패키지가

lock object들입니다.

Interlocked 를 하는건 락과 다를봐가 없는건 아닙니다

일단 말씀 하신 여러쓰레드에서 진입 불가능한게 아니라는 말은 잘못된 말씀입니다

저 함수를 사용하면 CPU 단하나만 그 메모리 블럭에 접근하는것을 보장하는 함수입니다

특정 CPU 어셈블리 명령으로 아마 그런게 있을것으로 보이기때문에 성능상에서도 분명이득이

꽤나 있을것으로 생각됩니다

게다가 락을 건다는건 운영체제의 뮤텍스를 사용하겠다는것인데 , 그것의 오버헤드와 Interlocked의

비용차이는 천지 차이라고 생각이 됩니다
나디아
Posts: 102
Joined: 2004-08-07 11:36

LockFree

Post by 나디아 »

구글에서 검색하면서 읽어 보다가 본 링크 입니다.

http://www.cl.cam.ac.uk/research/srg/netos/lock-free/

자원의 변조(Read/Write) 시점을 알기 위해서 흔히 생각하는 InterLockXXXX류의 대체 알고리즘으로 아래와 같은 것들을 사용하고 있더군요

- CAS(Compare And Swap) 류
- STM(Software Transactional Memory)류

나열된 문서를 다 읽어 보진 않았지만, Lock을 쓸 때의 상황보다 좀 더 여러 가지를 유연하게 만들어 주긴 한다고
하는데 아직 이해 하진 못하였습니다.

문서에서는 변조 가능 상황 확인을 위해서 의사코드로 while(x); 와 같은 형태를 사용하고 있느나, 이를 실제로 구현하기 위해서는 CPU Idle이 필요하고(Spin 개념도 포함) 여러 가지 생각해 봐야 될 상황이 좀 보입니다.

논리적으로, 수학적으로 완벽하고, 속도 빠르고, DeadLock, LiveLock 같은 상황 신경 안써도 되는
멀티쓰레드 자료관리 기법을 연구해 보고 싶군요.(희망사항 ㅠ.ㅜ)

DeadLock/LiveLock - http://en.wikipedia.org/wiki/Deadlock
^___^
Image
조성경
Posts: 307
Joined: 2005-12-13 11:50

Post by 조성경 »

mastercho wrote:Interlocked 를 하는건 락과 다를봐가 없는건 아닙니다

일단 말씀 하신 여러쓰레드에서 진입 불가능한게 아니라는 말은 잘못된 말씀입니다

저 함수를 사용하면 CPU 단하나만 그 메모리 블럭에 접근하는것을 보장하는 함수입니다

특정 CPU 어셈블리 명령으로 아마 그런게 있을것으로 보이기때문에 성능상에서도 분명이득이

꽤나 있을것으로 생각됩니다

게다가 락을 건다는건 운영체제의 뮤텍스를 사용하겠다는것인데 , 그것의 오버헤드와 Interlocked의

비용차이는 천지 차이라고 생각이 됩니다
당연히 Interlocked의 비용이 더 싸긴합니다. 하지만 그것도 상황에 따라 다르다는거죠. 여기서

논의되고 있는 전반적인 흐름은 하나의 변수를 수정하는 간단한 연산을 말하는건 아닐텐데요.

위에 비회원님이 예를 드신 코드를 보죠.

Code: Select all

void Set(key, value)
{
    do
    {
        Map newMap(map);
        newMap[key] = value;
    } while(InterlockedExchange(map, newMap) != map);
}
모든 쓰레드가 전부 while의 조건문에 진입합니다. 단지 map과 newMap을 치환하는 과정만이

atomic 한거죠. 그걸 map과 비교해서 다시 루프를 돕니다. 어디서 본것 같지 않나요?

네 스핀락과 기본적인 구조가 같습니다.

하지만 여기에는 제가 원문에서 말한 리턴 변수 관리라는 또다른 변수가 존재합니다.

위의 예는 의사코드를 제시하신거라 생각합니다만, 저대로라면 빵구가 납니다.

(InterlockedExchange를 이용해서 map의 값을 바꾼 직후에 !=가 실행되기 전에 누군가

map의 값을 바꿔버린다면 논리적으로는 InterlockedExchange(map, newMap) == map이

되지만 실제결과는 !=가 되어서 또다시 do loop로 진입하게 되면서 꼬입니다: 이 문장 한차례 수정했습니다)

진입과 관련된 부분을 따로 관리하는 방법이 추가로 필요하게 되죠. 이러한 과정을

거치게되면 결국 이미 만들어진 lock과 다를바가 없어진다는 말입니다.

위와 같은 경우라면 그냥 Enter../LeaveCriticalSection으로 진입자체를 막아버리는게 가장

빠르고 현명한 방법입니다.

Interlockedxx 시리즈는 그 용도에 맞게 사용될때만 이득이 있습니다. 이처럼 flag같은 방식으로

사용하면 오히려 문제를 꼬이게 만듭니다.


ps. 이 방법에 가려진 문제가 또하나 있는데, 그건 아사(Starvation) 문제입니다. (한글 표현이

아사가 맞나 모르겠네요) 저 방법을 사용할때 재수없는 쓰레드가 아사상태에 빠지는 경우를

처리할수가 없습니다.
더 이상 이 곳에 오지 않습니다.
mastercho
Posts: 587
Joined: 2004-05-09 20:37

Post by mastercho »

neuk wrote:
위와 같은 경우라면 그냥 Enter../LeaveCriticalSection으로 진입자체를 막아버리는게 가장

빠르고 현명한 방법입니다.

Interlockedxx 시리즈는 그 용도에 맞게 사용될때만 이득이 있습니다. 이처럼 flag같은 방식으로

사용하면 오히려 문제를 꼬이게 만듭니다.
(MSDN 인용합니다 원자적으로 처리할수 있다는것을 보여주는 내용)
The InterlockedCompareExchange, InterlockedDecrement, InterlockedExchange,
InterlockedExchangeAdd, and InterlockedIncrement functions provide a simple mechanism for
synchronizing access to a variable that is shared by multiple threads. The threads of different
processes can use this mechanism if the variable is in shared memory.

예를 들어

Code: Select all


// flag 그 설정이나 접근은 원자적 접근 함수 계열인 interlockedXXX를 씁니다 

class STestData
{
public:
    int  a;
    int  b;

    int flag

    bool Write(int aaa,int bbb )
   {
         if( flag 이미 다른 누군가 a,b를 사용중인가? == true)
         {
              return false;  // 이미 누군가 사용중이므로 a,b에 접근 하지 말것
         }

         
          flag  사용중 설정;  
      
          a,b에 접근
          
          flag  사용중 해제
         
          return  true; // 성공적으로 쓰기에 성공함
    }

    bool  Read(int* pA,int* pB)
   {
          if( flag 이미 다른 누군가 a,b를 사용중인가? == true)
         {
              return false;  // 이미 누군가 사용중이므로 a,b에 접근 하지 말것
         }
       
           flag  사용중 설정;  
      
          a,b에 접근
          
          flag  사용중 해제
         
          return  true; // 성공적으로 읽기에 성공함

    }
}
이런식으로 사용할 경우 크리티컬 색션을 사용해 하는것처럼 여러개의 데이타를 보호하는 효과를 볼수 있을것입니다


그리고 다른 쓰레드가 접근하고 있어서 읽기나 쓰기에 실패할 경우 spin lock처럼 read나 write가 true를 리턴할때까지 CPU를 소모하며 대기할수도 있고 , 아니면 sleep를 사용하여 다른 쓰레드에게 cpu 사용권을 넘길수도 있습니다.

실제 스핀락 구현도 짧은 시간 기다려보고 그때까지 lock이 안풀리면 cpu 사용권을 다른쓰레드에게 넘기지요

이렇게 하면 락을 사용하는데 비용도 줄일수 있고, 스핀락 전략과 일반 Lock과 같은구현 두가지다 선택적으로
사용할수 있지 않을까 싶습니다

물론 구현하기는 쉽진 않겠지만 , 가능성은 있다는것이 중요하지 않을까요?
ascalon
Posts: 152
Joined: 2005-05-27 09:47
Contact:

Lock-Free에 관해

Post by ascalon »

Lock-Free에 대해 잘못 이해하고 있는 글들이 있어 간단히 설명하고자 합니다.

Lock-Free는 말 그대로 Lock 없이 프로그래밍 하는 것입니다. Lock은 멀티스레드 프로그램에서 데이터 동기화를 위해 어쩔 수 없이 사용되는 것입니다만 Lock때문에 많은 문제가 발생합니다. 예를 들면 Deadlock, context switch, priority inversion과 같은 것입니다. 잦은 Context switch는 그 자체도 상당한 CPU 시간을 요하지만, CPU의 캐쉬메모리를 무효화시켜 전체적 성능 저하를 가져옵니다. Priority Inversion은 Lock으로 인해 강제로 Context Switch가 일어날 경우 높은 우선순위를 가진 스레드가 낮은 우선순위를 가진 스레드에 CPU를 양보하게 되는 현상입니다.

여기서 Non-Blocking이라는 말도 함께 자주 등장합니다. Non-Blocking이란 멀티스레드 프로그램에서 스레드가 일정 시간안에 어떤 연산을 끝내는 것이 보장되는 것을 말합니다. Lock을 사용하면 다른 스레드가 그 Lock을 Release하기 전까지는 어떤 다른 스레드도 그 Lock으로 보호된 크리티컬 섹션에 들어갈 수 없습니다. 가장 이상적인 경우는 "Lock-Free + Non-Blocking" 이며 Lock-Free가 결국 Non-Blocking이기도 합니다.

Lock-Free를 위해 가장 많이 사용되고 가장 효과적이라고 알려진 것이 Compare-And-Swap(CAS) 연산이며 Win32 에서는 InterlockedCompareExchange입니다. CAS는 대부분의 CPU에서 지원하는 Atomic Operation이기도 합니다.

Lock-Free는 주로 아주 작은 성능 저하라도 매우 중요하거나 Lock의 사용을 최대한 없애야하는 극단적인 경우 사용됩니다. 예를 들면 운영체제의 스케줄러(Scheduler)에서 쓰는 Queue와 같은 것입니다. Windows API 중에 최근에 추가된 다음 API는 Lock-Free로 구현된 Single Linked List를 제공합니다. 그런데 Lock-Free에서 악명 높은 문제 중의 하나인 ABA 문제로 인해 범용 linked list로 사용하기 어려운 제약사항을 가지고 있습니다. 이 API는 사실 Linked list라기 보다 Stack에 가깝습니다.

Code: Select all

InitializeSListHead
InterlockedPushEntrySList
InterlockedPopEntrySList
모든 자료구조를 Lock-Free로 코딩할 수 있다면 정말 좋겠지만, Lock-Free는 일반적인 프로그램(서버 프로그램일지라도)에서 꼭 필요한 경우는 별로 없습니다. 그리고, Lock-Free 프로그램은 구현하기 매우 까다롭습니다. 버그를 찾기도 엄청나게 어려운 경우가 많습니다.

다시 한 번 말씀드리지만 , 제 위키 페이지에 http://www.devnote.net/wiki Lock-Free에 관한 내용을 올리면 알려드리도록 하겠습니다.
Locked