쓰레드 관리 기법 구현
우선 5개의 쓰레드로, 각 쓰레드는 십만 번 수행하며 AddVal(1)을 이용해 atomic하게 값을 증가시킵니다. 따라서 예상 결과값은 500000입니다.
소스 코드
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
//2019930019 이주호
namespace uos2019930019
{
class Program
{
private static volatile int _val = 0;
static int num = 100000;
static void AddValue(int value)
{
while (true)
{
var orgVal = _val;
var newVal = orgVal + value;
if (Interlocked.CompareExchange(ref _val, newVal, orgVal) == orgVal)
break;
}
}
static void ThreadBody()
{
for (int i = 0; i < num; i++) // Main 스레드와 병행 수행
AddValue(1);
}
static void Main(string[] args)
{
Console.WriteLine("2019930019 이주호 운영체제 과제 1-1");
Console.WriteLine();
List<Thread> tList = new List<Thread>();
int tnum = 5;
for(int i = 0; i < tnum; i++)
{
tList.Add(new Thread(ThreadBody));
tList[i].Start();
}
for(int i = 0; i < tnum; i++)
{
tList[i].Join();
}
Console.WriteLine("예상 결과 : {0}",num*tnum);
Console.WriteLine("연산 결과 : {0}",_val);
}
}
}
각 연산이 원자적으로 적용되었고, 예상했던 결과와 같습니다.
다음으로는 AddValue를 이용하지 않고, _val++을 이용해 값을 증가시킵니다.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
//2019930019 이주호
namespace uos2019930019
{
class Program
{
private static volatile int _val = 0;
static int num = 100000;
static void AddValue(int value)
{
while (true)
{
var orgVal = _val;
var newVal = orgVal + value;
if (Interlocked.CompareExchange(ref _val, newVal, orgVal) == orgVal)
break;
}
}
static void ThreadBody()
{
for (int i = 0; i < num; i++) // Main 스레드와 병행 수행
_val++;
}
static void Main(string[] args)
{
Console.WriteLine("2019930019 이주호 운영체제 과제 1-2");
Console.WriteLine();
List<Thread> tList = new List<Thread>();
int tnum = 5;
for(int i = 0; i < tnum; i++)
{
tList.Add(new Thread(ThreadBody));
tList[i].Start();
}
for(int i = 0; i < tnum; i++)
{
tList[i].Join();
}
Console.WriteLine("예상 결과 : {0}",num*tnum);
Console.WriteLine("연산 결과 : {0}",_val);
}
}
}
실행 결과
연산 결과와 예상 결과가 같지 않습니다. 연산 결과가 예상과 다른 이유는 다음과 같습니다. 만약 쓰레드 a와 b가 있다고 가정할 때, 0에서부터 쓰레드 a와 b가 모두 값을 더하려고 시도합니다. 그런데 이 방식은 atomic하지 않습니다. 따라서 a가 값을 더해 저장하기 직전(저장할 값은 1)에 b가 현재 값(현재 값은 0)을 가져가고, a는 _val에 1을 저장합니다. 다음으로 b도 _val에 값을 저장하려고 하는데 b가 1을 더한 값 1과 _val의 값이 같을 수 있습니다. 결국 덧셈이 누락된 것과 같은 결과가 나타나며, 이것이 계속해서 일어나면 연산 결과와 같이 예상 결과와 크게 차이날 수 있습니다.
우선 CAS로 기본적인 push와 pop메소드를 구현했습니다. 그리고 각 쓰레드는 while문을 만 번 순회합니다.
소스 코드
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
//2019930019 이주호
namespace uos2019930019
{
class Node
{
public int data;
public Node nextNode;
public Node(int dt)
{
data = dt;
nextNode = null;
}
}
class LinkedList
{
public Node Head;
}
class Program
{
static volatile LinkedList freeList = new LinkedList();
static volatile LinkedList headList = new LinkedList();
static int nodeCount = 10000;
static int nodes(ref Node Head) //작업이 끝나고 실행되므로 병행 수행을 고려하지 않습니다.
{
int cnt = 0;
while (Head != null)
{
cnt++;
Head = Head.nextNode;
}
return cnt;
}
static Node pop(ref Node Head)
{
Node orgVal, newVal;
while (true)
{
orgVal = Head;
if (orgVal == null)
return null;
try { newVal = orgVal.nextNode; } catch { continue; }
if (Interlocked.CompareExchange(ref Head, newVal, orgVal) == orgVal)
break;
}
orgVal.nextNode = null;
return orgVal;
}
static void push(ref Node Head, ref Node newVal)
{
while (true)
{
Node orgVal;
orgVal = Head;
newVal.nextNode = orgVal;
if (Interlocked.CompareExchange(ref Head, newVal, orgVal) == orgVal)
break;
}
}
static void ThreadBody()
{
Random r = new Random();
int n = r.Next(2, 10), m = r.Next(2, 10);
Console.WriteLine("Thread n : {0}, m : {1}", n, m);
int num = 10000;
while (--num >= 0)
{
for (int i = 0; i < n; i++) // Main 스레드와 병행 수행
{
Node nod = pop(ref freeList.Head);
if (nod != null)
push(ref headList.Head, ref nod); //노드를 제거해 바로 push합니다.
}
for (int i = 0; i < m; i++) // Main 스레드와 병행 수행
{
Node nod = pop(ref headList.Head);
if (nod != null)
push(ref freeList.Head, ref nod); //노드를 제거해 바로 push합니다.
}
}
}
static void Main(string[] args)
{
Console.WriteLine("2019930019 이주호 운영체제 과제 2-1 (ABA 문제 발생)");
Console.WriteLine();
for (int i = 0; i < nodeCount; i++)
{
Node nod = new Node(i);
push(ref freeList.Head, ref nod);
}
Thread t1 = new Thread(ThreadBody);
Thread t2 = new Thread(ThreadBody);
t1.Start();
t2.Start();
t1.Join();
t2.Join();
Console.WriteLine("=========작업 종료=========");
int fn = nodes(ref freeList.Head);
int hn = nodes(ref headList.Head);
Console.WriteLine("freeList 노드의 수 : {0}", fn);
Console.WriteLine("headList 노드의 수 : {0}", hn);
Console.WriteLine("만든 노드의 수 : {0}", nodeCount);
Console.WriteLine("실제 노드의 수 : {0}", fn + hn);
}
}
}
하지만 단순히 CAS로 노드를 달거나 제거할 때, ABA문제가 발생할 수 있습니다. 이 문제가 발생하면, freeList가 가지고 있는 노드의 수와 headList가 가지고 있는 노드의 수의 합이 처음 만든 노드의 수와 다를 수 있습니다.
이 경우는 올바르게 실행된 결과로, 두 리스트의 노드의 합이 만든 노드의 수와 같습니다.
이 경우는 ABA문제가 발생한 결과로, 두 리스트의 노드의 합이 만든 노드의 수와 다릅니다.
따라서 이 문제를 해결하기 위해, Node의 주소를 직접 주고받는 것이 아닌, 노드의 번호를 매개로 주고받는 방법을 사용했습니다.
소스 코드는 다음과 같습니다. ABA문제 해결을 조금 더 명확하게 표현하기 위해 while문을 십만 번 수행합니다.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
//2019930019 이주호
namespace uos2019930019
{
class Node
{
public int data;
public Node nextNode;
public Node(int dt)
{
data = dt;
nextNode = null;
}
}
class LinkedList
{
public Node Head;
}
class Program
{
static volatile LinkedList freeList = new LinkedList();
static volatile LinkedList headList = new LinkedList();
static int nodeCount = 10000;
static int nodes(ref Node Head) //작업이 끝나고 실행되므로 병행 수행을 고려하지 않습니다.
{
int cnt = 0;
while (Head != null)
{
cnt++;
Head = Head.nextNode;
}
return cnt;
}
static int? pop(ref Node Head)
{
Node orgVal;
Node newVal;
while (true)
{
orgVal = Head;
if (Head == null)
return null;
if (orgVal != Head)
continue;
try //Head가 null로 바뀌지 않았음을 보장합니다. pop도중 다른 쓰레드가 Head를 null로 바꾸었다면 오류가 발생하기 때문입니다.
{
newVal = orgVal.nextNode;
}
catch
{
continue;
}
int data = orgVal.data;
if (Interlocked.CompareExchange(ref Head, newVal, orgVal) == orgVal)
return data;
}
}
static void push(ref Node Head, int newVal)
{
Node tmpNode = new Node(newVal);
Node orgVal;
while (true)
{
orgVal = Head;
tmpNode.nextNode = orgVal;
if (Interlocked.CompareExchange(ref Head, tmpNode, orgVal) == orgVal)
break;
}
}
static void ThreadBody()
{
Random r = new Random();
int n = r.Next(2, 10), m = r.Next(2, 10);
Console.WriteLine("Thread n : {0}, m : {1}", n, m);
int num = 100000;
while (--num >= 0)
{
for (int i = 0; i < n; i++) // Main 스레드와 병행 수행
{
int? nod = pop(ref freeList.Head);
if (nod != null)
push(ref headList.Head, (int)nod); //노드를 제거해 바로 push합니다.
}
for (int i = 0; i < m; i++) // Main 스레드와 병행 수행
{
int? nod = pop(ref headList.Head);
if (nod != null)
push(ref freeList.Head, (int)nod); //노드를 제거해 바로 push합니다.
}
}
}
static void Main(string[] args)
{
Console.WriteLine("2019930019 이주호 운영체제 과제 2-2 (ABA문제 해결)");
Console.WriteLine();
for (int i = 0; i < nodeCount; i++)
{
push(ref freeList.Head, i);
}
Thread t1 = new Thread(ThreadBody);
Thread t2 = new Thread(ThreadBody);
t1.Start();
t2.Start();
t1.Join();
t2.Join();
Console.WriteLine("=========작업 종료=========");
int fn = nodes(ref freeList.Head);
int hn = nodes(ref headList.Head);
Console.WriteLine("freeList 노드의 수 : {0}", fn);
Console.WriteLine("headList 노드의 수 : {0}", hn);
Console.WriteLine("만든 노드의 수 : {0}", nodeCount);
Console.WriteLine("실제 노드의 수 : {0}", fn + hn);
}
}
}
실행 결과
다음과 같이 여러번 실행해도 만든 노드의 수와 수행한 후의 노드의 수가 변하지 않는 것을 알 수 있습니다. 다만 이 경우 해당 데이터를 가지는 노드를 계속 생성하기 때문에 메모리 누수 문제가 생길 수 있습니다만 c#의 경우 가비지 컬렉터 기능이 있어 그런 문제를 발견하지 못했습니다.
이전의 것과 작동은 동일하게 하지만, mutex lock과 unlock을 이용해 상호 배제를 했습니다. 또한 수행 시간 진단을 위해 stopwatch를 사용했습니다. 마찬가지로 while문을 십만 번 순회합니다.
소스 코드
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
//2019930019 이주호
namespace uos2019930019
{
class Node
{
public int data;
public Node nextNode;
public Node(int dt)
{
data = dt;
nextNode = null;
}
}
class LinkedList
{
public Node Head;
}
class Program
{
static Mutex mutex = new Mutex();
static volatile LinkedList freeList = new LinkedList();
static volatile LinkedList headList = new LinkedList();
static int nodeCount = 10000;
static int nodes(ref Node Head) //작업이 끝나고 실행되므로 병행 수행을 고려하지 않습니다.
{
int cnt = 0;
while (Head != null)
{
cnt++;
Head = Head.nextNode;
}
return cnt;
}
static Node pop(ref Node Head)
{
if (Head == null)
return null;
Node orgVal = Head, newVal;
newVal = orgVal.nextNode;
Head = newVal;
orgVal.nextNode = null;
return orgVal;
}
static void push(ref Node Head, ref Node newVal)
{
Node orgVal = Head;
newVal.nextNode = orgVal;
Head = newVal;
}
static void ThreadBody()
{
Random r = new Random();
int n = r.Next(2, 10), m = r.Next(2, 10);
Console.WriteLine("Thread n : {0}, m : {1}", n, m);
int num = 100000;
while (--num >= 0)
{
for (int i = 0; i < n; i++) // Main 스레드와 병행 수행
{
mutex.WaitOne(); //mutex_lock()
Node nod = pop(ref freeList.Head);
mutex.ReleaseMutex(); //mutex_unlock()
if (nod != null)
{
mutex.WaitOne();
push(ref headList.Head, ref nod); //노드를 제거해 바로 push합니다.
mutex.ReleaseMutex();
}
}
for (int i = 0; i < m; i++) // Main 스레드와 병행 수행
{
mutex.WaitOne();
Node nod = pop(ref headList.Head);
mutex.ReleaseMutex();
if (nod != null)
{
mutex.WaitOne();
push(ref freeList.Head, ref nod); //노드를 제거해 바로 push합니다.
mutex.ReleaseMutex();
}
}
}
}
static void Main(string[] args)
{
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
Console.WriteLine("2019930019 이주호 운영체제 과제 3 (mutex)");
Console.WriteLine();
for (int i = 0; i < nodeCount; i++)
{
Node nod = new Node(i);
push(ref freeList.Head, ref nod);
}
Thread t1 = new Thread(ThreadBody);
Thread t2 = new Thread(ThreadBody);
t1.Start();
t2.Start();
t1.Join();
t2.Join();
Console.WriteLine("=========작업 종료=========");
int fn = nodes(ref freeList.Head);
int hn = nodes(ref headList.Head);
Console.WriteLine("freeList 노드의 수 : {0}", fn);
Console.WriteLine("headList 노드의 수 : {0}", hn);
Console.WriteLine("만든 노드의 수 : {0}", nodeCount);
Console.WriteLine("실제 노드의 수 : {0}", fn + hn);
stopwatch.Stop();
Console.WriteLine("수행 시간 : " + stopwatch.ElapsedMilliseconds + "ms");
}
}
}
실행 결과
pop과 push를 하는 데 있어서 상호 배제가 완전하게 보장되기 때문에 ABA문제는 발생하지 않습니다. 하지만 lock을 호출하는 것 자체가 많은 리소스를 요구하고, 딜레이를 발생시키기 때문에 성능이 많이 떨어집니다. 세부과제 2에서 해결했던 방식의 수행 시간은 다음과 같습니다.
다음과 같이 수행 시간이 크게 차이나는 것을 볼 수 있습니다.