자바 : Fork/Join framework

🚀 Fork/Join 정의 

여기를 공부하기 위해서 운영체제의 프로세스와 스레드 파트를 공부하였고, 자바의 스레드를 걸쳐 Fork/Join까지 나름 딥하게 이해하려고 공부를 해왔다. 우선 정의를 한번 살펴보자.
Fork/Join 프레임워크는 다중 프로세서의 이점을 이용하기 위해서 ExecutorService 인터페이스를 구현한다. 내부적인 동작 방식은 최대한 쪼개질 수 있을 때까지 쪼개져서 이런 작은 단위의 조각들이 회귀적으로 동작하게 되어있다. 알고리즘에서 우리가 흔히 "분할 정복"이라고 부르는 개념과 같다고 이해를 하면 좋을 것 같다. 
Fork/Join의 목적은 사용 가능한 모든 처리능력을 사용하여 프로그램의 수행능력을 향상하는 데에 있다.

즉 Fork/Join은 CPU를 더 쉽게, 효율적으로 사용하기 위해서 만들어졌다.

🚀 동작 방식

ExecutorService 인터페이스를 구현한 모든 것과 마찬가지로, 스레드 풀 안에서 개별 스레드들한테 업무를 분배하는 방식이다. 하지만 Work Stealing 알고리즘을 적용시킨 Fork/Join은 기존에 ExecutorService 인터페이스를 단순 구현한 것과는 다르게 동작하게 된다. 개별 스레드들이 좀 더 바쁜 스레드의 업무를 유휴 스레드가 일을 가져가면서 모든 스레드가 바쁘게 동작하는 방식이다.

🚀 Work stealing?

어떤 작업이 대기하고 있는 큐(Queue)가 있다고 할 때, 한쪽만 끝이 아니라 양쪽이 끝으로 인식되는 큐를 Dequeue라고 한다. 여러 개의 Dequeue에 작업이 나뉘어 어떤 일이 진행될 때 만약 하나의 Dequeue는 매우 바쁘고, 다른 Dequeue는 바쁘지 않을 때가 읽을 것도 이런 상황에서 할 일이 없는 Deque가 바쁜 Dequeue에 대기하고 있는 일을 가져가서 해 주는 것이라고 생각하면 된다. 아래의 그림을 보면 이해가 좀 더 쉬울 것이다.
이러한 Work streal이라는 개념이 Fork/Join이라는 것에는 기본적으로 포함되어 있다. 즉 Fork/Join을 사용하면 별도로 구현하지 않아도 된다는 뜻이다.

🚀 메서드

Fork/Join 기능은 java.util.concurrent 패키지의 RecursiveAction과 RecursiveTask라는 abstract 클래스를 사용해야 한다.
결론적으로 말하면 "~Action은 결과 리턴과, Generic이 없다." 정도의 차이가 있다. RecursiveTask 클래스는 <V>라는 타입으로 리턴된다. 

두 클래스 모두 ForkJoinTask를 상속받고 있는데 해당 클래스는 Serializable, Future <V>라는 인터페이스를 구현하였다. 여기서 Future라는 인터페이스는 "비동기적인 요청을 하고 응답을 기다릴 때 사용"된다.

Fork/Join 작업을 수행하려면 RecursiveTask 클래스나 RecursiveAction 클래스를 확장하여 개발하면 된다. 두 클래스 모두 compute()라는 메서드가 있고, 이 메서드가 재귀 호출되고, 연산을 수행한다.

원형	설명
public abstract class RecursiveAction extends ForkJoinTask<Void>	A recursive resultless ForkJoinTask. This class establishes conventions to parameterize resultless actions as Void ForkJoinTasks. Because null is the only valid value of type Void, methods such as join always return null upon completion.
public abstract class RecursiveTask<V> extends ForkJoinTask<V>	A recursive result-bearing ForkJoinTask.

 작업을 수행하는 클래스를 만든 후에는 ForkJoinPool 클래스를 사용하여 작업을 시작한다.

	Call from non-fork/join clients (Fork/Join 클라이언트 밖에서 호출)	Call from within fork/join computations (Fork/Join 클라이언트 내에서 호출)
Arrange async execution (비 동기적 호출 수행시)	execute(ForkJoinTask)	ForkJoinTask.fork()
Await and obtain result (호출 후 결과 대기)	invoke(ForkJoinTask)	ForkJoinTask.invoke()
Arrange exec and obtain Future (호출 후 Future 객체 수신)	submit(ForkJoinTask)	ForkJoinTask.fork() (ForkJoinTasks are Futures)

Fork/Join은 복잡한 연산을 여러 스레드에서 실행하기 위해서 만든 것이다. 즉 계산이 복잡하면 복잡할수록 Fork/Join의 효과는 크며, 계산을 수행하기 위해서 스레드를 관리할 필요가 없다는 것이 핵심이다.

🎯  예제

package com.study;
 
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask; 
 
class GetSum2 extends RecursiveTask<Long> {
 
    long from, to;
 
    public GetSum2(long from, long to) {
        this.from = from;
        this.to   = to;
    }
 
    @Override
    protected Long compute() {
 
        long gap = to - from;
 
        try {
            Thread.sleep(1000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
 
        log("From = " + from + " To = " + to);
 
        if(gap<=3) {
            long tempSum = 0;
            for(long loop = from; loop <= to; loop++) {
                tempSum += loop;
            }
            log("Return !! " + from + " ~ " + to + " = " + tempSum);
            return tempSum;
        }
 
        long middle = (from + to) / 2;
        GetSum2 sumPre = new GetSum2(from, middle);
        log("Pre      From = " + from + " To = " + middle);
        sumPre.fork();
        GetSum2 sumPost = new GetSum2((middle+1), to);
        log("Post     From = " + (middle + 1) + " To = " + to);
 
        return sumPost.compute() + (long)sumPre.join();
    }
 
    public void log(String message) {
        String threaName = Thread.currentThread().getName();
        System.out.println("[" + threaName + "] " + message);
    }
 
}
 
public class ForkJoin {
 
    static final ForkJoinPool mainPool = new ForkJoinPool();
 
    public static void main(String[] args) {
        ForkJoin sample = new ForkJoin();
        sample.calc2();
    } 
    
    public void calc2() {
        long from = 0;
        long to = 10;
 
        GetSum2 sum = new GetSum2(from, to);
        Long result = mainPool.invoke(sum);
        System.out.println("Fork Join : Total sum of " + from + " ~ " + to + " = " + result);
    }
}
 

ForkJoin클래스부터 살펴보면,
- ForkJoinPool 이라는 클래스의 객체를 생성한다.
- 계산을 수행할 GetSum2 클래스의 객체를 만든다.
- ForkJoinPool에 선언되어 있는 invoke()라는 메서드를 사용하여 계산을 수행하는 객체를 넘겨주면, 작업이 시작된다. 그리고 그 결과를 받는다.

결과

위의 설명을 읽고 결과를 본다면 쉽게 이해가 될 것이다. 이해가 안 된다면 아마 재귀 호출의 원리를 모를 수도 있을 것이다. 그래도 구동원리를 이미지화시켜보면서 마무리를 짓도록 하겠다.

🚀  마무리

자바를 하면서 Fork/Join이라는 개념은 처음 알게 되었다. 이렇게 하면서 드는 생각이 코딩 테스트 공부하면서 한번 백준에서 적용해보고 싶은 궁금증이 생겼다.

 

참고자료

- [교재] 자바의 신 (이상민 저)

- https://docs.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html

- https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ExecutorService.html 

- https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/RecursiveAction.html

- https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/RecursiveTask.html

- https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ForkJoinPool.html