if let leader = classmate.firstIndex(of: classmate.max()!) {
    print(leader+1)
}

Set에서 가장 많은 수의 인덱스 찾기

//[Set([1, 2]), Set([0, 2]), Set([1, 4, 3, 0]), Set([2]), Set([2])]

let classmateCount = classmate.map { $0.count }
if let leader = classmateCount.firstIndex(of: classmateCount.max()!) {
    print(leader+1)
}

먼저 map 이용해서 배열로 바꾸기!

그러면 배열에서 가장 큰 수의 인덱스 찾는거랑 똑같음!!

Split 활용

....X
..XX.
.....
.XX..
X....

for i in 0..<n {
    let splitRow = room[i].split(separator: "X").map { $0.count }
    let splitCol = room.map({ $0[i] }).split(separator: "X").map { $0.count }
}

row기준으로 나누기, col기준으로 나누기 이렇게 하면 됨

배열에서 값 찾기

var frame = [(Int, Int, Int)]() // (학생 번호, 추천 횟수, 게시된 시간)

for r in recommend {    
    if let index = frame.firstIndex(where: { $0.0 == r }) {
        frame[index].1 += 1
}

firstIndex, where

배열에서 가장 작은 값 찾기 (min)

 let minRecommend = frame.min(by: { $0.1 < $1.1 })!.1

min, by

print

print(frame.map { $0.0 }.sorted().map { String($0) }.joined(separator: " "))
// [(Int, Int, Int)]() 여기서 첫번째 값 기준으로 sort -> map -> joined

입력 값의 크기를 줄이는 방법(?)

만약에 어떤 값을 입력 받았을 때 그 값이 중복이지 않아도 될 때

readLine()!.split(separator: " ").map { Int($0)! }

Set(readLine()!.split(separator: " ").map { Int($0)! })

처음걸로 contains하면 O(n), Set으로 변환하면 O(1)로 줄어든다.

for문 거꾸로

for i in stride(from: n-1, through: 0, by: -1)

through ~까지

2차원 배열 내부의 특정 값의 개수 구하기

let result = cloudInfo.flatMap { $0 }.filter { $0 == k }.count

cloudInfo라는 2차원 배열을 flatMap해서 하나로 만들어준 다음

2차원 배열 내부 요소 더하기

print(map.flatMap { $0 }.reduce(0, +))

배열 일부 구간 제거

var numbers = [1,2,3,4,5,6]
numbers.removeSubrange(1..<4) // 인덱스 1,2,3 범위의 값을 제거한다.
print(numbers) // [1,5,6]

옆으로 출력

print(index+1, terminator: " ")

병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬하는 방식으로 동작합니다. 이 과정은 재귀적으로 구현됩니다.

병합 정렬의 동작과정

병합 정렬의 시간복잡도

선택 정렬의 시간복잡도는 O(NlogN)이다. 분할 과정이 한 번 시행할 때마다 리스트의 크기가 1/2씩 감소하기 때문이다.

병합 정렬 코드 (Swift)

func mergeSort(_ arr: [Int]) -> [Int] {
    if arr.count <= 1 { return arr }

    let mid = arr.count / 2
    let leftArr = Array(arr[0..<mid])
    let rightArr = Array(arr[mid..<arr.count])

    let sortedLeftArr = mergeSort(leftArr)
    let sortedRightArr = mergeSort(rightArr)

    return merge(sortedLeftArr, sortedRightArr)
}

func merge(_ left: [Int], _ right: [Int]) -> [Int] {
    var left = left
    var right = right
    var res: [Int] = []

    while !left.isEmpty && !right.isEmpty {
        if left[0] < right[0] {
            res.append(left.removeFirst())
        } else {
            res.append(right.removeFirst())
        }
    }

    if !left.isEmpty {
        res.append(contentsOf: left)
    }

    if !right.isEmpty {
        res.append(contentsOf: right)
    }
    return res
}

let arr = [8, 3, 4, 7, 1, 5, 9, 2]
print(mergeSort(arr))

선택정렬은 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬입니다.

선택 정렬의 동작과정

선택 정렬의 시간복잡도

선택 정렬의 시간복잡도는 O(n²)이다.

선택 정렬 코드 (Swift)

func selectionSort(_ arr: [Int]) -> [Int] {
    var arr = arr
    let n = arr.count

    for i in 0..<arr.count {
        var min = i
        for j in i+1..<n {
            if arr[j] < arr[min] {
                min = j
            }
        }
        arr.swapAt(i, min)
    }
    return arr
}

let arr = [3, 7, 1, 8, 4]
print(selectionSort(arr))

선택 정렬 개선 코드 (Swift)

func selectionSort(_ arr: [Int]) -> [Int] {
    var arr = arr
    let n = arr.count

    for i in 0..<arr.count {
        var min = i
        for j in i+1..<n {
            if arr[j] < arr[min] {
                min = j
            }
        }
        if min != i {
            arr.swapAt(i, min)
        }
    }
    return arr
}

버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법입니다.

정렬이 필요한 이유 어떤 배열이 주어졌을 때, 그 배열이 미리 정렬되어 있다면 훨씬 빠른 속도 로 검색이 가능하다.

버블 정렬의 동작 과정

STEP3를 보면 이미 정렬된 배열을 한번 더 돌게 되는데, 조금 더 효율적으로 코드를 짜기 위해서 한번도 Swap되지 않았을 경우에는 이미 정렬 된 상태이므로 바로 배열을 반환해주면 좋을 것 같다.

버블 정렬의 시간복잡도

버블 정렬의 시간복잡도는 O(n²)이다.

버블 정렬 코드 (Swift)

func bubbleSort(_ arr: [Int]) -> [Int] {
    var arr = arr
    let n = arr.count
    for i in 0..<n-1 {
        for j in 0..<n-i-1 {
            if arr[j] > arr[j+1] {
                arr.swapAt(j, j+1)
            }
        }
    }
    return arr
}
let arr = [3, 1, 4, 2]
print(bubbleSort(arr))
//[1, 2, 3, 4]

> 위에서 설명한것처럼 STEP2에서 이미 정렬됐음에도 불구하고
STEP3에서 종료가 된다.

STEP1: [1, 3, 2, 4] STEP2: [1, 2, 3, 4] STEP3: [1, 2, 3, 4]

## 버블 정렬 개선 코드 (Swift)
> ```
func bubbleSort(_ arr: [Int]) -> [Int] {
    var arr = arr
    let n = arr.count
    for i in 0..<n-1 {
        var didSwap = false
        for j in 0..<n-i-1 {
            if arr[j] > arr[j+1] {
                arr.swapAt(j, j+1)
                didSwap = true
            }
        }
        if !didSwap { return arr }
        print("STEP\(i+1):", arr)
    }
    return arr
}
let arr = [3, 1, 4, 2]
print(bubbleSort(arr))

이렇게 didSwap 변수를 생성해 swap이 일어나지 않았을 경우 바로 반환해주도록 개선해보았다.

STEP1: [1, 3, 2, 4]
STEP2: [1, 2, 3, 4]

선형검색은 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색하는 알고리즘입니다.

선형 검색은 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 사용합니다.

선형 검색의 동작 과정

만약 23이라는 값을 찾고 있다면

1. 배열/라스트를 하나씩 순회하면서 찾는 값과 비교한다.
2. 원하는 값을 찾았을 경우 값을 반환해준다.

선형 검색의 성능

최선의 경우 -> O(1) : 찾고자 하는 값이 배열의 첫 번째 위치에 있는 경우 한 번의 비교로 값을 찾을 수 있다.

평균의 경우 -> O(n)

최악의 경우 -> O(n) : 최악의 경우, 찾고자 하는 값이 배열의 마지막에 있거나 배열에 존재하지 않는 경우, 모든 요소를 확인해야한다.

선형 검색 코드 (Swift)

배열 arr과 target을 받았을 때, 배열을 순회하면서 target을 찾으면 true, 찾지 못했다면 false를 반환하는 함수

func linearSearch(arr: [Int], target: Int) -> Bool {
    for i in 0..<arr.count {
        if arr[i] == target {
            return true
        }
    }
    return false
}
let arr = [6, 2, 42, 17, 9, 23]
print(linearSearch(arr: arr, target: 23))
// true

Big-O 표기법은 알고리즘이 해당 차수이거나 그보다 낮은 차수의 시간 복잡도를 가진다는 의미이다. 즉, 알고리즘에 필요한 시간의 상한선을 의미한다.

O(1) O(log n) O(N) O(nlog n) O(n²)

Big-Ω

Big-O와 반대되는 개념으로 최선의 경우를 뜻한다. 즉, 알고리즘에 필요한 시간의 하한선을 의미한다. 예를들어 숫자 28을 선형 탐색으로 찾으려고 할 때 [28, 6, 4, 23]이라면 한번에 찾을 수 있다.

Ω(1) Ω(log n) Ω(N) Ω(nlog n) Ω(n²)

Deadlock이란 무엇일까? 우선 이런 그림을 생각해놓자

데드락이란 운영체제 또는 소프트웨어의 잘못된 자원 관리로 인하여 둘 이상의 프로세스 또는 스레드들이 아무것도 진행하지 않는 상태로 서로 영원히 대기하는 상황을 말한다.

전에 기아(Starvation)라는 상태와 비슷한 것 같은데...

Deadlock VS Starvation

Deadlock은 asleep상태에서 자원, Event를 기다리는데 일어날 가능성이 없음 Starvation은 ready상태에서 CPU를 기다리는 것 (우선순위에 밀려서)

자원의 분류

일반적 분류 : Hardware resource, Software resource 데드락 관점에서 자원을 바라보면...

• 선점 가능 여부에 따른 분류
• 할당 단위에 따른 분류
• 동시 사용 가능 여부에 따른 분류
• 재사용 가능 여부에 따른 분류

1. 선점 가능 여부에 따른 분류

Preemptible resources 선점 당한 후 돌아와도 문제가 발생하지 않는 자원 ex) Processor, Memory 등

Non - Preemptible resources 선점 당하면 이후 진행에 문제가 발생하는 자원 ex) disk drive 등

2. 할당 단위에 따른 분류

Total allocation resources 자원 전체를 프로세스에게 할당 ex) Processor, disk drive

Partitioned allocation resources 하나의 자원을 여러 조각으로 나누어 여러 프로세스들에게 할당 ex) Memory

3. 동시 사용 가능 여부에 따른 분류

Exclusive allocation resources 한 순간에 한 프로세스만 사용 가능한 자원 ex) Processor, disk drive, Memory

Shared allocation resources 여러 프로세스가 동시에 사용 가능한 자원 Program(sw), Shared data

4. 재사용 가능 여부에 따른 분류

SR 시스템 내에 항상 존재하는 자원 사용이 끝나면 다른 프로세스가 사용 가능 ex) Processor, disk drive, Memory, Program

CR 한 프로세스가 사용한 후에 사라지는 자원 ex) signal, message

Deadlock을 발생시킬 수 있는 자원의 형태

Non - Preemptible resources -> 한번 할당받으면 끝날때까지 쓰기 떄문에 요청을 해도 못 주기 때문에 데드락 발생 Exclusive allocation resources -> 나눠쓰는건(Shared allocation) 그냥 나눠쓰면 되는데 얘는 아님 -> 데드락 발생 SR(Serially reusable resources) / CR 할당 단위는 딱히 문제 없음

Deadlock 발생의 예

2개의 프로세스(P1, P2) 2개의 자원(R1, R2) 를 가지고 있다고 가정

P1이 R2 요청 P2가 R1 요청 이 상태에서 P1이 R1 요청 -> 아직 데드락 아님 P2가 R2 요청 -> 서로가진걸 요청 -> 데드락

Deadlock Model

1. Graph Model Node : 프로세스 노드(P1, P2), 자원 노드(R1, R2) Edge : Rj -> Pi : 자원 Rj이 프로세스 Pi에 할당됨 Pi -> Rj : 프로세스 Pi가 자원 Rj을 요청(대기중)

2. State Transition Model ex) 2개의 프로세스와 A type의 자원 2개(unit) 존재 프로세스는 한번에 자원 하나만 요청/반납 가능

Deadlock 발생 필요 조건

자원의 특성

1. Non - Preemptible resources

2. Exclusive allocation resources

프로세스의 특성

*3. Hold and Wait : 자원을 하나 hold하고 다른 자원 요청 *

4. Circular wait

4가지 모두 성립해야 데드락 발생!!

Deadlock 해결 방법

Deadlock Prevention

4가지 모두 성립해야 데드락이 발생한다고 했으니 4가지 중 하나를 제거하면 데드락이 절대 발생하지 않는다!!

1. Non - Preemptible resources 2. Exclusive allocation resources 3. Hold and Wait ** **4. Circular wait

모든 자원을 공유 허용

Exclusive allocation resources 조건 제거 하지만 현실적으로 불가능하다.

모든 자원에 대해 선점 허용

Non - Preemptible resources 조건 제거 모든 자원에 대해 선점을 허용한다는 것 또한 현실적으로 불가능하다. 하지만 유사한 방법으로 프로세스가 할당 받을 수 없는 자원을 요청한 경우, 기존에 가지고 있던 자원을 모두 반납하고 작업 취소하는 방법이 있다. 심각한 자원 낭비가 발생하긴한다..

필요한 자원 한번에 모두 할당

Hold and Wait 필요한 자원 한번에 모두 할당하고 필요 없어져도 반납 X 자원 낭비 발생 -> 필요하지 않은 순간에도 가지고 있기 때문 무한 대기 현상 발생 가능

Circular wait 조건 제거

Total allocation을 일반화 한 방법 자원들에게 순서 부여 프로세스는 순서의 증가 방향으로만 자원 요청 가능 (Circular이 만들어질수없다.) 자원 낭비 발생

Prevention은 자원 낭비가 너무 심하고 비현실적이다...

Deadlock Avoidance

앞에서 Prevention은 너무 자원낭비가 심했다. 회피(Avoidance)방법을 알아보자. Deadlock Avoidance은 시스템의 상태를 계속 감시한다. Deadlock이 될 가능성이 있는 자원 할당 요청을 보류한다. 즉 시스템을 항상 safe state로 유지하는 방법이다.

Safe state

모든 프로세스가 정상적 종료 가능한 상태 Safe sequence가 존재 -> Deadlock 상태가 되지 않을 수 있음을 보장

Unsafe state

Deadlock 상태가 될 가능성이 있음 (반드시 발생X)

Deadlock Avoidance 가정

1. 프로세스의 수가 고정됨
2. 자원의 종류와 수가 고정됨
3. 프로세스가 요구하는 자원 및 최대 수량을 알고 있음
4. 프로세스는 자원을 사용 후 반드시 반납한다

-> Not practical 하긴 함 ㅎㅎ..

Deadlock Avoidance 알고리즘

1. Dijkstra's algorithm Banker's algorithm 2. Habermann's algorithm

** Dijkstra) Banker's algorithm** 한 종류의 자원이 여러개, 시스템을 항상 safe state로 유지한다고 가정

예시1) 1 resource type R, 10 resource units, 3 processes Max. Claim : 요구한 최대 자원의 수 Cur. Alloc : 현재 할당 받은 자원의 수 Additional Need : 추가로 필요한 자원의 수

쉽게 생각해서 내가 10만원을 가지고 있다. 친구 3명이 돈을 빌림 P1은 만원 빌렸고, 2만원이 더 필요함 P2는 5만원 빌렸고, 4만원이 더 필요함 P3는 2만원 빌렸고, 3만원이 더 필요함 나는 총 8만원을 빌려줬고 2만원이 남은 상태 친구들은 반드시 돈을 갚는 친구들임!! 남은 금액 빌려주는 순서는? P1 - P3 - P2 P1에게 빌려주면 3만원 돌려받음! 그럼 P3에게 빌려줄 수 있다. P3에게 빌려주고 5만원 받으면 P2에게 빌려줄수있음! 이게 Safe sequence이다.

예시2) 1 resource type R, 10 resource units, 3 processes 아까와 동일한 상태에서 추가로 필요한 자원의 수만 달라졌다. 2만원 밖에 없기때문에 돈을 빌려줄수없음!! 이게 Unsafe sequence이다.

Dijkstra's algorithm

P1이 R하나를 요청 -> P1 - P3 - P2 순서로 빌려주면 Safe sequence 존재함

P2가 R 하나 요청 -> 남은 자원이 하나뿐이라 Unsafe sequence

즉, 어떤 상태에서 자원 요청이 들어왔을때 자원을 주었다고 "가정"해보고 Safe sequence가 있으면 OK 없으면 X 이게 Banker's algorithm

Habermann's algorithm

자원이 A, B, C 3개가 각각 10, 5, 7개 존재 5개의 Processes

A 3개, B 3개, C 2개 더 빌려줄 수 있음 P2 → P4 → P1 → P3 → P5 순서로 빌려주면 Safe sequence 존재 Banker's algorithm에서 자원의 개수만 늘어난게 Habermann's algorithm

Deadlock의 발생을 막을 수 있지만... 1. High overhead : 항상 시스템을 감시하고 있어야함 2. Low resource utilization : Safe state 유지를 위해, 사용되지않는 자원이 존재함 3. Not practical : 프로세스 수와 자원 수가 고정, 필요한 최대 자원 수를 알고있어야함

Deadlock Detection and Recovery

Deadlock Detection

Deadlock 방지를 위한 사전 작업 X 즉, 데드락이 발생해도 피하지 않음 주기적으로 Deadlock 발생 확인 ✅ 시스템이 Deadlock 상태인가? ✅ 어떤 프로세스가 Deadlock 상태인가? Resource Allocation Graph를 사용해서 Deadlock을 찾아냄

Resource Allocation Graph (RAG)

Deadlock 검출을 위해 사용 Directed(방향성), bipartite Graph

그래프는 "노드"와 "엣지"로 구성 G = (N, E) Node 프로세스의 노드들(P1, P2, ... Pn)과 리소스 노드들(R1, R2, ... Rn)의 집합으로 구성

Edge 엣지는 Np와 Nr사이에만 존재 프로세스에서 리소스, 리소스에서 프로세스로만 연결 가능 • e = (Pi, Rj) : 자원 요청 예) P1 → R1 프로세스 : 프로세스 P1이 자원 R1을 요청중 • e = (Rj, Pi) : 자원 할당 예) R2 → P2 프로세스 : 자원 R2가 프로세스 P2에 할당됨

Rk : k type의 자원 Tk : Rk의 단위 자원 수 |(a, b)| : (a, b) edge의 수

RAG Example

Graph reduction

데드락을 쉽게 판단할수있는 알고리즘!! 주어진 RAG에서 edge를 하나씩 지워가는 방법이다. Completely reduced → 다 지워짐, 데드락 X Irreducible → 지울 수 없는 엣지 존재, 데드락 O

Unbloked process 엣지를 지운다. → 필요한 자원을 모두 할당 받을 수 있는 프로세스

Graph reduction procedure

1. Unblocked process에 연결 된 모든 edge wprj
2. 더 이상 unblocked process가 없을 때 까지 1 반복

*최종 Graph에서 * • 모든 edge가 제거됨 → Completely reduced • 일부 edge가 남음 → Irreducible

Graph reduction example 1

모든 엣지가 지워짐 → 데드락 X

Deadlock Avoidance VS Deadlock Detection

Deadlock Avoidance

• 최악의 경우를 생각 • 데드락이 발생하지 않음

Deadlock Detection

•최선의 경우를 생각 •Deadlock 발생 시 Recovery 과정이 필요

Deadlock Recovery

Deadlock을 검출 한 후 해결하는 과정

Deadlock Recovery Method

1. Process termination • Deadlock 상태에 있는 프로세스를 종료 시킴 • 강제 종료 된 프로세스는 이후 재시작 됨

termination cost model 종료 시킬 deadlock 상태의 프로세스 선택 • 우선순위 • 종류 • 총 수행 시간 • 남은 수행 시간 • 종료 비용 ...

2. Resouce preemption • Deadlock 상태 해결을 위해 선점할 자원 선택 • 자원을 빼앗긴 프로세스는 강제 종료 됨

동기화(synchronization)

시스템을 동시에 작동시키기 위해 프로세스들이 서로 정보를 공유하는 것

동기화가 필요한 이유

공유 데이터에 프로세스가 동시에 접근하면 Data Inconsistency(데이터 불일치)가 발생할 수 있다. Data Consistency(데이터의 일관성)을 유지하기 위한 메커니즘을 동기화라고 한다.

이러한 상태에 도달하는 것은 여러 개의 프로세스가 동시에 내 잔고를 조작하도록 허용했기 때문! 이와 같이 동시에 여러 개의 프로세스가 동일한 자료에 접근하여 조작하고,

그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상태(race condition)라고 한다.

이러한 경쟁 상태가 발생하지 않도록 해야하고 진입하게 되면 임계 영역으로 잠궈야 한다.(Lock)

임계영역(Critical Section)

공유 데이터를 접근하는 코드 영역

임계 영역 문제를 해결하기 위한 3가지 조건

1. Mutual exclution (상호 배제)

• 하나의 프로세스가 임계 영역에 존재하다면, 다른 프로세스는 임계 영역에 접근할 수 없어야 한다.
• 즉, 한번에 두개 이상의 프로세스 접근 X
• 2. Progress (진행)*
• 임계 영역에 프로세스가 존재하지 않을 경우, 다른 프로세스가 접근할 수 있도록 해야한다.
• 임계 영역에 접근하고자 하는 프로세스가 하나가 아니라면 어느것이 들어갈지 결정해주어야한다.
• 3. Bounded Waiting (한정 대기)*
• 다른 프로세스의 기아(Starvation)를 방지하기 위해 한번 임계 구역에 들어간 프로세스는 다음 임계영역에 들어갈 때 제한을 두어야 한다.

Mutual exclution Methods

enterCS()

임계 영역 진입 전 다른 프로세스가 임계 영역 안에 있는지 검사 화장실 들어가기 전에 노크!! 같은 느낌...

exitCS()

임계영역을 벗어날때 시스템이 알려줌 저 끝났어요. 다음 분 들어오세요!! 같은 느낌...

Mutual exclution Solutions

SW Solution

Dekker's Algorithm

Two Process ME을 보장하는 최초의 알고리즘

플래그와 턴 변수를 사용하여 두 프로세스가 서로의 상태를 확인하고, 임계 구역에 들어갈 수 있는지 판단

f0 ← false
f1 ← false
turn ← 0   // or 1

 p0:                                 p1:
     f0 ← true                         f1 ← true
     while f1 {                          while f0 {
         if turn ≠ 0 {                      if turn ≠ 1 {
             f0 ← false                         f1 ← false
             while turn ≠ 0 {                  while turn ≠ 1 {
             }                                   }
             f0 ← true                          f1 ← true
         }                                   }
     }                                    }

    // 임계 구역                          // 임계 구역 
    ...                                   ...
    // 나머지 구역                        // 나머지 구역
   turn ← 1                             turn ← 0
   f0 ← false                           f1 ← false

Peterson's Algorithm

Dekker의 알고리즘을 개선하여 더 간결하고 이해하기 쉽게 만든 알고리즘

Dijkstra's Algorithm

프로세스 n개의 상호배제 문제를 해결한 알고리즘

SW Solution의 문제점

1. 속도가 느리고, 구현이 복잡하다.
2. 상호배제 실행 중 preemption 될 수 있다.
3. Busy waiting : 기다리는데 바쁘다 -> 비효율적이다.

HW Solution

TestAndSet instruction

실행중에 인터럽트를 받지않음 -> preemption 되지 않음

3개 이상의 프로세스의 경우, Bounded Waiting 조건 위배.. 그럼 N개의 프로세스는..?

HW Solution의 문제점 Busy Waiting! Busy Waiting 문제를 해소한 상호배제 기법 -> 세마포어

OS Solution

Spinlock

임계 구역에 진입이 불가능할 때 진입이 가능할 때까지 루프를 돌면서 재시도하는 방식 초기화 P(), V() 연산으로만 접근 가능

P()는 자물쇠를 거는거, V()는 자물쇠를 푸는거라고 생각하면 쉬움 들어갈때 잠구고 나올때 풀기,,

스핀락의 문제 한 스레드가 Lock을 오랫동안 소유하고 있다면 기다리는 스레드들은 계속해서 무한루프만 돌고있는 상태가 된다. 즉 굉장히 비효율적이다. 그래서 멀티 프로세서 시스템에서만 사용 가능

Semaphore

세마포어(Semaphore)는 음이 아닌 정수형 변수(S) 초기화 연산 P(), V() or wait(), signal() 임의의 S 변수 하나에 ready queue가 할당 됨 S는 물건 수로 생각

스핀락과 다르게 ready queue에서 기다림

세마포어는 Counter의 개수에 따라 1개의 경우 이진 세마포어(Binary Semaphore) S가 0과 1 두종류의 값만 갖는 경우 상호배제나 프로세스 동기화의 목적으로 사용 2개 이상의 경우 카운팅 세마포어(Counting Semaphore) S가 0이상의 정수값을 가질 수 있는 경우 생산자-소비자 문제 등을 해결하기 위해 사용

Semaphore로 해결 가능한 동기화 문제들

1. 상호배제 문제 (Mutual exclusion) 스핀락은 임계 구역에 진입이 불가능할 때 진입이 가능할 때까지 루프를 돌면서 기다리지만 세마포어는 대기실에서 기다리면서 대기

2. 프로세스 동기화 문제 (Process synchronization) 프로세스들의 실행 순서 맞추기 sync라는 세마포어 변수 pj가 물건을 들고있었다라고 가정했을때, 프로세스 i는 물건이 반납될때까지 P(sync)에서 대기. j는 V(sync) 지나면서 물건 반납

3. 생산자-소비자 문제

   생산자 프로세스 : 메시지를 생성하는 프로세스 그룹 소비자 프로세스 : 메세지를 전달받는 프로세스 그룹

single buffer일때 single buffer이기 때문에 공간이 1인 경우이다. 물건을 놓고 있을때는 가져가면 안되고 물건을 꺼내가는 중에는 놓을 수 없다. 한번에 한명만 접근 가능

consumed, produced라는 변수 생성 메시지를 생산해서 넣으려고할때 buffer가 비었는지 확인

생산자 P(consumed) -> consumed가 1인지 체크하고 1이면 0으로 변경 후. 물건을 놓기 V(produced) -> 0에서 1로 바꾸면서 생산됐다고 알려줌

소비자 P(produced) -> 물건이 생산됐는지 확인 0이라면 생산이 안된거니깐 대기실에서 기다림 1이라면 안으로 들어가면서 0으로 변경 V(consumed) -> 물건 소비하고 1로 변경

4. Reader-writer 문제
5. Dining philosopher 문제 ...

High-level Mechanism

프로그래밍 언어가 상호배제를 서포팅하기 때문에 사용이 쉽다.

Monitor (모니터)

공유 데이터와 Critical section의 집합

Condition Variable wait(). signal()

사각형 안이 모니터이고, Critical data와 Critical sections을 모아놓은 방이라고 생각해보자.

책방인데 한번에 한명만 들어올 수 있는 책방이라고 생각했을때 Critical data는 사고 싶은 책, Critical sections은 카운터

모니터의 구조

Entry queue (진입 큐) • 모니터 내의 procedure 수만큼 존재

Mutual exclusion -> Language가 보장 • 모니터 내에는 항상 "하나의 프로세스"만 진입 가능 (책방에는 한명만)

Information hiding (정보 은폐) • 공유 데이터는 모니터 내의 프로세스만 접근 가능

Condition queue (조건 큐) • 모니터 내의 "특정 이벤트"를 기다리는 프로세스가 대기

Signaler queue (신호제공자 큐) • 모니터에 항상 "하나의 신호제공자 큐"가 존재 • signal() 명령을 실행한 프로세스가 임시 대기

우리는 보통 여러개의 프로세스가 시스템 내에 존재하는 다중 프로그래밍을 사용한다. 따라서 자원을 할당 할 프로세스를 선택해야하는데 이게 바로 스케줄링!!

자원 관리

시간 분할 관리

• 하나의 자원을 여러 스레드들이 번갈아 가면서 사용 / 예시) 프로세서
• 프로세스 스케줄링 - 프로세서 사용시간을 프로세스들에게 분배

공간 분할 관리

• 하나의 자원을 분할하여 동시에 사용 / 예시) 메모리

스케줄링의 목적

시스템의 성능 향상을 위해 사용한다.

성능

1. 응답 시간 : 작업 요청으로부터 응답을 받을때까지의 시간
2. 작업 처리량 : 단위 시간 동안 완료된 작업의 수
3. 자원 활용도 : 주어진 시간동안 자원이 활용된 시간 ...

대기 시간, 응답 시간, 반환 시간

도착에서 실행 시작 전까지 대기시간 도착부터 작업 진행중 처음 응답이 도착할때까지의 시간 응답시간 실제로 프로세스가 실행된 시간 실행시간 처음부터 종료까지의 시간 반환시간

스케줄링 기준

스케줄링 기법이 고려하는 항목들

1. 프로세스의 특성
2. 시스템 특성
3. 프로세스의 긴급성
4. 프로세스 우선순위
5. 프로세스 총 실행 시간 ...

스케줄링 단계

Long-term Scheduling (장기 스케줄링)

큐에 넣을 프로세스를 결정

• 시스템에 제출 할(커널에 등록 할) 작업 결정

  다중 프로그래밍 정도 조절

• 메모리에 올라가 있는 프로세스 수 조절

가끔 호출되기 때문에 느려도 괜찮아 시분할 시스템에서는 모든 작업을 시스템에 등록해야하기 때문에 Long-term Scheduling이 불필요

Mid-term Scheduling (중기 스케줄링)

메모리에 적재된 프로세스 수 관리

너무 많은 프로세스에게 메모리를 할당해 시스템의 성능이 저하되는 경우, 메모리에 적재된 프로세스의 수를 동적으로 조절하기 위해 추가된 스케줄러

Short-term Scheduling (단기 스케줄링)

프로세스를 할당할 프로세스를 결정

준비 상태의 프로세스 중에서 어떤 프로세스를 다음번에 실행 상태로 만들것인지 결정한다. 단기 스케줄러는 가장 빈번하게 발생하기 때문에 매우 빨라야한다.

스케줄링 정책 (Policy)

1. 선점 / 비선점
2. 우선순위

선점(Preemptive) / 비선점(Non-Preemptive) Scheduling

쉽게 말해 선점은 누가 빼앗을 수 있다. 비선점은 뺏을 수 없다.

Preemptive

타의에 의해 자원을 빼앗길 수 있음 예를들어 더 급한 프로세스가 등장하면 빼앗을 수 있다.

장점 : 응답성이 증가 (Time-sharing system, real-time system에 적합) 단점 : Context Switch overhead가 큼

Non-Preemptive

할당받은 자원을 스스로 반납할 때까지 사용

장점 : Context Switch overhead가 적음 단점 : 잦은 우선순위 역전, 평균 응답시간 증가

우선순위(Priority)

정적 우선순위

프로세스 생성시 결정된 우선순위가 유지됨

장점 : 구현이 쉽고, 오버헤드가 적음 단점 : 시스템 환경변화에 대한 대응이 어려움

동적 우선순위

프로세스의 상태변화에 따라 우선순위 변경 장점 : 시스템 환경변화에 대한 유연한 대응 가능 단점 : 구현이 복잡하고 우선순위 재계산 오버헤드가 큼

스케줄링 알고리즘

FCFS, RR, SPN, SRTN, HRRN ...

FCFS (First Come First Service)

쉽게 말해 선착순!! 도착 시간을 기준으로 먼저 레디 큐에 도착한 프로세스를 먼저 처리 Batch system에 적합, interactive system에 부적합 단점은 긴 평균 응답시간 예를 들어 60초 짜리가 먼저오고 2초짜리가 뒤에오면 2초만 쓰면 되는데도 불구하고 계속 기다려야한다.

RR (Round Robin)

쉽게 말해 돌아가면서 쓰자!! 먼저 도착한 프로세스를 먼저 처리하는데 자원 사용 제한 시간(time quantum)이 있음 프로세스는 할당된 시간이 지나면 자원을 반납해야함 장점은 특정 프로세스의 자원 독점을 방지 단점은 Context switch overhead가 크다 대화형, 시분할 시스템에 적합

SPN (Shortest Process Next)

= SJF (Shortest Job First) Burst time이 가장 작은 프로세스를 먼저 처리

장점 : 평균 대기시간 최소화, 시스템 내 프로세스 최소화, 많은 프로세스들에게 빠른 응답 시간 제공

단점 : 무한 대기 현상 발생 -> 뒤에 온 프로세스의 BT이 더 짧다면.. 먼저와도 엄청 기다려야 할 수도 있음 정확한 실행 시간을 알 수 없음

SRTN (Shortest Remaining Time Next)

SPN의 변형 잔여 실행 시간이 더 적은 프로세스가 등장하면 선점 장점 : SPN의 장점 극대화 단점 : 잔여 실행을 계속 추적해야함 = Overhead

HRN(High Response Ratio Next)

SPN의 변형 프로세스의 대기시간을 고려하여 기회를 제공 Response Ratio = 대기시간 + 서비스(실행)시간 / 서비스(실행)시간

SPN / SRTN / HRN은 효율성은 좋지만 실행 시간 예측 부하라는 단점이 있음 그래서 MLQ / MFQ가 등장!

MLQ (Multi Level Queue)

작업별 별도의 레디 큐를 가짐 (앞에 나온 스케줄링 기법은 레디큐가 하나) 큐 사이에는 우선순위 기반의 스케줄링 사용

빠른 응답시간(?) -> 중요한 프로세스는 빠르지만.. 우선순위가 낮다면 starvation 현상 발생..

MFQ (Multi Level Feedback Queue)

프로세스의 큐간 이동이 허용된 MLQ 피드백을 통해 우선 순위 조정 장점 : BT를 예상하지 않고 앞서 나온 스케줄링 기법(SPN / SRTN / HRN)의 효과를 볼수있음 단점 : 설계, 구현이 복잡하고 스케줄링 오버헤드가 크다. Starvation문제도 여전하다..

시뮬레이션은 처음이라 문제 읽자마자 당황했는데 풀다보니 나름 할만했다!

풀이 과정

격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는 1번 행이, 1번 행의 위에는 N번 행이 있고, 1번 열의 왼쪽에는 N번 열이, N번 열의 오른쪽에는 1번 열이 있다.

이 부분이 조금 헷갈렸는데 배열의 마지막 다음이 첫번째 원소니깐 이 부분은 모듈러 연산을 통해 새로운 위치가 범위 0에서 n-1 사이에 있도록 제한했다. 그리고 nx, ny가 음수일 경우 +n을 해줬다.

        var nx = (x + dx[d] * s) % n
        var ny = (y + dy[d] * s) % n
        if nx < 0 { nx += n }
        if ny < 0 { ny += n }

2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다. 이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다. 예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.

for i in stride(from: 2, through: 8, by: 2) {
            let nx = x + dx[i]
            let ny = y + dy[i]
            if isWithinMap(nx, ny) && map[nx][ny] > 0 {
                count += 1
            }
        }

대각선 방향을 확인하기 위해 stride를 사용해 방향을 뽑아냈고,

func isWithinMap(_ x: Int, _ y: Int) -> Bool {
    return x >= 0 && x < n && y >= 0 && y < n
}

isWithinMap함수를 생성해 map을 넘어가는지 아닌지 확인해주었다.

바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.

!cloudsMoved.contains(where: { $0 == (x, y) })

contains를 이용해 3에서 구름이 사라진 칸이 아닌 칸에 구름 생성

전체 코드

func isWithinMap(_ x: Int, _ y: Int) -> Bool {
    return x >= 0 && x < n && y >= 0 && y < n
}

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n, m) = (input[0], input[1])
var map = [[Int]]()
for _ in 0..<n {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    map.append(input)
}

var clouds = [(n-1, 0), (n-1, 1), (n-2, 0), (n-2, 1)]

// ←, ↖, ↑, ↗, →, ↘, ↓, ↙
let dx = [0, 0, -1, -1, -1, 0, 1, 1, 1]
let dy = [0, -1, -1, 0, 1, 1, 1, 0, -1]

for _ in 0..<m {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    let (d, s) = (input[0], input[1])
    var cloudsMoved = [(Int, Int)]()

//  모든 구름이 d 방향으로 s칸 이동한다. (1번 행과 N번 행, 1번 열과 N번 열이 연결되어있음)
    for (x, y) in clouds {
        var nx = (x + dx[d] * s) % n
        var ny = (y + dy[d] * s) % n
        if nx < 0 { nx += n }
        if ny < 0 { ny += n }
        cloudsMoved.append((nx, ny))
    }

//  구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가
    for (x, y) in cloudsMoved {
        map[x][y] += 1
    }

//  물이 증가한 칸에 대각선 방향으로 거리가 1인 칸에 "물이 있는 / 바구니의 수만큼" 물 증가
    for (x, y) in cloudsMoved {
        var count = 0
        for i in stride(from: 2, through: 8, by: 2) {
            let nx = x + dx[i]
            let ny = y + dy[i]
            if isWithinMap(nx, ny) && map[nx][ny] > 0 {
                count += 1
            }
        }
        map[x][y] += count
    }

//  바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어듦.
//  이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.
    var newClouds = [(Int, Int)]()
    for x in 0..<n {
        for y in 0..<n {
            if map[x][y] >= 2 && !cloudsMoved.contains(where: { $0 == (x, y) }) {
                map[x][y] -= 2
                newClouds.append((x, y))
            }
        }
    }
    clouds = newClouds
}

var sum = 0
for x in 0..<n {
    for y in 0..<n {
        sum += map[x][y]
    }
}
print(sum)

프로세스란?

프로세스는 실행중인 프로그램이라고 정의할 수 있다. 맥에서 활성 상태 보기에 들어가면 이렇게 프로세스를 볼 수 있다.

프로그램 VS 프로세스

프로그램

• 실행 할 프로그램 + 데이터
• 컴퓨터 시스템에 실행 요청 전의 상태

프로세스

• 실행을 위해 커널에 등록된 작업
• 시스템 성능 향상을 위해 커널에 의해 관리됨

프로세스의 정의

• 커널에 등록되고, 커널의 관리하에 있는 작업
• 각종 자원들을 요청하고 할당 받을 수 있는 개체
• 프로세스 제어 블록(PCB)를 할당 받은 개체
• 능동적인 개체 -> 실행중에 각종 자원을 요구, 할당, 반납하며 진행

Process Control Block(PCB)

PCB는 프로세스 생성시 생성된다. 각 프로세스들에 대한 중요한 정보를 관리하며, 커널공간 내부에 존재한다. 운영 체제는 PCB를 통해 프로세스를 제어하고 스케줄링한다.

PCB가 관리하는 정보

참고 - PCB 정보는 OS마다 조금 다르다.

• PID : 프로세스 고유 식별 번호
• 스케줄링 정보 : 프로세스 우선순위 등의 정보
• 프로세스 상태 : 자원할당, 요청 정보
• 메모리 관리 정보 : Page Table, segment table...
• 입출력 상태 정보 : 할당받은 입출력 장치, 파일 등에 대한 정보
• Context save area : 프로세스의 레지스터 상태를 저장하는 공간 ...
• 계정 정보 : 자원 사용 시간 등을 관리

프로세스의 종류

자원(Resource)

커널의 관리 하에 프로세스에게 할당/반납 되는 수동적 개체 H/W resource -> processor, memory, keyboard... S/W resource -> Message, signal, files ...

프로세스의 상태

생성(Created State)

• 작업을 커널에 등록
• PCB 할당 및 프로세스 생성
• 가용 메모리 공간 체크 및 프로세스 상태 전이 즉 메모리가 있으면 준비(Ready), 없으면 지연 준비(Suspended Ready)

준비(Ready State)

프로세서 외에 다른 모든 자원을 할당 받은 상태

• 프로세서 할당 대기 상태 (CPU만 있으면 바로 실행 가능)
• 즉시 실행 가능 상태

  Dispatch

  준비 → 실행 : 우선순위가 높은 프로세스 선정하여 명령어 실행

실행(Running State)

프로세서와 필요한 자원을 모두 할당 받은 상태

Preemption(Time out)

실행 → 준비 : 클럭이 인터럽트를 발생시켜 제어권을 빼앗음(Preemption, 독점 방지)

Block / Sleep

실행 → 대기 : 프로세서가 입출력, 자원 등을 기다리기 위해 대기로 전환

Wake Up

대기 → 준비 : 입출력이 완료되거나 자원이 할당되어 다시 실행

지연 준비(Suspended Ready)

메모리를 할당 받지 못한(빼앗긴) 상태 커널 또는 사용자에 의해 발생

Swap-out(Suspended)

준비(대기) 상태에서 기억 장치를 반납하고 지연 준비(지연 대기) 상태로 전이

Swap-in(Resume)

지연 준비(지연 대기) 상태에서 기억 장치를 할당받아 준비(대기) 상태로 전이

종료(Terminated)

프로세스 수행이 끝난 상태 모든 자원 반납 후, 커널 내에 일부 PCB 정보만 남아있는 상태

• 이후 프로세스 관리를 위해 정보를 수집

인터럽트

예상치 못한, 외부에서 발생한 이벤트

인터럽트의 종류

I/O interrupt Clock interrupt Console interrupt Program Check interrupt Machin check interrupt ...

인터럽트 처리 과정

1. 인터럽트 발생
2. 프로세스 중단 이때 Context Saving 발생 (현재까지 수행중이었던 상태를 PCB에 저장)
3. 인터럽트 처리 3-1 Interrupt handling - 인터럽트의 발생 장소와 원인을 파악하고 인터럽트를 처리할 것인지, 무시할 것인지 결정 3-2 Interrupt Service - 인터럽트 서비스 루틴을 호출하여 인터럽트를 처리
   4. 인터럽트 처리 완료 이때 인터럽트 전에 실행중이던 프로세스가 다시 올라올 수도 있지만, Ready queue의 가장 앞에 있던 프로세스가 올라올 수도 있음

Context Switching (문맥 교환)

Context

프로세스와 관련된 정보들의 집합

Context Saving

현재 프로세스의 레지스터 Context를 저장하는 작업

Context restoring

레지스터 Context를 프로세스로 복구하는 작업

두 작업을 합치면 Context Switching이 된다. 즉 실행중인 프로세스의 Context를 저장하고, 앞으로 실행 할 프로세스의 Context를 복구하는 일

이러한 Context Switching은 자주 발생하기 때문에 OS의 성능에 큰 영향을 준다. 따라서 불필요한 Context Switching을 줄이는 것이 중요하다. 이때 스레드를 사용해 줄일 수 있다.

스레드(Thread)

프로세스가 할당받은 자원을 이용하는 실행흐름의 단위

프로세스는 자원과 제어를 모두 독립적으로 가지고, 스레드는 자원을 같은 프로세스 내의 다른 스레드와 공유하지만 제어는 독립적으로 가진다.

스레드는 Single-thread와 Multi-threads가 있는데 아래의 그림은 멀티스레드..

스레드의 장점

1. 사용자 응답성 : 일부 스레드의 처리가 지연되어도, 다른 스레드의 작업은 계속 처리 가능

2. 자원공유 : 자원을 공유해서 효율성 증가 (커널의 개입을 피할 수 있음)

3. 경제성 : 프로세스의 생성, Context Switch에 비해 효율적

4. 멀티 프로세서 활용 : 병렬처리를 통한 성능 향상

스레드 사용의 예시

식당(프로세스)을 운영하는데 직원(스레드)이 여러명 존재 직원1 -> 주방에서 요리 직원2 -> 서빙 직원3 -> 계산

만약에 직원(스레드)가 하나뿐이라면.. 모든 업무를 혼자서 수행해야하기에 매우 비효율적이다.

스레드의 구현

스레드에는 User Thread와 Kernel Thread가 있다.

User Thread

사용자 영역의 스레드 라이브러리로 구현된다. 스레드의 생성, 스케줄링 ...

커널은 스레드의 존재를 모른다. 즉 커널의 개입을 받지 않기 떄문에 생성과 관리의 부하가 적고 유연한 관리가 가능하다. 또한 이식성이 높다

Kernel Thread

커널이 각 스레드를 개별적으로 관리하기 때문에 프로세스 내 스레드들이 병행 수행 가능하다.

OS가 직접 관리, 커널 영역에서 스레드의 생성/관리를 수행하기 때문에 오버헤드가 크다.

Multi-Threading Model

다대일(n:1) 모델 - 사용자 수준 스레드 일대일(1:1) 모델 - 커널 수준 스레드 다대다(n:m) 모델 - 혼합형 스레드

혼합형 스레드

n개의 사용자 수준 스레드 - m개의 커널 스레드(n>m) 사용자는 원하는 수만큼 스레드를 사용할 수 있다. 커널 스레드는 자신에게 할당된 하나의 사용자 스레드가 block 상태가 되어도, 다른 스레드 수행 가능

지난 포스팅에서 컴퓨터 시스템상의 OS의 위치를 설명하기 위해 컴퓨터 시스템의 구성 요소를 살펴보았는데요. 컴퓨터 시스템은 이렇게 구성되어있습니다. 이 그림을 통해 알수있듯 어떤 사용자나 응용 소프트웨어라도 직접 하드웨어에 접근하는 것은 허용되지 않습니다. 반드시 운영체제를 통해서 접근해야하는데 이렇듯 운영체제는 응용 소프트웨어와 하드웨어 사이의 중계역할을 수행합니다.

메모리 구조

운영체제는 프로그램을 실행시킬 때 해당 프로그램을 위한 4개의 공간을 제공합니다.

• 코드 : 프로그램 코드가 적재되는 메모리 공간
• 데이터 : 전역변수들이 적재되는 공간
• 힙 : 프로그램이 실행 중 동적으로 저장할 데이터를 위한 공간
• 스택 : 함수가 호출될 때 매개변수, 지역변수, 함수가 실행을 마치고 돌아갈 주소등을 저장하기 위한 공간

컨텍스트 스위칭(Context Switching)

컨텍스트(Context) 란 어떤 프로그램이 실행중인 일체의 상황을 뜻한다. 즉 프로세스나 스레드가 실행 중인 상태와 관련된 모든 정보를 의미한다. 이는 프로세스나 스레드가 실행을 멈추고 다른 작업으로 전환될 때, 나중에 다시 실행을 재개할 수 있도록 하기 위해 저장되는 정보이다.

운영체제가 현재 실행중인 프로그램 A의 컨텍스트를 저장해두고, 다른 프로그램인 B를 실행 시키기 위해 프로그램 B에 저장된 컨텍스트를 CPU로 옮기는 것을 컨텍스트 스위칭(Context Switching)이라고 한다. 이때 컨텍스트 정보들은 PCB(Process Control Block)에 저장된다.

사진 출처 : 명품 운영체제 

운영체제를 구성하는 요소

운영체제는 도구/GUI, 커널, 드라이버들로 구성되는 소프트웨어이다.

사진 출처 : 명품 운영체제 

도구/GUI 소프트웨어

도구 소프트웨어는 User가 컴퓨터를 편하게 사용할 수 있도록 운영체제 패키지에 포함되어 제공되는 프로그램이다. Window에는 파일탐색기, 제어판, 작업관리자와 같은 프로그램이 있다. 리눅스에는 쉘(Shell)이 있다.

커널

커널은 운영체제의 핵심 부분이다. 커널은 부팅 후부터 메모리에 상주하며 CPU나 캐시, 메모리와 같은 하드웨어를 관리한다.

• 프로세스와 스레드 관리

• 메모리 관리
• 파일 시스템 관리
• 디바이스 드라이버를 호출하여 장치 입출력 이러한 핵심 기능들이 커널 코드에 의해 실행된다.

디바이스 드라이버

디바이스 드라이버는 장치를 직접 제어하는 소프트웨어이다. 예를들어 마우스의 클릭, 움직임을 인지하는 마우스 드라이버 키보드에서 사용자가 입력한 키를 읽어오는 키보드 드라이버 등 다양한 드라이버가 존재한다.

시스템 호출(System Call)

시스템 호출은 커널과 응용프로그램 사이의 인터페이스로 응용프로그램에서 커널 코드를 실행하는 기법이다.

OS는 하드웨어를 직접적으로 관리하기 때문에 응용 프로그램은 커널에 작성된 함수를 직접 호출할 수 없다. 응용프로그램은 OS가 제공하는 인터페이스를 통해서만 자원을 활용할 수 있다. 일반적으로 시스템 호출 라이브러리에 들어있는 시스템 호출 함수를 호출해서 사용한다. 시스템 호출은 소프트웨어 인터럽트의 일종이다.

인터럽트

인터럽트는 하드웨어 장치들이 CPU에게 하드웨어 신호(인터럽트 신호)를 물리적으로 발생시켜 입출력 완료나 타이머 완료 등을 CPU에게 알리는 방법이다. CPU가 인터럽트 신호를 받게 되면 수행중인 작업을 멈추고(이때 수행중이던 프로세스의 정보는 PCB에 저장) 인터럽트의 요청을 처리하는 코드를 실행한다. 이 코드를 ISR(Interrupt Service Routine)이라고 한다. 이러한 인터럽트에는 하드웨어 인터럽트(외부 인터럽트) / 소프트웨어 인터럽트(내부 인터럽트)가 있다.

하드웨어 인터럽트(외부 인터럽트)

외부 장치가 발생시키는 인터럽트로, I/O 작업, 타이머, 전원 관리 등 다양한 이벤트를 처리한다.

소프트웨어 인터럽트(내부 인터럽트)

프로그램 내에서 명령어로 발생시키는 인터럽트로, 시스템 호출, 트랩, 예외 등이 있다.

사용자 공간과 커널 공간

다중사용자/다중프로세스가 실행되기 때문에 현재의 운영체제는 응용프로그램과 운영체제 커널의 메모리 영역을 확실하게 구분하기 위해 사용자 공간과 커널 공간으로 나누었다. 또한 응용 프로그램이 커널 공간을 접근할 수 없도록 시스템의 실행모드를 사용자 모드와 커널 모드로 나누었다. 또한 응용 프로그램은 사용자 모드에서만 실행, 커널 코드는 커널 모드에서만 실행하도록 나누었다.

32비트 Windows 운영체제에서 전체 4GB의 메모리 영역에 대해 하위 2GB는 사용자 공간, 상위 2GB는 커널 공간으로 나뉜다.

이렇게 메모리를 사용자 공간과 커널 공간으로 나누는 이유는 응용 프로그램으로부터 커널 코드와 데이터를 지키기 위함이다. 커널이 개방되어 있으면 바이러스 침범, 시스템 훼손, 시스템 중단등의 심각한 문제가 발생할 수 있기 때문이다.

운영체제(Operating System)

운영체제는 컴퓨터의 하드웨어를 관리하며, 사용자가 컴퓨터를 쉽고 편리하게 사용할 수 있도록 도와주는 시스템 소프트웨어

컴퓨터(Computer)

여기서 컴퓨터란 다양한 연산을 수행하고 데이터를 처리할 수 있는 기계로, 일반적인 PC뿐만 아니라 노트북, 스마트폰, 태블릿 등 다양한 전자 장치를 포함한다.

운영체제의 종류

MacOS, iOS, iPadOS, watchOS, Linux, Window, Android 등이 있다.

운영체제의 역할

운영체제가 존재하는 이유는 1. 사용자의 컴퓨터 사용 편리성과 2. 자원의 효율적 사용 및 관리 이다.

컴퓨터를 구성하는 자원

하드웨어 자원 - 키보드, 마우스, 프린터, CPU, 메모리(RAM) ... 소프트웨어 자원 - 응용 프로그램 데이터 자원 - 파일, DB ...

따라서 운영체제는 아래와 같은 역할을 한다.

1. 프로세스 관리

프로세스(Process)

컴퓨터에서 실행중인 프로그램

운영체제는 프로세스 실행, 프로세스 생성과 종료, 스케줄링, 프로세스간의 통신과 동기화 기능도 제공한다.

2. 메모리 관리

각 프로세스에 적절한 메모리를 할당하고 반환한다. 또한 프로세스에 할당 된 메모리를 다른 프로세스로부터 보호, 메모리가 부족할 경우 가상 메모리 기능을 수행한다.

3. 파일 시스템 관리

운영체제만이 파일이 기록된 위치를 알수있기 때문에 운영체제는 파일의 정보, 파일과 디렉터리 생성 및 관리, 파일에 대한 접근권한 등의 파일을 다루는 모든 기능을 수행한다.

4. 입출력(I/O) 장치 관리

마우스, 키보드등의 다양한 입출력 장치들을 제어한다.

5. 보안 관리

시스템에 접근하는 사용자를 인증하거나 시스템 자원에 대한 접근 권한을 설정하고, 관리함으로써 컴퓨터 시스템과 사용자 정보를 보호한다.

6. 네트워킹

네트워크 장치를 관리하고 다양한 네트워크 기능을 지원한다.

7. 사용자 인터페이스 제공

CLI : 텍스트 명령을 통해 시스템과 상호작용할 수 있는 인터페이스를 제공한다. GUI : 그래픽 요소를 통해 사용자와 상호작용할 수 있는 인터페이스를 제공한다.

처음에 윗 예시처럼 quack / quack이라 두마리인줄 알았는데 알고보니 연속된 quack은 한마리였던거임!! 그리고 울음소리를 전부 사용해야 한다는 부분이 좀 헷갈렸다.

그래서 우선 정상적인 울음소리가 아닌 경우

• q로 시작하지 않거나
• k로 끝나지 않거나
• 울음소리 전체가 5로 나누어떨어지지 않으면
• 1을 출력해주었다.

  duckSound[0] != "q" || duckSound[soundCnt-1] != "k" || soundCnt % 5 != 0

울음 소리의 수는 맞지만 윗 예시처럼 이상한 울음소리를 거르기 위해 아래와 같은 조건 추가

if duckSound[i] == "q" && visited[i] == 0 {
            getDuckCnt(i)
        }

getDuckCnt

여기서는 quack 배열을 만들고, quack 전용 idx를 만들어서 울음소리와 quack을 하나씩 비교하고 방문 처리 새로운 오리인지 아닌지 확인해주는 변수를 추가 만약에 새로운 오리라면 duckCnt += 1해주고 isNewDuck = false 바꿔주면서 k 다음 q가 오는 한마리의 오리가 우는 상황을 대비

func getDuckCnt(_ start: Int) {
    var idx = 0 //quack용 index
    var isNewDuck = true //새로운 오리인지 아닌지
    for i in start..<soundCnt {
        if duckSound[i] == quack[idx] && visited[i] == 0 {
            idx += 1
            visited[i] = 1
            if duckSound[i] == "k" {
                idx = 0
                if isNewDuck {
                    duckCnt += 1
                    isNewDuck = false
                }
            }
        }
    }
}

오리의 수가 0이거나 방문하지 않은 울음소리가 있다면 이 또한 정상적인 울음소리가 아니기 때문에 -1

if duckCnt == 0 || visited.contains(0) {
        print(-1)
    } else {
        print(duckCnt)
    }

전체 코드

func getDuckCnt(_ start: Int) {
    var idx = 0 //quack용 index
    var isNewDuck = true //새로운 오리인지 아닌지
    for i in start..<soundCnt {
        if duckSound[i] == quack[idx] && visited[i] == 0 {
            idx += 1
            visited[i] = 1
            if duckSound[i] == "k" {
                idx = 0
                if isNewDuck {
                    duckCnt += 1
                    isNewDuck = false
                }
            }
        }
    }
}

let duckSound = readLine()!.map { String($0) }
let soundCnt = duckSound.count
var visited = Array(repeating: 0, count: soundCnt)
let quack = ["q", "u", "a", "c", "k"]
var duckCnt = 0 // 출력해야 할 오리 수

if duckSound[0] != "q" || duckSound[soundCnt-1] != "k" || soundCnt % 5 != 0 {
    print(-1)
} else {
    for i in 0..<soundCnt {
        if duckSound[i] == "q" && visited[i] == 0 {
            getDuckCnt(i)
        }
    }
    if duckCnt == 0 || visited.contains(0) {
        print(-1)
    } else {
        print(duckCnt)
    }
}

그래프(Graph)

정점(노드)과 정점을 연결하는 간선(edge)의 집합으로 구성된 자료구조

지난 포스팅에서 다루었던 트리도 그래프의 일종입니다.

• 정점(Vertex): 그래프의 구성 요소 중 하나로, 노드(Node)라고도 불리고, 데이터를 저장할 수 있다.

• 간선(Edge): 그래프의 두 정점을 연결하는 선으로, 노드들 간의 관계를 나타냅니다. 간선에는 방향성이 있는 방향 그래프와 방향성이 없는 무방향 그래프가 있습니다.

그래프의 종류

1. 무방향 그래프(Undirected Graph)
2. 방향 그래프(Directed Graph)
3. 가중치 그래프(Weighted Graph) ...

무방향 그래프(Undirected Graph)

간선에 방향이 없는 그래프이다.

방향 그래프(Directed Graph)

간선에 방향이 있는 그래프이다. 따라서 간선은 한 정점에서 다른 정점으로만 방향성을 가진다.

가중치 그래프(Weighted Graph)

간선에 가중치(또는 비용)가 있는 그래프입니다. 각 간선은 양의 가중치 또는 음의 가중치를 가질 수 있다.

그래프 표현 방법

1. 인접 행렬(Adjacency Matrix)
2. 인접 리스트(Adjacency List)

인접 행렬(Adjacency Matrix)

2차원 배열을 사용하여 그래프의 연결 관계를 나타낸다. 만약 노드에서 노드로 이동이 가능하다면 1로, 아니라면 0으로 표기한다.

우선 무방향 그래프는 대각선을 기준으로 대칭인 특성을 가진다.

      A
     / \
    B - C

    A  B  C
A [0, 1, 1]
B [1, 0, 1]
C [1, 1, 0]

방향 그래프는 대칭성이 없다.

    A  →  B
   ↗︎  ↙︎  ↓
  C  →  D

   A  B  C  D
A [0, 1, 1, 0]
B [0, 0, 0, 1]
C [0, 0, 0, 1]
D [0, 0, 0, 0]

인접 리스트(Adjacency List)

각 정점마다 해당 정점과 인접한 정점들을 연결 리스트 형태로 저장한다.

    A
   / \
  B - C

A: [B, C]
B: [A, C]
C: [A, B]

    A  →  B
      ↙︎  ↓
  C  →  D

 A: [B]
B: [C, D]
C: [D]
D: []

인접행렬과 인접리스트의 장단점

인접 행렬 장점

• 두 정점 사이의 연결 여부를 상수 시간(O(1)) 내에 확인할 수 있다.
• 간선의 수가 정점의 수에 비해 많은 경우에 효율적이다.

인접 행렬 단점

• 무조건 2차원 배열을 사용해야하므로 메모리 낭비가 발생한다.

인접 리스트 장점

• 간선의 수가 정점의 수에 비해 적은 경우에 효율적이다.
• 연결된 정점들만을 저장하기 때문에 메모리를 절약할 수 있다.

인접 리스트 장점

• 특정 두 노드가 연결되었는지 확인하기 위해 연결 리스트를 순회해야하므로 시간이 인접 행렬에 비해 오래 걸린다.

트리(Tree)

계층적인 구조를 나타내는 비선형 자료 구조

트리의 구조

노드 : 트리에서 데이터를 구성하는 각 요소을 노드라고 한다.

루트 노드: 트리의 가장 상위에 있는 노드를 루트(root) 노드이다.

부모 노드: 어떤 노드에 연결된 상위 노드를 해당 노드의 부모 노드라고 한다.

자식 노드: 어떤 노드의 하위에 연결된 노드들을 해당 노드의 자식 노드라고 한다.

리프 노드: 자식 노드가 없는 노드, 리프 노드는 트리의 가장 하위에 위치해 있다.

간선(edge) : 노드를 연결하는 선

Level : 노드의 깊이

Depth : 트리에서 노드가 가질 수 있는 최대 Level

이러한 트리에는 이진 트리(Binary Tree), 이진 탐색 트리(Binary Search Tree), 힙(Heap), AVL 트리, B-트리 등 다양한 종류의 트리가 존재하는데...

이번 포스팅에서는 이진 탐색 트리를 구현해보겠다.

이진 트리(Binary Tree)

각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조

이진 탐색 트리(Binary Search Tree)

이진 탐색트리는 이진 트리에서 다음과 같은 조건이 붙은 트리이다.

• 각 노드의 왼쪽 서브 트리에 있는 모든 노드들의 값은 해당 노드의 값보다 작습니다.
• 각 노드의 오른쪽 서브 트리에 있는 모든 노드들의 값은 해당 노드의 값보다 큽니다.

Swift Code

Node Class

class Node<T> {
    var data: T
    var left: Node?
    var right: Node?

    init(data: T) {
        self.data = data
    }
}

BinarySearchTree Class

class BinarySearchTree<T: Comparable> {
    var root: Node<T>?

Insert

    func insert(data: T) {
        root = insertRecursive(root, data)
    }

    private func insertRecursive(_ node: Node<T>?, _ data: T) -> Node<T> {
        guard let node = node else {
            return Node(data: data)
        }

        // 현재 노드가 내 데이터보다 크면 왼쪽으로, 작으면 오른쪽으로 가면서 내 위치를 찾는다.
        if data < node.data {
            node.left = insertRecursive(node.left, data)
        } else {
            node.right = insertRecursive(node.right, data)
        }
        return node
    }
}

Search

    func search(_ data: T) -> Bool {
        return searchRecursive(root, data)
    }

    private func searchRecursive(_ node: Node<T>?, _ data: T) -> Bool {
        guard let node = node else {
            return false
        }

        if node.data == data {
            return true
        } else if data < node.data {
            return searchRecursive(node.left, data)
        } else {
            return searchRecursive(node.right, data)
        }
    }

let bst = BinarySearchTree<Int>()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(1)
bst.insert(4)
bst.insert(6)
bst.insert(9)

print(bst.search(4)) //true
print(bst.search(2)) //false

 ┌──9
┌──7
│ └──6
5
│ ┌──4
└──3
 └──1

 시각적으로 확인해보았다.
 이건 https://babbab2.tistory.com/90 여기 참고함

이진탐색 트리 GIF 자료 출처 https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)

배열(Array)

여러 개의 데이터 요소를 담을 수 있는 자료 구조

@frozen
struct Array<Element>

배열의 생성

// 'Int' 요소 배열
let oddNumbers = [1, 3, 5, 7, 9, 11, 13, 15]


// 'String' 요소 배열
let foods = ["Chicken", "Pizza", "Hamburger"]

// 빈 배열 만들기
var emptyFloats: Array<Float> = Array()
var emptyDoubles: [Double] = []
var emptyInts = [Int]()

// 기본값으로 초기화된 배열이 필요할 경우
var digitCounts = Array(repeating: 0, count: 10)
print(digitCounts)
// 출력 -> [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

배열 값에 접근

for - in을 사용해 배열 각각의 값에 접근할 수 있다.

let foods = ["Chicken", "Pizza", "Hamburger"]

for food in foods {
    print("I like \(food).")
}

// 출력 -> I like Chicken.
// 출력 -> I like Pizza.
// 출력 -> I like Hamburger.

isEmpty를 이용해 빈 배열인지 count를 사용해 배열 요소 개수를 쉽게 확인할 수 있다.

let emptyArray = [Int]()
let oddNumbers = [1, 3, 5, 7, 9, 11, 13, 15]

if emptyArray.isEmpty {
    print("배열이 비어있습니다.")
} else {
    print("배열에 \(oddNumbers.count)개의 값이 들어있습니다.")
}

// 출력 -> 배열이 비어있습니다.

if oddNumbers.isEmpty {
    print("배열이 비어있습니다.")
} else {
    print("배열에 \(oddNumbers.count)개의 값이 들어있습니다.")
}

// 출력 -> 배열에 8개의 값이 들어있습니다.

first를 이용해 배열의 첫번째 값, last를 이용해 마지막 값 가져올 수 있다.

let foods = ["Chicken", "Pizza", "Hamburger"]

if let firstElement = foods.first, let lastElement = foods.last {
    print(firstElement, lastElement, separator: ", ")
}

// 출력 -> Chicken, Hamburger

개별 요소에도 접근가능

let emptyArray = [Int]()
let foods = ["Chicken", "Pizza", "Hamburger"]

print(foods[1]) // Pizza
print(emptyArray[0]) // 빈 배열에 접근하면 에러발생

배열의 값 삽입, 삭제, 수정, 찾기

배열의 삽입

• append(_:) -> 배열 끝에 요소 삽입
• append(contentsOf:) -> 배열 끝에 배열 삽입
• insert(_:at:) -> 원하는 위치에 요소 삽입

  var fruits = ["Apple", "Mango", "Banana"]
  

fruits.append("Grape") fruits.append(contentsOf: ["Strawberry", "Blueberry"])

print(fruits) // ["Apple", "Mango", "Banana", "Grape", "Strawberry", "Blueberry"]

fruits.insert("Lemon", at: 3)

print(fruits) // ["Apple", "Mango", "Banana", "Lemon", "Grape", "Strawberry", "Blueberry"]

#### 배열의 삭제
- removeFirst() -> 첫번째 요소 삭제
- remove(at:) -> 특정 위치 요소 삭제
- removeLast() -> 마지막 요소 삭제

fruits.removeFirst() // ["Mango", "Banana", "Lemon", "Grape", "Strawberry", "Blueberry"]

fruits.remove(at: 3) // ["Mango", "Banana", "Lemon", "Strawberry", "Blueberry"]

fruits.removeLast() //["Mango", "Banana", "Lemon", "Strawberry"]

#### 배열의 수정
- 기존 요소를 새 값으로 바꿀 수 있다.

var fruits = ["Apple", "Mango", "Banana"]

if let i = fruits.firstIndex(of: "Mango") { fruits[i] = "Lemon" }

print(fruits) // ["Apple", "Lemon", "Banana"]

#### 배열의 요소 찾기
- contains() -> 지정된 요소가 포함되어있는지의 여부 (Bool값 반환)
- first -> 첫번째 요소 반환
- firstIndex(of:) -> 지정된 값의 첫번째 인덱스 반환
- last -> 마지막 요소 반환

var fruits = ["Mango", "Banana", "Lemon", "Strawberry", "Blueberry"]

print(fruits.contains("Mango")) // true print(fruits.first!) // Mango print(fruits.firstIndex(of: "Lemon")!) // 2 print(fruits.last!) // Blueberry

- - -

### 배열의 정렬
#### sort() -> 배열을 직접 변경하여 정렬

var numbers = [5, 2, 7, 1, 9] numbers.sort() print(numbers) // [1, 2, 5, 7, 9]

#### sorted() -> 정렬된 새로운 배열을 반환

var numbers = [5, 2, 7, 1, 9] var sortedNumbers = numbers.sorted() print(sortedNumbers) // [1, 2, 5, 7, 9]

#### 오름차순, 내림차순 정렬

var numbers = [5, 2, 7, 1, 9]

numbers.sort(by: <) print(numbers) // [1, 2, 5, 7, 9]

numbers.sort(by: >) print(numbers) // [9, 7, 5, 2, 1]

```

참고자료 https://developer.apple.com/documentation/swift/array

우선 이 문제에 대한 내 계획은! pat의 마지막 원소의 위치를 찾아서, 처음부터 pat의 마지막 원소까지 출력하기였다.

    let end = pat.suffix(1)
    let lastIndex = myString.lastIndex(of: end)
    return myString[0...lastIndex]

이런 느낌을 원했는데,,

error: cannot convert value of type 'String.SubSequence' (aka 'Substring') to expected argument type 'String.Element' (aka 'Character')

음 우선 lastIndex(of:)를 사용하기 위해 String.SubSequence인 end값을 Character로 변환해주었다. 그리고 distance(from:to:)는 from과 to의 거리를 리턴해주는데 이걸 사용해서 거리를 구하고 prefix + 1을 통해 결과를 도출해냈다. prefix + 1을 한 이유는 prefix는 문자열의 길이만큼만 가져오기 때문이다.

func solution(_ myString:String, _ pat:String) -> String {
    let end = Character(String(pat.suffix(1)))
    if let lastIndex = myString.lastIndex(of: end) {
        let idx = myString.distance(from: myString.startIndex, to: lastIndex)
        let res = myString.prefix(idx+1)
        return String(res)
    }
    return ""
}

문자열과 관련된 공부를 좀 더 깊게 해봐야겠다.