OS

프로세스와 스레드의 비교 분석: k-means 알고리즘을 활용한 성능 평가

bit주세요 2024. 1. 26. 16:52

프로세스와 스레드는 기본적이면서도 핵심적인 개념입니다. 이 두가지 개념은 시스템 자원을 활용하는 방식과 멀티태스킹을 수행하는 방법에 있어 근본적인 차이를 갖고 있습니다.

프로세스는 독립적인 메모리 공간을 갖는 실행중인 인스턴스이며, 스레드는 프로세스 내에서 실행되는 실행 단위입니다. 프로젝트의 목표는 두 개념을 명확히 구분하고, 각각이 가지는 특징을 실험을 통해 심층적으로 이해하는 것입니다. 이를 위해, JVM 환경에서 k-means 클러스터 알고리즘을 활용하여 싱글 스레드, 멀티 스레드, 멀티 프로세스의 세 가지 구현을 통해 성능과 효율성을 분석합니다. 이러한 분석을 통해, 프로세스와 스레드가 소프트웨어 성능에 미치는 영향을 구체적으로 파악하고, 각각의 사용 상황에 대한 이해를 높이고자 합니다.

 

OS-lab 에서 코드를 확인하실 수 있습니다.

K-means 알고리즘 개요

k-means 알고리즘은 데이터 포인트들을 K개의 그룹으로 분류하는 것으로, 여기서 K는 사용자가 사전에 정한 그룹의 수 입니다.

 

알고리즘은 다음과 같습니다:

  • 초기화: 먼저, K개의 초기 '중심점(centroids)'을 무작위로 선택합니다. 이 중심점들은 각 클러스터의 중심을 나타냅니다.
  • 할당: 각 데이터 포인트를 가장 가까운 중심점에 할당하여 그룹을 형성합니다. '가까운' 기준은 이 프로젝트에서 유클리드 거리로 측정합니다.
  • 업데이트: 각 클러스터의 중심점을 재계산하여 클러스터의 평균 위치로 이동시킵니다.
  • 반복: 할당과업데이트과정을클러스터의할당이변경되지않거나특정반복횟수에도달할때까지반복합니다.

이것을 그림으로 보면 다음과 같습니다.

 

해당 프로젝트에서 k-means 알고리즘이 갖는 의미는 2가지 정도가 있습니다

1. 많은 연산량

각 반복에서 모든 데이터 포인트에 대한 클러스터와 중심점을 계산하기 때문에 알고리즘의 복잡도에 영향을 주는 요소는  데이터포인트(N), 클러스터(K), 반복횟수(I) 세가지로 O(NKI)의 연산량을 가집니다.

2. 병렬처리 가능성

1) 클러스터 할당 : 각 데이터포인트는 독립적으로 클러스터 할당에 필요한 연산을 진행할 수 있습니다.

2) 중심점 계산 : 중심점은 해당 클러스터의 모든 데이터포인터를 기준으로 계산되므로 각 클러스터마다 독립적으로 수행 할 수 있습니다.

 

위 두가지 특성을 가지고 있어 병렬화 전략을 통해 성능을 향상시킬 수 있는 잠재력을 가집니다.

 

 

실험방법

동일한 조건을 위해 미리 생성해둔 dataPoints 파일을 사용하여 테스트했습니다. 성능의 측정은 파일을 읽고 dataPoints가 초기화 된 후를 기준으로 합니다.

싱글스레드

single thread 시나리오

Main Thread 에서 알고리즘을 동작시킵니다. 성능측정은 앞서 말씀 드린것 처럼 TestCase가 로드되고 초기화된 시점에서 진행되기 때문에 프로그램 시작과 동시에 생성되는 Main Thread의 생성비용은 측정되지 않습니다. 따라서 순수 알고리즘의 실행 시간만을 측정합니다.

멀티스레드

multi thread 시나리오

  • 스레드 생성 및 작업 범위 지정 : 테스트 케이스가 초기화된 후, 실행 파라미터에 따라 지정된 수만큼의 스레드를 생성합니다. 각 스레드는 dataPoints의 전체 크기를 고려하여 동일한 작업 범위를 가집니다.
  • 병렬 알고리즘 처리 : 생성된 스레드들은 각각 자신에게 할당된 파티션을 클러스터링합니다. 메인 스레드는 모든 스레드의 작업이 완료될 때까지 대기합니다.
  • 작업 완료 및 동기화 : 스레드의 작업 완료 기준은 스레드 수로 초기화된 CountDownLatch의 카운터가 0이 되는 순간입니다. 각 스레드가 작업을 마치면 CountDownLatch의 카운터를 감소시키며, 이 카운터가 0에 도달하면 모든 스레드의 작업이 완료된 것으로 판단 합니다. 지정된 횟수만큼 반복됩니다.
  • 데이터 공유 : 스레드 간에는 각 클러스터의 중심점인 centroid와 dataPoints가 공유되지만 각 스레드에서는 centorid의 값을 읽기만하고, dataPoints는 2차원 배열의 형태로 할당받은 파티션은 한개의 스레드만 접근하기 때문에 dataPoints를 클러스터링 하는데 잠금에 대한 비용은 없습니다.

멀티프로세스

프로세스간 IPC는 소켓을 사용했습니다.

  • 소켓 생성 및 연결: 메인 프로세스는 서브 프로세스 수에 맞춰 소켓을 생성하고, 각각의 서브 프로세스가 연결될 때까지 대기합니다. 서브 프로세스들은 메인 프로세스의 포트 정보를 받아 소켓 연결을 시도합니다.
  • 데이터 전송: 연결이 완료되면, 메인 프로세스는 각 서브 프로세스에 처리할 데이터인 dataPoints의 파티션과 클러스터 중심점(centroid) 정보를 전송합니다. dataPoints는 초기에 한 번만 전송되며, 이후에는 변경된 centroid 정보만 반복적으로 전송됩니다.
  • 작업 수행 및 반복: 서브 프로세스는 받은 데이터로 클러스터 연산을 수행합니다. 모든 프로세스의 작업이 완료되면, 메인 프로세스는 새로운 centroid를 계산하고, 이 과정을 지정된 횟수만큼 반복합니다.

서브 프로세수 만큼 스레드를 생성하여 IPC를 관리하지만 실제 클러스터 연산은 각 서브 프로세스에서 독립적으로 수행됩니다.

 

 

실험환경

아래의 테스트는 M1 프로세서 MacOS 환경에서 진행했습니다

Apple M1
hw.physicalcpu: 8
hw.logicalcpu: 8
hw.memsize: 8589934592

 

실험결과

데이터 크기에 따른 수행속도비교

가로 : 데이터 수 / 세로 : 수행속도

N의 크기를 1,000 ~ 100,000 까지 증가시키며 수행속도를 측정한 결과입니다 1000~10,000 까지는 N의 크기를 1,000 씩 증가시키고

10,000 ~ 100,000 까지는 10,000씩 증가시키며 측정 했습니다.

 

데이터의 수가 많아질수록 수행속도의 폭이 커져 그래프상에서 잘 보이진 않지만 N = 1000일때에 싱글스레드 > 멀티스레드 > 멀티프로세스 순으로 높은 성능을 보였고, 이후로는 멀티스레드 > 싱글스레드 > 멀티프로세스의 순으로 높은 성능을 보였습니다. 

N = 20,000 부근 이후 부터는 멀티 프로세스의 성능이 싱글스레드의 성능을 앞서면서 멀티 스레드 > 멀티 프로세스 > 싱글 스레드의 성능을 보입니다.

 

싱글스레드의 기울기가 가장 크고 멀티프로세스와 멀티 스레드는 비슷한 기울기를 보이며 평행합니다. 기울기는 성능의 저하를 의미합니다. 싱글스레드에서 데이터의 크기가 커질수록 가장 높은 성능저하를 보이고, 멀티 프로세스와 멀티 스레드에서의 성능저하는 비슷합니다.

프로세스와 스레드는 기울기가 비슷하지만 평행하는것은 프로세스의 생성비용,IPC 로인한 오버헤드가 스레드의 생성비용보다 큰것을 의미합니다.

CPU / Memory 사용량

아래는 N = 1,000,000으로 수행 했을때의 CPU, Memory 사용량입니다. VisualVM을 사용하여 측정했습니다. VisualVM, 과 터미널을 제외하고 종료가능한 프로세스를 모두 종료한 상태에서 99%의 idle 상태를 확보한 후 테스트를 진행했습니다.

싱글스레드

싱글스레드로 동작했을때 평균적으로 12.5%정도의 CPU를 사용했습니다. M1프로세서가 8개의 코어를 가지고 있기 때문에 정확하게 1/8 의 CPU 사용률을 갖습니다.

메모리 사용량은 125MB 안팎으로 알고리즘이 실행될수록 소폭 상승하는 모습을 확인할 수 있습니다.

멀티스레드

멀티 스레드 환경에서는 4스레드 환경에서 테스트를 진행했습니다. 메인스레드를 포함하면 총 5개의 스레드를 사용한 것인데 메인스레드에서는 별도의 연산을 진행하지않고 다른 스레드에게 계산을 위임하고 대기하기 때문에 실제로 가장 오랫동안 활성화 되는 스레드는 4개입니다.

43%~ 50% 정도의 CPU사용량을 보였습니다. 7%의 등락폭을 보이는 이유는 먼저 작업을 끝낸 스레드가 idle상태로 전환되는 원인이 가장 클 것으로 추측됩니다.

메모리 사용량은 싱글스레드 환경일 때와 유의미한 차이는 없었습니다.

멀티 프로세스

메인프로세스

서브 프로세스

 

메인 프로세스에서는 약 6퍼센트의 점유율을 보이고 서브 프로세스는 12퍼센트의 CPU점유율을 보이고 있습니다 서브프로세스는 이러한 프로세스가 4개 구동되고 있습니다. 스레드와 비교했을때 CPU 사용량 에서는 비슷한 양상을 보입니다.

 

하지만 메모리를 사용량에서 멀티스레드보다 높은 사용량을 보이고 VisualVM에서 CPU 사용률 1%미만의 GC는 내림되어 그래프상으로는 보이지 않지만 heap 메모리가 산 모양을 그리며 여러차례의 GC가 발생하는 모습을 보입니다.

 

프로세스간에는 직접적으로 메모리를 공유할 수 없기때문에 데이터를 복사하고 전송하는 과정에서 멀티스레드에 비해 큰 메모리 사용량을 보입니다.

 

실험결과 분석

싱글 스레드

  • 싱글 스레드는 리소스 오버헤드가 최소화되어 있습니다. 단일 실행 경로를 따르기 때문에 컨텍스트 전환 비용이 발생하지 않습니다.
  • 동기화나 데드락 문제가 없으며, 단일 실행 흐름으로 인해 디버깅이 용이합니다.
  • 멀티코어 환경에서 CPU 리소스의 전체 활용이 어렵습니다. 데이터의 병렬 처리가 불가능합니다.

멀티 스레드

  • 데이터를 병렬로 처리함으로써 성능이 향상됩니다. 멀티코어 환경에서 더욱 효과적입니다.
  • 프로세스에 비해 메모리와 리소스를 보다 효율적으로 공유합니다.
  • 리소스 공유, 동기화, 스레드 관리 및 스케줄링 등을 고려해야 하므로 싱글 스레드에 비해 복잡합니다.

멀티 프로세스

  • 각 프로세스는 독립적인 메모리 공간을 갖습니다.
  • 프로세스 간 통신은 상대적으로 높은 오버헤드와 자원 사용을 요구합니다.
  • 여러 프로세서에서 최대 코어를 사용하여 테스트할 경우, 멀티 스레드보다 뛰어난 성능을 보일 수 있습니다. 이는 멀티 프로세스의 수평적 확장 가능성을 의미합니다.

결론

이 실험을 통해 얻은 결론은 싱글 스레드, 멀티 스레드, 멀티 프로세스 모델 각각이 특정 조건과 환경에서 최적의 성능을 발휘할 수 있다는 점입니다.

싱글 스레드는 리소스 오버헤드가 적고 단순하지만, 데이터의 병렬 처리가 불가능하여 멀티코어 환경에서의 성능이 제한됩니다.

 

반면, 멀티 스레드는 병렬 처리를 통해 성능을 향상시키지만, 동기화와 최적화에서 복잡성을 수반합니다. 실제로 이 프로젝트를 진행할 때 가장많은 시간을 소요한부분도 이상적인 실험 결과를 위해 최적화를 진행하는 부분 이었습니다. 이과정이 직관적이지 않고 실제 성능개선을 보장하기도 쉽지 않기 때문에 복잡성은 배가 되는것 같습니다.

예를들어 이 프로젝트에서는 스레드에 파티션을 지정하여 값을 쓰도록해 Lock Free로 병렬처리를 할수 있도록 했고 Thread풀을 생성해서 thread를 재사용 했습니다. 결과만 두고보면 대단한 레시피가 있는것은 아니지만 알고리즘에 특성에맞는 최적화 방법을 찾는 과정이 직관적이지 않고 주변 지식을 요구하기 때문에 복잡도가 증가하는것 같습니다.

 

멀티 프로세스는 멀티 스레드와 비슷한 양상을 띄지만, 고립성을 제공하며, 확장 가능성이 뛰어나지만, 오버헤드와 리소스 사용에 제약이 있습니다. 따라서 애플리케이션의 요구 사항과 환경을 분석하여 적절한 모델을 선택해야 합니다.