분류 전체보기
-
OS: 프로그램의 구조, 인터럽트, Syscall, 프로세스 실행 상태os 운영체제 2024. 3. 28. 18:58
프로그램의 구조: 프로그램이 CPU에서 명령을 수행하려면 해당 명령을 담은 프로그램의 주소가 메모리에 올라가 있어야 함. 프로그램의 주소 영역: 코드 : 프로그램 함수들의 코드가 기계어 명령 형태로 변환되어 저장되는 부분 데이터 : 전역 변수등 프로그램이 사용하는 데이터는 저장하는 부분 스택 : 함수가 호출될 때 호출된 함수의 수행을 마치고 복귀할 주소 및 데이터를 임시로 저장하는 부분 인터럽트: 인터럽트 때문에 CPU를 빼앗긴 위치는 운영체제가 관리하는 PCB(프로세스 제어 블록)에 저장됨 인터럽트가 발생하면 PCB에 해당 프로그램의 수행 위치를 저장. 인터럽트 처리 후 PCB에 저장된 주소를 복원시켜 원래 하던 일을 재개. CPU는 PC가 가리키는 메모리 위치의 프로그램을 수행한다. CPU가 운영체제..
-
OS: 스풀, CISC, 데드락os 운영체제 2024. 3. 27. 21:08
스풀(Simultaneous Peripheral Operation On-Line): CPU와 IO가 독립적으로 동작하도록 함, I/O가 CPU보다 느림 -> 대기시간 발생 -> 이를 해결하기 위해 스풀러가 고안됨 스풀러는 디스크를 매우 커다란 버퍼로 사용함 (원래는 메인메모리를 버퍼로 사용) 다중 프로그래밍 환경에서 다수의 프로세스들이 서로 입출력 장치를 요구하거나 그 장치의 수가 제한 되어 있는 경우 이를 공유하기 위해 가상장치를 각 프로세스에게 제공해준다. CPU와 I/O가 혼합된 작업의 경우, I/O의 처리를 기다리지 않고 이를 가상장치를 통해 디스크에 넣어둔 다음, CPU가 다른 작업을 수행할 수 있게 한다 스풀링은 스풀을 적용하는 것 또는 스풀을 위해 마련된 저장공간을 채우는 동작을 뜻한다. ..
-
알고리즘: (BIT 부분 합, 누적 합)알고리즘 2024. 3. 27. 18:45
부분 합:A[n]배열이 있을 때, a,b (0A[a]~A[b]까지 더하는 문제. 1. Brute-force1. 순회하여 부분 합을 구한다. 전처리: x시간복잡도: O(n) 2. O(n) 전처리, O(sqrt(n)) 질의1. 배열 A를 sqrt(n)개의 원소씩 그룹으로 묶음2. 각각의 합을 구함3. a, b가 주어지면 양 끝부분의 합만 직접 구하고 중간 부분은 미리 구한 합을 더해줌 전처리: O(n)시간복잡도: O(sqrt(n)) 전처리 후 sqrt(n)개의 그룹, worst case: a=1, b=n-1 중간 값을 처리하는 시간복잡도: sqrt(n)-2 (총 그룹의 수-양 끝의 2그룹) 양 끝 값을 처리하는 시간복잡도: 2sqrt(n) (양 그룹의 원소의 수) 총 시간 복잡도..
-
컴퓨터 네트워크 4주차: p2p, BitTorrent, DHT교내 강의/컴퓨터 네트워크 2024. 3. 27. 16:11
서버-클라이언트의 구조의 경우: 서버 입장에서 n개의 클라이언트들에게 파일을 업로드 할 때의 속도: nF/u(파일의 크기/업로드 속도) 클라이언트 입장에서 하나의 파일 다운 속도: F/d(파일의 크기/minimum download rate 둘 중 더 큰 값이 최종적으로 서버->n개의 클라이언트에게 파일을 보내고 다운받는 속도가 된다. P2P 구조의 경우: 서버 역할 peer의 업로드: F/u 클라이언트 역할 peer의 다운로드 F/d n개의 클라이언트가 받는 총 용량 nF에서 이때의 max upload rate: u + ∑u 위 세개의 속도 중 제일 큰 값이 최종적으로 서버->n개의 클라이언트에게 파일을 보내고 다운받는 속도가 된다. server-client는 서버가 파일을 하나씩 다 올려야하고, P2P..
-
알고리즘: RMQ알고리즘 2024. 3. 25. 21:03
RMQ(Range Minimum Query): (query란 단어의 뜻은 문의하다, 질문하다) 참고자료 숫자가 n개 있는 배열이 하나 있고, 해결해야 하는 (l,r)의 쿼리가 q개 들어오는 상황 기준 1. Brute Force q(l,r)일 때 l부터 r까지 전부 훑어서 RMQ를 찾음. 전처리: x 시간 복잡도: O(n) 업데이트: O(n) 직관적이고 쉬움, 배열의 값을 업데이트하는 것이 자유로움. 2. 미리 전부 전처리 전처리로 테이블을 미리 만들어 놓고 테이블에서 가져옴 전처리: O(n^2) 시간복잡도: O(1) 업데이트: O(n^2) 시간복잡도가 낮으나 전처리가 길고, 배열의 값을 하나만 바꿔도 테이블을 O(n^2)을 들여 만들어야 함 3. Sqrt Decomposition root(n)개로 n을 ..
-
컴퓨터 구조: 어드레싱 모드란?os 운영체제 2024. 3. 25. 18:50
어드레싱 모드: https://skagh.tistory.com/8 참고 즉시 어드레싱(Direct Addressing): 명령어가 operand(피연산자)를 포함. ex) ADD 5 빠르지만 수에 제한이 있음 직접 어드레싱(Indirect Addressing): 명령어에 메모리주소(->데이터)를 포함. ex) ADD a 주소 공간을 쉽게 바꿀 수 있지만 주소 공간이 제한됨 간접 어드레싱(Indirect Addressing): 주소->메모리주소->데이터 ex. ADD (A) 주소 공간이 커지지만 실행에 2번의 메모리 접근 = 느림. 레지스터 어드레싱(Register Addressing): 명령어에 레지스터주소(->데이터). 장점 : 명령어의 주소필드가 작아도 됨. 메모리 접근이 없다. 매우 빠르다 단점 :..