전체 글

buffer: 임시 저장 공간, buffer 조작은 포인터 이동(빈 버퍼 혹은 찬 버퍼 가리킴) 여러 생산자가 동시에 빈 버퍼에 접근, 혹은 여러 소비자가 동시에 공유 데이터에 접근 시 문제 발생 -> lock/unlock 버퍼가 모두 찼을때 생산자가 오거나 버퍼가 모두 비어있을때 소비자가 왔을때 문제 발생 -> counting writer 접근 시, 다른 writer와 모든 reader 접근 불가 reader 접근 시, 모든 writer 접근 불가 읽는 작업도 배타적으로하면 매우 비효율적 여러 reader가 동시에 도착하면 공유변수 readcount이 중복계산될 수 있으므로 lock/unlock 최초 reader는 DB에 writer 접근 못하게 막고, 최후 reader는 DB에 writer 접근 허용..

Semaphores 프로그래머가 이렇게 lock/unlock 관련한 코드를 고민하기 어려우므로 앞의 방식들을 추상화한다 Semaphore S integer variable (자원의 수) (이전의 알고리즘들은 S=1인 경우라고 생각할 수 있다) 아래 두가지 atomic 연산에 의해서만 접근 가능 critical section을 수행중인 다른 프로세스를 CPU ready queue가 아닌 semaphore에 대한 wait queue에서 대기 이 연산에서 S 변수는 S가 양수면 기다리는 프로세스가 없다는 것, 음수면 기다리고 있다는 의미 (위에서와 다름) critical section의 길이가 긴 경우 block/wakeup이 좋음 critical section의 길이가 매우 짧은 경우 block/wakeup..

데이터 공유 상황에서 누가 언제 어떤 데이터를 읽고 연산했는지에 따라 원하지 않는 결과가 나올 수 있기 때문에 그에 맞는 처리 필요 커널모드에서 1까지 수행하다가 인터럽트가 걸린다면 count가 감소한 작업은 인터럽트 처리 이후, 이전에 불러온 count값을 연산한 값으로 덮어씌워지므로 증가한 결과값만 남게 된다 해결: 중요한 변수를 다루는 동안에는 인터럽트가 걸려도 그 작업을 마칠때까지 인터럽트 처리 보류 real time 시스템의 엄밀한 상황이 아닌 time sharing 시스템이므로 이렇게 쉽게 해결하고 가는 것이 좋다 효율: CPU lock/unlock Test_and_set() 출처: https://core.ewha.ac.kr/publicview/C0101020140401134252676046?..

큐를 나누고, CPU는 어느 큐를 먼저 고를지, 그리고 그 큐에서 어떤 프로세스를 먼저 고를지 스케줄링 CPU 사용시간이 적은 프로세스에 RR보다 더 큰 우선순위 부여 기타 상황에서의 CPU 스케줄링 Real-Time Scheduling Hard real-time systems: Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링 Soft real-tme computing: Soft real-time task는 일반 프로세스에 비해 높은 우선순위를 갖도록 스케줄링 Thread Scheduling Local scheduling: user level thread는 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정 Global scheduling:..

CPU burst: 프로세스 실행 과정 중 CPU의 제어권을 얻어 연속적으로 인스트럭션을 실행하는 단계 I/O burst: CPU 제어권을 잃고 I/O를 실행하는 단계 CPU bound job: 계산 위주의 job (few very long CPU bursts) I/O bound job: CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job (many short CPU bursts) 중요 용어: nonpreemtive(비선점형), preemtive(선점형) 시스템 입장에서: CPU utilization, Throughput 프로그램 입장에서: Turnaround time, Waiting time, Response time 선점형 스케줄링에서 대기 시간은 여러번 있을 수 있지만 응답 시간은 ..

최단 경로 문제: 각 간선의 가중치 합이 최소가 되는 두 정점(또는 노드) 사이의 경로를 찾는 문제 정점: 교차로, 간선: 길, 가중치: 거리 & 시간 등의 이동 비용 다익스트라 알고리즘: 항상 노드 주변의 최단 경로만을 택하는 대표적인 그리디 알고리즘 -> BFS 이용 임의의 정점을 출발 집합에 더할 때, 그 정점까지의 최단거리는 계산이 끝났다는 확신을 가지고 더한다 743. network delay time - 다익스트라 알고리즘 -> 시작점에서 각 노드까지 최단시간 계산하고 저장(BFS) 및 계산되지 않는 노드 여부 확인 heapq 모듈에는 우선순위 업데이트 기능 없음 이전 노드의 값이 무엇인지 필요없으므로 생략 787. cheapest flights within k stops - 다익스트라 알고리..

프로세스 생성: 부모 프로세스가 자식 프로세스 생성 -> 트리(계층 구조) 형성 프로세스는 자원을 필요로 함 (OS로부터 or 부모와 공유) 자원의 공유 Copy-on-write(COW): write하기 전까지는 부모와 자원을 공유하다가 이후 copy write하게 되면 본래의 내용이 바뀌게 됨 부모와 자식이 모든 자원을 공유하는 모델 일부를 공유하는 모델 전혀 공유하지 않는 모델 수행(execution) 부모 자식이 공존하며 수행되는 모델 자식이 종료될 때까지 부모가 기다리는 모델 주소 공간 자식은 부모의 공간 복사 (binary and OS data) 자식은 그 공간에 새로운 프로그램을 올림 유닉스의 예 fork() 시스템 콜이 새로운 프로세스 생성 이후 exec() 시스템 콜을 통해 새로운 프로그램..

그래프: 객체의 일부 쌍들이 연관되어 있는 객체 집합 구조 오일러 경로: 모든 간선(edge)을 한 번씩 방문하는 유한 그래프 경로(= 한붓그리기) 모든 정점(vertex)이 짝수 개의 차수(degree)를 갖는다면 오일러 경로 해밀턴 경로: 각 정점을 한 번씩 방문하는 무향 또는 유향 그래프 경로 최적 알고리즘이 없는 대표적인 NP-완전 문제 (NP문제 중 NP-난해 문제) 해밀턴 순환: 원래의 출발점으로 돌아오는 경로 외판원 문제: 최단거리인 해밀턴 순환을 찾는 문제 -> 다이나믹 프로그래밍으로 최적화 그래프 순회 (그래프 탐색): 그래프의 각 정점을 방문하는 과정 깊이 우선 탐색(DFS)이 너비 우선 남색(BFS)에 비해 더 널리 쓰임 DFS는 주로 스택이나 재귀로 구현(재귀 선호), BFS는 주로..

Thread (lightweight process): CPU의 수행 단위 thread의 구성: program counter, register set, stack space (CPU 수행 관련 정보) thread끼리 공유하는 부분(=task): code section, data section, OS resources heavyweight process: 하나의 thread 다중 스레드로 구성되면 하나의 서버 스레드가 blocked 상태여도 다른 스레드가 실행되어 빠른 처리 가능 동일한 일을 수행하는 다중 스레드가 협력하여 높은 처리율과 성능 향상 동일한 일을 수행하는 프로세스를 여러개 실행하면 메모리 낭비가 심함 스레드 생성, CPU switching이 프로세스 생성, context switching보다 ..

프로세스: 실행중인 프로그램 프로세스의 맥락(context) CPU 수행 상태를 나타내는 하드웨어: Program counter, 각종 레지스터 PC가 어떤 코드를 가리키는가, 레지스터에 어떤 정보를 담고 있는가 프로세스의 주소 공간: code, data, stack 프로세스 관련 커널 자료 구조: PCB(Process Control Block), kernel stack 프로세스가 실행 될 때마다 각각 별도로 PCB를 data에 두고 관리 A의 코드 실행 중에 함수 호출이 일어나면 본인의 스택에 그 함수를 호출하고 리턴 후 관련 정보 쌓음 A 본인이 스스로 할 수 없는 것을 OS에 요청하면(시스템콜) 그와 관련되어 실행되는 커널에서의 코드가 함수를 호출하면 A의 커널 스택에 개별적으로 쌓고 관리 프로세스..