[Algorithm 관련] Reverse singly linked list

http://cslibrary.stanford.edu/109/list.gif

http://cslibrary.stanford.edu/109/list.gif

링크드 리스트는 Singly Linked list와 Doubly Linked list 타입을 갖는 데이터 구조이다. Singly Linked list는 자신의 값과 자신의 다음의 Node의 레퍼런스를 가지는 구조이며, Doubly Linked list는 자신의 값과 자신의 전의 Node의 레퍼런스와 자신의 다음에 이어지는 Node의 레퍼런스를 가지는 구조이다. 한번의 연속된 메모리를 할당하지 않는 특성을 가졌지만, Traverse를 하기에 꽤 비싼 비용이 드는 데이터 구조임에 틀림 없다.

Singly Linked list에서 어떻게 하면 reverse를 시킬 수 있을 까? 이것이 오늘의 알고리즘의 문제이다.

Time Complexity를 O(n)으로 풀수 있는 iterative한 방법이다. 먼저, 세개의 node를 저장할 변수를 만든다. prvNode, crrNode, nextNode. crrNode가 nil 아닐 때 까지 Loop를 돈다. 그러면서 치환을 통해 리스트를 반대로 돌릴 수 있다. 다음은 Objective-C 코드이다.

  1. - (LLNode *)reverseLinkedList:(LLNode *)header
  2. {
  3.     if (header == nil) {
  4.         return nil;
  5.     }
  6.  
  7.     LLNode *prvNode = nil;
  8.     LLNode *crrNode = header;
  9.     LLNode *nextNode;
  10.  
  11.     while (crrNode != nil)
  12.     {
  13.         nextNode = crrNode.next;
  14.         [crrNode setNext:prvNode];
  15.         prvNode = crrNode;
  16.         crrNode = nextNode;
  17.     }
  18.  
  19.     return prvNode;
  20. }

[Algorithm 관련] 순열 Permutation -Recursively-

신발 끈을 묶는 방법을 글로 쓰라고 하면 써볼 수 있겠는가? 저자는 자신이 없다. 글 재주가 없어서 그럴수도 있고 혹은 손에 익은 기술을 한번도 말로 표현해보려 하지 않아서 일지도 모른다. 순열, 즉 permutation 알고리즘 문제가 저자한테는 같은 느낌이다. 종이 위에 써보라고 하면 큰 어려움 없이 써 내려 갈수 있지만 막상 pseudo 코드나 과정을 설명하는 글을 써보라고 하면 자신이 없다.

먼저 permutation가 무엇인지 알아보자. 영어로 anagram이라고 표현하는 것도 보았다. 간단한 예를 들어 설명을 하자면 ‘ABC’의 순열은 다음과 같다.

ABC, ACB, BAC, BCA, CAB, CBA

알파벳 순서를 바꾸어서 만들어 낼 수 있는 String들을 말한다. 참고로 n개의 알파벳의 permutation 수는 n! 이다. 위 예는 알파벳 수가 3개이므로 3 * 2 * 1 = 6개의 조합이 나올 수 있다. Permutation을 구하기 위한 가장 쉬운 방법은 ‘각각의 알파벳 하나씩을 시작으로 하는 permutation’의 조합을 찾으면 된다. 무슨 말인지 모르겠다면 다음를 한번 살펴보자:

for(each possible starting letter) {list all permutation that start with that letter}

for 반복문 (각가의 처음에 시작 가능한 글자들) {해당 글자로 시작하는 모든 순열 리스트}

보통 재귀함수를 사용할 때는 for문과 같은 반복문을 사용하지 않는다. 왜냐하면 재귀적 호출 자체가 반복하는 것이기 때문이다. 하지만 permutation 문제에서는 예외라고 할 수있다. 시작 가능한 각각의 글자를 반복 문으로 돌면서 그 속안에서는 해당 글자로 시작하는 모든 순열을 재귀적 호출로 만들어 내는 것이다.

재귀적 함수의 기본으로는 기본 조건(Base condition)이라는 것이 있다. 이것은 무한 반복이 되지 안도록 탈출구를 만들어 놓은 것인데, 해당 알고리즘에서도 for 반목문을 사용하지만 동일하게 base condition이 존재해야한다.

  1. // Pre-condition: str is a valid C String, and k is non-negative
  2. //                            and less than or equal to the length of str.
  3. // Post-condition: All of the permutations of str with the first k
  4. //                             characters fixed in their original positions
  5. //                             are printed. Namely, if n is the length of str,
  6. //                             then (n-k)! permutations are printed.
  7. void RecursivePermute(char str[], int k);
  8.  
  9. for (j=k; j<strlen(str); j++) {
  10.     ExchangeCharacters(str, k, j);
  11.     RecursivePermute(str, k+1);
  12.     ExchangeCharacters(str, j, k);
  13. }

위 Pseudo 코드를 살펴 보면 k라는 non-negative 인수가 있다. 이것은 첫 번째 글자의 인덱스를 저장한 parameter이다. 반복문을 돌면서 permutation을 구할 때는 자리를 바꾸면서 구할 것이고, k 값이 str의 길이와 같으면  출력을 하고 끝낼 것이다.

  1. void RecursivePermute(char str[], int k) {
  2.  
  3.      int j;
  4.  
  5.      // Base-case: All fixed, so print str.
  6.      if (k == strlen(str))
  7.          printf("%s\n", str);
  8.  
  9.      else {
  10.  
  11.          // Try each letter in spot j.
  12.          for (j=k; j<strlen(str); j++) {
  13.  
  14.              // Place next letter in spot k.
  15.              ExchangeCharacters(str, k, j);
  16.  
  17.              // Print all with spot k fixed.
  18.              RecursivePermute(str, k+1);
  19.  
  20.              // Put the old char back.
  21.              ExchangeCharacters(str, j, k);
  22.          }
  23.      }
  24. }

위 코드는 c 코드이다.

  1. @implementation ViewController
  2.  
  3. - (void)viewDidLoad {
  4.     [super viewDidLoad];
  5.  
  6.     [self printPermutation:@"abc"];
  7. }
  8.  
  9. - (void)didReceiveMemoryWarning {
  10.     [super didReceiveMemoryWarning];
  11.     // Dispose of any resources that can be recreated.
  12. }
  13.  
  14. #pragma mark – Private methods
  15.  
  16. - (void)printPermutation:(NSString *)str
  17. {
  18.     [self permutationHelper:str index:0];
  19. }
  20.  
  21. - (void)permutationHelper:(NSString *)str index:(NSInteger)k
  22. {
  23.     if (str.length == k) {
  24.         NSLog(@"%@", str);
  25.         return;
  26.     }
  27.  
  28.     NSInteger idx;
  29.  
  30.     for (idx = k; idx < str.length; idx++)
  31.     {
  32.         NSString *swappedStr = [self swapString:str onIndex:idx withNewIndex:k];
  33.         [self permutationHelper:swappedStr index:k+1];
  34.     }
  35. }
  36.  
  37. - (NSString *)swapString:(NSString *)str onIndex:(NSInteger)idx withNewIndex:(NSInteger)k
  38. {
  39.     unichar charForIdx = [str characterAtIndex:idx];
  40.     unichar charForK = [str characterAtIndex:k];
  41.  
  42.     NSString *strForK = [NSString stringWithCharacters:&charForK length:1];
  43.     NSString *tmpStr = [str stringByReplacingCharactersInRange:NSMakeRange(idx, 1)
  44.                                                     withString:strForK];
  45.  
  46.     NSString *strForIdx = [NSString stringWithCharacters:&charForIdx length:1];
  47.     return [[tmpStr stringByReplacingCharactersInRange:NSMakeRange(k, 1)
  48.                                  withString:strForIdx] copy];
  49. }
  50.  
  51. @end

Objective-C 코드이다.

 

[Obj-C] 개체 복사하기 – NSCopying -

Objective-C에서 클래스 인스턴스를 복사할 때 구현 되어 있어야 하는 Protocol은 NSCopying이다. 해당 Protocol은 하나의 인터페이스를 제공한다.

  1. - (id)copyWithZone:(NSZone *)zone

여기에서 Zone은 메모리에 있는 데이터의 Segment들이 있는 구역을 뜻한다. 옛날 그 어느날에는 memory segment를 특정 영역에 생성하여 관래했다고 한다. 하지만 꽤 오래전 부터 사용하지 않는 기술이다. 지금은 모든 앱은 하나의 Zone을 가지고 있다. 그러므로 인수 값인 zone에 대해서 크게 신경 쓰지 말고 기본적으로 무엇인지에 대해서만 인지하고 있으면 될 것이다.

보통 개발을 하다가 복사를 하고 싶으면 NSObject에 있는 copy 메서드를 사용하거나 mutableCopy를 사용하여 mutable 개체를 복사하고 있을 것이다. 사용자가 정의한 개체 복사를 위해는 NSObject의 copy나 mutableCopy 메서드를 override해서 사용하면 안된다. Copy 메서드가 호출하는 copyWithZone: 메서드를 override해서 사용해야 한다.

  1. #import <Foundation/Foundation.h>
  2.  
  3. @interface EOCPerson : NSObject <NSCopying>
  4.  
  5. @property (nonatomic, copy, readonly) NSString *firstName;
  6. @property (nonatomic, copy, readonly) NSString *lastName;
  7.  
  8. - (id)initWithFirstName:(NSString*)firstName
  9.             andLastName:(NSString*)lastName;
  10.  
  11. - (void)addFriend:(EOCPerson*)person;
  12. - (void)removeFriend:(EOCPerson*)person;
  13.  
  14. @end
  15.  
  16. @implementation EOCPerson {
  17.     NSMutableSet *_friends;
  18. }
  19.  
  20. - (id)initWithFirstName:(NSString*)firstName
  21.             andLastName:(NSString*)lastName {
  22.     if ((self = [super init])) {
  23.         _firstName = [firstName copy];
  24.         _lastName = [lastName copy];
  25.         _friends = [NSMutableSet new];
  26.     }
  27.     return self;
  28. }
  29.  
  30. - (void)addFriend:(EOCPerson*)person {
  31.     [_friends addObject:person];
  32. }
  33.  
  34. - (void)removeFriend:(EOCPerson*)person {
  35.     [_friends removeObject:person];
  36. }
  37.  
  38. - (id)copyWithZone:(NSZone*)zone {
  39.     EOCPerson *copy = [[[self class] allocWithZone:zone]
  40.                        initWithFirstName:_firstName
  41.                              andLastName:_lastName];
  42.     copy->_friends = [_friends mutableCopy];
  43.     return copy;
  44. }
  45.  
  46. @end

위 코드에서 copyWithZone: 메서드의 copy->_friends를 주목하자. _friends는 internal 인스턴스이기 때문에 -> 문법을 사용했음을 기억하자.

복사 개념에는 ‘Shallow Copy’(얕은 복사)와 ‘Deep Copy’(깊은 복사)가 있다. 얕은 복사란 인스턴스 프로퍼티로 Collection 타입의 개체가 있을 때 컨테이너는 복사를 하되 속의 있는 내용물은 기존 컨테이너가 가지고 있던 레퍼런스를 포인트하고 있는 개념이다. 깊은 복사는 말 그대로 클론을 하나 만들어서 새로운 메모리 영역에 올리는 것을 뜻한다.  NSCopying는 기본적으로 얕은 복사를 한다. 그러므로 깊은 복사를 하기 위해서는 추가적인 조취가 필요하다.

Effective Objective-C 2.0 Matt Galloway

Effective Objective-C 2.0 Matt Galloway

위 사진을 보면 얕은 복사는 컨테이너는 복사가 되었지만 내용물은 원본 개체의 내용물을 가르키고 있는 것을 볼 수있다. 반면 깊은 복사는 클론을 만들어 낸 것을 볼수 있다.

  1. - (id)deepCopy {
  2.     EOCPerson *copy = [[[self class] alloc]
  3.                        initWithFirstName:_firstName
  4.                              andLastName:_lastName];
  5.     copy->_friends = [[NSMutableSet alloc] initWithSet:_friends
  6.                                              copyItems:YES];
  7.     return copy;
  8. }

NSMutableSet의 initWithSet:copyItems: 생성자를 통해서 깊은 복사를 할 수 있다.

[Multi-Thread 프로그래밍] Swift에서 GCD 사용하기

몇해 전 Apple은 NSOperation과 동시에 멀티스레드 환경에서 작업할 수 있게 해주는 GCD 매카니즘을 시장에 내놓았다. iOS라는 기존 컴퓨터와 다른 특별한 환경에서 요구되는 빠른 반응성을 위해 무거운 과업을 Main Thread Queue가 아닌 Background thread Queue에서 실행해야만 한다. 이때 NSOperation 기술보다는 블록을 사용한 GCD가 더 가독성 높은 코드를 만들어 낼 수있기 때문에 많은 개발자의 사랑을 받고 있는 것 같다.

해당 블로그 포스트는 기본적인 멀티 스레드에 대한 개념과 GCD 라이브러리들에 대한 내용을 담을 것이다. 또한 본 포스트는 self-study에 대한 복습 정도의 메모를 주목적으로 하고 있기 때문에 자세한 설명이 없다면 댓글를 통해 문의 바란다.

멀티 스레딩의 기본 개념

  • 순차적(Serial) VS 동시적(Concurrent)

한 과업(Task)이 여러 과업들 중에 한번에 한개씩 실행된다면 ‘순차적(Serially)’ 진행이라 하고, 동시에 여러 과업이 동시에 실행이 된다면 ‘동시적(concurrently)’ 진행이다.

  • 과업 (Task)

이 글에서 설명하는 과업이란 Micro하게 보자면 오브젝티스-C에서는 ‘Block’으로 표현할 수 있고, Swift로 말하자면 ‘Closure’가 될 것이다. 블럭은 하나의 과업을 구현하고자 하는 코드 묶음이라고 할 수 있겠다. 그런데 이 블럭이나 클러져는 메서드의 파라미터나 인자, 혹은 클래스 인스턴스 Property가 되어 이곳 저곳으로 모듈화하여 사용되어 질 수 있다.

  • 동기식(Synchronous) VS 비동기식(Asynchronous)

동기식과 비동기식은 기본적으로 언제 과업을 호출한 곳에서 다음 코드 진행에 관한 컨트롤 권한을 넘겨 줄 것인가에 대한 개념이다. 예를 동기식은 자신의 과업 (여기에서 클러져나 블럭으로 표현되어 질 수 있다.)이 다 끝나고 코드 진행을 시키기 위해 컨트롤 권한을 준다면 ‘동기식’이고, 자신의 과업이 혹은 블럭이 다 완료 되지 않은 상황 가운데, 다음 코드로 넘어가게 한다면 비동기식일 것이다.

  • 임계구역 (Critical Section)

이 개념은 반드시 동시에 실행되어서는 안될 코드 구역을 말하는 것이다. 멀티 스레드 프로그래밍에서 공유자원을 사용할 때 여러 스레드에서 동시에 접근할 수 있는 위험성 있는 지역을 보호하는 개념이다.

  • 경합 조건(Race Condition)

멀티 스레드 프로그래밍에서 두 명령어가 동시에 같은 기억 장소를 접근하고자 할때 그들 사이의 경쟁에 의해 수행 결과를 예측할 수 없게 되는 것인데, 이와 같은 현상은 바람직하지 않으므로 OS에서 이것을 해소해주어야 할 것이다. 출처

  • 교착상태 (Deadlock)

한개 이상의 스레드에서 서로가 필요한 작업이나 리소스를 기다리는 상태이다. 예를 들어 첫번째 스레드가 두번째 스레드가 끝나야 일을 진행 할 수 있고, 두번째 스레드는 첫번째 스레드가 끝나야 일을 진행 할 수 있는 경우이다. 이런 경우에는 이도저도 못하는 교착상태에 빠져 버린다.

  • 스레드 세이프 (Thread Safe)

스레드 세이프한 코드는 멀티 스레드나 동시 과업 환경에서 아무런 문제 없이 호출 되어지고 실행가능한 코드를 말한다. Swift 언어의 let으로 시작하는 변수가 ‘스레드 세이프’하다고 할 수 있겠다. 초기화 할때 정해진 값이 끝까지 변하지 않기 때문이다. 반대로 var로 시작하는 변수는 ‘스레드 세이프’하지 않다. 멀티 스레드 환경에서 언제든지 읽혀지고 쓰여질 수 있기 때문이다.

  • 문맥 교환 (Context Switch)

한 프로세스 안에서 하나 이상의 스레드에서 다른 스레드로 작업환경을 변경하고자 할 때 저장과 불러오기의 과정을 문맥 교환이라고 한다. 문맥 교환이 잦아지면 성능의 문제가 있다. 최소화하는 것도 성능개선에 중요한 부분이다.

  • 동시성(Concurrency) VS 병렬성(Parallelism)

동시성은 두 개 이상의  과업이 시작, 실행, 완료등이 같은 시간대에서 행하여지는 것을 뜻한다. 그런데 주의 할 것은 두 과업이 반드시 같은 순간에 실행되는 것을 의미하지 않는다. 예를 들어, 싱글 코어 CPU에서 시간을 쪼개어 동시에 작업 중인 과업을 왔다갔다 하면서 연산한다. 반면 병렬성은 말그대로 동시에 과업을 수행하는 것을 뜻한다. 멀티 코어 CPU에서 가능하다.

출처. raywenderlich.com

출처. raywenderlich.com

Queue

GCD에서는 스레드 풀은 크게 두 가지 타입이 있는데, 순차적 큐와 동시적 큐이다. GCD를 사용하게 되면 스레드를 직접 생성 혹은 호출하여 사용하지 않는다. 스레드 풀인 큐에서 넣어 놓고 과업을 실행하게 되는데, 자신의 상황에 맞게 사용하기 위해서는 어떤 것들이 있는지 알아야 할 것이다.

  1. 순차적 큐(Serial Queue): 한번에 하나의 과업이 순차적으로 실행되어지는 스레드 큐를 뜻한다.  과업이 실행되는 순서는 FIFO(First In First Out)이다. GCD에서 dispatch_get_main_queue가 대표적인 순차적 큐이다. UI 작업은 메인 큐에서만 해야한다. 하지만 사용자 정의 순차적 큐도 만들 수 있다. 큐를 생성할 때는dispatch_queue_create(“com.bartysways.Project”, DISPATCH_QUEUE_SERIAL)와 같이 ‘DISPATCH_QUEUE_SERIAL’ 파라미터를 지정해주면 된다.
  2. 동시적 큐(Concurrent Queue): 동시적 큐는 비동기적인 작업을 할 때 사용하기에 알맞은 큐이다. 과업의 시작 순서는 전적으로 GCD가 판단을 하게 되어지는데, 어떤 코어에서 어떤 것을 먼저 실행하고 완료되어질지는 GCD와 과업의 종류에 따라 달렸다. dispatch_queue_create(“com.bartysways.Project”, DISPATCH_QUEUE_CONCURRENT).
출처: raywenderlich.com

출처: raywenderlich.com

Quality of Service

GCD에서 제공하는 QoS 클래스가 있다. 이 클래스는 GCD가 동시적 큐에서 과업의 우선순위를 정할 때 고려되어지는 클래스로써 과업의 의도를 추상화 하여 표현하여 네이밍을 하였다. QoS를 사용하여 GCD를 사용할 때의 장점은 각 디바이스 아키텍쳐에 맞는 환경을 시스템이 고려하여 멀티 스레딩을 효율적으로 해준다는 것에 있다. 물론 일일히 NSThread를 사용하여 관리 하여 코딩할 수 있지만, 많은 코딩과 많은 복잡도를 애플이 제공해주는 메카니즘에게 맡기고 그 혜택을 누릴 수 있는 것이다.

  • QOS_CLASS_USER_INTERACTIVE: 해당 클래스는 UI 업데이트를 위한 과업을 실행할 때 명시하는 클래스이다. 이 클래스를 사용하게 되면 과업은 순차적으로(동기식) 항상 Main Queue에서 실행된다.
  • QOS_CLASS_USER_INITIATED: 해당 클래스는 UI 이벤트를 통해 초기화 작업을 해야 할 때를 위해서 제공된다. 관련된 과업은 비동기식으로 실행된다. 예를 들어 사진 필터를 제공하는 기능이 있다고 가정을 하자, 원하는 필터 효과를 적용하기 위해서 버튼을 탭하고 해당 이미지를 필터에 맞는 효과를 적용할 때 필요한 과업을 해당 클래스를 지정하여 실행하면 효과적이다.
  • QOS_CLASS_UTILITY: 파일 I/O 작업이나 네트워킹 작업 같이 긴 시간을 필요로 하는 작업에 적당한 클래스이다.
  • QOS_CLASS_BACKGROUND: 이 클래스는 시간에 구애 받지 않고 사용자가 신경쓰지 않아도 되는 작업들을 백그라운드에서 실행하고자 할때 사용 되어지도록 디자인된 클래스이다. 예를 들어 로그아웃 시 로컬에 저장되어 있는 파일을 지워야 한다든지 혹은 이지미 파일을 다운로드 받은 후 캐싱을 한다든지 와 같은 작업을 할 때 적당할 것이다.

 

Practical Example

dispatch_async

  1. override func viewDidLoad(){
  2.    let queue = dispatch_get_global_queue(Int(QOS_CLASS_USER_INTERACTIVE.value), 0)
  3.    dispatch_async(queue){
  4.        println("First Block")
  5.    }
  6.    println("Second Block")
  7. }

위 코드의 실행 결과는 ‘Second Block’이 먼저 실행된 다음 ‘First Block’이 실행된다. 글로벌 큐에서 dispatch_async를 하게 되면, 클로져 안에 들어 있는 코드는 메인 큐가 아닌 글로벌 큐에 들어가서 자신의 순서가 되어 있을 때 실행되어진다. 여기에서 말하는 글로벌 큐는 메인 큐가 메인 스레드를 뜻한다면, 새로운 스레드를 뜻하는데 소위 백그라운드 스레드라고 해도 무관할 것이다. (참고로 글로벌 큐는 해당 디바이스의 CPU 코어 갯수에 따라 갯수가 정해진다.)

dispatch_sync

  1. override func viewDidLoad(){
  2.     super.viewDidLoad()
  3.  
  4.    let queue = dispatch_get_global_queue(Int(QOS_CLASS_USER_INTERACTIVE.value), 0)
  5.    dispatch_sync(queue){
  6.        println("First Block")
  7.    }
  8.    println("Second Block")
  9. }

위 코드의 실행 결과는 ‘First Block’, ‘Second Block’ 순으로 실행이 된다. 물론 메인 큐가 아닌 글로벌 큐에서 작업이 실행 되지만, 해당 클로저의 코드가 다 끝나기 전까지 메인 스레드에게 통제권을 넘기지 않는다.

dispatch_after

  1. func executeDelay() {
  2.  
  3.     let delayInSeconds = 3.0
  4.     let popTime = dispatch_time(DISPATCH_TIME_NOW, Int64(delayInSeconds * Double(NSEC_PER_SEC)))
  5.     let queue = dispatch_get_main_queue()
  6.  
  7.     dispatch_after(popTime, queue) {
  8.         println("Bang! Bang! Bang!")
  9.     }
  10.   }

위 코드는 3초 후에 클로져의 코드가 실행된다.

dispatch_once

  1. private var signalOnceToken = dispatch_once_t()
  2.  
  3.   override func viewDidLoad() {
  4.     super.viewDidLoad()
  5.  
  6.     dispatch_once(&signalOnceToken) {
  7.         println("Just one time!")
  8.     }
  9. }

dispatch_once는 프로세스가 떠 있는 동안 한번만 실행했으면 할 때 사용을 한다. 싱글톤 패턴을 구사 할 때 사용해도 무관하다.

Readers and Writers 문제 핸들링

dispatch_barrier_async

GCD의 barriers API를 ‘동시적큐’에서 사용하면 관련 과업은 타과업과 동시에 실행되지 않고 단독 독점을 하여 실행하게 된다. 이 API를 사용하여 읽기 작업이나 쓰기 작업을 한다면 두 개 이상의 Task에서 동시 접근을 막을 수 있게 된다.

  1. private let concurrentPhotoQueue = dispatch_queue_create(
  2.     "com.raywenderlich.GooglyPuff.photoQueue", DISPATCH_QUEUE_CONCURRENT)
  3.  
  4. func addPhoto(photo: Photo) {
  5.  
  6.   dispatch_barrier_async(concurrentPhotoQueue) {
  7.  
  8.     self._photos.append(photo)
  9.  
  10.     dispatch_async(GlobalMainQueue) {
  11.       self.postContentAddedNotification()
  12.     }
  13.   }
  14. }

위 예제에서 ‘_photos’ Array 개체에 새로운 값을 넣어 줄 때, dispatch_barrier_async 함수를 사용한다면 스레드 안전하게 실행할 수 있게 된다.

Screen Shot 2015-07-16 at 4.47.45 PM

위 그림을 살펴보자. 동시적큐에서 여러 과업이 병렬되어 실행되고 있는 모습을 볼 수 있다. 그런데 ‘Barrier Task’ 블럭을 보면 단독적으로 시간을 보내는 모습을 볼 수 있다.

Dispatch Apply && Dispatch Groups

Dispatch group은 그룹의 묶음으로 지정된 과업이 다 마쳤을 때 notify해주는 기능을 가지고 있다. 실예로 iOS 프로젝트에서 UITableView를 사용할 때 화면에 보이는 각 cell마다 thumbnail 이미지를 다운로드 과업들이 다 끝났을 때 알림을 받고 싶다면 해당 API를 써서 구현할 수 있다. 아래 예제를 보고 확인해보자.

  • dispatch_apply: for 반복문 처럼 동작한다.
  • dispatch_group_create:
  • dispatch_group_enter
  • dispatch_group_leave
  • dispatch_group_wait
  • dispatch_group_notify: 비동기식으로 그룹이 들어온 만큼 다 나가면 디스패치 된다.

  1. func downloadWithCompletion(completion: DownloadingCompletionClosure?) {
  2.  
  3.     var storedError: NSError?
  4.     var downloadGroup = dispatch_group_create()
  5.     let addresses = ["http://www.....", "http://www.....", "http://www....."]
  6.     let queue = dispatch_get_global_queue(Int(QOS_CLASS_USER_INITIATED.value), 0)
  7.  
  8.     //#1 다운로드 반복 구문
  9.     dispatch_apply(addresses.count, queue) { (i: Int) -> Void in
  10.  
  11.       let address = addresses[i]
  12.       let url = NSURL(string: address)
  13.  
  14.       dispatch_group_enter(downloadGroup)
  15.  
  16.       let item = Download(url: url!) {
  17.         image, error in
  18.         if error != nil {
  19.           storedError = error
  20.         }
  21.         dispatch_group_leave(downloadGroup)
  22.       }
  23.       ItemManager.sharedManager.addItem(item)
  24.     }
  25.  
  26.     //#2 다운로드 완료시 실행되는 부분
  27.     dispatch_group_notify(downloadGroup, GlobalMainQueue){
  28.  
  29.       if let completion = completion {
  30.         completion(error: storedError)
  31.       }
  32.     }
  33.   }

Dispatch Block

iOS8에서 새로 추가된 Dispatch Block은 기존에 사용하던 클로져와 같은 개념이나 추가된 기능을 포함하고 있다. QoS와 같은 큐안에서 우선순위를 정할 수 있는 기능이 추가 되었으며, 무엇 보다도 취소(Cancelable) 가능해졌다. 하지만 기억해둬야 할 점은 취소라는 기능이 뜻하는 것은 대기중인 과업이 큐에서 빼주는 것을 의미한다. 그러므로 만약 과업이 자기 차례가 돌아와 벌써 실행이 시작되었으면 과업은 끝까지 실행을 하고 말것이다.

  • dispatch_block_create
  • dispatch_block_cancel

  1. //#1. dispatch_block을 사용해 dispatch_async 사용하기
  2. let queue = dispatch_get_global_queue(Int(QOS_CLASS_USER_INITIATED.value), 0)
  3. let block = dispatch_block_create(DISPATCH_BLOCK_INHERIT_QOS_CLASS){
  4.     println("Hello")
  5. }
  6. dispatch_async(queue, block)
  7. .
  8. .
  9. .
  10. //#2. 취소하기
  11. dispatch_block_cancel(block)

GCD Testing

GCD는 멀티스레드 프로그래밍을 보다 쉽고 효율적으로 관리 실행해주게끔 도와주는 것 이상으로 단위 테스트를 할 때도 유용하게 사용할 수 있다. 예를 들어 비동기식 서버통신을 테스트를 할 땐 GCD에서 재공하는 Semaphore나 XCTest 프레임 워크에서 제공하는 XCTestExpectation을 통해서 테스트할 수있다. 필자는 해당 기능이 소개되기 전 비동기식 서버통신에 관련된 단위 테스트를 짜기위해 여러가지 고민했던 기억이 난다. 그때 당시 내린 결론은 비동기식 단위 테스트는 불가능하니 서버 통신이 가지고 올 수있는 모든 단위 케이스들을 테스트했던 기억이 난다. 아무튼 비동기식 단위 테스트를 어떻게 할 수 있는지 살펴보자.

  • Semaphores: 프로세스간 메세지 전송을 하거나, 혹은 공유 자원을 통해서 특정 data를 공유하게 될 경우 발생하는 문제는, 공유된 자원에 여러개의 프로세스가 동시에 접근을 하면서 발생한다. 단지 한번에 하나의 프로세스만 접근 가능하도록 만들어 줘야 하고, 이때 세마포어를 쓴다. 출처 보통 스레드 차원에서는 뮤텍스, 프로세스 차원에서는 세마포어를 통해 멀티 스레드 환경에서 개발하게 된다.
  • expectation: XCTest 프래임워크에서 비동기식 코드를 테스트할 수 있겠금 제공해주는 방법이다.

Semaphores

세마포어는 한 공유자원에 접근할 수 있는 Thread의 수를 정의 해놓고, 접근을 제어하는 도구이다. 보통 ‘뮤텍스랑 세마포어’를 비교할 때는 화장실 예를 사용한다. 화장실를 사용하기 위해서는 화장실 열쇠가 있어야 한다. 뮤텍스는 하나의 열쇠를 가지고 화장실 전체를 사용할 수있는데, 만약 앞사람이 사용중이라면, 다른 사용자의 접근을 차단하고 사용이 끝나면 다른 대기자가 사용을 할수 있도록 허용하는 방식이라고 할 수있다. 반면 세마포어는 뮤텍스와 맞찬가지로 화장실을 사용하기 위해서는 열쇠가 필요한데, 각 비어있는 칸마다 열쇠를 나누어주고 화장실 입구 지키미가 접근을 관리하는 방식이다. 만약 남은 열쇠가 없다면 대기해야 한다.

자 그럼, GCD를 사용하여 Semaphore를 사용하는 방법을 알아보자.

  1. func downloadImageURLWithString(urlString: String) {
  2.     let url = NSURL(string: urlString)
  3.     let semaphore = dispatch_semaphore_create(0) // 1
  4.     let photo = DownloadPhoto(url: url!) {
  5.       image, error in
  6.       if let error = error {
  7.         XCTFail("\(urlString) failed. \(error.localizedDescription)")
  8.       }
  9.       dispatch_semaphore_signal(semaphore) // 2
  10.     }
  11.  
  12.     let timeout = dispatch_time(DISPATCH_TIME_NOW, DefaultTimeoutLengthInNanoSeconds)
  13.     if dispatch_semaphore_wait(semaphore, timeout) != 0 { // 3
  14.       XCTFail("\(urlString) timed out")
  15.     }
  16. }

차단을 원하는 자원에 대해서 서메포어를 생성하면 해당자원을 가르키는 세마포어 값이 할당된다. 이 값이 0이면, 다른 프로세스는 해당 자원에 접근할 수 없고, 0 보다 크면 해당 자원에 접근할 수 있는 개념이다. dispatch_semaphore_create(0)을 통해서 세마포어 개체를 초기화하고, 과업이 다 끝나면 dispatch_semaphore_signal(semaphore)를 통해서 다른 프로세스의 접근을 허용할 수 있겠금 신호를 보내준다. dispatch_semaphore_wait(semaphore, timeout)를 통해서 코드 진행을 정해진 시간만큼 블럭해준다.

expectation

XCTest에서 제공해주는 메카니즘으로 expectation 개체를 생성하고 작업이 다 끝나 해당 개체의 fulfill()이 불려지기 전까지 코드 진행을 멈춰서 기다리게 하는 방법이다. 예제 코드는 다음과 같다.

  1. func downloadImageURLWithString(urlString: String) {
  2.   let url = NSURL(string: urlString)
  3.   let downloadExpectation = expectationWithDescription("Image downloaded from \(urlString)") // 1
  4.   let photo = DownloadPhoto(url: url!) {
  5.     image, error in
  6.     if let error = error {
  7.       XCTFail("\(urlString) failed. \(error.localizedDescription)")
  8.     }
  9.     downloadExpectation.fulfill() // 2
  10.   }
  11.  
  12.   waitForExpectationsWithTimeout(10) { // 3
  13.     error in
  14.     if let error = error {
  15.       XCTFail(error.localizedDescription)
  16.     }
  17.   }
  18. }

문서 History

Update: 2015-09-15

Dispatch Group에 대한 간략한 설명 추가.